This paper establishes high-probability, non-asymptotic upper bounds for the population excess risk of minimum $\ell_q$-norm interpolating estimators in linear regression, valid for all $1<q<\infty$ under three scenarios: convex concentration, mild moment assumptions and log-concavity. Consequently, we derive sufficient conditions for these estimators to exhibit benign overfitting. Our analysis hinges on a Feature Space Decomposition (FSD) framework, which naturally highlights the self-regularizing properties of minimum norm interpolants as well as the role of alignment between the signal and the features for benign overfitting. From a technical perspective, our approach circumvents the traditionally used Convex Gaussian Min-max Theorem (CGMT) by instead leveraging the Dvoretzky-Milman theorem. We emphasize that the FSD method has the potential to refine standard uniform convergence approaches. Furthermore, the isomorphic Dvoretzky-Milman theorem established herein -- proven under the three scenarios mentioned above -- for the $\ell_q$-norm is of independent mathematical interest.
A statistical theory is developed that characterizes how regularization geometry and signal sparsity govern generalization near interpolation in the prototypical setting of high-dimensional regression and identifies regimes in which sparsity-promoting regularization makes exact interpolation much more accurate than app...
G. Kur, I. Rugina, C. Dominé et al.· arXiv.org· 0 citations
This paper establishes a unified non-linear regularization framework for high-dimensional $M$-estimation, encompassing both linear regression and Cox's proportional hazards models. Rather than relying on traditional additive non-convex penalties, the proposed paradigm embeds sparsity directly into the parameter mapping...
Efficient preconditioning plays an important role in large-scale first-order optimization. In this paper, we propose an adaptive accelerated optimistic dual averaging ($\text{A}^2$ODA) method for unconstrained convex optimization that adopts low-cost preconditioning based on $p$-norm geometry for $p\in[2,\infty]$. The...
This paper develops a method to analyze benign overfitting in linear regression for general norms and general (sub-Gaussian) distributions and proves that minimum-p-norm interpolation with p>1 can benignly overfit even for non-Gaussian distributions, under suitable conditions.
Daniel Barzilai, Ohad Shamir· arXiv.org· 0 citations
Convex regression provides a flexible nonparametric estimation framework while incorporating appropriate shape information. However, its standard least-squares formulation has $O(n^2)$ supporting-hyperplane constraints creating a computational bottleneck as the sample size $n$ increases. We study a $K$-nearest-neighbor...
We develop a general methodology based on the Feature Space Decomposition framework for establishing explicit, instance-specific sharp rates for the expected estimation error of convex-constrained least squares estimators in the sequence model, without requiring estimates of localized Gaussian mean widths. We apply thi...
Zong Shang· 0 citations
We use cookies to run the site and, with your consent, for analytics and to show ads.
See our Cookie Policy.