machine learning system designers

Abstract: Generative lossy compression combines a rate-limited representation with a stochastic decoder that preserves source-dependent information while generating unresolved detail. We ask what remains reusable when a rate-distortion-perception (RDP) system selected for one operating point is transferred to a prescribed conditional-generation task. We distinguish the single-letter RDP factorization from its block-code implementation and compare Full Redesign with three increasingly restrictive transfer strategies. Renderer-Only Transfer retains only the renderer and redesigns semantic steering. Representation-Induced Transfer additionally retains the semantic latent law induced by the original representation. Full-Model Transfer retains a compatible RDP code, marginalizing over the task conditional law to form its semantic encoder. For finite alphabets, we characterize Renderer-Only Transfer's exact compression-common-randomness rate region, renderer-hull controllability condition, and compression-rate penalty relative to Full Redesign. Under unlimited common randomness, this penalty is the minimum residual semantic information $I(S;U|X)$ forced by the inherited renderer. Representation-Induced Transfer is exact if and only if the semantic condition depends on the source only through the recurrent-class label $C$ of the end-to-end RDP test channel. Every compatible RDP code reused under Full-Model Transfer preserves $C$ and supports every task satisfying $X-C-S$. Any additionally transferable within-class semantic dependence must satisfy $I(S;X|C)\le R_0-H(C)$, where $R_0$ is the inherited compression rate. The bound is exact when $R_0=H(C)$. A scalar Gaussian specialization yields a renderer-noise controllability threshold, a closed-form transfer penalty, and examples of identical Gaussian RDP test channels with different Renderer-Only Transfer capabilities.

Abstract: How depth and width of neural networks shape learned representations is usually studied only after training. We show that, in a tractable feature-learning setting, this dependence can instead be obtained in closed form. Using neural collapse as a probe of representation geometry, we express NC1--NC3 directly in terms of the learned feature kernel, extending an identity known for NC1 to the angular part of NC2 and to NC3 under a ridge readout. For deep linear networks with exchangeable class structure, the resulting kernel equations yield a geometric law, exact within the theory, for the layerwise evolution of within-class variability. At large width, the accumulated compression becomes a function of the depth-to-width ratio $L/N$, with its rate determined self-consistently by the data, prior and architecture. Numerical experiments support the derived dependence on depth, width and signal-to-noise ratio. The result is a representation-level scaling law derived from feature-learning theory rather than fitted after training.

Abstract: Omniprediction is a learning guarantee which requires a single predictor to be competitive relative to the best hypothesis from a benchmark class for any loss chosen from a family of loss functions. Loss Outcome Indistinguishability (loss OI for short) is a stronger notion that implies omniprediction. It requires the predicted distribution on labels to be indistinguishable from the true distribution to tests that depend on the loss functions and the benchmark class. Multiaccuracy and multicalibration are multigroup fairness notions that generalize classical notions of calibration and accuracy in expectation. Most known learning algorithms for omniprediction (both for the standard notion and for strengthenings like loss OI) rely on some version of these multigroup fairness notions, or on an intermediate notion called calibrated multiaccuracy. We ask if this is necessary: Does omniprediction require some form of multigroup fairness? We show that the answer is no for (plain) omniprediction, and yes for loss OI. First, a sequence of works shows that multicalibration or calibrated multiaccuracy imply omniprediction. We rule out even a weak converse, by showing that omniprediction for proper losses does not imply even accuracy in expectation, a much weaker notion than any of calibration, multiaccuracy, or multicalibration. Second, prior work showed how to achieve loss OI from a combination of calibration and multiaccuracy. We show a converse: loss OI is equivalent to a form of calibrated multiaccuracy.

