betaFeedback

WorksMathematics

KL-Guided Support Selection and Subspace Cubic Newton Methods for Sparse Optimization

Abstract

We study sparse composite optimization with a smooth loss and a possibly nonconvex, nonsmooth regularizer. The objective is locally smooth on each fixed support. Our method combines full-space proximal-gradient steps with inexact cubic-regularized Newton steps on a subspace selected by thresholding. If the iterates are bounded and the objective satisfies the Kurdyka–Łojasiewicz (KL) property, the entire sequence converges to a first-order stationary point. A threshold based on the KL exponent ensures that the selected coordinate set coincides with the support of the limit after finitely many iterations, without requiring a nondegeneracy assumption. We also provide a residual-based threshold when such an exponent exists and its value is unknown. Under an additional continuity assumption on the restricted Hessian, the line search eventually accepts full cubic steps. With bounded cubic regularization parameters and damping parameters chosen to meet the target tolerances, we bound the number of outer iterations needed to reach restricted approximate second-order stationarity after support identification and entry into the full-step regime. We conduct numerical experiments in two settings: when the KL exponent is known and when it is unknown. In the former case, we use a degenerate problem to demonstrate the effectiveness of the proposed method. In the latter case, we compare the proposed method and its adaptive variant with existing solvers on sparse recovery and logistic regression problems.

Min Tao (corresponding author)

Mathematics Subject Classification (2020) 90C26 · 65K05 · 90C30

Introduction

Sparse optimization models often combine a smooth loss with a regularizer that is nonsmooth in the full space. However, many sparsity-promoting regularizers yield a twice continuously differentiable objective when restricted to a fixed support. We combine full-space proximal-gradient steps with cubic-regularized Newton steps on a selected coordinate subspace. A central question is whether the selected coordinate set eventually coincides with the support of the limit point when the usual nondegeneracy condition fails. We prove that finite support identification still holds under a suitable thresholding rule determined by the positive power-type KL exponent of the objective at the limit.

In this paper, we consider composite problems of the form

min⁡x∈RnF(x):=g(x)+h(x),(1)\min_{x\in\mathbb{R}^{n}} F(x) := g(x) + h(x), \tag*{(1)}

where g:Rn→R‾:=R∪{+∞}g:\mathbb{R}^{n}\to\overline{\mathbb{R}}:=\mathbb{R}\cup\{+\infty\} is a proper, lower semicontinuous (l.s.c.), possibly nonconvex and nonsmooth function that is prox-bounded with threshold λg>0\lambda_g>0 and whose proximal mapping Prox⁡γg\operatorname{Prox}_{\gamma g} can be computed efficiently for 0<γ<λg0<\gamma<\lambda_g. We use the following standing assumptions.

Assumption 1.1 (i) For every nonzero x∈dom⁡F\mathbf{x}\in\operatorname{dom}F, let

Mx={z∈Rn:supp⁡(z)=supp⁡(x)}.\mathcal{M}_{\mathbf{x}}=\{\mathbf{z}\in\mathbb{R}^{n}:\operatorname{supp}(\mathbf{z})=\operatorname{supp}(\mathbf{x})\}.

The restriction of FF to Mx\mathcal{M}_{\mathbf{x}} is finite-valued and twice continuously differentiable in a relative neighborhood of x\mathbf{x}. For every nonempty S⊆supp⁡(x)S\subseteq\operatorname{supp}(\mathbf{x}), let ∇SF\nabla_S F and ∇S2F\nabla_S^2 F denote the corresponding coordinate gradient and principal Hessian of this restriction, respectively. The mapping ∇S2F\nabla_S^2F is strictly continuous at x\mathbf{x} relative to Mx\mathcal{M}_{\mathbf{x}}, with the constant lip⁡Mx∇S2F(x)\operatorname{lip}_{\mathcal{M}_{\mathbf{x}}}\nabla_S^2F(\mathbf{x}); see Definition 2.4.

(ii) h:Rn→Rh:\mathbb{R}^{n}\to\mathbb{R} is continuously differentiable with an LL-Lipschitz continuous gradient for some L≥0L\geq0.

(iii) The objective function is bounded below, i.e., F‾:=inf⁡x∈RnF(x)>−∞\underline{F}:=\inf_{\mathbf{x}\in\mathbb{R}^{n}}F(\mathbf{x})>-\infty.

The following two models illustrate that the local smoothness condition in Assumption 1.1(i) can be readily satisfied.

