Statistical Learning Theory

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

Sep 22, 2026stat.ML

On the Gradient Heterogeneity Dynamics of Adversarially Robust Federated Regression

Federated learning (FL) is intrinsically heterogeneous: honest clients may have different data-generating models. On top of that, adversarial clients can make heterogeneity even more pronounced by sharing arbitrary updates. Existing analyses typically control the interaction between statistical heterogeneity and adversarial behavior through gradient-dissimilarity conditions. However, the underlying bound is imposed a priori and may yield conservative guarantees even for least-squares regression. We instead derive the gradient heterogeneity from the statistical model of linear and nonlinear regression with fresh data samples at every round. Our bounds separate heterogeneity among the honest clients' ground-truth model parameters, finite-sample label noise, and initialization. We then demonstrate that, for any

(f,κ)

-robust aggregator with coefficient

κ= O(f/n)

, where

f

is the number of adversarial clients and

n

the total number of clients (with

f/n < 1/2

), convergence holds after an explicit sample burn-in.

Leonardo F. Toso, James Anderson, Nirupam Gupta +1

Columbia University, USA · University of Copenhagen, Denmark · Sorbonne Université and Université Paris Cité, CNRS, LPSM, France

Byzantine-Robust Federated Learning Non-IID Federated Learning Statistical Learning Theory Federated Learning

Ask PDF

Sep 21, 2026stat.ML

Adversarially Robust PAC Learning with Optimal VC Rates

We study the problem of \emph{adversarially robust} PAC learning. In this framework, the learner observes independent samples from an unknown distribution over

\mathcal{X} \times \{0,1\}

, as in classical PAC learning. However, given a perturbation map

\mathcal{U} : \mathcal{X} \to 2^{\mathcal{X}}

known to the learner, the goal is to output, with high probability, a predictor that correctly classifies \emph{every} perturbation

z \in \mathcal{U}(x)

of most future examples

(x,y)

drawn from the same underlying distribution. We determine the \emph{optimal}

\mathcal{U}

-independent sample complexity of this problem in both the realizable and agnostic settings. More specifically, for every concept class

\mathcal{H}

\operatorname{VC}

dimension

d

, we prove upper bounds of

\mathcal{O} \big( d/ε+ \log(1/δ)/ε\big)

in the realizable setting and

\mathcal{O} \big( d/ε^2 + \log(1/δ)/ε^2 \big)

