PaperlayerView exact revision on arXiv

Source-linked AI summary

Sparse Regression Learning by Aggregation and Langevin Monte-Carlo

Arnak Dalalyan, Alexandre B. Tsybakov

arXiv:0903.1223v3stat.APmath.ST

TL;DR

The paper studies regression learning with deterministic designs, independent errors, and dictionaries whose dimensions may exceed the sample size. It develops PAC-Bayesian bounds and sparse EWA, then uses Langevin Monte-Carlo to compute the aggregate approximately, with convergence supported theoretically and numerically.

  • Problem

    Sparse regression must handle dictionaries with M ≫ n while avoiding restrictive design assumptions and computationally intractable procedures.

  • Method

    The paper proves PAC-Bayesian bounds for EWA, applies a heavy-tailed sparsity prior, and approximates the resulting aggregate with Langevin Monte-Carlo.

  • Results

    The EWA satisfies a sparsity oracle inequality with leading constant one, while the Langevin Monte-Carlo approximation has convergence supported by theory and numerical experiments.

  • Takeaways & Limitations

    Sparse EWA offers a computationally tractable alternative to ℓ0-penalized empirical risk minimization for large dictionaries.

  • Takeaways & Limitations

    The paper notes that earlier numerical Lasso results differ across software packages, with MATLAB l1_ls providing a more accurate approximation in the reported example.

Abstract

from arXiv · show

We consider the problem of regression learning for deterministic design and independent random errors. We start by proving a sharp PAC-Bayesian type bound for the exponentially weighted aggregate (EWA) under the expected squared empirical loss. For a broad class of noise distributions the presented bound is valid whenever the temperature parameter $β$ of the EWA is larger than or equal to $4σ^2$, where $σ^2$ is the noise variance. A remarkable feature of this result is that it is valid even for unbounded regression functions and the choice of the temperature parameter depends exclusively on the noise level. Next, we apply this general bound to the problem of aggregating the elements of a finite-dimensional linear space spanned by a dictionary of functions $φ_1,...,φ_M$. We allow $M$ to be much larger than the sample size $n$ but we assume that the true regression function can be well approximated by a sparse linear combination of functions $φ_j$. Under this sparsity scenario, we propose an EWA with a heavy tailed prior and we show that it satisfies a sparsity oracle inequality with leading constant one. Finally, we propose several Langevin Monte-Carlo algorithms to approximately compute such an EWA when the number $M$ of aggregated functions can be large. We discuss in some detail the convergence of these algorithms and present numerical experiments that confirm our theoretical findings.

1. Introduction

The paper addresses sparse regression when the dictionary dimension can greatly exceed the sample size, extending EWA theory and introducing Langevin Monte-Carlo computation for large models.

  • Motivation: High-dimensional regression becomes difficult when M ≫ n, motivating sparsity assumptions that enable interpretable and consistent estimation.The assumption is that only a few coordinates or dictionary elements describe the underlying model.
  • Existing methods: Classical sparse procedures such as the Lasso are computationally attractive but require restrictive Gram-matrix conditions for consistency.Examples include mutual coherence, uniform uncertainty, irrepresentable, and restricted eigenvalue conditions.
  • Existing methods: The ℓ0-penalized least-squares estimator can attain optimal prediction accuracy under almost no Gram-matrix assumptions, but computing it is NP-hard.
  • Contributions: The authors extend EWA analysis with a sparsity-favoring prior, obtaining sparsity oracle inequalities while requiring almost no assumptions on the Gram matrix.The extension includes a PAC-Bayesian bound whose temperature depends only on the noise distribution and allows unbounded regression functions.
  • Contributions: Langevin Monte-Carlo is proposed to approximate the sparsity-prior EWA when the dictionary dimension M is large.Numerical experiments are reported to confirm fast convergence and demonstrate performance of the resulting estimators.

2. PAC-Bayesian type oracle inequality

