PaperlayerView exact revision on arXiv

Source-linked AI summary

On Iterative Hard Thresholding Methods for High-dimensional M-Estimation

Prateek Jain, Ambuj Tewari, Purushottam Kar

arXiv:1410.5137v2cs.LGstat.ML

TL;DR

High-dimensional estimation can be statistically feasible under sparsity or low-rank structure, but existing IHT analyses require restrictive conditions that often fail in statistical settings. The paper develops an RSC/RSS-based framework for IHT-style and fully corrective methods, proving tight global-convergence guarantees that apply to sparse and low-rank regression.

  • Problem

    Existing analyses of scalable PGD/IHT methods rely on restrictive RIP or condition-number assumptions that do not accommodate common high-dimensional statistical settings with arbitrarily correlated variables.

  • Method

    The paper analyzes IHT-style and fully corrective hard-thresholding algorithms for arbitrary differentiable objectives satisfying RSC/RSS conditions, using enlarged support projections.

  • Results

    The resulting guarantees are tight, match known minimax lower bounds, and establish global convergence for sparse linear regression, low-rank matrix regression, and noisy settings.

  • Takeaways & Limitations

    IHT-style methods are shown to be applicable to high-dimensional statistical estimation while retaining competitive recovery and sometimes much faster runtime than convex or greedy alternatives.

  • Takeaways & Limitations

    The guarantees require restricted strong convexity and smoothness conditions, even though the condition number itself may be arbitrarily large.

Abstract

from arXiv · show

The use of M-estimators in generalized linear regression models in high dimensional settings requires risk minimization with hard $L_0$ constraints. Of the known methods, the class of projected gradient descent (also known as iterative hard thresholding (IHT)) methods is known to offer the fastest and most scalable solutions. However, the current state-of-the-art is only able to analyze these methods in extremely restrictive settings which do not hold in high dimensional statistical models. In this work we bridge this gap by providing the first analysis for IHT-style methods in the high dimensional statistical setting. Our bounds are tight and match known minimax lower bounds. Our results rely on a general analysis framework that enables us to analyze several popular hard thresholding style algorithms (such as HTP, CoSaMP, SP) in the high dimensional regression setting. We also extend our analysis to a large family of "fully corrective methods" that includes two-stage and partial hard-thresholding algorithms. We show that our results hold for the problem of sparse regression, as well as low-rank matrix recovery.

1 Introduction

High-dimensional estimation can be statistically possible under sparsity or low-rank structure, but efficient methods face computational and analytical barriers. This work analyzes IHT-style methods under RSC/RSS conditions, extending guarantees to broad statistical settings and algorithms.

  • When p greatly exceeds n, consistent estimation can remain information-theoretically possible under sparsity or low-rank assumptions.
  • Sparse and low-rank estimation often involves NP-hard constrained optimization, motivating scalable alternatives.
  • Convex relaxations can have slow rates, while greedy methods become slow when sparsity or rank is relatively high.
  • PGD/IHT methods efficiently project onto sparsity and low-rank feasible sets, but traditional convex analyses do not cover their non-convex structure.
  • Prior hard-thresholding analyses relied on restrictive RIP or condition-number requirements that are incompatible with arbitrarily correlated variables in high-dimensional statistical settings.Existing guarantees can fail when the restricted condition number is large, and many analyses focus only on least-squares objectives.
  • The paper provides global convergence guarantees for IHT-style algorithms under RSC/RSS, including arbitrary differentiable objectives and arbitrarily large condition numbers.The framework covers IHT, GraDeS, CoSaMP, SP, and OMPR, and uses enlarged support projections to relax prior requirements.
  • The results extend to sparse linear regression, low-rank matrix regression, noisy settings, and fully corrective hard-thresholding methods.The reported bounds match known minimax lower bounds, while experiments find competitive recovery and sometimes orders-of-magnitude runtime advantages over convex and greedy methods.

2 Problem Setup and Notations

The paper formulates sparse estimation as empirical-risk minimization over sparse parameters and extends the setup to low-rank matrix regression. Its analysis assumes differentiability together with restricted strong convexity and smoothness.

  • High-dimensional sparse estimation seeks an s∗-sparse parameter using observations X_i ∈ R^p and responses Y_i ∈ R.
  • The objective is typically an empirical risk formed by averaging a loss over the observed data.
  • The analysis requires differentiability plus restricted strong convexity and restricted strong smoothness, rather than additional properties of the objective.
  • Low-rank matrix regression replaces vector covariates with matrices and estimates a low-rank matrix by minimizing empirical loss.
  • For matrix regression, the RSC/RSS definitions are adapted by replacing the L0 norm with matrix rank.

