This work constructs a counterexample empirically showing that smoothness alone is not sufficient for the sequential convergence of AdaGrad-type algorithms, and suggesting that additional geometric hypotheses are indispensable for sequential convergence results.
Abstract
We prove sequential convergence results for the AdaGrad algorithm family optimizing convex differentiable objectives. Specifically, we provide necessary and sufficient conditions for the convergence of iterates for the three main AdaGrad variants (AdaNorm, AdaDiag, AdaFull) when the objective is convex and locally Lipschitz-smooth, closing the question left open from the literature. We harness this general result to study the three variants under the generalized $(L_0,L_1)$-smoothness condition and show sequential convergence for sufficiently small constant step size. Moreover, under the so-called $(L_0,L_1)$-polynomially modifiable smoothness assumption, which is a relaxation of the $(L_0,L_1)$ generalized smoothness property and is satisfied by many function classes such as $L$-smooth functions or univariate polynomials, sequential convergence for these AdaGrad variants is proved for arbitrary learning rates. This result provides conditions under which AdaGrad presents adaptivity, i.e., does not require tuning the parameters based on the instance. Finally, we provide numerical illustrations of the behavior of AdaGrad on convex and nonconvex functions. In particular, we construct a counterexample empirically showing that smoothness alone is not sufficient for the sequential convergence of AdaGrad-type algorithms, and suggesting that additional geometric hypotheses (e.g., convexity as in this paper, or the Kurdyka-\L ojasiewicz inequality) are indispensable for sequential convergence results.
Minimizing gradients of a convex function is an important problem across optimization and learning tasks. The gradient provides a directly computable certificate of approximate stationarity, and its minimization usually implies stronger results than those for minimization of function values. In this work, we study gradient-norm minimization for convex functions that are $(L,\kappa)$-H\"older smooth with respect to the $\ell_p$-norms, $p \geq 1$. We develop algorithms that achieve near-optimal gradient-oracle complexity for this problem. In the smooth case, our results resolve the previously open setting $p>2$. For H\"older-smooth objectives, we close the complexity gap throughout the full $p$-range, including to the best of our knowledge, a gap in the Euclidean case. We provide two families of algorithms: the first one comes with a simple iteration and generalizes a phenomenon known as mirror duality, exploiting dual behaviours of algorithms with errors and inexact computations. The second makes use of accumulating regularizers centered at different approximate solutions, which we sequentially minimize in order to provide our near-optimal rates.
Nico Pelleriti, Maryam Shiran, David Martínez-Rubio et al.· 0 citations
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.
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· arXiv.org· 0 citations
This work presents a new lower bound of $\Omega(T^{-1.9319})$ for the last-iterate convergence rate of gradient descent with predetermined nonnegative stepsize schedules, and provides rigorous evidence that stepsize schedules alone cannot accelerate plain GD to the optimal $O(T^{-2})$ convergence rate.
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 novel convergence analysis framework for the BPGM with the Shannon entropy kernel is developed, yielding strong convergence results for a broad class of objective functions under linear constraints.
He Chen, Anthony Man-Cho So· 1 citation
We use cookies to run the site and, with your consent, for analytics and to show ads.
See our Cookie Policy.
