Worst-case convergence analysis of relatively inexact gradient descent on smooth convex functions

Fran\c{c}ois Glineur; Pierre Vernimmen

REVIEW 3 major objections 5 minor 35 references

Worst-case convergence analysis of relatively inexact gradient descent on smooth convex functions

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

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

Pith's one-line read The paper proves that for smooth convex functions, relatively inexact gradient descent converges for every stepsize $h\in[0,\tfrac{2}{1+\delta}]$ and that the one-step worst-case rate is given by an explicit three-regime formula, with…

desk verdict The one-step three-regime rate and the sharp h_max = 2/(1+δ) are solid and useful, but the 'exact worst-case' claim rests on an unproven intermediate-regime conjecture. read the letter →

arxiv 2506.17145 v2 pith:CP6V6ZF3 submitted 2025-06-20 math.OC

Pierre Vernimmen , François Glineur This is my paper · ORCID

classification math.OC MSC 90C2590C3090C22

keywords inexactgradientdescentrelativeerrorsmoothconvexoptimizationworst-caseconvergenceperformanceestimationstepsizeselectionsemidefiniteprogramming

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

Gradient descent normally assumes exact gradients, but in practice gradients come with errors. This paper studies a relative error model where the approximate gradient $d$ satisfies $\|d-\nabla f(x)\|\le \delta\|\nabla f(x)\|$ for a fixed $\delta<1$, so the error automatically shrinks near the optimum. The central claim is that on smooth convex functions the worst-case one-step contraction of the squared gradient norm is exactly the explicit three-regime formula stated in Theorem 2.3, and that convergence is guaranteed precisely for stepsizes $h\le 2/(1+\delta)$ while larger stepsizes can fail. If correct, the method is far more robust to relative noise than previous bounds suggested, and the optimal constant stepsize becomes nearly independent of the number of iterations once $\delta$ is moderate. The upper bound is proven for all regimes; the matching lower bound in the middle regime depends on a conjecture supported by numerical performance-estimation evidence.

What carries the argument

The central object is the performance-estimation formulation of worst-case analysis: the worst-case rate is posed as an optimization over gradients, iterates, and function values subject to the smooth-convex interpolation inequalities $f_i \ge f_j + \langle g_j, x_i-x_j\rangle + \tfrac{1}{2L}\|g_i-g_j\|^2$ and the relative inexactness constraint $\|d_0-g_0\|^2 \le \delta^2\|g_0\|^2$. The one-step argument takes a nonnegative linear combination of the interpolation inequalities and the inexactness constraint, then reduces the resulting $3\times 3$ matrix positivity condition, via a Schur complement, to a scalar optimization over a multiplier $\lambda$; the optimal multiplier is the largest real root $\tilde\lambda$ of the cubic in Definition 2.2. This machinery produces the three-regime formula and, in the left and right regimes, the explicit univariate worst-case functions that certify tightness.

What would settle it

Take $\delta=0.5$ and a stepsize $h$ strictly inside the intermediate regime, such as the near-optimal value shown in Figure 2.3, and compute a certified upper bound on the one-step worst-case rate using a branch-and-bound performance-estimation method. If the certified value lies strictly below the formula $C(h,\delta)$ of Theorem 2.3, then the intermediate regime is not tight; if it exceeds it, the upper bound itself fails. A single such gap would settle whether the claimed exact one-step rate is correct.

Watch

Extended reading notes

Core claim

