Oriel — AI & technology worth noticing, every day.

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

SourceExternal IDURL
arXiv AI Papersoai:arXiv.org:2611.03653v1https://arxiv.org/abs/2611.03653 Read discussion