Statistical Learning Theory

Follow this topic Ask about this topic

Momentum

34 papers in the last four weeks, up 127% on the four weeks before. 0.3% of all new papers.

Jul 13Week of Sep 28

Latest papers 395

Jun 4, 2026math.ST

How abundant are good interpolators?

Let

S

be the set of unit norm linear classifiers

θ\in \mathbb{R}^d

which correctly classify every point of a labeled dataset

(X_i,y_i)_{i=1}^n

,

X_i \in \mathbb{R}^d

,

y_i \in \{-1,+1\}

, with a possibly negative margin

κ

fixed in advance. Under two natural data-generating distributions of the

(X,y)

pairs -- a Gaussian mixture model and a logistic model with Gaussian features -- and in the proportional regime

n/d \to α

with small enough

α

, we establish a large deviation principle on the event that a point

θ

chosen uniformly at random from

S

achieves a given generalization error, with high probability over the choice of the data. The associated large deviation rate function is deterministic and describes the proportion, at the exponential scale in

d

, of interpolating classifiers having a given desired performance. As a consequence, we establish the following concentration phenomenon: all but an exponentially small fraction of interpolating classifiers have approximately the same generalization performance given by the unique maximizer of this rate function. We numerically compare this maximizer to the performance of empirical risk minimization by gradient descent and to the performance of a natural linear program, both finding a point in

S

, and deduce that in the overparametrized regime of small

α

, these efficient procedures outperform the vast majority of interpolators, pointing to their nontrivial benign overfitting in this setting.

August Y. Chen, Ahmed El Alaoui

Cornell University, Department of Computer Science. Ithaca, NY, USA. · Cornell University, Department of Statistics and Data Science. Ithaca, NY, USA.

Benign Overfitting Statistical Learning Theory

Jun 4, 2026cs.LG

Tight list replicability bounds via a novel sphere covering theorem

In recent years, list replicability has emerged as a framework for formalizing reproducibility in learning theory. A central question is how the required list size relates to the accuracy parameter and natural complexity measures of the hypothesis class. To achieve sharp bounds on list replicability, we prove a novel topological sphere covering theorem, derived from the Borsuk-Ulam theorem. Specifically, if the

d

-sphere is covered by open sets, each of which lies in an open hemisphere, then

d+1

of these sets must have a common intersection. Using this result, we obtain a sharp bound on the relationship between list size and accuracy for VC classes. We also show that for large-margin half-spaces, provided the margin is not too large, the optimal list size equals the ambient dimension. However, when the margin is taken to be very large, we devise a replicable algorithm achieving the minimal list size of

\lceil d/2 \rceil + 1

.

Ari Blondal, Hamed Hatami, Pooya Hatami +2

McGill University · Ohio State University

ML Reproducibility Statistical Learning Theory

Jun 4, 2026cs.LG

Dead Directions: Geometric Singular Learning

Singular learning theory and information geometry study the same spaces: the former in resolved coordinates, the latter in original coordinates under a non-degeneracy assumption that overparameterised models violate. This paper carries one direction of the bridge between them, from Watanabe's invariants to Fisher geometry, through one primitive, the dead direction: a unit vector along which the Fisher metric degenerates, equivalently a direction crossing the analytic singular set along which the KL divergence keeps a zero of high order, its KL order set by how fast that divergence vanishes. Our central result recovers the KL order as the decay rate of the directional Fisher quadratic form approaching the singularity, in original coordinates, without a Hironaka resolution. A selection rule on smooth fibres translates this rate into Watanabe's single-direction contribution to the real log canonical threshold, and the recovery extends to multi-component crossings, multiplicity

m

, the singular fluctuation

ν

, prior-RLCT shifts, and tempered posteriors. We then carry the rate into a deep network: a multi-layer K-FAC factorisation writes each Fisher block as a product of activation- and gradient-side rates with a duality between them, instantiated at residual streams, layer normalisation, and attention. A quotient theorem carries the rate to the gauge quotient for optimizers whose update commutes with the group action; Adam's per-coordinate preconditioner fails that condition, so we construct DDCAdam, an equivariant Adam-family preconditioner, and prove the quotient rate along its trajectory. The result is a trajectory-rate readout of Watanabe's triple

(λ, m, ν)

from one checkpoint's forward and backward passes, without posterior sampling.

Tejas Pradeep Shirodkar

IIIT, Hyderabad

Information Geometry Singular Learning Theory Statistical Learning Theory

Jun 4, 2026cs.LG

Mitigating the Curse of Dimensionality in Uniform Convergence of Deep Neural Networks via Smooth Activations

This paper establishes a theoretical framework for the uniform convergence of smoothly activated deep neural network (DNN) estimators. While standard ReLU networks achieve minimax-optimal rates in the