The paper's discovery is that one step of relatively inexact gradient descent on an $L$-smooth convex function has a worst-case behavior split into three stepsize regimes, instead of the two regimes of exact gradient descent. In the left short-step regime $h\le \tfrac{3}{2(1+\delta)}$ the rate for the squared gradient norm in terms of the initial objective gap is $\frac{1}{h(1-\delta)}+\frac12$; in the right long-step regime $h\ge \tfrac{3\delta+2-\sqrt{4-3\delta^2}}{2\delta(1+\delta)}$ it is $2\bigl(1-h(1+\delta)\bigr)^2$; in the middle regime the rate is $\frac{2\tilde\lambda}{h\tilde\lambda^2+(2h-1)\tilde\lambda+h-1}$, where $\tilde\lambda$ is the largest real root of a cubic equation. The left and right rates are tight, attained by univariate worst-case functions (a Huber-like function and a quadratic), and the worst-case inexact direction is $d=(1\pm\delta)\nabla f(x)$, meaning the worst relative error acts exactly like a miscalibrated stepsize. The intermediate regime is conjectured to be tight with a bivariate worst-case function, for which the paper gives a partial two-dimensional construction and strong numerical evidence but no full analytical proof.

Load-bearing premise

The claim that the one-step rate is exactly the stated formula in the intermediate regime rests on Conjecture 2.6, which asserts tightness of the bound and bivariate worst-case structure, but is supported only by numerical performance-estimation evidence and a partial two-dimensional construction, not by an analytical worst-case function.

Editorial extensions

If this is right

For any relative error level $\delta\in[0,1)$, convergence to a minimizer is guaranteed for every constant stepsize $h\le \tfrac{2}{1+\delta}$, and this threshold is tight: no larger constant stepsize retains the guarantee.
In the short-step regime the rate per step is scaled by the factor $1-\delta$, while in the long-step regime the effective stepsize is $h(1+\delta)$, so relative noise behaves like a deliberate mistuning of the stepsize rather than an arbitrary perturbation.
The optimal stepsize for the worst-case one-step rate lies inside the narrow intermediate regime and, for moderate to large $\delta$, depends very little on the number of iterations, in contrast to the exact case where the optimal stepsize grows with the iteration count.
For multiple steps, the upper and lower bounds coincide in the left regime, giving a tight $O(1/N)$ rate with the same $\delta$-dependent prefactor, and a sharper tight subinterval exists in the right regime.
Using a stepsize at the right end of the intermediate regime, $h=\tfrac{3\delta+2-\sqrt{4-3\delta^2}}{2\delta(1+\delta)}$, yields near-optimal worst-case performance across a wide range of iteration counts and inexactness levels.

Reading between the lines

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

If Conjecture 2.6 is correct, the intermediate regime shows that one-dimensional worst-case examples miss the true difficulty of relative inexactness: the error must rotate around the gradient, so analyses restricted to univariate functions systematically understate the worst case.
The near-independence of the optimal stepsize from the iteration count suggests a practical design rule for low-precision training: choose the stepsize near the right end of the intermediate regime once the relative error level is known, and do not increase it as the training horizon grows.
Because the worst-case relative error is equivalent to stepsize miscalibration, accelerated methods with momentum, which are more sensitive to stepsize, may suffer disproportionately under relative inexactness; this is a testable conjecture for a performance-estimation analysis of accelerated variants.
The numerical observation that the worst-case error becomes orthogonal to the gradient at the optimal stepsize hints at a general principle for designing inexact oracles: aligning the error budget perpendicular to the gradient may be the least harmful way to spend an inexactness allowance.

Share X Bluesky LinkedIn Reddit HN

Signed reviews

No signed human review yet.

Editorial analysis

A structured set of objections, weighed in public.

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

Desk Editor's Note

read the letter

You should read this as a conditional accept, not a reject. The core new result is real: the one-step worst-case rate for relatively inexact gradient descent on smooth convex functions splits into three regimes, and the sharp stepsize threshold h_max = 2/(1+δ) improves Vasin's earlier bound substantially. The left and right regimes are proven tight with explicit Huber and quadratic worst-case functions, and the worst-case-error-as-stepsize-miscalibration interpretation is a nice insight. The upper-bound proof uses explicit multiplier constructions and ships code, so it is reproducible, and the paper is clear about what is and is not proven.

