Greedy Sparsity-Constrained Optimization

Sohail Bahmani; Bhiksha Raj; Petros Boufounos

Source-linked AI summary

Greedy Sparsity-Constrained Optimization

Sohail Bahmani, Bhiksha Raj, Petros Boufounos

arXiv:1203.5483v3Mar 25, 2012stat.MLmath.NAmath.OCstat.CO

TL;DR

Sparse optimization is well studied for linear models with squared-error loss, but less so for nonlinear or nonquadratic costs. The paper introduces GraSP, a greedy solver analyzed under SRH and SRL conditions. It provides bounded-distance guarantees for sparse optima and studies sparse logistic regression, while noting bounded-parameter assumptions in many prior ℓ1 results.

Problem
Sparse optimization theory has focused largely on linear models with squared-error fidelity, leaving nonlinear and nonquadratic cost functions less studied.
Method
GraSP greedily selects large-gradient coordinates, minimizes the cost over their union with the current support, and hard-thresholds the result to s terms.
Results
Under SRH or SRL, GraSP is guaranteed to produce a sparse vector within bounded distance of the true sparse optimum.
Takeaways & Limitations
The framework extends sparse-recovery guarantees beyond quadratic costs and applies concretely to ℓ2-regularized logistic loss.
Takeaways & Limitations
Many prior ℓ1-regularization guarantees implicitly require the true parameter to be bounded.

Abstract

from arXiv · show

Sparsity-constrained optimization has wide applicability in machine learning, statistics, and signal processing problems such as feature selection and compressive Sensing. A vast body of work has studied the sparsity-constrained optimization from theoretical, algorithmic, and application aspects in the context of sparse estimation in linear models where the fidelity of the estimate is measured by the squared error. In contrast, relatively less effort has been made in the study of sparsity-constrained optimization in cases where nonlinear models are involved or the cost function is not quadratic. In this paper we propose a greedy algorithm, Gradient Support Pursuit (GraSP), to approximate sparse minima of cost functions of arbitrary form. Should a cost function have a Stable Restricted Hessian (SRH) or a Stable Restricted Linearization (SRL), both of which are introduced in this paper, our algorithm is guaranteed to produce a sparse vector within a bounded distance from the true sparse optimum. Our approach generalizes known results for quadratic cost functions that arise in sparse linear regression and Compressive Sensing. We also evaluate the performance of GraSP through numerical simulations on synthetic data, where the algorithm is employed for sparse logistic regression with and without $\ell_2$-regularization.

1. Introduction

High-dimensional, underdetermined problems often require sparse parameter estimation, but nonlinear and nonquadratic settings have received less attention. The paper proposes GraSP with guarantees under SRH or SRL conditions.

Motivation: Sparse structure helps make high-dimensional inference tractable when samples are fewer than features.Such structure supports robust regression, hypothesis testing, model reduction, variable selection, and efficient signal acquisition.
Research gap: Sparse estimation in nonlinear models has received comparatively little attention than sparse estimation in linear models.Prior work commonly extends ℓ1-regularization from linear regression to nonlinear models.
Contribution: GraSP is a greedy algorithm for sparse estimation with general nonlinear models and arbitrary cost functions.The paper presents this work as an extended version with improved guarantees over prior work.
Contribution: Under SRH or SRL conditions, GraSP has accuracy guarantees for smooth and non-smooth cost functions.SRH concerns well-conditioned Hessians on sparse canonical subspaces, while SRL provides an analogous condition for non-smooth functions.
Application: The paper also proves SRH for ℓ2-penalized logistic loss.

2. Background

Compressed Sensing established sparse recovery for underdetermined linear measurements, but its squared-error framework and common convex approaches impose computational or modeling limitations. Prior nonlinear-model methods often rely on ℓ1-regularization and bounded-parameter assumptions.

Sparse linear regression and Compressed Sensing: Compressed Sensing estimates sparse vectors from noisy linear measurements y = Ax⋆ + e with n ≪ p.The standard formulation seeks the sparsest estimate consistent with the measurements.
Sparse linear regression and Compressed Sensing: Exact sparse recovery in noiseless settings can follow when every 2s columns of A are linearly independent, but the ideal solver is generally NP-hard.
Sparse linear regression and Compressed Sensing: ℓ1-norm minimization provides a polynomial-time convex proxy for ℓ0-norm minimization, but its guarantees generally require n = O(s log p/s) measurements.Ideally, n = O(s) measurements would suffice for estimating x⋆.
Sparse linear regression and Compressed Sensing: Greedy pursuits iteratively use residual errors to identify nonzero positions and estimate their values, with accuracy guarantees requiring more stringent conditions.
Sparse linear regression and Compressed Sensing: RIP is a principal condition used to guarantee accurate Compressed Sensing recovery.Other conditions include incoherence and the Nullspace Property.
Beyond linear models: Squared error is appropriate for many signal-acquisition applications but not for all estimation and prediction problems, including logistic-loss settings.This motivates theory and algorithms for broader sparsity-constrained optimization problems.
Beyond linear models: Prior nonlinear-model studies mostly use convex costs with ℓ1-regularization, whose solution sparsity is not generally known to be optimal.
Beyond linear models: Many ℓ1-regularization guarantees implicitly assume that the true parameter is bounded.Examples include assumptions involving parameter length or containment inside the unit ball.

