The Ball-Proximal (="Broximal") Point Method: a New Algorithm, Convergence Theory, and Applications

Aadi Rane; Hanmin Li; Kaja Gruntkowska; Peter Richt\'arik

The Ball-Proximal (="Broximal") Point Method: a New Algorithm, Convergence Theory, and Applications

T0 review · reviewed 2026-08-09 · deepseek-v4-flash

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

Pith's one-line read The paper claims that replacing the quadratic penalty in the proximal point method with a ball constraint gives an algorithm that converges linearly and reaches an exact minimizer in finitely many steps for nonsmooth convex problems, and…

desk verdict Solid convex theorem under a very expensive oracle; the nonconvex extension has a real continuity gap and rests on a bespoke assumption. read the letter →

arxiv 2502.02002 v2 pith:NGSYS47D submitted 2025-02-04 math.OC cs.LGstat.ML

Kaja Gruntkowska , Hanmin Li , Aadi Rane , Peter Richtárik This is my paper · ORCID

classification math.OCcs.LGstat.ML MSC 90C2590C2690C3065K05

keywords ball-proximalpointmethodbroximaloperatornonsmoothconvexoptimizationlinearconvergencefiniteterminationball-convexitynormalizedgradientdescenttrust-regionmethods

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

The paper introduces the Ball-Proximal Point Method (BPM), which at each iteration minimizes the objective inside a Euclidean ball centered at the current point instead of adding a quadratic penalty as the proximal point method does. The central claim is that for any proper, closed, convex objective, an exact ball oracle makes BPM converge linearly in function value and find an exact global minimizer in finitely many steps, without any smoothness or strong convexity assumption. This contrasts with the sublinear rate of the classical proximal point method in the nonsmooth convex regime. The paper further introduces ball-convexity and shows that the same global convergence guarantees hold for that broader, possibly nonconvex, function class, while also relating BPM to normalized gradient descent, acceleration, adaptive step sizes, and trust-region methods.

What carries the argument

The central object is the ball-proximal ("broximal") operator $\operatorname{brox}_f^t(x) = \arg\min_{z \in B_t(x)} f(z)$, where $B_t(x)$ is the Euclidean ball of radius $t$ around $x$: it replaces the quadratic penalty of the proximal operator with a hard ball constraint. The machinery is the second brox theorem, which extracts from optimality of the ball subproblem a scalar $c_t(x) \ge 0$ such that $c_t(x)(x-u) \in \partial f(u)$ and the supporting inequality above; combined with the fact that non-optimal broximal iterates lie on the ball boundary, this inequality yields both the distance decrease by $t_k^2$ and the ratio-symmetric linear contraction in Theorem 8.1. BPM also inherits a family of reformulations: it is a normalized proximal point method for differentiable convex objectives, normalized gradient descent on the newly defined ball envelope under smoothness, and an idealized trust-region method whose model is exact.

What would settle it

Minimize $f(x) = |x|$ from $x_0 = 2$ with constant radius $t = 1$: the exact broximal oracle returns $x_1 = 1$ and $x_2 = 0$, so finite termination occurs after two steps; any approximate oracle that returns points with suboptimality $\varepsilon > 0$ inside the ball will fail to reproduce this exact trajectory, showing that the finite and linear guarantees are contingent on exact oracle access.

Watch

Extended reading notes

Core claim

Under the assumption that each ball subproblem is solved exactly, BPM with any positive radii $\{t_k\}$ satisfies: if the ball around $x_k$ contains a minimizer, the next iterate is optimal; otherwise the step moves exactly distance $t_k$ and the squared distance to any minimizer decreases by at least $t_k^2$. Consequently, once $\sum_{k=0}^{K-1} t_k^2 \ge \operatorname{dist}^2(x_0, X_f)$, the iterate $x_K$ is an exact global minimizer. The function-value error obeys $f(x_{k+1}) - f_\star \le \left(1 + t_k / \|x_{k+1} - x_\star\|\right)^{-1} (f(x_k) - f_\star)$, giving linear convergence with no smoothness or strong convexity, and the distance $\|x_{k+1} - x_\star\|$ never increases. The paper's second brox theorem establishes the driving inequality: for convex $f$ and $u \in \operatorname{brox}_f^t(x)$, there exists $c_t(x) \ge 0$ with $f(y) - f(u) \ge c_t(x)\langle x-u, y-u\rangle$ for all $y$, which is exactly what powers the contraction.

Load-bearing premise

Each iteration of BPM requires an exact oracle that returns a true global minimizer of $f$ inside the ball $B_{t_k}(x_k)$, a subproblem that is generally as hard as the original global optimization; the nonconvex extension further postulates an inequality that is nearly the contraction used in the proof.

Editorial extensions

If this is right