The main soft spot is exactly where the reader and the stress-test note put it. The abstract says the authors 'derive the exact worst-case behavior of the method after one step', but that is only true in the left and right regimes. In the intermediate regime, tightness is Conjecture 2.6, supported by numerical PEP evidence and a bivariate construction that matches the bound only at the optimal stepsize, not across the whole interval. The authors are honest about this in the body—they label it a conjecture and say no explicit worst-case instance was found—so the problem is in the framing, not the mathematics. The abstract and introduction should be brought in line with what is actually proven.

The multi-step lower bound (Theorem 3.2) is sketchy: the proof says 'argument similar to that in Theorem 2.4' without spelling out the N-step construction. It looks plausible, and the functions are given, but a referee will want a complete argument. Remark 3.3 also asserts a sharper bound 'it can be shown' without proof. These are fixable, but they need to be addressed.

On the positive side, the derivation is self-contained, the cubic defining λ⎯ is structural rather than fitted, and the numerical experiments are clearly separated from the analytical results. The citation pattern looks fine—building on the authors' own earlier PEP work is normal here, and the comparison with [12] is useful.

My bottom line: send it to peer review. A good referee can push for either a proof of Conjecture 2.6 or a corrected abstract that limits the 'exact' claim to the proven regimes. With that revision, this is a solid contribution to the PEP and inexact-optimization literature.

Referee Report

3 major / 5 minor

Summary. The manuscript analyzes constant-stepsize gradient descent with relative gradient inexactness on L-smooth convex functions. Using the Performance Estimation Problem (PEP) framework, it derives a one-step worst-case upper bound C(h, delta) with three stepsize regimes (Theorem 2.3), proves tightness of the left and right regimes via explicit Huber and quadratic worst-case functions (Theorem 2.4), and conjectures tightness of the intermediate regime (Conjecture 2.6). It then extends the analysis to several steps with an upper bound (Theorem 3.1), a lower bound (Theorem 3.2), and numerical observations on optimal stepsizes. The abstract advertises an 'exact worst-case' one-step result, but the intermediate-regime tightness is not proven.

Significance. If the intermediate-regime conjecture were resolved, the paper would provide the exact one-step worst-case rate for relatively inexact gradient descent on smooth convex functions, with a clean three-regime structure and explicit worst-case functions in the two outer regimes. The proven upper bound also yields an admissible stepsize range h in [0, 2/(1+delta)] that improves on previous bounds such as those of Vasin. The use of PEP with explicit multiplier constructions, computer-assisted symbolic algebra, and openly available code is a strength: the derivation is self-contained and reproducible. However, the advertised exactness claim for the one-step rate is only fully proven in the left and right regimes; the intermediate regime rests on numerical evidence, so the significance of the central claim is currently conditional.

major comments (3)

[Section 2.4; Conjecture 2.6] The abstract and Section 1.3 claim that the paper derives 'the exact worst-case behavior of the method after one step.' This exactness claim is not established for the whole one-step stepsize range. Theorem 2.3 provides an upper bound, and Theorem 2.4 proves tightness only in the left and right regimes. For h in the intermediate interval [3/(2(1+delta)), (3delta+2-sqrt(4-3delta^2))/(2delta(delta+1))], the lower bound is Conjecture 2.6, supported by numerical PEP solutions and a bivariate construction that matches the bound only at the optimal stepsize (Section 2.4, Figure 2.6). The manuscript should either supply a certified analytical lower-bound certificate for the whole intermediate interval or amend the abstract and introduction to state the result as a proven upper bound with a conjectured matching lower bound.
[Section 3.2; Theorem 3.2] The lower-bound theorem for N steps is not fully proved. The proof defines f1 and f2 and then says the result follows 'using an argument similar to that in Theorem 2.4, adapted to the N-steps case.' This adaptation is nontrivial: one must verify that the iterates stay in the appropriate linear/quadratic regions for all N steps, that the max of the two candidate lower bounds is valid for every h in [0, 2/(1+delta)], and that the boundary between the regimes is handled. As written, this is a proof sketch rather than a complete proof; it should be expanded or the statement should be marked as conditional.
[Section 3.2; Remark 3.3] Remark 3.3 asserts that a sharper upper bound, matching the lower bound 2(1-h(1+delta))^{-2N}, holds for all h >= h_tilde(N), where h_tilde(N) is defined implicitly as a root of a polynomial whose degree increases with N. No proof or even outline is provided for this claim. Since this remark is used to support the statement that the multi-step rate is tight on [h_tilde(N), 2/(1+delta)), it should be proved, or explicitly labeled as a conjecture. The definition of h_tilde(N) also needs a uniqueness/validity statement.