in the agnostic setting, together with an optimal first-order refinement of the latter. These bounds match the corresponding lower bounds for classical PAC learning. Consequently, and perhaps surprisingly, adversarial robustness incurs \emph{no additional} distribution-free statistical cost, uniformly over all perturbation maps. Our bounds improve exponentially on those of [Montasser, Hanneke, and Srebro; COLT '19]. On the technical side, we present short and elementary proofs based on a new algorithmic principle that we call \emph{binomial-bagging}. We believe that binomial-bagging and its analysis may be of independent interest.

Steve Hanneke, Amirreza Shaeiri

Department of Computer Sciences, Purdue University, USA.

Sample Complexity Adversarial Robustness PAC Learning Statistical Learning Theory

Ask PDF

Sep 16, 2026cs.LG

Double descent is the principle of least action

The test error of a model plotted against its number of parameters

d

falls, peaks when the model can just fit the training data, and falls again, exhibiting the double descent phenomenon. We explain the phenomenon with statistical mechanics. The training trajectory of a stochastic gradient-based method is a particle wandering over the energy landscape of the training loss at an induced temperature

T

, and a run that has equilibrated visits every parameter vector of a given training loss equally often, the fundamental postulate of statistical mechanics, with probability given by the Boltzmann distribution. Because training starts at an initial point and has only finite time to diffuse, it carries an effective weight decay, which makes every parameter a quadratic degree of freedom. The equipartition theorem then distributes the energy among the

d

degrees of freedom in shares of

T/2

, so at a fixed training loss adding parameters lowers the temperature and drives the Boltzmann distribution toward the stationary path. Finally, adding parameters can only lower the

L^2

norm of the stationary path, so a solution sampled at fixed loss is less likely to be large with increasing

d

, effectively increasing weight regularization.

Congzhou M Sha

Penn Medicine Doylestown Hospital, 595 W State St, Doylestown, PA 18901, United States

Double Descent Statistical Physics of Learning Statistical Learning Theory

Ask PDF

Sep 16, 2026stat.ML

Fast Learning Rates for Physics-Informed Kernel Methods

In physics-informed machine learning, a target function

u^*

is learned from noisy value observations

y_i=u^*(x_i)+ \varepsilon_i

, together with differential information, given either by noisy observations

d_j=(Du^*)(z_j)+ξ_j

or by a known physical constraint

Du^*=v

. We consider the setting where

D

is a linear differential operator and analyze a physics-informed kernel estimator

\hat u

combining

n

value observations and

m

differential observations. In this context, we ask how much can differential information improve predictions, and how does this improvement depend quantitatively on

n

m

, and

D

. We prove finite-sample bounds, supported by numerical simulations, revealing a two-regime structure for the prediction error. When

m

is limited, the rate depends jointly on

n

and

m

; when

m

exceeds a problem-dependent threshold, the rate saturates and matches the oracle rate obtained when the perfect constraint

D \hat u = Du^*

is imposed. Examples are discussed for Sobolev spaces which are reproducing kernel Hilbert spaces and include partial Laplacian constraints on the torus and gradient observations on bounded domains. These examples illustrate the range of possible learning rate improvements --- from the standard nonparametric

n^{-1/4}

to the parametric rate

n^{-1/2}

. Finally, we derive physically consistent rates in a stronger norm that jointly controls the errors in

\hat u

and

D\hat u

Luc Brogat-Motte, Joachim Bona-Pellissier, Giacomo Meanti +1

SAIL Unit, Istituto Italiano di Tecnologia, Genoa, Italy · MaLGa Center, DIBRIS, Università degli Studi di Genova, Genoa, Italy

Kernel Regression Physics-Informed ML Statistical Learning Theory

Ask PDF

Sep 16, 2026cs.LG

How Many Labels Does Model Choice Need? Certificates and Budgets for Selective Prediction

Classifiers can make identical predictions yet require labels to compare their selective performance: confidence ranks weight the same errors differently. We quantify this requirement for the area under the generalized risk-coverage curve (AUGRC). A prelabel lower bound rules out insufficient budgets. With all labels known, a covering linear program bounds the minimum number of labels sufficient to fix the winner (the certificate size) within

K-1

labels for

K

candidates. For fixed

K

, independent uniform orders and identical predictions, the prelabel bound approaches one quarter of the pool. With iid Bernoulli errors independent of the orders, every exact acquisition policy reads almost all labels asymptotically, although a two-candidate certificate needs only half. Across 108 feature-panel comparisons on nine datasets, disagreement labels settle every accuracy choice but no AUGRC choice. A 20% budget is ruled out in 96 conditions; certificates need 56-57% on average. On ten conditions with pretrained image classifiers, confidence-score choice reads 68-91% of 10,000 labels for exact selection and 50-67% with AUGRC tolerance

5\times10^{-4}

. An exact stopping test works with any acquisition order. Together, these results link confidence ranks to label budgets and certified model comparison.

Tetsuji Kuboyama

Computer Centre, Gakushuin University

Model Selection Selective Prediction Classification Statistical Learning Theory

Ask PDF

Sep 15, 2026stat.ML

Sharp margin-based generalization bounds for realizable SVM

Let the exact homogeneous hard-margin support vector machine be trained on

m

independent observations from a Borel probability law on a real Hilbert space. We prove that, with score zero counted as an error, there is a universal numerical constant

C

such that

\Pp\left( γ_m>0,\quad \Risk(u_m)> \frac{C}{m} \left( K_m+\log\frac1δ \right) \right) \le δ.

Here

γ_m

is the empirical homogeneous margin,

u_m

is the exact minimum-norm unit-margin separator,

r_m

is the largest training radius, and

K_m:=r_m^2\norm{u_m}^2=r_m^2/γ_m^2

\{γ_m>0\}

. The proof is driven by a deterministic deletion problem. Given vectors

x_1,\ldots,x_n

in the unit ball, delete a set

B

of constraints and let

u_B

be the closest point to the origin that satisfies every retained unit-margin constraint. Suppose that

\norm{u_B}^2\le k

and that every deleted vector has nonpositive score under

u_B

. We prove that a family of such deletion sets of cardinality

q

has size at most

\exp(8k+2q)

. The conceptual step is an exact identity obtained from the KKT representation of

u_B

. For a random deletion set, the identity converts the mean squared spread of the separators into a weighted sum of score deficits. It therefore forces a coordinate whose deletion status separates the two conditional means by a quantitatively large amount. Revealing that coordinate decreases the conditional separator variance enough to control the binary entropy of the split. An entropy induction gives the deletion count, and an exact factorial ghost-sample identity converts that count into the stated high-probability SVM bound.

Steve Hanneke, Aryeh Kontorovich

Support Vector Machines Statistical Learning Theory Generalization Bounds

Ask PDF

Sep 15, 2026cs.LG

A Weighted Kernel Method for Approximation that Adapts to Learned Multivariable Structure

Approximating the input-output behavior of a multivariable black-box function from limited data is challenging when blind to the importance of its inputs and their interactions. We introduce total sensitivity kernels (TSKs), a method based on families of weighted ANOVA kernels that learn and adapt to this multivariable structure. TSKs parameterize the weights on each multivariable component of the target function by factors for each input. We propose learning these factors directly from function evaluations by selecting the reproducing kernel Hilbert space (RKHS) in which the target function has minimum norm. Under suitable conditions, we show that this norm-minimization problem admits a unique solution, and we establish consistency of a finite-data formulation based on minimum-norm interpolation. The learned TSK factors characterize the participation of individual inputs across interactions and main effects, providing a kernel-dependent notion of input sensitivity related to total Sobol indices. Numerical experiments demonstrate that adapting the kernel to learned multivariable structure can substantially improve approximation accuracy over a standard product kernel.

John E. Darges, Laura Weidensager

Department of Mathematics, Emory University · Department of Mathematics, Simon Fraser University

Kernel Regression Kernel Methods Statistical Learning Theory

Ask PDF

Sep 14, 2026cs.LG

Benign Loss Landscapes Can Coexist with Worst-Case Hardness

Deep neural networks are expressive enough to contain worst-case targets that can be evaluated in polynomial time but cannot be learned in polynomial time by gradient descent. For practical tasks they nonetheless learn well, raising the question of what non-generic structure of real-world targets enables this. Existing surrogate models cannot pose this question because they either lack hard-to-learn targets entirely (deep linear networks) or cannot evaluate such targets efficiently (kernel methods, infinite-width limits). We study tree tensor networks (TTNs), a model class that generalizes deep linear networks and Tucker decompositions. We show they embed arbitrary read-once Boolean formulas, and thus contain polynomial-size targets that cannot be learned by gradient descent in polynomial time under the same mechanism as neural networks. Despite this, we prove that their loss landscapes are conditionally benign for every realizable target: every local minimum that is minimum-norm is global. Thus, surprisingly, bad local minima are not what distinguishes between typical and worst-case problems in TTNs. Instead, learning difficulty in TTNs can arise from high-order degenerate saddle points, which we show are caused by rank-deficiency. This is explored through a case study of the parity function, illustrating the potential for TTNs to relate landscape geometry to computational hardness.

Zach Furman, Stephan Wäldchen, Yangda Bei +1

University of Melbourne · Iliad

Tensor Networks Statistical Learning Theory Loss Landscape Geometry

Ask PDF

Sep 11, 2026cs.LG

Relatively Smart II: Tractable or Semi-Supervised Instance-Optimal Learning

We continue the study of relatively smart learning, introduced by Dughmi and Pour (2026), which asks a supervised learner to compete, marginal by marginal, with every distribution-fixed error guarantee soundly certifiable from unlabeled data. They showed that the One-Inclusion Graph (OIG) learner is relatively smart with a quadratic sample-complexity blowup, and that no relatively smart learner can do better, leaving open whether ERM or another natural or tractable learner achieves comparable guarantees. They also left open whether the blowup can be restricted to unlabeled data. Our firs results shows that ERM---and in fact any proper consistent learner---is relatively smart for binary classification in the distribution-free setting. We show that a small certifiable error with

m

samples implies a similarly small error on the uniform distribution over a random sample of size

O(m^2)

, yielding a cover of size at most

2^{m+1}

on that sample. This suffices to control the error of proper consistent learners with

O(m^2)

samples. We then show that semi-supervised relatively smart learning is information-theoretically possible with a quadratic blowup only in unlabeled sample complexity and no blowup in labeled sample complexity. The learner uses a natural generalization of OIG to a leave-most-out transductive problem, where labels of part of a finite pool are revealed and the remaining labels are predicted. Finally, this label efficiency comes at a cost in simplicity and tractability. If the hypothesis class is accessed only through an agnostic ERM oracle, any semi-supervised relatively smart learner with substantially sub-quadratic labeled-sample blowup requires super-polynomially many oracle calls. This holds even when the marginal is given explicitly, and thus also yields an intractability result for distribution-fixed learning that may be of independent interest.

Shaddin Dughmi, Alireza F. Pour

University of Southern California · University of Waterloo

Classification Semi-Supervised Learning Statistical Learning Theory

Ask PDF

Sep 10, 2026stat.ML

Generalization Analysis of Distributed Kernel-based Robust Gradient Descent Algorithms

In this paper, we investigate the generalization performance of distributed gradient descent algorithms in a reproducing kernel Hilbert space under a robust loss function

l_σ

. By exploiting the spectral characterization of gradient descent together with the intrinsic properties of robust loss functions, we establish optimal learning rates for the distributed kernel-based robust gradient descent (DKRGD) algorithm with an appropriately chosen scale parameter

σ

. The proposed parameter choice of

σ

simultaneously alleviates the saturation phenomenon and guarantees statistical robustness. A key technical contribution is a novel error analysis that provides substantially sharper bounds for products of operators, thereby significantly relaxing existing restrictions on the maximum number of local machines while retaining optimal learning rates. Finally, we develop a communication-efficient strategy that further improves the convergence performance of DKRGD.

Jun-Yi Meng, Zheng-Chu Guo, Yuan Mao

School of Mathematical Sciences, Zhejiang University, Hangzhou 310058, P. R. China · College of Informatics, Huazhong Agricultural University, Wuhan 430070, P. R. China

Kernel Regression Communication-Efficient Distributed Training Robust Loss Functions Distributed Training Statistical Learning Theory

Ask PDF

Sep 9, 2026stat.ML

Weighted Empirical Risk Minimization for Machine Learning under Long-Range Dependence: Exact Pathwise Rates and Learning-Error Geometry

We develop an exact almost-sure learning theory for smooth parametric models trained by regularly weighted empirical risk minimization on long-range dependent data. The training observations are generated from a fixed finite window of a stationary Gaussian sequence, and the sample weights are regularly varying. If the loss gradient at the population minimizer has Wiener-chaos rank

m

and a nonzero low-frequency coefficient, then, in the long-memory interior regime, the finite-lag score reduces on the iterated-logarithm scale to a single weighted Hermite chaos. This yields an almost-sure Bahadur representation, an exact limsup law for the learned parameter, and, for

m\ge2

, the functional cluster set of the complete learning trajectory. The polynomial learning exponent is determined by the memory parameter and the chaos rank and is invariant under the admissible power weighting, whereas the sharp pathwise constant and cluster geometry depend on the weights. In the rank-one case, global optimization over the admissible power exponents shows that every optimizer is positive. Time-series prediction and classification examples illustrate the results.

Elina Moldavskaya

Technion–Israel Institute of Technology, Israel

Statistical Learning Theory Empirical Risk Minimization

Ask PDF

Sep 9, 2026cs.AI

A Function-Space Approach to the Statistical Mechanics of Learning Dynamics

In the kernel regime, neural-network learning inherits its preferences from a frozen spectrum. During feature learning, this spectrum evolves, yet networks retain systematic biases toward simple, smooth directions. We develop a function-space statistical framework explaining the origin of these preferences, treating functions and their learning operators as macroscopic variables, with parameterization entering through the multiplicity of parameter configurations realizing each function. For mean-squared loss, error relaxes exactly under the evolving learning operator

M=JJ^\ast

. Training stochasticity induces a Gaussian weight over function-space states, while parameter multiplicity contributes an entropic operator

B

, defined by the curvature of its log multiplicity. A local Laplace expansion yields the fluctuation free energy

Φ_{\mathrm{fluc}}(M;B)=\frac{σ_ξ^2}{2}\log\det(M^{-1}+B)+\mathrm{const}

, analogous to an Occam factor. Under mild statistical conditions, this free energy is rotationally stationary exactly when

[M,B]=0

, is minimized by pairing large eigenvalues of

M

with small eigenvalues of

B

, and generates a local restoring force against mismatch. Learning is therefore biased toward faster relaxation along entropically cheaper directions. This preference strengthens with training noise and vanishes in the deterministic limit, beyond gradient-flow accounts of operator alignment. For ReLU networks, we relate entropic curvature to the minimal rearrangement of activation boundaries required for a functional change and bound this structural cost by directional smoothness. Consequently, smooth directions are preferentially learned faster, in a data-adaptive manner, even as the learning operator evolves.

Yizhou Zhang, Weichen Wu, Lun Du +1

Variational AI · The Voleon Group · Independent Researcher +1

Statistical Physics of Learning Representation Learning Neural Network Training Dynamics Statistical Learning Theory Implicit Regularization

Ask PDF

Sep 8, 2026cs.LG

Nearly Tight Rademacher Bounds for Sparsely Activated Neural Networks

An input may activate few hidden units even when different inputs collectively use an entire network. We study the statistical complexity of this input-dependent sparsity in the one-hidden-layer ReLU model of Awasthi et al. (COLT 2024). For width

s

, at most

k

active units per input, and effective weight and bias bounds

W,B

, every size-

m

sample in the class's fixed radius-

R

input domain satisfies

\mathcal{R}(S)\le CWR\min\{k,\sqrt{sk/m}\log^{3/2}(2m)\}+kB/\sqrt m

. A support-preserving cover and a single normalized chaining argument remove the previous explicit dimension factor, up to logarithms. Lower bounds on appropriate i.i.d. marginals match up to those logarithms, showing how changing active units across inputs retains a width dependence. The input domain matters: zero-bias networks sparse on the entire ball have at most

2k

nonzero units and complexity

O(kWR/\sqrt m)

, whereas bias bounds comparable to

WR

restore the worst-case rate on that same domain in only logarithmic dimension. A spherical-cap construction proves the latter claim without assuming sparsity merely on the sampling support. For a specified normalized bounded loss and biases comparable to

WR

, we also obtain agnostic minimax excess-risk bounds of order

\min\{1,\sqrt{s/(km)}\}

up to logarithms.

Xiaoyu Li, Zhizhou Sha, Jiaojiao Jiang +2

University of New South Wales · University of Texas at Austin · University of Sydney

Neural Network Generalization ReLU Neural Networks Activation Sparsity Statistical Learning Theory

Ask PDF

Sep 8, 2026cs.LG

PAC-Bayesian Bounds for Learning Partially Observed Stochastic Linear Time-Invariant State-Space Systems with Inputs and Sub-Gaussian Noise

In this paper we derive a Probably Approximately Correct (PAC)-Bayesian error bound for partially observed linear time-invariant (LTI) stochastic dynamical systems in state-space form with inputs and sub-Gaussian noise. Such bounds are widespread in machine learning, and they are useful for characterizing the predictive power of models learned from finitely many data points. The bound derived in this paper relates the expectation of prediction errors with the prediction error generated by the model on the data used for learning. In addition, we show that it can also be used to derive bounds for the parameter estimation error. In turn, this allows us to provide finite-sample error bounds for the prediction error and parameter estimation error for a wide class of system identification algorithms. Furthermore, as LTI systems are a sub-class of recurrent neural networks (RNNs), these error bounds could be a first step towards PAC-Bayesian bounds for RNNs.

Mihaly Petreczky, Mohamad Al Ahdab, John Leth

CRIStAL, Centrale Lille, Universit´e de Lille, France · Department of Electronic Systems, Aalborg University, Denmark

PAC-Bayesian Generalization Bounds Stochastic Linear Dynamical Systems System Identification Statistical Learning Theory State Space Models

Ask PDF

Sep 7, 2026cs.LG

Sharp Structure-Agnostic Minimax Risk for Partial Linear Models

We characterize the sharp structure-agnostic minimax risk for coefficient estimation in the partial linear model when the outcome and treatment nuisances are learned by two distinct black-box learners, which resolves the open problem in double machine learning posed by Gu (2025). For each nuisance

q\in\{μ,π\}

, we characterize the available learner by an approximation-error budget

a_q

and a stochastic-error budget

s_q

, with the latter controlled through localized Rademacher complexity. Writing

\mathcal E_n

for the minimax mean-squared error, we show that

\mathcal E_n\asymp1\wedge\left\{\frac1n+\left(a_μa_π+\min\left\{a_πs_μ+s_π^2,\,a_μs_π+s_μ^2\right\}\right)^2\right\}.

The main new ingredient is a novel lower bound for the general two-learner problem. Our proof constructs four finite-mixture testing experiments using orthogonal code functions. Across these experiments, the hidden perturbations are placed outside both learner classes, outside only the treatment learner class, outside only the outcome learner class, or inside both learner classes. These four configurations capture, respectively, the interaction between the two approximation errors, the two asymmetric interactions between one learner's approximation error and the other learner's learning error, and the joint estimation difficulty of learning both nuisances. Combining the four resulting lower bounds yields the displayed rate, which matches the latest upper bound in Gu (2026). Our result shows that standard double machine learning can overstate the intrinsic difficulty of target estimation and provides a target-specific principle for learner selection: approximation error and stochastic complexity must be jointly balanced across the two nuisance learners rather than optimized separately.

Haichen Hu, David Simchi-Levi

Center for Computational Science and Engineering, MIT · Department of Civil and Environmental Engineering, MIT · Institute for Data, Systems, and Society, MIT

Double ML Semiparametric Inference Minimax Estimation Statistical Learning Theory

Ask PDF

Sep 3, 2026cs.LG

High-Dimensional Learning Dynamics of Attention-Indexed Models

Attention mechanisms are central to modern foundation models, yet their training dynamics remain poorly understood, especially when the attention matrices have extensive rank. In this work, we study attention-indexed models, a broad framework that can represent multi-layer and multi-head attention architectures. First, we show that, in a suitable high-dimensional limit, the population-loss landscape is characterized by a finite set of trace order parameters. In contrast, online stochastic gradient descent (SGD) is governed by an infinite hierarchy of matrix moments, which we show can be exponentially well-approximated by a finite truncated system. Second, this framework reveals that attention parameterization itself can act as an architectural implicit bias. Direct optimization of an attention matrix

S\in\mathbb{R}^{d\times d}

can remain trapped in an uninformative state. Tied attention (

S=WW^\top

) induces an automatic symmetry-breaking mechanism and yields weak recovery in

Θ(d^2\log d)

samples. For untied attention,

S=UV^\top

, we uncover a fast-slow mechanism: the pre-activation mean first evolves on a fast timescale, while the overlaps evolve on a slower one. Weak recovery on the

Θ(d^2\log d)

scale occurs when the state selected by the fast dynamics breaks the initial symmetry.

Yizhou Xu, Margarita Sagitova, Lenka Zdeborová +1

1Information, Learning and Physics Laboratory, École Polytechnique Fédérale de Lausanne (EPFL) · 2Statistical Physics of Computation Laboratory, École Polytechnique Fédérale de Lausanne (EPFL)

Implicit Bias Attention Mechanisms Neural Network Training Dynamics Statistical Learning Theory

Ask PDF

Sep 3, 2026stat.ML

Towards a Statistical Understanding of Mixture-of-Experts

Mixture-of-experts (MoE) architectures increase model capacity by combining a collection of expert predictors through input-dependent routing, while often activating only a small subset of experts for each input. Despite their growing importance in modern large-scale models, the statistical roles of their design choices, especially routing, sparse activation, and shared experts, remain only partially understood, as existing theory has largely focused on parametric or correctly specified MoE models. In this paper, we view MoE as a form of localized aggregation and show how this localization reshapes the approximation-estimation-computation tradeoff. We derive oracle risk bounds for learning dense and sparse routing with evolving experts, separating approximation, expert-learning, and router-estimation errors, and characterize how sparse Top-K routing can retain the benefits of localized aggregation while controlling per-input computation. We also interpret gating through the geometry of input space, relating routing performance to regions of local expert advantage, and show how shared experts, as adopted in architectures such as DeepSeekMoE, can extract common predictive structure so that routed experts focus on residual local variation. Together, these results provide a unified statistical framework for understanding MoE through input-dependent expert aggregation, in which expert specialization and computational tradeoffs are governed by local predictive structure.

Siyuan He, Bokai Yang, Jie Hu +2

Qiuzhen College, Tsinghua University, Beijing, China. · KLATASDS-MOE, School of Statistics, East China Normal University, Shanghai, China. · Yau Mathematical Sciences Center, Tsinghua University, Beijing, China. +1

Mixture of Experts Sparse Mixture-of-Experts Mixture-of-Experts Models Statistical Learning Theory

Ask PDF

Sep 2, 2026stat.ML

A Closed-Form Formula for Consistent Lipschitz Regression on Metric Spaces with Sparse Neural Network Realizations

Several classical machine-learning methods, such as KRRs and SVRs, are both computationally and analytically tractable since their estimators either admit closed-form expressions or are obtained by minimizing convex training objectives; neither feature is generally available for deep neural networks. We address this by introducing a simple closed-form ``two-stage'' compositional formula

\hat{f}

for reconstructing an unknown Lipschitz function

f:\mathcal{X}\to \mathbb{R}

on a metric space

(\mathcal X,ρ)

from

N

i.i.d. noisy observations. Our main result is a high-probability uniform (

L^{\infty}

) recovery guarantee that jointly controls approximation and statistical errors while enjoying an optimization error of zero; in particular, we do not assume oracle access to an approximate ERM. Our secondary main results establish the optimality of our formula in three complementary senses. 1) Function space: On Ahlfors-regular metric spaces, the hypothesis class parameterized by our formula attains the optimal fat-shattering dimension. 2) Parameter space: Its dependence on the parameters is maximally numerically stable, in the sense that a smaller approximation error cannot be achieved with a smaller Lipschitz dependence on the model parameters. 3) Forward pass: Its dependence on the input is maximally regular, matching the Lipschitz constant of the target function