L^2(P)

norm for various nonparametric regression tasks, we establish a theoretical lower bound demonstrating that least-squares ReLU estimators can suffer from the curse of dimensionality in their uniform convergence behavior. Motivated by the need for reliable uniform guarantees in downstream tasks requiring worst-case reliability, we address this limitation by analyzing smoothly activated DNNs (smooth DNNs), encompassing both feedforward and residual structures. We establish novel pseudo-dimension bounds, non-asymptotic approximation guarantees, and Hölder-norm bounds for the approximators of these models. Leveraging these results, we derive non-asymptotic uniform convergence rates for smooth DNN estimators across multiple statistical contexts, including Huber, least-squares, quantile, and logistic regression. We prove that smooth DNNs can mitigate the {curse of dimensionality} in uniform convergence by adaptively exploiting the low-dimensional hierarchical composition structure of the target function. Supported by both simulation studies and a real-world application, our results position smooth DNNs as a theoretically grounded and practically viable alternative to ReLU networks for statistical learning tasks requiring uniform guarantees.

Yizhe Ding, Runze Li, Jia Liu +1

Department of Statistics, The Pennsylvania State University

ReLU Neural Networks Neural Network Approximation Theory Statistical Learning Theory

Jun 3, 2026cs.LG

A prism hierarchy of learning regimes in large linear autoencoders

Theoretical studies of machine learning models commonly consider different limiting regimes in which the learning dynamics of gradient descent becomes theoretically tractable. It is, however, desirable to have a systematically obtained picture of qualitatively different extreme learning regimes for a particular type of models. In this paper we propose such a picture for large weight-tied linear autoencoders characterized by input and latent dimensions, initialization magnitude, and training set size. This model is nonlinear in the weights and its gradient flow does not have a general theoretical solution. We show that at the level of the formal loss-expansion hierarchy, its extreme regimes are naturally associated with faces of a triangular prism. In particular, there are five basic extreme regimes associated with the 2-faces of the prism: (1) large-data, (2) small-data, (3) mean-field, (4) narrow-latent, and (5) free. For regimes (1,2,3,4), we derive and rigorously characterize the limiting train and population dynamics under gradient flow, rigorously prove convergence to these limits, and get good agreement with experimental results. The resulting limits reveal spectral critical slowing, initialization-driven trapping away from the PCA optimum, and regimes in which population loss converges exponentially while training loss relaxes only algebraically.

Eugene Golikov, Yaroslav Gusev, Dmitry Yarotsky

Applied AI Institute Moscow, Russia · Steklov Mathematical Institute of Russsian Academy of Sciences Moscow, Russia

Autoencoders Neural Network Training Dynamics Statistical Learning Theory Gradient Descent Dynamics

Jun 3, 2026cs.LG

Mean-based algorithms: A lower bound and regret

Mean-based algorithms are online learning algorithms that assign low probability to actions with low average rewards. Recent research shows that they converge to serially undominated actions, which serve as approximations to Nash equilibria in economic games. However, empirical studies indicate that mean-based algorithms converge more slowly in bandit-feedback settings than established no-regret alternatives. This work investigates mean-based algorithms under unknown horizons and bandit feedback. In this setting, we provide the first lower bound on the algorithm-defining sequence

γ_t

, establishing a fundamental limit on the learning speed of such algorithms. In multi-armed bandit problems, this result constrains the rate at which any algorithm can reliably identify low-reward actions while acting according to this knowledge. We also propose two mean-based algorithms: one generalizes

ε

-greedy, and the other extends mean-based Exp3 to unknown horizons. Our experiments show that mean-based algorithms, although slightly slower, can perform competitively with other bandit-feedback algorithms. We further study the relationship to regret. Depending on the choice of

γ_t

, the intersection with no-regret algorithms is non-trivial, and we show that some algorithms are both mean-based and no-regret.

Julius Durmann, Amelie Kleber

Technical University of Munich

Multi-Armed Bandits Regret Minimization Statistical Learning Theory

Jun 3, 2026cs.LG

Prediction Under Imperfect Compression: A Theory of Approximate MDL

Minimum Description Length (MDL) formalizes the principle of Occam's razor by optimizing the total description length:

L(\mathrm{model})+L(\mathrm{data} \ | \ \mathrm{model})

. For sequential prediction, the MDL method repeatedly selects a model with a minimum objective score of the observed prefix for the next step prediction. Classical MDL prediction theory shows that exact optimization of the MDL objective indeed provides a strong compression guarantee that supports reliable prediction. However, practical machine learning usually can only find models by approximately optimizing the objective function. To bridge this gap, this paper addresses the following fundamental question: Under what forms of approximation and regularization does approximate MDL still guarantee reliable sequential prediction? This work offers a principled characterization. We prove that for any approximation with additive slack

