Four Extensions of the Universal Law of Robustness: Log-Concave Covariates, Heterogeneous Mixtures, Vector-Valued Predictors, and Markovian Data
cs.LG, math.PR, stat.ML
Submitted: 2026-08-26
Updated: 2026-08-26
Comments: 62 pages
License: http://creativecommons.org/licenses/by/4.0/
The gist: Bubeck and Sellke's universal law of robustness says that fitting n noisy samples below the noise level with a class of p real parameters forces a Lipschitz constant of order sqrt nd/p…
Terminology
Abstract
Bubeck and Sellke's universal law of robustness says that fitting n noisy samples below the noise level with a class of p real parameters forces a Lipschitz constant of order sqrt nd/p, when the covariate distribution on R d is isoperimetric: smooth interpolation costs a factor d of overparametrization. Its hypotheses are Gaussian-type concentration, a homogeneous covariate law, scalar outputs, and independent samples; we relax each one. Exponential concentration suffices, at the unchanged rate and absolute constant and at the price of a capacity burn-in, some form of which we show is necessary; this gives the law for normalized log-concave covariates, with a d loss from the current KLS bound. For heterogeneous mixtures the worst component constant is replaced by the weighted average of the component constants, under a typicality condition on the mixture composition. For vector-valued predictors the bound at the Frobenius Lipschitz scale is free of the output dimension K, and the Euclidean bound loses only K-1/2, a loss that covariate-independent noise removes. Stationary Markov covariates retain the i.i.d. rate, the pseudo-spectral gap entering only the sample-size conditions. One master theorem carries the shared argument, and constants are explicit throughout.
Sources
- A direct proof of a unified law of robustness for Bregman divergence losses
- A Law of Robustness beyond Isoperimetry
- Concentration inequalities for Markov chains by Marton couplings and spectral methods
- Beyond the Universal Law of Robustness: Sharper Laws for Random Features and Neural Tangent Kernels
- A law of robustness for two-layers neural networks
- A Universal Law of Robustness via Isoperimetry
- Minimax optimality of deep neural networks on dependent data via PAC-Bayes bounds
- Dimension-free log-Sobolev inequalities for mixture distributions
- LipNeXt: Scaling up Lipschitz-based Certified Robustness to Billion-parameter Models
- Bernstein-type Inequalities for Markov Chains and Markov Processes: A Simple and Robust Proof
- Logarithmic bounds for isoperimetry and slices of convex sets
- No Free Prune: Information-Theoretic Barriers to Pruning at Initialization
- Stability Bound for Stationary Phi-mixing and Beta-mixing Processes
- A law of robustness for two-layer neural networks with arbitrary weights
- The Price of Robustness: Stable Classifiers Need Overparameterization
- Bridging the Gap: Rademacher Complexity in Robust and Standard Generalization
Related papers
- A Physics-Regulated Neural Framework for Learning 3D Grain Growth Dynamics
- FlexMoE: Learning One-for-All Multi-Budget Expert Pruning for Flexible MoE Deployment
- OptiMind: Improving Small Language Models for Optimization Modeling through Formulation Guidance and Multi-Turn Learning
- Staying in the Sweet Spot: Boost Reasoning Evolution via Responsive Rollout Difficulty Manipulation
- Examining the Impact of Data and Training Methods on Emergent and Subliminal Misalignment
- Rethinking Black-Box On-Policy Distillation: A Rubric-based Analysis