betaFeedback

WorksMathematics

A Proximal Gradient Method for Nonconvex Nonsmooth Optimization with Applications

Abstract

We study a proximal-gradient method for the sum of a convex smooth function gg and a possibly nonconvex, nonsmooth, strongly quasar-convex regularizer. The gradient step is weighted by the quasar-convexity parameter, so, for step sizes in the descent range, the iteration decreases a weighted objective, while the unweighted sum serves for comparison. We establish a geometric envelope around every global minimizer of the unweighted objective, with an explicit radius independent of the step size; a common minimizer yields global linear convergence. We also prove that every critical point uu of the weighted objective lies within an explicit multiple of ∥∇g(u)∥\|\nabla g(u)\| from every global minimizer of the unweighted objective. Together with an optimized composite comparison, this yields asymptotic distance bounds. An example shows that the two objectives can have different critical points. For power-regularized least squares with powers between zero and one, descent provides a confinement ball for the sharp local modulus, and support identification combined with a KL argument yields whole-sequence convergence.

Introduction

Composite optimization provides a natural formulation for problems in which a smooth data-fitting term is combined with a nonsmooth regularizer. Proximal-gradient method gradient methods exploit this structure by separating a gradient step from a proximity step. Nonconvex penalties are of particular interest in sparse approximation, where they induce different sparsity patterns and estimation biases from convex regularizers. Their analysis requires care: the proximity operator can be set-valued, stationary points need not be globally optimal, and guarantees derived from convexity are no longer available [1, 3, 5, 18].

Quasar-convexity offers a different source of structure by controlling a function along segments directed toward a global minimizer. Smooth quasar-convex optimization admits efficient first-order methods [9, 14, 24]. For nonsmooth functions, the proximal-point analysis in [6] establishes global convergence and linear rates under strong quasar-convexity. The proximal comparison inequality relative to the quasar-convex center in [6 Proposition 15] is a starting point for the present work. Proximal quasar-convexity has also been introduced for composite models with convex regularizers and random zeroth-order oracles [8]. Our setting differs because the regularizer itself may be nonconvex and its quasar-convex center need not minimize the full composite objective.

The composite analysis in [13 Section 3.3] considers an accelerated proximal-gradient method for a strongly quasar-convex smooth term and a convex nonsmooth term. The composite convergence result is restricted to the quasar-convexity parameter equal to one (κ=1\kappa= 1 in our notation) and requires the smooth term to satisfy the extended strong quasar-convexity inequality at a global minimizer of the sum, together with a lower-curvature condition. The location of this reference point is essential, since adding a convex term may displace the minimizer from the original quasar-convex center. In our setting, the smooth term is convex, while the regularizer may be nonconvex and nonsmooth. We retain its own quasar-convex center and derive proximal comparisons valid at arbitrary reference points.

We analyze the splitting iteration

xk+1∈Prox⁡βkh(xk−κβk∇g(xk)),0<κ≤1,x_{k+1} \in\operatorname{Prox}_{\beta_k h}\left(x_k-\kappa\beta_k\nabla g(x_k)\right), \qquad0 < \kappa\le1,

where gg is convex with a Lipschitz continuous gradient and hh is proper, lower semicontinuous, and strongly quasar-convex. The factor κ\kappa in the gradient step is chosen to match the coefficient arising from the proximal comparison for a strongly quasar-convex regularizer. Both component comparisons then carry the factor 2κβk2\kappa\beta_k, and their sum yields estimates relative to global minimizers of f=g+hf = g + h, which need not coincide with the quasar-convex center of hh. This choice allows us to exploit the geometry of the regularizer without imposing quasar-convexity on the composite objective. For steps in the descent range, the iteration decreases Fk=κg+hF_k = \kappa g + h, so its critical-point convergence concerns this weighted objective. We thus distinguish the objective decreased by the algorithm from the unweighted objective used in the global-minimizer comparisons.

Our first main result combines geometric and asymptotic distance estimates relative to global minimizers of ff. For every constant step in the descent range, a geometric envelope controls the distance to a ball centered at any such minimizer, with an explicit radius independent of the step size. A common minimizer of gg and hh yields global linear convergence for every proximal selection. Our second main result is a comparison at critical points: every critical point uu of FκF_{\kappa} lies within an explicit multiple of ∥∇g(u)∥\lVert\nabla g(u)\rVert from every global minimizer of ff. Optimizing the free parameter in the composite inequality recovers this same comparison constant when μ≤κγ/(2−κ)\mu\leq\kappa\gamma/(2-\kappa), where μ\mu and γ\gamma denote, respectively, the strong-convexity modulus of gg and the quasar-convexity modulus of hh (Assumption (H), Section 3); for larger values of μ\mu, the critical-point comparison supplies the stronger asymptotic estimate. An example with a nonconvex regularizer shows that critical points of FκF_{\kappa} need not be critical for ff.