C

of the more general form of the balanced MDL objective:

λ\cdot L(\mathrm{model})+L(\mathrm{data} \ | \ \mathrm{model})

, the cumulative expected squared prediction error is finite for all

λ\ge1

. The case

λ>1

is proved by an affinity-telescoping argument, while the boundary case

λ=1

is proved by a likelihood-ratio stopping argument based on exact static MDL bounds. Our results establish that classical MDL regularization remains robust to any fixed additive optimization error. Furthermore, we establish that our characterization of the approximate MDL framework is sharp: When

0<λ<1

, overfits can happen to incur infinite cumulative expected error in the universal class of estimable measures, and hence a strong form of model-complexity regularization is necessary. In addition, model selection may fail in every regularized regime

λ>0

, under multiplicative approximation, and thus, additive approximation is both sufficient and essential.

Qian Li, Xinyu Mao, Shang-Hua Teng +1

Shenzhen Research Institute of Big Data · University of Southern California

Minimum Description Length Approximation Algorithms Statistical Learning Theory Sequence Modeling

Jun 3, 2026stat.ML

Flatness and Generalization: Learning Multi-Index Models with Homogeneous Neural Networks

A common heuristic used to explain the generalization of first-order gradient methods on non-convex neural networks is that "flat interpolators generalize well" (Hochreiter and Schmidhuber, 1994; Keskar et al., 2017), where flatness can be measured by the trace of the Hessian of the empirical loss. However, Dinh et al. 2017) showed that, using symmetry of the network that can change flatness while keeping the population and empirical losses unchanged, any interpolator can be made sharper or flatter. This result makes the earlier heuristic statement vacuous. In this paper, we show that for learning an unknown multi-index model with

2

-layer non-convex homogeneous neural networks, there is a connection between flatness and generalization, despite the existence of symmetries. This connection pertains to the "flattest" interpolators, i.e., the interpolators that have orderwise minimum flatness among all interpolators. First, we show that there exists a natural class of non-generalizing interpolators whose flatness cannot be made closer to the flattest possible, even using symmetries. Second, we show that for data generated by a sum of single-index models, if the approximation error and label noise are low, any flattest interpolator achieves small population loss, i.e., the flattest interpolators always generalize. This establishes a direct link between flatness and generalization which applies to a large class of activations and realistic data distributions.

Harsh Vardhan, Hossein Taheri, Arya Mazumdar

Neural Network Generalization Flat Minima Statistical Learning Theory Feedforward Neural Networks Multi-Index Models

Jun 3, 2026cs.LG

The price of multi-group transductive learning

We show every multi-group learner in the transductive setting may incur a multiplicative penalty in its error rate on some group relative to the error rate achievable in the single-group setting, and the penalty can increasing linearly with the number of groups, up to roughly the square-root of the sample size. This stands in stark contrast to optimal multi-group learners in an analogous (group-realizable) statistical setting, where the penalty is always at most logarithmic in the sample size and independent of the number of groups.

Noah Bergam, Samuel Deng, Daniel Hsu

Columbia University

Transductive Learning Statistical Learning Theory

Jun 3, 2026cs.LG

Shortcomings and capacities of real-constrained neural networks in complex spaces

We find the asymptotic ratio between the storage capacities when enforcing real pre-activations in a complex hypothesis class as opposed to complex ones in the same class. We use weights drawn from the complex Gaussian, which converge asymptotically in norm to the square root of dimension almost surely. Our methods depend on Gardner volume-type comparisons at critical capacity. Our proof relies on an application of the Harish-Chandra-Itzykson-Zuber (HCIZ) formula, nonstandard in literature. With the HCIZ formula, we may obtain a more robust approximation for the final asymptotic ratio. This strategy is applicable to our work specifically since we integrate over the unitary and orthogonal compact manifolds, facilitated via the Weyl integration formula and the Haar measure.

Andrew Gracyk

Department of Mathematics Purdue University West Lafayette, IN 47907, United States

Complex-Valued Neural Networks Statistical Learning Theory

Jun 1, 2026cs.LG

A Doeblin-Anchored Contrastive Chart for Learning Markov Transition Kernels

Learning a Markov transition model is not merely conditional density estimation: the learned object must be a valid transition kernel before it is iterated in downstream dynamics. This paper introduces a Doeblin-anchored contrastive chart, a statistical-to-dynamical coordinate framework for learning transition kernels from contrastive objectives. Given a restart law and an anchor strength, the chart mixes the target transition with the restart law. The resulting anchored kernel is simultaneously a Doeblin-minorized Markov kernel, the positive conditional law in a binary contrastive experiment, and an explicitly invertible coordinate for the original transition law. We prove that the anchored contrastive risk identifies the anchored transition density and calibrates excess risk to density error. Since inversion of a learned score may produce a signed or unnormalized object, we introduce a measurable Markovization operator that restores kernel validity while preserving integrated