The paper establishes a PAC-Bayesian oracle inequality for EWA under a noise-distribution assumption, then specializes it to finite dictionaries and sparse aggregation.

  • Model and EWA: The regression setup uses deterministic design points and independent identically distributed random errors in a non-parametric model.The empirical norm and EWA are defined over a measurable family of candidate functions with prior π and temperature β.
  • Noise assumption: Assumption N characterizes the noise through an auxiliary variable ζ, a distributional scaling relation, conditional centering, and a bounded function v.
  • PAC-Bayesian inequality: For any prior π and probability measure p, Theorem 1 gives the oracle inequality when β ⩾ max(4∥v∥∞, 2L/t0).The bound includes the Kullback-Leibler divergence between p and π.
  • PAC-Bayesian inequality: The theorem’s noise condition is independent of the sample size and the dictionary, enabling a temperature choice that does not change with n.The authors contrast this with an earlier result restricted to essentially Gaussian and uniform noise.
  • Noise examples: For Gaussian, Rademacher, uniform, and bounded symmetric noise, the theorem yields explicit temperature conditions tied to the noise scale.Gaussian and Rademacher examples give β ⩾ 4σ^2, while bounded symmetric noise gives β ⩾ 4B^2.
  • Finite dictionaries: With a finite dictionary and uniform prior, Theorem 1 immediately yields a sharp model-selection aggregation oracle inequality.

3. Sparsity prior and SOI

The paper introduces a heavy-tailed sparsity prior for exponentially weighted aggregation and derives a sparsity oracle inequality for high-dimensional dictionary models, including settings with M much larger than n. The resulting bound achieves the standard sparse rate without assumptions on the dictionary, while Langevin Monte-Carlo provides a tractable computational approximation.

  • Model and assumptions: The framework includes linear and single-index regression with a known twice continuously differentiable link function, using dictionary evaluations Xi = (φ1(Zi), ..., φM(Zi))⊤.The design is normalized so the diagonal entries of the empirical Gram matrix are one, and bounded dictionary functions yield the required Lipschitz condition.
  • Sparsity prior: The sparsity prior is designed for dictionary models where M may greatly exceed n and the target is well approximated by a vector with few nonzero coordinates.The prior is motivated by high-dimensional sparse representations and uses heavy-tailed behavior to keep most coordinates near zero while allowing a few large coefficients.
  • Sparsity prior: The prior combines a differentiable Huber-type penalty with an ℓ1-ball constraint and heavy-tailed coordinate behavior based on Student t(3).The Huber function is used because it behaves like absolute value while remaining differentiable; the resulting prior is heuristically close to a scaled Student t(3) distribution.
  • Sparsity oracle inequality: Theorem 2 gives a sparsity oracle inequality for the EWA under Assumption N, β ≥ max(4∥v∥∞, 2L/t0), R > 2Mτ, and α ≤ 1/(4Mτ).The result applies to λ* satisfying ∥λ*∥1 ≤ R − 2Mτ and includes the link-function constant Cg,f.
  • Sparsity oracle inequality: Choosing τ^2 ∼ (Mn)^−1 and R = O(Mτ) makes the main remainder terms order O(1/n), while the dominant sparsity term depends on the number M* of nonzero coordinates.For sparse λ*, this yields the rate M*(log M)/n.
  • Sparsity oracle inequality: The rate M*(log M)/n matches other sparse-recovery methods, but the theorem requires no assumption on the dictionary {φ1, ..., φM}.For logistic regression with f valued in [0,1], the paper states Cg,f ≤ 3; a corresponding probit bound is also given.

4. Computation of the EW-aggregate by the Langevin Monte-Carlo

The paper uses Langevin diffusion and its Euler discretization to approximate the EWA with a sparsity prior in high dimensions. Time averages converge to the target EWA quantity, while discretization requires sufficiently small steps or corrective measures to avoid instability.

  • Motivation: Langevin Monte-Carlo is proposed to approximately compute the sparsity-prior EWA when the dictionary dimension M is much larger than n.The approach replaces difficult M-dimensional integrations with simulation-based approximations.
  • Continuous-time diffusion: The Langevin diffusion is a Markov process whose stationary distribution enables computation of high-dimensional integrals associated with the EWA.Positive recurrence provides a stationary distribution, and geometric ergodicity supports convergence of time averages.
  • Continuous-time diffusion: The diffusion average converges to the target vector bλ, replacing M-dimensional integration with a one-dimensional finite-time integral.The target involves integration over RM, whereas the simulated average integrates the diffusion over time.
  • Discretization: The discretization is valid when sampling is sufficiently dense, but an insufficiently small h can make the discrete Markov process transient and cause the approximation to explode.Metropolis-Hastings correction guarantees convergence but increases rejection, while reducing h slows computation but preserves execution-time control.
  • Discretization: The Euler scheme discretizes the diffusion with step h, and its interpolated process converges in distribution to the Langevin diffusion as h → 0.Brownian-bridge interpolation and the Girsanov formula establish convergence of the discretized process in the stated limit.
  • Theoretical result: The paper proves a linear-model result for the limiting vector bλ under deterministic design and zero-mean noise with finite covariance.This proposition connects the diffusion-based computation to the linear regression setting.

