Four Extensions of the Universal Law of Robustness: Log-Concave Covariates, Heterogeneous Mixtures, Vector-Valued Predictors, and Markovian Data
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 √(nd/p), when the covariate distribution on ℝ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.
Related
- Approximate Solomonoff Induction: On the Robustness of Learned Universal Predictors
- Stabilizing Private LASSO under Heterogeneous Covariates via Anisotropic Objective Perturbation
- Difference-in-Differences for Heterogeneous Effects of General Treatment Strategies Accounting for Time-Varying Covariates
- Orthogonal polynomials and the centres of the universal central extensions of superelliptic Krichever--Novikov algebras
- Kernel Density Regression Estimation with Covariates on Riemannian Manifolds
BibTeX
@misc{peter2026four,
title = {{Four Extensions of the Universal Law of Robustness: Log-Concave Covariates, Heterogeneous Mixtures, Vector-Valued Predictors, and Markovian Data}},
author = {Tobias J. Peter},
howpublished = {arXiv},
year = {2026},
month = nov,
doi = {10.48550/arxiv.2611.03653},
eprint = {2611.03653},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2611.03653},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - Four Extensions of the Universal Law of Robustness: Log-Concave Covariates, Heterogeneous Mixtures, Vector-Valued Predictors, and Markovian Data
AU - Tobias J. Peter
PY - 2026
DA - 2026/11/01
PB - arXiv
DO - 10.48550/arxiv.2611.03653
UR - https://arxiv.org/abs/2611.03653
AB - 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 √(nd/p), when the covariate distribution on ℝ^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.
ER -