minor comments (5)

[Section 2.1] In the proof of Theorem 2.1, 'previsously' should read 'previously.'
[Figure 2.2] The axis labels for lambda(h) are garbled: expressions such as 'right = 2 h(1 + ) / h(1 + ) 1' are missing delta and are hard to read. Please render the formulas with proper symbols.
[Section 2.4] The sentence 'whereas the worse 1D constructions fall short' is grammatically unclear; it should be 'whereas the 1D constructions fall short' or a similar correction.
[Section 1.5] The statement that an explicit worst-case function is provided 'for nearly all values of the stepsize' is accurate, but it would help the reader if the exceptional values were identified explicitly as the intermediate regime, consistent with Conjecture 2.6.
[Definition 2.2] Definition 2.2 defines lambda-tilde as the largest real root of a cubic, but the text does not state explicitly that this root is unique and positive over the relevant parameter range. A short lemma or explicit verification would make the definition more robust.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity: the PEP-based rate is derived from interpolation and inexactness inequalities, and the only notable gap is an unproven tightness conjecture, which is not circular.

full rationale

The derivation chain in this paper is self-contained. The one-step upper bound in Theorem 2.3 is obtained by taking nonnegative linear combinations of the smooth-convex interpolation inequalities (INT) and the relative inexactness constraint (1), with multipliers whose values come from the semidefinite-positiveness conditions in the proof; the quantity lambda-tilde is the largest real root of a cubic obtained from the proof structure, not a parameter fitted to the claimed rate. Tightness in the left and right regimes is established by explicit worst-case functions: a Huber function for the left regime and a quadratic for the right regime, with admissible inexact directions d0 = (1±delta) grad f(x0). These are genuine lower-bound constructions, not reverse-engineered fits. The intermediate regime is explicitly labelled as a conjecture (Conjecture 2.6), supported only by numerical PEP evidence, so the abstract's phrase 'exact worst-case behavior' is stronger than what is proven in that regime; however, this is an unproven completeness gap, not circularity, because the conjectured lower bound is not an input to the upper-bound derivation. The multi-step upper bound in Theorem 3.1 is a direct summation of the one-step inequality, and the lower bound in Theorem 3.2 uses explicit Huber and quadratic functions; both are transparent. References to [11] and [24] supply standard interpolation conditions and the exact-case rate, and the paper even reproves the one-step exact case as preparation. No fitted input is renamed as a prediction, and no load-bearing premise is justified only by the authors' prior work. Thus the central claim is not circular; the appropriate score is 0.

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

The analysis uses no fitted constants and introduces no new mathematical entities. The multiplier lambda-tilde is derived as the largest root of a cubic equation whose coefficients come from the proof structure, not from data fitting. The main additional burden beyond standard assumptions is the conjectured tightness in the intermediate regime.

assumptions (5)

