arXiv Machine Learning

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

arXiv:2610. 23009v1 Announce Type: new Abstract: Given a labeled dataset $\{(x_i, y_i)\}_{i = 1}^n$, consider drawing a parameter vector $\hat{\theta}$ uniformly at random from those that interpolate the data within a width-$W$ depth-$D$ ReLU architecture with continuous weights bounded within $[-M, M]$.

arXiv Statistics ML
Oct 2

Transferable Graph Metanetworks

Transferable Graph Metanetworks extend the graph metanetwork paradigm to predict properties of neural networks of varying widths. By enforcing invariance to width-dependent representations and continuity across similar functions, the proposed modifications enable robust size generalization, especially for networks trained under the maximal‑update parameterization (μP) up to 42× the training width. The authors provide empirical evidence across multiple tasks and theoretical guarantees in the infinite‑width limit, explaining both successes and limitations under different parameterizations.

By Yuxin Ma, Adir Dayan, Yam Eitan, Haggai Maron, Soledad Villar
arXiv AI
Sep 24

Path Regularization: A Near-Complete and Optimal Nonasymptotic Generalization Theory for Multilayer Neural Networks and Double Descent Phenomenon

The paper presents a near-complete, nonasymptotic generalization theory for multilayer neural networks using path regularization, applicable to broad Lipschitz loss functions without requiring bounded loss or extreme network hyperparameters. It provides an explicit upper bound that addresses approximation rates in generalized Barron spaces and demonstrates the double descent phenomenon for ReLU networks. The authors claim near-minimax optimality for regression problems and plan to establish matching lower bounds in future work.

By Hao Yu
arXiv Machine Learning
Oct 19

Escaping Parameter Space: Tight Generalization Bounds via Representation Quality

The paper presents a tight generalization bound for deterministic neural networks that relies on the quality of their last hidden layer representations rather than traditional parameter-space metrics. By using a parameter‑free k‑nearest‑neighbor classifier to assess representation quality, the bound decomposes into three measurable components—local class geometry, decoder‑network agreement, and training stability—providing both a non‑vacuous certificate and a diagnostic tool for understanding generalization. Experiments show the bound achieves an 8.0‑percentage‑point gap to test error on CIFAR‑10 with ResNet‑18, yields the first non‑vacuous certificates on CIFAR‑100, and certifies 1.4 % on CIFAR‑10 and 23.1 % on 1,000‑class ImageNet using frozen DINOv2 representations.

By Niclas G\"oring, Shuofeng Zhang, Branton DeMoss, Ard A. Louis
arXiv Machine Learning
Sep 4

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

arXiv:2609. 03129v1 Announce Type: cross Abstract: 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.

By Ruiyang Hong, Hrad Ghoukasian, Anastasis Kratsios
arXiv Machine Learning
Jul 14

Approximation of Analytic Functions by ReLU Neural Networks with Adjustable Depth and Width

arXiv:2607. 10589v1 Announce Type: cross Abstract: In contrast to most studies on neural network approximation theory that characterize results through a single parameter, such as the total number of network parameters, \cite{shen2020deep} pioneered the characterization of approximation rates as a joint function of the width parameter $N$ and the depth parameter $L$, thereby granting greater architectural flexibility.

By Yanming Lai, Defeng Sun, Yang Wang
arXiv Statistics ML
Oct 1

Grokking through the Lens of Minimum-Norm Interpolation

The paper develops a statistical theory for minimum‑norm interpolation in high‑dimensional regression, showing how regularization geometry and signal sparsity affect generalization. It identifies regimes where sparsity‑promoting regularizers yield exact interpolation that is far more accurate than approximate fitting, and proves a zero–one generalization law for strongly overparameterized noiseless problems. The authors also characterize training and generalization errors along ρ‑regularization paths when feature dimension and sample size are proportional, demonstrating that generalization improves with more sparsity‑promoting norms and sparser targets, and that small changes in regularization strength can cause large shifts in generalization. whyItMatters":"The work provides a quantitative understanding of delayed generalization (grokking) and reveals a statistical instability in minimum‑norm interpolation, offering insights that could guide the design of regularizers for better generalization in overparameterized models."

By Gil Kur, Ileana Rugina, Cl\'ementine Carla Juliette Domin\'e, Marco Mondelli
arXiv Machine Learning
Oct 21

Communication Complexity of Universal Features

arXiv:2610.27402v1 Announce Type: cross Abstract: Motivated by the notion of features from machine learning, we study the complexity of representing data that allows for evaluation with a given famil...

By Lunjia Hu, Anish Jayant, Peter Li, Princewill Okoroafor, Abhishek Shetty