CS Paper Radar

"Deep lifts": Neural networks can generalize even with the dumbest optimizer

Sunil Madhow, Yu-Xiang Wang

cs.LG ·submitted 2026-10-16 06:37 UTC · v2

Abstract

Given a labeled dataset $\{(x_i, y_i)\}_{i = 1}^n$, consider drawing a parameter vector $\hatθ$ uniformly at random from those that interpolate the data within a width-$W$ depth-$D$ ReLU architecture with continuous weights bounded within $[-M, M]$. We study the generalization properties of $\hatθ$ in the case where the dataset can, in fact, be explained by a smaller $w$-by-$d$ ReLU network. Despite the obliviousness of the selection rule for $\hatθ$, it adaptively generalizes at the rate $\tilde O\left(\frac{wdWD}{n}\right)$, rather than being governed by the VC dimension of the full $W$-by-$D$ hypothesis class. The reason is due to a particular inductive bias in ReLU networks: the $w$-by-$d$ parameter *witnesses* an exponential volume of $W$-by-$D$ interpolating parameters, which dwarfs the volume of poorly generalizing parameters (conditioned on interpolation). We explicitly construct this set of near-equivalent $W$-by-$D$ parameters by a proof technique called *deep lifting*, and then tie the achievable volume to stability properties of the $w$-by-$d$ witness. Examples show that these techniques allow us to convert approximation-theoretic results into generalization guarantees for nonparametric classes. We further show that generalization of uniform-random interpolators can survive label corruptions.

Closest papers

Nearest neighbours by meaning across the whole index.

On the Depth Transfer of Neural Optimizers via L-Smoothness

cs.LG math.OC ·2026-10-09 ·Maximilian Wong, Chenyu Xu, Jiajin Li, Yiping Lu
similarity 0.62
Abstract

Scaling deep learning models efficiently requires predictable performance transfer across compute regimes. Establishing reliable hyperparameter transfer allows optimal training dynamics and structural choices to be discovered on low-cost proxy models, avoiding catastrophic failures during massive-scale training. Existing depth-transfer analyses are architecture-specific and heuristic: hyperparameter transfer is only justified through toy blocks, and both rely on infinite-depth dynamics, a specific initialization, and feature-learning criteria. Building on $L$-smoothness framework of Xu et al. (2026), we understand hyperparameter transfer as how do the Lipschitz and $L$-smoothness constants of the loss scale with the depth $K$? We show that inverse-depth residual branch scaling $α=Θ(1/K)$ is sufficient to make both constants depth-independent at fixed width, uniformly over the bounded parameter domain and for arbitrary $p\to q$ geometries. Because the bounds depend on each residual branch only through its Lipschitz and smoothness constants, the argument applies to general residual networks (including branches of block depth $\geq 2$ such as transformer and ResNet blocks) without assumptions on initialization or correlations between layer weights. Since the smoothness constant controls the curvature penalty in the descent inequality, our bounds motivate a learning-rate scale without an additional depth-dependent curvature correction for updates bounded in the prescribed norm. This provides a geometric explanation of inverse-depth residual scaling and its application to the operator-norm geometries associated with AdamW, Muon, and MOGA. Learning-rate sweeps on GPT-2 (depths 2--128) and CIFAR-100 ResNets (8--32 residual blocks) confirm that Muon and MOGA exhibit stable learning-rate transfer under these prescriptions, with a common optimal rate across a 64-fold increase in depth.

0.19

Resolution-Consistent Greedy Neural Approximation on Infinite-Dimensional Spaces

cs.LG math.FA ·2026-08-21 ·Pablo M. Berná, Antonio Falcó, Diego Mondéjar
similarity 0.61
Abstract

