We study minimum-norm interpolation (MNI) in overparameterized linear regression with isotropic Gaussian covariates, in settings where the MNI has no closed-form formula. Whereas most prior work relied on Gaussian comparison tools such as the convex Gaussian min--max theorem (CGMT), our approach uses tools from high-dimensional geometry and probability. First, when the norm is in isotropic position, we obtain an ``offset''bound that controls the amount by which the MNI shrinks the ground truth. Second, we show that the ``intrinsic''variance of the $\ell_1$-MNI is at most $O(\tfrac{1}{n\log(d/n)^2})$, using a variant of Talagrand's $L_1$--$L_2$ inequality due to Cordero-Erausquin and Ledoux [2012], together with a classical result of Gluskin [1988]. We recover the sharp mean-squared error (MSE) bound for the $\ell_1$-MNI obtained by Wang et al. [2022], using the work of Fleury [2012] on the symmetric Gaussian polytope, which is defined via \[ P_{n,d} := \mathrm{conv}\{\pm X_i\}_{i=1}^{d} \text{ where } X_i \overset{\mathrm{i.i.d.}}{\sim} N(0,\mathrm{I}_{n \times n}), \] rather than CGMT. Our methods also imply improvements on previous results in high-dimensional geometry that may be of independent interest. First, we show that with overwhelming probability, the ratio between the isotropic constant of $P_{n,d}$ and that of the Euclidean ball in $\mathbb{R}^n$ is at most $1+O((\log(d/n))^{-2})$, improving a result of Klartag and Kozma [2009]. We also establish a refined weighted thin-shell estimate on $P_{n,d}$, and provide an elementary proof of the main theorem of Fleury [2012].
Given a complete doubling metric measure space $(X,\rho,\mu)$ supporting a Poincar\'e inequality, we prove weak-type characterizations of the Sobolev space $\dot{W}^{1,p}(\mu)$ and the space of functions of bounded variation, achieving a full analogy in general Poincar\'e spaces with the Euclidean results of Brezis et al. [Anal. PDE 17 (2024), 943-979]. The main novelty is that the finiteness of a weak-type norm, which only refers to differences or mean oscillations of $f$ without assuming any smoothness a priori, already guarantees the membership of $f$ in the relevant Sobolev or BV space. This distinguishes our contribution from the recent work of F. Dai et al. [Adv. Math. 502 (2026), Paper No. 111153], where the related norm-equivalence was obtained under the a priori Lipschitz assumption on $f$. A key intermediate step in our approach is a new localized Bourgain-Brezis-Mironescu type characterization. More precisely, we prove that, if $p\in(1,\infty)$ and $\gamma\in\mathbb R\setminus\{0\}$, then, for any $f\in L^1_{\mathrm{loc}}(\mu)$, \begin{equation*}\tag{$*$} \|f\|_{\dot W^{1,p}(\mu)} \sim \|\rho^{-1}\phi^{-\gamma}F\|_{L^{p,\infty}(\phi^{\gamma p}V^{-1})}, \qquad F\in\{\Delta f,m_f\},\quad \phi\in\{\rho,V\}, \end{equation*} where the homogeneous Sobolev space $\dot{W}^{1,p}(\mu)$ is defined by the minimal $p$-weak upper gradient and, for any $x,y\in X$, we denote $V(x,y):=\mu(B(x,\rho(x,y)))$ and $\Delta f(x,y):=|f(x) - f(y)|$, and $m_f(x,y)$ is the mean oscillation of $f$ on the ball $B(x,\rho(x,y))$. For $p=1$, the equivalence $(*)$ holds after replacing $\|f\|_{\dot W^{1,1}(\mu)}$ by a bounded variation norm and restricting the parameters to the optimal ranges $\gamma\in(-\infty,-1)\cup(0,\infty)$ for $\phi=\rho$ or $\gamma\in (-\infty,-\frac1d)\cup(0,\infty)$ for $\phi=V$, where $d\in(0,\infty)$ is the lower dimension of $X$.
Tuomas Hytönen, Dachun Yang, Wen Yuan et al.· 0 citations
We prove an $\Omega(L/T)$ lower bound for the convergence rate of minimization in the class of functions that are convex and $L$-smooth relative to negative entropy on the standard $d$-simplex, valid for every first-order method when $d = \Omega(T^2)$. In particular, this shows that mirror descent is optimal up to a logarithmic factor in this class. This may be surprising due to the fact that accelerated methods are readily available under the assumption of smoothness in $\ell_1$-norm. While Dragomir et al. (Mathematical Programming, 2022) have already showed that acceleration might be impossible under relative smoothness, their prox-function is pathological and constructed together with the hard instance. In contrast, we show non-acceleration for a specific prox-function with particularly favorable structure. We also extend the result to the quantum setting, proving the same lower bound in the class of functions $L$-smooth relative to negative von Neumann entropy on the spectrahedron of $d \times d$ Hermitian positive-semidefinite matrices with unit trace.
Jacob M. Aguirre, Dmitrii M. Ostrovskii· 0 citations
We study Langevin-based methods for non-convex optimization under smoothness and dissipativity assumptions. Our focus is on obtaining non-asymptotic bounds for the expected excess risk rather than sampling guarantees for the full target distribution. The key ingredient of our analysis is a direct passage from relative entropy to objective-value error, based on a weighted Csisz\'ar--Kullback--Pinsker inequality and exponential-moment estimates. This avoids intermediate Wasserstein bounds and yields sharper dependence on the Log-Sobolev constant, a quantity that may scale exponentially with the inverse temperature and the dimension in non-convex problems. We first analyze the Unadjusted Langevin Algorithm with exact gradients and derive explicit bounds on $\mathbb{E}[F(x_k)]-\min F$ in terms of the inverse temperature, dimension, stepsize, smoothness and dissipativity parameters, and the Log-Sobolev constant. We then extend the result to an inexact-gradient version of ULA, allowing for biased and stochastic gradient surrogates whose mean-square error grows at most quadratically in the state. This framework covers stochastic gradients and zeroth-order estimators based only on function evaluations. In particular, we show that both Gaussian and spherical finite-difference estimators fit into the inexact-ULA theory and obtain explicit function-evaluation complexity bounds for zeroth-order Langevin optimization. To the best of our knowledge, these are the first non-asymptotic global non-convex optimization complexity bounds for zeroth-order ULA. We also provide numerical experiments illustrating the behavior of the proposed zeroth-order Langevin schemes.
E. Naldi, Marco Rando, Lorenzo Rosasco et al.· 0 citations
Exhaustive moment fitting in this constant-dimensional space produces a proper mixture and, together with the dimension-free moment characterization of Gaussian mixtures, achieves the optimal Hellinger rate in polynomial arithmetic time for every fixed $k$.
We prove dimension-free higher-order Sobolev norm estimates on open convex subsets of $\mathbb{R}^n$ with respect to Gaussian measure and use them to obtain norm equivalence on nonempty open convex subsets of $\ell^2$ endowed with a nondegenerate Gaussian measure. To the best of our knowledge, this is the first such equivalence theorem on a proper open subset of an infinite-dimensional Hilbert space, beyond the earlier whole-space results. We also prove the Malliavin--Sobolev norm equivalence for all $p\in[1,\infty)$ and $k\ge2$, including the case $p=1$, $k\ge3$ left open by Addona--Muratori--Rossi in \cite{AddonaMuratoriRossi}.
The goal of this work is to introduce a notion of mean curvature for level sets of functions in non-smooth spaces with Ricci curvature bounded below, and to prove that it satisfies sharp geometric inequalities. More precisely, we define a suitable Willmore functional $\mathcal{W}$ on Sobolev functions, whose domain of finiteness is dense in $L^p$ for any $1\le p<\infty$. For any function with finite Willmore energy, we show that almost all of its level sets admit a mean curvature vector satisfying the natural integration by parts formula with respect to the tangential divergence. As a main application, we show that in ${\rm RCD}(0,N)$ spaces with Euclidean volume growth, almost every level set of the electrostatic potential possesses a mean curvature vector in the above sense. Furthermore, we prove that this vector satisfies the same sharp Willmore inequality as in the smooth setting, alongside rigidity and almost-rigidity statements. Finally, as a technical tool, we generalize the sharp isocapacitary inequality to the non-smooth setting.