standard math The class of L-smooth convex functions is exactly characterized by the interpolation condition (INT) of Section 1.4.
This is the foundation of the PEP formulation, attributed to [11] and stated as equation (INT) in Section 1.4.
domain assumption An admissible value of the smoothness constant L is available, so the normalized stepsize h can be chosen in the guaranteed interval.
Stated in the Remark at the end of Section 1.1: 'we assume that an admissible value of the smoothness constant L is available'.
domain assumption At every iteration the approximate gradient satisfies the relative bound ||d_k - grad f(x_k)|| <= delta ||grad f(x_k)||.
This is the defining model of Algorithm 1, inequality (1), and all results are conditional on it being satisfied at each step.
ad hoc to paper The one-step worst-case rate in the intermediate regime is tight (Conjecture 2.6).
Section 2.4: only numerical PEP evidence and a bivariate construction are provided; no analytical worst-case function is given, so the 'exact' one-step claim rests on an unproved conjecture.
standard math The problem can be rescaled so that L = 1 without loss of generality.
Invoked in the proofs of Theorems 2.1 and 2.3 via the homogeneity argument cited from [11, Section 3.5].

how reviews work

0 comments

Cite this review

Pith. "Pith review of Worst-case convergence analysis of relatively inexact gradient descent on smooth convex functions." pith.science (2026). https://pith.science/paper/CP6V6ZF3

@misc{pith2026250617145,
  author       = {Pith},
  title        = {Pith review of: Worst-case convergence analysis of relatively inexact gradient descent on smooth convex functions},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/CP6V6ZF3}},
  note         = {Machine review of arXiv:2506.17145}
}

read the original abstract

We consider the classical gradient descent algorithm with constant stepsizes, where some error is introduced in the computation of each gradient. More specifically, we assume some relative bound on the inexactness, in the sense that the norm of the difference between the true gradient and its approximate value is bounded by a certain fraction of the gradient norm. This paper presents a worst-case convergence analysis of this so-called relatively inexact gradient descent on smooth convex functions, using the Performance Estimation Problem (PEP) framework. We first derive the exact worst-case behavior of the method after one step. Then we study the case of several steps and provide computable upper and lower bounds using the PEP framework. Finally, we discuss the optimal choice of constant stepsize according to the obtained worst-case convergence rates.

Figures

Figures reproduced from arXiv: 2506.17145 by the authors.

**Figure 1.1.** Convergence rate σN of exact and inexact (δ = 0.2) gradient descent after N iterations. Deriving proofs. Solving the PEP not only yields a tight worst-case performance guarantee, but also provides a way to derive a proof of those convergence bounds [11]. Those proofs are a byproduct of standard convex optimization duality. More concretely, all PEP convergence bounds can be obtained by summing the interpolation and… view at source ↗

**Figure 2.1.** Convergence rate of one step of exact and inexact gradient descents with [PITH_FULL_IMAGE:figures/full_fig_p021_2_1.png] view at source ↗

**Figure 2.2.** Multiplier λ(h) from the proof of Theorem 2.3 for different values of δ along the three regimes. This shows that the proof is continuous over all step sizes ∈ [0, 2 1+δ ]. Compared to the exact case, where two stepsize regimes naturally arise (short-step and long-step), an interesting phenomenon occurs in the inexact setting: the emergence of a third distinct regime. We refer to the first regime, h ∈ h 0, 3 2(1+δ) … view at source ↗

Figures from the paper (10 more)

**Figure 2.3.** Figure 2.3: (top) Convergence rate (blue dots) for different levels of inexactness for all [PITH_FULL_IMAGE:figures/full_fig_p023_2_3.png]

**Figure 2.4.** Figure 2.4: Comparison of our hmax for which convergence is guaranteed with the one from [12]. 2.3. Tightness of the rate in the left and right regimes After establishing worst-case convergence rates for the inexact gradient descent in Theorem 2.3, we now show that these rates c…

**Figure 2.5.** Figure 2.5: Exact and inexact (δ = 0.3) gradient descent on worst-case functions for left and right regimes. From these plots, we observe a clear pattern: in the left regime, where the stepsize is already small, the worst-case effect of relative inexactness is to make the step e…

