Pith. sign in

REVIEW 4 major objections 5 minor 64 references

Performance Estimation of second-order optimization methods on classes of univariate functions

T0 review · 4 major / 5 minor · reviewed 2026-08-06 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗

Pith's one-line read The paper derives exact univariate interpolation conditions for second-order function classes and uses them to sharpen worst-case convergence guarantees, improving Cubic Regularized Newton's descent bound by a factor of five.

desk verdict First exact univariate second-order interpolation conditions plus a promising CNM speedup, but the main descent lemma rests on a misprinted Corollary 5 and needs a repair before the results hold as stated. read the letter →

arxiv 2506.22764 v1 pith:723H3CLL submitted 2025-06-28 math.OC

Anne Rubbens , Nizar Bousselmi , Julien M. Hendrickx , François Glineur This is my paper · ORCID
classification math.OC MSC 68Q2590C5390C2526A06
keywords PerformanceEstimationinterpolationconditionssecond-orderoptimizationCubicRegularizedNewtonNewton'smethodself-concordantfunctionsHessianLipschitzworst-casecomplexity
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

Second-order methods such as Newton's method and its cubic-regularized variants are used throughout optimization, but their worst-case performance is rarely known exactly. This paper establishes exact interpolation conditions for univariate functions with Lipschitz Hessian and for generalized, quasi-, and standard self-concordant functions, then feeds these conditions into the Performance Estimation technique to compute tight worst-case guarantees. The headline result is an improved descent lemma for Cubic Regularized Newton: on univariate functions with M-Lipschitz Hessian, each step decreases the function value by at least $(5M/12)(|f'(x_{k+1})|/M)^{3/2}$, five times the classical constant, which translates into a $5^{2/3}$-fold (about 2.9) improvement in the sublinear gradient convergence rate. Because univariate examples are legitimate lower-bound instances for multivariate problems, these bounds also show that certain existing multivariate rates are unimprovable, and they permit fair comparisons among Newton variants on the same performance measures.

What carries the argument

The central machinery is a lifting theorem: given exact interpolation conditions for a univariate class $F$, the paper derives exact interpolation conditions for the class of functions whose derivative lies in $F$, provided $F$ has extremal interpolating envelopes and the lifted class is connectable. For Hessian-Lipschitz functions, the lifted conditions come from integrating the pointwise minimal and maximal M-smooth interpolants between two data points; this produces Theorem 5, a complete set of inequalities on pairs $(x_i, f_i, g_i, h_i)$. Corollary 5 extracts from those conditions a refined cubic upper bound on the function increase, and Theorem 7 plugs that refined bound into the Cubic Regularized Newton step to obtain the factor-5 descent lemma.

What would settle it

Check the refined cubic bound (45) at $M=1$ on $f(t)=t^3/6 - t^2/2$ with $x=0$ and $y=1$: the left side is $1/6$ and the right side is approximately $1/6 - (1/3)(1/2)^{3/2}$, so the printed inequality fails. Whether the corrected variant used at step (51), with the absolute value divided by $M$ inside the $3/2$ power, holds for all functions in the Hessian-Lipschitz class decides Theorem 7.

Watch

Extended reading notes

Core claim

On its own terms, the paper's contribution is a systematic way to turn a univariate function class into a finite list of inequalities that a dataset of points, gradients, and Hessians must satisfy to be interpolable by a function in the class. With those inequalities, worst-case optimization performance becomes a finite non-convex optimization problem that can be solved numerically and sometimes analytically. The strongest specific discovery is Theorem 7: for univariate functions with M-Lipschitz Hessian, every Cubic Regularized Newton iterate satisfies the descent inequality $f(x_k)-f(x_{k+1}) \geq (5M/12)(|f'(x_{k+1})|/M)^{3/2}$, improving the classical cubic-regularization descent lemma by a factor of 5. Telescoping this inequality yields the best-iterate gradient bound $4M^{1/3}/5^{2/3}(3(f(x_0)-f_*)/(2N))^{2/3}$. The paper also proves that some established multivariate bounds, including Newton's and gradient-method local convergence on Hessian-Lipschitz functions and damped Newton on self-concordant functions, are tight by exhibiting univariate functions that attain them.

Load-bearing premise

The improved factor-5 descent lemma rests on the refined cubic bound derived from the new Hessian-Lipschitz interpolation conditions; if that refined bound is not valid in the form used at step (51) of the proof, the factor-5 improvement collapses.

Editorial extensions

