acceptodds
Withdrawn from ICLR 2027

Optimal Convex Optimization with Inexact Second-Order Oracles

Withdrawn from ICLR 2027, so left out of the paper lists and the map.

Abstract

In this paper, we present a novel second-order method called Accelerated Inexact Newton Extragradient (AINE) for convex optimization using -inexact Hessians. We show that AINE can find an -solution in the inexact second-order oracle (ISO) complexity of when the Hessian is -Lipschitz continuous, and a better complexity of when the third-order derivative is -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 complexity lower bounds to demonstrate that our methods are (nearly) optimal.

Primary area:
optimization
Keywords:
convex optimization, second-order optimization, inexact oracles

Reviews

Among:
Shape:
1234this paper, Bottom 27%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.00 over 3 reviews, above 27% of the others.
Reviewer_mCEWOpenReview ↗
Rating
3
Confidence
4
Informativeness
3
Presentation
2
Soundness
2
Read review
Paper summary

This paper considers the question of optimal acceleration of convex second-order methods under δ\delta-inexact Hessians. The contribution is threefold:

  1. Accelerated Inexact Newton Extragradient method, which achieves O(δT−2+L2T−7/2)O(\delta T^{-2} + L_2 T^{-7/2}) rate.
  2. Its superfast version, which achieves O~(δT−2+L3T−5)\tilde{O} (\delta T^{-2} + L_3 T^{-5}) rate for functions under higher smoothness.
  3. Lower bounds of Ω(δT−2+L2T−7/2)\Omega (\delta T^{-2} + L_2 T^{-7/2}) and Ω(δT−2+L3T−5)\Omega (\delta T^{-2} + L_3 T^{-5})
Critical strengths

The main strength of this paper is its theoretical analysis. The authors close the question of optimal acceleration of second-order methods with inexact Hessians. Moreover, they consider a higher-smoothness setting and propose a near-optimal method in this scenario. I find these theoretical results important for modern optimization.

Critical weaknesses
  1. Related works.
  • To the best of my knowledge, none of the works (Gasnikov et al., 2019; Bubeck et al., 2019; Jiang et al., 2021) consider the implementation of a near-optimal third-order method using only second-order derivatives (superfast) and achieve the O~(L3T−5)\tilde{O}(L_3 T^{-5}) rate with such an implementation (lines 41–42, 150–151). As far as I know, the first method achieving this rate is [1].
  • Similarly, for optimal tensor methods, a superfast second-order implementation was considered by Carmon et al. (2022). It is important to note that they achieved O(L3T−5){O}(L_3 T^{-5}) Hessian complexity, while O~(L3T−5)\tilde{O}(L_3 T^{-5}) gradient complexity.
  • I am not sure that footnote (c) in Table 1 is correct as written. Agafonov et al. (2024a) have Section 6 dedicated to solving the tensor subproblem for p=3p=3. The paper indeed lacks an explicit inner iteration complexity bound, but establishes relative strong convexity and smoothness of the subproblem and provides a way to solve it using BDGM. The iteration complexity follows directly from these results and Nesterov (2021a). At the same time, Section 4 of Ghadimi et al. (2017) only restates eigendecomposition, without explicit per iteration cost, yet the INCR and AINCR rows have no such footnote.
  • From my perspective, it is inaccurate to state (lines 453–454) that Proposition 5.1 extends the lower bounds of Agafonov et al. (2024b) , as they consider stochastic gradients. Indeed, in the exact-gradient setting, the authors remove the linear span assumption, but the wording should be clear and precise.
  1. Practicality.
  • The authors do not compare their method with inexact non-accelerated methods. Following the experimental results of Carmon et al. (2022), it would be interesting to see whether optimal acceleration can outperform basic inexact methods and non-optimal accelerated ones in the inexact Hessian setting.
  • At the same time, AINE requires three problem parameters: the smoothness constant, the inexactness level, and the distance to the solution, which may make it impractical. From the experimental section in the appendix, it is not clear how these parameters were chosen for different methods.
  1. I think that the writing in several places oversimplifies the arguments and may mislead readers:
  • lines 127-129. I do not see how assumption 2.3 unifies FO and SO methods by setting δ=0\delta = 0.
  • lines 214-215: the potential bound (Lemma 3.2) requires not only MS condition, but updates in lines 27, 15-16, 20-21 of Algorithm 2.
  • lines 390, 399-401. From monotone version of algorithm it follows only that xtx_t belongs to the level-set. To bound ztz_t it seems that the authors also use Lemma 3.2.
  • line 374. I am not sure that YtY_t is needed only for stability. It seems to be a crucial part of the argument needed to bound all the inner iterates.
  1. The text has minor issues, e.g.
  • line 136: “has known suboptimal”
  • line 150: “generalization”
  • line 167: missing braces
  • line 205: yy is defined as argmin over yy
  • line 22 of Algorithm 1: p∈{1,2}p \in \{1, 2\}, while algorithm requires p∈{2,3}p \in \{2, 3\}
  • lines 329: Y\mathcal{Y} is undefined. Is it compact?
  • line 357: yty_t is undefined
  • the paper uses the ICLR 2026 template instead of 2027.