**Figure 2.6.** Figure 2.6: Convergence rate of intermediate regime from Theorem 2.3 versus 1D and 2D [PITH_FULL_IMAGE:figures/full_fig_p029_2_6.png]

**Figure 2.7.** Figure 2.7: Worst-case direction error d0 − ∇f(x0) rotating around the gradient in the intermediate regime (example with normalized gradient and δ = 0.5). Moreover, numerical evidence from the PEP experiments suggests that the orthogonality condition discussed above is met preci…

**Figure 3.1.** Figure 3.1: Lower and upper bounds and exact value of the convergence rate for different [PITH_FULL_IMAGE:figures/full_fig_p033_3_1.png]

**Figure 3.2.** Figure 3.2: Threshold h˜(N) as a function of N for different values of δ (dots). Dashed lines indicate the maximum stepsize 2/(1 + δ), and the shaded regions highlight the interval between h˜ and this threshold. 3.3. Approximation of the optimal stepsize We now investigate the o…

**Figure 3.3.** Figure 3.3: Numerical hopt depending on the number of iterations N for different levels of inexactness δ (solid lines) and corresponding end of 1-step intermediate regimes (dashed lines). We observe two distinct behaviors depending on the inexactness level δ: • For small values …

**Figure 3.** Figure 3: confirms that choosing as stepsize the right end of the interme [PITH_FULL_IMAGE:figures/full_fig_p035_3.png]

**Figure 3.4.** Figure 3.4: Numerical rate at hopt (solid dots) and at its approximation by 3δ+2− √ 4−3δ 2 2δ(δ+1) (dashed lines) for different number of iterations. This sharply contrasts with the exact case, where stepsize h must grow with N to maintain optimality. In the relatively inexact s…

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

35 extracted references · 30 canonical work pages

[12]

Gradient directions and relative inexactness in optimization and machine learning

A. Vasin, Gradient directions and relative inexactness in optimization and machine learning, arXiv preprint arXiv:2407.00667 (2024)

work page Pith review arXiv 2024
[1]

Fazlyab, A

M. Fazlyab, A. Robey, H. Hassani, M. Morari, G. Pappas, Efficient and accurate estimation of Lipschitz constants for deep neural networks, Advances in neural information processing systems 32 (2019)

work page 2019
[2]

Lan, First-order and stochastic optimization methods for machine learning, Vol

G. Lan, First-order and stochastic optimization methods for machine learning, Vol. 1, Springer, 2020

work page 2020
[3]

Nesterov, Introductory lectures on convex optimization: A basic course, Vol

Y. Nesterov, Introductory lectures on convex optimization: A basic course, Vol. 87, Springer Science & Business Media, 2013

work page 2013
[4]

Empirical and computer-aided robustness analysis of long-step and accelerated methods in smooth convex optimization

P. Vernimmen, F. Glineur, Empirical and computer-aided robustness analysis of long-step and accelerated methods in smooth convex opti- mization, arXiv preprint arXiv:2506.09730 (2025)

work page Pith review arXiv 2025
[5]

d’Aspremont, Smooth optimization with approximate gradient, SIAM Journal on Optimization 19 (3) (2008) 1171–1183.doi:10.1137/ 060676386

A. d’Aspremont, Smooth optimization with approximate gradient, SIAM Journal on Optimization 19 (3) (2008) 1171–1183.doi:10.1137/ 060676386

work page 2008
[6]

Devolder, F

O. Devolder, F. Glineur, Y. Nesterov, First-order methods of smooth convex optimization with inexact oracle, Mathematical Programming 146 (2014) 37–75

2014
[7]

N.-C.Kempke, T.Koch, Low-precisionfirst-ordermethod-basedfix-and- propagate heuristics for large-scale mixed-integer linear optimization, arXiv preprint arXiv:2503.10344 (2025)

arXiv 2025

Show all 35 references

[8]

De Klerk, F

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

2017
[9]

De Klerk, F

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

2020
[10]