L^1

accuracy up to a constant factor. Oracle inequalities and Hölder--ReLU approximation bounds yield nonparametric rates for independent transition pairs. For stationary geometrically

β

-mixing trajectories, a conservative thinning-and-coupling extension yields the same reconstruction interface with an effective sample size. Occupancy-weighted perturbation bounds transfer one-step kernel error to finite-horizon marginal, path-law, and occupation-measure errors under explicit coverage.

Ao Xu

School of Artificial Intelligence Jilin University No. 2699, Qianjin Street, Chaoyang District Changchun 130012, China · Zhongguancun Academy Daniufang 2nd Ring Road, Haidian District Beijing 100094, China

Contrastive Learning Markov Models Statistical Learning Theory

Jun 1, 2026cs.LG

Network Learning with Semi-relaxed Gromov-Wasserstein

Estimating the generative mechanism of large-scale networks is a fundamental challenge in statistical machine learning. It requires the identification of the latent connectivity structure, which is in general an NP-hard combinatorial problem due to the absence of canonical node labels. We address this challenge by allowing for probabilistic couplings, thereby relaxing the assignment problem. Our estimation framework can be formulated as a semi-relaxed Gromov-Wasserstein objective and provides a low-dimensional representation of the generative structure. We solve this via a block-coordinate conditional gradient algorithm. Despite the relaxation, the resulting solution is typically deterministic: in fact, we show that the optimality gap between the relaxed solution and the deterministic assignment vanishes at rate

O(1/n)

, where

n

is the number of nodes. This allows for tractable recovery of the underlying model and enables rigorous statistical analysis: we establish consistency and minimax-optimal convergence rates for both stochastic block models and Holder-smooth graphons. Our implementation scales efficiently with

n

, as demonstrated on both synthetic and real-world datasets.

Charles Dufour, Ulysse Naepels, Leonardo V. Santoro

EPFL, Institute of Mathematics Lausanne, Switzerland

Graph Structure Learning Latent Variable Models Stochastic Block Model Statistical Learning Theory Optimal Transport

Jun 1, 2026stat.ML

Provable Data Scaling Law for Meta Learning via Complexity Minimization

Pre-training has become a fundamental paradigm in modern machine learning, with one of its key empirical benefits being reduced downstream sample complexity as the scale of pre-training data increases. However, existing theoretical frameworks for pre-training do not fully explain this phenomenon. In this paper, we introduce complexity minimization, a novel meta-representation learning framework designed to enable theoretical analysis of this scaling behavior, which learns representations by evaluating the downstream model complexity best suited to each domain and minimizing the worst-case such complexity across source domains. Our end-to-end theoretical analysis, spanning pre-training through downstream regression, shows that this framework provably captures this scaling behavior; in particular, we show that the error rate of few-shot adaptation improves as the amount of meta-training data grows. Empirically, we demonstrate that incorporating complexity regularization into existing meta-learning methods consistently improves downstream sample efficiency.

Kazuto Fukuchi, Ryuichiro Hataya, Kota Matsui

University of Tsukuba, Japan · RIKEN AIP, Japan · SB Intuitions Corp., Japan +3

Meta-Learning Few-Shot Learning Statistical Learning Theory Data-Efficient Learning

Jun 1, 2026cs.LG

Regime-Arrival Uncertainty in Generalization Bounds under Distribution Shift

The standard generalization bounds assume that the training and deployment distributions are the same, or are static, and don't consider regime switching environments where the ratio of calm vs crisis states is different. This paper proposes a framework that generalizes regime-aware models by quantifying the extra risk due to regime composition mismatch, when distribution shifts are Markov-switching. We obtain an exact decomposition, separating regime mismatch from regime sensitivity; we extend the bound to beta-mixing data using the effective sample size corrected for the spectral gap; and we show a minimax lower bound for synthetic data and on 25 years of global equity indices. The proposed penalty is an ex post realized generalization gap, whereas the training-only estimator does not show significant correlation: the feature geometry of crises can be detected, but not the temporal arrival. Thus, the framework is not a forecast machine. Forecasting the composition of the future regime is an open question in the rare cases of regime change.

Prince Poudel

Independent researcher.

Distribution Shift Robustness Statistical Learning Theory Temporal Distribution Shift Generalization Bounds

Jun 1, 2026cs.LG

Everywhere Learning: Artificial Intelligence with Pointwise Constraints