For nonsmooth convex objectives, BPM with constant radius $t$ terminates at an exact global minimizer in at most $\lceil \operatorname{dist}^2(x_0, X_f)/t^2 \rceil$ iterations, something PPM with finite step size cannot do.
A single iteration with radius $t_0 \ge \operatorname{dist}(x_0, X_f)$ solves the problem from scratch, because the ball then contains a minimizer.
The linear rate in Theorem 8.1 requires neither strong convexity nor smoothness, eliminating the usual conditions behind linear convergence of proximal-type methods.
BPM's reformulation as normalized gradient descent on the ball envelope gives a principled derivation of normalization and of increasing adaptive step sizes toward the solution.
Choosing radii $t_k = (\gamma \|\nabla f(x_{k+1})\|)^{1/p}$ recovers $p$-th order proximal point updates and their $O(1/K^p)$ accelerated rates.

Reading between the lines

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

My inference: the finite-termination guarantee is a statement about the exact ball oracle, not about implementable computation; replacing the oracle by any approximate solver, such as projected gradient descent or sampling inside the ball, should destroy exact finite termination and likely degrade the contraction factor, so the practical value of BPM rests on how well cheap subroutines approximate
My inference: the ball-envelope reformulation suggests a testable design principle: apply normalized gradient descent to progressively narrower ball envelopes, tuned so that every iterate lies within distance $t$ of the previous one, which could yield a practical algorithm with BPM-like guarantees and per-step cost controlled by the envelope width.
My inference: ball-convexity is a structural condition that is hard to verify for a given nonconvex function; a useful next step would be to characterize simple sufficient conditions, for instance piecewise linear or star-shaped landscapes with controlled curvature, under which Assumption A.1 holds with an explicit $c_t(x)$.

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.

Desk Editor's Note

read the letter

Read this for a clean convex theorem and an equally clean warning about oracle assumptions. The convex core of the paper, Theorem 8.1, is correct: if you can exactly minimize a closed convex f on a ball at each step, BPM gets squared-distance decrease, linear function-value contraction, and finite termination without smoothness or strong convexity. I checked the appendix proof; it holds up under the exact ball oracle. That is a genuine, if conceptual, contribution. The paper is also honest about the oracle being expensive, and it positions itself reasonably against the Carmon et al. ball-optimization literature.

The nonconvex story is weaker. Assumption A.1 (ball-convexity) is engineered: its defining inequality is exactly the contraction inequality used in the proof, so the nonconvex results are consequences of a bespoke condition rather than an independently motivated structural class. And there is a concrete gap in Theorem E.16. It promises linear and finite convergence under proper, closed f plus A.1, but the proof needs ||x_{k+1}-x_k||=t_k. That boundary property is Proposition E.8, which explicitly assumes continuity. For extended-real-valued nonconvex f, proper and closed means lower semicontinuity only, which allows upward jumps, so the proposition does not apply. Either the theorem needs a continuity hypothesis or the boundary property has to be proved from A.1 alone. As written, the nonconvex claims overreach.

The reformulation sections (normalized PPM, normalized GD on the ball envelope, trust-region framing) are mostly elementary re-derivations, but they are clearly written and will help some readers connect ideas. The appendix extensions (stochastic, Bregman) are standard and not the reason to read the paper. Citation pattern looks fine; the self-citation is not a problem because the convex result is formally derived, not just claimed.

Who should read it: people working on oracle-based optimization or on understanding what assumptions actually drive finite convergence. It is a useful example of how an exact-ball oracle is a very strong premise. I would give it a serious referee — the convex theorem deserves an outlet and the nonconvex gap is fixable. I would also bring it to our group, with the oracle caveat front and center.

Circularity Check

0 steps flagged · score 2.0 of 10

No significant circularity: the convex core is a genuine derivation from convexity plus the explicit ball oracle, and the nonconvex extension is an honest conditional statement under the stated Assumption A.1.

full rationale

The paper's central convex result, Theorem 8.1, is self-contained: it derives linear and finite convergence from the proper, closed, convex assumption together with the exact ball oracle, via Theorem D.2. No parameter is fitted and then renamed a prediction, and the method's high oracle cost is explicitly acknowledged in Section 1.5, where BPM is called a conceptual “master” method. The reformulations in Lemma 3.1, Theorem 3.2, Theorem 4.2, and Theorem 5.2 are either identities or explicit reductions to known results (e.g., Ahn & Sra 2020 for AGM), not circular predictions. The nonconvex extension is conditional on Assumption A.1, whose inequality (15) is indeed the same inequality used to prove the contraction; the proof of Theorem E.16 begins with that defining property. This makes the nonconvex class bespoke and the result conditional, but it is not circular: the paper does not claim to derive the assumption from the conclusion, and Example 1 shows the class is nonempty outside convexity. The more serious issue is a correctness gap, not circularity: Theorem E.16 is stated under only proper, closed, and Assumption A.1, but its proof needs the boundary identity ||x_{k+1}-x_k||=t_k, which Proposition E.8 establishes only under continuity; a lower-semicontinuous nonconvex function may have upward jumps, so the finite-convergence criterion based on sum t_k^2 is not justified under the stated hypotheses. This should be flagged as a correctness risk. The paper's self-citations are not load-bearing for the main derivation, and there is no uniqueness theorem or ansatz smuggled in through citation. Overall, the derivation chain does not reduce to its inputs by construction; no circular step meets the evidentiary bar.

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

