pith. sign in

arxiv: 2509.04375 · v2 · submitted 2025-09-04 · 🧮 math.OC

Extending Linear Convergence of the Proximal Point Algorithm: The Quasar-Convex Case

Jos\'e de Brito , Felipe Lara , Di Liu This is my paper

Pith reviewed 2026-05-18 18:53 UTC · model grok-4.3

classification 🧮 math.OC
keywords proximal point algorithmquasar-convex functionsconvergence rateslinear convergenceproximity operatorstar-convex functionsoptimizationcomplexity analysis
0
0 comments X

The pith

The proximal point algorithm generates a minimizing sequence with O(ε^{-1}) rate for quasar-convex functions and linear convergence under strong quasar-convexity.

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

The paper shows that the proximal point algorithm works beyond convex functions by establishing convergence properties for quasar-convex objectives. For quasar-convex functions the generated sequence reaches an ε-accurate point after O(ε^{-1}) steps while remaining minimizing. Under the stronger assumption of strong quasar-convexity the same algorithm converges linearly and requires only O(ln(ε^{-1})) iterations to reach ε accuracy. These rates replicate the classical convex and strongly convex guarantees but now apply to a wider family of functions that need not be convex. The proofs rest on verifying that the proximity operator of a quasar-convex function inherits the key monotonicity-type inequalities used in the convex case.

Core claim

This work investigates the properties of the proximity operator for quasar-convex functions and establishes the convergence of the proximal point algorithm to a global minimizer with a particular focus on its convergence rate. In particular, we demonstrate: (i) the generated sequence is minimizing and achieves an O(ε^{-1}) complexity rate for quasar-convex functions; (ii) under strong quasar-convexity, the sequence converges linearly and attains an O(ln(ε^{-1})) complexity rate. These results extend known convergence rates from the (strongly) convex to the (strongly) quasar-convex setting.

What carries the argument

The proximity operator of a quasar-convex function, which satisfies the monotonicity-type inequalities required to extend the standard convex convergence arguments of the proximal point method.

If this is right

  • The proximal point sequence converges to a global minimizer for any quasar-convex objective.
  • An O(ε^{-1}) iteration bound holds for reaching an ε-minimizer when the objective is quasar-convex.
  • Under strong quasar-convexity the iterates converge linearly to the minimizer.
  • The iteration complexity improves to O(ln(ε^{-1})) when strong quasar-convexity holds.
  • The same rates apply to the special case of star-convex functions, some of which appear novel even in that setting.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • Quasar-convexity offers a practical modeling assumption for certain non-convex problems that still admit global minimization via proximal methods.
  • Similar rate extensions may hold for other proximal-type algorithms when applied to quasar-convex objectives.
  • The numerical experiments indicate that the predicted rates are observable on concrete quasar-convex instances.
  • The framework could guide analysis of first-order methods on loss landscapes that satisfy quasar-convexity but violate convexity.

Load-bearing premise

The proximity operator of a quasar-convex function satisfies the key inequalities needed to carry over the standard convex convergence arguments.

What would settle it

A concrete quasar-convex function for which the proximal point iterates either fail to approach the global minimizer or require more than O(ε^{-1}) steps to reach ε accuracy.

Figures

Figures reproduced from arXiv: 2509.04375 by Di Liu, Felipe Lara, Jos\'e de Brito.

Figure 1
Figure 1. Figure 1: An illustration of the quasar-convex function [PITH_FULL_IMAGE:figures/full_fig_p020_1.png] view at source ↗
Figure 2
Figure 2. Figure 2: Convergence of function value sequence and the norm of iterates over [PITH_FULL_IMAGE:figures/full_fig_p022_2.png] view at source ↗
Figure 3
Figure 3. Figure 3: Convergence of function value sequence and the norm of iterates over [PITH_FULL_IMAGE:figures/full_fig_p022_3.png] view at source ↗
read the original abstract

This work investigates the properties of the proximity operator for quasar-convex functions and establishes the convergence of the proximal point algorithm to a global minimizer with a particular focus on its convergence rate. In particular, we demonstrate: (i) the generated sequence is mi\-ni\-mi\-zing and achieves an $\mathcal{O}(\varepsilon^{-1})$ complexity rate for quasar-convex functions; (ii) under strong quasar-convexity, the sequence converges linearly and attains an $\mathcal{O}(\ln(\varepsilon^{-1}))$ complexity rate. These results extend known convergence rates from the (strongly) convex to the (strongly) quasar-convex setting. To the best of our knowledge, some findings are novel even for the special case of (strongly) star-convex functions. Numerical experiments corroborate our theoretical results.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