If this is right

  • Cubic Regularized Newton's best-iterate gradient convergence on univariate Hessian-Lipschitz functions improves from $4M^{1/3}(3(f_0-f_*)/(2N))^{2/3}$ to $4M^{1/3}/5^{2/3}(3(f_0-f_*)/(2N))^{2/3}$, and the same $5^{2/3}$ factor applies to the convex and strongly convex variants.
  • The univariate worst-case instances found by the analysis serve as multivariate lower bounds, so the improved factor-5 descent is not an artifact of dimension one: no multivariate method can beat this decrease on those instances.
  • Established bounds are provably tight: Newton's method's quadratic local convergence on Hessian-Lipschitz functions is attained by $-M|x|^3/6 + \mu x^2/2$, and the analogous gradient-method linear rate is attained by two cubic-by-parts functions.
  • For Gradient Regularized Newton on quasi-self-concordant functions, the univariate one-step worst-case bound becomes $e^{r/(r+1)}(r-1)+1$ where $r$ is the normalized gradient-to-Hessian ratio before the step, and for damped Newton on self-concordant functions the single-step bound is shown to remain tight for any number of iterations.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

  • If the corrected cubic bound behind Theorem 7 holds, the same $5M/12$ factor is a natural target for a multivariate proof; the authors conjecture it, and the numerical tests reported in the paper on separable cubic-plus-quadratic functions support that conjecture.
  • The lifting technique is not tied to second derivatives: the same extremal-interpolant construction could produce exact worst-case guarantees for third-order or tensor methods, or for zeroth-order methods, in one dimension.
  • The appearance of simple cubic-by-parts extremal functions across several analyses suggests that the extremal instances for second-order univariate methods form a small parametric family; testing whether that family remains extremal under perturbations or adaptive step sizes is a concrete next step.
  • Because the paper's multivariate lower bounds come from univariate instances, any future multivariate upper bound that improves on them would have to avoid matching the univariate extremal examples, effectively delimiting how much dimension can help.
Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Referee Report

4 major / 5 minor

Summary. The paper develops a method for deriving exact interpolation conditions for univariate function classes with second-order oracle information, covering Hessian-Lipschitz functions, generalized self-concordant functions, self-concordant functions, and quasi-self-concordant functions. These conditions are then fed into Performance Estimation Problems (PEPs), solved both analytically and numerically, to analyze several second-order methods: Cubic Regularized Newton, Gradient Regularized Newton, Newton's method, and damped Newton variants. The advertised contributions include an improved univariate descent lemma for Cubic Regularized Newton (raising the constant from M/12 to 5M/12), improved or tightened convergence guarantees for several methods, new worst-case functions, and a numerical comparison framework. The main machinery is Theorem 1 (lifting interpolation conditions to derivative classes), Theorems 3-5 (explicit interpolation conditions), and a series of applications in Section 5.

Significance. If the results are correct, this would be a valuable step for second-order performance estimation: exact univariate interpolation conditions are obtained for several nontrivial classes, the proofs in the appendices are detailed, and the PEP-based analysis produces concrete worst-case functions and comparisons. The paper also ships reproducible code on GitHub, and several claimed worst-case functions are simple and checkable. However, the central advertised improvement for Cubic Regularized Newton is not established as written: Corollary 5 is false, and the proof of Theorem 7 relies on an unstated corrected variant of that corollary. A plausible repair exists from the bounds already derived in Appendix D, but the claim must be re-derived and restated correctly before the paper can be accepted.

major comments (4)
  1. [§4.4, Corollary 5, Eq. (45)] The printed inequality (45) is false as stated. For M=1, take f(x)=x^2/2, which belongs to H_1, and x=0, y=1. The condition |f''(x)-f''(y)| = 0 ≠ 1 = M|y-x| is satisfied. The left-hand side is f(1)-f(0)-f'(0)-f''(0)/2 = 1/2 - 0 - 0 - 1/2 = 0, while the right-hand side is 1/6 - (1/3)(|1-0-1-1|/1)^{3/2} = 1/6 - 1/3 = -1/6. Hence 0 ≤ -1/6 is violated. The error appears to come from the proof's AM-GM step: the quantity that arises from the upper bound in Proposition 5, Eq. (115), involves M/2 inside the absolute value, not M|y-x|(y-x) as printed.
  2. [§5.1, proof of Theorem 7, Eq. (49)] The proof of the improved descent lemma applies Corollary 5 with M/2 inside the absolute value: the expression simplified by Eq. (51) is f'(x_{k+1}) - f'(x_k) - f''(x_k)(x_{k+1}-x_k) - (M/2)(x_{k+1}-x_k)|x_{k+1}-x_k|, whereas Corollary 5 as stated has M|y-x|(y-x). The corrected M/2 variant is not stated in Corollary 5 and is not proved there. Since inequality (49) and the subsequent rate (50) depend exactly on this step, the factor-5 improvement is not established as written. The ingredients for a repair appear to be present in Proposition 5 and Eq. (115), but the corrected corollary and its proof must be supplied before Theorem 7 can be accepted.
  3. [§5.4.2, Theorem 16] The multi-iteration tightness assertion in Theorem 16 is not supported by the proof. The proof says the bound follows directly from Theorem 14 and that the attaining function is (82), but Theorem 14 is a single-iteration statement for Newton's method, not for damped Newton, and (82) is the single-iteration worst-case function from Theorem 15. Iterating a single-iteration bound gives the upper bound in (83), but it does not show that a single function attains equality at all N iterations simultaneously. The claim that the bound is tight for multiple iterations needs a dedicated proof, or should be explicitly downgraded to a numerical observation.
  4. [§5, numerical PEPs] Several numerical claims are presented as exact worst-case guarantees or as improvements over existing bounds, yet the paper does not state that Gurobi's non-convex solver was run in a mode that certifies global optimality for every reported instance. This matters because the tightness interpretation of the PEP results requires a global optimum, while a merely feasible solution would only provide a lower bound on the worst case. Please clarify, for each numerical figure used as a guarantee, whether global optimality was certified, and, if not, mark the corresponding results as lower bounds or heuristics rather than exact guarantees.