[1] Kamzolov, Dmitry, and Alexander Gasnikov. "Near-optimal hyperfast second-order method for convex optimization and its sliding." arXiv preprint arXiv:2002.09050 (2020).

Questions for authors
  1. What is the main obstacle to remove additional logarithm in L3L_3 setting?
  2. Why do you compare AINE with the Optimal MS Acceleration method of Carmon et al. (2022), rather than with your own algorithm with exact Hessians and δ=0\delta=0?
  3. Is it possible to show any local convergence guarantees for your methods?
Reviewer_7UCSOpenReview ↗
Rating
1
Confidence
2
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

The paper proposes Accelerated Inexact Newton Extragradient (AINE) for unconstrained convex optimization with exact gradients and Hessian estimates satisfying a uniform spectral-norm error bound δ\delta. It adapts Monteiro-Svaiter acceleration through an epoch-based regularization schedule. Suppressing initial-distance factors, the Hessian-Lipschitz result gives O((δ/ϵ)1/2+(L2/ϵ)2/7)O\left((\delta/\epsilon)^{1/2}+(L_2/\epsilon)^{2/7}\right) oracle complexity. With Lipschitz third derivatives and a bounded initial sublevel set, a Bregman gradient subroutine gives O((δ/ϵ)1/2+(L3/ϵ)1/5)O\left((\delta/\epsilon)^{1/2}+(L_3/\epsilon)^{1/5}\right) Hessian estimates, with a logarithmic overhead in gradient evaluations. The paper also gives deterministic bundled-oracle lower bounds and reports runtime comparisons on covtype logistic regression with three Hessian batch sizes.

Critical strengths
  1. The upper bounds address a real gap in inexact second-order optimization. Under the paper's uniform Hessian-error model, the p=2p=2 result retains the optimal delta-dependent term while improving the smoothness-dependent complexity from ϵ−1/3\epsilon^{-1/3} in the closest accelerated inexact methods to ϵ−2/7\epsilon^{-2/7}. Handling the error floor in the movement analysis requires an adaptation of the existing acceleration framework.

  2. The p=3p=3 result uses approximate Hessians and exact gradients without requiring a third-derivative oracle. Section 4 accounts for the inner gradient work and states the additional bounded-sublevel-set assumption. These theoretical results deserve credit.

Critical weaknesses
  1. The provided p=3p=3 implementation does not implement the oracle analyzed in the paper. Algorithm 3 requires BDGM iterations and an MS stopping test, and Algorithm 2 uses a monotone outer step for p=3p=3. In optimizers.py, run_AINE instead calls a solver for a quadratic model with quartic regularization and includes none of these steps (lines 49-62 and 269-327). This leaves a substantial gap between the theoretical algorithm and the implementation offered to support it. The authors need to identify the code and commands used for the reported curves. Until that connection is established, the p=3p=3 curves cannot be taken as validation of the algorithm covered by Corollary 4.1.

  2. The Hessian and regularization formulas in the provided code are incorrect for the stated objective. In Run_Logistic.py (lines 90-104), the curvature weights are hh instead of h(1−h)h(1-h), and the regularization coefficient is added to every matrix entry rather than to the diagonal. For the objective and gradient implemented in that file, the Hessian should be

    ∇2f(x)=1nX⊤diag⁡ ⁣(hi(1−hi))X+λI.\nabla^2 f(x)=\frac{1}{n}X^\top\operatorname{diag}\!\bigl(h_i(1-h_i)\bigr)X+\lambda I.

    The AINE updates also use H + 2*delta instead of H+2δIH+2\delta I (optimizers.py, lines 278 and 309). These errors change the matrices used by the methods. Even the full-data branch is not an exact Hessian, although the code assigns δ=0\delta=0 in that setting. The effect on the paper's figures remains unresolved because the precise version used for those runs has not been established.

  3. The experiments are not connected clearly enough to the assumptions and parameters of the guarantees. Appendix L gives batch sizes and cites a concentration inequality, but does not explain the δ\delta values, failure probabilities, or how the guarantee is maintained over the run. The provided implementation also averages curvature matrices evaluated at different iterates; a bound for a fresh sample at the current point does not by itself control this additional error. The choices corresponding to LpL_p, the initial-distance scale, and the constants in Eq. (6) are not adequately explained either. As a result, I cannot tell whether the numerical setting satisfies the conditions used to establish the claimed rates.

  4. The comparisons do not isolate the source of the reported time advantage. Appendix L does not give the baseline configurations or tuning protocol. In the provided code, CRN and OTM use full-data curvature matrices, while AINE and AINCR use sampled matrices. That comparison can be useful, but it does not isolate the contribution of the new acceleration schedule. Including AINCR is useful, although the paper does not document how its estimator and tuning are matched to AINE. The plotting script also uses the best final objective value among the methods as the reference labeled f⋆f^\star, without an independent accuracy check. This makes the small-gap part of the comparison difficult to interpret. A clearly documented comparison using matched inexact oracles and a reliable reference objective on the same problem is needed to support the superiority claim.

