CS Paper Radar

Sharp Structure-Agnostic Minimax Risk for Partial Linear Models

Haichen Hu, David Simchi-Levi

cs.LG math.ST ·submitted 2026-09-07 21:32 UTC · v1
theory

Abstract

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.

Closest papers

Nearest neighbours by meaning across the whole index.

Reweighting for Transfer Classification: Exact Risk Conversion and Minimax Adaptation

cs.LG math.STstat.ML ·2026-11-06 ·Aoran Chen, Yang Feng
similarity 0.61
Abstract · 87 pages, 5 figures. Main text (32 pages) followed by the Supplementary Material

A source can make a training mixture easier to learn while making its accuracy less valuable for the target. We study how the training problem a source creates and the finite-sample error of learning it jointly determine target-risk guarantees under reweighting. For binary classification, for each pair of laws and each positive target weight, we derive the sharpest target excess hinge-risk bound implied by mixture excess alone, uniformly over clipped predictors. This exact conversion curve is determined by density-weighted local votes. A two-sample oracle inequality for weighted support vector machines supplies the mixture excess, and the composition becomes explicit for Gaussian kernels. On a tilted-boundary class, we establish the all-procedure minimax classification rate $[n+s_+^2/(m^{-1}+τ^2)]^{-1}$ in the transferable strength $s_+$ and the tilt $τ$, separating source sampling uncertainty ($m^{-1}$) from relation uncertainty ($τ^2$). A target-checked Gaussian-SVM selector adapts to unknown $s_+$ and $τ$ up to a logarithmic factor for fixed dimension, and retains the target-only rate up to the same factor against arbitrary independent sources under the stated target model. On a separate smooth opposition class, the minimax risk within the family of exact Gaussian SVMs fitted to the original labels with nonnegative weights is exponentially larger than the unrestricted minimax risk whenever the target sample is at most half the source sample, despite arbitrary data-dependent weighting and tuning. The value of a source thus depends on the training problem it creates, on what accuracy there means for the target, and on whether the permitted use of the source can implement the needed correction.

0.27

A Data-dependent Early Stopping Rule using Rademacher Complexity with L1-norm

cs.LG ·2026-08-25 ·Duy Hoang, Bastien Berret, Olivier Bruneau, Laurent Fribourg
similarity 0.59
Abstract · 22 pages, 11 figures

Training neural networks requires balancing the trade-off between fitting the training data and achieving robust performance on unseen inputs. This ability, commonly referred to as generalizability, is determined by the gap between the empirical risk on the training set (``empirical loss'') and the expected risk over the data distribution (``generalization error''). Existing approaches typically estimate the generalization error numerically, requiring gradient descent training and an ``early stopping'' strategy. In this work, we introduce an analytic framework that estimates the optimal time of early stopping without the need for training. Several works in the literature also give such analytical estimations, but they are generally based on random matrix theory and often make assumptions on the distribution of the data or the eigenvalue distribution of the covariance matrix. In contrast, our work is based on Rademacher complexity (RC) without needing such probabilistic assumptions. For both theoretical and numerical reasons, it is more relevant to express RC with the L1- norm rather than with the L2-norm. We focus on the case of linear models and the problem of linear regression. Thanks to the ``linear probing'' method, our results can, however, be successfully applied to nonlinear neural networks, as illustrated in the classification MNIST example.

0.31

Sharp Generalization for Nonparametric Regression in Interpolation Space by Shallow Over-Parameterized Neural Networks with Channel Attention

cs.LG stat.ML ·2026-11-01 ·Yingzhen Yang, Ping Li
theory similarity 0.59
Abstract

We study nonparametric regression using an over-parameterized two-layer ReLU neural network with fixed covariance-based channel attention, trained by gradient descent with both layers updated simultaneously. The spherical covariates follow an arbitrary fixed non-atomic distribution, and the target function lies in an interpolation space with spectral bias widely studied in the statistical learning literature. We prove that early-stopped training achieves regression risk $\cO(\eps_n^2)$, where $\eps_n$ is the critical population rate of the attention kernel $\Kattn$. Its positive eigenvalues are $λ_j^{s'}$, where $λ_j$ are those of the ReLU feature covariance kernel $K$ and $s'=2s+3$ for $s\ge1$. Under polynomial eigenvalue decay $λ_j\asymp j^{-2α}$ with $α>1/2$, the regression risk bound $\cO(\eps_n^2)$ specializes to the minimax optimal rate $\cO(n^{-2αs'/(2αs'+1)})$. Our analysis is based on two new technical results on the optimization and generalization of the attention network. First, the neural network function after every gradient descent iteration admits a decomposition into a function with bounded Reproducing Kernel Hilbert Space (RKHS) norm and a uniformly small residual. Second, local Rademacher complexity converts this decomposition into a regression risk bound. Kernel gradient descent on the same ball attains the same rate, while our theorem gives explicit sufficient width and auxiliary-sample conditions for simultaneous network training. Our analysis is further extended to covariates supported on $\RR^d$ through a novel normalization method. Under a sub-Gaussian covariate distribution, the attention network achieves a nearly optimal regression risk $\cO((\log n)n^{-s'(d+3)/(s'(d+3)+d)})$ without a density assumption.

0.21

Stochastic gradient descent with initial regularization