minor comments (5)
  1. [Title page and Abstract] The author string contains a typographical artifact: 'F ran¸cois Glineur' should read 'François Glineur'.
  2. [§4.4, Corollary 5] The notation in (45) is hard to parse: the exponent should be written as ((|...|)/M)^{3/2} rather than as a nested radical over the fraction.
  3. [§5.4.2, Theorem 16] The statement of Theorem 16 uses γ in the right-hand side of (83) but γ_k in the hypothesis; please make the dependence on k consistent and explicit.
  4. [§5.1, Remark 14] Remark 14 states improvements to results in [39, Theorems 6.1 and 6.2] based on Theorem 7; this remark will only become valid once the corrected version of Theorem 7 is established.
  5. [§5.2 and Figure 7] Figure 7 is said to compare the bound (59) with PEP results, but the caption does not report which PEP formulation or solver settings were used; adding this to the caption or the reproducibility notes would help.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity: the analytic claims are derived from exact interpolation conditions that characterize the input function classes, and self-citations concern only the generic PEP methodology.

full rationale

The paper's core derivation chain is self-contained with respect to function-class definitions. The HM interpolation conditions (Theorem 5) are obtained by integrating extremal interpolants of the class of M-Lipschitz gradients, i.e. from the defining inequality |h_i - h_j| <= M|x_i - x_j| plus the consistency equations for gradient and function values; no performance quantity is used to define the class and no parameter is fitted to data. Corollary 5 and Theorem 7 then follow algebraically from those exact conditions, and Appendix F verifies the resulting descent constant on an explicit cubic-by-parts function. The only self-citations (e.g. [21,49] for PEP) are references to a general computational methodology and to the existing M-smooth interpolation result; they are not used to justify the new univariate second-order interpolation conditions or the descent bounds. A separate correctness issue does exist: inequality (45) in Corollary 5 is false as printed, and the proof of Theorem 7 uses a variant with M/2 inside the absolute value that is not the stated corollary; however, this is a mathematical proof gap rather than circular reasoning, because the claimed descent lemma is not assumed in the derivation of the interpolation conditions. The reader's suggested repair using Proposition 5 (115) is consistent with this assessment. Hence no circular step can be exhibited.

Assumptions & free parameters 0 free parameters · 3 assumptions · 0 invented entities

The analytical core is a self-contained derivation from function class definitions, requiring only standard analysis tools. The numerical contributions assume global optimality of non-convex solves through Gurobi, which is not certified. The paper's classification of specific function classes under the generalized smoothness umbrella relies on definitions from the cited literature.

assumptions (3)
  • domain assumption The target classes (Hessian Lipschitz, self-concordant, quasi-self-concordant) are subsumed by the generalized Lipschitz classes FM,alpha,(+) for specific alpha values, following the definitions in [46].
    The paper cites [46] for the class definitions; the correspondence Table 3 is assumed from prior literature.
  • ad hoc to paper For all numerical PEPs in Section 5, Gurobi's non-convex solver (version 11) is assumed to return a global optimum of the non-convex QCQP or general-constraint problems.
    The paper states it uses Gurobi 11's non-convex solver but gives no optimality certificates; the reported worst-case figures are exact only under global optimality.
  • standard math The real line's connectivity and the fundamental theorem of calculus apply to the extended function classes (e.g., bar-C^m).
    Used in Lemma 1 to equate interpolation without function values to interpolation with function values of the derivative class; the paper extends derivatives to +infinity on the effective domain.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Performance Estimation of second-order optimization methods on classes of univariate functions." pith.science (2026). https://pith.science/paper/723H3CLL

@misc{pith2026250622764,
  author       = {Pith},
  title        = {Pith review of: Performance Estimation of second-order optimization methods on classes of univariate functions},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/723H3CLL}},
  note         = {Machine review of arXiv:2506.22764}
}
read the original abstract

We develop a principled approach to obtain exact computer-aided worst-case guarantees on the performance of second-order optimization methods on classes of univariate functions. We first present a generic technique to derive interpolation conditions for a wide range of univariate functions, and use it to obtain such conditions for generalized self-concordant functions (including self-concordant and quasi-self-concordant functions) and functions with Lipschitz Hessian (both convex and non-convex). We then exploit these conditions within the Performance Estimation framework to tightly analyze the convergence of second-order methods on univariate functions, including (Cubic Regularized) Newton's method and several of its variants. Thereby, we improve on existing convergence rates, exhibit univariate lower bounds (that thus hold in the multivariate case), and analyze the performance of these methods with respect to the same criteria.

