Star Quasiconvexity: an Unified Approach for Linear Convergence of First-Order Methods Beyond Convexity

Phan Quoc Khanh, Felipe Lara · 2025

Read Star Quasiconvexity: an Unified Approach for Linear Convergence of First-Order Methods Beyond Convexity by Phan Quoc Khanh, Felipe Lara (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-2510-24981.txt.

Introduction

Phan Quoc Khanh and Felipe Lara name a new broad class of curve shapes for use in best fit math. The class, star quasiconvex, wraps in plain convex shapes, star shapes, and a few known kin as plain cases. Such shapes matter since first order tools can be shown to home in fast on them, past the plain convex world.

The pair give a few marks of the class, for both smooth and rough cases. In the rough case, all low sets of such a curve are star shaped at a low point. In the smooth case, strong forms match a known slope rule. They also show a close step tool runs in a straight line pace to the lone best point.

Catalog record

CREATORPhan Quoc Khanh, Felipe Lara
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE56 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2510-24981

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Star Quasiconvexity: an Unified Approach for Linear Convergence of First-Order Methods Beyond Convexity Phan Quoc Khanh, Felipe Lara Abstract We introduce a class of generalized convex functions, termed star quasiconvexity, to ensure the linear convergence of gradient and proximal point methods. This class encompasses convex, star-convex, quasiconvex, and quasar-convex functions. We establish that a function is star quasiconvex if and only if all its sublevel sets are star-shaped with respect to the set of its minimizers. Furthermore, we provide several characterizations of this class, including nonsmooth and differentiable cases, and derive key properties that facilitate the implementation of first-order methods. Finally, we prove that the proximal point algorithm converges linearly to the unique solution when applied to strongly star quasiconvex functions defined over closed, star-shaped sets, which are not necessarily convex. Keywords : Nonconvex optimization; Gradient methods; Proximal point methods; Linear convergence; Star-shaped functions 1 Introduction Let h:\mathbb{R}^{n}\rightarrow\overline{\mathbb{R}}:=\mathbb{R}\cup\{\pm\infty\} be a proper function. The most classical problem in optimization is the unconstrained minimization problem: \min_{x\in\mathbb{R}^{n}}\,h(x). (P) This paper investigates a generalized notion of convexity that ensures the linear convergence of first-order methods for solving the minimization problem in ( P ). The standard assumption for achieving linear convergence in gradient and proximal point methods is that the objective function h is strongly convex. This property is highly desirable as it guarantees the existence and uniqueness of a solution, implies quadratic growth conditions, and ensures the Polyak- \L ojasiewicz (PL) property, among other benefits. Motivated by these properties, several authors have introduced broader classes of functions that retain these convergence guarantees. Notable examples include: Strongly quasiconvex functions: introduced by Polyak in 1966 as a particular case of uniformly quasiconvex functions [ 37 ] , this was one of the first such generalizations. Although not immediately proven, it was later established that this class satisfies PL property and quadratic growth, leading to linear convergence rates for gradient-type methods [ 17 , 26 ] and proximal point methods [ 25 ] . Strongly star-convex functions: defined by Nesterov and Polyak in 2006 [ 33 ] , this class also ensures linear convergence for both gradient and proximal point methods, as demonstrated in [ 20 ] and [ 8 ] , respectively. Strongly quasar-convex functions: introduced under various names in [ 14 , 15 , 20 ] (among others), this class has been shown to yield linear convergence for gradient-type methods [ 14 , 15 , 19 , 20 ] and, recently, for the proximal point method in [ 8 ] . The relationship between these classes is summarized below: \displaystyle\begin{array}[]{ccccccc}{\rm strongly~quasiconvex}&\Longleftarrow&{\rm strongly~convex}&\Longrightarrow&{\rm strongly~star-convex}\\ &&&&\Downarrow\\ &&&&{\rm strongly~quasar-convex}\end{array} Since all the previous notions includes strongly convex functions and they provide linear convergence for first-order methods, the authors in [ 17 , 26 , 27 ] studied the relation between (strongly) quasiconvex and (strongly) quasar-convex functions in the differentiable case. It was showed in [ 17 , Subsection 3.1] that both classes are not related each other and, as a consequence, the following natural question arises: What is the class of generalized (strongly) convex functions that guarantees global linear convergence rate for first-order methods and includes both (strongly) quasiconvex and (strongly) quasar-convex functions?. Our Contribution: We introduce the notion of (strong) star quasiconvexity for solving the question above by proving that both (strongly) quasiconvex and (strongly) quasar-convex functions are (strongly) star quasiconvex, an inclusion which is proper since we show examples of strongly star quasiconvex functions which are neither quasiconvex nor quasar-convex (see Example 8 ). Second, we provide four different characterizations for (strongly) star quasiconvex functions; (i) by characterizing star quasiconvex functions via the star-shapedness of its sublevel sets in Theorem 9 ; (ii) by showing that (strongly) star quasiconvex functions are (strongly) quasiconvex functions along rays starting from its unique minimizer in Theorem 12 ; (iii) by finding a stronger property for the continuous case in Corollary 16 ; and, (iv) by characterizing the behaviour of its gradient in the differentiable case in Proposition 24 . Third, several interesting properties for smooth and nonsmooth strongly star quasiconvex functions are derived from the previous analysis as: quadratic growth, Polyak- \L ojasiewicz property, and also 2 -supercoercivity as well as relationships with the proximity operator on star-shaped sets among others. Notably, some of these properties are even novel for strong quasar-convexity and/or strong quasiconvexity, too. Fourth, we observed that the gradient method and its heavy ball and Nesterov accelerations achieves linear convergence rate, extending the results from [ 14 , 15 , 17 , 19 , 20 , 26 ] to strongly star quasiconvex functions. Sixth, we ensure linear convergence of the proximal point algorithm (PPA henceforth) for strongly star quasiconvex on star-shaped set, extending the results from [ 8 , 25 ] as well as presenting the first (as far as we know) convergence result of PPA on star-shaped sets. Finally, we present conclusions and future research lines. The structure of the paper is as follows: In Section 2 we present notation and basic definitions on generalized convexity. In Section 3 , we present the motivation for introducing (strong) star quasiconvex functions, four different characterizations for this class of functions as well as interesting properties for developing first-order type algorithms. In Section 4 , we present the linear convergence of the gradient method as well as for its heavy ball and Nesterov accelerations. In Section 5 , we ensures linear convergence for PPA on star-shaped sets. Conclusions and future research directions are described in Section 6 . 2 Preliminaries The inner product in \mathbb{R}^{n} and the Euclidean norm are denoted by \langle\cdot,\cdot\rangle and \lVert\cdot\rVert , respectively. We denote \mathbb{R}_{+}:=[0,+\infty[ , \mathbb{R}_{++}:=\,]0,+\infty[ and \mathbb{N}_{0}:=\mathbb{N}\cup\{0\} . Let K\subseteq\mathbb{R}^{n} . Its asymptotic (recession) cone by K^{\infty}:=\left\{u\in\mathbb{R}^{n}:~\exists~t_{k}\rightarrow+\infty,~\exists~x_{k}\in K,~\frac{x_{k}}{t_{k}}\rightarrow u\right\}. Furthermore, for any set K\subset\mathbb{R}^{n} , it follows from [ 4 , 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\lVert\beta x+(1-\beta)y\rVert^{2} \displaystyle=\beta\lVert x\rVert^{2}+(1-\beta)\lVert y\rVert^{2}-\beta(1-\beta)\lVert x-y\rVert^{2}. (1) \displaystyle\langle x-z,y-x\rangle \displaystyle=\frac{1}{2}\lVert z-y\rVert^{2}-\frac{1}{2}\lVert x-z\rVert^{2}-\frac{1}{2}\lVert y-x\rVert^{2}, (2) Let K\subseteq\mathbb{R}^{n} be nonempty. Then given x_{0}\in K , the set K is said to be star-shaped at the point x_{0} if for every x\in K , the segment [\overline{x},x]\subseteq K . 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. It is indicated by {\rm epi}\,h:=\{(x,t)\in\mathbb{R}^{n}\times\mathbb{R}:h(x)\leq t\} the epigraph of h , by S_{\delta}(h):=\{x\in\mathbb{R}^{n}:h(x)\leq\delta\} the sublevel set of h at the height \delta\in\mathbb{R} and by {\rm argmin}_{\mathbb{R}^{n}}h the set of all minimal points of h . A function h is lower semicontinuous (lsc henceforth) at \overline{x}\in\mathbb{R}^{n} if for any sequence \{x_{k}\}_{k}\subseteq\mathbb{R}^{n} with x_{k}\rightarrow\overline{x} , h(\overline{x})\leq\liminf_{k\rightarrow+\infty}h(x_{k}) . Furthermore, the current convention \sup_{\emptyset}h:=-\infty and \inf_{\emptyset}h:=+\infty is adopted. A function h with convex domain is said to be: (a) (strongly) convex on {\rm dom}\,h , if there exists \gamma\geq 0 such that if for all x,y\in\mathrm{dom}\,h and all \lambda\in[0,1] , we have h(\lambda y+(1-\lambda)x)\leq\lambda h(y)+(1-\lambda)h(x)-\lambda(1-\lambda)\frac{\gamma}{2}\lVert x-y\rVert^{2}, (3) (b) (strongly) quasiconvex on {\rm dom}\,h , if there exists \gamma\geq 0 such that if for all x,y\in\mathrm{dom}\,h and all \lambda\in[0,1]

Read the complete text