(a) Sparse recovery. For A∈Rm×nA\in\mathbb{R}^{m\times n}, b∈Rm\mathbf{b}\in\mathbb{R}^{m}, and λ>0\lambda>0, consider problem (1.1) with h(x)=12∥Ax−b∥22h(\mathbf{x})=\frac{1}{2}\lVert A\mathbf{x}-\mathbf{b}\rVert_2^2.

(i) L1/L2L_1/L_2 regularization. Let g(x)=λ∥x∥1/∥x∥2g(\mathbf{x})=\lambda\lVert\mathbf{x}\rVert_1/\lVert\mathbf{x}\rVert_2; see Tao [38]. We define ∥0∥1/∥0∥2=1\lVert\mathbf{0}\rVert_1/\lVert\mathbf{0}\rVert_2=1 to make gg lower semicontinuous at the origin. For x≠0\mathbf{x}\ne\mathbf{0} and ∅≠S⊆supp⁡(x)\varnothing\ne S\subseteq\operatorname{supp}(\mathbf{x}), its restricted Hessian satisfies

lip⁡Mx∇S2F(x)≤36λ∥x∥0∥x∥23.\operatorname{lip}_{\mathcal{M}_{\mathbf{x}}}\nabla_S^2F(\mathbf{x})\leq\frac{36\lambda\sqrt{\lVert\mathbf{x}\rVert_0}}{\lVert\mathbf{x}\rVert_2^3}.

(ii) LppL_p^p regularization. Let g(x)=λ∥x∥ppg(\mathbf{x})=\lambda\|\mathbf{x}\|_p^p, 0<p<10<p<1; see [46]. For x≠0\mathbf{x}\ne\mathbf{0} and ∅≠S⊆supp⁡(x)\varnothing\ne S\subseteq\operatorname{supp}(\mathbf{x}), its restricted Hessian satisfies

lip⁡Mx∇S2F(x)≤λp(1−p)(2−p)(min⁡i∈S∣xi∣)3−p.\operatorname{lip}_{\mathcal{M}_{\mathbf{x}}}\nabla_S^2 F(\mathbf{x})\le\frac{\lambda p(1-p)(2-p)}{(\min_{i\in S}|x_i|)^{3-p}}.

(b) L1−μL2L_1-\mu L_2-regularized logistic regression. Let the rows of A∈Rm×nA\in\mathbb{R}^{m\times n} be aiT\mathbf{a}_i^\mathsf{T}, and let bi∈{−1,1}b_i\in\{-1,1\}. For λ>0\lambda>0 and 0<μ≤10<\mu\le1, consider [35]

min⁡(z,u)∈Rn×Rλ(∥z∥1−μ∥z∥2)+1m∑i=1mlog⁡(1+e−bi(aiTz+u)).(2)\min_{(\mathbf{z},u)\in\mathbb{R}^n\times\mathbb{R}} \lambda(\|\mathbf{z}\|_1-\mu\|\mathbf{z}\|_2)+\frac{1}{m}\sum_{i=1}^{m}\log(1+e^{-b_i(\mathbf{a}_i^\mathsf{T}\mathbf{z}+u)}). \tag*{(2)}

Here uu is an unpenalized intercept. Set x=(z,u)\mathbf{x}=(\mathbf{z},u), take the regularization term as gg, and take the logistic loss as hh. For z≠0\mathbf{z}\ne\mathbf{0}, write Sz=supp⁡(z)S_z=\operatorname{supp}(\mathbf{z}). For ∅≠S⊆supp⁡(x)\varnothing\ne S\subseteq\operatorname{supp}(\mathbf{x}),