Everywhere learning is a new paradigm whereby Artificial Intelligence (AI) systems are trained to satisfy loss constraints with probability one over the data distribution. This is in contrast to the standard paradigm of training AI systems to minimize average losses. We develop an approximate duality theory to substantiate a generalization analysis that establishes the proximity between solutions of empirical and statistical everywhere learning problems. Our results show that dual variables reweigh the data distribution towards points in which loss constraints are more difficult to satisfy and that generalization is controlled by the mismatch between the concentration of mass of the data distribution and the concentration of mass on points where constraints are more difficult to satisfy. We further show that we can control generalization with a sparse L1 penalty on constraint relaxations. We illustrate the merits of everywhere learning with an experiment in agentic classification for language model tasks.

Ignacio Boero, Ignacio Hounie, Luiz Chamon +1

Department of Electrical and Systems Engineering, University of Pennsylvania · École polytechnique, Institut Polytechnique de Paris

Constrained Optimization Statistical Learning Theory

Jun 1, 2026cs.LG

Near-Optimal Machine Unlearning Utility for Smooth Strongly Convex Losses

Machine unlearning is motivated by legal and user-facing requirements to remove the influence of individuals' data from trained models, such as the right to be forgotten. Prior work has developed algorithms and error bounds for unlearning in smooth strongly convex stochastic optimization but the fundamental statistical cost of unlearning has remained unclear. We nearly resolve this problem by proving upper and lower bounds on the excess population risk of approximate

(\varepsilon, δ)

-unlearning; our bounds are tight up to a condition-number factor. For mean estimation over the unit ball, our upper and lower bounds match. In fact, our algorithm achieves

\varepsilon

-unlearning, which implies a notable separation between differential privacy and unlearning:

(\varepsilon, δ)

-unlearning has no statistical advantage over pure

\varepsilon

-unlearning. The optimal rate is the usual sampling error plus an unlearning penalty that interpolates between the retraining from scratch rate and an exponentially smaller term as

\varepsilon/d

grows, where

d

is the dimension of the model. The retraining penalty dominates the sampling error for large unlearning requests. In particular, retraining from scratch is information theoretically optimal up to

\varepsilon \lesssim d

. On the other hand, for

\varepsilon \gg d

and large unlearning requests, our

\varepsilon

-unlearning algorithm offers an exponential accuracy improvement over retraining the model from scratch and differentially private baselines.

Matthew Regehr, Gautam Kamath, Andrew Lowy

University of Waterloo · University of Waterloo and Vector Institute · CISPA Helmholtz Center for Information Security

Statistical Learning Theory Machine Unlearning

May 31, 2026cs.LO

How (and when) can you fit examples to logic-based hypothesis classes over infinite structures?

We study fitting problems, sometimes called ``training problems'', where we have a finite sample consisting of inputs and outputs, and we want to know whether there is a function in a certain class that could produce these outputs, exactly or approximately, on the given inputs. We focus on the computational and descriptive complexity of fitting for logically-defined classes in common decidable structures, like the real ordered field and Presburger arithmetic, and also for broader classes defined via combinatorial or model-theoretic properties. We isolate the complexity of these fitting problems, with particular attention to cases where we can use queries in a natural query language over the sample to determine whether a sample is fittable.

Michael Benedikt, Alessio Mansutti

University of Oxford, UK · IMDEA Software Institute, Spain

Statistical Learning Theory

May 31, 2026stat.ME

Measuring the Symmetry--Data Exchange Rate

Equivariance theory predicts that an architectural symmetry prior reduces sample complexity by a factor of |G|; this is widely cited but rarely measured as a scaling law with controls that separate the prior from its confounds. On a controlled C_n-symmetric task, we report three findings. First, a wrong-group control with identical orbit size and matched compute is worse than no constraint (joint pairwise CI [+0.79, +3.26] excludes zero, robust across estimators); misaligned constraint is actively harmful, not merely unhelpful. Second, an augmentation baseline equipped with test-time orbit averaging matches the equivariant model exactly -- bit-identical per-epoch validation curves across matched cells -- so the architecture-vs-augmentation gap is conditional on asymmetric test-time computation, not unconditional. Third, the relative exchange rate beta_diff = 1.28 is consistent in sign and order of magnitude with the theoretical 1.0 (single-level CI [+0.92, +2.05]); the more conservative two-level bootstrap (seeds x group sizes) widens this to [-0.63, +1.72], including zero, and a finer-N replication on a sqrt(2)-spaced grid is inconclusive (point estimate -0.82). The methodological contributions -- the relative-rate estimator that cancels the shared-difficulty confound, the wrong-group control, and a pre-specified failure taxonomy -- transfer to any inductive bias whose strength can be parameterised. Honest scoping: the primary estimator beta_diff was adopted post-hoc after the initial analysis revealed a positive-slope identifiability problem; the design was never externally pre-registered; and the headline number rests on an OLS slope over seven group sizes on a coarse N grid. This is an exploratory study, not a confirmatory measurement; the wrong-group result is the cleanest finding and the one we report with the most confidence. A registered replication on fresh seeds is future work.