Questions for authors
  1. Which code version and commands generated the curves in Appendix L? Please identify where the p=3p=3 implementation performs the BDGM iterations, MS stopping test, and monotone outer update. If the experiments use a simplified method, what ensures that it satisfies the oracle conditions used in Corollary 4.1?

  2. Can the authors explain or correct the Hessian weights and scalar matrix additions identified above? If the plotted runs used these routines, please rerun the affected comparisons with the correct curvature and diagonal regularization. Whether the reported advantage survives these corrections would materially affect my assessment.

  3. Please specify the estimator, any averaging, delta and its confidence level, the parameter choices for Eq. (6), and the baseline tuning and timing conventions. On the existing covtype problem, a comparison with matched inexact oracles and an independently checked reference objective would help determine whether the observed gains come from the proposed schedule.

Reviewer_YsHHOpenReview ↗
Rating
2
Confidence
3
Informativeness
1
Presentation
2
Soundness
3
Read review
Paper summary

This paper considers second-order methods for convex optimization with an inexact Hessian oracle, where the Hessian estimator deviates from the true Hessian by at most δ\delta in operator norm. Building on the optimal Monteiro-Svaiter acceleration framework from Carmon et al. (2022) and a variant from Adil et al. (2026), they generalize the accelerated Newton proximal extragradient (NPE) method to this inexact setting by adding ℓ2\ell_2 regularization to the subproblem. They establish a complexity of O((δ/ϵ)1/2+(L2/ϵ)2/7)O((\delta/\epsilon)^{1/2} + (L_2/\epsilon)^{2/7}) when the Hessian is Lipschitz and a complexity of O~((δ/ϵ)1/2+(L3/ϵ)1/5)\tilde{O}((\delta/\epsilon)^{1/2} + (L_3/\epsilon)^{1/5}) when the third-order derivative is Lipschitz. By using the lower bound results from Arjevani et al. (2019), they also show that the above complexity bounds are optimal up to logarithmic factors.

Critical strengths

For the considered problem setting (i.e., second-order methods with an inexact Hessian oracle), this paper improves the complexity bound of prior work and shows that it is optimal up to logarithmic factors. Specifically, when the Hessian is Lipschitz, the proposed method improves the error-free term from O((L2/ϵ)1/3)O((L_2/\epsilon)^{1/3}) to O((L2/ϵ)2/7)O((L_2/\epsilon)^{2/7}). Similarly, when the third-order derivative is Lipschitz, it improves O((L3/ϵ)1/4)O((L_3/\epsilon)^{1/4}) to O((L2/ϵ)1/5)O((L_2/\epsilon)^{1/5}) and does not require access to a third-order oracle.

Critical weaknesses

While this paper is technically solid, it appears to be heavily built on existing techniques from Carmon et al. (2022) and Adil et al. (2026) and does not seem to introduce fundamentally new algorithmic ideas. Given that the A-NPE method from Carmon et al. (2022) achieves the optimal complexity bounds with an exact Hessian oracle, it is indeed natural to consider it as the starting point in the inexact Hessian setting. Conceptually, the authors' contribution is to extend A-NPE to tolerate errors in the Hessian oracle by adding a proper regularization term in the subproblem, and the overall proof strategies closely follow those in Carmon et al. (2022) and Adil et al. (2026). In terms of the lower bound in Proposition 5.1, it also appears to be a relatively straightforward corollary from the results in Arjevani et al. (2019).

Questions for authors

In the proof sketch of Theorem 3.1, the authors highlight that a new analysis, different from Adil et al. (2026), is required in order to upper bound the cardinality of the set S↑S^{\uparrow}. Specifically, they separate S↑S^{\uparrow} into two sets depending on the increment ∣yt−zt∣\\|y_t - z_t\\| and bound their cardinalities separately. However, the formal proof given in Appendix C does not follow this strategy: instead, there the authors choose the constant in the definition of λs′\lambda_s' large enough so that ∣yt−zt∣\\|y_t - z_t\\| can be lower bounded in terms of λt′\lambda_t'. As a result, my understanding is that the proof is conceptually quite similar to the one in Adil et al. (2026). Could the authors please clarify this?

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Discussion (0)

Sign in to comment.