Drori, M

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

2014
[11]

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

2017
[13]

Vasin, A

A. Vasin, A. Gasnikov, P. Dvurechensky, V. Spokoiny, Accelerated gra- dient methods with absolute and relative noise in the gradient, Opti- mization Methods and Software 38 (6) (2023) 1180–1229

2023
[14]

Kornilov, E

N. Kornilov, E. Gorbunov, M. Alkousa, F. Stonyakin, P. Dvurechensky, A. Gasnikov, Intermediate gradient methods with relative inexactness, arXiv preprint arXiv:2310.00506 (2023)

2023 arXiv
[15]

Vasin, V

A. Vasin, V. Krivchenko, D. Kovalev, F. Stonyakin, N. Tupitsa, P. Dvurechensky, M. Alkousa, N. Kornilov, A. Gasnikov, On solving minimization and min-max problems by first-order methods with rela- tive error in gradients, arXiv preprint arXiv:2503.06628 (2025)

2025
[16]

Hallak, K

N. Hallak, K. Y. Levy, A study of first-order methods with a proba- bilistic relative-error gradient oracle, Preprint, optimization-online. URLhttps://optimization-online.org/wp-content/uploads/ 2025/02/RAGM.pdf

2025
[17]

P. D. Khanh, B. Mordukhovich, D. B. Tran, Convergence of first-order algorithms with momentum from the perspective of an inexact gradient descent method, arXiv preprint arXiv:2505.03050 (2025)

2025 arXiv
[18]

Bello-Cruz, M

Y. Bello-Cruz, M. L. Gonçalves, J. G. Melo, C. Mohr, A relative in- exact proximal gradient method with an explicit linesearch, Journal of Optimization Theory and Applications 206 (1) (2025) 1–32

2025
[19]

S. Wang, V. Y. Tan, Robust distributed gradient descent to corrup- tion over noisy channels, in: 2024 IEEE International Symposium on Information Theory (ISIT), IEEE, 2024, pp. 2520–2525

2024
[20]

Vasin, A

A. Vasin, A. Gasnikov, V. Spokoiny, Stopping rules for accelerated gra- dient methods with additive noise in gradient (2021). 39

2021
[21]

D. B. Thomsen, A. Taylor, A. Dieuleveut, Tight analyses of first-order methods with error feedback, arXiv preprint arXiv:2506.05271 (2025)

2025
[22]

Vernimmen, F

P. Vernimmen, F. Glineur, Convergence analysis of an inexact gradient method on smooth convex functions, in: Proceedings of the 32nd Euro- pean Symposium on Artificial Neural Networks, Computational Intelli- gence and Machine Learning, 2024, pp. 125–130

2024
[23]

D. Kim, J. A. Fessler, Optimizing the efficiency of first-order methods for decreasing the gradient of smooth convex functions, Journal of opti- mization theory and applications 188 (1) (2021) 192–219

2021
[24]

T.Rotaru, F.Glineur, P.Patrinos, Exactworst-caseconvergenceratesof gradient descent: a complete analysis for all constant stepsizes over non- convex and convex functions, arXiv preprint arXiv:2406.17506 (2024)

2024
[25]

A. B. Taylor, J. M.Hendrickx, F.Glineur, Exactworst-case performance of first-order methods for composite convex optimization, SIAM Journal on Optimization 27 (3) (2017) 1283–1313

2017
[26]

Version 11.0

MOSEK ApS, The MOSEK Python Fusion API manual. Version 11.0. (2025). URLhttps://docs.mosek.com/latest/pythonfusion/index.html

2025
[27]

A. B. Taylor, J. M. Hendrickx, F. Glineur, Performance estimation tool- box (pesto): Automated worst-case analysis of first-order optimization methods, in: 2017 IEEE 56th Annual Conference on Decision and Con- trol (CDC), IEEE, 2017, pp. 1278–1283

2017
[28]

Goujaud, C

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

