Research map / Learning theory and algorithms / Matrix and tensor methods
Be a Goldfish: Forgetting Bad Conditioning in Sparse Linear Regression via Variational Autoencoders
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Shows that a linear VAE with a sparsity-promoting diagonal decoder and a ridge-style preconditioner can recover optimal sparse solutions to sparse linear regression, including ill-conditioned design matrices and low sparsity levels where LASSO fails.
Problem
Sparse linear regression (NP-hard) with ill-conditioned, correlated design matrices and low sparsity levels, where LASSO and other classical methods fail to recover the optimal sparse support.
Approach
Use a linear-encoder/decoder VAE whose decoder contains a trainable diagonal sparsity-promoting matrix, plus a ridge-style preconditioner P=(ΦΦᵀ+γI)⁻¹ applied inside the VAE, so that the VAE loss has no bad local minima and its global minima recover the optimal sparse solution as γ→0 and the preconditioned matrix satisfies RIP.
Key results
- On a standard Gaussian design (n=200, d=100), the linear VAE achieves higher support recovery than LASSO and SBL, particularly at lower sparsity; LASSO's recovery falls to zero for kappa > 30.
- On the ill-conditioned Gaussian random walk design, the preconditioned VAE keeps a higher recovery rate than SBL, augmented basis pursuit and LASSO until kappa <= 20.
- On the Riboflavin design (n=71, d=100), the preconditioned VAE achieves the highest recovery rate for kappa <= 10.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use the linear VAE instead of LASSO or SBL | SLR with a standard Gaussian design matrix · Standard Gaussian design matrix, κ ≤ 60 | support recovery rate | Helped |
| Use the preconditioned VAE instead of SBL or augmented basis pursuit | SLR with a Gaussian random walk design matrix · Gaussian random walk design matrix, κ ≤ 20 | support recovery rate | Helped |
| Use the preconditioned VAE instead of competing methods | SLR with the Riboflavin design matrix · Riboflavin dataset, κ ≤ 10 | support recovery rate | Helped |
| Increase the number of features | SLR methods on the Gaussian random walk design matrix · Gaussian random walk design matrix, κ = 20, d = 100 | support recovery rate | Hurt |
| Increase the number of observations | SLR methods on the Gaussian random walk design matrix · Gaussian random walk design matrix, κ = 10 | support recovery rate | Helped |
| Use the preconditioned VAE instead of LASSO or augmented basis pursuit | SLR on the Gaussian random walk design matrix · Gaussian random walk design matrix, varying d | support recovery rate: 5–10% | Helped |
| Change the distribution of nonzero coefficients | Proposed VAE support identification · Standard Gaussian design matrix, five coefficient distributions | support recovery rate: no more than two percentage points | No clear effect |
| Increase SNR | SLR methods on a standard Gaussian design matrix · Standard Gaussian design matrix, SNR 20 dB to 40 dB | support recovery rate | Helped |
| Use the preconditioned VAE instead of other methods at high SNR | SLR on the Gaussian random walk design matrix · Gaussian random walk design matrix, SNR above 60 dB | support recovery rate | Helped |
| Train γ rather than fix it during preconditioning (ablation) | Preconditioned VAE · Gaussian random walk design matrix | support recovery rate | Helped |
| Use a randomly chosen 200-feature Riboflavin subset rather than the 100 highest-variance features | Preconditioned VAE · Riboflavin dataset | support recovery rate | Helped |
Surprising findings
- Trainable gamma yields higher support recovery than a fixed gamma, and imperfect SGD optimization can prevent reaching the gamma-to-zero optimum.
Limitations
- Theoretical guarantees rely on the RIP condition with small delta and on gamma approaching zero, which requires the optimizer to succeed.
- Preconditioning does not help for some special ill-conditioned matrix classes, where lattice-based hardness implies intractability.
- Experiments are noiseless or limited to small synthetic and one real dataset with 10 trials.
Experimental setup
Datasets: Riboflavin dataset (Bühlmann et al., 2014) synthetic Gaussian design matrices synthetic Gaussian random walk design matrices
Benchmarks: support recovery rate on synthetic Gaussian design matrices support recovery rate on Gaussian random walk design matrices support recovery rate on Riboflavin design matrix
Metrics: sparse support recovery rate mean squared error recovery rate vs. SNR
Baselines: LASSO sparse Bayesian learning augmented basis pursuit
Builds on: Wipf 2023 VAE no-bad-local-minima Dai & Wipf 2019 sparse Bayesian learning LASSO
Closest papers by meaning
- Marginalization is not Marginal: No Bad VAE Local Minima when Learning Optimal Sparse Representations (ICML 2023 · similarity 0.93)
- Beyond Vanilla Variational Autoencoders: Detecting Posterior Collapse in Conditional and Hierarchical Variational Autoencoders (ICLR 2024 · similarity 0.90)
- Variational Autoencoders Pursue PCA Directions (by Accident) (CVPR 2019 · similarity 0.89)
- Trading Information between Latents in Hierarchical Variational Autoencoders (ICLR 2023 · similarity 0.89)
- From Variational to Deterministic Autoencoders (ICLR 2020 · similarity 0.89)
- Sparse Autoencoders, Again? (ICML 2025 · similarity 0.89)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.