f

. When

\mathcal X=[0,1]^d

is equipped with the

\ell^\infty

norm,

\hat{f}

admits algorithmic ReLU-MLP and exact ReLU-multi-head transformer realizations of depth

\mathcal{O}(\log(N))

with

\mathcal{O}(N)

nonzero parameters.

Ruiyang Hong, Hrad Ghoukasian, Anastasis Kratsios

Neural Network Approximation Theory Statistical Learning Theory Lipschitz Neural Networks

Ask PDF

Sep 2, 2026stat.ML

Occupancy-based Quantile Risk Control

Conformal risk control is an emerging framework for the safe deployment of machine learning models with finite-sample guarantees. To accommodate a broader class of risk notions, quantile risk control extends this framework to quantile-based risk measures. However, existing methods either suffer from excessive conservatism or lack rigorous finite-sample guarantees. To address these limitations, we introduce Occupancy-based Quantile Risk Control (OQRC), a novel method that provides tight risk control bounds with finite-sample validity. Our key idea is to formulate risk control as a finite-occupancy problem by partitioning the loss space with the ordered calibration losses. Specifically, we estimate the distribution of test losses across the resulting bins and upper-bound the risk by the maximum loss attained within each bin. We then select the parameter

λ

such that this upper bound does not exceed a predefined threshold