3. Problem Formulation and the GraSP Algorithm

The paper formulates sparse optimization for general cost functions and proposes GraSP, whose guarantees rely on restricted curvature conditions. It describes the iterative support-pursuit procedure and states accuracy results for smooth and nonsmooth objectives.

3. Problem Formulation and the GraSP Algorithm: The target is to approximately minimize a general cost function subject to an ℓ0 sparsity constraint.This extends the squared-error formulation used in standard compressed sensing.
3.1 Algorithm Description: GraSP generalizes CoSaMP by using cost-function gradients to identify promising support directions before restricted minimization and pruning.The method merges the current support with the 2s largest gradient coordinates, minimizes over at most 3s indices, and retains the best s-term approximation.
3.2 Sparse Reconstruction Conditions: SRH and SRL bound the cost function’s restricted curvature through Hessian or Bregman-divergence conditions analogous to RIP, RSC, and RSS.For squared-error objectives, SRH is essentially equivalent to RIP; SRH constrains sparse subspaces without requiring global convexity.
3.1 Algorithm Description: Each iteration evaluates the gradient, selects 2s largest-magnitude coordinates, merges supports, minimizes on the combined support, and hard-thresholds the estimate.The algorithm halts when the objective or estimated minimizer changes sufficiently little.
3.1 Algorithm Description: Restricted Newton and restricted gradient-descent variants reduce the support-restricted minimization, with the latter reducing to IHT for squared error.The restricted Newton step requires an invertible restricted Hessian.
3.3 Main Theorems: Theorem 1 gives GraSP accuracy guarantees for twice continuously differentiable functions satisfying an appropriate SRH condition.The theorem assumes a bound on the SRH constant, while the associated error depends on the sparse optimum’s gradient behavior.
3.3 Main Theorems: The gradient at the sparse target determines the accuracy floor, which becomes negligible when that target is sufficiently close to an unconstrained minimum.For statistical targets that are not empirical-loss minimizers, the restricted gradient term has a statistical interpretation and can determine precision.

4. Example: Sparse Minimization of ℓ2-regularized Logistic Regression

The paper analyzes sparse minimization for ℓ2-regularized logistic regression, whose regularization ensures strong convexity while explicit sparsity constraints remain necessary. It verifies the SRH condition using Hessian bounds and matrix concentration under additional assumptions.

Logistic regression formulation: The logistic loss can be non-unique or approach arbitrarily small values along diverging parameters in underdetermined or linearly separable problems.An ℓ2 penalty makes the objective η-strongly convex, yielding a unique, bounded minimizer, but does not itself promote sparsity.
Verifying SRH: The ℓ2-regularized logistic Hessian is bounded above by 1/4n A^T A, while the regularizer contributes ηI to the Hessian.For any displacement ∆, the resulting quadratic form is bounded by 1/4n ||A∆||_2^2 + η||∆||_2^2.
Verifying SRH: Matrix Chernoff bounds are used to control ||A∆||_2^2 over sparse directions and establish SRH with high probability.The proof applies concentration to sums of independent positive semidefinite matrices and then uses a union bound over index sets.
SRH guarantee: Under assumptions on the random design, the ℓ2-regularized logistic loss has SRH constant µ_k bounded by 1 + 1/(1+τ) with probability at least 1 − ε.The stated guarantee applies for τ > 0 and ε ∈ (0, 1), with the sample-size condition expressed through the surrounding bound.
Sample-size implications: When k and p grow while p choose k remains constant, sufficiently many observations can yield small failure rates, although the required order may depend on R and therefore k.Additional structure such as independent sub-Gaussian entries can permit a better rate without the stated techniques.
Approximation error: The approximation error is controlled through the gradient restricted to the target support, and the analysis extends to GLMs with bounded second derivatives.For such GLMs, the error can be bounded using the variance of v_ψ = ψ′(⟨a, x⋆⟩) − y.

5. Experimental Results

The experiments compare GraSP variants with LASSO, elastic net, and Logit-OMP on synthetic and real-data sparse logistic regression. Regularization and debiasing improve GraSP’s relative-error performance, while loss behavior depends on the sampling ratio and dataset.