We develop constructive approximation and learning guarantees for shallow neural models with infinite-dimensional inputs observed through finitely many coordinates. The analysis is based on a parameter-normalized neural dictionary and its associated weighted variation class. Within this class, the approximation error separates into a distribution-dependent coordinate-truncation term and a greedy finite-width term. For empirical regression, a fully-corrective greedy procedure yields population guarantees whose statistical complexity is uniform in the retained input resolution. The same framework extends to Hilbert-valued responses without an explicit dependence on the output dimension. The dimension-free statements are statistical, not computational: selecting a new neuron still requires solving a nonconvex parameter-search problem. The quasi-Polish construction underlying recent infinite-dimensional universal approximation results provides a motivating example, and synthetic experiments illustrate the predicted resolution, width, and sample-size regimes.

0.18

Dimension-Free Rank Lifting from Random Hyperplane Arrangements

cs.LG math.PR ·2026-09-30 ·Luca Becchetti, Matteo Russo, Ruben Skorupinski
theory similarity 0.59
Abstract

We study the width required for a randomly initialized hidden layer of a neural network to achieve rank lifting. Namely, given a dataset $X \in \mathbb{R}^{m \times d}$ of $m$, $d$-dimensional input vectors separated by an angle of at least $θ$, we consider the random feature matrix $σ(XR)$, where $R$ is standard Gaussian. For positively homogeneous nonpolynomial activations, which include sign, Heaviside, ReLU, and ReLU powers among others, we prove that $$n \gtrsim \frac{1}θ\max\left\{m,\log\left(\frac{1}δ\right)\right\}$$ neurons suffice for $σ(XR)$ to have full row rank $m$ with probability at least $1-δ$. This dimension-free bound exponentially improves the previous general-dimensional guarantee for sign features (Drago et al., 2026) and is essentially tight. The proof shows that one random feature column escapes every proper subspace of $\mathbb{R}^m$ with probability $Ω(θ)$, using a coupling of nearby Gaussian directions and a local crossing of the induced hyperplane arrangement. We also study stable rank lifting, where the goal is to establish a quantitative analogue of exact rank lifting, i.e., a lower bound on the smallest eigenvalue of the empirical feature Gram matrix in high-probability. Our analysis unifies and generalizes stable rank guarantees for all $q$-homogeneous non-polynomial activations following prior work in Panigrahi et al. (2020) and Song (2026). In particular, we combine a diagonally dominant Taylor tail of the population kernel with truncation and matrix concentration, to show that for positively homogeneous nonpolynomial activations, stable rank lifting is achieved at width $$n \gtrsim C^q \frac{m}{θ^{2q+1}} \log^{2q+\frac{1}{2}}\left(\frac{m}θ\right) \log\left(\frac{m}δ\right),$$ where $q$ is the degree of the activation and $C > 0$ is some universal constant.

0.20

Every Layer Counts: An Exponential $L_2$ Depth Hierarchy for ReLU Networks

cs.LG ·2026-08-24 ·Itay Safran
theory similarity 0.59
Abstract

We prove a depth hierarchy for ReLU neural networks in which every additional ReLU layer can save exponentially many neurons. For all $k\geq2$, we construct a globally $[0,1]$-valued, $1$-Lipschitz function realized by a depth-$(k+1)$ network of width $\mathcal{O}(d^4)$, whereas any depth-$k$ network with unrestricted weights and width at most $\frac{2^d}{2d(k-1)}$ has squared $L_2$ error at least $1/24$ under an absolutely continuous distribution supported at exponential distance from the origin. To the best of our knowledge, this is the first exponential hierarchy across all adjacent fixed depths, and the first exponential separation for ReLU networks between two fixed depths whose shallower network has depth at least $3$. The lower bound also immediately yields the corresponding hierarchy for exact computation. Moreover, the case $k=2$ gives a compactly supported separation between depths $3$ and $2$ with unrestricted shallow-network weights, answering a question raised by Safran, Eldan, and Shamir (2019). The distribution used in our construction nevertheless has all its mass at exponential radius, placing the hierarchy outside the regularity regime in which such a separation would imply major threshold-circuit lower bounds. We also prove an exact separation for a more regular target, which is globally $[0,1]$-valued and $\mathcal{O}(\sqrt d)$-Lipschitz and maps the unit hypercube onto $[0,1]$. It is computed by a polynomial-width depth-$4$ network, whereas any depth-$3$ network agreeing with it on the unit hypercube requires exponentially many first-layer neurons, even with unrestricted weights.

