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
arXiv:2609. 30212v1 Announce Type: cross Abstract: We study the deterministic oracle complexity of finding approximate solutions to composite monotone inclusion problems, formed by the sum of a smooth single-valued monotone operator and a maximally monotone set-valued operator, under the tangent-residual criterion.
By Ruichen Jiang, TaeHo Yoon
The paper introduces the Anchored Extra-Proximal (AEP) framework for solving composite monotone inclusion problems, combining anchored extrapolation with an inexact anchored proximal update. By replacing the operator in the implicit update with its Taylor approximation and using a bisection line search, the authors derive a pth-order method that achieves a tangent-residual error ε in “~O(ε^{-2/(3p-1)})” oracle calls for every p ≥ 2. This complexity matches a proven lower bound, establishing the method as optimally efficient for deterministic algorithms in the pth-order oracle model.
arXiv:2611. 05527v1 Announce Type: cross Abstract: In this paper, we provide tight lower bounds for minimizing high-order H\"older-smooth and uniformly convex functions when their orders match.
By Cedar Site Bai
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: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:2609. 21880v1 Announce Type: cross Abstract: We study the optimization of convex objectives with $(L,\kappa-1)$-H\"older-continuous gradients in $\ell_q$ over $R B_p^d$, $1<\kappa\le 2$.
By David Mart\'inez-Rubio, Brian Bullins, Crist\'obal Guzm\'an, Mathieu Molina
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:2511. 22331v2 Announce Type: replace-cross Abstract: Bilevel optimization minimizes an objective function, defined by an upper-level problem whose feasible region is the solution of a lower-level problem.
By Lesi 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:2610. 42040v1 Announce Type: cross Abstract: We study the stochastic second-order oracle complexity of solving smooth convex finite-sum optimization with $n$ components.
By Xinliang Zhang, Lesi Chen, Zonghan Li, Jingzhao Zhang
arXiv:2608. 25182v1 Announce Type: cross Abstract: In this paper, we study alternating regret in online convex optimization (OCO), motivated by the success of alternating learning dynamics in two-player games.
By Mengxiao Zhang