Research map / Optimization / Nonconvex and smooth optimization
Smoothing Proximal Gradient Methods for Nonsmooth Sparsity Constrained Optimization: Optimality Conditions and Global Convergence
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Proposes smoothing proximal gradient methods (SPGM-IHT and SPGM-BCD) for nonsmooth sparsity-constrained optimization, with optimality hierarchy results and global convergence rate analysis.
Problem
Nonsmooth sparsity-constrained optimization (non-convex, NP-hard) where existing methods cannot handle general nonsmooth objectives, yield weak optimality conditions, or lack comprehensive convergence analysis.
Approach
Smooths the nonsmooth term via a Moreau-envelope-style penalty on the linear constraint Ax-b=y and solves the resulting smooth sparse problem with either an IHT or a block-coordinate (k-subset enumeration) majorization step, giving block-k stationary points and global convergence rates matching the best known bounds.
Key results
- SPGM-BCD attains block-k stationary points, which are stronger than Lipschitz stationary points of IHT-style methods (optimality hierarchy from Proposition 1).
- Convergence bounds O(1/T)+O(ln(T)/T)+irreducible error with L_F||x̄|| for SPGM-IHT and 3L_F||x̄|| for SPGM-BCD.
- Numerical experiments: SPGM-IHT performs comparably to IHT-style methods while SPGM-BCD consistently surpasses them.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| use SPGM-IHT instead of existing IHT-style methods | nonsmooth sparsity constrained optimization · Two nonsmooth sparsity constrained optimization tasks | numerical performance | No clear effect |
| use SPGM-BCD instead of the compared nonsmooth sparsity constrained optimization algorithms | nonsmooth sparsity constrained optimization · Two nonsmooth sparsity constrained optimization tasks | numerical performance | Helped |
Limitations
- SPGM-BCD's deterministic block-k stationary point requires enumerating C(n,k) subproblems; randomized selection needed in practice.
- Irreducible error term 3L_F||x̄|| in the SPGM-BCD bound is three times that of the PSGD bound.
- Analysis relies on restricted strong convexity and smoothness assumptions over s-sparse vectors.
Experimental setup
Metrics: objective value convergence rate bounds
Baselines: PSGD ADMM-IHT DIHT CVX-l1 NCVX-lp
Builds on: iterative hard thresholding penalty decomposition methods dual iterative hard thresholding Moreau-Yosida approximation
Closest papers by meaning
- Non-asymptotic Analysis of Stochastic Methods for Non-Smooth Non-Convex Regularized Problems (NeurIPS 2019 · similarity 0.90)
- Dual Iterative Hard Thresholding: From Non-convex Sparse Minimization to Non-smooth Concave Maximization (ICML 2017 · similarity 0.89)
- A Feasible Level Proximal Point Method for Nonconvex Sparse Constrained Optimization (NeurIPS 2020 · similarity 0.88)
- Methods for Convex $(L_0,L_1)$-Smooth Optimization: Clipping, Acceleration, and Adaptivity (ICLR 2025 · similarity 0.87)
- A Bregman Proximal Stochastic Gradient Method with Extrapolation for Nonconvex Nonsmooth Problems (AAAI 2024 · similarity 0.86)
- Optimizing $(L_0, L_1)$-Smooth Functions by Gradient Methods (ICLR 2025 · similarity 0.86)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.