3 Iterative Hard-thresholding Method

The paper analyzes projected gradient descent and iterative hard-thresholding methods under RSC/RSS conditions, including sparse and low-rank settings. It identifies stronger hard-thresholding behavior when the projection sparsity or rank exceeds the target complexity.

  • Sparse-vector IHT: The sparse-vector projection P_s selects the s largest-magnitude entries and can be implemented efficiently.
  • Sparse-vector IHT: When s* ≪ s, hard thresholding satisfies a stronger approximation property than its standard projection guarantee.This property is formalized in Lemma 1 and underpins the IHT analysis.
  • Sparse-vector IHT: RSC/RSS combined with the hard-thresholding property yields geometric convergence rates for IHT.
  • Low-rank matrix regression: Low-rank matrix regression uses an analogous projected-gradient analysis with matrix hard thresholding based on singular-value decomposition.The proof replaces coordinate restrictions with subspace restrictions and uses the corresponding matrix thresholding lemma.
  • Low-rank matrix regression: The low-rank convergence result replaces vector projection with the matrix operator P_Ms under corresponding RSC/RSS conditions.

4 High Dimensional Statistical Estimation

The paper develops generic high-dimensional convergence and statistical guarantees for IHT-style methods under RSC/RSS, including nonconvex losses and noisy or missing data. These results are specialized to sparse linear regression and related estimation settings.

  • Generic guarantees: A generic theorem applies IHT when the loss is differentiable and satisfies RSC/RSS at sparsity level s+s*.The theorem allows the loss function to be nonconvex.
  • Sparse linear regression: For sparse linear regression, sub-Gaussian covariates provide RSC/RSS with high probability under a sample-size condition.
  • Sparse linear regression: The resulting sparse-regression conditions control the RSC/RSS ratio through the covariance condition number κ(Σ).The passages give L_k/(9α_k) ≤ κ(Σ) and choose s proportional to κ(Σ)^2s*.
  • Noisy and missing data: The framework extends to feature noise and missing data, including additive Gaussian noise modeled through unbiased estimators of covariance and cross-covariance.
  • Noisy and missing data: For the noisy setting, the analysis retains RSC/RSS guarantees and permits application of the generic theorem even when the loss is nonconvex.

5 Fully-corrective Methods

The paper develops RSC/RSS-based analyses for fully corrective hard-thresholding methods, including two-stage and partial hard-thresholding algorithms. These methods use enlarged supports or partial projections to obtain convergence guarantees beyond restrictive RIP analyses.

  • Fully-corrective methods: Fully corrective methods minimize the objective over the current iterate's support and include algorithms such as CoSaMP and Subspace Pursuit.The framework targets general loss functions under RSC/RSS conditions rather than only least-squares objectives under RIP.
  • Two-stage Hard Thresholding Methods: The two-stage analysis relies on the observation that hard thresholding does not increase the objective function substantially.This supports a generic RSC/RSS analysis for two-stage methods with arbitrary loss functions.
  • Partial Hard Thresholding Methods: Partial hard thresholding projects onto s-sparse vectors while allowing at most ℓ newly selected support elements.The projection is computed efficiently by hard thresholding only over the coordinates outside the current support.
  • Partial Hard Thresholding Methods: Each IPHT(ℓ) iteration either reaches the target objective value or adds at least one new support element.This property is established under stated RSC/RSS conditions and sparsity requirements.
  • Partial Hard Thresholding Methods: Theorem 5 gives convergence for IPHT(ℓ), with the τ-th iterate satisfying f(θτ) − f(θ∗) ≤ ϵ.The guarantee assumes RSC/RSS parameters and a sufficiently large algorithmic sparsity level s.

6 Experiments

Experiments on high-dimensional sparse linear regression compare hard-thresholding methods with L1 and greedy baselines across recovery, dimensionality, sparsity, and conditioning. Hard-thresholding methods achieve comparable or better recovery with substantially shorter runtimes.

  • Evaluation: All evaluated algorithms recovered the support set within 2% at the baseline noise level σ = 0.1.The experiments therefore emphasized runtime comparisons for the baseline setting.
  • Runtime and recovery: 150× faster: HTP outperformed L1 at p = 20000 while achieving exact support recovery; the gap exceeded 350× at higher p.L1 missed 2 and 4 support elements in the two reported dimensionality settings.
  • Runtime and recovery: Hard-thresholding methods were as effective as L1 and greedy methods for recovery under noisy settings while being more efficient and scalable.The comparison included HTP, GraDeS, CoSaMP, OMPR, SP, L1, and FoBa.
  • Runtime and recovery: 60 −75× slower: FoBa lagged HTP at true sparsity levels s∗ = 300 and 500.HTP converged in fewer than 5 iterations, whereas FoBa used 300 and 500 iterations respectively.
  • Ill-conditioned problems: At condition number κ = 50, increasing the projected sparsity level improved recovery properties for IHT-style algorithms.The experiment varied projected sparsity while keeping p, s∗, and σ at baseline levels.