The central convex theorem depends only on standard convex analysis and the assumption that the ball subproblem is solved exactly. The nonconvex extension depends on the bespoke Assumption A.1, which is nearly identical to the contraction inequality used in the proof, and on a continuity assumption that is not stated in Theorem E.16. No parameters are fitted to data.

assumptions (8)

domain assumption f is proper, closed and convex
Theorem 8.1 and Corollary 8.2 are stated for this class; convexity supplies the subgradient inequality in Theorem D.2.
domain assumption Exact ball-minimization oracle
Algorithm 1 assumes argmin over B_t(x) is computed exactly. Without this, the distance and function-value contractions do not hold.
ad hoc to paper Assumption A.1 (Bt-convexity)
Introduced in Appendix A and used in Theorem E.16; it is essentially inequality (15), the same inequality from which all contraction rates are derived.
ad hoc to paper Assumption E.18 (weak Bt-convexity)
Defined to obtain the halved-rate finite convergence in Theorem E.21; no independent characterization or practical verification is provided.
domain assumption Continuity of f for the boundary property
Proposition E.8, used to ensure steps have length t in the ball-convex case, is proven under continuity; this is omitted from Theorem E.16.
standard math Ahn and Sra (2020) AGM-as-PPM analysis
Theorem G.2 and Theorem 4.2 reduce A-BPM convergence to this cited result; the paper does not re-derive it.
domain assumption L-smoothness for ball envelope gradient equivalence
Theorem 5.2 and Lemma H.4 require convex L-smooth f to identify the gradient of the ball envelope with the gradient at the next iterate.
domain assumption Strict convexity of the Bregman generator h
Lemma J.3 uses strict convexity of h to ensure the Bregman sublevel set is strictly convex and the broximal operator is singleton-valued.

invented entities (3)

Ball-proximal (broximal) operator
purpose: Core iteration: argmin over a ball; a new operator replacing the quadratic penalty in the proximal operator with a hard ball constraint.
A mathematical definition with no external falsifiable handle such as a measurable particle or conserved quantity.
Ball envelope N^t_f
purpose: Associate a smoothed envelope to f, analogous to the Moreau envelope, and reinterpret BPM as normalized gradient descent on it.
It is the infimal convolution of f with the indicator of a ball; a definition rather than an independently verified entity.
Bt-convexity and weak Bt-convexity
purpose: Define nonconvex function classes on which global convergence claims are proven.
These assumptions are introduced by the authors and are not validated against independent benchmarks; one toy example in Example 1 shows nonconvexity is possible.

how reviews work

0 comments

Cite this review

Pith. "Pith review of The Ball-Proximal (="Broximal") Point Method: a New Algorithm, Convergence Theory, and Applications." pith.science (2026). https://pith.science/paper/NGSYS47D

@misc{pith2026250202002,
  author       = {Pith},
  title        = {Pith review of: The Ball-Proximal (="Broximal") Point Method: a New Algorithm, Convergence Theory, and Applications},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/NGSYS47D}},
  note         = {Machine review of arXiv:2502.02002}
}

read the original abstract

Non-smooth and non-convex global optimization poses significant challenges across various applications, where standard gradient-based methods often struggle. We propose the Ball-Proximal Point Method, Broximal Point Method, or Ball Point Method (BPM) for short - a novel algorithmic framework inspired by the classical Proximal Point Method (PPM) (Rockafellar, 1976), which, as we show, sheds new light on several foundational optimization paradigms and phenomena, including non-convex and non-smooth optimization, acceleration, smoothing, adaptive stepsize selection, and trust-region methods. At the core of BPM lies the ball-proximal ("broximal") operator, which arises from the classical proximal operator by replacing the quadratic distance penalty by a ball constraint. Surprisingly, and in sharp contrast with the sublinear rate of PPM in the nonsmooth convex regime, we prove that BPM converges linearly and in a finite number of steps in the same regime. Furthermore, by introducing the concept of ball-convexity, we prove that BPM retains the same global convergence guarantees under weaker assumptions, making it a powerful tool for a broader class of potentially non-convex optimization problems. Just like PPM plays the role of a conceptual method inspiring the development of practically efficient algorithms and algorithmic elements, e.g., gradient descent, adaptive step sizes, acceleration (Ahn & Sra, 2020), and "W" in AdamW (Zhuang et al., 2022), we believe that BPM should be understood in the same manner: as a blueprint and inspiration for further development.