0 major / 3 minor

Summary. The paper investigates properties of the proximity operator for quasar-convex functions and establishes convergence rates for the proximal point algorithm. It shows that the generated sequence is minimizing and achieves an O(ε^{-1}) complexity rate for quasar-convex functions; under strong quasar-convexity the sequence converges linearly with O(ln(ε^{-1})) complexity. These extend known convex rates to the quasar-convex setting, with some results novel even for star-convex functions. Numerical experiments are included to corroborate the theory.

Significance. If the derivations hold, the work meaningfully extends the applicability of proximal-point methods to a wider class of non-convex problems that includes star-convex functions. Credit is due for the explicit construction of the quasar-convex analogue of the subdifferential inequality (Section 3) and the uniform treatment that avoids circularity or post-hoc parameter fitting, yielding clean, falsifiable rates.

minor comments (3)
  1. [Abstract] Abstract: the phrase 'some findings are novel even for the special case of (strongly) star-convex functions' is left unspecified; a brief parenthetical identifying the novel statements would improve readability.
  2. [Section 3] Section 3: the key proximal inequality is derived cleanly, but a short remark comparing the quasar parameter μ=1 case directly to the classical convex subdifferential inequality would help readers verify the reduction.
  3. Notation: the symbol for the quasar-convexity parameter is introduced without an explicit forward reference to its range; adding 'μ ∈ (0,1]' at first use would prevent minor confusion.

Simulated Author's Rebuttal

0 responses · 0 unresolved

We thank the referee for their positive summary of our work on the proximal point algorithm for quasar-convex functions and for recommending minor revision. The assessment that the results extend convex rates and include novel aspects even for star-convex functions is appreciated. As the report lists no specific major comments, we have no point-by-point rebuttals to provide.

Circularity Check

0 steps flagged

No significant circularity detected

full rationale

The paper establishes the required proximal inequalities for quasar-convex functions directly from the function definition in Section 3, then carries over the standard convex distance-decrease argument for the proximal point algorithm without any reduction to fitted inputs, self-citations, or ansatzes. The O(ε^{-1}) and linear rates follow from these explicit derivations rather than by construction from prior results or data fits. The analysis for the star-convex special case is handled uniformly within the same framework, rendering the derivation self-contained against external benchmarks.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

The central claims rest on the structural properties of quasar-convex functions and the well-definedness of their proximity operators; these are treated as domain assumptions rather than derived.

axioms (1)
  • domain assumption Quasar-convex functions admit a proximity operator whose iterates remain minimizing and satisfy the stated complexity bounds.
    This property is invoked to transfer convex convergence arguments to the quasar-convex setting.

pith-pipeline@v0.9.0 · 5672 in / 1123 out tokens · 36393 ms · 2026-05-18T18:53:52.860242+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Lean theorems connected to this paper

Citations machine-checked in the Pith Canon. Every link opens the source theorem in the public Lean library.

What do these tags mean?
matches
The paper's claim is directly supported by a theorem in the formal canon.
supports
The theorem supports part of the paper's argument, but the paper may add assumptions or extra steps.
extends
The paper goes beyond the formal theorem; the theorem is a base layer rather than the whole result.
uses
The paper appears to rely on the theorem as machinery.
contradicts
The paper's claim conflicts with a theorem or certificate in the canon.
unclear
Pith found a possible connection, but the passage is too broad, indirect, or ambiguous to say the theorem truly supports the claim.

Forward citations

Cited by 2 Pith papers

Reviewed papers in the Pith corpus that reference this work. Sorted by Pith novelty score.

  1. Quasar-Convex Optimization: Fundamental Properties and High-Order Proximal-Point Methods

    math.OC 2026-04 unverdicted novelty 7.0

    Quasar-convex functions admit high-order proximal algorithms with linear convergence for p=2 and superlinear for p>2 under suitable conditions.

  2. Robust Learning Meets Quasar-Convex Optimization: Inexact High-Order Proximal-Point Methods

    math.OC 2026-05 unverdicted novelty 5.0

    Robust learning problems are formulated as quasar-convex optimization, and HiPPA is proposed as an inexact high-order proximal method with global and superlinear convergence guarantees.