For the application h(x)=ρ∥x∥pph(x)=\rho\lVert x\rVert_p^p, 0<p<10<p<1, strong quasar-convexity is available only on bounded sets. We recall its sharp modulus on a Euclidean ball and derive the required ball directly from the initial weighted objective value, resolving the confinement requirement without modifying the algorithm. To complete the application, we apply established thresholding and restricted-KL arguments [1, 27, 28] to verify whole-sequence convergence to a critical point of FκF_{\kappa}. These properties complement the comparison estimates and do not imply global sparse recovery.

Section 2 presents the preliminaries, and Section 3 develops the proximal comparison inequalities and convergence estimates. Section 4 applies the results to power-regularized least squares, followed by the conclusions in Section 5.

Preliminaries and Basic Definitions

The inner product on Rn\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 x0∈Rnx_0\in\mathbb{R}^n and radius ε>0\varepsilon>0 is denoted by B(x0,ε)\mathbb{B}(x_0,\varepsilon). For r≥0r\geq0, we write B(x0,r):={x∈Rn:∥x−x0∥≤r}\mathbb{B}(x_0,r):=\{x\in\mathbb{R}^n:\lVert x-x_0\rVert\leq r\} for the closed ball, and also use BB in place of B\mathbb{B}. We set (t)+:=max⁡{t,0}(t)_+:=\max\{t,0\} for t∈Rt\in\mathbb{R}. We write R+:=[0,+∞[\mathbb{R}_+:=[0,+\infty[ and R++:=]0,+∞[\mathbb{R}_{++}:=]0,+\infty[. For a nonempty set K⊂RnK\subset\mathbb{R}^n, we denote its closure by K‾\overline{K}.

A nonempty set K⊂RnK\subset\mathbb{R}^n is said to be star-shaped at x0∈Kx_0\in K if, for every x∈Kx\in K, the segment [x0,x]⊂K[x_0,x]\subset K.

Given any u,v,w∈Rnu,v,w\in\mathbb{R}^n and any θ∈R\theta\in\mathbb{R}, the following relations hold:

⟨u−w,v−u⟩=12∥w−v∥2−12∥u−w∥2−12∥v−u∥2(1)\langle u-w,v-u\rangle=\frac{1}{2}\lVert w-v\rVert^2-\frac{1}{2}\lVert u-w\rVert^2-\frac{1}{2}\lVert v-u\rVert^2 \tag*{(1)}
∥θu+(1−θ)v∥2=θ∥u∥2+(1−θ)∥v∥2−θ(1−θ)∥u−v∥2(2)\lVert\theta u+(1-\theta)v\rVert^2=\theta\lVert u\rVert^2+(1-\theta)\lVert v\rVert^2-\theta(1-\theta)\lVert u-v\rVert^2 \tag*{(2)}

Given any extended-valued function h:Rn→R‾h:\mathbb{R}^n\to\overline{\mathbb{R}}, the effective domain of hh is defined by dom⁡h:={x∈Rn:h(x)<+∞}\operatorname{dom}h:=\{x\in\mathbb{R}^n:h(x)<+\infty\}. The function hh is proper if dom⁡h\operatorname{dom}h is nonempty and h(x)>−∞h(x)>-\infty for all x∈Rnx\in\mathbb{R}^n. The notion of properness is important when dealing with minimization problems.

We denote by Sλ(h):={x∈Rn:h(x)≤λ}S_{\lambda}(h):=\{x\in\mathbb{R}^n:h(x)\leq\lambda\} the sublevel set of hh at level λ∈R\lambda\in\mathbb{R}, and by argmin⁡Rnh\operatorname*{argmin}_{\mathbb{R}^n}h the set of its global minimizers. A function hh is lower semicontinuous (lsc) at x‾∈Rn\overline{x}\in\mathbb{R}^n if, for every sequence {xk}k⊂Rn\{x_k\}_k\subset\mathbb{R}^n with xk→x‾x_k\to\overline{x}, we have h(x‾)≤lim inf⁡k→+∞h(xk)h(\overline{x})\leq\liminf_{k\to+\infty}h(x_k).

A proper function h:Rn→R‾h : \mathbb{R}^{n} \to\overline{\mathbb{R}} is coercive if

lim⁡∥x∥→+∞h(x)=+∞,\lim_{\lVert x\rVert\to+\infty} h(x) = +\infty,

or equivalently, if Sλ(h)S_{\lambda}(h) is bounded for every λ∈R\lambda\in\mathbb{R}.

The following generalized convexity notion has been used in several applications in machine learning because it supports convergence guarantees for gradient methods (see [9, 12, 13, 14, 24] and references therein).

Motivated by [14 Lemma 10], we define quasar-convexity as follows:

Definition 2.1. Let κ∈]0,1]\kappa\in]0,1], γ≥0\gamma\ge0, let h:Rn→R‾h : \mathbb{R}^{n} \to\overline{\mathbb{R}} be proper, and let K⊂RnK \subset\mathbb{R}^{n} be star-shaped at x‾∈K∩argmin⁡Rnh\overline{x} \in K \cap\operatorname{argmin}_{\mathbb{R}^{n}} h. We say that hh is (κ,γ)(\kappa,\gamma)-strongly quasar-convex on KK with respect to x‾\overline{x} if