0.30

Optimal approximation of smooth functions by ReLU neural networks

cs.LG stat.MLmath.NA ·2026-10-15 ·Thomas Nagler
similarity 0.58
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

Nearly Tight Rademacher Bounds for Sparsely Activated Neural Networks

cs.LG stat.ML ·2026-09-08 ·Xiaoyu Li, Zhizhou Sha, Jiaojiao Jiang, Junbin Gao, Andi Han
similarity 0.57
Abstract

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.

0.28

Learning Rate Transfer and Feature Learning Across Depth for Constrained Spectral Optimizers: Complete Scion

cs.LG math.OC ·2026-11-11 ·Eline Pot, Laurent Lefebvre, Mathieu Segond, Antonio Silveti-Falls
top venue similarity 0.57
Abstract

Hyperparameter transfer across model depth is instrumental in training deep models, as it enables learning rates calibrated on shallow networks to be effectively applied to deeper architectures. The recent CompleteP framework establishes a $1/L$ residual scaling rule that demonstrates this for Adam-family optimizers. We study whether similar transfer extends to constrained optimization methods, specifically Frank-Wolfe and projected non-Euclidean normalized steepest descent, where updates are determined by linear minimization oracles. We derive scaling rules for these methods which confirm that the $1/L$ residual scaling applies, although the arguments differ from the Adam-family optimizers. Our analysis supports depth-wise transfer and width-wise transfer of the learning rate for the Scion algorithm while ensuring feature learning and avoiding the kernel-regime. In experiments on NLP transformers (nanoGPT on FineWeb), vision transformers (DeiT on ImageNet), and vision MLPs (MLP-Mixer on CIFAR-10), we observe learning rate transfer across depth and feature learning for appropriately chosen residual scaling.

0.33

Dimension-Free Scaling Laws for Size Generalization: An Exponential Separation

cs.LG cs.AI ·2026-10-13 ·Behrooz Tahmasebi, Melanie Weber
published similarity 0.57
Abstract · 32 pages, 1 figure. An extended abstract of this paper appeared at the ICML 2026 HiLD Workshop (July 10, 2026)

Modern machine learning models increasingly operate on variable-size structured data, such as sets and graphs. A central requirement is \emph{size generalization}: the ability of a model trained on inputs of one size to generalize to inputs of a different, potentially much larger, size. Classical statistical learning theory, however, primarily considers fixed input domains, and its guarantees often deteriorate with input dimension. Although extensive work has established when models on sets and graphs can be transferred across input sizes, such results do not characterize the statistical cost of doing so: the sample complexity of size generalization, and its relationship to classical in-domain learning, remain largely unknown. We develop a statistical learning theory of size generalization and establish a sharp exponential separation in sample complexity. Letting $n$ denote the number of training samples, we show that polynomial source decay is insufficient for efficient size generalization: while it yields error $n^{-Θ(1)}$ and hence polynomial sample complexity for in-domain learning, size-generalization error decays only as $(\log n)^{-Θ(1)}$, yielding an exponential separation. Thus, polynomial in-domain sample complexity can become exponential across sizes. We then identify an exponential source condition under which size generalization achieves error $n^{-Θ(1)}$, recovering polynomial sample complexity. These guarantees are independent of input dimension and depend only on the number of training samples, yielding dimension-free scaling laws. We also provide matching minimax lower bounds, establishing optimality. To our knowledge, this work provides the first dimension-free minimax theory of size generalization and a rigorous characterization of when, and at what statistical cost, learning can transfer across input sizes.

0.31