PaperlayerView exact revision on arXiv

Source-linked AI summary

Sparse Estimation by Exponential Weighting

Philippe Rigollet, Alexandre B. Tsybakov

arXiv:1108.5116v2math.STstat.MEstat.TH

TL;DR

The paper studies sparse approximation in fixed-design Gaussian regression using exponential weights. It applies sparsity pattern aggregation to derive oracle inequalities across sparsity settings, with results that hold without dictionary assumptions.

  • Problem

    The paper asks how to estimate a regression function that may be well approximated by a sparse representation in a dictionary, including when the dictionary has no assumed conditions.

    Source: §1 · p. 2, §5.2.1 · p. 8

  • Method

    It uses exponential weights to implement sparsity pattern aggregation and derives inequalities for ordinary, fused, and group sparsity.

    Source: §1 · p. 3, §5.2.2 · p. 8, §5.2.3 · p. 10

  • Results

    The coordinatewise sparsity oracle inequality holds without assumptions on the dictionary.

    Source: §5.2.1 · p. 8

  • Takeaways & Limitations

    The paper extends sparsity oracle inequalities to fused sparsity, where few first differences are nonzero, and to arbitrary groups that may overlap or leave variables uncovered.

    Source: §5.2.2 · p. 8, §5.2.3 · p. 10

    The paper’s sharpest results are developed for Gaussian regression with fixed design and known noise variance; related results in other models are somewhat weaker.

    Source: §6 · p. 10

Abstract

from arXiv · show

Consider a regression model with fixed design and Gaussian noise where the regression function can potentially be well approximated by a function that admits a sparse representation in a given dictionary. This paper resorts to exponential weights to exploit this underlying sparsity by implementing the principle of sparsity pattern aggregation. This model selection take on sparse estimation allows us to derive sparsity oracle inequalities in several popular frameworks, including ordinary sparsity, fused sparsity and group sparsity. One striking aspect of these theoretical results is that they hold under no condition in the dictionary. Moreover, we describe an efficient implementation of the sparsity pattern aggregation principle that compares favorably to state-of-the-art procedures on some basic numerical examples.

1. INTRODUCTION

The paper studies exponential weighting for regression with a fixed dictionary, where the goal is to match the best candidate or combination without assuming a true underlying model. It develops oracle-inequality results and uses exponential averaging to address sparse estimation.

1. INTRODUCTION

  • The paper focuses on sparsity oracle inequalities whose remainder depends on dictionary size, sample size, and the candidate vector’s complexity.The main complexity measure is the number of nonzero coefficients; other sparsity measures are also considered.Source: §1 · p. 2
  • For a fixed candidate class under model misspecification, the paper seeks sharp oracle inequalities with leading constant 1 and finite-sample validity.The best candidate can still have positive risk, creating an unavoidable systematic bias term.Source: §1 · p. 2
  • Oracle reasoning compares estimator risk with the best risk in a candidate class rather than estimating parameters of a presumed true model.This comparison remains meaningful whether or not the best candidate is true.Source: §1 · p. 2
  • In model-selection aggregation, the goal is to match the best function in the dictionary, with the optimal remainder rate of order (log M)/n.The passage identifies this rate as minimax optimal in the cited regression settings.Source: §1 · p. 2
  • Exponential weighting averages dictionary functions, unlike selectors, which cannot attain the optimal (log M)/n rate.The paper describes sparsity pattern aggregation and oracle inequalities for ordinary, fused, and group sparsity, alongside an efficient implementation and numerical comparisons.Source: §1 · p. 3
  • The paper develops exponential-weighting oracle inequalities and extends them to estimator aggregation and sparse settings, including fused and group sparsity.It also describes an efficient sparsity-pattern aggregation implementation and compares it with state-of-the-art procedures on basic numerical examples.Source: §1 · p. 3

2. EXPONENTIAL WEIGHTING AND PENALIZED RISK MINIMIZATION

Selecting a single dictionary function is suboptimal for model selection, while a convex mixture can attain the optimal rate. The paper obtains such mixtures through penalized empirical risk minimization with a Kullback–Leibler penalty, yielding exponential weights.

2.1 Suboptimality of Selectors

  • An empirical risk minimizer is a natural model-selection candidate, but the section shows that selectors fail to achieve the optimal remainder rate.The lower-bound discussion identifies this as an intrinsic shortcoming of choosing only one dictionary function.Source: §2.1 · p. 3
  • A convex mixture with exponential weights can attain the optimal minimax rate (log M)/n, unlike procedures that select one function.The section states that the limitation applies to selectors generally, including penalized empirical-risk selectors.Source: §2.1 · p. 3

