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 parameter...
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 codime...
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 lo...
Jacob M. Aguirre, Dmitrii M. Ostrovskii· arXiv.org· 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 $\log f$ is convex in the $Du$ variable. In particular, our approach is pointwise and does not...
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.
S. Jerad· 1 citation
We use cookies to run the site and, with your consent, for analytics and to show ads.
See our Cookie Policy.