5. Implementation and experimental results

The paper implements the EWA through Langevin Monte-Carlo and evaluates it against the Lasso in two simulated regression and image-recovery examples. The experiments report practical computation, predictive performance, and sparsity selection.

  • Implementation: The LMC algorithm takes observations, predictors, noise level, and tuning parameters as input, then outputs a coefficient vector for prediction.The update combines the potential gradient, Gaussian noise, and averaging over the trajectory.
  • Implementation: The trajectory average converges at rate T^-1/2, motivating T = n, while an adaptive stopping rule is suggested when convergence is observed.The discretization step is chosen as h = β/(Mn) = β/Tr(X⊤X).
  • Example 1: For n = 200, M = 500, and S = 20, EWA coefficient estimates are reported as more accurate and better at selecting the nonzero coordinates than Lasso.The EWA’s approximate sparsity is linked to exact recovery of zero coordinates in noise-free orthogonal models.
  • Example 1: In Example 1, EWA outperforms Lasso across the considered combinations of sparsity S and dictionary size M.The experiment uses Rademacher predictors, Gaussian noise, an S-sparse target, and 500 replications.
  • Example 2: In Example 2, EWA has smaller predictive risk than Lasso and surpasses the ideal Lasso-Gauss procedure under large noise variance.The EWA takes less than two seconds to compute in this example, although the ideal Lasso-Gauss procedure is faster.
  • Example 2: Figure 3 compares the original image, a noisy sample with σ = 0.5 and missing pixels shown in black, and the EWA estimate.The setup uses n = 200 and k = 15.

6. Conclusion and outlook

The conclusion presents new oracle inequalities for EWA and Langevin Monte-Carlo as a computational method for approximate EWA evaluation. It emphasizes sparsity guarantees without atom-correlation assumptions and tractable computation compared with ℓ0-penalized ERM.

  • The paper’s two contributions are new oracle inequalities for EWA and an LMC method for approximately computing the EWA.
  • The sparsity oracle inequality bounds EWA against the best linear combination with a residual proportional to M*(log M)/n.Here M is the true dimension and M* is the number of atoms in the best linear combination.
  • The sparsity oracle inequality requires no condition on the relationship between different dictionary atoms.
  • Unlike ℓ0-penalized empirical-risk minimization, the suggested EWA is computationally tractable and can be efficiently solved using LMC.Simulations also suggest that EWA efficiently selects the sparsity pattern.
  • Theoretical justification of sparsity-pattern selection and more thorough study of LMC parameter choices remain future research topics.

Appendix: proofs of technical results

The appendix establishes technical properties of the Langevin approximation, its convergence, and the sparsity-prior bounds used in the theoretical analysis. The proofs rely on moment bounds, Lipschitz control, absolute continuity, and mixing arguments.

  • LMC approximation: The LMC discretization is analyzed under a step-size restriction h ≤ 1/∥A∥, with bounded drift components and centered Gaussian innovations.The proof introduces v = 2β^-1X⊤Y and A = 2β^-1X⊤X.
  • LMC approximation: The discretized process is coupled to Brownian motion, allowing comparison between the discrete LMC path and the continuous Langevin diffusion.The Brownian motion is constructed so that W_kh = ξ_k.
  • LMC approximation: Girsanov’s formula expresses the Radon-Nikodym derivatives between the discretized and continuous path distributions, while Lipschitz drift bounds control their divergence.
  • Convergence: Pinsker’s inequality converts the divergence control into convergence in total variation as h → 0.Uniform moment bounds for the diffusion support the argument.
  • Convergence: As T → ∞, geometric mixing and a bias-variance decomposition show convergence of the time-averaged Langevin process.
  • Sparsity prior: The sparsity-prior proof bounds prior-related terms using scaled Student t(3) variables, Chebyshev’s inequality, and properties of the prior’s auxiliary functions.
  • Noise conditions: For the bounded-noise construction, the appendix verifies distributional scaling, zero conditional mean, and the required moment-generating-function condition.It shows ξ + ζ has the same distribution as (1 + γ)ξ and derives E[ζ | ξ = a] = 0.
Loading 0903.1223v3…