Abstract: Efficient vector retrieval requires both a corpus geometry that supports retrieving the right documents through vector similarity, and a query encoder that can embed queries near their desired documents in the embedding space. Recent work has studied geometric capacity through the lens of the minimum embedding dimension needed to realize all top-$k$ answer sets of $n$ documents. We study a different notion of geometric capacity--the maximum recall achievable for a frozen document index--and explore whether learned query encoders can reach this ceiling. On several real-world retrieval benchmarks, we show that retrieval quality of single-vector query encoders often lies far below what the document indices can support. Motivated by this observation, we give theoretical evidence that learning query encoders can be computationally hard. In particular, we construct a retrieval task that (1) admits a query encoder with perfect recall which is representable by a small one-hidden-layer ReLU network, but (2) any statistical-query learner (a class capturing learners that access training data through aggregate statistics) provably requires exponentially many statistical queries to achieve non-trivial recall advantage over the random baseline $k/n$. Taken together, our results suggest substantial unrealized geometric capacity in retrieval benchmarks and establish query encoder learnability as a possible barrier in embedding-based retrieval.

Abstract: Softmax attention is ubiquitous in modern machine learning, but its quadratic scaling with sequence length makes it costly. To reduce this cost, attention is often approximated with fast algorithms, which incur error but can still perform well in practice and on some inputs. At the same time, the growing diversity of attention applications makes approximation guarantees that do not depend on particular input structure a compelling target. For such uniform guarantees over all inputs, known runtime lower bounds rule out fast algorithms for near-exact attention, but leave open the practically important regime: is there an efficient algorithm with even a modest uniform approximation guarantee? We answer this question negatively. Under standard complexity-theoretic assumptions, no truly subquadratic algorithm can approximate attention with any nontrivial additive or relative guarantee uniformly over all inputs. This impossibility holds in the mildest parameter regime for which known algorithms do not already achieve strong approximation guarantees in near-linear time, and extends to practically relevant relaxations: even after polynomial preprocessing of the KV cache, no efficient algorithm can obtain a nontrivial uniform approximation guarantee, or identify a small set of keys receiving substantial attention under sparsity. Overall, our results settle the computational limits of uniform attention approximation.

Abstract: Stochastic reconfiguration (SR) is the standard optimizer for neural quantum states (NQS), but modern NQS often have far more parameters than Monte Carlo samples. We show that in this regime the diagonal shift is more than a numerical stabilizer. It acts as a statistical filter for finite-sample generalization. At a fixed wave function, SR is ridge regression from tangent features to the centered local energy. Its residual is the expressivity gap, the part of imaginary-time evolution outside the current tangent space. This gap is orthogonal to the tangent space in population, but finite batches make it act as noise that SR can overfit. The shift therefore balances shrinkage of useful update directions against variance from fitting sampled residuals. Exact diagnostics on a $4\times4$ Heisenberg graph separate two effects of overparameterization. Larger tangent spaces help when they reduce the expressivity gap, but they can hurt when they overfit a fixed gap. In a $100$-site transverse-field Ising family trained with a foundation NQS, validation risk is U-shaped in the shift while variance decreases, matching the noisy-ridge model. This view leads to multi-shift SR (MS-SR), which averages independent ridge solves at data-adaptive shifts to form a richer, lower-variance spectral filter. Checkpoint-local experiments show that MS-SR lowers validation risk and update variance relative to the fixed-shift SR baseline. We further compare MS-SR and SR in paired online training continuations, with independent endpoint energy evaluations and a separate update-cost benchmark.

Abstract: We show that there exists a class of boolean functions C such that $(i)$ there is a distribution-independent statistical query algorithm for learning C that makes a polynomial number of queries of inverse polynomial tolerance and $(ii)$ for any set of functions $Φ_1, \dots, Φ_r$ such that for all $f \in$ C we can write $f(x) = \text{sign} \left( \sum_{i = 1}^r w_i Φ_i(x) \right)$ for some set of weights $w_i \in \mathbb{R}$, we must have that $r \geq n^{ω(1)}$. This gives a superpolynomial separation between dimension complexity and the query complexity of distribution-free learning in the statistical query model, negatively answering a question of Feldman, Kamath, and Srebro [FKS26]. Our construction C is a subclass of DNFs, and the proof is a simple consequence of recent progress on agnostically learning conjunctions [DKR25,CPS26] and the work of Razborov and Sherstov on the sign rank of DNFs [RS10].