α

with high probability

1-δ

. Theoretically, we establish a finite-sample guarantee showing that OQRC yields tight risk control bounds that converge to the optimal bounds at a provable rate of

\mathcal{O}_ p(n^{-1/2})

. Extensive experiments demonstrate the effectiveness of our method, reducing the risk gap by up to 78.64% on common benchmarks.

Zihao Shi, Huajun Xi, Bingyi Jing +1

Southern University of Science and Technology · Mohamed bin Zayed University of Artificial Intelligence · The Chinese University of Hong Kong, Shenzhen +1

Conformal Risk Control Statistical Learning Theory

Ask PDF

Sep 1, 2026cs.LG

Rethinking Learnability in Offline Data-driven Optimization

Black-Box Optimization (BBO) has broad applications, while traditional algorithms such as evolutionary algorithms and Bayesian optimization face efficiency challenges as real-world BBO problems grow increasingly complex. Data-driven optimization has been the most popular paradigm to improve the efficiency of BBO, by learning from data. Offline data-driven optimization seeks high-quality solutions using only a fixed set of previous evaluations, attracting substantial attention because it requires no additional online evaluations. Many offline optimization methods have been proposed, but a fundamental question remains unanswered: what learnability is sufficient for offline optimization? Prior theoretical studies show that Probably Approximately Correct (PAC) learnability is insufficient, as the optimal region may remain poorly learned even when most regions are well learned. In this paper, we propose algorithm-dependent learnability, which requires accuracy only on the optimizer's trajectory. We prove that its value-query form is sufficient for representative discrete settings, including greedy and local search for submodular maximization, while its first-order analogue is sufficient for projected gradient descent on convex minimization. Motivated by this notion, we formalize a trajectory-learning framework comprising trajectory construction, trajectory modeling, and candidate generation, and analyze existing trajectory-based methods under it. We further propose Uncertainty-aware Gradient-guided Trajectory Learning (UGTL), which constructs locally coherent improvement trajectories reflecting plausible search paths, models them with conditional diffusion, and selects a diverse candidate set. Our experiments show that UGTL achieves the best average rank, 3.1/25, among 25 methods on Design-Bench tasks, and confirm that our trajectory construction plays a significant role in the improvement.

