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.
Abstract
Recent work has shown that, for smooth convex optimization, plain gradient descent can be accelerated from its textbook convergence rate of $O(T^{-1})$ (where $T$ denotes the number of iterations) to $O\big(T^{-\log_2(1+\sqrt{2})}\big)$ using carefully designed stepsize schedules alone, without resorting to momentum or other algorithmic modifications. Despite this progress, however, little was known about lower bounds for such methods beyond the classical $\Omega(T^{-2})$ benchmark for general first-order methods. In this work, we present a new lower bound of $\Omega(T^{-1.9319})$ for the last-iterate convergence rate of gradient descent with predetermined nonnegative stepsize schedules. This result provides rigorous evidence that stepsize schedules alone cannot accelerate plain GD to the optimal $O(T^{-2})$ convergence rate. The proof was developed by GPT-5.6 Sol Pro under the authors'guidance.
For smooth nonconvex stochastic multi-objective problems, stochastic multi-gradient descent (SMG) computes an approximate steepest common descent direction of the objectives from stochastic gradients. With unbiased, variance-bounded stochastic gradients, this note establishes a new convergence rate for SMG in terms of the squared Pareto-stationarity (PS) measure. With a constant stepsize and linearly growing mini-batches, this measure at the algorithm's output is $\widetilde O(T^{-1})$ after $T$ iterations. This improves on the $\widetilde O(T^{-1/4})$ bound obtained by Chen et al. (2024) under the same setting, where $\widetilde O(\cdot)$ suppresses logarithmic factors. The key to the rate improvement is to exploit the Lipschitz continuity of the PS measure, defined by the norm of the multi-gradient descent algorithm (MGDA) direction, rather than the $(1/2)$-H\"older continuity of the MGDA direction used by Chen et al. (2024). The proof was discovered while the author was preparing homework for a graduate course: ChatGPT 5.4 Thinking Extended generated the initial proof strategy in response to an author-written homework-solution prompt; the author then verified and reorganized the resulting argument. The appendices document the prompt and summarize the student submissions.
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
Let $f:\mathbb{R}^d \rightarrow \mathbb{R}$. We consider gradient descent $x_{n+1} = x_n - \tau_n \nabla f(x_n)$, where the stepsize $\tau_n = \tau \cdot e^{rn}$ is exponentially growing (with $\tau>0$ and $0<r \ll 1$). This diverges for almost all initial values. We show that restarting the algorithm whenever $\|x_{n+1} - x_n\| \geq e^r\|x_n - x_{n-1}\|$ has good properties: it works very well in practice; we determine the limiting convergence rate in the case of convergence to a non-degenerate local minimum: it improves on classic gradient descent even though computational cost is comparable. The precise choice of $0<r \ll 1$ does not matter much and the method is virtually independent of an initial stepsize $\tau$ that is too small: while the convergence rate for gradient descent decays linearly as $\tau \rightarrow 0$, it decays as $1/\log(1/\tau)$ in this modified version; numerical examples illustrate the results.
Franccois Cl'ement, Stefan Steinerberger· 0 citations
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 stochastic gradient descent with initial regularization with initial regularization is analyzed and dimension-free upper bounds on its expected excess risk for the squared loss are derived.
Whether exact scalar feedback intrinsically incurs the additional dimension $d$ paid by known zeroth-order methods remains open even for Lipschitz convex optimization. For a universal Lipschitz scale, the value only bound $O(d^2\log(d+1)\log(1/\epsilon))$ and two-point bound $O(d\epsilon^{-2})$ yield the upper bound $\widetilde O\left(d\min\{d,\epsilon^{-2}\}\right)$. By contrast, prior lower bounds for arbitrary randomized algorithms give only $\Omega(\min\{d,\epsilon^{-2}\})$, leaving a factor $d$ unexplained. We close this gap, up to logarithmic factors, for arbitrary adaptive randomized algorithms minimizing a convex objective with a universal Lipschitz scale over the $d$-dimensional Euclidean unit ball, where each query returns only the exact scalar value. Let $T_\epsilon$ denote the minimum number of queries required to return an $\epsilon$-suboptimal point with probability at least $1/2$, uniformly over the function class. We prove that \[T_\epsilon\ge c\,\frac{d\min\{d,\epsilon^{-2}\}}{\log\!\bigl(\min\{d,\epsilon^{-2}\}\bigr)},\] for $d\ge d_0$ and $0<\epsilon\le\epsilon_0$, where $c,\epsilon_0>0$ and $d_0\in\mathbb N$ are universal constants. This gives $\Omega\left(\frac{d}{\epsilon^2\log(1/\epsilon)}\right)$ in the low-accuracy regime $\epsilon\ge d^{-1/2}$ and $\Omega\left(\frac{d^2}{\log d}\right)$ in the high-accuracy regime $\epsilon\le d^{-1/2}$ with the latter independent of $\epsilon$. These bounds match the corresponding upper bound up to logarithmic factors. To our knowledge, this is the first near-optimal lower bound for arbitrary adaptive randomized algorithms throughout both accuracy regimes of exact value Lipschitz convex optimization. The proof uses a random support function hard family and develops a posterior mean energy method for adaptive exact max observations, in place of first-order zero chain constructions and noise based transcript inequalities.
Haihan Zhang, Chenheng Zhang, Zhiquan Qi et al.· 0 citations
