Four Extensions of the Universal Law of Robustness: Log-Concave Covariates, Heterogeneous Mixtures, Vector-Valued Predictors, and Markovian Data
Paper · https://arxiv.org/abs/2611.03653
arXiv:2611.03653v1 Announce Type: new 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 $\mathbb{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 $\log 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.
First seen by Oriel on .
AI summary
The paper extends the universal law of robustness to log-concave covariates, heterogeneous mixtures, vector-valued predictors, and stationary Markov data through one master theorem with explicit constants.
- Exponential concentration preserves the original rate and absolute constant after a necessary capacity burn-in, yielding normalized log-concave results with a log d loss from the current KLS bound.
- For heterogeneous mixtures, a weighted average of component constants replaces the worst-component constant when the mixture composition satisfies a typicality condition.
- Vector-valued predictors incur no output-dimension K penalty at the Frobenius Lipschitz scale; the Euclidean bound loses K^{-1/2}, removable with covariate-independent noise.
- Stationary Markov covariates retain the i.i.d. rate, while the pseudo-spectral gap affects only sample-size conditions.
#robustness #log-concave distributions #vector-valued predictors #markov data
Generated by gpt-5.6-sol. Check the original for details.
Aliases
| Source | External ID | URL |
|---|---|---|
| arXiv AI Papers | oai:arXiv.org:2611.03653v1 | https://arxiv.org/abs/2611.03653 Read discussion |