h(λx‾+(1−λ)x)≤κλh(x‾)+(1−κλ)h(x)−λ(1−λ2−κ)κγ2∥x−x‾∥2h(\lambda\overline{x} + (1-\lambda)x) \le\kappa\lambda h(\overline{x}) + (1-\kappa\lambda)h(x) - \lambda\left(1-\frac{\lambda}{2-\kappa}\right)\frac{\kappa\gamma}{2}\lVert x-\overline{x}\rVert^{2}

for all λ∈[0,1]\lambda\in[0,1] and all x∈K∩dom⁡hx \in K \cap\operatorname{dom} h. When K=RnK = \mathbb{R}^{n}, we omit the reference to KK; when γ=0\gamma= 0, we say that hh is κ\kappa-quasar-convex.

In particular, K∩dom⁡hK \cap\operatorname{dom} h is star-shaped at x‾\overline{x}, since the right-hand side is finite for x∈K∩dom⁡hx \in K \cap\operatorname{dom} h.

If hh is (κ,γ)(\kappa,\gamma)-strongly quasar-convex on KK with respect to x‾\overline{x} and γ>0\gamma> 0, then x‾\overline{x} is the unique minimizer of hh on KK, by the quadratic-growth inequality (5) below; in the global case, argmin⁡Rnh={x‾}\operatorname{argmin}_{\mathbb{R}^{n}} h = \{\overline{x}\}. If γ=0\gamma= 0, then K∩argmin⁡RnhK \cap\operatorname{argmin}_{\mathbb{R}^{n}} h is star-shaped at x‾\overline{x} (see [14 Observation 3]). For κ=1\kappa= 1, (strongly) quasar-convex functions are (strongly) star-convex [21]. In particular, every (strongly) convex function with modulus γ≥0\gamma\ge0 that attains its minimum is (1,γ)(1,\gamma)-strongly quasar-convex with respect to any of its minimizers.

The relationship between convex/star-convex/quasar-convex notions is summarized below:

strongly convex⟹∗strongly star-convex⟹∗strongly quasar-convex⇓⇓⇓convex⟹∗star-convex⟹∗quasar-convex\begin{array}{ccccc} \text{strongly convex} & \overset{*}{\Longrightarrow} & \text{strongly star-convex} & \overset{*}{\Longrightarrow} & \text{strongly quasar-convex} \\ \Downarrow& & \Downarrow& & \Downarrow\\ \text{convex} & \overset{*}{\Longrightarrow} & \text{star-convex} & \overset{*}{\Longrightarrow} & \text{quasar-convex} \end{array}

where “*” denotes that argmin⁡Rnh≠∅\operatorname{argmin}_{\mathbb{R}^{n}} h \ne\varnothing is required. None of the reverse implications holds in general (see [9, 13, 14, 21]).

Remark 2.2. Neither (strong) quasiconvexity nor (strong) quasar-convexity implies the other in general. Indeed, the function in [11 Example 11] is strongly quasiconvex but not quasar-convex, while the function in [6 Example 8] is strongly quasar-convex on a ball in dimension at least two but not quasiconvex. For differentiable functions, sufficient conditions under which strong quasiconvexity implies quasar-convexity are provided in [11, 17].

A function h:Rn→Rh : \mathbb{R}^{n} \to\mathbb{R} is said to be LL-smooth on an open set K⊂RnK \subset\mathbb{R}^{n} if it is differentiable on KK and

