We study the last iterate of the projected subGradient Method (sGM) for convex Lipschitz objectives defined on $\mathbb{R}^d$. We prove that, for a finite horizon $n$ and a constant stepsize $\eta=\Theta(1/\sqrt n)$, the last iterate achieves an optimization error of order $d/\sqrt n$, showing that the extra $\log n$ factor appearing in high dimensions is unnecessary in every fixed dimension. We complement this result with a matching linear-in-$d$ lower bound and show that the sharp worst-case dimension-horizon dependence is of order $\min\{d,\log n\}/\sqrt n$. This solves, in particular, a COLT open problem posed by Koren and Segal in 2020 and shows that the correct dependence on the dimension is linear rather than logarithmic.
A variant of the cubic-regularized Newton method for nonconvex optimization that is parameter-free in that it requires no prior knowledge of problem-dependent parameters is analyzed, and an oracle complexity bound is derived for finding an $(varepsilon, \delta)-second-order stationary point.
The Johnson--Lindenstrauss lemma asserts that every set of $n$ points in $d$-dimensional Euclidean space embeds into $O(\varepsilon^{-2}\log n)$-dimensional Euclidean space with distortion at most $1+\varepsilon$. Larsen and Nelson conjectured that the optimal target dimension throughout the full range of the parameters $n,d, \varepsilon$ is \[ \Theta\left(\min\left\{d,n-1,\frac{\log(2+\varepsilon^2n)}{\varepsilon^2}\right\}\right). \] We resolve this conjecture in the affirmative. In fact, we prove the stronger statement that the upper bound is attained by a linear map. The matching lower bound, due to Larsen--Nelson and Alon--Klartag, holds even for nonlinear embeddings.
Let $2\le k\le n$, let $\Omega\subset\mathbb{R}^n$ be open and convex, and let $u$ be a convex viscosity solution of $\sigma_k(D^2u)=1$ in $\Omega$. We prove that the set on which $u$ fails to be locally $C^2$ has vanishing $(n-1)$-dimensional Hausdorff measure. In the intermediate range $3\le k<n$, this gives a codimension-one refinement of the known almost-everywhere partial regularity, and the exponent is sharp. More generally, for a convex viscosity subsolution of $\sigma_k(D^2u)\ge\lambda>0$, we obtain Hausdorff bounds for strata defined by the affine dimension of all supporting contact sets. The proof combines a support-dependent Chou--Wang barrier argument, an estimate for the product of the smallest $k$ semiaxes of a John ellipsoid, and Mooney's convex section-covering theorem. As a direct analytical consequence, the full distributional Hessian is absolutely continuous and $u\in W^{2,1}_{\mathrm{loc}}(\Omega)$, yielding a $k$-Hessian counterpart of the $W^{2,1}$ regularity known for singular Monge--Amp\`ere solutions. In a logically separate structural part, we characterize the distinguished number of flat directions, $n-k+1$, by an asymptotic infimum mean-value formula over affine sections, and explain how this mean-value heuristic leads to the supporting-contact geometry used in the proof.
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
In this paper, we establish a doubling argument to obtain Hessian estimates for convex solutions to the Hessian quotient equation $\frac{\sigma_n}{\sigma_k}(D^2u) = f(x,u,Du)$ for $k=n-1$ and $k=n-2$ under the condition that $1/f$ is concave in the $Du$ variable. In particular, our approach is pointwise and does not make use of the Legendre transform or integral-based local maximum principles. We provide a counterexample demonstrating that interior estimates can fail if no structural assumption is imposed on $f$ in the $Du$ variable. Finally, we extend our doubling argument to general Hessian quotient equations $\frac{\sigma_l}{\sigma_k}(D^2u) = f(x,u,Du)$ for $k \in \{l-1, l-2\}$, under a similar structural condition imposed on $f$ in the $Du$ variable, alongside an additional structural concavity assumption on the operator introduced by Lu-Tsai 2026.
A new, fast adaptive regularization methods is proposed and analyzed under local Lipschitz smoothness of the $p$-th order tensor, matching the complexity bounds of standard tensor methods under global Lipschitz smoothness yp to logarithmic terms.