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.
We analyze a variant of the cubic-regularized Newton method for nonconvex optimization. This variant is parameter-free in that it requires no prior knowledge of problem-dependent parameters. Under the generalized smoothness condition $\|\nabla^3 f(x)\| \leq L_0 + L_1 \|\nabla f(x)\|$, we derive an oracle complexity bound for finding an $(\varepsilon, \delta)$-second-order stationary point. This assumption is weaker than the generalized smoothness conditions used in existing analyses of second-order methods, while the complexity bound improves upon existing guarantees for parameter-free second-order methods. In particular, when $L_1 = 0$, the bound matches the optimal dependence on $L_0$ as well as on $\varepsilon$, $\delta$, and the initial function value gap, up to additive logarithmic terms. To establish this bound, we derive Taylor-type inequalities and prove their equivalence to the generalized smoothness condition.
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. For nonconvex problems, it achieves the optimal $\mathcal{O}\!\left(|\log(\epsilon)|\epsilon^{-(p+1)/p}\right)$ complexity to obtain first-order $\epsilon$-stationary points and in the convex case, it yields $\mathcal{O}\!\left(|\log(\epsilon)|\epsilon^{-1/p}\right)$ iterations to drive the optimality gap below $\epsilon$, thus matching the complexity bounds of standard tensor methods under global Lipschitz smoothness yp to logarithmic terms. The proposed algorithm follows the line of standard tensor methods with an appropriately chosen regularization and suitable modifications. Initial numerical experiments and comparisons for some nonconvex regression problems are made with the standard adaptive cubic regularization where we showcase some potential of the proposed method.