References

  1. [1]H. ATTOUCH, J. BOLTE, B.F. SVAITER, Convergence of descent methods for semi-algebraic and tame problems: proximal algorithms, forward–backward splitting, and regularized Gauss–Seidel methods. Math. Program. 137, 91–129, (2013).
  2. [2]M. AVRIEL, W.E. DIEWERT, S. SCHAIBLE, I. ZANG. “Generalized Concavity”. SIAM, Classics in Applied Mathematics, Philadelphia, (2010).
  3. [3]S. Banert, R.I. Boţ, A general double-proximal gradient algorithm for d.c. programming, Math. Program., 178, 301–326, (2019).DOI
  4. [4]H.H. Bauschke, P.L. Combettes. “Convex Analysis and Monotone Operator Theory in Hilbert Spaces”. CMS Books in Mathematics. Springer-Verlag, second edition, (2017).
  5. [5]J. Bolte, S. Sabach, M. Teboulle, Proximal alternating linearized minimization for nonconvex and nonsmooth problems, Math. Program., 146, 459–494, (2014).DOI
  6. [6]J. de Brito, F. Lara, D. Liu, Extending linear convergence of the proximal point algorithm: the quasar-convex case, preprint, arXiv:2509.04375, (2025). Version 2, revised 14 April 2026.arxiv.org/abs/2509.04375
  7. [7]A. Cambini, L. Martein. “Generalized Convexity and Optimization”. Springer-Verlag, Berlin-Heidelberg, (2009).DOI
  8. [8]A.A. Farzin, Y.-M. Pun, P. Braun, I. Shames, Minimisation of quasar-convex functions using random zeroth-order oracles, Trans. Mach. Learn. Res., (2026).arxiv.org/abs/2505.02281
  9. [9]S. Guminov, A. Gasnikov, I. Kuruzov, Accelerated methods for weakly-quasi-convex optimization problems, Comput. Manag. Sci., 20, Article number: 36, (2023).DOI
  10. [10]N. Hadjisavvas, S. Komlós, S. Schaible (eds.). “Handbook of Generalized Convexity and Generalized Monotonicity”. Springer-Verlag, New York, (2005).DOI
  11. [11]N. Hadjisavvas, F. Lara, R.T. Marcavillaca, P.T. Vuong, Heavy ball and Nesterov accelerations with Hessian-driven damping for nonconvex optimization, Applied Math. Optim., 93, article number 63, (2026).
  12. [12]M. Hardt, T. Ma, B. Recht, Gradient descent learns linear dynamical systems, J. Mach. Learning Res., 19, 1–44, (2018).
  13. [13]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, Optimization, published online 5 June 2026.arxiv.org/abs/2405.19809
  14. [14]O. Hinder, A. Sidford, N. Sohoni, Near-optimal methods for minimizing star-convex functions and beyond. In: Proc. 33rd Conf. Learning Theory, Proc. Mach. Learning Res., 125, 1894–1938, (2020).arxiv.org/abs/1906.11985
  15. [15]K. Knight, W. Fu, Asymptotics for Lasso-type estimators, The Annals of Statistics, 28, 5, 1356–1378, (2000).DOI
  16. [16]F. Lara, On strongly quasiconvex functions: existence results and proximal point algorithms, J. Optim. Theory Appl., 192, 891–911, (2022).DOI
  17. [17]F. Lara, C. Vega, Delayed feedback in online non-convex optimization: a non-stationary approach with applications, Numer. Algorithms, (2025).arxiv.org/abs/2412.14506
  18. [18]F. Lara, L.H. Yen, On the minimization of the sum of nonconvex functions with applications to mathematical programming. J. Global Optim., DOI: 10.1007/s10898-025-01520-6, (2025).DOI
  19. [20]I. Necoara, Y. Nesterov, F. Glineur, Linear convergence of first order methods for non-strongly convex optimization, Math. Program., 175, 69–107, (2019).arxiv.org/abs/1504.06298
  20. [21]Y. Nesterov, B.T. Polyak, Cubic regularization of Newton method and its global performance, Math. Program., 108, 177–205, (2006).DOI
  21. [22]B.T. Polyak, Existence theorems and convergence of minimizing sequences in extremum problems with restrictions, Soviet Math. Dokl., 7, 72–75, (1966).
  22. [23]R.T. Rockafellar, R.J.-B. Wets. “Variational Analysis”. Grundlehren der mathematischen Wissenschaften, 317. Springer-Verlag, Berlin-Heidelberg, (1998).DOI
  23. [24]J.-K. Wang, A. Wibisono, Continued acceleration for quasar convex functions in non-convex optimization. In: Int. Conf. Learning Repres., (2023).arxiv.org/abs/2302.07851
  24. [27]J. Zeng, S. Lin, Y. Wang, Z. Xu, L₁/₂ regularization: convergence of iterative half thresholding algorithm, IEEE Trans. Signal Process., 62(9), 2317–2329, (2014).DOI
  25. [28]J. Zeng, S. Lin, Z. Xu, Sparse regularization: convergence of iterative jumping thresholding algorithm, IEEE Trans. Signal Process., 64(19), 5106–5118, (2016).arxiv.org/abs/1402.5744

Paper details

vlnc:W_487mr8m2
Version
v1 · latest
Published
Fresh — added to the Hub within the last 30 days
Added
License
CC0-1.0
Usage

views · 0

downloads · 0

A view counts once per browser per day, a download each time the PDF is requested.

  • Mathematics

Not recorded for this paper

View statement
Looking for related papers…
Contents