Ahmed M. Adly

Independent Researcher · Egypt

Sample Complexity Equivariant Neural Networks Statistical Learning Theory

May 31, 2026stat.ME

Theoretical Analysis of Engression and Reverse Markov Engression

Engression is a recently proposed and effective framework for conditional distribution learning. Its multi-step Reverse Markov extension further improves generative flexibility by decomposing complex conditional sampling into sequential reverse transitions. Despite their strong empirical performance, rigorous finite-sample statistical guarantees for these methods remain unavailable. In this paper, under deep neural network parameterizations, we establish nonasymptotic convergence bounds for Engression by directly controlling the Energy Distance between the learned and target conditional distributions. For the Reverse Markov framework, we further develop an Energy-Distance-based chain rule that enables a rigorous analysis of error propagation across reverse steps. Our analysis yields corresponding excess-risk bounds that are near-optimal up to logarithmic factors relative to the classical minimax rate over a general Hölder class.

Jiaqi Huang, Gongjun Xu, Ji Zhu

Department of Statistics, University of Michigan · Ann Arbor, MI 48109, U.S.A.

Conditional Distribution Estimation Statistical Learning Theory Conditional Generative Modeling

May 30, 2026cs.LG

Semi-Supervised Learning with Noisy Proxy Covariates: Generalization Bounds and Distribution Regression

In many modern machine learning pipelines, abundant pretrained representations serve as noisy proxy covariates, while task-specific labels remain scarce. We study semi-supervised regression in this setting, and propose a simple two stage estimator that learns kernel eigenfeatures from all proxy covariates and fits a ridge predictor on labeled data. We derive finite sample bounds showing that fast labeled sample rates are recovered when proxy perturbation is controlled and unlabeled proxy covariates are sufficiently abundant. We also show that distribution regression is a direct special case, with analogous guarantees when the finite bag size is large enough. Experiments show consistent gains over supervised and semi-supervised baselines, especially in low label regimes.

Kwangho Kim, Jisu Kim

Department of Statistics, Korea University, Seoul, Korea · Department of Statistics, Seoul National University, Seoul, Korea

Kernel Ridge Regression Semi-Supervised Learning Statistical Learning Theory

May 29, 2026stat.ML

Is Zero-Shot Super-Resolution Possible in Operator Learning?