Reference graph

Works this paper leans on

53 extracted references · 53 canonical work pages · cited by 2 Pith papers

  1. [1]

    Ahookhosh, A

    M. Ahookhosh, A. Iusem, A. Kabgani, F. Lara , Asymptotic conver- gence analysis of high-order proximal-point methods beyond sublinear rates, arXiv: 2505.20484v1 , (2025)

    work page arXiv 2025

  2. [2]

    N.T. An, N.M. Nam , Convergence analysis of a proximal point algorithm for minimizing differences of functions, Optimization, 66, 129–147, (2017)

    work page 2017

  3. [3]

    Arrow, B.H

    K.J. Arrow, B.H. Chenery, B.S. Minhas, R.M. Solow, Capital-labor substitution and economic efficiency, Review Econ. Stat. , 43(3), 225–250, (1961)

    work page 1961

  4. [4]

    Attouch, J

    H. Attouch, J. Bolte, B.F. Svaiter , Convergence of descent me- thods for semi-algebraic and tame problems: proximal algorithms, forward– backward splitting, and regularized Gauss–Seidel methods. Math. Program. 137, 91–129, (2013)

    work page 2013

  5. [5]

    Asymptotic Cones and Functions in Opti- mization and Variational Inequalities

    A. Auslender, M. Teboulle. “Asymptotic Cones and Functions in Opti- mization and Variational Inequalities”. Springer-Verlag, New York, (2003)

    work page 2003

  6. [6]

    Generalized Con- cavity

    M. Avriel, W.E. Diewert, S. Schaible, I. Zang . “Generalized Con- cavity”. SIAM, Classics in Applied Mathematics, Philadelphia, (2010)

    work page 2010

  7. [7]

    Banert, R.I

    S. Banert, R.I. Bot ¸, A general double-proximal gradient algorithm for d.c. programming, Math. Programm., 178, 301–326, (2019)

    work page 2019

  8. [8]

    Convex Analysis and Monotone Ope- rators Theory in Hilbert Spaces

    H.H. Bauschke, P.L. Combettes. “Convex Analysis and Monotone Ope- rators Theory in Hilbert Spaces”. CMS Books in Mathematics . Springer- Verlag, second edition, (2017)

    work page 2017

  9. [9]

    Generalized Convexity and Optimization

    A. Cambini, L. Martein . “Generalized Convexity and Optimization”. Springer-Verlag, Berlin-Heidelberg, (2009)

    work page 2009

  10. [10]

    Z. Chen, Y. Lu, H. Wang, Y. Liu, T. Li, Quantum Langevin dynamics for optimization, Commun. Math. Phys. , 406, 52, (2025)

    work page 2025

  11. [11]

    Optimization and Nonsmooth Analysis

    F.H. Clarke . “Optimization and Nonsmooth Analysis”. SIAM, New York, (1990). 23

    work page 1990

  12. [12]

    Cobb, P.H

    C.W. Cobb, P.H. Douglas, A theory of production, American Economic Review, 18, 139–165, (1928)

    work page 1928

  13. [13]

    Combettes, T

    P.L. Combettes, T. Pennanen, Proximal methods for cohypomonotone operators, SIAM J. Control Optim. , 43, 731–742, (2004)

    work page 2004

  14. [14]

    Theory of Value

    G. Debreu. “Theory of Value”. New York: John Wiley, (1959)

    work page 1959

  15. [15]

    S.-M. Grad, F. Lara, Solving mixed variational inequalities beyond con- vexity. J. Optim. Theory Appl. , 190, 565–580, (2021)

    work page 2021

  16. [16]

    S.-M. Grad, F. Lara , An extension of the proximal point algorithm beyond convexity, J. Global Optim. , 82, 313–329, (2022)

    work page 2022

  17. [17]

    S.-M. Grad, F. Lara, R.T. Marcavillaca , Relaxed-inertial proximal point type algorithms for quasiconvex minimization, J. Global Optim. , 85, 615–635, (2023)

    work page 2023

  18. [18]

    S.-M. Grad, F. Lara, R.T. Marcavillaca, Strongly quasiconvex func- tions: what we know (so far), J. Optim. Theory Appl., 205, paper 38, (2025)

    work page 2025

  19. [19]

    G¨uler, On the convergence of the proximal point algorithm for convex minimization, SIAM J

    O. G¨uler, On the convergence of the proximal point algorithm for convex minimization, SIAM J. Control Optim. , 29(2), 403–419, (1991)

    work page 1991

  20. [20]

    Guminov, A

    S. Guminov, A. Gasnikov, I. Kuruzov , Accelerated methods for weakly-quasi-convex optimization problems, Comput. Manag. Sci. 20, Arti- cle number: 36, (2023)

    work page 2023

  21. [21]

    Handbook of Generalized Convexity and Generalized Monotonicity

    N. Hadjisavvas, S. Komlosi, S. Schaible . “Handbook of Generalized Convexity and Generalized Monotonicity”. Springer-Verlag, Boston, (2005)

    work page 2005

  22. [22]

    Hadjisavvas, F

    N. Hadjisavvas, F. Lara, R.T. Marcavillaca, P.T. Vuong , Heavy ball and Nesterov accelerations with Hessian-driven damping for nonconvex optimization, arXiv: 2506.15632 , (2025)

    work page arXiv 2025

  23. [23]

    Hardt, T

    M. Hardt, T. Ma, B. Recht , Gradient descent learns linear dynamical systems, J. Mach. Learning Res. , 19, 1–44, (2018)

    work page 2018

  24. [24]

    Hermant, J.-F

    J. Hermant, J.-F. Aujol, C. Dossal, A. Rondepierre , Study of the behaviour of Nesterov accelerated gradient in a non convex setting: the strongly quasar convex case, hal-04589853, (2024)

    work page 2024

  25. [25]

    Hinder, A

    O. Hinder, A. Sidford, N. Sohoni , Near-optimal methods for minimi- zing star-convex functions and beyond. Proc. 33th Conf. on Lear. Theory , 125, 1894–1938, (2020)

    work page 1938

  26. [26]

    Iusem, T

    A. Iusem, T. Pennanen, B.F. Svaiter, Inexact variants of the proximal point algorithm without monotonicity, SIAM, J. Optim. , 13, 1080–1097, (2003). 24

    work page 2003

  27. [27]

    Newton-type methods for optimization and variational problems

    A.F. Izmailov, M.V. Solodov. “Newton-type methods for optimization and variational problems”. I Cham: Springer. (2014)

    work page 2014

  28. [28]

    Kabgani, F

    A. Kabgani, F. Lara , Strong subdifferentials: theory and applications in nonconvex optimization, J. Global Optim. , 84, 349–368, (2022)

    work page 2022

  29. [29]

    Knight, W

    K. Knight, W. Fu , Asymptotics for Lasso-type estimators, The Annals of Statistics, 28, 5, 1356–1378, (2000)

    work page 2000

  30. [30]

    Lara, On strongly quasiconvex functions: existence results and proxi- mal point algorithms, J

    F. Lara, On strongly quasiconvex functions: existence results and proxi- mal point algorithms, J. Optim. Theory Appl. , 192, 891–911, (2022)

    work page 2022

  31. [31]

    Lara, R.T

    F. Lara, R.T. Marcavillaca, P.T. Vuong , Characterizations, dy- namical systems and gradient methods for strongly quasiconvex functions, J. Optim. Theory Appl. , 206, article number 60, (2025)

    work page 2025

  32. [32]

    F. Lara, C. Vega , Delayed feedback in online non-convex optimization: a non-stationary approach with applications, arXiv: 2412.14506 , (2024)

    work page arXiv 2024

  33. [33]

    The structure of American economy, 1919-1939: an em- pirical application of equilibrium analysis

    W.W. Leontief. “The structure of American economy, 1919-1939: an em- pirical application of equilibrium analysis”. Cambridge, MA: Harvard Uni- versity Press, (1941)

    work page 1919

  34. [34]

    A. Lowy, J. Ullman, S.J. Wright , How to make the gradients small privately: improved rates for differentially private non-convex optimization, ICML-24, article number 1335, 32904–32923, (2024)

    work page 2024

  35. [35]

    Lu, Iterative reweighted minimization methods forℓp regularized uncon- strained nonlinear programming, Math

    Z. Lu, Iterative reweighted minimization methods forℓp regularized uncon- strained nonlinear programming, Math. Programm., 147, 277–307, (2014)

    work page 2014

  36. [36]

    Martinet, Regularisation d’inequations variationelles par approxima- tions successives, Rev

    B. Martinet, Regularisation d’inequations variationelles par approxima- tions successives, Rev. Francaise Inf. Rech. Oper., 154–159, (1970)

    work page 1970

  37. [37]

    Martinet, Determination approch´ ee d’un point fixe d’une application pseudo-contractante, C.R

    B. Martinet, Determination approch´ ee d’un point fixe d’une application pseudo-contractante, C.R. Acad. Sci. Paris , 274, 163–165, (1972)

    work page 1972

  38. [38]

    Microeconomic The- ory

    A. Mas-Colell, M.D. Whinston, J.R. Green . “Microeconomic The- ory”. Oxford: Oxford University Press, (1995)

    work page 1995

  39. [39]

    McFadden, Constant elasticity of substitution production functions, The Review of Economic Studies, 30, no

    D. McFadden, Constant elasticity of substitution production functions, The Review of Economic Studies, 30, no. 2, pp. 73–83, (1963)

    work page 1963

  40. [40]

    M.N. Nam, J. Sharkansky , On strong quasiconvexity of functions in infinite dimensions, arXiv: 2409.17450 , (2024)

    work page arXiv 2024

  41. [41]

    Necoara, Y

    I. Necoara, Y. Nesterov, F. Glineur, Linear convergence of first order methods for non-strongly convex optimization, Math. Programm., 175, 69– 107, (2019)

    work page 2019

  42. [42]

    Nesterov, B.T

    Y. Nesterov, B.T. Polyak, Cubic regularization of newton method and its global performance, Math. Programm., 108, 177–205, (2006). 25

    work page 2006

  43. [43]

    Pan, J.-S

    S. Pan, J.-S. Chen, Entropy-like proximal algorithms based on a second- order homogeneous distance function for quasi-convex programming, J. Global Optim., 39, 555–575, (2007)

    work page 2007

  44. [44]

    Pennanen , Local convergence of the proximal point algorithm and multiplier methods without monotonicity, Math

    T. Pennanen , Local convergence of the proximal point algorithm and multiplier methods without monotonicity, Math. Oper. Res. , 27, 170–191, (2002)

    work page 2002

  45. [45]

    Polyak , Existence theorems and convergence of minimizing se- quences in extremum problems with restrictions, Soviet Math

    B.T. Polyak , Existence theorems and convergence of minimizing se- quences in extremum problems with restrictions, Soviet Math. , 7, 72–75, (1966)

    work page 1966

  46. [46]

    Rockafellar, Monotone operators and proximal point algorithms, SIAM J

    R.T. Rockafellar, Monotone operators and proximal point algorithms, SIAM J. Control Optim. , 14, 877–898, (1976)

    work page 1976

  47. [47]

    Sun, R.J.B

    W.Y. Sun, R.J.B. Sampaio, M.A.B. Candido , Proximal point algo- rithm for minimization of DC function,J. Comp. Math., 21, 452–462, (2003)

    work page 2003

  48. [48]

    Semismooth Newton methods for variational inequalities and constrained optimization problems in function spaces

    M. Ulbrich . “Semismooth Newton methods for variational inequalities and constrained optimization problems in function spaces”. MOS-SIAM Se- ries on Optimization. (2011)

    work page 2011

  49. [49]

    Vladimirov, Ju.E

    A.A. Vladimirov, Ju.E. Nesterov, Ju.N. Chekanov , O ravnomerno kvazivypuklyh funkcionalah [On uniformly quasiconvex functionals], Vestn. Mosk. un-ta, vycis. mat. i kibern. , 4, 18–27, (1978)

    work page 1978

  50. [50]

    J.-K. Wang, A. Wibisono , Continuized acceleration for quasar convex functions in non-convex optimization, arXiv: 2302.07851 , ICLR, (2023)

    work page arXiv 2023

  51. [51]

    F. Wen, L. Chu, R.C. Qiu , A nonsmooth version of Newton’s method, Math. Programm., 58(1), 353–367, (1993)

    work page 1993

  52. [52]

    F. Wen, L. Chu, R.C. Qiu , A survey on nonconvex regularization-based sparse and low-rank recovery in signal processing, statistics, and machine learning, IEEE Access, 6, 69883–69906, (2018)

    work page 2018

  53. [53]

    Y. Xu, A. Zeevi, Towards optimal problem dependent generalization error bounds in statistical learning theory, Math. Oper. Res., 50, 40–67, (2025). 26

    work page 2025