Predetermined stepsize schedules featuring carefully chosen long steps have recently been shown to accelerate gradient descent (GD) on smooth convex functions. A prominent class of such schedules is built through recursive composition. In this paper, we characterize the convergence of these optimized recursive schedules, revealing a nonconstant log-periodic modulation across prescribed horizons. Specifically, we prove that for every $N \geq 1$, the optimized ConPP/OBS-S schedules satisfy $$f(x_{N-1})-f_\ast \le \frac{1}{2N^p\Phi(\log_2N)-1} \frac{L}{2}\|x_0-x_\ast\|^2, \qquad p=\log_2(1+\sqrt2), $$ where $\Phi$ is a positive, Lipschitz, nonconstant $1$-periodic function. We derive this by proving that balanced splitting is optimal at every horizon for these constructions, resolving a conjecture of Zhang and Jiang. Furthermore, for their asymmetric counterparts (ConPD/OBS-F schedules), we show that although optimal splits are not necessarily balanced, the same Silver exponent asymptotically persists alongside a distinct log-periodic modulation.
We study the time-uniform convergence of the raw iterate of standard stochastic gradient descent (SGD) for unconstrained smooth convex objectives. We prove that, under standard noise assumptions, the time-uniform convergence rate gets arbitrarily close to $\sqrt{\log n / n}$ but never reaches it. More specifically, we...
The last-epoch rate is proved, matching the known quadratic lower bound in its $(n,K)$-dependence, and it is shown that the $\beta_\star^2/K^2$ splitting term is unavoidable and obtain a matching lower bound up to logarithms in the stated constant-stepsize regime.
A tight lower bound is proved of $\Omega(\lambda^{1/2}\epsilon^{-7/2})$ for finding points satisfying the recently proposed relaxed notion of $(\lambda,\epsilon)$-stationarity, which allows combining further-away gradients.
How far can stochastic gradient descent ascent (SGDA) go by tuning its timescale ratio and step sizes in nonconvex min-max games? We answer this question for nonconvex-P{\L} (NC-P{\L}) games by establishing the first tight complexity of two-timescale SGDA with a fixed timescale ratio and non-increasing step sizes. For...
We present new algorithms for stochastic optimization problems in which the objective is neither smooth nor convex, subject to a convex constraint set. Our algorithms return a $(\delta,\varepsilon)$-Goldstein stationary point, as recently defined for constrained problems by Liu et al. (2024), with improved complexities...
Fix a target accuracy $\varepsilon$, a gradient-noise level $s$, and a horizon $N$. We wish to design algorithms which minimize the probability of observing a suboptimality gap which exceeds the target accuracy, i.e., $\mathcal{E}_N = -\log \sup_{f,P} \mathbb{P}_P(f(x_A) - f_\star \ge \varepsilon)$, with the noise law...
B. V. Van Parys· 0 citations
We use cookies to run the site and, with your consent, for analytics and to show ads.
See our Cookie Policy.
