arXiv:2610. 03222v1 Announce Type: cross Abstract: This paper studies the complexity of convex optimization using lazy second-order oracles (Doikov, Chayti, and Jaggi, ICML 2023), where an algorithm queries gradients every iteration and Hessians once per $m$ iterations.
By Xinliang Zhang, Lesi Chen, Chengchang Liu, Jingzhao Zhang
arXiv:2608. 10418v1 Announce Type: cross 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.
By Jianhao Ma, Yuxin Chen
arXiv:2611. 04171v2 Announce Type: replace-cross Abstract: We study the minimization of the average of $n$ convex $(L_0,L_1)$-smooth functions: the Hessian norm of each function is bounded by an affine function of its gradient norm.
By Mikhail Rudomanov, Ivan Fomin, Alexander V. Gasnikov, Fedor S. Stonyakin
arXiv:2502.21099v3 Announce Type: replace-cross
Abstract: This paper proposes {\sf AEPG-SPIDER}, an Adaptive Extrapolated Proximal Gradient (AEPG) method with variance reduction for minimizing compos...
By Ganzhao Yuan
arXiv:2606. 05438v1 Announce Type: new Abstract: We study the deterministic first-order oracle complexity of finding \(\epsilon\)-stationary points in smooth nonconvex optimization when the objective satisfies higher-order smoothness assumptions.
By Dongruo Zhou
arXiv:2608. 08463v1 Announce Type: cross Abstract: We study second- and higher-order methods for solving smooth monotone variational inequalities (MVI).
By Lesi Chen, Xinliang Zhang, Hengyu Wang, Chengchang Liu, Yongchao Chen, Jingzhao Zhang
The paper investigates the limits of accelerating gradient descent (GD) using predetermined step sizes in smooth convex optimization. It establishes new lower bounds: an ≥·n−1.6342 non‑anytime bound and an ≥·n−1.2408 anytime bound, surpassing previous results. These findings also demonstrate a strict separation between convergence exponents achievable in non‑anytime versus anytime settings.
By Yuhan Ye, Kaizhao Liu
arXiv:2609. 23837v1 Announce Type: cross Abstract: We study the complexity of finding $(\delta,\epsilon)$-Goldstein stationary points of nonsmooth nonconvex Lipschitz functions.
By Guy Kornowski
arXiv:2511. 19656v3 Announce Type: replace Abstract: Although upper bound guarantees for bilevel optimization have been widely studied, progress on lower bounds has been limited due to the complexity of the bilevel structure.
By Kaiyi Ji
arXiv:2610.07814v1 Announce Type: cross
Abstract: 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 ques...
By Junsoo Ha
arXiv:2609.36033v1 Announce Type: cross
Abstract: Among distinct optimal acceleration mechanisms for deterministic monotone root-finding problems and fixed-point problems, dual-anchoring has recently...
By TaeHo Yoon, Nicolas Loizou
arXiv:2609. 23557v1 Announce Type: cross Abstract: We study second- and higher-order methods for solving smooth monotone variational inequalities (MVI).
By Xinliang Zhang, Lesi Chen, Linxuan Pan, Chengchang Liu, Junchi Yang, Jingzhao Zhang