2.2 Exponential Weighting as a Penalized Procedure

  • Penalized empirical risk minimization seeks a convex combination by minimizing empirical risk plus a penalty over the simplex.The penalty should approximate the oracle inequality’s remainder, but directly optimizing this objective may be difficult.Source: §2.2 · p. 4
  • A Kullback–Leibler penalty yields an explicit exponential-weight solution that averages dictionary functions rather than selecting one.The weights depend on empirical risks and a prior distribution over the dictionary.Source: §2.2 · p. 4

3. ORACLE INEQUALITIES

The section gives oracle inequalities for exponential-weight aggregates, with remainder terms that account for the comparison distribution and the prior. A uniform prior yields an optimal-order remainder, while prior choice can reflect preferences among dictionary functions.

3. ORACLE INEQUALITIES

  • An aggregate is a data-dependent weighted average of functions in the dictionary.The paper’s exponential-weight aggregate uses weights specified by its exponential-weights construction.Source: §3 · pp. 4–5
  • The authors note that related results extend to non-Gaussian errors and general probability distributions over the parameter space.These extensions are attributed to Dalalyan and Tsybakov (2007, 2008).Source: §3 · p. 5
  • The general oracle bound compares aggregate risk with a mixture over probability distributions, penalizing the comparison distribution by its Kullback–Leibler divergence from the prior.The paper notes that the discrete bound follows by choosing discrete distributions in the general result.Source: §3 · p. 5
  • With a uniform prior, the exponential-weight aggregate has an oracle inequality with remainder of optimal order (log M)/n.The prior assigns equal weight to each function when there is no preference among dictionary elements.Source: §3 · p. 5

4. AGGREGATION OF ESTIMATORS

The paper extends exponential weighting from deterministic functions to estimators, including linear estimators. For linear estimators, it modifies the weights to use an unbiased risk estimate and gives bounds under stated matrix conditions.

4.1 From Aggregation of Functions to Aggregation of Estimators

  • Aggregation can use preliminary estimators built on one sample and aggregated on another, or use the same observations for both steps.The latter approach is used for projection estimators and a more general class of linear estimators.Source: §4.1 · p. 5
  • Direct sample splitting does not apply to independent samples that are not identically distributed; randomization remains possible but yields weaker bounds.The randomization-based bounds include an additional expectation over the randomization distribution and a larger remainder term.Source: §4.1 · p. 6

4.2 Aggregation of Linear Estimators

  • For linear estimators, the paper modifies exponential weights because empirical risk minus σ² is no longer an unbiased risk estimate.The modified procedure uses a version of Mallows’s Cp as an unbiased estimator of expected risk.Source: §4.2 · p. 6
  • For commuting, symmetric positive-definite estimator matrices, the exponentially weighted aggregate satisfies risk bounds when β ≥ 8σ².The result builds on bounds for projection estimators and extends to linear estimators under these matrix conditions.Source: §4.2 · p. 6

5. SPARSE ESTIMATION

The paper aggregates least-squares estimators indexed by sparsity patterns, choosing priors to target coordinatewise, fused, or group sparsity. It derives oracle inequalities for these settings, including group-sparse rate optimality, without assumptions on the dictionary.

5. SPARSE ESTIMATION

  • The paper considers a family of least-squares estimators indexed by sparsity patterns, then aggregates them with suitably chosen priors to obtain sparsity oracle inequalities.The dictionary functions define the design matrix for these least-squares fits.Source: §5 · p. 6, §5.1 · p. 7

5.1 Sparsity Pattern Aggregation

  • Sparsity pattern aggregation combines least-squares estimators for patterns rather than selecting a single pattern, using exponential weights and a prior over patterns.The prior can favor coordinatewise sparse, group sparse, or piecewise-constant candidates within a frequentist risk analysis.Source: §5.1 · pp. 6–7

5.2.1 Coordinatewise sparsity

  • The coordinatewise sparsity oracle inequality holds without assumptions on the dictionary, unlike the cited Lasso-type procedures.The inequality follows by choosing an exponentially downweighting prior on patterns with larger support.Source: §5.2.1 · p. 8

5.2.2 Fused sparsity

  • Fused sparsity targets coefficients that are piecewise constant, or more generally sparse after an invertible transformation.With the first-differences matrix, a sparse transformed vector corresponds to a piecewise-constant coefficient vector with few jumps.Source: §5.2.2 · pp. 8–9
  • Fused sparsity is expressed as coordinatewise sparsity of Dθ; the paper allows any invertible D, not only the first-differences matrix.The fused aggregate's oracle inequality requires no assumption on X; the authors report that analogous fused Lasso bounds were unavailable to their knowledge.Source: §5.2.2 · pp. 8–9

