Be a Goldfish: Forgetting Bad Conditioning in Sparse Linear Regression via Variational Autoencoders

Kuheli Pratihar, Debdeep MukhopadhyayICML 2025 · OpenReview

TL;DR

While Variational Autoencoders (VAEs) are famous for generating high-fidelity images and text, this paper proves they can also solve NP-hard mathematical problems. By tweaking a VAE's architecture to intrinsically "precondition" poorly behaved data matrices, the authors show it can bypass bad local minima and find the optimal solution for Sparse Linear Regression (SLR) in scenarios where classic algorithms like LASSO completely fail.

What Problem Does This Paper Address?

The paper tackles Sparse Linear Regression (SLR), a fundamental problem in high-dimensional statistics. The goal of SLR is to find a small (sparse) set of coefficients that best explains a set of observations based on a "design matrix" of features. Because you have to figure out both which features matter and what their values are, SLR is a notoriously NP-hard combinatorial problem.

The standard tool for this is LASSO, which uses an $\ell_1$ penalty to force sparsity. However, LASSO reliably fails under two common real-world conditions:

  1. Ill-conditioned design matrices: When the features in the matrix are highly correlated, the matrix behaves poorly mathematically (it fails the "Restricted Isometry Property" or RIP).
  2. Low sparsity: When the true solution has a relatively high number of non-zero coefficients compared to the number of observations.

Finding a "preconditioner" to fix an ill-conditioned matrix is computationally intractable in many cases. The authors ask: Can we design a VAE that intrinsically preconditions these bad matrices and solves the SLR problem even when sparsity is low?

Methods

The authors step away from deep, non-linear neural networks and instead use a linear encoder-decoder VAE architecture.

Here is the clever part: instead of standard weights, the VAE decoder incorporates the actual SLR design matrix multiplied by a trainable, sparsity-promoting diagonal matrix. This allows the VAE to implicitly select the non-zero features during training.

To handle ill-conditioned matrices, they introduce a preconditioning factor tied to the VAE's decoder variance parameter ($\gamma$). Mathematically, multiplying the design matrix by this factor squishes the spread of its eigenvalues. Because $\gamma$ is a trainable parameter in the VAE loss function, the model learns to improve the condition number of the matrix on the fly.

The authors provide rigorous mathematical proofs showing that under this specific architecture, the VAE loss landscape is smoothed out. Spurious local minima disappear, guaranteeing that any minimum found by the optimizer is a global minimum corresponding to the optimal sparse solution.

Datasets

The authors evaluated their method in noiseless and noisy settings using three types of design matrices:

  • Standard Gaussian Distribution (Synthetic): A well-conditioned baseline matrix.
  • Gaussian Random Walk (Synthetic): A highly ill-conditioned matrix where features are heavily correlated (a known failure case for standard LASSO).
  • Riboflavin Dataset (Real-world): Biological measurements of genetic features. This dataset is inherently ill-conditioned and challenging because it has fewer observations ($n=71$) than features ($d=100$ or $200$).

Key Insights and Ideas

  • VAEs are powerful optimizers: We usually think of VAEs as generative models, but their ability to marginalize over a posterior distribution effectively smooths out complex, non-convex loss landscapes. This makes them secret weapons for NP-hard inverse problems.
  • Implicit over Explicit Sparsity: Instead of forcing sparsity with a rigid mathematical penalty (like LASSO's $\ell_1$ norm), the VAE learns the mean and covariance of the sparse coefficients. This richer representation is why it survives in low-sparsity regimes.
  • Intrinsic Preconditioning: You don't need a separate, computationally expensive algorithm to fix a bad matrix before solving the regression. By tying the preconditioning matrix to the VAE's variance parameter, the network "forgets" the bad conditioning dynamically during gradient descent.

Key Results

The empirical results validate the theoretical claims, demonstrating that the proposed VAE architectures significantly outperform traditional methods across various conditions.

Support Recovery Rates across different design matrices
  • Superior Support Recovery: Across all datasets, the VAE-based approach consistently identified the correct non-zero features (support recovery) at much higher rates than LASSO, Sparse Bayesian Learning (SBL), and Augmented Basis Pursuit (AugBP).
  • Tolerance to Low Sparsity: On the nasty Gaussian Random Walk matrix, baseline methods failed almost immediately as the number of non-zero entries ($\kappa$) increased. The preconditioned VAE maintained high recovery rates up to $\kappa \le 20$.
  • Real-World Success: On the challenging Riboflavin dataset, the VAE achieved the highest recovery rate for $\kappa \le 10$, proving its viability on actual biological data with highly limited sample sizes.
  • Trainable vs. Fixed Parameters: The empirical results confirmed that making the preconditioning factor ($\gamma$) a trainable parameter yielded significantly better recovery rates than keeping it fixed.

Limitations and Future Work

Limitations: The theoretical guarantee that the VAE finds the exact optimal sparse solution requires the parameter $\gamma$ to approach zero. In practice, this relies on the Stochastic Gradient Descent (SGD) optimizer perfectly navigating the landscape; if SGD stops early or gets stuck, the ideal scenario isn't perfectly realized. Additionally, while robust, performance naturally degrades at very high noise levels (low SNR).

Future Work: The authors suggest applying this VAE approach to challenging domains that suffer from ill-conditioned data and low sample sizes, such as privacy-preserving machine learning, neuroimaging, and cancer genomics. They also plan to investigate new preconditioning strategies and establish formal sample complexity bounds for VAE-based sparse recovery.

Summary updated

Abstract

Variational Autoencoders (VAEs), a class of latent-variable generative models, have seen extensive use in high-fidelity synthesis tasks, yet their loss landscape remains poorly understood. Prior theoretical works on VAE loss analysis have focused on their latent-space representational capabilities, both in the optimal and limiting cases. Although these insights have guided better VAE designs, they also often restrict VAEs to problem settings where classical algorithms, such as Principal Component Analysis (PCA), can trivially guarantee globally optimal solutions. In this work, we push the boundaries of our understanding of VAEs beyond these traditional regimes to tackle NP-hard sparse inverse problems, for which no classical algorithms exist. Specifically, we examine the nontrivial Sparse Linear Regression (SLR) problem of recovering optimal sparse inputs in the presence of an ill-conditioned design matrix having correlated features. We provably show that, under a linear encoder-decoder architecture incorporating the product of the SLR design matrix with a trainable, sparsity-promoting diagonal matrix, any minimum of VAE loss is guaranteed to be an optimal solution. This property is especially useful for identifying (a) a preconditioning factor that reduces the eigenvalue spread, and (b) the corresponding optimal sparse representation. Lastly, our empirical analysis with different types of design matrices validates these findings and even demonstrates a higher recovery rate at low sparsity where traditional algorithms fail. Overall, this work highlights the flexible nature of the VAE loss, which can be adapted to efficiently solve computationally hard problems under specific constraints.
BibTeX
@inproceedings{pratihar2025be,
  author = {Kuheli Pratihar and Debdeep Mukhopadhyay},
  title = {{Be a Goldfish: Forgetting Bad Conditioning in Sparse Linear Regression via Variational Autoencoders}},
  booktitle = {International Conference on Machine Learning},
  year = {2025},
  url = {https://openreview.net/forum?id=aTQtGq7IyT},
}
Figure