Figures

Figures reproduced from arXiv: 2502.02002 by the authors.

**Figure 1.** Behavior of BPM on a piecewise linear nonconvex function. The dark blue line represents the function f, while the crimson line illustrates the iterates of BPM. The algorithm is tested for t ∈ {1, 2, 2.5, 3}, starting at x0 = −4. New approach to nonconvex optimization. Recent research has made significant progress in nonconvex optimization, providing theoretical guarantees for convergence to stationary points and,… view at source ↗

**Figure 2.** Visualization of BPM applied to the Six-Hump Camel function, starting from the initial point (−1.9, 0), with step sizes t ∈ {0.3, 1.2}. B. Numerical Experiments To validate the theoretical findings and further illustrate the mechanism of BPM, we conduct numerical experiments on a simple optimization problem. Specifically, we consider the minimization of the well-known Six-Hump Camel function (Molga & Smutnicki, 2005… view at source ↗

**Figure 3.** Number of runs of BPM (out of 1000) that reached a global minimum for t ∈ {0.2, 0.5, 1, 1.5, 2}. 17 [PITH_FULL_IMAGE:figures/full_fig_p017_3.png] view at source ↗

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

83 extracted references · 55 canonical work pages

[1]

write newline

" write newline "" before.all 'output.state := FUNCTION n.dashify 't := "" t empty not t #1 #1 substring "-" = t #1 #2 substring "--" = not "--" * t #2 global.max substring 't := t #1 #1 substring "-" = "-" * t #2 global.max substring 't := while if t #1 #1 substring * t #2 global.max substring 't := if while FUNCTION format.date year duplicate empty "emp...
[2]

Convex optimization with p -norm oracles

Adil, D., Bullins, B., Jambulapati, A., and Sidford, A. Convex optimization with p -norm oracles. arXiv preprint arXiv:2410.24158, 2024

arXiv 2024
[3]

Understanding Nesterov's Acceleration via Proximal Point Method

Ahn , K. and Sra , S. Understanding N esterov's Acceleration via Proximal Point Method . arXiv e-prints, 2020. doi:10.48550/arXiv.2005.08304

work page Pith review arXiv doi:10.48550/arxiv.2005.08304 2020
[4]

QSGD : Communication-efficient SGD via gradient quantization and encoding

Alistarh, D., Grubic, D., Li, J., Tomioka, R., and Vojnovic, M. QSGD : Communication-efficient SGD via gradient quantization and encoding. Advances in Neural Information Processing Systems, 30, 2017

2017
[5]

A convergence theory for deep learning via over-parameterization

Allen-Zhu, Z., Li, Y., and Song, Z. A convergence theory for deep learning via over-parameterization. In International conference on machine learning, pp.\ 242--252. PMLR, 2019

2019
[6]

Tighter performance theory of F ed E x P rox

Anyszka, W., Gruntkowska, K., Tyurin, A., and Richt \'a rik, P. Tighter performance theory of F ed E x P rox. arXiv preprint arXiv:2410.15368, 2024

arXiv 2024
[7]

Stochastic bias-reduced gradient methods

Asi, H., Carmon, Y., Jambulapati, A., Jin, Y., and Sidford, A. Stochastic bias-reduced gradient methods. Advances in Neural Information Processing Systems, 34: 0 10810--10822, 2021

work page 2021
[8]

and Levy, K

Bach, F. and Levy, K. Y. A universal algorithm for variational inequalities adaptive to smoothness and noise. In Conference on learning theory, pp.\ 164--194. PMLR, 2019

work page 2019

Show all 83 references

[9]

H., Combettes, P

Bauschke, H. H., Combettes, P. L., et al. Convex analysis and monotone operator theory in Hilbert spaces, volume 408. Springer, 2011

2011
[10]

First-order methods in optimization

Beck, A. First-order methods in optimization. SIAM, 2017

2017
[11]

and Teboulle, M

Beck, A. and Teboulle, M. Smoothing and first order methods: A unified framework. SIAM J. Optim., 22: 0 557--580, 2012

2012
[12]

Bertsekas, D. P. Incremental proximal methods for large scale convex optimization. Mathematical Programming, 129 0 (2): 0 163--195, 2011

2011
[13]

Bubeck, S. et al. Convex optimization: Algorithms and complexity. Foundations and Trends in Machine Learning , 8 0 (3-4): 0 231--357, 2015

2015
[14]

T., Sidford, A., and Tian, K

Carmon, Y., Jambulapati, A., Jiang, Q., Jin, Y., Lee, Y. T., Sidford, A., and Tian, K. Acceleration with a ball optimization oracle. Advances in Neural Information Processing Systems, 33: 0 19052--19063, 2020

2020
[15]

Thinking inside the ball: Near-optimal minimization of the maximal loss

Carmon, Y., Jambulapati, A., Jin, Y., and Sidford, A. Thinking inside the ball: Near-optimal minimization of the maximal loss. In Conference on Learning Theory, pp.\ 866--882. PMLR, 2021

2021
[16]

Optimal and adaptive monteiro-svaiter acceleration

Carmon, Y., Hausler, D., Jambulapati, A., Jin, Y., and Sidford, A. Optimal and adaptive monteiro-svaiter acceleration. Advances in Neural Information Processing Systems, 35: 0 20338--20350, 2022

2022
[17]

T., Liu, D., Sidford, A., and Tian, K

Carmon, Y., Jambulapati, A., Jin, Y., Lee, Y. T., Liu, D., Sidford, A., and Tian, K. Resqueing parallel and private stochastic convex optimization. In 2023 IEEE 64th Annual Symposium on Foundations of Computer Science (FOCS), pp.\ 2031--2058. IEEE, 2023

2023
[18]

R., Gould, N

Conn, A. R., Gould, N. I. M., and Toint, P. L. Trust Region Methods. Society for Industrial and Applied Mathematics, 2000. doi:10.1137/1.9780898719857

doi
[19]

Recent theoretical advances in non-convex optimization

Danilova, M., Dvurechensky, P., Gasnikov, A., Gorbunov, E., Guminov, S., Kamzolov, D., and Shibaev, I. Recent theoretical advances in non-convex optimization. In High-Dimensional Optimization and Probability: With a View Towards Data Science, pp.\ 79--163. Springer, 2022

2022
[20]

N., Pascanu, R., Gulcehre, C., Cho, K., Ganguli, S., and Bengio, Y

Dauphin, Y. N., Pascanu, R., Gulcehre, C., Cho, K., Ganguli, S., and Bengio, Y. Identifying and attacking the saddle point problem in high-dimensional non-convex optimization. Advances in neural information processing systems, 27, 2014

2014
[21]

T., Tran, N

Dinh, C. T., Tran, N. H., and Nguyen, T. D. Personalized federated learning with moreau envelopes. Advances in Neural Information Processing Systems, 33: 0 21394--21405, 2020

2020
[22]

Porcupine neural networks: (almost) all local optima are global

Feizi, S., Javadi, H., Zhang, J., and Tse, D. Porcupine neural networks: (almost) all local optima are global. arXiv preprint arXiv:1710.02196, 2017

2017 arXiv
[23]

Sharpness-aware minimization for efficiently improving generalization

Foret, P., Kleiner, A., Mobahi, H., and Neyshabur, B. Sharpness-aware minimization for efficiently improving generalization. In International Conference on Learning Representations, 2021

2021
[24]

and Gower, R

Garrigos, G. and Gower, R. M. Handbook of convergence theorems for (stochastic) gradient methods. arXiv preprint arXiv:2301.11235, 2023

2023 arXiv
[25]

No spurious local minima in nonconvex low rank problems: A unified geometric analysis

Ge, R., Jin, C., and Zheng, Y. No spurious local minima in nonconvex low rank problems: A unified geometric analysis. In International Conference on Machine Learning, pp.\ 1233--1242. PMLR, 2017

2017
[26]

P., Li, Z., and Richt \'a rik, P

Gorbunov, E., Burlachenko, K. P., Li, Z., and Richt \'a rik, P. MARINA : Faster non-convex distributed learning with compression. In International Conference on Machine Learning, pp.\ 3788--3798. PMLR, 2021

2021
[27]

M., Schmidt, M., Bach, F., and Richt \'a rik, P

Gower, R. M., Schmidt, M., Bach, F., and Richt \'a rik, P. Variance-reduced methods for machine learning. Proceedings of the IEEE, 108 0 (11): 0 1968--1983, 2020

1968
[28]

EF21-P and friends: Improved theoretical communication complexity for distributed optimization with bidirectional compression

Gruntkowska, K., Tyurin, A., and Richt \'a rik, P. EF21-P and friends: Improved theoretical communication complexity for distributed optimization with bidirectional compression. In International Conference on Machine Learning, pp.\ 11761--11807. PMLR, 2023

2023
[29]

On the convergence of the proximal point algorithm for convex minimization

G\" u ler, O. On the convergence of the proximal point algorithm for convex minimization. SIAM Journal on Control and Optimization, 29 0 (2): 0 403--419, 1991. doi:10.1137/0329022

1991 doi
[30]

Haeffele, B. D. and Vidal, R. Global optimality in neural network training. 2017 IEEE Conference on Computer Vision and Pattern Recognition (CVPR), pp.\ 4390--4398, 2017

2017
[31]

Gradient descent learns linear dynamical systems

Hardt, M., Ma, T., and Recht, B. Gradient descent learns linear dynamical systems. Journal of Machine Learning Research, 19 0 (29): 0 1--44, 2018

2018
[32]

Beyond convexity: Stochastic quasi-convex optimization

Hazan, E., Levy, K., and Shalev-Shwartz, S. Beyond convexity: Stochastic quasi-convex optimization. Advances in neural information processing systems, 28, 2015

2015
[33]

Hinder, O., Sidford, A., and Sohoni, N. S. Near-optimal methods for minimizing star-convex functions and beyond. arXiv preprint arXiv:1906.11985, 2019

1906 arXiv
[34]

Adaptive learning rates for faster stochastic gradient methods

Horv \'a th, S., Mishchenko, K., and Richt \'a rik, P. Adaptive learning rates for faster stochastic gradient methods. arXiv preprint arXiv:2208.05287, 2022

2022 arXiv
[35]

Closing the computational-query depth gap in parallel stochastic convex optimization

Jambulapati, A., Sidford, A., and Tian, K. Closing the computational-query depth gap in parallel stochastic convex optimization. In The Thirty Seventh Annual Conference on Learning Theory, pp.\ 2608--2643. PMLR, 2024

2024
[36]

M., and Jordan, M

Jin, C., Netrapalli, P., Ge, R., Kakade, S. M., and Jordan, M. I. On nonconvex optimization for machine learning: Gradients, stochasticity, and saddle points. J. ACM, 68 0 (2), February 2021. ISSN 0004-5411. doi:10.1145/3418526

2021 doi
[37]

and Zhang, T

Johnson, R. and Zhang, T. Accelerating stochastic gradient descent using predictive variance reduction. Advances in neural information processing systems, 26, 2013

2013
[38]

Linear convergence of gradient and proximal-gradient methods under the P olyak- ojasiewicz condition

Karimi, H., Nutini, J., and Schmidt, M. Linear convergence of gradient and proximal-gradient methods under the P olyak- ojasiewicz condition. In Machine Learning and Knowledge Discovery in Databases: European Conference, ECML PKDD 2016, Riva del Garda, Italy, September 19-23, ...

2016
[39]

and Jin, C

Khaled, A. and Jin, C. Faster federated optimization under second-order similarity. arXiv preprint arXiv:2209.02257, 2022

2022 arXiv
[40]

R., and Johansson, M

Khirirat, S., Feyzmahdavian, H. R., and Johansson, M. Distributed learning with compressed gradients. arXiv preprint arXiv:1806.06573, 2018

2018 arXiv
[41]

Kiwiel, K. C. Convergence and efficiency of subgradient methods for quasiconvex minimization. Mathematical programming, 90: 0 1--25, 2001

2001
[42]

An alternative view: When does SGD escape local minima? In International conference on machine learning, pp.\ 2698--2707

Kleinberg, B., Li, Y., and Yuan, Y. An alternative view: When does SGD escape local minima? In International conference on machine learning, pp.\ 2698--2707. PMLR, 2018

2018
[43]

Kloeden, P. E. and Platen, E. Numerical Solution of Stochastic Differential Equations. Springer Berlin, Heidelberg, 1992

1992
[44]

A method for the solution of certain non-linear problems in least squares

Levenberg, K. A method for the solution of certain non-linear problems in least squares. Quarterly of Applied Mathematics, 2 0 (2): 0 164--168, 1944

1944
[45]

and Richt \'a rik, P

Li, H. and Richt \'a rik, P. On the convergence of F ed P rox with extrapolation and inexact prox. In OPT 2024: Optimization for Machine Learning, 2024

2024
[46]

Variance reduced distributed non-convex optimization using matrix stepsizes

Li, H., Karagulyan, A., and Richt \'a rik, P. Variance reduced distributed non-convex optimization using matrix stepsizes. arXiv preprint arXiv:2310.04614, 2023

2023 arXiv
[47]

The power of extrapolation in federated learning

Li, H., Acharya, K., and Richtarik, P. The power of extrapolation in federated learning. arXiv preprint arXiv:2405.13766, 2024 a

2024 arXiv
[48]

Det-CGD : Compressed gradient descent with matrix stepsizes for non-convex optimization

Li, H., Karagulyan, A., and Richt \'a rik, P. Det-CGD : Compressed gradient descent with matrix stepsizes for non-convex optimization. In International Conference on Learning Representations, 2024 b

2024
[49]

An improved analysis of stochastic gradient descent with momentum

Liu, Y., Gao, Y., and Yin, W. An improved analysis of stochastic gradient descent with momentum. Advances in Neural Information Processing Systems, 33: 0 18261--18271, 2020

2020
[50]

and Richt \'a rik, P

Loizou, N. and Richt \'a rik, P. Linearly convergent stochastic heavy ball method for minimizing generalization error. arXiv preprint arXiv:1710.10737, 2017

2017 arXiv
[51]

and Mishchenko, K

Malitsky, Y. and Mishchenko, K. Adaptive gradient descent without descent. arXiv preprint arXiv:1910.09529, 2019

1910 arXiv
[52]

Marquardt, D. W. An algorithm for least-squares estimation of nonlinear parameters. Journal of the society for Industrial and Applied Mathematics, 11 0 (2): 0 431--441, 1963

1963
[53]

R \'e gularisation d'in \'e quations variationnelles par approximations successives

Martinet, P. R \'e gularisation d'in \'e quations variationnelles par approximations successives. Revue Française d’informatique et de recherche op \'e rationnelle , 1970

1970
[54]

Convergence of first-order algorithms for meta-learning with M oreau envelopes

Mishchenko, K., Hanzely, S., and Richt \'a rik, P. Convergence of first-order algorithms for meta-learning with M oreau envelopes. arXiv preprint arXiv:2301.06806, 2023

2023 arXiv
[55]

and Smutnicki, C

Molga, M. and Smutnicki, C. Test functions for optimization needs. Test functions for optimization needs, 101: 0 48, 2005

2005
[56]

Monteiro, R. D. C. and Svaiter, B. F. An accelerated hybrid proximal extragradient method for convex optimization and its implications to second-order methods. SIAM Journal on Optimization, 23 0 (2): 0 1092--1125, 2013. doi:10.1137/110833786

2013 doi
[57]

Proximit \'e et dualit \'e dans un espace H ilbertien

Moreau, J.-J. Proximit \'e et dualit \'e dans un espace H ilbertien. Bulletin de la Soci \'e t \'e Math \'e matique de France , 93: 0 273--299, 1965

1965
[58]

Revisiting normalized gradient descent: Fast evasion of saddle points

Murray, R., Swenson, B., and Kar, S. Revisiting normalized gradient descent: Fast evasion of saddle points. IEEE Transactions on Automatic Control, 64 0 (11): 0 4818--4824, 2019

2019
[59]

Murty, K. G. and Kabadi, S. N. Some NP -complete problems in quadratic and nonlinear programming. Mathematical Programming, 39: 0 117--129, 1987

1987
[60]

and Nesterov, Y

Nemirovski, A. and Nesterov, Y. Optimal methods of smooth convex minimization. USSR Computational Mathematics and Mathematical Physics, 25 0 (2): 0 21--30, 1985. ISSN 0041-5553

1985
[61]

and Yudin, D

Nemirovski, A. and Yudin, D. Problem Complexity and Method Efficiency in Optimization. Wiley, 1983

1983
[62]

Introductory lectures on convex optimization: A basic course, volume 87

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

2003
[63]

Inexact accelerated high-order proximal-point methods

Nesterov, Y. Inexact accelerated high-order proximal-point methods. Mathematical Programming, 197 0 (1): 0 1--26, 2023

2023
[64]

Nesterov, Y. E. Minimization methods for nonsmooth convex and quasiconvex functions. Matekon, 29 0 (3): 0 519--531, 1984

1984
[65]

and Wright, S

Nocedal, J. and Wright, S. Numerical optimization, pp.\ 1--664. Springer Series in Operations Research and Financial Engineering. Springer Nature, 2006

2006
[66]

and Boyd, S

Parikh, N. and Boyd, S. Proximal algorithms. Found. Trends Optim., 1 0 (3): 0 127–239, January 2014. ISSN 2167-3888. doi:10.1561/2400000003

2014 doi
[67]

and Wang, X

Planiden, C. and Wang, X. Strongly convex functions, M oreau envelopes, and the generic nature of convex functions with strong minimizers. SIAM Journal on Optimization, 26 0 (2): 0 1341--1364, 2016

2016
[68]

and Wang, X

Planiden, C. and Wang, X. Proximal mappings and M oreau envelopes of single-variable convex piecewise cubic functions and multivariable gauge functions. Nonsmooth Optimization and Its Applications, pp.\ 89--130, 2019

2019
[69]

Polyak, B. T. Introduction to optimization. New York, Optimization Software, 1987

1987
[70]

EF21 : A new, simpler, theoretically better, and practically faster error feedback

Richt \'a rik, P., Sokolov, I., and Fatkhullin, I. EF21 : A new, simpler, theoretically better, and practically faster error feedback. Advances in Neural Information Processing Systems, 34: 0 4384--4396, 2021

2021
[71]

A unified theory of stochastic proximal point methods without smoothness

Richt \'a rik, P., Sadiev, A., and Demidovich, Y. A unified theory of stochastic proximal point methods without smoothness. arXiv preprint arXiv:2405.15941, 2024

2024 arXiv
[72]

and Monro, S

Robbins, H. and Monro, S. A stochastic approximation method. The Annals of Mathematical Statistics, pp.\ 400--407, 1951

1951
[73]

Rockafellar, R. T. Monotone operators and the proximal point algorithm. SIAM Journal on Control and Optimization, 14 0 (5): 0 877--898, 1976

1976
[74]

Ryu, E. K. and Boyd, S. Stochastic proximal iteration: a non-asymptotic improvement upon stochastic gradient descent. Technical report, 2016

2016
[75]

and Zhang, T

Shamir, O. and Zhang, T. Stochastic gradient descent for non-smooth optimization: Convergence results and optimal averaging schemes. In International Conference on Machine Learning, pp.\ 71--79. PMLR, 2013

2013
[76]

Effects of depth, width, and initialization: A convergence analysis of layer-wise training for deep linear neural networks

Shin, Y. Effects of depth, width, and initialization: A convergence analysis of layer-wise training for deep linear neural networks. Analysis and Applications, 20 0 (01): 0 73--119, 2022

2022
[77]

and Richt \'a rik, P

Tyurin, A. and Richt \'a rik, P. DASHA : Distributed nonconvex optimization with communication compression and optimal oracle complexity. In International Conference on Learning Representations, 2024

2024
[78]

Adversarial flows: A gradient flow characterization of adversarial attacks

Weigand, L., Roith, T., and Burger, M. Adversarial flows: A gradient flow characterization of adversarial attacks. arXiv preprint arXiv:2406.05376, 2024

2024
[79]

and Ma, L

Yang, Z. and Ma, L. Adaptive step size rules for stochastic optimization in large-scale learning. Statistics and Computing, 33, 02 2023. doi:10.1007/s11222-023-10218-2

2023 doi
[80]

Why gradient clipping accelerates training: A theoretical justification for adaptivity

Zhang, J., He, T., Sra, S., and Jadbabaie, A. Why gradient clipping accelerates training: A theoretical justification for adaptivity. arXiv preprint arXiv:1905.11881, 2019

1905 arXiv
[81]

Toward understanding the importance of noise in training neural networks

Zhou, M., Liu, T., Li, Y., Lin, D., Zhou, E., and Zhao, T. Toward understanding the importance of noise in training neural networks. In International Conference on Machine Learning, pp.\ 7594--7602. PMLR, 2019 a

2019
[82]

SGD converges to global minimum in deep learning via star-convex path

Zhou, Y., Yang, J., Zhang, H., Liang, Y., and Tarokh, V. SGD converges to global minimum in deep learning via star-convex path. arXiv preprint arXiv:1901.00451, 2019 b

1901 arXiv
[83]

Understanding A dam W through proximal methods and scale-freeness

Zhuang, Z., Liu, M., Cutkosky, A., and Orabona, F. Understanding A dam W through proximal methods and scale-freeness. Transactions on Machine Learning Research, 2022

2022

Pith tools

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

[1] [1]

write newline

" write newline "" before.all 'output.state := FUNCTION n.dashify 't := "" t empty not t #1 #1 substring "-" = t #1 #2 substring "--" = not "--" * t #2 global.max substring 't := t #1 #1 substring "-" = "-" * t #2 global.max substring 't := while if t #1 #1 substring * t #2 global.max substring 't := if while FUNCTION format.date year duplicate empty "emp...

[2] [2]

Convex optimization with p -norm oracles

Adil, D., Bullins, B., Jambulapati, A., and Sidford, A. Convex optimization with p -norm oracles. arXiv preprint arXiv:2410.24158, 2024

arXiv 2024

[3] [3]

Understanding Nesterov's Acceleration via Proximal Point Method

Ahn , K. and Sra , S. Understanding N esterov's Acceleration via Proximal Point Method . arXiv e-prints, 2020. doi:10.48550/arXiv.2005.08304

work page Pith review arXiv doi:10.48550/arxiv.2005.08304 2020

[4] [4]

QSGD : Communication-efficient SGD via gradient quantization and encoding

Alistarh, D., Grubic, D., Li, J., Tomioka, R., and Vojnovic, M. QSGD : Communication-efficient SGD via gradient quantization and encoding. Advances in Neural Information Processing Systems, 30, 2017

2017

[5] [5]

A convergence theory for deep learning via over-parameterization

Allen-Zhu, Z., Li, Y., and Song, Z. A convergence theory for deep learning via over-parameterization. In International conference on machine learning, pp.\ 242--252. PMLR, 2019

2019

[6] [6]

Tighter performance theory of F ed E x P rox

Anyszka, W., Gruntkowska, K., Tyurin, A., and Richt \'a rik, P. Tighter performance theory of F ed E x P rox. arXiv preprint arXiv:2410.15368, 2024

arXiv 2024

[7] [7]

Stochastic bias-reduced gradient methods

Asi, H., Carmon, Y., Jambulapati, A., Jin, Y., and Sidford, A. Stochastic bias-reduced gradient methods. Advances in Neural Information Processing Systems, 34: 0 10810--10822, 2021

work page 2021

[8] [8]

and Levy, K

Bach, F. and Levy, K. Y. A universal algorithm for variational inequalities adaptive to smoothness and noise. In Conference on learning theory, pp.\ 164--194. PMLR, 2019

work page 2019