PaperlayerView exact revision on arXiv

Source-linked AI summary

Restricted Strong Convexity Implies Weak Submodularity

Ethan R. Elenberg, Rajiv Khanna, Alexandros G. Dimakis, Sahand Negahban

arXiv:1612.00804v2stat.MLcs.ITcs.LG

TL;DR

Sparse subset selection needs reliable methods for choosing a small feature set from high-dimensional data, while prior weak-submodularity analysis focused on linear regression. This paper connects restricted strong convexity and smoothness to weak submodularity for general objectives, obtaining multiplicative guarantees for greedy methods and broader supported consequences for feature selection.

  • Problem

    Sparse subset selection is computationally difficult, and existing submodularity connections were limited mainly to linear regression rather than arbitrary objective functions.

  • Method

    The paper shows that restricted strong convexity and smoothness imply weak submodularity, then analyzes Oblivious selection, generalized OMP, and Forward Stepwise Regression.

  • Results

    Forward Stepwise Regression achieves a (1 − e^-γ)-approximation and OMP achieves a (1 − e^-m/M)-approximation to the best k-subset.

  • Takeaways & Limitations

    Greedy feature selection receives multiplicative guarantees for broad classes of general likelihood functions and directly controls the number of selected features.

  • Takeaways & Limitations

    The bounds are loose for special cases such as modular functions and linear regression, where additional tools and problem-specific properties are needed.

Abstract

from arXiv · show

We connect high-dimensional subset selection and submodular maximization. Our results extend the work of Das and Kempe (2011) from the setting of linear regression to arbitrary objective functions. For greedy feature selection, this connection allows us to obtain strong multiplicative performance bounds on several methods without statistical modeling assumptions. We also derive recovery guarantees of this form under standard assumptions. Our work shows that greedy algorithms perform within a constant factor from the best possible subset-selection solution for a broad class of general objective functions. Our methods allow a direct control over the number of obtained features as opposed to regularization parameters that only implicitly control sparsity. Our proof technique uses the concept of weak submodularity initially defined by Das and Kempe. We draw a connection between convex analysis and submodular set function theory which may be of independent interest for other statistical learning applications that have combinatorial structure.

1 Introduction

The paper studies sparse subset selection, extending weak-submodularity analysis beyond linear regression to general objective functions. Under restricted strong convexity and smoothness, it derives multiplicative guarantees for greedy feature-selection methods without sparsity assumptions.

  • Motivation: Sparse subset selection seeks the best k features among p candidates, but the optimization is NP-hard even for sparse linear regression.The framework covers objectives including generalized linear-model likelihoods, graphical-model learning objectives, and arbitrary M-estimators.
  • Connection: The paper extends Das and Kempe’s weak-submodularity connection from linear regression to arbitrary objective functions satisfying restricted strong convexity and smoothness.This establishes weak submodularity with parameter γ ≥ m/M under the paper’s restricted conditions.
  • Implications: The results require no assumptions on the sparsity of the underlying problem and directly control the number of selected features, unlike regularization parameters.The paper contrasts this with ℓ1-regularized methods, which require assumptions such as irrepresentability for exact sparsity guarantees.
  • Guarantees: Greedy methods receive multiplicative guarantees relative to the best k-subset: Oblivious achieves γ/k, OMP achieves 1 − e^-m/M, and Forward Stepwise achieves 1 − e^-γ.These methods progressively account for feature interactions while increasing computational cost.
  • Guarantees: Forward Stepwise can approximate the best k-sparse feature performance within arbitrary accuracy when allowed to select more than k features.Under additional assumptions, the paper also derives statistical convergence guarantees for the selected parameter.
  • Implications: Weak submodularity is presented as a sharper technical tool than restricted strong convexity because RSC implies weak submodularity, while some weakly submodular problems do not satisfy RSC.The connection broadens submodular theory’s use in settings where spectral conditions are restrictive or unwarranted.

2 Preliminaries

