This paper shows that AINE can find an $\epsilon$-solution in the inexact second-order oracle (ISO) complexity of $\delta/\epsilon)^{1/2} + (L_2/\epsilon)^{2/7} )$ when the Hessian is $L_2$-Lipschitz continuous, and establishes matching oracle complexity lower bounds for both setups.
Abstract
In this paper, we present a novel second-order method called Accelerated Inexact Newton Extragradient (AINE) for convex optimization using $\delta$-inexact Hessians. We show that AINE can find an $\epsilon$-solution in the inexact second-order oracle (ISO) complexity of $\mathcal{O}( (\delta/\epsilon)^{1/2} + (L_2/\epsilon)^{2/7} )$ when the Hessian is $L_2$-Lipschitz continuous, and a better complexity of $\mathcal{O}( (\delta/\epsilon)^{1/2} + (L_3/\epsilon)^{1/5} )$ when the third-order derivative is $L_3$-Lipschitz continuous. Notably, each iteration of our method can be conducted in the same running time as matrix multiplication up to logarithmic factors. In addition, we also establish matching oracle complexity lower bounds for both setups, demonstrating the optimality of our methods.
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 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 study second- and higher-order methods for solving smooth monotone variational inequalities (MVI). Monteiro and Svaiter (SIAM J. Optim., 2012) showed that a second-order method, NPE, converges at the rate of $\mathcal{O}(T^{-1.5})$. For convex-concave minimax optimization, a subset of MVI problems, Chen, Liu, Luo, and Zhang (COLT 2025) recently improved the complexity to $\tilde{\mathcal{O}}( T^{-1.75})$ . However, it is open whether the conjectured complexity for MVI can be improved. In this paper, by using a large-step inexact Halpern iteration, we propose a novel Halpern-NPE method that achieves an even faster rate of $\tilde{\mathcal{O}}(T^{-2})$ for solving MVIs. We also provide the $p$th-order generalization of our method. We first introduce an Anchored Tensor Method (ATM) that achieves the rate of $\mathcal{O}(T^{-(p-1)})$, and then combine it with the Halpern iteration to achieve a faster convergence rate of $\tilde{\mathcal{O}}(T^{-p})$. This improves all prior results for $p \ge 2$ and matches the classical extragradient method for $p=1$.
Lesi Chen, Xinliang Zhang, He Wang et al.· 0 citations
These results are the first global convergence results to demonstrate a provable advantage of a quasi-Newton method over the extragradient method, without querying the Jacobian of the operator.
Three inexact AL schemes are developed that preserve the standard AL subproblem structure and attain the optimal primal-dual complexity in the convex setting, improving prior AL bounds of $\mathcal O(\epsilon^{-4/3})$, $\mathcal O(\epsilon^{-7/4})$, and $\mathcal O(\epsilon^{-2})$, and removing the logarithmic factor from PAL guarantees.
Arnesh Sujanani, Saeed Ghadimi, Henry Wolkowicz· 0 citations
We study how far gradient descent (GD) can be accelerated by predetermined stepsizes in smooth convex optimization. Going beyond the classical $\Omega(n^{-2})$ first-order oracle lower bound of Nemirovsky and Yudin (1983), we prove an $\Omega(n^{-1.6342})$ non-anytime lower bound and an $\Omega(n^{-1.2408})$ anytime lower bound. These improve the recent $\Omega(n^{-1.932})$ non-anytime lower bound of Ma and Chen (2026) and the $\Omega(n^{-4/3})$ anytime lower bound of Tsai et al. (2026), respectively. Both results continue to hold when the stepsizes may be negative. Our anytime lower bound also shows that the $O(n^{-\log_2(1+\sqrt{2})})$ rate of non-anytime silver schedules (Altschuler and Parrilo, 2025; Grimmer et al., 2025) is unattainable in the anytime setting. This establishes a strict separation between the two settings.
Yutian Ye, Kai-Zhao Liu· 1 citation
We use cookies to run the site and, with your consent, for analytics and to show ads.
See our Cookie Policy.
