Extending Linear Convergence of the Proximal Point Algorithm: The Quasar-Convex Case
José de Brito, Felipe Lara, Di Liu · 2025
Read Extending Linear Convergence of the Proximal Point Algorithm: The Quasar-Convex Case by José de Brito, Felipe Lara, Di Liu (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2509-04375.txt.
Introduction
José de Brito and two co-authors extend convergence guarantees for a classic optimization method to a wider family of functions in a 2025 mathematics paper. The proximal point algorithm inches toward a minimum by repeatedly solving nearby easier problems. Quasar-convex functions curve toward their lowest point in a one-sided way, weaker than full convexity. The authors study the proximity operator for such functions and track the algorithm's step sequence.
Under plain quasar-convexity, the sequence reaches a global minimizer with a stated complexity rate. Under the strong version, convergence turns linear, far faster, with a logarithmic-style rate. Some results are new even for star-convex functions, a special case. Numerical experiments match the theory, widening the safe territory for this workhorse method.
Catalog record
| CREATOR | José de Brito, Felipe Lara, Di Liu |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 57 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2509-04375
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Extending Linear Convergence of the Proximal Point Algorithm: The Quasar-Convex Case José de Brito, Felipe Lara, Di Liu 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 minimizing and achieves an 𝒪 ( ε − 1 ) \mathcal{O}(\varepsilon^{-1}) complexity rate for quasar-convex functions; (ii) under strong quasar-convexity, the sequence converges linearly and attains an 𝒪 ( ln ( ε − 1 ) ) \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. Keywords : Nonconvex optimization; Proximal point algorithms; Linear convergence; Quasar-convexity Mathematics Subject Classification: 90C26; 90C30. 1 Introduction Let h:\mathbb{R}^{n}\rightarrow\overline{\mathbb{R}}:=\mathbb{R}\cup\{\pm\infty\} be a proper function. We are interested in solving the problem \min_{x\in\mathbb{R}^{n}}\,h(x), (1) via the Proximal Point Algorithm (PPA henceforth) [ 36 , 37 , 46 ] , a scheme which given x^{0}\in\mathbb{R}^{n} and a sequence of positive parameters \{\beta_{k}\}_{k} , generates a sequence as follows: x^{k+1}\in{\rm argmin}_{x\in\mathbb{R}^{n}}\,\left(h(x)+\frac{1}{2\beta_{k}}\lVert x^{k}-x\|^{2}\right),~\forall~k\in\mathbb{N}_{0}:=\mathbb{N}\cup\{0\}. (2) Despite its simplicity, PPA is a powerful tool in continuous optimization, as it allows us to simplify the original problem by solving better-conditioned subproblems. For instance, when h is convex, the function x\mapsto h(x)+\frac{1}{2\beta_{k}}\lVert x^{k}-x\rVert^{2} is strongly convex. This property makes solving the subproblems easier because proper, lower semicontinuous (lsc henceforth) strongly convex functions possess remarkable properties, such as a unique minimizer and quadratic growth. In fact, when h is convex, the sequence \{x^{k}\}_{k} generated by ( 2 ) is a minimizing sequence for problem ( 1 ). Specifically, it is decreasing, converges to the minimum (though not linearly), and achieves a complexity rate of \mathcal{O}(\varepsilon^{-1}) . Moreover, if h is strongly convex, then \{x^{k}\}_{k} converges linearly to the unique solution with an improved complexity rate of \mathcal{O}(\ln(\varepsilon^{-1})) . Due to these appealing properties, significant research efforts in recent decades have been devoted to extending the convergence guarantees of the PPA to broader function classes. Notable contributions include extensions to weakly convex and hypomonotone operators [ 13 , 26 , 44 ] ; developments in DC programming [ 2 , 4 , 7 , 47 ] ; and studies of (strongly) quasiconvex functions [ 17 , 30 , 43 ] . However, these frameworks fail to fully preserve the desirable properties of the convex case. For instance, PPA achieves only sublinear convergence for weakly convex and DC functions. Although linear convergence is possible for strongly quasiconvex functions, there is no evidence that PPA even converges to a minimizer in the general quasiconvex (not strongly) case [ 43 ] . This paper bridges this gap by presenting a comprehensive extension of PPA from convex to quasar-convex functions. We establish global convergence to a minimizer and provide a detailed analysis of its convergence rate. This extension is compelling for three key reasons: First, the quasar-convex class is a strict generalization of fundamental convexity classes. It encompasses all convex functions with a nonempty solution set [ 20 , 23 ] , all strongly convex functions as well as all (strongly) star-convex functions [ 42 ] . Second, quasar-convexity arises naturally in numerous nonconvex applications, including machine learning [ 23 , 32 , 34 ] and stochastic optimization [ 10 , 53 ] . Furthermore, its favorable geometry is also crucial for accelerating gradient-based methods (see [ 20 , 22 , 23 , 24 , 25 , 50 ] and references therein). Third, as we demonstrate, quasar-convexity provides a natural modeling framework for novel problems in microeconomics, statistics, and machine learning that are beyond the reach of convex models (see Subsection 3.1 ). Our Contribution : We study (strongly) quasar-convex functions with modulus \gamma\geq 0 . To that end, first we establish sufficient conditions for (nonsmooth) functions to be (strongly) quasar-convex. In particular, we show that the \ell_{p} -regularization ( 0<p<1 ) [ 52 ] and the CES (Constant Elasticity of Substitution) [ 3 ] , Cobb-Douglas [ 12 ] , and Leontief [ 33 ] production/utility functions are quasar-convex (and strongly quasar-convex on bounded convex sets). Second, we investigate the proximity operator of quasar-convex functions by proving that it is always nonempty (i.e., existence of iterates is guaranteed) and demonstrating cases where it is not a singleton. Furthermore, we establish a useful relationship between the minimizers of the proximity operator and the minimizers of the function. Third, we prove that the set of fixed points of the proximity operator coincides with the set of minimizers of a quasar-convex function, which provides the stopping criterion for PPA. Fourth, we implement PPA for quasar-convex functions ( \gamma\geq 0 ) and show that the generated sequence is minimizing with a complexity rate of \mathcal{O}(\varepsilon^{-1}) when \gamma=0 , matching the rate for convex functions [ 19 ] . Fifth, for the special case of strongly quasar-convex functions ( \gamma>0 ), we prove that PPA converges linearly to the unique solution and achieves an \mathcal{O}(\ln(\varepsilon^{-1})) complexity rate, exactly as in the strongly convex case. Finally, we present numerical experiments with nonconvex examples to demonstrate the potential of our results. The paper is structured as follows: In Section 2 , we introduce preliminary concepts and basic definitions related to generalized convexity. In Section 3 , we study nonsmooth quasar-convex functions, analyze key properties of the proximity operator, and present illustrative examples with applications in machine learning and economics. In Section 4 , we implement the proximal point algorithm (PPA) and analyze its convergence behavior and complexity rates for both strongly quasar-convex and quasar-convex cases. In Section 5 , we provide numerical experiments on nonconvex problems, demonstrating the practical implications of our theoretical results. Finally, in Section 6 , we conclude with a discussion of our findings and outline potential directions for future research. 2 Preliminaries and Basic Definitions The inner product of \mathbb{R}^{n} and the Euclidean norm are denoted by \langle\cdot,\cdot\rangle and \lVert\cdot\rVert , respectively. The open ball with center at x_{0}\in\mathbb{R}^{n} and radius \varepsilon>0 is denoted by \mathbb{B}(x_{0},\varepsilon) . We denote \mathbb{R}_{+}:=[0,+\infty[ and \mathbb{R}_{++}:=\,]0,+\infty[ , hence \mathbb{R}^{n}_{+}:=[0,+\infty[\,\times\ldots\times[0,+\infty[ and \mathbb{R}_{++}^{n}:=\,]0,+\infty[\,\times\ldots\times\,]0,+\infty[ ( n times), respectively. Let K be a nonempty set in \mathbb{R}^{n} , its closure is denoted by \overline{K} and its asymptotic (recession) cone by K^{\infty}:=\{u\in\mathbb{R}^{n}:~\exists~t_{k}\rightarrow+\infty,~\exists~x_{k}\in K,~\frac{x_{k}}{t_{k}}\rightarrow u\} . Furthermore, for any set K\subset\mathbb{R}^{n} , it follows from [ 5 , Proposition 2.1.2] that K^{\infty}=\{0\} if and only if K is bounded. Given any x,y,z\in\mathbb{R}^{n} and any \beta\in\mathbb{R} , the following relations hold: \displaystyle~~~~~\langle x-z,y-x\rangle=\frac{1}{2}\lVert z-y\rVert^{2}-\frac{1}{2}\lVert x-z\rVert^{2}-\frac{1}{2}\lVert y-x\rVert^{2}, (3) \displaystyle\lVert\beta x+(1-\beta)y\rVert^{2}=\beta\lVert x\rVert^{2}+(1-\beta)\lVert y\rVert^{2}-\beta(1-\beta)\lVert x-y\rVert^{2}. (4) Given any extended-valued function h:\mathbb{R}^{n}\rightarrow\overline{\mathbb{R}} , the effective domain of h is defined by {\rm dom}\,h:=\{x\in\mathbb{R}^{n}:h(x)<+\infty\} . It is said that h is proper if {\rm dom}\,h is nonempty and h(x)>-\infty for all x\in\mathbb{R}^{n} . The notion of properness is important when dealing with minimization problems. We denote by {\rm epi}\,h:=\{(x,t)\in\mathbb{R}^{n}\times\mathbb{R}:h(x)\leq t\} the epigraph of h , by S_{\lambda}(h):=\{x\in\mathbb{R}^{n}:h(x)\leq\lambda\} the sublevel set of h at the height \lambda\in\mathbb{R} and by {\rm argmin}_{\mathbb{R}^{n}}h the set of all minimal points of h . A