The paper frames sparse support selection as a combinatorial optimization problem and introduces weak submodularity, restricted curvature conditions, and three greedy selection strategies.

  • Weak submodularity: Weak submodularity extends diminishing-returns analysis through a submodularity ratio, while ordinary submodularity corresponds to ratio at least one.
  • Curvature conditions: Restricted strong concavity and restricted smoothness control objective curvature over sparse domains, with parameters m and M varying systematically with the domain size.
  • Sparse selection: Sparse support selection chooses at most k features from p candidates to optimize a model objective, but the problem is NP-hard even for sparse linear regression.
  • Set-function formulation: A concave objective induces the set function f(S)=maxsupp(x)⊆S l(x)−l(0), making support selection equivalent to maximizing f over sets of size k.
  • Selection algorithms: The Oblivious algorithm selects individually strongest features, Forward Stepwise repeatedly chooses the largest marginal gain, and OMP uses gradient correlations.

3 Approximation Guarantees

The paper bounds weak submodularity using restricted curvature and converts that connection into approximation guarantees for Oblivious, Forward Stepwise, and OMP feature selection.

  • Weak submodularity bound: Restricted strong concavity and smoothness imply a lower bound on the submodularity ratio, extending the RIP-to-weak-submodularity connection beyond linear regression.
  • Oblivious guarantee: The Oblivious algorithm achieves a γ/k-approximation to the best k-subset after k steps.
  • Forward Stepwise guarantee: Forward Stepwise provides a stronger constant-factor approximation under smoothness and strong concavity on the 2k-sparse domain.
  • Extended Forward Stepwise guarantee: Running Forward Stepwise for r=ck steps gives a (1−e^−cγ)-approximation, while r=k log n gives a (1−n^−γ)-approximation.
  • Scope: The bounds can be loose for modular functions and linear regression because sharper results require additional structure-specific tools.
  • OMP guarantee: OMP is more computationally efficient than Forward Stepwise but has a weaker guarantee, while its exponent improves over prior linear-regression analysis by a factor of γ.

4 Statistical Recovery Guarantees

The paper derives parameter-recovery guarantees from objective-approximation bounds and compares them with existing results under linear and logistic regression settings.

  • General recovery result: Parameter-recovery bounds follow by combining an approximate objective guarantee with a general theorem for sparse solutions.
  • Linear regression: Under the stated Gaussian linear-regression setup, parameter error converges to zero with high probability when (s+r)σ^2 log p=o(n) and r=Ω(s log n).
  • Comparison with prior OMP recovery: The paper’s recovery theorem applies for any spike parameter a, whereas Zhang’s comparison requires a≤1/(s+1).
  • Statistical comparison: In the spiked covariance model, the paper’s results are better by a factor of s in statistical accuracy but worse by a factor of log n in sample complexity.
  • Logistic regression: For logistic regression, the approximation guarantee matches prior bounds up to constants, while the recovery theorem holds more generally than a comparison requiring incoherence assumptions.

5 Theorem Proofs

The proofs establish greedy approximation bounds by relating aggregate marginal gains to objective improvements under restricted curvature conditions.

  • Weak submodularity proof: The proof bounds the denominator and numerator of the submodularity-ratio expression using restricted smoothness and strong concavity.
  • Weak submodularity proof: For individual coordinates, the proof compares the optimized one-feature extension with a scaled direction toward the larger support solution.
  • Oblivious guarantee proof: The Oblivious proof constructs a k-sparse vector from singleton solutions and combines multiple applications of the curvature definition.
  • Forward Stepwise proof: Forward Stepwise analysis relates the next greedy gain to the gain from adding the remainder of the optimal set.
  • Forward Stepwise proof: The final Forward Stepwise bound follows the standard approximation argument for normalized, monotone submodular maximization after expressing successive gains through the remainder sequence.

5.5 Proof of Theorem 4