lip⁡∇S2F(x)≤{Mlog⁡+2λμ3∥z∥22,z≠0,163,z=0,u≠0.\operatorname{lip}\nabla_S^2F(\mathbf{x})\le \begin{cases} M_{\log}+\dfrac{2\lambda\mu}{\sqrt{3}\|\mathbf{z}\|_2^2}, & \mathbf{z}\ne\mathbf{0},\\ \dfrac{1}{6\sqrt{3}}, & \mathbf{z}=\mathbf{0},u\ne0. \end{cases}
Mlog⁡=163m∑i=1m(∥ai,Sz∥22+1)3/2.M_{\log}=\frac{1}{6\sqrt{3}m}\sum_{i=1}^{m}(\|\mathbf{a}_{i,S_z}\|_2^2+1)^{3/2}.

Table 1 lists several commonly used sparsity-promoting regularizers that satisfy Assumption 1.1(i).

References

  1. [1]Attouch, H., Bolte, J.: On the convergence of the proximal algorithm for nonsmooth functions involving analytic features. Mathematical Programming 116(1), 5–16 (2009). https://doi.org/10.1007/s10107-007-0133-5
  2. [2]Attouch, H., Bolte, J., Redont, P., Soubeyran, A.: Proximal alternating minimization and projection methods for nonconvex problems: An approach based on the Kurdyka–Łojasiewicz inequality. Mathematics of Operations Research 35(2), 438–457 (2010). https://doi.org/10.1287/moor.1100.0449
  3. [3]Bareilles, G., Lutzeler, F., Malick, J.: Newton acceleration on manifolds identified by proximal gradient methods. Mathematical Programming 200(1), 37–70 (2023). https://doi.org/10.1007/s10107-022-01873-w
  4. [4]Beck, A.: First-order methods in optimization. SIAM (2017). https://doi.org/10.1137/1.9781611974997
  5. [5]Birgin, E.G., Gardenghi, J.L., Martínez, J.M., Santos, S.A., Toint, P.L.: Worst-case evaluation complexity for unconstrained nonlinear optimization using high-order regularized models. Mathematical Programming 163(1–2), 359–368 (2017). https://doi.org/10.1007/s10107-016-1065-8
  6. [6]Blumensath, T., Davies, M.E.: Iterative Hard Thresholding for Compressed Sensing. Applied and Computational Harmonic Analysis 27(3), 265–274 (2009). https://doi.org/10.1016/j.acha.2009.04.002
  7. [7]Boţ, R.I., Csetnek, E.R., Nguyen, D.-K.: A proximal minimization algorithm for structured nonconvex and nonsmooth problems. SIAM Journal on Optimization 29, 1300–1328 (2019). https://doi.org/10.1137/18M1190689
  8. [8]Boţ, R.I., Li, G.Y., Tao, M.: Full splitting algorithms for fractional programs with structured numerators and denominators. SIAM Journal on Optimization 35(4), 2623–2653 (2025). https://doi.org/10.1137/23M1626591
  9. [9]Boyd, S., Vandenberghe, L.: Convex Optimization. Cambridge University Press, Cambridge (2004). https://doi.org/10.1017/CBO9780511804441
  10. [10]Carmon, Y., Duchi, J.: Gradient descent finds the cubic-regularized nonconvex Newton step. SIAM Journal on Optimization 29(3), 2146–2178 (2019). https://doi.org/10.1137/17M113898
  11. [11]Cartis, C., Gould, N.I.M., Toint, P.L.: Adaptive cubic regularisation methods for unconstrained optimization. Part I: motivation, convergence and numerical results. Mathematical Programming 127(2), 245–295 (2011). https://doi.org/10.1007/s10107-009-0286-5
  12. [12]Cartis, C., Gould, N.I.M., Toint, P.L.: Adaptive cubic regularisation methods for unconstrained optimization. Part II: worst-case function and derivative-evaluation complexity. Mathematical Programming 130(2), 295–319 (2011). https://doi.org/10.1007/s10107-009–0337-y
  13. [13]Chen, T.Y., Curtis, F.E., Robinson, D.P.: A reduced-space algorithm for minimizing ℓ₁-regularized convex functions. SIAM Journal on Optimization 27(3), 1583–1610 (2017). https://doi.org/10.1137/16M1062259
  14. [14]Curtis, F.E., Dai, Y., Robinson, D.P.: A subspace acceleration method for minimization involving a group sparsity-inducing regularizer. SIAM Journal on Optimization 32(2), 545–572 (2022). https://doi.org/10.1137/21M1141111
  15. [15]Gao, Y., Yue, M.-C., Ng, M.K.: Approximate secular equations for the cubic regularization subproblem. In: Advances in Neural Information Processing Systems 35 (2022). https://doi.org/10.52202/068431–1036
  16. [16]Gong, P., Zhang, C., Lu, Z., Huang, J., Ye, J.: A General Iterative Shrinkage and Thresholding Algorithm for Non-convex Regularized Optimization Problems. In: Proceedings of the 30th International Conference on Machine Learning, Proceedings of Machine Learning Research 28(2), 37–45 (2013).arxiv.org/abs/1303.4434
  17. [17]Hare, W.L., Lewis, A.S.: Identifying active constraints via partial smoothness and prox-regularity. Journal of Convex Analysis 11(2), 251–266 (2004). https://doi.org/10.68381/jca11017
  18. [18]Huang, L., Jia, J., Yu, B., Chun, B.-G., Maniatis, P., Naik, M.: Predicting execution time of computer programs using sparse polynomial regression. Advances in Neural Information Processing Systems 23, 883–891 (2010). https://papers.nips.cc/paper_files/paper/2010/hash/9566564d0c319973d3173a74a03860c–Abstract.html
  19. [19]Jia, X., Liang, X., Shen, C., Zhang, L.-H.: Solving the cubic regularization model by a nested restarting Lanczos method. SIAM Journal on Matrix Analysis and Applications 43(2), 812–839 (2022). https://doi.org/10.1137/21M1436324
  20. [20]Jiang, R.J., Yue, M.-C., Zhou, Z.S.: An accelerated first-order method with complexity analysis for solving cubic regularization subproblems. Computational Optimization and Applications 79(2), 471–506 (2021). https://doi.org/10.1007/s10589–021–00274–7
  21. [21]Jiang, R.J., Zhou, Z.S., Zhou, Z.R.: Cubic regularization methods with second-order complexity guarantee based on a new subproblem reformulation. Journal of the Operations Research Society of China 10(3), 471–506 (2022). https://doi.org/10.1007/s40305–022–00398–5
  22. [22]Lee, C.-P.: Accelerating inexact successive quadratic approximation for regularized optimization through manifold identification. Mathematical Programming 201, 599–633 (2023). https://doi.org/10.1007/s10107–022–01916–2
  23. [23]Lewis, A.S.: Active sets, nonsmoothness, and sensitivity. SIAM Journal on Optimization 13(3), 702–725 (2002). https://doi.org/10.1137/S1052623401387623
  24. [24]Lewis, A.S., Wright, S.J.: A proximal method for composite minimization. Mathematical Programming 158, 501–546 (2016). https://doi.org/10.1007/s10107–015–0943–9
  25. [25]Lewis, A.S., Wylie, C.: Active-set Newton methods and partial smoothness. Mathematics of Operations Research 46(2), 712–725 (2021). https://doi.org/10.1287/moor.2020.1075
  26. [26]Lewis, A.S., Zhang, S.: Partial smoothness, tilt stability, and generalized Hessians. SIAM Journal on Optimization 23(1), 74–94 (2013). https://doi.org/10.1137/110852103
  27. [27]Li, G., Pong, T.K.: Global convergence of splitting methods for nonconvex composite optimization. SIAM Journal on Optimization 25, 2434–2460 (2015). https://doi.org/10.1137/140998135
  28. [28]Liang, J., Fadili, J., Peyré, G.: Activity identification and local linear convergence of forward–backward-type methods. SIAM Journal on Optimization 27(1), 408–437 (2017). https://doi.org/10.1137/16M106340X
  29. [29]Lieder, F.: Solving large-scale cubic regularization by a generalized eigenvalue problem. SIAM Journal on Optimization 30(4), 3345–3358 (2020). https://doi.org/10.1137/19M1291388
  30. [30]Lin, M., Yuan, Y., Sun, D., Toh, K.-C.: A Highly Efficient Algorithm for Solving Exclusive Lasso Problems. Optimization Methods and Software 39(3), 489–518 (2024). https://doi.org/10.1080/10556788.2023.2253566
  31. [31]Liu, R., Deng, G., He, H.: Generalized Jaccard feature screening for ultra-high dimensional survival data. AIMS Mathematics 9(10), 27607–27626 (2024). https://doi.org/10.3934/math.20241341
  32. [32]Lou, Y., Yan, M.: Fast L₁−L₂ Minimization via a Proximal Operator. Journal of Scientific Computing 74(2), 767–785 (2018). https://doi.org/10.1007/s10915-017-0463-2
  33. [33]Nesterov, Y., Polyak, B.: Cubic regularization of Newton method and its global performance. Mathematical Programming 108(1), 177–205 (2006). https://doi.org/10.1007/s10107-006-0706-8
  34. [34]Nutini, J., Schmidt, M., Hare, W.: Active-set complexity of proximal gradient: How long does it take to find the sparsity pattern? Optimization Letters 13, 645–655 (2019). https://doi.org/10.1007/s11590-018-1325-z
  35. [35]Qin, J., Lou, Y.F.: ℓ₁−₂ regularized logistic regression. In: Proceedings of the 53rd Asilomar Conference on Signals, Systems, and Computers, pp. 779–783 (2019). https://doi.org/10.1109/IEEECONF44664.2019.9048830
  36. [37]Simon, N., Friedman, J., Hastie, T., Tibshirani, R.: A sparse-group lasso. Journal of Computational and Graphical Statistics 22(2), 231–245 (2013). https://doi.org/10.1080/10618600.2012.681250
  37. [38]Tao, M.: Minimization of L₁ over L₂ for sparse signal recovery with convergence guarantee. SIAM Journal on Scientific Computing 44(2), A770–A797 (2022). https://doi.org/10.1137/20M136801X
  38. [39]Tao, M., Zhang, X.-P.: Study on L₁ over L₂ minimization for nonnegative signal recovery. Journal of Scientific Computing 95(3), Article 94 (2023). https://doi.org/10.1007/s10915-023-02225-2
  39. [40]Tao, M., Zhang, X.-P.: A complexity analysis framework for active manifold identification with applications to L₀ and Lₚ regularization models. Applied Mathematics & Optimization 93, Article 50 (2026). https://doi.org/10.1007/s00245-026-10410-6
  40. [41]Tao, M., Zhang, X.P., Xia, Z.H.: On partial smoothness, activity identification and faster algorithms of L₁ over L₂ minimization. IEEE Transactions on Signal Processing 72, 2874–2889 (2024). https://doi.org/10.1109/TSP.2024.3404250
  41. [42]Themelis, A., Stella, L., Patrinos, P.: Forward-backward envelope for the sum of two non-convex functions: Further properties and nonmonotone linesearch algorithms. SIAM Journal on Optimization 28(3), 2274–2303 (2018). https://doi.org/10.1137/16M1080240
  42. [43]Tibshirani, R.: Regression Shrinkage and Selection via the Lasso. Journal of the Royal Statistical Society: Series B 58(1), 267–288 (1996). https://doi.org/10.1111/j.2517-6161.1996.tb02080.x
  43. [44]Wang, H., Yang, X.Y., Zhu, Y.C.: Alternating iteratively reweighted ℓ₁ and subspace Newton algorithms for nonconvex sparse optimization. arXiv preprint arXiv:2407.17216 (2024).
  44. [45]Wu, Y.Q., Pan, S.H., Yang, X.Q.: A Regularized Newton Method for ℓq-Norm Composite Optimization Problems. SIAM Journal on Optimization 33(3), 1676–1706 (2023). https://doi.org/10.1137/22M1482282
  45. [46]Xu, Z., Chang, X., Xu, F., Zhang, H.: L₁/₂ Regularization: A Thresholding Representation Theory and a Fast Solver. IEEE Transactions on Neural Networks and Learning Systems 23(7), 1013–1027 (2021). https://doi.org/10.1109/TNNLS.2021.2917412
  46. [47]Zeng, L., Yu, P., Pong, T.K.: Analysis and algorithms for some compressed sensing models based on L₁/L₂ minimization. SIAM Journal on Optimization 31(2), 1576–1603 (2021). https://doi.org/10.1137/20M1355380
  47. [48]Zhang, Y.: Theory of compressive sensing via ℓ₁-minimization: A non-RIP analysis and extensions. Journal of the Operations Research Society of China 1(1), 79–105 (2013). https://doi.org/10.1007/s40305-013-0010-2
  48. [49]Zhang, S., Xin, J.: Minimization of Transformed L₁ Penalty: Closed Form Representation and Iterative Thresholding Algorithms. Communications in Mathematical Sciences 15(2), 511–537 (2017). https://doi.org/10.4310/CMS.2017.v15.n2.a9
  49. [50]Zhao, J., Doikov, N., Lucchi, A.: Cubic regularized subspace Newton for non-convex optimization. Proceedings of the 28th International Conference on Artificial Intelligence and Statistics, Proceedings of Machine Learning Research 258, 811–819 (2025).arxiv.org/abs/2406.16666
  50. [51]Zou, H., Hastie, T.: Regularization and Variable Selection via the Elastic Net. Journal of the Royal Statistical Society: Series B 67(2), 301–320 (2005). https://doi.org/10.1111/j.1467-9868.2005.00503.x

Paper details

vlnc:W_mbperxam
Version
v1 · latest
Published
Fresh — added to the Hub within the last 30 days
Added
License
CC BY 4.0
Usage

views · 3

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