Four Extensions of the Universal Law of Robustness: Log-Concave Covariates, Heterogeneous Mixtures, Vector-Valued Predictors, and Markovian Data

Bubeck and Sellke showed that fitting \(n\) noisy samples below the noise level with \(p\) real parameters forces a Lipschitz constant of order \(\sqrt{nd/p}\) when covariates on \(\mathbb{R}^d\) are isoperimetric. Smooth interpolation therefore costs a factor \(d\) of overparametrisation. The original assumptions are Gaussian-type concentration, a single covariate law, scalar outputs and independent samples.

This paper relaxes each one. Under exponential concentration the rate and absolute constant are unchanged, at the price of a capacity burn-in that it shows to be necessary in some form. For mixtures, a weighted average of component constants replaces the worst one. For vector outputs, the bound at the Frobenius Lipschitz scale does not depend on the output dimension \(K\). Stationary Markov covariates keep the independent rate, with the pseudo-spectral gap entering only the sample-size conditions.