Synthetic Data: The synthetic study compares GraSP, ℓ2-regularized GraSP, LASSO, elastic net, Logit-OMP, and debiased GraSP variants across sampling ratios.Performance is averaged over 200 trials for each (n, ρ) pair.
Synthetic Data: At n/p > 0.7, unregularized GraSP’s empirical logistic loss becomes effectively identical to the loss at the true parameter.At lower sampling ratios, GraSP is inaccurate and may not converge because the loss can vary sharply near linearly separable data.
Synthetic Data: At low sampling ratios, GraSP+ℓ2 is consistently closer to the true loss than the other methods, while at high ratios unregularized GraSP is consistently closer.ℓ2 regularization stabilizes GraSP at low sampling ratios but introduces high-ratio loss bias; debiasing reduces this bias for the regularized variant.
Synthetic Data: With ℓ2 regularization, GraSP achieves better relative error than GLMnet and ordinary GraSP across almost the entire tested sampling-ratio range.Debiasing improves both GraSP methods except at very low sampling ratios, and these variants generally outperform Logit-OMP.
Real Data: On DEXTER, non-debiased GraSP variants and convex methods have comparable losses, whereas debiased GraSP methods attain the smallest losses in both DEXTER and ARCENE except for a few Logit-OMP cases.Convex methods perform significantly better on ARCENE.

6. Discussion and Conclusion

The paper introduces GraSP as a greedy approximate solver for sparsity-constrained optimization beyond quadratic linear models. Its guarantees use SRH or SRL conditions, while its computational cost becomes a limitation at very large scale.

Discussion and Conclusion: GraSP is a greedy approximate solver for a wide range of sparsity-constrained optimization problems.The method is intended for settings involving general nonlinear models.
Discussion and Conclusion: SRH and SRL provide convergence guarantees for smooth and non-smooth cost functions, respectively, and generalize RIP-style conditions beyond squared-error objectives.The paper gives ℓ2-regularized logistic loss as a concrete SRH example.
Discussion and Conclusion: GraSP generalizes CoSaMP from linear squared-error recovery to broader sparsity-constrained cost functions.The extension covers loss functions with Lipschitz-continuous gradients through SRH verification.
Discussion and Conclusion: For very large input dimension p, function and gradient evaluations dominate GraSP’s running time; randomization is proposed as future work to reduce this cost.At medium and large scale, the inner convex optimization step has complexity polynomial in sparsity s.

Appendix A. Iteration Analysis For Smooth Cost Functions

The smooth-cost analysis builds an iteration-invariant error bound for GraSP by combining propositions about restricted Hessian behavior with lemmas for successive estimates. Under the SRH condition, this invariant is applied recursively to obtain the theorem.

Proof structure: The proof architecture derives propositions, then lemmas, then an iteration invariant that yields the main result.The invariant relates the current and next iteration's estimation errors.
Restricted Hessian tools: Proposition 1 bounds quadratic forms using eigenvalue intervals for symmetric positive-definite matrix-valued functions.The eigenvalues lie in [B(t), A(t)] with B(t) > 0.
Restricted Hessian tools: The intermediate vector b is characterized by vanishing restricted gradient, ∇f(b)|T = 0, enabling Hessian-based control of x⋆ − b.The analysis uses invertibility of an integrated restricted Hessian matrix W.
Iteration invariant: Lemma 3 states an iteration-invariant inequality relating the current error ∥b̂x − x⋆∥2 to the next error ∥b̂s − x⋆∥2.This relation is obtained after combining bounds on the intermediate estimate and its best s-term approximation.
Theorem derivation: For functions satisfying μk-SRH, the restricted parameters are ordered with sparsity level, and Lemma 3 is applied recursively across iterates.The theorem proof uses monotonicity of αk, βk, and μk together with recursive application of the invariant.

Appendix B. Iteration Analysis For Non-Smooth Cost Functions

The non-smooth-cost analysis replaces Hessian arguments with restricted Bregman-divergence inequalities under the SRL assumption. These inequalities support lemmas for successive estimates, an iteration invariant, and a recursively derived theorem.

SRL framework: For non-smooth functions, αk(x) and βk(x) characterize restricted bounds used to analyze sparse perturbations.The analysis applies these bounds to vectors whose combined support with x has size at most k.
SRL framework: Propositions 3, 4, and 5 establish inequalities for restricted Bregman divergences under the SRL assumption.The propositions use sparse-support subsets and relations between gradients at two points.
SRL framework: The proof derives the Bregman inequalities by combining bounds at perturbed points and requiring the resulting quadratic expressions to have nonpositive discriminants.This argument is applied for arbitrary real t.
Iteration invariant: Lemma 6 relates the current iterate's estimation error to the next iterate's estimation error under the non-smooth analysis.The result follows from Lemmas 4 and 5 together with support containment and best s-term approximation arguments.
Theorem derivation: Theorem 2 applies Lemma 6 recursively when the SRL parameter satisfies μ4s ≤ 3+, yielding the stated result.The proof indexes vectors by iteration and repeatedly applies the invariant.