The proof bounds greedy progress by comparing each selected feature’s incremental gain with the remaining gain from the optimal sparse set. It applies smoothness and restricted strong concavity to establish the required approximation relation.

  • Lemma-based bound: The proof first bounds the objective ratio between optimal subsets of consecutive sizes using restricted smoothness and strong concavity.The parameters are evaluated on the relevant sparse domains, with k′ constrained between M′/m and k.
  • Conclusion: Assuming l(β(∅)) = 0, the resulting inequalities can be iterated when M′/m is constant and M′/m < k′ < k.This iteration yields the theorem’s greedy approximation relationship for sufficiently large k.
  • OMP progress: At each OMP iteration, the selected coordinate’s incremental gain is compared with the gain from adding the remaining elements of the optimal set.OMP selects the coordinate maximizing the gradient, which supports the incremental-gain lower bound.
  • OMP progress: The proof expresses the OMP gain through a gradient norm and uses smoothness to relate this quantity to the optimal-set gap.The argument uses the inclusion S ∪ S_R ⊇ S∗ before completing the proof by the same recurrence used for Theorem 3.

5.7 Proof of Theorem 6

This proof derives the theorem’s bound from restricted strong concavity, smoothness, and concentration arguments. It also shows how the resulting conditions apply beyond linear regression to generalized linear models.

  • Proof: The proof applies restricted strong concavity to sparse coefficient differences and rearranges the resulting inequality into the final bound.The argument uses a standard inequality to control cross terms before rearrangement.
  • Probability guarantee: A result from prior work supplies the required probabilistic inequality with probability at least 1 − 1/p.This establishes the high-probability part of the theorem’s guarantee.
  • Condition verification: Although an RIP-type condition fails when the maximum s-sparse eigenvalue grows like 1 + s, the proof only requires a bound on M1.Tail bounds give M1 ≤ 4 with high probability in the stated setting.
  • Condition verification: The resulting conditions provide a lower bound on γ with probability at least 1 − p^-Ω(1) − e^-Ω(n).The bound depends on sparsity, dimension, sample size, and the parameters s and r.
  • Scope: The same results can be applied to generalized linear models using existing arguments, while the stated asymptotic conditions constrain s and r relative to n.The proof specifies (s + r)σ2 log p = o(n) and r = Ω(s log n).

6 Experiments

The experiments compare greedy feature-selection methods with regularized and oblivious baselines on correlated synthetic data and the high-dimensional RCV1 dataset. Greedy methods generally perform better in the synthetic study, while OMP has the largest RCV1 log-likelihood at equal feature count.

  • Algorithms and setup: The experiments evaluate greedy algorithms with a logistic log-likelihood and compare them with Lasso, Lasso-Pipeline, and FoBa.FoBa runs forward selection and removes features whose loss would exceed half the latest marginal gain.
  • Datasets: The synthetic experiment uses a 600 × 200 correlated design with a 50-feature true support, while RCV1 uses 10,000 samples in 47,236 dimensions.The synthetic data use an AR process; RCV1 has no ground-truth support for recovery evaluation.
  • Metrics: Performance is measured by normalized objective value, support recovery, area under ROC, and generalization accuracy.Generalization accuracy is estimated on additional observations drawn from the training distribution.
  • Synthetic results: Across the synthetic metrics, Oblivious performs worst, OMP is slightly worse than FS and FoBa, and Lasso-Pipeline performs worse than the other non-oblivious methods.The authors interpret the pattern as evidence that greedy selection degrades more gracefully than Lasso with correlated features.
  • RCV1 results: At 300 features on RCV1, all algorithms have roughly the same generalization accuracy, but OMP has the largest log-likelihood.FS and FoBa are omitted from this dataset because of their large running-time complexity.

7 Conclusions