5.2.3 Group sparsity

  • For group sparsity, the oracle aggregate mimics a candidate with small approximation error supported by few groups, and the groups may overlap or leave coordinates uncovered.The oracle inequality applies to arbitrary choices of groups.Source: §5.2.3 · p. 10
  • The group sparsity pattern aggregate is rate optimal on the stated multi-task class, where the matching minimax lower bound establishes the rate.The paper identifies this as the first example of a rate-optimal estimator under group sparsity; the bound holds without assumptions on the dictionary.Source: §5.2.3 · p. 10

6. RELATED PROBLEMS

The paper focuses on fixed-design Gaussian regression with known noise variance, where sharp sparsity oracle inequalities for exponential weighting are available. Related results cover broader models, but use different procedures or yield different oracle bounds.

6. RELATED PROBLEMS

  • The analysis is limited to fixed-design Gaussian regression with known noise variance, the setting where the sharpest EW sparsity oracle inequalities are available.Similar but somewhat weaker properties are obtained for exponential weighting in other models.Source: §6 · p. 10
  • Prior work treats random-design regression, density estimation, and classification using EW procedures driven by continuous or mixed priors rather than aggregation of estimators.Those results derive sparsity oracle inequalities from PAC-bounds and include the ℓ1-norm of θ alongside |θ|0.Source: §6 · pp. 10–11
  • Some procedures for unknown variance and non-Gaussian noise exist, but the cited non-Gaussian result does not satisfy this paper’s sparsity-oracle definition.Its bound involves characteristics of θ and the target function in addition to |θ|0.Source: §6 · p. 11

7. NUMERICAL IMPLEMENTATION

The implementation approximates exponential-weight aggregates with a Metropolis–Hastings chain, and simulations compare ordinary and fused screening with established estimators.

7. NUMERICAL IMPLEMENTATION

  • Exact computation sums over 2^M least-squares estimators, so the implementation approximates the aggregate by sampling its Gibbs-type distribution with a Metropolis–Hastings chain.The chain proposes uniformly among neighboring patterns on the hypercube, and its stationary distribution is the target distribution.Source: §7 · p. 11
  • The Metropolis approximation is a stochastic greedy procedure that uses sparsity–prediction trade-offs to decide whether to add or remove a variable.A safe implementation with three times more iterations increased computation time by at most a factor of two.Source: §7 · p. 12

7.1 Numerical Experiments

  • The ordinary-sparsity experiments use 500 replications, two (n,M,S) settings, and Lasso, mc+, and scad as comparators to exponential screening.The simulations use Gaussian design and noise; the compared penalized estimators use cross-validated regularization parameters.Source: §7.1 · p. 12
  • Exponential Screening outperforms Lasso and performs similarly to mc+ and scad across the reported ordinary-sparsity comparisons.The comparison uses boxplots over 500 realizations for estimation and prediction performance.Source: Figure 3 · p. 13, §7.1 · p. 13
  • Although the exponential-screening aggregate is not itself sparse, its Metropolis approximation can output a sparse solution after the chain reaches the true pattern.A typical realization recovers the pattern after about 2,000 iterations.Source: §7.1 · pp. 12–14
  • Fused Exponential Screening outperforms fused Lasso, fused mc+, and fused scad in the reported piecewise-constant examples.The mc+ and scad outputs take only two values and miss most of the structure in the larger example.Source: Fused sparsity · p. 14

APPENDIX

The appendix develops proof arguments for oracle bounds and lower bounds, including a testing reduction under a Rademacher design.

APPENDIX

  • The oracle-bound argument starts from comparison with a minimizer of the true risk over the candidate functions and controls the resulting stochastic term using a Gaussian maximum bound.The proof invokes a bound involving 2 log M for unit-norm vectors.Source: APPENDIX · p. 14
  • For the design construction, the proof uses an i.i.d. Rademacher matrix and invokes a weak restricted isometry property for vectors with at most two nonzero coordinates.The stated property requires positive constants bounded below by κ̄.Source: APPENDIX · p. 14
  • The lower-bound argument converts estimation into a testing problem by selecting which candidate function the estimator returns.It then applies a testing inequality when pairwise Kullback–Leibler divergences meet the stated condition.Source: APPENDIX · pp. 16–17
Loading 1108.5116v2…