Research map / Optimization / Nonconvex and smooth optimization
Optimization over Sparse Support-Preserving Sets: Two-Step Projection with Global Optimality Guarantees
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 IHT with a two-step projection (hard-threshold then project onto support-preserving convex set) and proves global objective-value guarantees in deterministic, stochastic, and zeroth-order settings via a constrained l0 three-point lemma.
Problem
Sparse optimization with l0 hard sparsity constraints plus extra convex constraints; prior methods need closed-form mixed projections or give only local convergence guarantees.
Approach
A two-step projection (hard-thresholding to k largest entries, then Euclidean projection onto a k-support-preserving convex set) replaces the mixed Euclidean projection; an extended three-point lemma yields global objective-value bounds with a tunable trade-off between sparsity relaxation and sub-optimality factor (1+2rho).
Key results
- Deterministic IHT-2SP guarantees min_t R(w_t) <= (1+2rho)R(wbar)+eps with k >= O(kappa^2 kbar/rho^2)
- Zeroth-order HZO-HT-2SP removes the non-vanishing system error present in prior ZO hard-thresholding results (apart from smoothing error mu)
- Synthetic experiments illustrate the sparsity-optimality trade-off controlled by rho
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Add two-step projection for support-preserving constraints | IHT · Deterministic sparse optimization with support-preserving constraints | objective upper bound: R \left(\vw_{\hat{T}}\right)\leq (1+2 \rho) R (\bar{\vw})+ \varepsilon | Helped |
| Add two-step projection for support-preserving constraints | Stochastic IHT · Stochastic sparse optimization with support-preserving constraints | expected objective upper bound: \mathbb{E} R(\vw_{\hat{T}}) \leq (1 + 2\rho) R(\bar{\vw}) + \varepsilon | Helped |
| Use exponentially increasing random-direction batches and two-step projection | Zeroth-order hard-thresholding · Zeroth-order sparse optimization | expected objective gap: HZO-HT: \mathcal{O}(\Delta); HZO-HT-2SP: \mathcal{O}(\mu) | Helped |
| Decrease \rho toward 0 (ablation) | IHT-2SP · Deterministic sparse optimization with support-preserving constraints | objective upper bound: (1+2 \rho) R(\bar{\vw})+ \varepsilon | Helped |
| Decrease \rho toward 0 (ablation) | IHT-2SP · Deterministic sparse optimization with support-preserving constraints | required sparsity level: k\geq \frac{4(1-\rho)^2L_s^2}{\rho^2\nu_s^2}\bar k | Hurt |
| Set \rho=0.5 when the comparator is a global minimizer (ablation) | IHT-2SP · Deterministic sparse optimization with support-preserving constraints | objective upper bound: \min _{t \in[T]} R\left(\vw_{t}\right) \leq R(\bar{\vw})+ \varepsilon | Helped |
Limitations
- Guarantees are for objective value under RSC/RSS, with sparsity relaxation k = Omega(kappa^2 kbar/rho^2) needed
- Output is (1+2rho) multiplicative sub-optimal unless the comparator is a global minimizer over the l0 ball
- Zeroth-order results retain a smoothing error term mu
Experimental setup
Metrics: objective value suboptimality convergence rate
Baselines: IHT stochastic IHT zeroth-order IHT projected gradient descent with mixed constraints
Builds on: iterative hard thresholding relative concavity of hard thresholding (Lemma 4.1) HSG-HT stochastic IHT zeroth-order hard thresholding
Closest papers by meaning
- A Richer Theory of Convex Constrained Optimization with Reduced Projections and Improved Rates (ICML 2017 · similarity 0.90)
- Sparse Convex Optimization via Adaptively Regularized Hard Thresholding (ICML 2020 · similarity 0.89)
- On the Convergence of Projected Bures-Wasserstein Gradient Descent under Euclidean Strong Convexity (ICML 2024 · similarity 0.86)
- Zeroth-Order Methods for Constrained Nonconvex Nonsmooth Stochastic Optimization (ICML 2024 · similarity 0.86)
- A Study of First-Order Methods with a Deterministic Relative-Error Gradient Oracle (ICML 2024 · similarity 0.86)
- Stochastic Smoothed Primal-Dual Algorithms for Nonconvex Optimization with Linear Inequality Constraints (ICML 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.