The paper extends the weak-submodularity analysis from linear regression to objectives satisfying restricted strong convexity. Its experiments and conclusions support greedy feature selection as a constant-factor approach for broad objective classes, while identifying further extensions.

  • Conclusions: Objectives satisfying restricted strong convexity also satisfy a relaxed form of submodularity that supports analysis against the best sparse solution.This extends the earlier linear-regression connection between RIP and weak submodularity.
  • Empirical conclusion: The experiments report that greedy feature selection outperforms regularized approaches in a nonlinear regression model.The synthetic figure also reports overfitting beyond 50 steps and regularization bias for Lasso.
  • Future directions: The stated framework is positioned for broader likelihood-based and structured-selection settings, including group sparsity, thresholding, and dictionary selection.The authors specifically mention general likelihood functions satisfying RSC and RSM.
  • Empirical conclusion: On the RCV1 Binary dataset, OMP outperforms the Lasso-Pipeline.The dataset has 10,000 samples and 47,236 dimensions.

A Motivating Example (Linear Regression)

A three-variable linear-regression example shows that greedy forward selection can choose a highly suboptimal two-feature subset. The gap from the optimal R2 can be arbitrarily large even when p = 3.

  • Even in p = 3 dimensions, greedy forward selection can be arbitrarily far from the optimal R2.The example concerns choosing a 2-subset of three unit-norm variables.
  • When z > 0, greedy selection chooses x3 first because its single-feature R2 is 4z2.The greedy path begins with SG 1 = {3}.
  • The optimal two-feature set is {x1, x2}, whose R2 is 1.This contrasts with the greedy choice produced by the constructed example.

B Greedy Selection for GLMs

For GLMs, the paper applies greedy feature-selection algorithms to log-likelihood objectives and bounds their weak submodularity through restricted curvature and design-matrix conditions. Regularization supplies strong convexity directly, while sample-complexity results provide high-probability ratio guarantees.

  • Objective and setup: Greedy algorithms 1–3 are applied directly to GLM log-likelihood objectives as an alternative to sparsity-inducing regularization.The analysis covers both regularized and unregularized regression.
  • Objective and setup: The GLM objective is formed from the negative log-likelihood, with a regularization term typically added for stability and identifiability.The associated normalized set function is monotone because enlarging β’s support does not decrease the log-likelihood.
  • Curvature conditions: The Hessian has the form H(β) = X⊤DX + ηI, and bounding Dii yields ηI ≼ H(β) ≼ sX⊤X + ηI.These bounds provide the curvature conditions used to control the submodularity ratio.
  • High-probability guarantee: Under Assumption 1, with probability 1 − δ, the regularized GLM submodularity ratio satisfies γU,r ≥ η/(η + s(1 + ϵ)¯θ).The guarantee requires the stated sample-complexity condition on n.
  • Curvature conditions: Restricted strong convexity and bounded smoothness on sparse supports imply weak submodularity, with γU,r ≥ 1/µr under the stable restricted Hessian condition.The paper notes that GLMs may satisfy these properties on sparse supports under suitable design restrictions.

B.1 Restricted strong convexity of GLMs

The paper derives weak-submodularity guarantees for unregularized GLMs by establishing restricted strong convexity and smoothness under design-matrix assumptions. Sub-Gaussian designs yield sample-complexity conditions and an explicit lower bound on the submodularity ratio.

  • Unregularized GLMs: For unregularized GLMs, the loss is the negative log-likelihood, and the analysis can be extended to η > 0.The discussion sets η = 0 to avoid clutter.
  • Weak submodularity guarantees: The contribution is a set of sample-complexity bounds ensuring weak submodularity for the associated GLM set function.These bounds connect restricted curvature conditions to the greedy-selection analysis.
  • Restricted curvature: The restricted-convexity analysis uses Bregman-divergence lower and upper bounds to characterize strong convexity and smoothness on sparse domains.The design matrix is assumed to have i.i.d. sub-Gaussian rows with covariance matrix Σ.
  • Restricted curvature: Under the sub-Gaussian design assumption, Theorem 7 supplies a constant αq depending on the GLM family for the restricted-curvature analysis.The theorem is used to obtain sparse-support sample-complexity results.
  • Weak submodularity guarantees: Under the resulting sample-complexity condition, the submodularity ratio for fGLM2 satisfies γU,r ≥ m′/M′.Here m′ and M′ are defined from the lower and upper curvature bounds, respectively.
Loading 1612.00804v2…