Figures

Figures reproduced from arXiv: 2506.22764 by the authors.

Figure 1
Figure 1. Given (x0, g0, h0) = (0, 1, 1), M = 1 and x1 = 1 2 , the plot shows the admis￾sible region for (g1, h1) such that {(xi, gi, hi)}i=0,1 satisfies (i) classical conditions defining quasi-self-concordant functions, i.e., (37), (black curves), or (ii) inter￾polation conditions for this function class, i.e., Corollary 4 (red curves). It also shows the points (g1, h1) corresponding to the worst-case of a variant of Newton’… view at source ↗
Figure 2
Figure 2. Illustration of the method to obtain interpolation conditions ensuring [PITH_FULL_IMAGE:figures/full_fig_p010_2.png] view at source ↗
Figure 3
Figure 3. Given α ≥ 0, M = 1, and S = {(xi, fi)}i=1,2, extremal interpolants fmin, fmax (Definition 3) of S, depending on α. The considered sets are either S˜1 = {(xi, ˜fi)}i=1,2 = {(0, 1 2 ),(1, 3 4 )}, or S˜2 = {(xi, ˜fi)}i=1,2 = {(0, 1 2 ),(1, 1 4 )} [PITH_FULL_IMAGE:figures/full_fig_p023_3.png] view at source ↗
Figures from the paper (12 more)
Figure 4
Figure 4. Figure 4: Derivation of interpolation conditions ensuring [PITH_FULL_IMAGE:figures/full_fig_p028_4.png]
Figure 5
Figure 5. Figure 5: Worst-case performance of the best mink=1,...,N |f ′ (xk)| and last |f ′ (xN )| iterates of the Cubic Newton method on Hessian M-Lipschitz functions for varying number of iterations N and M = f0 − fN = 1. of a performance guarantee. On one hand, we must use the correct…
Figure 6
Figure 6. Figure 6: Worst-case performance |f ′ (xk+1)| of the Cubic Regularized Newton method for different step size α on Hessian M-Lipschitz functions with fk−fk+1 = 1 and different values of M. it can be shown that this worst-case scales with (fk − fk+1) 2 3 . Further analysis of such…
Figure 7
Figure 7. Figure 7: compares the worst-case local convergence of GNM2 on µ-strongly convex Hessian M-Lipschitz univariate functions from (59) (red dots) and from PEP (blue dots) for varying number of iterations N, initial gradient |f ′ (x0)| ≤ R = µ 2 4M , µ = 0.1 and M = 1 [PITH_FULL_IM…
Figure 8
Figure 8. Figure 8: shows the iterations of the Gradient method on functions f and g. Interestingly, it exhibits the same kind of behavior as for smooth convex functions, i.e., short steps slowly converge whereas long steps overshoot [49, [PITH_FULL_IMAGE:figures/full_fig_p037_8.png]
Figure 9
Figure 9. Figure 9: Worst-case performance by PEP (blue dots) of [PITH_FULL_IMAGE:figures/full_fig_p038_9.png]
Figure 10
Figure 10. Figure 10: Worst-case performance by PEP (blue dots) of [PITH_FULL_IMAGE:figures/full_fig_p039_10.png]
Figure 11
Figure 11. Figure 11: Worst-case performance λ(x2) for varying initial λ(x0) of two iterations of Newton method (black dots) compared to bounds [37, Theorem 5.2.2.1] (dashed lines), [29, Equation (11)] (solid lines), and the PEP results (dots). better than predicted by previous theoretical…
Figure 12
Figure 12. Figure 12: compares the numerical and analytical solution of PEP (blue dots and curve) with [17, Equation (49)] (red curve) on the worst-case performance of one iteration of (GNM1) on 1-quasi-self-concordant functions [PITH_FULL_IMAGE:figures/full_fig_p044_12.png]
Figure 13
Figure 13. Figure 13: Worst-case performance of GNM1 for varying number of iterations N on 1-quasi-self-concordant functions with η(x0) = M |f ′ (x0)| f′′(x0) ≤ 0.4. Lemma 10 ([17], Equation (53)) A single iteration of Newton method x+ = x− f ′ (x) f′′(x) on M-quasi-self-concordant µ-stron…
Figure 14
Figure 14. Figure 14: Worst-case performance |f ′ (xk+1)| of different second-order methods on µ-strongly convex Hessian M-Lipschitz functions for varying µ and initial gradient |f ′ (xk)| = 1 and M = 1. We observe that CNM, GNM1, GNM2, and ADNM share similar behavior with CNM being faster…
Figure 15
Figure 15. Figure 15: Illustration of the proof of Proposition [PITH_FULL_IMAGE:figures/full_fig_p050_15.png]

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

64 extracted references · 59 canonical work pages

  1. [1]

    Journal of Optimization Theory and Applications 202(1), 475–496 (2024)

    Abbaszadehpeivasti, H., de Klerk, E., Zamani, M.: On the rate of convergence of the difference-of-convex algorithm (DCA). Journal of Optimization Theory and Applications 202(1), 475–496 (2024)

    work page 2024

  2. [2]

    Proceedings of the London Mathematical Society 114(1), 133–158 (2017)

    Azagra, D., Mudarra, C.: Whitney extension theorems for convex functions of the classes C1 and C1,ω. Proceedings of the London Mathematical Society 114(1), 133–158 (2017)

    work page 2017

  3. [3]

    Calculus of Variations and Partial Differential Equations 58(84) (2019)

    Azagra, D., Mudarra, C.: Smooth convex extensions of convex functions. Calculus of Variations and Partial Differential Equations 58(84) (2019)

    work page 2019

  4. [4]

    Electronic Journal of Statistics 4, 384 – 414 (2010)

    Bach, F.: Self-concordant analysis for logistic regression. Electronic Journal of Statistics 4, 384 – 414 (2010)

    work page 2010

  5. [5]

    In: Conference on learning theory, pp

    Barr´ e, M., Taylor, A., d’Aspremont, A.: Complexity guarantees for polyak steps with momentum. In: Conference on learning theory, pp. 452–478. PMLR (2020)

    work page 2020

  6. [6]

    SIAM Journal on Optimization 34(3), 3033–3063 (2024)

    Bousselmi, N., Hendrickx, J.M., Glineur, F.: Interpolation conditions for linear operators and applications to performance estimation problems. SIAM Journal on Optimization 34(3), 3033–3063 (2024)

    work page 2024

  7. [7]

    Siam journal on optimization 20(6), 2833–2852 (2010)

    Cartis, C., Gould, N.I., Toint, P.L.: On the complexity of steepest descent, Newton’s and regularized Newton’s methods for nonconvex unconstrained optimization problems. Siam journal on optimization 20(6), 2833–2852 (2010)

    work page 2010

  8. [8]

    Part I: motivation, convergence and numerical results

    Cartis, C., Gould, N.I., Toint, P.L.: Adaptive cubic regularisation methods for uncon- strained optimization. Part I: motivation, convergence and numerical results. Mathemat- ical Programming 127(2), 245–295 (2011)

    work page 2011

Show all 64 references
  1. [9]

    arXiv preprint arXiv:2302.11962 (2023)

    Chayti, E.M., Doikov, N., Jaggi, M.: Unified convergence theory of stochastic and variance- reduced cubic Newton methods. arXiv preprint arXiv:2302.11962 (2023)

    2023

  2. [10]

    IEEE Transactions on Automatic Control 68(12), 7136–7150 (2023)

    Colla, S., Hendrickx, J.M.: Automatic performance estimation for decentralized optimiza- tion. IEEE Transactions on Automatic Control 68(12), 7136–7150 (2023)

    2023

  3. [11]

    SIAM (2000) 48 A

    Conn, A.R., Gould, N.I., Toint, P.L.: Trust region methods. SIAM (2000) 48 A. Rubbens, N. Bousselmi, J. M. Hendrickx, F. Glineur

    2000

  4. [12]

    Mathematical Program- ming (2024)

    Das Gupta, S., Freund, R.M., Sun, X.A., Taylor, A.: Nonlinear conjugate gradient meth- ods: worst-case convergence rates via computer-assisted analyses. Mathematical Program- ming (2024)

    2024

  5. [13]

    Mathematical Programming 204(1), 567–639 (2024)

    Das Gupta, S., Van Parys, B.P., Ryu, E.K.: Branch-and-bound performance estimation programming: A unified methodology for constructing optimal optimization methods. Mathematical Programming 204(1), 567–639 (2024)

    2024

  6. [14]

    Optimization Letters 11, 1185–1199 (2017)

    De Klerk, E., Glineur, F., Taylor, A.B.: On the worst-case complexity of the gradient method with exact line search for smooth strongly convex functions. Optimization Letters 11, 1185–1199 (2017)

    2017

  7. [15]

    SIAM Journal on Optimization 30(3), 2053–2082 (2020)

    De Klerk, E., Glineur, F., Taylor, A.B.: Worst-case convergence analysis of inexact gradient and Newton methods through semidefinite programming performance estimation. SIAM Journal on Optimization 30(3), 2053–2082 (2020)

    2020

  8. [16]

    Doikov, N.: New second-order and tensor methods in convex optimization. Ph.D. thesis, Universit´ e catholique de Louvain, Louvain-la-Neuve, Belgium (2021)

    2021

  9. [17]

    arXiv preprint arXiv:2308.14742 (2023)

    Doikov, N.: Minimizing quasi-self-concordant functions by gradient regularization of New- ton method. arXiv preprint arXiv:2308.14742 (2023)

    2023 arXiv

  10. [18]

    SIAM Journal on Optimization 34(1), 27–56 (2024)

    Doikov, N., Mishchenko, K., Nesterov, Y.: Super-universal regularized Newton method. SIAM Journal on Optimization 34(1), 27–56 (2024)

    2024

  11. [19]

    Mathematical Programming 194, 41–83 (2022)

    Dragomir, R.A., Taylor, A.B., d’Aspremont, A., Bolte, J.: Optimal complexity and certi- fication of Bregman first-order methods. Mathematical Programming 194, 41–83 (2022)

    2022

  12. [20]

    In: International Conference on Machine Learning, pp

    Drori, Y., Shamir, O.: The complexity of finding stationary points with stochastic gradient descent. In: International Conference on Machine Learning, pp. 2658–2667. PMLR (2020)

    2020

  13. [21]

    Mathematical Programming 145(1), 451–482 (2014)

    Drori, Y., Teboulle, M.: Performance of first-order methods for smooth convex minimiza- tion: a novel approach. Mathematical Programming 145(1), 451–482 (2014)

    2014

  14. [22]

    Mathematical Programming 194(1-2), 975–1016 (2022)

    Gannot, O.: A frequency-domain analysis of inexact gradient methods. Mathematical Programming 194(1-2), 975–1016 (2022)

    2022

  15. [23]

    Mathematical Programming Computation 16(3), 337–367 (2024)

    Goujaud, B., Moucer, C., Glineur, F., Hendrickx, J.M., Taylor, A.B., Dieuleveut, A.: Pepit: computer-assisted worst-case analyses of first-order optimization methods in Python. Mathematical Programming Computation 16(3), 337–367 (2024)

    2024

  16. [24]

    preprint arXiv:2205.15033 (2022)

    Goujaud, B., Taylor, A., Dieuleveut, A.: Optimal first-order methods for convex functions with a quadratic upper bound. preprint arXiv:2205.15033 (2022)

    2022 arXiv

  17. [25]

    Geometric and Functional Analysis 19(4), 1101–1118 (2009)

    Gruyer, E.L.: Minimal Lipschitz extensions to differentiable functions defined on a Hilbert space. Geometric and Functional Analysis 19(4), 1101–1118 (2009)

    2009

  18. [26]

    Advances in Neural Information Processing Systems (NeurIPS) (2022)

    Guille-Escuret, C., Ibrahim, A., Goujaud, B., Mitliagkas, I.: Gradient descent is optimal under lower restricted secant inequality and upper error bound. Advances in Neural Information Processing Systems (NeurIPS) (2022)

    2022

  19. [27]

    URL https: //www.gurobi.com

    Gurobi Optimization, LLC: Gurobi Optimizer Reference Manual (2024). URL https: //www.gurobi.com

    2024

  20. [28]

    Advances in Neural Information Processing Systems 35, 25320–25334 (2022)

    Hanzely, S., Kamzolov, D., Pasechnyuk, D., Gasnikov, A., Richt´ arik, P., Tak´ ac, M.: A damped Newton method achieves global O(1/k2) and local quadratic convergence rate. Advances in Neural Information Processing Systems 35, 25320–25334 (2022)

    2022

  21. [29]

    Mathematical Methods of Operations Research 94(2), 253–279 (2021)

    Hildebrand, R.: Optimal step length for the Newton method: case of self-concordant func- tions. Mathematical Methods of Operations Research 94(2), 253–279 (2021)

    2021

  22. [30]

    Optimization Letters 18(3), 847–854 (2024)

    Ivanova, A., Hildebrand, R.: Optimal step length for the maximal decrease of a self- concordant function by the Newton method. Optimization Letters 18(3), 847–854 (2024)

    2024

  23. [31]

    In: 2023 European Control Conference (ECC)

    Kamri, Y., Hendrickx, J.M., Glineur, F.: On the worst-case analysis of cyclic coordinate- wise algorithms on smooth convex functions. In: 2023 European Control Conference (ECC). IEEE (2023)

    2023

  24. [32]

    Funda- menta Mathematicae 22(1), 77–108 (1934)

    Kirszbraun, M.: ¨Uber die zusammenziehende und Lipschitzsche transformationen. Funda- menta Mathematicae 22(1), 77–108 (1934)

    1934

  25. [33]

    SIAM Journal on Optimization 35(1), 270–301 (2025)

    Lee, J., Yi, S., Ryu, E.K.: Convergence analyses of Davis–Yin splitting via scaled relative graphs. SIAM Journal on Optimization 35(1), 270–301 (2025)

    2025

  26. [34]

    Advances in Neural Information Processing Systems 36 (2024)

    Li, H., Qian, J., Tian, Y., Rakhlin, A., Jadbabaie, A.: Convex and non-convex optimization under generalized smoothness. Advances in Neural Information Processing Systems 36 (2024)

    2024

  27. [35]

    preprint arXiv:2410.14811 (2024)

    Luner, A., Grimmer, B.: Performance estimation for smooth and strongly convex sets. preprint arXiv:2410.14811 (2024)

    2024 arXiv

  28. [36]

    SIAM Journal on Optimization 33(3), 1440–1462 (2023)

    Mishchenko, K.: Regularized Newton method with global convergence. SIAM Journal on Optimization 33(3), 1440–1462 (2023)

    2023

  29. [37]

    Nesterov, Y.: Lectures on convex optimization, vol. 137. Springer (2018) Performance Estimation of second-order optimization methods 49

    2018

  30. [38]

    SIAM (1994)

    Nesterov, Y., Nemirovskii, A.: Interior-point polynomial algorithms in convex program- ming. SIAM (1994)

    1994

  31. [39]

    Mathematical programming 108(1), 177–205 (2006)

    Nesterov, Y., Polyak, B.T.: Cubic regularization of Newton method and its global perfor- mance. Mathematical programming 108(1), 177–205 (2006)

    2006

  32. [40]

    Math- ematical programming 120, 125–145 (2009)

    Polyak, R.A.: Regularized Newton method for unconstrained convex optimization. Math- ematical programming 120, 125–145 (2009)

    2009

  33. [41]

    arXiv preprint arXiv:2406.17506 (2024)

    Rotaru, T., Glineur, F., Patrinos, P.: Exact worst-case convergence rates of gradient de- scent: a complete analysis for all constant stepsizes over nonconvex and convex functions. arXiv preprint arXiv:2406.17506 (2024)

    2024

  34. [42]

    arXiv preprint arXiv:2405.08405 (2024)

    Rubbens, A., Hendrickx, J.M.: A constraint-based approach to function interpolation, with application to performance estimation for weakly convex optimisation. arXiv preprint arXiv:2405.08405 (2024)

    2024

  35. [43]

    preprint arXiv:2504.14377 (2025)

    Rubbens, A., Hendrickx, J.M., Taylor, A.: A constructive approach to strengthen algebraic descriptions of function and operator classes. preprint arXiv:2504.14377 (2025)

    2025 arXiv

  36. [44]

    McGraw-Hill, New York (1976)

    Rudin, W.: Principles of Mathematical Analysis, 3rd edn. McGraw-Hill, New York (1976)

    1976

  37. [45]

    SIAM Journal on Optimization 30(3), 2251–2271 (2020)

    Ryu, E.K., Taylor, A.B., Bergeling, C., Giselsson, P.: Operator splitting performance es- timation: Tight contraction factors and optimal parameter selection. SIAM Journal on Optimization 30(3), 2251–2271 (2020)

    2020

  38. [46]

    Mathematical Programming 178(1), 145–213 (2019)

    Sun, T., Tran-Dinh, Q.: Generalized self-concordant functions: a recipe for Newton-type methods. Mathematical Programming 178(1), 145–213 (2019)

    2019

  39. [47]

    In: Conference on Learning Theory, pp

    Taylor, A., Bach, F.: Stochastic first-order methods: non-asymptotic and computer-aided analyses via potential functions. In: Conference on Learning Theory, pp. 2934–2992. PMLR (2019)

    2019

  40. [48]

    Taylor, A.B.: Convex interpolation and performance estimation of first-order methods for convex optimization. Ph.D. thesis, Catholic University of Louvain, Louvain-la-Neuve, Belgium (2017)

    2017

  41. [49]

    Mathematical Programming 161, 307–345 (2017)

    Taylor, A.B., Hendrickx, J.M., Glineur, F.: Smooth strongly convex interpolation and exact worst-case performance of first-order methods. Mathematical Programming 161, 307–345 (2017)

    2017

  42. [50]

    Journal of Optimization Theory and Applications 178, 455–476 (2018)

    Taylor, A.B., Hendrickx, J.M., Glineur, F.: Exact worst-case convergence rates of the proximal gradient method for composite convex minimization. Journal of Optimization Theory and Applications 178, 455–476 (2018)

    2018

  43. [51]

    arXiv preprint arXiv:2409.16047 (2024)

    Toint, P.L.: Examples of slow convergence for adaptive regularization optimization meth- ods are not isolated. arXiv preprint arXiv:2409.16047 (2024)

    2024 arXiv

  44. [52]

    American Journal of Mathematics 67(1), 83–93 (1945)

    Valentine, F.A.: A Lipschitz condition preserving extension for a vector function. American Journal of Mathematics 67(1), 83–93 (1945)

    1945

  45. [53]

    Whitney, H.: Differentiable functions defined in closed sets. I. Transactions of the American Mathematical Society 36(2), 369–387 (1934)

    1934

  46. [54]

    Yan, M.: Extension of convex function. Journal of Convex Analysis 21(4), 965–987 (2014) A Proof of Lemma 5 Proof (Proof of Lemma 5) (Necessity) Suppose S = {(xi, f0 i , f1 i , ..., fm i )}i∈[N ] is F -interpolable, and let f ∈ Fbe a function interpolating S, and in particular ...

    2014

  47. [55]

    The second case for fmax leads to no further constraint

    Hence, S is interpolable if and only if it satisfies (27), and ∀xi < xj : • Integration of fmin(x), Case 1: If α >1, or if α <1 and ˜gi + ˜gj ≥ M (xj − xi) = β(α) |β(α)| M (xj − xi), or considering FM,0: fj − fi ≥ β(α) |β(α)|M (β(α) + 1) ˜gβ(α)+1 i + ˜gβ(α)+1 j − 1 2β(α) (˜gi ...

  48. [56]

    When ∆h12 = ±M ∆x12 : gmax(x) = gmin(x) = g1 + h1∆xx1 ± M 2 ∆x2 x1 = g2 + h2∆xx2 ± M 2 ∆x2 x2

    + M (x1 − 2y1)(x − y1) if x ∈ [y1, y2] g2 + h2∆xx2 − M 2 ∆x2 x2 if x ∈ [y2, x2], (105) where y1 = x2 − T g 12 + M 2 ∆x2 12 ∆h12 + M ∆x12 − ∆h12 + M ∆x12 4M y2 = x2 − T g 12 + M 2 ∆x2 12 ∆h12 + M ∆x12 + ∆h12 + M ∆x12 4M , and gmax(x) =    g1 + h1∆xx1 + M 2 ∆x2 x1 if x ...

  49. [57]

    We first observe that gmin interpolates S since gmin(x1) = g1, gmin(x2) = g2, g′ min(x1) = h1 and g′ min(x2) = h2

    + M x2(x − y2) = g2 + h2∆xx2 − M 2 ∆x2 x2 − T g 12 − ∆h12(y2 − x2) − M (y2 − x2)∆x12 + ∆x2 12 2 − (y2 − y1)2 = g2 + h2∆xx2 − M 2 ∆x2 x2 − (T g 12 + M ∆x2 12 2 ) − (∆h12 + M ∆x12)(y2 − x2) + ∆h12 + M ∆x12 4M = g2 + h2∆xx2 − M 2 ∆x2 x2. We first observe that gmin interpolates S ...

  50. [58]

    Indeed, all conditions follow directly from the definition of g, h, λ0 and λ1 except for (110), i = 1, 2, which become equivalent to (39) and are thus satisfied by assumption on S

    + M (x1 − 2y1)(x − y1), is a valid solution. Indeed, all conditions follow directly from the definition of g, h, λ0 and λ1 except for (110), i = 1, 2, which become equivalent to (39) and are thus satisfied by assumption on S. Suppose now ∆h12 = −M ∆x12, which implies T g 12 = ...

  51. [59]

    By Lemma 7, these conditions are equivalent to the conditions of Theorem 5

    Indeed, in Proposition 5, we prove necessity and sufficiency of (39), (40), (44) and (30) to HM -interpolability of a set S = {(xi, gi, hi, fi)}i=1,2, relying on the integration of the extremal gradients derived in Lemma 12. By Lemma 7, these conditions are equivalent to the c...

  52. [60]

    If ∆hij + M |∆xij | ̸= 0, then |∆hij | ≤M |∆xij |, (113) T f ij ≥ −M 6 |∆xij |3 + T g ij + M 2 ∆xij |∆xij | 2 2 (∆hij + M |∆xij |) + (∆hij + M |∆xij |)3 96M 2 , (114) T f ij ≤ M 6 |∆xij |3 − T g ij − M 2 ∆xij |∆xij | 2 2 (M |∆xij | −∆hij ) − (M |∆xij | −∆hij )3 96M 2 , (115) T...

  53. [61]

    If ∆hij ± M |∆xij | = 0, then T g ij = ∓ M 2 ∆xij |∆xij | (117) T f ij = ∓ M 6 |∆xij |3 (118) Proof Suppose x1 < x2. By Lemma 1, it holds that S is FM -interpolable if and only if it satisfies |hj − hi| ≤M |xj − xi| (Proposition 1), (116) and Z x2 x1 gmin(x)dx ≤ f2 − f1 ≤ Z x2...

  54. [62]

    Then, f2 − f1 = Z x2 x1 gmin(x)dx ⇔ T f 12 = ± M 6 ∆x3 12 (126) Finally, suppose x1 < x2 and ∆h12 = ±M ∆x12 ⇔ ∆h21 = ±M ∆x21, implying T g 12 = ∓ M 2 ∆x2

  55. [63]

    By Lemma 12 applied to the pair (2, 1), it holds that T f 21 = ± M 6 ∆x3 21 ⇔ (103),(102) T f 12 = ∓∆x3

  56. [64]

    (127) Combining (126) and (127), it holds that ∀i, j= 1, 2 if ∆hij = ±M |∆xij |, then necessarily T f ij = ± M 6 |∆xij |3 (and T g ij = ± M 2 ∆xij |∆xij |) for S to be HM -interpolable. ⊓ ⊔ Performance Estimation of second-order optimization methods 57 E Proof of Lemma 7 Proof...

Pith tools

Reviewed August 6, 2026 · model on record in the stance chip above.