Neural operators are often reported to exhibit zero-shot super-resolution, a phenomenon in which a model trained on coarse grids produces accurate predictions on finer testing grids without additional retraining. Despite strong empirical evidence, the theoretical foundations of this phenomenon remain unclear. In this work, we provide a systematic theoretical study of zero-shot super-resolution in operator learning. We first show that zero-shot super-resolution can be information-theoretically impossible even in benign settings such as when the input functions are available over the entire continuum and the ground truth is a simple rank-one linear operator. We then identify H{" o}lder smoothness of the output functions as a sufficient condition for zero-shot super-resolution and derive corresponding generalization bounds. Finally, we also validate the identified failure modes through experimental results.

Unique Subedi, Ambuj Tewari

Department of Statistics, University of Michigan

Operator Learning Statistical Learning Theory Neural Operators Image Super-Resolution

May 29, 2026cs.LG

Beyond Additive Decompositions: Interpretability Through Separability

Interpretable machine learning requires models that are accurate and structurally faithful to the data. Existing explainability methods rely heavily on additive representations (e.g., Generalized Additive Models (GAMs), SHapley Additive exPlanations (SHAP), functional ANOVA), which can suffer from signal cancellation and off-support extrapolation in the presence of strong interactions. We propose Tensor Separation Learning (TSL), a regression model that learns a sum of rank-1 products of univariate per-feature functions via a stagewise greedy procedure with orthogonal refitting. By enforcing separability, TSL avoids the information loss inherent in additive projections caused by marginalizing higher-order interactions. The learned TSL model can be fully reconstructed from first-order partial dependence functions, up to constant factors. This stage-wise correspondence ensures that the resulting visualizations are faithful to the fitted components. We establish approximation-rate guarantees for functions with bounded mixed

p

-th order partial derivatives and demonstrate that TSL competes with black-box models on regression benchmarks.

Jinyang Liu, Munir Eberhardt Hiabu

Department of Mathematical Sciences, University of Copenhagen, Denmark.

Interpretable ML Statistical Learning Theory

May 29, 2026stat.ML

Hedging on the Frontier: Learning New Tasks with Few Samples

When a learner faces a new task with few samples, it must leverage any available side information. In practice, this often comes in the form of model evaluations on related tasks in public benchmarks. A key question then is how to model task relatedness such that it is both realistic and the benchmark evaluations lead to provable gains. Empirically, we observe that weak monotonicity is often approximately satisfied: if a model dominates another on many benchmarks, it also tends to outperform on the new task. We explore the statistical complexity of learning under (approximate) weak monotonicity, leveraging it within two learning paradigms: transfer learning and model selection aggregation. We show that not only can we prune the model class based on monotonicity, but we can also further adapt to the geometry of the available trade-offs by hedging on the frontier.

Tobias Wegel, Federico Di Gennaro, Geelon So +1

Department of Computer Science, ETH Zurich · Department of Computer Science and Engineering, UC San Diego

Few-Shot Learning Transfer Learning Statistical Learning Theory

May 28, 2026cs.LG

Universal Multiclass Transductive Online Learning

We consider the problem of universal transductive online classification with a possibly unbounded label space. This setting considers online learning, with the sequence of instances (without labels) known to the learner in advance. We say a concept class

\mathcal{H}

is learnable if there is a learning algorithm

\mathcal{A}

, such that for every realizable sequence, the number of mistakes made by

\mathcal{A}

grows at most sublinearly with the number of predictions. We characterize the learnability of this setting and show that there are only two possible optimal rates for the learnable classes: either bounded or increasing logarithmically. We introduce a new combinatorial structure, called ``Level-Constrained-Littlestone-Littlestone (LCLL) tree'', which, along with the indifference property, characterizes the learnability. We also extend the learnability result to the agnostic case and the case where only the stochastic process that generates the instance sequence is known.

Steve Hanneke, Hongao Wang

Department of Computer Science, Purdue University, West Lafayette, IN 47907, USA

Multiclass Classification Transductive Learning Classification Statistical Learning Theory

May 28, 2026cs.DS

On Language Generation in the Limit with Bounded Memory

We study language generation in the limit under bounded memory. In this task, a learner observes examples from an unknown target language one at a time and must eventually output only new valid examples. Prior work assumes access to the entire history, a strong assumption since realistic algorithms retain limited past information. Classical work in learning theory shows memory constraints dramatically alter learnability; we extend this to language generation. First, we study memoryless generators. Under a mild enumeration restriction, every countable collection of infinite languages remains generable without memory. Without this restriction, we exactly characterize when memoryless generation is possible. For finite collections, we characterize the optimal minimax density achievable by memoryless generators -- the best density guaranteed against any collection of a given size. This combinatorial bound relies on Sperner's theorem and symmetric chain decompositions. We further show that a sliding window of the last

W

examples does not improve this worst-case density, whereas allowing it to store

b

adaptively chosen past examples improves the achievable density for every

b \geq 1

. Finally, we revisit identification in the limit, where the learner must converge to a single correct hypothesis for the target language. We focus on its incremental variant, where the learner remembers only its previous guess. Here, although exact identification fails on a collection of just three languages, a mild relaxation requiring convergence to an ``approximate'' version of the target is achievable for every finite collection. These results show bounded memory affects these tasks differently: generation remains achievable for every countable collection, while density and identification are confined to finite collections, with guarantees weakening as the collection grows.

Jon Kleinberg, Anay Mehrotra, Amin Saberi +1

Cornell University · Stanford University · Google Research

Statistical Learning Theory Text Generation

May 28, 2026stat.ML

Diffusion Models Are Statistically Optimal for Learning Low-Dimensional Multi-Modal Distributions

Score-based diffusion models have demonstrated remarkable empirical success in learning high-dimensional distributions, particularly those exhibiting low-dimensional and multi-modal structures. However, theoretical understanding of their statistical efficiency remains limited. Existing theories typically rely on strong regularity assumptions, such as uniformly bounded densities or globally smooth score functions, which fail to capture such intrinsic structures. In this work, we study the sample complexity of diffusion models for learning distributions supported on a union of low-dimensional subspaces. Assuming that the data distribution within each subspace is subgaussian, we show that diffusion models require at most

\widetilde{O}(\varepsilon^{-k \vee 2})

samples to achieve

\varepsilon

error in 1-Wasserstein distance, where

k

is the intrinsic dimension. This near-optimal convergence rate depends only on the intrinsic dimension and significantly improves upon prior theoretical guarantees that suffer from the curse of dimensionality. Notably, our analysis applies to a broad collection of distributions without imposing smoothness, bounded-density, or log-concavity assumptions. Overall, our results show that diffusion models can statistically adapt to intrinsic low-dimensional structure while naturally accommodating multi-modal data, offering a rigorous theoretical justification for their success in complex high-dimensional learning tasks.

Jingda Wu, Changxiao Cai

Department of Industrial and Operations Engineering, University of Michigan, Ann Arbor, USA.

Sample Complexity Statistical Learning Theory Diffusion Models

May 28, 2026cs.LG

Open Problem: Separating Geometric and Algorithmic Compression via Cayley-Table Completion

Modern statistical learning theory and deep learning characterize generalization primarily in terms of continuous capacity control (e.g., norm-based regularization, margin maximization, low-rank bias). While highly successful in continuous domains, deep learning consistently fails to extrapolate exact algorithmic or discrete algebraic rules, reflecting a missing inductive bias toward algorithmic complexity minimization. We propose the Cayley-table completion as the canonical testbed for this missing bias, serving as the discrete algebraic counterpart to matrix completion. Just as matrix factorization combined with weight decay yields an implicit geometric bias toward low linear rank, recent results demonstrate that operator-valued tensor factorizations paired with a flatness prior yield an implicit algorithmic bias toward exact discrete associativity. We pose the open problem of establishing formal exact recovery bounds for Cayley-table completion, and challenge the community to generalize continuous flatness priors to autonomously discover broader discrete algorithmic axioms without combinatorial search.

Dongsung Huh

Statistical Learning Theory Algorithmic Reasoning

May 28, 2026cs.LG

The Interplay Between Interpolation and Aggregation in Regression: Optimal Sample Complexity

This work investigates theoretically the interplay between interpolation and aggregation in regression. We establish that the

γ

-graph dimension characterizes learnability for a broad class of natural aggregation procedures. Furthermore, we prove that an extremely simple aggregation procedure, combining three interpolating hypotheses via the median, is optimal among all these aggregation procedures, and is strictly more powerful than proper learning. Finally, we show that some hypothesis classes are learnable only by aggregating infinitely many hypotheses or by using non-interpolating aggregation rules (which may predict outside the range of their inputs), and any finite interpolating aggregation fails to achieve even trivial performance.

Mikael Møller Høgsgaard, Kasper Green Larsen, Liang-Yu Zou

Department of Computer Science, Aarhus University, Aarhus, Denmark · Department of Statistics, University of Oxford, Oxford, United Kingdom

Statistical Learning Theory

May 27, 2026cs.LG

Principled Algorithms for Optimizing Generalized Metrics in Multi-Label Learning

Many real-world classification tasks require predicting multiple labels per instance, necessitating the optimization of complex evaluation metrics such as the

F

-measure and Jaccard index. While the Empirical Utility Maximization (EUM) framework is natural for these population-level metrics, existing theoretical results are largely limited to asymptotic Bayes-consistency. In this paper, we develop principled learning algorithms for optimizing a broad class of generalized metrics within the EUM framework, grounded in the stronger notion of

H

-consistency. Our key contribution is the design of novel surrogate loss functions for multi-label learning that admit provable

H

-consistency bounds, enabling optimization with non-asymptotic guarantees tailored to the hypothesis class and finite samples. Crucially, we prove these combinatorially formulated surrogates decompose exactly, operating in strictly

O(l)

time without approximations. Building on this foundation, we introduce MMO (Multi-Label Metric Optimization), a new family of algorithms for optimizing generalized linear-fractional metrics. We validate our approach through extensive experiments, demonstrating robust scalability and superior performance over state-of-the-art continuous baselines on large-scale datasets (MS-COCO, Reuters-21578) in high-sparsity, deep learning regimes. Our results offer both theoretical rigor and practical effectiveness for general multi-label metric optimization.

Mehryar Mohri, Yutao Zhong

Google Research & CIMS · New York, NY 10011 · Google Research

Multi-Label Classification Statistical Learning Theory

May 27, 2026cs.LG

Optimal ridge regularization revisited

We consider

L^2

-regularized linear (ridge) regression over a finite data sample

X

with bounded covariance and linear prediction targets

y

with additive isotropic noise of finite variance. We present an iterative procedure to compute the optimal regularization strength numerically from the generative parameters in the fixed-

X

setting and prove its convergence at limited noise levels. Our experimental evaluation over synthetic data shows that the proposed procedure combined with sample-based parameter estimates attains near-optimal random-

X

generalization across a wide range of sample sizes, aspect ratios, and noise levels, at an added computational cost equivalent to one preliminary ridge regression in the underparameterized regime and two in the overparameterized case.

Jack Timmermans, Sergio A. Alvarez

Department of Computer Science, Boston College, Chestnut Hill, MA 02467 USA

Linear Regression Statistical Learning Theory Ridge Regression Hyperparameter Optimization