7 Discussion and Conclusions

The paper provides global convergence guarantees for a broad family of IHT-style methods under RSC/RSS conditions, including arbitrary differentiable and possibly non-convex objectives. Enlarged support sizes remove restrictive condition-number requirements, while experiments show major runtime advantages and comparable or better recovery.

  • Contributions: The analysis covers IHT, GraDeS, CoSaMP, SP, and OMPR for differentiable objectives satisfying RSC/RSS conditions.The guarantees apply even when the objective is possibly non-convex.
  • Key insight: Running the algorithms with an enlarged support size is the central insight enabling strong contraction and unified hard-thresholding analyses.The same framework yields high-dimensional M-estimation guarantees through established RSC/RSS results.
  • Empirical conclusions: Hard-thresholding methods outperform convex-relaxation and greedy methods in runtime, sometimes by orders of magnitude, while maintaining competitive or better recovery.The reported scope includes sparse and low-rank structures.
  • Scope: The results cover sparsity and low-rank structure, while broader structures remain a direction for future work.The paper points to decomposability and atomic-norm frameworks as possible connections for such extensions.

A Proofs for Section 3

The appendix proofs establish projection and support relations used to analyze IHT-style iterations. They combine hard-thresholding properties with RSC/RSS inequalities to control successive iterates and derive convergence conditions.

  • Projection properties: Hard thresholding selects the s coordinates of largest magnitude and sets all remaining coordinates to zero.This projection property underlies the approximation comparisons used in the proofs.
  • Support bookkeeping: The proof tracks the union It = S∗ ∪ St ∪ St+1 to apply RSS over the supports of the target and consecutive iterates.Both current and next iterates are supported within this union.
  • Convergence proof: The proofs combine the gradient-step identity, hard-thresholding comparisons, and RSC/RSS inequalities to bound successive objective or iterate terms.These inequalities are then rearranged under the selected step-size and sparsity conditions.
  • Support bookkeeping: The support analysis bounds the relevant union by s + 2s∗, enabling the RSC-based control of the next iterate.The set construction separates newly added, removed, and target support elements.
  • Projection properties: The projection argument uses the fact that the hard-thresholded vector is no farther from the target than the unprojected update.This comparison completes the relevant approximation bound.

B Proofs for Section 4

The proofs derive estimation bounds by combining empirical-loss optimality, restricted strong convexity, and duality, then solving a quadratic inequality.

  • The proof begins with the empirical loss minimizer over the set of s-sparse vectors.
  • Restricted strong convexity supplies one inequality for the estimation analysis, using sparsity of θ∗ and θτ.
  • Duality provides an upper bound that is combined with the preceding inequalities.
  • The combined inequalities are rearranged into a quadratic inequality in ∥θ̄ − θτ∥2, which immediately yields the result.

C Proofs for Section 5

The proofs analyze hard-thresholding and fully corrective updates through restricted smoothness or sparsity-based inequalities, support-set case analysis, and a condition relating s, ℓ, and s∗.

  • The analysis introduces a general result for any γ ≥ 1 before deriving the stated lemma as a corollary.
  • Fully corrective updates are analyzed through missing true-support elements MDt and incorrect active elements FAt.
  • Several inequalities use disjointness of MDt and FAt and norm properties to obtain the desired bounds.
  • The proof uses restricted strong or smoothness properties to control thresholding updates and objective values.
  • The theorem follows under the assumption s + ℓ − s∗ ≥ 4L^2·ℓ.
  • The support-update argument separates mutually exclusive cases according to the number of selected elements and their relation to the true support.

D Supplementary Experimental Results

The supplementary material presents additional plots, including algorithm counterparts and runtime behavior as sample sizes increase relative to s∗·log p.

  • The supplementary material contains plots omitted from the main text.
  • Figure 2 provides counterparts of Figure 1 for OMPR, CoSaMP, and L1.
  • Figure 3 examines the effect of increasing sample sizes relative to the base value s∗·log p on runtime.
Loading 1410.5137v2…