cs.LG math.OCstat.ML ·2026-08-24 ·Nabil Kahalé
theory similarity 0.59
Abstract · 33 pages

We analyze a variant of stochastic gradient descent with initial regularization (SGDIR) and derive dimension-free upper bounds on its expected excess risk for the squared loss. In the noiseless case, we obtain new bounds for both averaged and non-averaged SGDIR under moment, source, and capacity assumptions. For a particular value of the source parameter, these bounds are of order $m^{-2}\log^{2}m$, where the number of training samples is of order $m$. For another value of the source parameter, we obtain, for any $ε>0$, bounds of order $m^{-3+ε}$, provided that the capacity parameter exceeds $ε^{-1}$. We also establish a lower bound that matches our upper bounds in certain regimes up to a polylogarithmic factor. In the noisy case, we provide an instance-based comparison between SGDIR and ridge regression. Under general assumptions and a mild lower bound on the regularization parameter, we show that the expected excess risk of SGDIR is no larger than that of ridge regression, up to a polylogarithmic factor. Numerical experiments on synthetic and real data are consistent with our theoretical findings.

0.35

Optimal approximation of smooth functions by ReLU neural networks

cs.LG stat.MLmath.NA ·2026-10-15 ·Thomas Nagler
similarity 0.59
Abstract

We study uniform approximation of the Hölder ball $\mathcal H_1^s([0,1]^D)$ by fully connected ReLU networks. Except in the one-dimensional Lipschitz case, existing constructions remain separated from the information-theoretic efficiency limit. This article closes the gap for every $s>0$ and $D\ge1$: networks with width $O(N)$, depth $O(L)$, and parameter magnitude $O(1)$ attain uniform approximation error of order $(N^2L^2\log N)^{-s/D}$. No relation between width and depth is required. The construction uses new encoding and decoding mechanisms that exploit higher-order finite-difference bounds for local Taylor coefficients of the target function. As a statistical consequence, empirical risk minimizers over the corresponding clipped network classes attain the minimax regression rate $n^{-2s/(2s+D)}$ without additional logarithmic factors. The paper also gives a detailed exposition of the key approximation techniques, covering both established and new mechanisms.

0.19

Adversarially Robust PAC Learning with Optimal VC Rates

cs.LG stat.MLmath.ST ·2026-09-21 ·Steve Hanneke, Amirreza Shaeiri
theory similarity 0.58
Abstract · 35 pages, 2 figures

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}$ of $\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.

0.17

Constrained Online Learning with Noisy Constraint Values

cs.LG cs.AImath.OC ·2026-09-07 ·Vaneet Aggarwal
theory similarity 0.58
Abstract

We study constrained online convex optimization with adversarial constraints and conditionally unbiased, finite-variance observations of constraint values and gradients. Under common feasibility, our \LEDGER\ algorithm attains $O(\sqrt T)$ expected regret and $O(\sqrt{T\log(eT)})$ expected budget violation, the largest cumulative overspend over any window. It uses a reflected exponential potential, clipped signed observations, and predictable adaptive regularization, with one feedback triple and one projection per round. Neither a Slater condition, independence between feedback channels, nor an absolute constraint-value bound is needed. A Gaussian testing lower bound proves that the budget rate has optimal horizon dependence under square-root regret at fixed positive noise, including the logarithm. The same obstruction holds for terminal violation, so the logarithm is not a cost of maximizing over windows; an $O(\sqrt T)$ budget bound instead forces linear regret. In contrast, fixed positive Gaussian value noise yields a joint regret--hard-violation lower bound of $Ω(\min\{σ,1\}T/\log^2 T)$, even with exact gradients in one dimension. The hard-violation construction matches arbitrarily many moments while preserving a feasible-endpoint gap and constant endpoint probabilities. Together, the bounds separate uncertainty about hard feasibility from learnable signed budgets. Deterministic restarts remove the horizon input without changing either upper rate.

0.26

Hard Way, The Only Way: Provable Merits of Training on Hardest Examples

cs.LG ·2026-10-15 ·Elvis Dohmatob
theory similarity 0.58
Abstract

Despite a surge of empirical interest in the ``unreasonable effectiveness'' of drastic data pruning for AI systems, a unified theoretical understanding of this phenomenon remains elusive. In this work, we provide a precise high-dimensional theory of learning under data pruning via weighted empirical risk minimization (ERM). As in previous work, we analyze a setting where pruning is performed along a one-dimensional subspace of the input space. Our analysis precisely characterizes the limiting test error curves in the regime where the input dimension N and sample size P tend to infinity with a fixed ratio N/P. The resulting theory recovers several recent results in the literature as special cases and provides a general lens to evaluate how pruning strategies interact with the loss function and label noise. Crucially, we characterize the optimal pruning strategy in the high-sample regime where P greatly exceeds N. We demonstrate that strategic pruning can accelerate the decay of classification test error from the classical sqrt(N/P) rate, typical of vanilla ERM with loss functions without exponential tail (e.g., quadratic loss), to the much faster Bayes-optimal scaling of order N/P. In this setup, we prove that, surprisingly, this optimal performance is achieved by a drastic pruning strategy: discarding almost all training data except for a small proportion, consisting strictly of the 2N hardest training examples.

0.28