Chao Qian, Chen-Guang Wang, Rong-Xi Tan +1

State Key Laboratory of Novel Software Technology, Nanjing University, Nanjing 210023, China · School of Artificial Intelligence, Nanjing University, Nanjing 210023, China

Black-Box Optimization Statistical Learning Theory

Ask PDF

Aug 31, 2026stat.ML

Informative Label Missingness in Multiclass Classification Information Geometry and Excess Risk

Informative label missingness can change the usual efficiency ordering between completely and partially labelled classifiers because the pattern of missing labels may itself carry information about the classification model. We develop a general likelihood-based theory for this phenomenon in parametric multiclass classification. An efficient-information decomposition separates information lost through unavailable class memberships from information contributed by the missing-label mechanism. We then derive a quadratic expansion of plug-in excess risk over the active pairwise faces of the multiclass Bayes boundary, showing that classification efficiency depends on how information gains and losses align with directions that perturb the decision boundary. This yields a classification-weighted generalized-eigenvalue criterion under which informative partial classification may have smaller asymptotic classification risk without globally dominating complete classification in Fisher information. Near missing completely at random, with the marginal missing-label proportion fixed, redistribution of missing labels changes lost class-label information at first order, whereas efficient information from the missingness pattern appears only at second order. Three-class quadratic discriminant calculations, finite-sample experiments, and a semi-synthetic multiclass application illustrate the resulting regime-dependent behaviour.