2024
[29]

Zhang, The Schur complement and its applications, Vol

F. Zhang, The Schur complement and its applications, Vol. 4, Springer Science & Business Media, 2006

2006
[30]

Meurer, C

A. Meurer, C. P. Smith, M. Paprocki, O. Čertík, S. B. Kirpichev, M. Rocklin, A. Kumar, S. Ivanov, J. K. Moore, S. Singh, T. Rathnayake, S.Vig, B.E.Granger, R.P.Muller, F.Bonazzi, H.Gupta, S.Vats, F.Jo- hansson, F. Pedregosa, M. J. Curry, A. R. Terrel, v. Roučka, A. Saboo, 40 I...

2017
[31]

URLhttps://www.wolfram.com/mathematica

Wolfram Research Inc., Mathematica, Version 14.2, champaign, IL, 2024. URLhttps://www.wolfram.com/mathematica

2024
[32]

Vernimmen, Tight convergence analysis of exact and inexact gradient methods with constant and silver schedules, Master’s thesis, UCLouvain (2024)

P. Vernimmen, Tight convergence analysis of exact and inexact gradient methods with constant and silver schedules, Master’s thesis, UCLouvain (2024)

2024
[33]

Das Gupta, B

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

2024
[34]

Cortild, L

D. Cortild, L. Ketels, J. Peypouquet, G. Garrigos, New tight bounds for SGD without variance assumption: A computer-aided lyapunov analy- sis, arXiv preprint arXiv:2505.17965 (2025)

2025
[35]

Rubbens, S

A. Rubbens, S. Colla, J. M. Hendrickx, Computer-aided analyses of stochastic first-order methods, via interpolation conditions for stochastic optimization, arXiv preprint arXiv:2507.05466 (2025). 41

2025

Pith tools

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

[1] [12]

Gradient directions and relative inexactness in optimization and machine learning

A. Vasin, Gradient directions and relative inexactness in optimization and machine learning, arXiv preprint arXiv:2407.00667 (2024)

work page Pith review arXiv 2024

[2] [1]

Fazlyab, A

M. Fazlyab, A. Robey, H. Hassani, M. Morari, G. Pappas, Efficient and accurate estimation of Lipschitz constants for deep neural networks, Advances in neural information processing systems 32 (2019)

work page 2019

[3] [2]

Lan, First-order and stochastic optimization methods for machine learning, Vol

G. Lan, First-order and stochastic optimization methods for machine learning, Vol. 1, Springer, 2020

work page 2020

[4] [3]

Nesterov, Introductory lectures on convex optimization: A basic course, Vol

Y. Nesterov, Introductory lectures on convex optimization: A basic course, Vol. 87, Springer Science & Business Media, 2013

work page 2013

[5] [4]

Empirical and computer-aided robustness analysis of long-step and accelerated methods in smooth convex optimization

P. Vernimmen, F. Glineur, Empirical and computer-aided robustness analysis of long-step and accelerated methods in smooth convex opti- mization, arXiv preprint arXiv:2506.09730 (2025)

work page Pith review arXiv 2025

[6] [5]

d’Aspremont, Smooth optimization with approximate gradient, SIAM Journal on Optimization 19 (3) (2008) 1171–1183.doi:10.1137/ 060676386

A. d’Aspremont, Smooth optimization with approximate gradient, SIAM Journal on Optimization 19 (3) (2008) 1171–1183.doi:10.1137/ 060676386

work page 2008

[7] [6]

Devolder, F

O. Devolder, F. Glineur, Y. Nesterov, First-order methods of smooth convex optimization with inexact oracle, Mathematical Programming 146 (2014) 37–75

2014

[8] [7]

N.-C.Kempke, T.Koch, Low-precisionfirst-ordermethod-basedfix-and- propagate heuristics for large-scale mixed-integer linear optimization, arXiv preprint arXiv:2503.10344 (2025)

arXiv 2025