Fariborz Setoudehtazang, Geoffrey J. McLachlan

Dipartimento di Scienze Statistiche, Universit`a di Padova, Padova, Italy · School of Mathematics and Physics, The University of Queensland, Australia

Information Geometry Learning with Missing Data Multiclass Classification Classification Statistical Learning Theory

Ask PDF

Aug 31, 2026stat.ML

Estimating Population-Risk Curves Along Nonconvex Gradient Flows from the Training Sample

We estimate the conditional population-risk curve of a realized smooth nonconvex gradient flow from the training sample. Flow approximate leave-one-out (Flow-ALO) propagates a deletion response and evaluates omitted observations at approximate deleted paths. The risk-curve error decomposes into response approximation, exact-LOO fluctuation, and deletion-to-full risk transfer. On each fixed finite horizon, bounded centered training-loss gradients, a one-sided Hessian lower bound, locally Lipschitz Hessians, and a strict tube-closure condition yield an explicit

(n-1)^{-2}

bound for the deletion-response error. Bounded evaluation-loss gradients transfer the deletion-response bound to the score without requiring the Hessian to be invertible. Direct first-order jackknife cancellation and exact-LOO concentration control deletion-to-full risk transfer and fluctuation, respectively, completing recovery of the conditional population-risk curve. For bounded smooth two-layer mean-field networks training both layers, the score-error bound is uniform in width.

Mingzhi Song

Department of Mathematics, The University of Hong Kong

Nonconvex Optimization Statistical Learning Theory

Ask PDF

Aug 31, 2026math.LO

A Borel Concept Class of VC Dimension One with a Non-PAC Consistent Learner in ZFC

The fundamental theorem of statistical learning states that, under suitable measurability assumptions, finite Vapnik--Chervonenkis (VC) dimension guarantees that every proper consistent learning rule is probably approximately correct (PAC). Blumer, Ehrenfeucht, Haussler, and Warmuth showed, assuming the Continuum Hypothesis, that the "well-behavedness" condition of the concept class cannot be omitted: they constructed a concept class of Borel sets of VC dimension one admitting a consistent learning rule that is not PAC. We show that the Continuum Hypothesis is unnecessary. Working in Zermelo--Fraenkel set theory with the Axiom of Choice (ZFC) alone, we construct a concept class of Borel sets on

[0,1]

of VC dimension one and a proper consistent learning rule that is not PAC. More precisely, for a suitable Borel probability measure and target concept, the rule has true risk one at every sample size on a set of samples of outer probability one. Consequently, finite VC dimension and Borel measurability of the individual concepts do not suffice to guarantee that every proper consistent learning rule is PAC. The result shows, with no need of extra set-theoretical assumptions, that the additional regularity assumption in the fundamental theorem cannot in general be omitted.

Mateus Jesus de Arruda Campos, Gabriel Fernandes, Vinicius de Oliveira Rodrigues

PAC Learning Statistical Learning Theory

Ask PDF

Aug 27, 2026cs.LG

Contact Geometry and Covariance Deficits in Volume-Sampled Least Squares

We classify when ordinary fixed-size volume sampling followed by unweighted least squares attains its sharp coefficient-covariance ceiling on a fixed design. For a real whitened design without coloops and a fixed positive-loss residual, the contact space is unchanged at every strict-interior sample size. Its possible nonzero values form a finite orthogonal family: each maximal parallel class of normalized Naimark-complement rows determines a deletion nullspace of dimension one less than the class size. A single residual attains an entire query precisely when the query range lies in one class space. The proof starts from two-sided Loewner comparison of every normalized covariance deficit with an explicit leave-one-out operator, using supported omission moments and reverse deletion. Residual augmentation provides resolvent and second-moment upper bounds, while complement geometry yields query-specific margins, angular concentration, local alignment, and a multi-output energy obstruction. Exact families give closed-form margins and covariances, exhibit support-boundary jumps, and approach the ceiling despite a uniformly positive geometric margin. Finally, the same moment identities give upper and lower bounds on expected fixed-query squared-loss excess. The subset draw is the only randomness; all support and endpoint restrictions are explicit.

Kihun Rhee, Hanjoon Byun, Junpyo Seo

Randomized Sketching Linear Regression Statistical Learning Theory

Ask PDF

Aug 26, 2026cs.LG

Two Dimensions Govern Agnostic Multiclass Transductive Learning

In transductive classification, an adversary fixes a labeled population, one label is hidden uniformly, and the learner sees all remaining labels. For binary classes, agnostic transductive and PAC learning have the same minimax rate. Whether this extends to multiclass learning was open, especially for unbounded label spaces where uniform convergence can fail. We resolve the question up to logarithmic factors. For every multiclass class

\mathcal H

with DS dimension

d_{DS}

and Natarajan dimension

d_{\mathrm N}

, the optimal agnostic transductive excess error satisfies

\widetildeΘ\left(\frac{d_{DS}}{n}+\sqrt{\frac{d_{\mathrm N}}{n}}\right).

The result holds for arbitrary label spaces. The two terms are both necessary. A DS pseudo-cube gives the realizable

d_{DS}/n

obstruction, while a Natarajan cube with repeated points and fair labels gives the agnostic

\sqrt{d_{\mathrm N}/n}

obstruction. The upper bound uses a random-reservation principle. The learner deliberately ignores a constant fraction of the visible labels, which makes the true test point uniform in a large unseen block. We combine realizable compression, a label-space reduction, and inside-menu agnostic compression across this finite-population split. A new without-replacement multiplicative-weights lemma preserves the fast

d_{DS}/n

term. Consequently, agnostic multiclass PAC and transductive learning obey the same two-dimension law up to logarithmic factors.

Pahan Dewasurendra

Johns Hopkins University

Multiclass Classification Transductive Learning Statistical Learning Theory

Ask PDF

Aug 18, 2026stat.ML

Feature Priming in Online Linear Regression: Sparse-Regret Lower Bounds and Tight Coordinatewise Rates

In high-dimensional online prediction, sparse comparators motivate regret bounds that depend on sparsity rather than ambient dimension. Feature priming seeks such adaptation by reweighting features using past data and refitting a minimum-norm predictor. At COLT 2023, Warmuth and Amid posed the open problem of whether the univariate, Pearson, or multivariate priming rules admit competitive online regret guarantees. Under the natural past-only Moore--Penrose protocol, we establish sparse-regret lower bounds that refute the corresponding sparse-logarithmic guarantee. The key obstruction is cheap nuisance interpolation, which permits exact interpolation of the history while assigning insufficient weight to the truly predictive coordinate. An exact target-mass identity and a two-sign argument convert this obstruction into clipped prediction loss. Hadamard constructions yield

Ω(\min\{T,\sqrt d\})

clipped regret for each of the three unit-power rules against a zero-loss one-sparse comparator. For every fixed power

α\ge1

, one shared paired construction further yields linear regret simultaneously for all three powered rules and selectors among them in sufficiently high dimension. A rank upper bound is tight for powered univariate priming, even with Euclidean-unit inputs, and for unit-power Pearson priming with coordinatewise bounded inputs and target-preserving totalization. A separate algebraic construction gives

Ω(\min\{T,d^{1/4}\})

regret for unit-power multivariate priming under Euclidean-unit inputs. The univariate lower bound persists under any nonnegative second-stage ridge schedule, while a paired ridge construction yields linear lower bounds for all three powered rules. Exploratory diagnostics on frozen language-model activations are consistent with the same qualitative mechanism. The exact multivariate frontier remains open.

Huibo Xu, Shi Fu, Qixin Zhang +1

Nanyang Technological University, Singapore

Linear Regression Statistical Learning Theory

Ask PDF

Aug 13, 2026stat.ML

Bagging Robustly Learns VC Classes with Linear Sample Complexity

We revisit the problem of learning predictors robust to adversarial examples at test-time. We prove that VC classes are adversarially robustly learnable with sample complexity linear in the VC dimension

d

, providing an exponential improvement over the previous upper bound of Montasser, Hanneke, and Srebro (2019). Remarkably, this result is achieved with a simple improper algorithm that combines the classic heuristic bagging (bootstrap aggregation) of Breiman (1996) with robust empirical risk minimization (RERM). Our algorithm computes RERMs on

O(d^\star)

independent bootstrap samples and outputs their majority vote, where

d^\star

denotes the dual VC dimension. We complement this result with a lower bound showing that this is unavoidable: in general, any learner in this oracle model requires

Ω(d^\star)

calls to an RERM oracle, even when given arbitrarily many training examples.

Omar Montasser

Yale University

Adversarial Robustness Classification Statistical Learning Theory

Ask PDF

Aug 13, 2026math.ST

On the Structural Limits of Machine Learning Decision Systems: An Information-Theoretic, Interaction-Based, and Stochastic-Dynamical Perspective

Machine learning procedures are commonly evaluated in terms of predictive accuracy and computational efficiency. However, their achievable performance is fundamentally constrained by structural properties of the underlying data-generating process, which are formalized in terms of informational bounds. In this work we examine intrinsic limits of data-driven decision systems from an information-theoretic and interaction-based perspective. We analyze minimal achievable error in classification through Fano-type bounds and precision limits in parametric estimation via the Cramér-Rao inequality, emphasizing that such limits depend on the underlying model rather than on algorithmic sophistication alone. We further discuss how implicit assumptions, such as independence, ergodicity, and distributional stability, affect the validity of inferential procedures. Building on interaction-based modeling principles, we review typical frameworks such as Markov Random Fields and potential based representations for encoding dependence mechanisms. We also describe decision systems, including LLM-integrated agent architectures, as feedback-driven stochastic processes where state-dependent dynamics may induce emergent macroscopic behavior. This perspective highlights the importance of having adequate models for the data as a prerequi- site for expanding predictive capability, and situates algorithmic learning within the informational limits imposed by the models.

Nestor R. Barraza, Gabriel Pena

Universidad Nacional de Tres de Febrero. Departamento de Ciencia y Tecnología. · Universidad de Buenos Aires. Facultad de Ingeniería.

Stochastic Linear Dynamical Systems Statistical Learning Theory Decision-Making under Uncertainty Information-Theoretic Lower Bounds

Ask PDF

Aug 13, 2026stat.ML

Statistical Properties of Robust Learning under Distributional Shifts

Distributional shifts arise when the target deployment environment differs from the source environment that generated the training data. Robust learning frameworks such as Distributionally Robust Optimization (DRO) and Robust Satisficing (RS) aim to address this challenge, yet their finite-sample guarantees under such shifts, and their systematic comparison, remain underexplored: existing analyses typically establish guarantees either in the source environment or for adversarial worst-case performance over an ambiguity set. This paper instead studies generalization error in the target environment---the excess loss under the shifted target distribution. Our contributions are threefold. First, we derive finite-sample generalization error bounds in the shifted target environment for both DRO and RS. These bounds explicitly characterize the trade-off between reduced sensitivity to shift and the regularization penalty induced by each method's robustness hyperparameter, and they avoid the curse of dimensionality associated with Wasserstein empirical concentration. Second, when partial shift information such as shift magnitude or direction is available, we propose information-directed hyperparameter calibrations and compare the two methods given the same information. Under these calibrations, and in the partial-information regimes we study, DRO and RS exhibit complementary theoretical and empirical behavior. Finally, we apply the framework to a network lot-sizing problem, using it to interpret how robust policies respond to positive shifts in the demand distribution. Together, these results fill a gap in understanding the statistical properties of robust learning methods under distributional shifts and provide a principled basis for comparing DRO and RS.

Zhiyi Li, Xiaojie Mao, Yunbei Xu +1

National University of Singapore · Tsinghua University · University College London

Distribution Shift Robustness Distributionally Robust Optimization Robust Optimization Statistical Learning Theory

Ask PDF

Aug 10, 2026stat.ML

Logarithmic-Free Moment and Generalization Bounds for Uniformly Stable Algorithms

Uniform stability is a classical tool for controlling the generalization error of a learning algorithm. Bousquet, Klochkov, and Zhivotovskiy (2020) showed that the problem can be reduced to a moment inequality for a sum of weakly interacting functions of independent random variables. Their bound contains an additional factor

\log n

, and they asked whether this factor can be removed. We answer this upper-bound question affirmatively. More specifically, let

Z=(Z_1,\ldots,Z_n)

have independent coordinates and let

g_i(Z)

satisfy

\mathbb E[g_i(Z)\mid Z_{-i}]=0, \ \left| \mathbb E[g_i(Z)\mid Z_i]\right|\le M, \ \text{for every } i = 1, \dots, n,

where

Z_{-i}

denotes all coordinates except

Z_i

. Assume additionally that changing any coordinate

Z_j

j\neq i

, changes

g_i

by at most

β

, we prove that, for every

p\ge2

, for every

p\ge2

\left\| \sum_{i=1}^n g_i(Z)\right\|_p \le 16pnβ+M\sqrt{2pn}.

This removes the

\log n

factor from the previous bound and matches the lower bound of Bousquet, Klochkov, and Zhivotovskiy up to universal constants in the range covered by their construction. Our proof first establishes the required estimate on the Rademacher cube, then transfers it to arbitrary product distributions by a two-copy randomization argument.

Thanh Nguyen-Cung, Binh T. Nguyen

VinUniversity

Algorithmic Stability Statistical Learning Theory Generalization Bounds

Ask PDF

Momentum

Related topics

Latest papers 395