Be a Goldfish: Forgetting Bad Conditioning in Sparse Linear Regression via Variational Autoencoders
Authors: Kuheli Pratihar
Debdeep Mukhopadhyay
Venue: ICML 2025 poster (2025)
Keywords: Variational Autoencoders
Sparse Linear Regression
NP-Hard
Smoothing
Sparsity
Matrix Conditioning
Primary area: deep_learning->generative_models_and_autoencoders
TL;DR: We use Variational Autoencoders that smoothen out bad local minima to solve the NP-hard inverse problem of Sparse linear regression and perform better than conventional methods.

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.

Be a Goldfish: Forgetting Bad Conditioning in Sparse Linear Regression via Variational Autoencoders
Kuheli Pratihar' Debdeep Mukhopadhyay
Abstract
1. Introduction
Variational Autoencoders (VAEs), a class of vatent-variable generative models, have seen ex- tensive 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 ca- pabilities, 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 Prin- cipal 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 exam- ine 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 incor- porating the product of the SLR design matrix with a trainable, pparsit-ppromoting diagonal ma- trix, any minimum of VAE loss is guaranteed be an optimal solution. This property is especially useful for identifying (a) preconditioning fac- tor 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. Over- all, this work highlights the flexible nature of the VAE loss, which can be adapted to efficiently solve computationally hard problems under spe- cific constraints.
Variational Autoencoders (VAEs) (Kingma & Welling, 2014) excel modeling complex, unknown distributions of observed data. Their ability to capture complex latent structures makes them particularly effective for high-fidelity image synthesis (Gulrajani et al., 2017), text generation in natural language processing (NLP) (Serban et al., 2017), and forecasting new data points in time-series analysis (Löwe et al., 2022). Despite these successes, the theoretical under- pinnings of VAEs remain only partially understood, leaving open questions about their full potential.
Recent theoretical developments have primarily exam- ined the latent space representational capabilities of VAEs (Zheng et al., 2022: Dai et al., 2018; 2021), which support high-quality reconstructions. However, when the observed data lies low-dimensional space, an affine VAE's latent representation effectively reduces to proba- bilistic PCA (Wipf, 2023). Under these conditions, there is little difference between VAE and a deterministic au- toencoder (AE), as both can learn the principal subspace of the data equally well (Dai et al., 2018; Lucas et al., 2019). Consequently, the primary value of these analyses lies in elucidating properties of the underlying energy functions, which guide the design of VAEs capable of accurately learn- ing data representations. Nonetheless, they constrain our perspective the broader capabilittes that VAEs may offer.
Confirming these observations, recent work (Wipf, 2023) leverages VAES to solve an NP-hard sparse inverse prob- lem an area in which generative models remain largely unexplored. In particular, (Wipf, 2023) finds the optimal solution for Simultaneous Sparse Regression (SSR), a task that conventional algorithms typically fail address reli- ably. This success stems from remarkable property: under specific mecodr-ddcoded architectures, VAEs exhibit no lo- cal minima. Consequently, all global minima correspond to the optimal solutions, providing a maximally sparse rep- resentation for SSR. These findings motivate the objective of broadening our understanding of VAEs as tools for solv- ing -h-hard problems under non-trivial conditions where existing algorithms fail to yield reliable solutions.
Department of Computer Science and Engineering, Indian Institute of Technology Kharagpur, Kharagpur, India. Correspon- dence to: Kuheli Pratihar kuhhlliue gmail.com>>.
Proceedings of the ndnd International Conference Machine Learning, Vancouver, Canada. PMLR 267, 2025. Copyright 2025 by the author(s).
In this work, we focus on Sparse Linear Regression (SLR) (Donoho & Stark, 1989). widely studied problem in

---

Be Goldfish: Forgetting Bad Conditioning in Sparse Linear Regression via Variational Autoencoders
high-dimensional statistics. The goal is to identify the opti- mal sparse solution for system of linear equations based observed data. The key challenge in SLR lies in identifying the sparse solution with the minimum error from a combi- natorial set of potential solutions. From an optimization perspective, SLR features a non-convex &y fy-oorm constraint coupled with a mean squared error objective, leading to a large number of suboptimal local minima and rendering the problem NP-hard. In this context, the ability of VAEs to eliminate spurious local minima becomes pivotal for recov- ering the optimally sparse solution.
we observe that the answer is affirmative. We conjecture that the VAE's inherent sparsity-inducing mechanisms con- tribute to this improved tolerance for low-sparsity scenarios.
In this work, we leverage the ability of VAEs to eliminate spurious local minima for the non-trivial settings of SLR. To summarize, our main contributions are:
Optimal Sparse Solution for SLR using VAEs: We show, for the first time, that VA can provably identify the optimal sparse solution for well-conditioned design matrices. This result relies on a VAE architecture with a linear encoder and decoder, both equipped with a sparsity-promoting diagonal matrix that eliminates lo- cal minima, thereby ensuring convergence to a global minimum.
Specifically, we consider two prominent non-trivial scenar- ios in which the sfate-of-the thetth art SLR algorithm, LASSO, provably fails (Kelner et al., 2022b). The challenge of identifying an optimal sparse solution among combina- torial set of suboptimal local minima is exacerbated when (a) the design matrix is ill-conditioned with highly corre- lated columns, or (b) the ground-truti truuh SLR coefficients are not sparse. Such conditions commonly arise in real-world and compressed sens-
Preconditioning for Ill-Condiiooned SLR: We demonstrate that VAEs inherently reduce the eigen- value spread of any full-rank fat design matrix, ef- fectively preconditioning it. In cases when the con- ditioning of the design matrix improves through this mechanism, VAEs achieve the optimal SLR solution.
settings, including ing (Rudelson & Vershynin, 2006; Hassanieh et al., 2012), as well as feature selection tasks in
ma- chine learning (PPML) (Akavia al., 2024; Li et al., 2021), thereby making the search for optimal solution substan- tially more challenging.
With the pro- posed encoder-decoder architecture, VAEs maintain a high recovery rate of sparse indices even at lower sparsity levels. Notably, we empirically demonstrate that for various types of design matrices, VAEs achieve greater tolerance to low sparsity at a fixed number of observations. In contrast, conventional algorithms such LASSO and augmented basis pursuit fail to perform well at lower sparsity levels.
Greater Tolerance to Low-Sparsity:
For an ill-conditioned design matrix, preconditioning (Kel- ner et al., 2022b; Wauthier et al., 2013) is often employed to improve its condition number. However, finding an ap- propriate preconditioner is a non-trivial task, and efficient algorithms do not exist. In this context, we ask:
How can we adapt VAEs to intrinsically precondition ill-conditioned design matrices?
The remainder of this paper is organized as follows. Sec- tion provides a detailed overview of the theoretical under- pinnings of VAEs. In Section 3, we discuss the fundamentals of SLR and its challenges. Section 4 begins by proving the existence of an optimal SLR solution using a VAE in the well conditondd case, followed by our proposed VAE ar- chitecture for preconditioning SLR. Section 5 details our experimental results for different types of design matrices, and finally, Section 6 concludes the paper.
While existing results show that VAFs with specific encoder- decoder architectures can provably achieve optimal sparse solutions for SSR (Wipf, 2023), they do not address the condition number of the design matrix. In this work, we propose a VAE architecture that intrinsically reduces the eigenvalue spread for any arbitrary full-rank fat design ma- trix, thereby preconditioning it. Consequently, design ma- trices whose condition number improves via this reduced eigenvalue spread can achieve the optimal SLR solution using the proposed VAE architecture. Next, in the case of large number of non-sparse coefficients, the most common strategy is to increase the number of observations in the SLR problem (Wainwright, 2006). However, classical algorithms typically fail when the level of sparsity is too low, leading to the question:
2. Background and Related Works
2.1. Variational Autoencoder
Formally, VAEs achieve this by training a 0-parameterized marginal distribution (x),, defined as:
=f / 2) dz
po (x) =
(1)
Can VAES intrinsically extend the sparsity threshold for SLR with a fixed number of observations?
where x E Rd is the d-dimensional observed data, z E R" is n-dimensional unobserved latent variable. In scenarios
Through empirical evaluations of various design matrices,
2

---

Be Goldfish: Forgetting Bad Conditioning in Sparse Linear Regression via Variational Autoencoders
where has low dimension, one often enforces n d to limit the number of latent dimensions. However, directly computing (1) is typically not feasible because the joint distribution pe (x, z). which is also needed to find the true posterior (2 x), is intractable in most practical set- tings. Consequently, VAEs employ Variational Inference (VI), which recasts the approximation of the ground-truth distribution as an optimization problem by replacing the intractable posterior pz x) with simpler distribution [z(2] x) (often Gaussian) and minimizing their Kullback- Leibler (KI.) divergence between them.
reconstruction error. Moreover, the global minima of such a marginalizaation-aasel VAE loss correspond to the optimal sparse representation for the NP-hard Simultancous Sparse Regression (SSR) problem, where no polynomial-tinn al- gorithm is known. This smoothing mechanism thus helps climinate the exponential number of suboptimal sparse so- lutions in SSR that arise for given sparsity level. Several other studies have also examined the optimization trajectory of VAEs (Dai et al., 2018; Shekhovtsov et al., 2022; Zietlow et al., 2021; Damm et al., 2023). These insights pave the way for designing VAE architectures that remove bad local minima in other sparse inverse problems, such as sparse linear regression (SLR), the primary focus of our work.
To perform this optimization, VAEs adopt an autoencoder- style architecture in which the encoder, parameterized by d, approximates the posterior te x), and the decoder, parameterized by 0, models the likelihood po(x | z). In practice, both are often chosen to be Gaussian:
In the next section, we elaborate on the challenges of solving SLR that motivate the construction of our proposed VAE technique.
[x 2) = N(x
Pz (z IT),
3. Challenges in Solving Sparse Linear Regression
(z(z x) = N(z Ms (x: 6), [x(x;) 6)),
(2)
together with the prior p(z) = ((z 0, O)). Here, 7 > 0 is a (trainable or fixed) scalar variance, and the functions ua (z; 0), Pa (x; Φ). and Σx (x; o) are instantiated by neural networks. With the above modeling. the KL-divergence between intractable posterior (z|xx) with simpler distri- bution qo (z)x) can be simplified to obtain VAE loss C(o, 0) given by:
In sparse linear regression (SLR), we are given a design matrix & E pdxxn and observations x E IR' satisfying
x = 42 + "7
(4)
where z" E R² is n-sparse coefficient vector, meaning it has at most K non-zero entries, and 17 TRd is small noise term. This is hard problem compared to standard linear regression, where there are no constraints on the sparsity of z and can be optimally solved using the ordinary least squares (OLS) algorithm. The SLR hardness arises from the difficulty in searching through an exponential solution space where both the location and the value of the sparse coefficients are unknown. Our goal is find k-sparse ă that minimizes the lg error with the sparsity constraint:
-Eg (xlx)) [x 2)] + +LL[gst [2 x) [[)]]
The first term in this expression is the reconstruction loss, while the second is the regularization term expressed as the KI. divergence between the learned latent distribution and the prior. The loss in (3) is then optimized over (o, 0) on the training data using stochastic gradient descent (SGD) to find the optimal latent representation or to generate synthetic samples from the input.
2 = arg
min x: [xl|o
||x
& 22
(5)
2.2. VAE Global Minima Analysis
Because the lo constraint makes (5) nonconvex, a frequent strategy is to add a sparsity-inducing penalty term g(z.) for each coefficient:
Prior theoretical analyses of VAEs have shown that global minima of the VAE objective can indeed recover the derlying data manifold (Zheng et al., 2022; Koehler et al., 2022; Dai et al., 2017; Lucas et al., 2019), demonstrating their excellence in approximating the ground-truth distri- bution. However, reaching these global minima is often delegated to an optimization algorithm such as SGD, which can be hindered by spurious local minima in the VAE loss landscape. Interestingly, it has been shown that certain ar- chitectural modifications to VAEs can eliminate these bad local minima, thereby facilitating convergence to the global optimum. First conjectured in (Dai & Wipf, 2019) and later proven in (Wipf, 2023), marginalizing over the posterior distribution effectively smooths away spurious minima that exploit an excessive number of latent dimensions to reduce
2 = arg min ||x + 21 + X > 9(x),
(6)
where À >> 0 is a trade-off parameter. A widely used choice for g(2,) ) is the f, norm, which gives the LASSO (Tibshirani, 1996), i... Σ.
||
However, the performance of LASSO depends on the con- ditioning of the design matrix &b In particular, a random i must often satisfy a small Restricted Isometry Constant (RIC) (Candes & Tao, 2005), which ensures that & behaves nearly like an orthonormal system on every k-sparse subset of coefficients (see below for definition). Concretely, no set
3

---

Be Goldfish: Forgetting Bad Conditioning in Sparse Linear Regression via Variational Autoencoders
of x columns in & is nearly linearly dependent, so no sparse vector z is "collapsed"" or "inflated" by T.
where + = P = Px, and x" remains the same K- sparse solution in (4). The key requirement is that + be better conditioned (exhibit a smaller å and a bounded condi- tion number), thus enabling LASSO or related algorithms to recover the optimal sparse representation more reliably.
Definition 3.1 (Restricted Isometry Constant), Let o E Rdxx be a real matrix. For an integer is Σ n, the n- Restricted Isometry Constant å of & is the smallest non- negative number such that,
However, constructing a suitable preconditioner can be chal- lenging and often relies on specific properties of 4, such as low treewidth in a Markov structure (Kelner al., 2022a). Moreover, (Gupte et al., 2024) shows that there exist ill- conditioned 4 for which no polynomial-time algorithm can produce a preconditioner sufficient to achieve the optimal solution, implying an average-case hardness for SLR.
(1 6)
5) ||21|2
122 S (1+ (1+5) |2|2
for every vector E IR that has at most nonzero entries. We abbreviate this condition as Restricted Isometry Property (RIP) for future use.
One can equivalently interpret this definition in terms of singular values of all k-column submatrices of Φ: small 5 forces those submatrices to be well-conditioned.
3.3. Sample Complexity in Solving SLR
Although LASSO is the de facto algorithm for sparse linear regression (SLR) when the design matrix is well- conditioned, requires on the order of = Oxx log n) observations to reliably recover the optimal solution (Kel- ner et al., 2024; 2022b). Consequently, if the number of non-zero elements is large and the number of samples is in- sufficient, LASSO fails. In fact, (Zhang et al., 201 I) shows that solving SLR with lower sparsity levels (i.e., fewer zero entries) can be significantly more challenging than the case of higher sparsity. Confirming this limitation of LASSO, prior works on preconditioning SI. generally target higher sparsity levels (Kelner al., 2022b; Wainwright, 2006; Jia & Rohe, 2015). However, in this work, we also consider the regime of lower sparsity.
3.1. Requirements for Well-conditioning
A helpful viewpoint is to examine the (scaled) "Gram matrix" Σ 1 Φ +b E Raxn, This Gram matrix perspective also arises when the rows of & are sampled i.i.d. from a distribution with covariance E. In that setting, Σ = _ 4 serves as the empirical (sample) covariance. If 4 satisfies the RIP with å sufficiently small (e.g. d < 1), then for every s-sparse vector z R",
|| 2212 dz
1
2 2
d dzz'Ez)
(8)
51 2
v d Iz Σz] S (1+ 6) 1z/2
(9)
Hence, all eigenvalues of E lie in the interval [1 5, ++ j.. which implies.
Next, we describe how VAEs can help overcome these chal- lenges in solving SLR despite ill-conditioning and an unfa- vorable sparsity regime.
= 0 max
Σ>
1+6 1-
cond( [
(10)
Tmin [Σ)
where co is the condition number. Thus, a small RIC 5 guarantees not only that ob acts almost as an isometry on all s-sparse vectors, but also that the Gram matrix Σ is well-conditioned.
4. Optimal SLR Solution using VAE
Leveraging the bad local minima smoothening property of VAEs (Wipf, 2023), we first demonstrate how VAEs, con- structed with specific encoder-decoder architecture, can achieve an optimal sparse representation for SLR (6). We do so in the noise-free scenario when the design matrix & is well-conditionss we propose a VAE architecture with intrinsic precondition- ing that reduces the spread in the eigenvalues, leading to well-conditioned & under certain conditions.
3.2. Preconditioning for Ill-Conditioned Design Matrices
Thereafter, for an ill-conditioned &b
When I does not satisfy the RIP, or equivalently when cond(E) is large (indicating ill-conditioning typically caused by highly correlated columns), finding an optimal パ- sparse solution is generally computationally intractable (Kel- ner et al., 2022a). Nonetheless, methods such as LASSO and other sparse estimators can often perform well in prac- tice if Σi is sufficiently well-conditioned (Gupte al., 2024; Kelner et al., 2022a).
We define optimal sparse representations as such that x z with k-sparse z achieves zero reconstruction error:
||x 1
p Iu (x::) = 0,
(12)
A standard approach for improving conditioning is precondi- tioning: we multiply both & and x by a matrix P E Raxn The resulting preconditioned SLR is given by:
where μ. is the encoder output and μt, is the decoder output for VAE (2). This condition, described in (Dai et al., 2021), is admittedly restrictive but is nonetheless employed as the search objective in many sparse-inverse problems (Candes & Tao, 2005; Candès et al., 2006). Thereafter, we use the
Px 2 + P w -
x +z W. (11)
4

---

Be Goldfish: Forgetting Bad Conditioning in Sparse Linear Regression via Variational Autoencoders
following lemma from (Dai & Wipf, 2019) to ascertain the sparse representational properties of VAE:
where 0- {Wa: 7) and (W s,
We are now positioned to show that, when the design matrix + is well-conditioned (i.e. there are no closely correlated columns), the loss function in (13) does not admit any "bad" local minima.
Lemma 4.1. Assume a Gaussian VAE model of continuous data defined by (2), where Ps W² z + b2 for some weight matrix W. and bias vector by; similarly, Phg = W, x + b= for some weight matrix W and bias vector by and Σ. = diag(s,² ? where s is an arbitrary parameter vector independent xf Then for any fixed value of y all local minima of the resulting VAE objective with respect to the parameters {Wa: n, bz. W., b2.8) $ are also global minima. Moreover, these global minima produce optimally sparse representations (12), when y +
Theorem 4.2. Any local minimum of (13), {w2, W $}
with a fixed n, is also global minimum. When " - 0, and 4 is well-conditioned, satisfying the RIP condition for small 8, the global minima achieve the optimal sparse solution for SLR in (4). The resulting sparse coefficients are given by:
á = diag w=] ] T (Φ diag W=
X.
(14)
This lemma highlights how linear encoder-decoder architec- tures can attain sparse latent representations when the data lies on -ow-dimensional manifold. Intuitively, an optimal sparse representation occurs because each local/global mini- mum selects principal subspace of the data while using the fewest possible nonzero columns of W Furthermore, at the indices of those zero-valued columns, elements of s tend to zero as 7 - 0. In contrast, the corresponding elements of frg convey the information about x (i.e., the active, non- random dimensions) needed for exact data reconstruction. Next, we propose a VAE architecture, following Lemma 4.1, for the SLR objective (6).
For brevity, the proof has been deferred to the Appendix A. We first show that (13) has no bad local minima, under the assumption that T is well-conditioned or satisfies the (xs, 6)- RIP with d < 1. With a perfect optimizer, a full rank & ensures the presence of a unique inverse Σ (ww for each w, leading to no bad local minima. However, practical SGD might identify distinct w's with close inverse values. We use the RIP bound ō to ensure that the difference in inverse terms is large enough to be detectable by SGD. For sparse Z, the RIP bound å can be expressed as a weighted sum of activated column norms of 4 and cross correlations between them. However, the presence of aligned columns leads to large correlations, increasing the value. This reduces the difference in inverse terms for distinct w's that differ along the indices of the aligned columns, leading to the requirement of a small o to find the true optimum. Thereafter, using Lemma 4.1, we show that for such a well- conditioned o, this global minimum of (13) coincides with the optimal sparse solution in the limit 7 - 0.
The SLR objective is closely tied to learning data-specific latent prior p(z) in variational Bayes (VB) methods (Wipf et al., 2011). However, in contrast to VB methods that model the prior distribution on the latent space, we pro- pose encoding the "sparsity" information via a trainable diagonal matrix in the VAE decoder, assuming standard Gaussian as the latent prior. We later demonstrate that such an encoding is beneficial for learning the optimal sparse representation (12) as opposed to finding the optimal latent prior for VB methods.
Interpretation of Theorem 4.2: The key takeaway for The- orem 4.2 is that one can construct VAE architecture for SLR with a trainable diagonal matrix to enforce sparsity rather than relying on an explicit & penalty (as in LASSO). Moreover, the VAE-based approach, grounded in variational inference, can learn both the mean (W :) and covariance (S ) of the sparse coefficients, thus embedding informa- tion about both the number of nonzero coefficients and their distribution. This is distinct from classical & regularization algorithms such as LASSO, which focus on constraining the number of nonzero coefficients but do not explicitly model their distribution.
The resulting decoder's Gaussian distribution po (x(z)) [(x; + diag] (,.. x) z, ?I) is parameterized by: fh T diag wz] z, and Σz = -I, where diag w.]] is sparsity- promoting diagonal matrix which selects the non-zero sparse features from & implicitly during the training process. Next, for the encoder, we use a linear mean vector μ = W. x where W₂ E Rndd and a full-rank covariance Σ, = SS with S E Ru arbitrary and independent of x. Note that, we assume & E ædxn a fat, full-rank matrix, i.e. d < n and rank ))) = min( dd n) d. This full-rank constraint ensures that & has d nonzero eigenvalues.
Nonetheless, the requirement that & be well-conditioned motivates further consideration of how VABs can be adapted for ill-conditioned dictionaries, which we address next.
With these choices, the VAE energy from (2), applied to the training data x, reduces to:
4.1. Preconditioning using VAFs
1 x + diaglw w z 6(),6) = (xlx))
27
+ d log
In order to achieve the loss-smoothing property for (13), the columns of & must be non-collinear. When & is ill- conditioned, its columns are nearly linearly dependent, lead-
7
+ ur/ss]]
[
loglss + ||W [W+X}3
(13)
5

---

Be Goldfish: Forgetting Bad Conditioning in Sparse Linear Regression via Variational Autoencoders
ing multiple local minima with distinct solutions in (13). Ill-conditioning can be reflected in various properties, such as failing the (KS, 8 RIP for smaller å or having a large condition number. Here we focus on reducing the condition number of & using VAEs, as it is directly tied to the spread of its cigenvalues. The well-known ridge regularizer (Hoerl Kennard, 1970) provides a way to shrink this spread for a given y via the preconditioning factor:
and we show that (17) can eliminate unwanted local minima if the optimal y also yields an P satisfying (K, (K,6)-RIP for some 6 < 1.
Theorem 4.4 (VAE-Induced Preconditioning). Any mini- mum { (w., W 2, S) of (17) a given 7 is a global min- imum if. P
[ 2 + 1) -1 4b satisfies the RIP con-
dition with 5 < 1. Under this circumstance, the global minimum matches the optimal sparse solution for SLR in (6) only if is small enough to meet the limiting conditions of Theorem 4.2, The resulting sparse coefficient & is given by:
P =
( + T +T11-1 E RRdd
(15)
While conventionally employed to boost the eigenvalues of low-rank matrices, we use (15) to reduce the difference between the largest and smallest eigenvalues of the (fat) full-rank matrix 4.
diag wa] 2 T PTT (P4 diag W. 2 o T PP)) Px.
(18)
The term is a training parameter in Theorem 4.4, which effectively penalizes the condition number of 4 in the VAE objective (17). As shown in Lemma 4.3, any positive value of y improves the condition number of P compared to &. Therefore, adding Y to the overall loss function improves the effective condition number of 4, pushing it to satisfy the RIP property (Appendix C). This assists in achieving the optimal sparse solutions for ill-conditioned design matrices where LASSO fails (Kelner et al., 2022a).
Lemma 4.3. Let & E Rdxn have rank r S minff, n), and let P be defined by (15). Then,
min +
cond P Φ) = cond +)-
cond )),
4
+
max
where max ) and minn (+) are the largest and smallest singular values of b. respectively.
This lemma shows that left-multilyying & by ($4" T I)- compresses its singular values, reducing the con- dition number unless o originally had all singular values equal (Appendix B). Under the assumption that + has d nonzero eigenvalues (i.e., & is full rank), any y >> 0 strictly improves cond ()) Whether this improvement is sufficient to satisfy the RIP condition (with small 8) depends the chosen
Interpretation of Theorem 4.4: From the proof of Theo- rem 4.4, we see that there can be multiple values of y that make the preconditioned design matrix & satisfy the RIP condition. For each such y", the VAE smoothens out bad local minima and converges to global minima. However, Theorem 4.2 tells us that the final solution only matches the true sparse representation when we choose approaching zero Thus, the desired solution for ? must be sufficiently small so that the global minimum of (17) aligns with the limiting case of > + 0 (using the preconditioned and x). Consequently, if an ill-conditioned design matrix can be preconditioned with suitably small 7 to satisfy the RIP condition, VAE can solve the corresponding SLR problem. Although this requirement is restrictive, it does occur in practice for certain ill ill-conditioned design matrices, as shown in Section 5.
We now define a VAE architecture that sinultaneously seeks to evaluate the optimal sparse coefficients z and the regu- larization term Y, to target satisfying (n. 5--RIP for some 5 < The key idea is to precondition & by P directly within the VAE training process, potentially revealing global optimum that meets the RIP condition. Specifically, the decoder's ' Gaussian distribution is updated to:
( 2) = N(x: P& diag(w,) (w.) ) z, 7 I)), (16)
where we reuse the same 7 for both the decoder covariance y and the preconditioning term P. This unifies the effect of y on preconditioning and the variance for the sparse com- ponents in the decoder. As & is of full rank, its condition number improves through multiplication by P. Similarly, we adjust the mean vector μ W P x in the encoder and maintain the full-rank covariance ss Consequently, the original VAE loss in (13) becomes:
4.2. Additional Perspectives
We now highlight some of the additional perspectives that can be drawn from the results in this section. They include a comparison with statistical methods for SIR, such as sparse Bayesian learning (SBL), and the role of VAEs in addressing challenging cases of ill illconditioned SLR design matrices.
1.2.1. COMPARISON WITH SPARSE BAYESIAN LEARNING
() = Bgg(2(x)
-
Px - P& diag(w.))
Addressing one of the key discussion points brought forth by an ICML 2025 reviewer during the evaluation of this paper, we compare our approach with Sparse Bayesian (17) learning (SBL) (Tipping, 2001; Wipf et al., 2011; 2015)
+ d log + tr [
- logg SS + | |
6

---

Be Goldfish: Forgetting Bad Conditioning in Sparse Linear Regression via Variational Autoencoders
in detail. SBL is an empirical Bayesian method for solv- ing SLR, which outperforms LASSO in support recovery accuracy (Lin et al., 2022). However, it relies type II maximum likelihood estimation, which benefits from prior knowledge of the distribution of the nonzero coefficients in z. In the absence of this prior information, SBL resorts to expectation maximization (EM) algorithms to optimize the SLR objective. Our proposed VAE addresses the limitations of SBL. as described below:
to facilitate sparse recovery. However, the impact of precon- ditioning on the solvability of SLR depends the matrix structure and how significantly its eigenvalues can be equal- ized. Hereafter, to validate our theoretical results in this section, we conduct the corresponding empirical analysis of SLR using various design matrices in Section 5.
5. Empirical Validation
To re-iterate, VAE-basee sparse recovery aims to iden- tify the positions of non-zero coefficients rather than directly estimating their values. Once the correct support (non-zero coefficient positions) is identified, the SLR problem sim- plifies significantly and can be solved using ordinary least squares (OLS). Under a full-rank design matrix and Gauss- Markov assumptions, OLS is an unbiased estimator leading to optimal sparse recovery with no bias.
1. Global Optimum: The global minimum in SBL for SLR corresponds to the optimally sparse coeffi- cients (Wipf & Rao, 2004); however, EM algorithms may converge to spurious local minima. Our VAE architecture smooths the loss landscape, enabling con- vergence to the global minimum, which coincides with the optimal sparse solution (Theorem 4.4).
Our experiments cover three types of design matrices in a noiseless setting We compare our approach, presented in Theorems 4.2 and 4.4, with established methods like LASSO (Tibshirani, 1996). SBL (Lin et al., 2022), and augmented basis pursuit (Kelner et al., 2024), for both well- conditioned and ill-conditioned design matrices. The VAE is trained using SGD with x. We first select uniformly random sparse locations within an n-dimensional vector, then sample x non-zero coefficients from standard normal distribution to obtain sparse coefficients z. Thereafter, x is generated by multiplying z with the design matrix 4. These x values are used to train the VAE using SGD.
2. Handling Ill-conditioned Matrices:
Design matrices that violate the RIP bound can cause numerical instabil- ity in the matrix inversion step of SBL's EM algorithm, reducing the sparse recovery rate. In contrast, our VAE preconditions the design matrices to satisfy the RIP bound, achieving higher recovery rate at the same sparsity level.
3. Computational Complexity: Each EM iteration in- volves a matrix inversion of time complexity O(n²), ) making SBL computationally expensive and limiting its scalability. In contrast, training our linear VAE via backpropagation runs in Onn)) time per epoch, since it avoids matrix inversion.
All the relevant codes and detailed user manual for replicating the experiments in this work are avail- able at https: wtt.:/hhii...o//AAA--IIAAA-AA-AA Be-a-Goldfishh SaafffishSSovving Swws-sooliiniii SSLR-using-Va
4. Implicit Sparsity Prior:
Our VAE overcomes the lack of prior knowledge on the sparse coefficients by in- corporating a trainable diagonal matrix diag(w) in the decoder, which implicitly captures sparsity information without requiring an explicit prior distribution.
5.1. Design Matrix from Standard Gaussian Distribution
In our first scenario, we construct design matrix + by drawing its features from a standard Gaussian distribution (Φ,,;~ ~ (O, I)). We set n = 200 features and d = 100 ob- servations, then recover the sparse coefficients 2 at different sparsity levels K E {2, 10, 20, 40, 50, 60). Repeating the experiment 10 times with randomly sampled features and non-zero coefficients yields the sparse support recovery rates shown in Fig. ((a). Compared to standard LASSO and SBL, our linear VAE approach, as presented in The- orem 4.2, achieves a higher recovery rate, particularly at lower sparsity.
4.2.2. HARD CASES OF ILL-CONDITIONED DESIGN MATRICES
While Theorem 4.4 shows that VAEs can narrow the eigen- value range of an ill-conditioned design matrix, it remains to be seen whether different kinds of ill ill-conditione ma- trices truly benefit from such preconditioning and can be considered as future direction. Interestingly, there are certain special classes of ill-conditioned matrices with a unique sparse solution, for which achieving lower error than LASSO is tantamount to breaking post-quantum assump- tions in lattice problems (Gupte et al., 2024). As result, some matrices may stay intractable even if a VAE-based approach reduces their eigenvalue separation. Nonetheless, whenever preconditioning succeeds in shrinking the spread of eigenvalues, the improved conditioning has the potential
For LASSO, the probability of recovering the correct sparse coefficients is governed by control parameter n-x-1 when the features are drawn from stan- 0_ 2x log(d-xj+
'Our technique also applies to noisy sparse recovery, dis- cussed Appendix
7

---

Be Goldfish: Forgetting Bad Conditioning in Sparse Linear Regression via Variational Autoencoders
exhibits higher tolerance to lower sparsity (i.e., larger k). We conjecture that this robustness arises because the VAE can learn both the mean and covariance parameters of the sparse coefficients. In contrast, LASSO focuses explicitly on reducing its & norm for promoting sparsity.
Lasso
SBL
VAE
Support Recovery Rate
1.0
Well-conditloned standard Gaussian design matrix
0.8
observations n = 500 features =100
0.6
Proposed VAE
0.4
5.2. Design Matrix from Gaussian Random Walk
0.2
Next, we construct an ill-conditioned + by drawing its features from a Gaussian random walk distribution. Specif- ically, the rows of & are i..d. copies of the elements of a random walk with i (ri,72....,.? ] where.
0.0
0
20
40
60
Number of nonzero entries (k)
(a)
To = r--1 +-i+t 1, 2 ~~N10,11 r ri 1),
(19)
Lasso SBL-
AugBP VAE PreconVAE
Support Recovery Rate
1.0
Ill-conditioned Random
This construction yields a covariance matrix Σ, = min(i, j). which has high condition number. As shown in (Kelner et al., 2022b), such a design matrix cannot be solved using LASSO without appropriate preconditioning. We employ the same matrix dimension and the sparsity val- ues as the previous case of standard Gaussian covariance in Section 5.1.
Walk design matrix
0.8
observations n=200
features =100
0.6
Proposed precenditioned VAE
0.4
0.2
0.0
Our empirical results in Fig. I(b) confirm that, while solu- tions without preconditioning fail, SBL (Lin al., 2022), augmented basis pursuit (Kelner et al., 2024), and our pre- conditioned VAE (Theorem 4.4) recover sparse solutions for low sparsity levels (e.g.. = 2). However, (i.e., as sparsity decreases), the preconditioned VAE out- performs other methods by maintaining higher recovery rate until K I 20. We conjecture that the VAE's learned preconditioning factor y effectively improves the condition number of & and enforces the RIP condition for small 6, leading to high recovery rates for 20.
20
40
60
Number of nonzero e entries (k)
(b)
increases
LessO
AugBP
VAE- PreconVAE
1.0
Support Recovery Rate
Practical Riboflavin
0.8
design matrix
observations n=71 features =100
0.6
Proposed
0.4
preconditioned VAE
5.3. Practical Design Matrix from Riboflavin Dataset
0.2
Lastly, we evaluate SLR on a design matrix constructed from real-life biological measurements in the riboflavin dataset (Bühlmann et al., 2014). The genetic features in this dataset are correlated, making & inherently ill-conditioned. Practical constraints limit the number of features to d = 100 and the number of observations to n = 71. Given the sam- ple complexity for successful LASSO is in the order of (xxx log(d)) (Kelner et al., 2022b), the smaller sample size in this case tests the low-sparsity tolerance of our precon- ditioned VAE (Theorem 4.4) in particularly challenging setting. Nevertheless, Fig. 1(C) shows that the precondi- tioned VAE achieves the highest recovery rate for K S 10. Although k = 10 represents a higher sparsity limit than in Fig. 1(a) and (b), our method still surpasses existing al- ternatives under these challenging conditions. Increasing the number of features d 200 leads to similar support recovery Fig. 1(c), as shown in additional experimental results in Appendix D.
0.0
20
40
60
Number of nonzero entries (k)
(c)
Figure 1. Sparse support recovery rate for SLR vs. increasing number of non-zero zero entries in z or the s-sparsity level for features of design matrix ;; sampled from (a) standard Gaussian, (b) Gaussian random walk, and (c) Ribotlavin dataset (Bühlmann al., 2014) for different recovery methods.
dard Gaussian (Wainwright, 2006). This sample complexity relationship aligns with our observations in Fig. I(a), where LASSO's s recovery rate diminishes as K increases. Indeed, for к > 30, LASSO's 's recovery rate falls to zero, reflecting the near-zero success probability reported in (Wainwright, 2006) for Og- < 0.22. By contrast, our VAE- method
8

---

Be Goldfish: Forgetting Bad Conditioning in Sparse Linear Regression via Variational Autoencoders
5.4. Impact of SLR Parameters on Sparse Recovery
methods, such as VAEs, may offer greater flexibility in han- dling lower sparsity. With all the above interesting insights, next, we conclude our paper.
As suggested by reviewers during the ICML 2025 rebuttal phase, evaluate the effect of changing SLR parameters on the support recovery performance using our proposed VAE. All detailed results can be found in Appendix D. We summarize the key takeaways as follows:
6. Conclusion and Future Work
In this work, we broaden our understanding of the local minima smoothing property of VAES in the context of well-known NP-hard problem in high-dimensional statistics: Sparse Linear Regression (SLR), Our primary focus is on scenarios involving ill-conditioned design matrices and low sparsity, where classic methods such as LASSO often fail. A key limitation of LASSO is that it reformulates the lo sparsity constraint into an é regularization objective, which can struggle to recover the optimal solution when the design matrix is poorly conditioned or the sparsity level is low.
1. Design matrix dimensions:
The preconditioned VAE consistently outperforms competing methods in sup- port recovery rate, both as the number of features n and the number of observations d increase. The reason is the presence of more information for solving the SLR problem.
2. Nonzero coefficient distribution: Our VAE's focus on support identification makes it insensitive to the non- zero coefficient distribution. Empirical results confirm similar recovery rates across various distributions of the nonzero coefficients.
By contrast, our central insight is that VAEs can simulta- neously impose sparsity constraints and learn the under- lying distribution of sparse coefficients, enabling more in- formed feature selection. Leveraging this capability, we pro- pose VAE architecture that intrinsically preconditions ill- conditioned design matrices, thereby surpassing LASSO in specific matrix classes. Across different types of design ma- trices, the VAE-based approach consistently demonstrates a higher tolerance for sparsity compared to LASSO and previously introduced preconditioning techniques. Overall, our findings expand the applicability of VAEs to NP-hard sparse inverse problems-an area where generative models have yet to be thoroughly explored. This work opens several promising research directions:
3. Noise level:
To assess the impact of additive noise 77, we conducted experiments at different SNR lev- els. While all methods improve with higher SNR, our VAE achieves superior recovery rates even at lower SNR. This robustness can be further enhanced by pre- processing techniques such as filtering or mixture-of- Gaussians models (Guo et al., 2021).
5.5. Fixed vs. Trainable y during Preconditioning
Theorems 4.2 and 4.4 show the existence of optimal sparse solutions when 7 - 0, and our empirical results in achieve the same for most cases except when SGD fails to attain the limiting solution. The trainable y assists in achieving a higher support recovery rate of the preconditioned VAE for ill-conditioned SLR compared to fixed 7.. Although pro- posed VAE architecture can achieve no bad local minima condition for fixed y, optimal sparse recovery with y - is contingent the success of the optimization algorithm. Imperfect optimization can hinder achieving this ideal sce- nario, as evidenced by our empirical results in Appendix D.
1. SLR in Challenging Domains: The ability of VAEs to handle low-sparsity and ill-conditioned design ma- trices in SIR is highly relevant to applications such as feature selection for privacy-preserving machine learning (Akavia et al., 2024; Li et al., 2021), neu- ral imaging of brain function (Shen et al., 2022), and genome selection in cancer research (Fan et al., 2024).
2. Theoretical Underpinnings for VAE-Based Solu- tions:
Our results suggest that existing limits on the solvability of SLR under LASSO can be pushed by em- ploying variational methods for sparse recovery, which account for both the sparsity constraint and the distri- bution of sparse coefficients. Future work includes investigating new preconditioning strategies for ill- conditioned design matrices and sample complexity bounds for accurate recovery in low-sparsity regimes.
5.6. Insights on Higher Tolerance to Low-Sparsity
A higher tolerance for low sparsity translates into obtaining an optimal sparse solution using fewer observations, thereby reducing data collection overhead. This advantage is par- ticularly beneficial in biological contexts, where datasets can contain millions of features (Rives et al., 2021). To encourage the adoption of VAE-based methods in such set-
tings, a solid theoretical understanding of SLR's 's solvability is essential. Although prior work (Kelner et al., 2020; 2024; Wainwright, 2006) has explored sample complexity limits for LASSO-based SLR, our findings suggest that variational
By uniting insights from generative modeling and high- dimensional statistics, our work broadens the theoretically grounded approach of VAEs in solving NP-hard inverse problems under specific constraints.

---

Be Goldfish: Forgetting Bad Conditioning in Sparse Linear Regression via Variational Autoencoders
Impact Statement
Dai, B. and Wipf. D. Diagnosing and Enhancing VAE Models. International Conference Learning Represen- tations, 2019.
This work bridges the fields of generative modeling and high-dimensional statistics. We leverage VAEs solve the well-known NP-hard problem of sparse linear regression (SLR). Traditional SLR methods often fail in real-world settings that feature correlated features or have a limited number of observations. VAEs can intrinsically "precondi- tion" these matrices under certain conditions, leading to a higher recovery rate.
Dai, B., Wang. Y., Aston, J., Hua, G., and Wipf, D. Hidden Talents of the Variational Autoencoder. arXiv preprint 1ew.:170.052000 2017.
Dai, B., Wang, Y., Aston, J., Hua, G., and Wipf, D. Connec- tions with Robust PCA and the Role of Emergent Sparsity in Variational Autoencoder Models. Journal of Machine Learning Research, 19(41):1-42, 2018.
From societal perspective, this result holds significant promise. It enables the accurate recovery of sparse signals in domains such neurological imaging, cancer genomics, and system identification. This VAE-based approach pro- vides faster and more precise insights, which can improve healthcare outcomes and drive scientific progress. Addition- machine learning, reliable SLR method can reduce training data requirements. This, in turn, helps safeguard sensitive information while lowering com- munication costs. Looking forward, employing VAEs for NP-hard inverse problems opens avenues for innovation in machine learning and statistical modeling. Researchers and practitioners can harness these generative capabilities to tackle applications where data is limited. Therefore, our pro- posed approach makes meaningful contribution broader scientific and societal benefits.
Dai, B., Wenliang, L.,, and Wipf, D. On the Value of Infi- nite Gradients in Variational Autoencoder Models. Ad- vances in Neural Information Processing Systems, 34: 7180-7192, 2021.
ally, in
Damm, S. al. The ELBO of Variational Autoencoders Converges to Sum of Entropies. In International Con- ference on Artificial Intelligence and Statistics, pp. 3931- 3960. PMLR, 2023.
Donoho, D. L. and Stark, P. B. Uncertainty Principles and Signal Recovery. SIAM Journal on Applied Matematics, 49(3):906 931, 1989.
Fan, K., Subedi, S., Yang. G., Lu, X., Ren, J., and Wu, C. Is Seeing Believing? A Practitioner's 's Perspective on High- Dimensional Statistical Inference in Cancer Genomics Studies. Entropy, 26(9):794, 20244
Acknowledgement: Our profound appreciation goes to the anonymous reviewers for their constructive feedback, which greatly refined this paper. Additionally, the authors are thankful for the partial funding received from the Center for Hardware-SScurity Entrepreneurship Research & De- velopment (C-HERD) and Information Security Education and Awareness (ISEA), both initiatives of MeitY, Govt. of India. Lastly, the authors were also partially supported by Qualcomm with Reference under Grant IND-492686.
Guirajani, I. et al. PixeIVAE: A Latent Variable Model for Natural Images. International Conference on Learning Representations, 2017.
Guo, Y., Wang, W., and Wang. X. A Robust Linear Re- gression Feature Selection Method for Data Sets With Unknown Noise. IEEE Transactions on Knowledge and Data Engineering, 35(1):31-44 2021.
References
Akavia, A. et al. Privacy Preserving Feature Selection for Sparse Linear Regression. Proceedings on Privacy En- hancing Technologies, 2024.
Gupte, A., Vafa, N., and Vaikuntanathan, V. Sparse Linear Regression and Lattice Problems. In Theory of Cryptog- raphy Conference, pp. 276-307. Springer, 2024.
Bühlmann, P., Kalisch, M., and Meier, L. Biigh--immsiionll Statistics with a View Toward Applications in Biology. Annual Review of Statistics and Its Application, 1(1):255- 278, 2014.
Hassamieh, H., Indyk, P., Katabi, D., and Price, E. Simple and Practical Algorithm for Sparse Fourier Transform. In Proceedings of the twenty-third annual ACM-SIAM symposiam on Discrete Algorithms, pp. 1183-1194, 2012.
Candes, E. J. and Tao, T. Decoding by linear programming. IEEE transactions on information theory, 51((2)44203- 4215, 2005.
Hoerl, A. E. and Kennard. R. W. Ridge Regression: Biased Estimation for Nonorthogonal Problems. Technometrics, 12(1):55-67, 1970.
Candès, E. J., Romberg, J., and Tao, T. Robust Uncertainty Principles: Exact Signal Reconstruction From Highly Incomplete Frequency Information. IEEE Transactions on information theory, 52(2):489-509, 2006.
Jia, and Rohe, K. Preconditioning the Lasso for sign consistency. Electronic Journal of Statistics, 9:1150- 1172, 2015.
10

---

Be Goldfish: Forgetting Bad Conditioning in Sparse Linear Regression via Variational Autoencoders
Kelner, J., Koehler, F., Meka, R., and Moitra, A. Learning Some Popular Gaussian Graphical Models without Con- dition Number Bounds. Advances in Neural Information Processing Systems, 33:10986-1000 10998, 2020.
Shekhovtsov, A. al. VAE Approximation Error: ELBO and Exponential Families. In International Conference on Learning Representations, 2022.
Shen, L.,, Pauly, J.,, and Xing. L. NeRP: Implicit Neural Rep- resentation Learning with Prior Embedding for Sparsely Sampled Image Reconstruction. IEEE Transactions on Neural Networks and Learning Systems, 35(1):770-782, 2022.
Kelner, J., Koehler, F., Meka, R., and Rohatgi, D. Lower Bounds on Randomly Preconditioned Lasso via Robust Sparse Designs. Advances in neural information process- ing systems, 35:24419 24431, 2022a.
Kelner, J., Koehler, F., Meka, R., and Rohatgi, D. Feature Adaptation for Sparse Linear Regression. Advances in Neural Information Processing Systems, 36, 2024.
Tibshirani, R. Regression Shrinkage and Selection via the Lasso. Journal of the Royal Statistical Society Series B: Statistical Methodology, 58(1):267-2885 1996.
Kelner, J. A., Koehler, F., Meka, R., and Rohatgi, D. On the
Tipping, M. E. Sparse Bayesian Learning and the Relevance
Power of Preconditioning in Sparse Linear Regression. In 2021 IEEE 62nd Annual Symposium on Foundations of Computer Science (FOCS), pp. 550-561. IEEE, 2022b.
Vector Machine. Journal of machine learning research, 1 (Jun):211-244, 2001.
Wainwright, M. J. Sharp thresholds for high-dimensional and noisy recovery of sparsity. arXiv preprint math/0605740, 2006.
Kingma, D. P. and Welling, M. Auto-Encoding Variational Bayes, stat, 1050:1, 1, 2014.
Koehler, F., Mehta, V. Zhou, C., and Risteski, A. Variational autoencoders in the presence of low-dimensional data: landscape and implicit bias. International Conference Learning Representations, 2022.
Wauthier, F. L., Jojic, N., and Jordan, M. I. A Compar- ative Framework for Preconditioned Lasso Algorithms. Advances in Neural Information Processing Systems, 26, 2013.
Li, X., Dowsley, R., and De Cock, M. Privacy-Preserving Feature Selection with Secure Multiparty Computation. In International Conference on Machine Learning, pp- 6326-6336. PMLR, 2021.
Wipf, D. Marginalization is not Marginal: No Bad VAE Local Minima when Learning Optimal Sparse Representa- tions. In International Conference on Machine Learning, pp. 37108-313330 11100337322. PMLR, 2023.
Lin, A., Song, A. H., Bilgic, B., and Ba, D. Covariance- Free Sparse Bayesian Learning. IEEE Transactions Signal Processing. 70:3818 3-3331, 2022.
Wipf, D., Yun, J.-M., and Ling, Q. Augmented Bayesian Compressive Sensing. In 2015 Data Compression Con- ference. pp. 123-132. IEEE, 2015.
Löwe, S., Madras, D., Zemel, R., and Welling, M. Amor- tized Causal Discovery: Learning to Infer Causal Graphs from Time-Series Data. In Conference on Causal Learn- ing and Reasoning, pp. 509 5255. PMLR, 2022.
Wipf, D. P. and Rao, B. D. Sparse Bayesian Learning for Basis Selection. IEEE Transactions on Signal processing, 52(8):2153,2164, 2004.
Lucas, J., Tucker, G., Grosse, R. B., and Norouzi, M. Don't Blame the ELBO! ALinear VAE Perspective Posterior Collapse. Advances in Neural Information Processing Systems, 32, 2019.
Wipf, D. P., Rao, B. D., and Nagarajan, S. Latent Variable Bayesian Models for Promoting Sparsity. IEEE Transac- tions on Information Theory,57 57(9))6236-625 2011.
Zhang, H. al. Close the Loop: Joint Blind Image Restora- tion and Recognition with Sparse Representation Prior. In 2011 International Conference on Computer Vision, pp. 770-777. IEEE, 2011.
Rives, A. et al. Biological structure and function emerge from scaling unsupervised learning to 250 million pro- tein sequences. Proceedings of the National Academy of Sciences, 118(15):e20162311 18, 2021.
Zheng, Y., He, T., Qiu, Y., and Wipf, D. P. Learning Man- ifold Dimensions with Conditional Variational Autoen- coders. Advances in Neural Information Processing Sys- tems, 15:34709-34722 2022.
D.
Rudelson, M. and Vershynin, R. Sparse reconstruction by convex relaxation: Fourier and Gaussian measurements. In 2006 40th Annual Conference on Information Sciences and Systems, pp. 207-212. IEEE, 2006.
Zietlow, D.,, Rolinek, M., and Martius, G. Demystifying Inductive Biases for 3-VAE Based Architectures. In International Conference on Machine Learning, 2021.
Serban, I. et al. A Hierarchical Latent Variable Encoder- Decoder Model for Generating Dialogues. In Proceed- ings of the AAAI conference on Artificial Intelligence, volume 31, 2017.

---

Be Goldfish:
Forgetting Bad Conditioning in Sparse Linear Regression via Variational Autoencoders
Appendix
In this section, we provide the proofs for the lemmas and theorems used this paper. We begin by listing the notation for both variables and functions. Boldface uppercase Greek symbols (e.g., 4) and boldface uppercase Latin letters (e.g.. P) denote matrices. Vectors are denoted by boldface lowercase letters (e.g., f2 or x). All scalars appear in regular font weight and lowercase letters. To minimize notation overload, we occasionally reuse symbols for related variables. For example, represents both the input vector to the VAE and the observation vector in SLR.
Table List of variables used throughout the paper
Variable
Dimension
Description
Variable
Dimension
Description
Sparse Linear Regression (SLR)
d
Scalar
Observation dimension
Scalar
Coefficient dimension Coefficient vector Noise vector jth column of + Preconditioned Preconditioned x
X
Igd
Observation vector Design matrix ęth row of + Preconditioning matrix Preconditioned
IR"
Rdxn
Rd
R"
+ .J
Rdd
P
Rdxddd
Rd
Rdxn
Scalar
Restricted isometry constant of +
Raxa
Gram/ Covariance matrix of $
A
Scalar
Regularizer for LASSO Sparsity value
Scalar
Bigenvalues Matrix Ground truth
Scalar
2"
R"
Variational Autoencoder (VAE)
d
Scalar
Input dimension
Scalar
Latent Dimension
X
Rd
Input vector
R"
Latent Vector
Scalar
Decoder variance
IRdxn
Linear decoder matrix
W,
R"
Decoder parameter
R"
Element- squared w,"
Rd
Decoder mean
Σ
Rdxd
Decoder covariance yI
b,
Id
Linear decoder bias
R"
Linear encoder bias
μ1
R
Encoder mean
Σ;
Raxn
Encoder covariance
R or
dxd
R
Identity matrix
(0, (0
Arbitrary
(Encoder, Decoder) parameter
We also use E for denoting the singular values matrix in singular value decomposition (SVD).
Table List of all functions used throughout the paper
Function
Description
Sparse Linear Regression (SLR)
| cond(E)
Ep norm of where E (0, Condition number for Σ
Variational Autoencoder (VAE)
Nx Σ)
Multivariate Gaussian distribution over x with mean f and Covariance Σ
(x(
Marginal probability distribution of x parameterized by A Joint probability distribution of x, z parameterized by 0 given z parameterized by Prior distribution of the latent variable z
Po(x, x z)
po (x|z)
Conditional likelihood distribution
p(z)
Do (2(2)x)
Posterior probability distribution of z given parameterized by
2 (2(x)
Approximate posterior distribution of z given parameterized by Expectation of over the probability distribution (z/x)
E (x)(
(2)x)
Kullback-Liebler divergence between two distributions (z) x), p(z)
((0,0) +)
VAE loss function w.r.t. encoder & and decoder 0 parameters
Furthermore, we denote local or global minima with a "hat," for instance, w. represents the vector W,, that minimizes the VAE loss C(B, 6). We use "star," for the ground-truth variable z" in (4) and for y" in Theorem 4.4. Preconditioned matrices and vectors carry a "tilde," for example, $ P& for the preconditioned design matrix.
12

---

Be Goldfish: Forgetting Bad Conditioning in Sparse Linear Regression via Variational Autoencoders
A. Proof of Theorem 4.2
We first optimize over the encoder parameters to obtain a condensed loss, which then analyzed with respect to the decoder parameter, the latter occupying the majority of the proof. For the encoder- rreoder- architecture choice objective in (13) reduces to:
1 - || + diag/ W W x + -trrrddie w.] + 4 diag w>]
())
[ SSS
7 d log tr log SSs + I x|22
(20)
with 0 - ? and Ø = (W..S) Although this loss is nonconvex, we can still take derivatives with respect to S to show the existence of a single stationary point. In doing so, we find that
( diag w.]] t T [iag[[s>]> + 1)
ss T
(21)
the unique minimizer. Note that the identity matrix in (21) of dimension n x n. Substituting (21) into (20), yields the revised cost as:
1 xx T diag[w,] W2 x112 + d log + log diag [wa. Φ Toa diag(w [w>] +I + [ x x|2
((0 () =
(22)
Since (22) is convex in W., we can also optimize these parameters without encountering local minima issues, noting that the optimal value satisfies:
We diag[w>] x (T diag[w,) w.,] 2 TT + 7 x.
-1
(23)
Note that the in (23) is of dimension d d, which we obtain after applying standard determinant identities (e.g., the Woodbury matrix identity). Column-wise, this expression is tantamount to H4, (x:(xx) Φ) = W. x. To simplify notation, let us write w w 2 0 (elementwise). We also define W e dlag[w]] Substituting (23) into (22) further reduces the remaining
parameters. The VAE loss can be equivalently expressed as:
((w,n) x -n' + log Ez|, with E xw@ T +
(24)
We now show that for a fixed y any minimum of (24) is global minimum and that, in the limiting case 7 + 0, the global minimum approaches the optimal sparse representation for SLR, provided the design matrix is well-conditioned satisfying the RIP condition with small delta.
A.1 Deriving the Stationarity Conditions
Let us denote + diag[w] お" + using the matrix E(w). The VAE loss then depends only on and is given by:
((w) x Σ (w) + log E(w)].
(25)
ac for each wy E w, for each of the two terms in (25).
We now compute the stationary points by finding Ow,
Derivative of the Quvrrre-uadrratic Term.
Consider (iw) x Σ 2-((w)x, (w) When the following matrix caleuuu identity for arbitrary matrix A:
i A A(0) AA ()( ae A())
(26)
08
is applied to --'(w) we get:
0 [-((w) = --- --((w) [Σ(w) (w)
Σ [ww
(27)
Ow;
Ow,
13

---

Be Goldfish: Forgetting Bad Conditioning in Sparse Linear Regression via Variational Autoencoders
Since (w(w) , 3 (because differentiating diag(w] with respect to wj picks out the jth diagonal element, yielding owy the jth rank-l component), we substitute it back into (27) get:
(w) = - E (w) (0,0,) 1 (w).
(28)
By the chain rule of differentiation,
① [x -
x [ [w) x= x Φ5 E --(xxx
0 (w)
(w)xx
(29)
Swy
Owy
Since x' T A x is a scalar for an arbitrary matrix A, we can rewrite (29) as:
xx xx===+(w) (w) - (w))
(30)
awy
Derivative of the Log-Det Term.
Next, consider the second term, T2(w) log [[w)] Applying the identity:
Q log (0) trace (0)) (A(O)
(31)
00
3e
get,
log [w)] = trace Σ (w)
(E(w) Chey
trace
X (w) (
(32)
Owy
Using the cyclic property of trace, trace( A B) = stracee BB A), and the fact that trace(uv v for vectors, we get
i
log
Σ w) o Σ (w)
(33)
Ow,
Adding the two contributions and setting the derivative w.r.t. Wi to zero,
aL(w) - -05, Σ ( + $ -----(wee Φ
(34)
(0) (w) $
Σ - (w) b5.
(35)
This stationarity condition balances the "weighted prediction" for the jth coordinate against its corresponding diagonal element E(w) -1. The equations for all j couple together, much like in sparse Bayesian regression.
We next show, by contradiction, that when is well-conditioned and satisfies the RIP condition, these coupled equations admit no spurious local minima: every minimum of the loss corresponds to global minimum. Finally, show that in the limit - 0, this global minimum converges to the sparse optimal solution.
A.2 No Bad Local Minima for Well-Conditioned Design Matrix
Lemma .1 Suppose there exist two distinet vectors w(1) and w(2), both satisfying the stationarity conditions over
(Ø) ((w(") 03 o; (0, E(w(2))-1x) = ((W(()))-1 Vj.
(36)
Then (1) = (2) if & satisfies the RIP condition with small d. In other words, there are no "bad" local minima under these stationarity conditions.
Proof. The main requirement for Lemma is the absence of distinct w(1 and w()) that satisfy (34). With perfect optimizer, the full rank assumption ensures the presence of unique inverse E-1(w) for unique w, leading bad local minima. However, practical optimizers such SGD might identify distinct (1) and (2) as minima for the loss function in (25) that satisfy Σ-1 (ww( x Σ- 3-'(w(2)) We use the RIP bound ó to ensure that the difference in inverse terms is large enough to be detectable by SGD.
Let z = Eies ase,, where C (l....,n) with |S] = k, be a s--parse vector and let & E Rdda with columns o....., A,..
Then, Φ Eies a;;, and its squared norm of 4z becomes: |
||Eres 2
14

---

Be Goldfish: Forgetting Bad Conditioning in Sparse Linear Regression via Variational Autoencoders
1.2.1 DEVIATION FROM ISOMETRY AND RIP CONSTANT
The RIP condition for k-sparse vectors requires:
(1 - 6)112122
22 S +1]12112
(37)
Subtracting |22|2, we obtain the deviation:
-1z12 = Σ
2f - +)+ Σ a,ay(o,: 0,)
(38)
$
(
Thus, the RIP constant 5 is defined the worst-case deviation over all k-sparse unit-norm vectors
max SC m1....., ||| iES
Σ 2o -) 1)+ + Σ
agay(o.
(39)
Eies af=1
A.2.2 RELATIONSHIP BETWEEN AND SGD
For a R-sparse z, the RIP bound ō can be expressed as a weighted sum of activated column norms of O and cross correlations between them. However, the presence of aligned columns leads to large correlations, increasing the ō value.
Without loss of generality, pick an index j E S but j & S2. Thus, (1) "turns on" column Φ while w(2) has w (2) = 0. If Φ, is co-linear with other columns it will lead a large 8. Furthermore, it also means small difference in X-1(w( and (2) as (1) and (2)) differ along the indices of the aligned columns having large correlations. It is due to the common large correlation term with Φ both in Σ (w(()) and Σ >-1 (w(),, they will have a small difference.
Therefore small 8 suggests small correlation and therefore larger separation between E-I(w(U) and E-1(w(()). This indicates that a small 8 is essential to find the true local/global optimum.
A.2.3 PROOF BY CONTRADICTION
We argue by contradiction. Assume (1) A (2) while both vectors satisfy (36). Define the active set Sm = {j my (m) > 0}
for m = 1,2. Note that each ((m) is strictly positive in its active coordinates, and hence corresponds to selecting certain subset of columns from Φ Our goal is to show that this situation cannot arise if O is well-conditioned.
Case 1: S * Sz. Without loss of generality, pick an index j E S₁ but j & Sz. Thus, w(1) "turns on" column Φ while (2) has w = Because & satisfied the RIP condition (Candes & Tao, 2005), o, cannot be near-collinear with the other active columns in Sz. Consequently, ((w(1) and (2w(2) differ in way that prevents both from simultaneously satisfying the stationarity conditions for the same x. This yields contradiction, so ((1) and (2) cannot both be solutions.
Case 2: S = S2. In this case, both (!) and (2) activate exactly the same set of columns. For each j E Si, the single-observation stationarity equation admits a unique positive solution for wy. Consequently, w(1) and (2) must coincide on every active coordinate, contradicting our assumption that they are distinct.
Since neither case can consistently support two different solutions, there cannot be bad local minimum that allows for multiple solutions of w. All local minima must provide the same solution as the global minimizer, implying no spurious local minima arise when & is well-conditioned.
If d is ill ill-oonitiooned, some columns can become nearly dependent, causing E( (w)()) and (2w(2)) to be nearly identical even when (11) A (2). This may introduce suboptimal local minima that trap optimization algorithms. Later, we show that VAEs can be used to find the preconditioning for to reduce its eigenvalue spread, potentially leading to an optimal sparse solution in specific cases.
15

---

Be Goldfish: Forgetting Bad Conditioning in Sparse Linear Regression via Variational Autoencoders
A.3 Optimal Sparse Solution at Global Minima
Lemma .2. Consider the single-data-pot point loss in (24), and let y O. Suppose we fix d elements of w to zero, and denote by Wa E B the remaining nonzero elements, with Φ R the corresponding columns of L, and Za $ Then any minimizer of the loss matches these nonzero coordinates of satisfying We 2
Proof. In the presence of non-zero 7, the optimal sparse solution requires us to solve (34) the implicit stationarity condition for which a closed form solution does not exist. We leverage Theorem 4 from (Dai & Wipf. 2019), which states that for any 7 > 0, there exists a 7 < for which the VAE loss can be reduced. Our proposed VAE architecture satisfies the conditions for Theorem from (Dai & Wipf, 2019) implying that y - leads minimizing the VAE loss. Therefore, it is valid to evaluate the limiting value of the loss function in (24), and use it obtain the local/ global minimum solution. When 7 + the loss in (24) takes the form
x
x
( diag
& a
(Φ,'x)
x)
diag
(
x).
(40)
Wi
Wa
Defining Za 4/ x, we isolate the d elements {2i corresponding to the nonzero coordinates {wa, This gives
x E(wa)
(41)
W..ii
Using the multiplicative property of determinants,
d
E(wa)] = diag(wa) 2 = = |dda(waa)) p =
Wd.s:
(42)
d
log E Ewwa) 2 log 12al
+
log wd.i
(43)
The term 2 log [ba] is constant with respect to way and thus does not affect minimization. Combining these, the loss is separated over the coordinates:
d
L(Wa)
Σ
+
Σ
logwa, Was + constant, where 2, ( x),
(44)
wd.
im1
Since the summation is separable in each wa,i, optimize each coordinate independently. For the ith term, setting the derivative to zero gives:
d
x was
log wa.s)
2
0,
dwa,i
w
Wd,
0d.i 2
= (
x)²
A second-derivative check confirms this is global minimum, since the objective is strictly convex in each wa,i Consequently. the unique minimizer over wa is given by Wd. = ( x)
Lemma .2 shows that the global optimal solution for the VAE loss in (24) recovers the sparse representation defined by the coefficients z" underlying the observation x in (4). Moreover, according to Lemma 4.1 any global minima a VAE with a linear encoder-decoder achieves the optimal sparse representation for z when 7 - 0. Therefore resulting encoder mean given by (24) also satisfies optimal reconstruction under the limiting condition of 7 -> 0 leading to:
ddiag[w, wz|m: bdiag w. _ _ // [.. + T ) =
(45)
diag w.] u2= = diag w. 2 t (ediag[w..
22 T ) 1 à 2 diag w._| @ ww.))/
(46)
(47)
where denotes the pseudo-inverse operation.
16

---

Be Goldfish: Forgetting Bad Conditioning in Sparse Linear Regression via Variational Autoencoders
B. Proof of Lemma 4.3
We aim to compare the condition number of P & with that Φ. Following the SLR setting in the main-text, & E Rd*k is a full-rank matrix with rank () = d < min (d, k) and preconditioner P + + identity matrix.
+yI) with y > 0 and I is the d x d
We start with computing the singular value decomposition (SVD) of + = orthonormal columns, and Σ dgd is diagonal matrix with the d eigenvalues following the order 01 2 0a > - U which yields,
UE
where U E Rdxd and V E Ruxd have
Then + +
+ U + tU" Φ +
(48)
and hence,
P = { + +71) - +11) U + 1
(1- 7
(49)
The preconditioned design matrix P + is given by,
+ + (UEVT)
PΦ
(50)
- P -1="+71)- EV- = EV
UMV..
(51)
where
M = + = diag ofty
(52)
Since U and V are orthonormal, the singular values of P d are the diagonal entries of M, i.. 0:/(0) +7) for 1....,d d. Hence,
O2 of +
min 0,
max
(
max Isid
Omin (P$)
isidd of +
(53)
Therefore, the condition number satisfies
cond (P = max P $
o
0f +
<
m1
= cond(
(54)
m (P
( +7
Since ())())
+7) S 1, we have
cond [P क)
cond ()).
(55)
Equality holds only if all singular values of are equal; otherwise, multiplying & on the left by (4 TT + strictly reduces its condition number.
C. Proof of Theorem 4.4
This proof builds on the arguments from the proof of Theorem 4.2 (see Appendix A), except for the limiting behavior of 7. Here, we do not require y - 0, but rather allow it to take a value which would satisfy the RIP condition. After preconditioning the design matrix & and the observation vector x by P (Φ $
+ the loss in (21) becomes
C(0,0)
Px P diag/w [w..
W, Px 2 + tr diag [w] + P P diag/w/ w., sSs
7
+ lo tr log SS I Px 2
(56)
with (Wz; 7) and Φ = (W., S). Replacing + P and x Px in (56) we get:
17

---

Be Goldfish: Forgetting Bad Conditioning in Sparse Linear Regression via Variational Autoencoders
1 | E diag/ Wx] W= x12 + tr [diag]] Wa] + 4 diag[wa] [ SS ?
(()
?
d log + tr( log SS + I X|2
(57)
For fixed 7, it follows from Theorem 4.2 that (57) has no bad local minima if the RIP condition holds for & with the chosen Clearly, Φ will not satisfy RIP for every because o itself is not guaranteed to satisfy RIP. Lemma 4.3 implies that cond ) I cond( (). but does not assure that Φ satisfies RIP for all y.
Suppose there exists a = 7 such that 1 satisfies RIP (i.e., its columns are linearly independent for the required support). In that case, (57) has no bad local minima, and any minimum of (57) is also a global minimum. This minimum leads the loss-minimizing Wa, consistent with the stationarity conditions:
((w) = x E x + log |.r where Σg a @ +
(58)
The uniqueness of of that induces coPpccmt क and hence eliminates bad minima in (57), is not guaranteed. However, since & meets RIP, Theorem 4.2 implies that using & as the design matrix and X as observations, the loss in (24) can attain the optimal sparse representation as + 0. Because the optimal sparse representation z" is unique, the specific 7 that enhances the RIP condition will also converge to this optimal sparse solution if it is sufficiently small to meet the limiting conditions for y + 0. This holds when
lim diag W.] 2 + diag [z] P T 7-0
+ +1 x + diag[ w2 $ ( diag w, 12555 )'xx
)
~ diag wr] $ ( diag w. 2 12 + +7"1) -xx,
(59)
where
00( (Φ Φ
=
+ -1 Φ
x (Ø +7-1) 1== x.
(60)
Thus,
ă = diag/vi wr] 1 +
( diag w 2 -Φ) ) x
diag/va wr] x T [ diag w_] 12xTPT)) PT) -1
Px
(61)
D. Additional Experimental Results
In this section, we provide all the additional experimental results comparing our technique with other works for different design matrices. First, summarize the methodology and key findings for each parameter variation (Section 5.4), followed by the additional results for the Riboflavin dataset (Section 5.3) and the impact of fixed vs. trainable on sparse recovery (Section 5.5).
D.1 Design Matrix Dimensions
To quantify the impact of feature dimension and number of observations d on SLR support recovery, we chose the Gaussian Random Walk design matrix from Section 5.2 with sparsity level λ = 20 and к = 10 respectively. First, we fixed the number of observations at d = 100 and varied the number of features n from 150 to 300 in steps of 50. Then, holding n 200 constant, we varied from 10 to 100. In each configuration, the nonzero coefficients were drawn i.i.d. from (O, 1). and we performed 10 independent trials, measuring the fraction of trials in which the estimated support matched the ground truth exactly. As shown in Fig. 2(a), recovery performance for all methods degrades as n increases (i.e., as the effective sparsity k/n. decreases), but our preconditioned VAE consistently achieves the highest support recovery rate across the entire range. Likewise, Fig. 2(b) demonstrates that increasing the observation count d improves recovery for all algorithms, with the VAE maintaining a 5-10% advantage over LASSO, and Augmented basis pursuit at each sample size. Both observations follow the insight that as more information becomes available for solving the SLR, the support recovery rate improves, with preconditioned VAE performing better than the others.
18

---

Be Goldfish: Forgetting Bad Conditioning in Sparse Linear Regression via Variational Autoencoders
Lasso
AugBP VAE
PreconVAE
Lasso AugBP
VAE
PreconVAE
Support Recovery Rate
1.0
Preconditioned-WW VAE
Support Recovery Rate
1.0
Gaussian Random Walk
performs better in all cases
design matrix
0.8
0.8
sparsity 10
features 200
0.6
0.6
Gaussian Random Walk design matrix
Preconditioned
0.4
0.4
VAE performs
sparsity x = 20
better for d 25
0.2
observations 100
0.2
0.0
0.0
150
200
250
300
2
2
2
Number of Features (n)
Number of Observations (d)
(a)
(b)
Figure 2. Sparse recovery rate number of features n, and (b) number of observations for Gaussian random walk design matrix.
Gaussian
Rayleigh
Chi-Squared
Gaussian
Rayleigh
Chi-Squared
Uniform
Poisson
Uniform
Poisson
1.0
Support Recovery Rate
observations n=200
0.08
observations n=200
Mean Square Loss
0.8
features =100
features d =100
0.06
0.6
0.04
0.4
0.02
0.2
0.0
0.00
0
20
40
60
20
40
60
Number of nonzero entries (k)
Number of nonzero entries (k)
(a)
(b)
Figure (a) Support recovery rate and (b) mean squared error using proposed VAE followed by standard least squares for different distributions of non-zero coefficients on standard Gaussian design matrix.
D.2 Nonzero Coefficient Distribution
We next evaluated whether the distribution of the nonzero coefficients affects recovery. Keeping (n, d) (200, 100), we sampled the nonzero entries from five distinct distributions: the standard Gaussian, Rayleigh, Chi-squared, Uniform, and Poisson distributions. For each distribution, we ran 10 trials and recorded both the support recovery rate (Fig. 3(a)) and the mean-squared error (MSE) of the coefficient estimates (Fig. 3(b).. The MSE curves for cases overlap, and the support recovery rates differ by no more than two percentage points. This confirms that our VAE's mechanism for identifying support is essentially invariant the actual value distribution of the nonzero coefficients.
D.3 Noise Level
We evaluated performance under additive measurement noise. Using (n, d) (200, 100) and Gaussian distributed nonzero coefficients, we injected noise 77 NN0 o²) and defined the signal-to-noise ratio SNR 10 log (ar(2z)/a /²)). We varied SNR, from OB 80 dB, running 10 trials for each evaluation. For the standard Gaussian design matrix (Fig. 4(a)), we found that although all methods improve with increasing SNR, our VAE outperforms LASSO and SBL at low SNR (20 dB to 40 dB). Similarly, for the Gaussian random walk design matrix (Fig. 4(b)), we observed that while all methods fail at low SNR, only the preconditioned VAE succeeds at SNR above 60 dB. These results suggest promising directions for future work, such as integrating VAE-based denoising or mixture-ot Saaeeee-of-Gaaae -a-ussssss preprocessing to extend reliable support recovery into even lower SNR regimes.
19

---

Be Goldfish: Forgetting Bad Conditioning in Sparse Linear Regression via Variational Autoencoders
PreconV/N
SBL
VAE
1.0
Standard Gaussian design
Gaussian random walk
matrix (sparsity = 2)
design matrix (sparsity 20) observations n=200
Sipport Sipport Recovery Rate
0.8
observations n=200
C.B
features d =100
Suparet Recovery
features =100
0.0
0.6
0.4
0.2
0.0
10
30
40
60
80
SNR (dB)
SNR (dB)
(a)
(b)
Figure 4. Sparse recovery rate for standard Gaussian design matrix and (b) Gaussian random walk matrix increasing SNR.
Lasso AugBP
VAE
PreconVAE
(A) Fixed gamma: 1e-1
1e-4 (B) Trainable gamma parameter:
Support Recovery Rate
Support Recovery Rate
1.0
Preconditioned VAE
Practical Riboflavin
Gaussian Random Walk Matrix observations n=200 features d =100
0.8
design matrix
observations n=71
0.6
features d =100
0.6
Proposed
0.4
0.4
Vecconditione
0.2
0.0
20
40
60
0.0
Number of nonzero entries (k)
40
60
Number of nonzero entries (k)
Figure Sparse recovery rate vs. sparsity for Gaussian random walk design matrix with preconditioned VAE and (a) fixed gamma, and (b) trainable gamma.
Figure 5. Sparse recovery rate vs. sparsity for a general- ized Riboflavin matrix.
D.4 Additional Experiments on Riboflavin Dataset
The Riboflavin dataset used for experiments in Section 5.3 the set of 100 genetic features exhibiting the highest empirical variances from total of 4088 available features (Bühlmann al., 2014). Indeed, this subset yields the worst condition number (2248). When selecting more general subset consisting of 200 randomly chosen features, we observed an improved condition number of 1345. Notably, in this scenario with better-conditionee matrix, our preconditioned VAE demonstrates better support recovery performance compared to others, illustrated in Fig. 5.
D.5 Fixed vs. Trainable y during Preconditioning
The trainable hyperparameter gamma significantly enhances the performance of the preconditioned VAE in addressing ill-conditioned SLR problems. According to Lemma 4.3, positive gamma term directly improves the condition number of the design matrix. Incorporating gamma as a trainable component during optimization further facilitates superior support recovery. In Fig. 6, we examine both fixed and trainable gamma scenarios, demonstrating that the trainable gamma approach achieves higher support recovery rates. Although the VAE architecture satisfies the criterion of having no bad local minima under a fixed gamma setting (Theorem 4.2), optimal sparse recovery is contingent upon approaching the limiting value of the minima gamma approaches zero. Imperfect optimization can hinder the achievement of this ideal scenario, evidenced by our empirical results. Nevertheless, the proposed method outperforms LASSO and related techniques, underscoring its potential for effectively solving sparse inverse problems.
20


Reviews:
[{"review_id": "kBBIiqmQZF", "reviewer": "Reviewer_aNAM", "summary": "The paper addresses the benefits of the variational autoencoder (VAE) objective to solve sparse linear regression (SLR). It shows that a particular VAE setup solves SLR under a restricted isoperimetry property (RIP) condition (Theorem 4.2), and a modification of this setup can induce preconditioning of the design matrix (Theorem). The benefit of this approach with respect to LASSO and augmented basis pursuit are demonstrated in an empirical validation study, specifically in the ill-conditioned and low-sparsity settings.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We are grateful to the reviewer for their insightful comments on our submission. Please find our detailed response below:\n\n## Addressing concerns about Theorem 4.2:\n\n1. **Use of RIP condition**: Thanks for this excellent observation. The main requirement for A.2 Lemma 1 is the absence of distinct $\\mathbf{w}^{(1)}$ and $\\mathbf{w}^{(2)}$ that satisfy Eq. (37). With a perfect optimizer, a full rank Φ ensures the presence of a unique inverse $\\Sigma^{-1}(\\mathbf{w})$ for each $\\mathbf{w}$, leading to no bad local minima. However, practical SGD might identify distinct $\\mathbf{w}$’s with close inverse values satisfying Eq. (37). We use the RIP bound 𝛅 to ensure that the difference in inverse terms large enough to be detectable by SGD. For a 𝛋-sparse z, the RIP bound 𝛅 can be expressed as a weighted sum of activated column norms of Φ and cross correlations between them (for detailed explanation, please see: https://anonymous.4open.science/r/VAE-for-SLR-3E8F/RB/R3Exp.pdf ). However, the presence of aligned columns leads to large correlations increasing 𝛅 value. A large 𝛅 suggests small difference in the inverse terms for $\\mathbf{w}$’s that differ along the indices of the aligned columns having large correlations. Therefore small 𝛅 suggests higher success rate for the optimization algorithm in finding the true local/global optimum.\n2. **Study of convergence as gamma goes to zero**: In the presence of γ (decoder variance), the optimal sparse solution requires us to solve the implicit stationarity condition in Eq. (37) for which a closed form solution does not exist. We leverage Theorem 4 from (Dai and Wipf, 2019 [e]) which states that for any γ>0, there exists a γ′<γ  for which the VAE loss can be reduced. Our proposed VAE architecture satisfies the conditions for Theorem 4 from [e] implying that γ → 0 leads to minimizing the VAE loss. Therefore, it's valid to evaluate the limiting value of loss function in Eq. (26), and use it to obtain the local/ global minimum solution.\n\n## γ term in Theorem 4.4\n\nThe γ term is a training parameter in Theorem 4.4, and it impacts the condition number of PΦ. As shown in Lemma 4.3 any positive value of γ improves the condition number of PΦ compared to Φ. Therefore, adding γ to the overall loss function improves the effective condition number of Φ, pushing it to satisfy the RIP property. \n\n**Choice/Learning of Decoder hyper-parameter γ**: The trainable γ assists in achieving a higher support recovery rate of the preconditioned VAE for ill-conditioned SLR (Fig. [https://anonymous.4open.science/r/VAE-for-SLR-3E8F/RB/R3FH.png ]) compared to fixed γ. Although proposed VAE architecture can achieve no bad local minima condition for a fixed γ, optimal sparse recovery with γ → 0 is contingent on the success of the optimization algorithm. Imperfect optimization can hinder achieving this ideal scenario, as evidenced by our empirical results. We will update our manuscript to clarify this point. \n\n## Experiments:\nWe chose the ill-conditioned Gaussian random walk design matrix scenario from Sec. 5 to perform the following experiments:\n\n1. Dependence on number of features: Fig. [https://anonymous.4open.science/r/VAE-for-SLR-3E8F/RB/R3FF.png ] shows that the pre-conditioned VAE consistently outperforms other methods in achieving a higher support recovery rate as the number of features increases. \n2. Dependence on number of observations: Fig. [https://anonymous.4open.science/r/VAE-for-SLR-3E8F/RB/R3FG.png ] shows that the support recovery rate for preconditioned VAE increases with the number of observations, as with increase in observations d, more information is available for solving the SLR. \n\nNote: We performed experiments with real-world Riboflavin dataset in Sec. 5.3 using the 100 highest variances genetic features. Additional experimental results with random Riboflavin features (Fig. [https://anonymous.4open.science/r/VAE-for-SLR-3E8F/RB/R3FI.png ]) shows similar support recovery rate as shown in Sec. 5.3. These results will be added to the manuscript.\n\n## Bias of the estimated solution\n\nWe emphasize that our VAE-based sparse recovery aims to identify the positions of non-zero coefficients rather than directly estimating their values. Once the correct support (non-zero coefficient positions) is identified, the SLR problem simplifies significantly and can be solved using ordinary least squares (OLS). Under a full-rank design matrix and Gauss-Markov assumptions, OLS is an unbiased estimator leading to optimal sparse recovery with no bias. However, at high sparsity VAE achieves a suboptimal support identification, introducing a bias (Fig. [https://anonymous.4open.science/r/VAE-for-SLR-3E8F/RB/R3FE.png ]) but VAE still achieves a lower bias compared to LASSO at all sparsities.\n\nResponse to other comments: We will start Section 3 with standard regression setting in the camera-ready manuscript.\n\nReferences: [e] https://arxiv.org/abs/1903.05789", "claims_and_evidence": "Claims are supported by theoretical and experimental results. \nTheory supports the claim that the chosen VAE setups are well-behaved for the SLR problem, and provide conditions for such behavior (notably on decoder noise parameter gamma). See below for a detailed discussion.\nHowever the theory only covers some properties of the theoretical optimum of the VAE objective and thus does not cover imperfect optimization. \nTherefore the empirical study of section 5 is welcome, and shows some benefits of VAEs for support recovery. However, other metrics, such as bias of the estimated solution, is not investigated empirically, nor even discussed.", "methods_and_evaluation_criteria": "The methods and evaluation criteria make sense however they are limited, when it comes to empirical validation. \nNotably, the influence of the number of features and number of observations is not studied. Importantly, the choice/learning of decoder hyperparameter gamma is also not studied while it is crucial to the theory.\n\nIdeally, one would also like to see the performance of the method on a real-world dataset.", "theoretical_claims": "I checked at a high level:\n- theorem 4.2: the steps of the proof look reasonable, except for:\n\t-  the use of the RIP condition (section A.2 in appendix): the exact role of delta (e.g. how small it must be) is not explicit, neither in the statement of the theorem, nor in the proof. A reference to (Candes and Tao, 2005) is provided, but it is overall unsatisfactory as a proof argument, because no explicit result is given. \n\t- the study of the convergence of the solution as gamma goes to zero: the authors seem to take the limit of the loss and study the resulting solution, instead of proving that the solution for a fixed gamma converges itself as gamma goes to zero.\n- lemma 4.3.: the steps of the proof look reasonable\n- theorem  4.4: I could not check (yet). However, I could not follow in the first place the explanations associated to the main text statement: below equation (19) (line 326) it is said \"treating gamma as trainable parameters effectively penalizes the condition number of Phi in the VAI objective (18)\", I do not see why (I don't see the condition number appearing in the objective).", "experimental_designs_or_analyses": "The experimental design is satisfactory, baring uncertainties on the choice of hyperparameters mentioned above.", "relation_to_broader_scientific_literature": "As far as I know, the paper mainly relates to (Wipf, 2023) addressing the problem of solving Simultaneous Sparse Regression (SSR) with VAEs. In contrast to it, the present paper addresses SLR (a more classic setting), but specifically investigates the benefits of VAEs in the challenging case of ill-conditioning and weak sparsity. This case has been address with a different approach in (Kelner et al., 2024), which is used as baseline.", "essential_references_not_discussed": "I am not sure it should be labeled as essential, but bias issues of SLR are surprisingly not discussed nor quantified, while there is an extensive literature on it notably for LASSO. E.g. \n\n A. Javanmard and A. Montanari. Debiasing the Lasso: optimal sample size\nfor Gaussian designs. Annals of Statistics, 46:2593–2622, 2018.", "other_strengths_and_weaknesses": "The writing can be improved in several places (e.g. sentences with missing words).", "other_comments_or_suggestions": "The setting could be better introduced to a general audience by being explicit about what the variables and parameter represent in a standard regression setting, at the beginning of section 3", "questions_for_authors": "Please address my comments on:\n- potential gaps/issues in the proof of theorem 4.2\n- the claim that gamma can be automatically learned in theorem 4.4\n- the missing analyses and metrics in the experimental section.\n\nI hope some of the raised issues are misunderstandings, therefore I am leaning towards accept for now, but could change my score.\n\n# Post rebuttal update\nI am happy with the answers provided by the authors.", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "dD3wNfKGHz", "reviewer": "Reviewer_7yVH", "summary": "This paper studies  the application of Variational Autoencoders for the sparse linear regression problem, particularly in cases involving ill-conditioned design matrices and low sparsity, situations where traditional methods like LASSO often fail.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We are grateful to the reviewer for taking the time to review this work and provide valuable comments. We will be sure to update our manuscript to correct for stylistic corrections. Some of the plausible modifications include: \n\n1. Using the same variable “n” for the coefficient dimension of SLR design matrix and latent dimension in VAE.\n2. Hat (local/ global minimum) and star (ground truth) notations can be reserved for the theorem/ lemma results, and all intermediate variables can be represented without hat and star. We will clarify this in the text about specific variable usage and update with the regular notations in the manuscript.", "claims_and_evidence": "The claims in the paper are supported by both theoretical analysis and empirical evidence. Specifically:\n- Theoretical claims: Proved including the elimination of spurious local minima (Theorems 4.2 and 4.4) under specific architectural constraints.\n- Empirical claims: Experiments conducted with three different types of design matrices (standard Gaussian, Gaussian random walk, and real-world Riboflavin dataset) demonstrate the effectiveness and improved robustness of the proposed method.", "methods_and_evaluation_criteria": "The proposed VAE methods and evaluation criteria (sparse support recovery rates across various sparsity levels and design matrix conditions) are sensible and appropriately chosen for the problem context.", "theoretical_claims": "No significant issues were found with the proofs provided.", "experimental_designs_or_analyses": "The experimental design and analyses were well-executed and sound. Specific checks included:", "relation_to_broader_scientific_literature": "It extends recent theoretical results by Wipf (2023) by applying VAEs beyond Simultaneous Sparse Regression (SSR) to the more challenging scenario of Sparse Linear Regression (SLR).", "essential_references_not_discussed": "nothing as far as I know", "other_strengths_and_weaknesses": "The work proposed to use VAE models to address solve the SLR problem. The work is self-contained interesting and sound in its own problem setup.", "other_comments_or_suggestions": "Minor stylistic corrections could further enhance clarity (e.g., consistency in variable definitions, notation simplicity).", "questions_for_authors": "NA", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "Afv9zS1lY1", "reviewer": "Reviewer_bPHS", "summary": "The paper studies the classic spare linear regression problem from a linear variational autoencoder (VAE) viewpoint. On the theoretical aspect, the paper provides two theorems. The first theorem guarantees that every local minimum of the VAE energy is a global minimum under a fixed variance and the global minimum achieves the optimal sparse solution when the variance converges to zero under the restricted isometry constant (RIP) condition. The second theorem is similar to the first one but with preconditioning to tackle the case when the design matrix is ill-conditioned. Numerical results show that the proposed VAE approach outperforms Lasso in some sparsity levels.\n\n## update after rebuttal\n\nThe reviewer would like to thank the authors for conducting additional experiments on SBL and sharing the comparisons. As my main concerns regarding SBL have been answered, I have adjusted my rating from weak reject to weak accept. Please incorporate these important comparisons of SBL into the paper as it is a better baseline compared to LASSO. Lastly, the design matrix should be fat and full rank so I believe the size 500x100 mentioned by the authors might be a typo.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for providing feedback and suggesting insightful experiments for our work. Please find our detailed response below:\n\n## Specific answers: \n\n1. **Role of decoder variance γ**: We solve for optimal $\\hat{\\mathbf{w}}_x$ by training the proposed VAE with SGD while using γ as a training parameter. Theorems 4.2 & 4.4 show the existence of optimal sparse solutions when γ → 0, and our empirical results achieve the same for most cases except when SGD fails to attain the limiting solution. We have also addressed this point in detail as a part of our response to *Reviewer aNAM* on γ term in Theorem 4.4. We request you kindly to look at the same owing to limited #characters for the rebuttal, in case additional clarification is required.\n\n2. **Comparison with other work**: Our experiments (Fig. https://anonymous.4open.science/r/VAE-for-SLR-3E8F/RB/R2FB.png ) reveal that while SBL methods such as Tipping’s and EM algorithm [a] surpasses LASSO in support recovery, our VAE-based approach demonstrates superior performance for Gaussian random walk design matrix. Additionally, our work provides theoretical optimality guarantees for VAEs even when dealing with ill-conditioned design matrices, a domain where SBL's performance remains largely unexplored [b]. Since SBL shares probabilistic roots with VAEs, this comparison suggests promising future research on investigating SBL's behavior under ill-conditioned design matrices and in high-sparsity regimes.\n\n3. **Training VAEs**: To generate training data x we first select r uniformly random sparse locations within an n dimensional vector, then sample r non-zero coefficients from a standard normal distribution to obtain sparse coefficients z. Thereafter, x is generated by multiplying z with the design matrix Φ. These x values are used to train the VAE using SGD.\n\n4. **Ground truth distribution**: Our proposed VAE focuses on locating non-zero coefficients of z, irrespective of their distribution. Once locations are determined, standard least squares retrieves exact coefficients. Our empirical results (Fig. https://anonymous.4open.science/r/VAE-for-SLR-3E8F/RB/R2FC.png ) demonstrate similar support recovery rate and mean squared error across various distributions, confirming our method's distributional invariance.\n\n5. **Impact of noise**: To assess its impact of noise on sparse recovery, we performed extensive experiments at different SNR levels (Fig. https://anonymous.4open.science/r/VAE-for-SLR-3E8F/RB/R2FD.png ). While recovery rate increases with SNR in all cases, our proposed VAE obtains a higher recovery rate at a lower SNR compared to others. The higher recovery rate of VAE at lower SNR can be boosted further to achieve sparse recovery in presence of larger noise. This presents an interesting future research direction where preprocessing techniques such as filtering & mixture of Gaussian models [c] can be applied.\n\n## Relation to broader scientific literature\n\nOur proposed VAE architecture focuses on theoretical exploration, beyond generative tasks like image or text synthesis. We aim to understand VAE properties relevant to challenging NP-hard problems such as SLR. Our work opens up the application space for VAEs beyond standard generative domains, such as in areas with sparsity constraints like brain anomaly localization and genome selection [d]. \n\n## Other comments or suggestions:\n\n1. **Notations**: We are referring to the posterior probability $p_\\theta(z |x)$  in Line 112 and Line 116, which is being modeled by $q_\\theta(z |x)$ in Eq. (2). The likelihood term $p_\\theta(x |z)$ in Eq. (2), is different from posterior $p_\\theta(z |x)$ in Eq. (2). We will update the explanation in the manuscript to enhance clarity. \n\n2. **Sparse penalty term**: In Eq. (6), g is a penalty term for the coefficients which promotes sparsity. Please note, we want a sparsity promoting term for defining a cost function for SLR instead of a diversity promoting term which increases variety in coefficients, e.g., g is L1 norm for LASSO.\n\n3. **Choice of linear architecture**: Lemma 4.1 connects the linear VAE global minimum to optimal sparse representations. We agree with the reviewer that linear VAEs limit conventional generative capabilities such as for images and text; however, they offer valuable insights into VAE properties. Please note that standard linear regression (LR), fails for sparse, underdetermined systems ( see Fig. https://anonymous.4open.science/r/VAE-for-SLR-3E8F/RB/R2FA.png ) due to exponentially large solution space where VAEs are capable of finding the sparse solution.\n\nReferences: \n[a] https://arxiv.org/abs/2105.10439;\n[b] https://ieeexplore.ieee.org/document/9810291; \n[c] https://ieeexplore.ieee.org/document/9420311; \n[d] https://www.mdpi.com/1099-4300/26/9/794.", "claims_and_evidence": "The VAE models considered in the paper are very restrictive. They are over simplified linear VAEs which we don’t use in practice. The models considered in the paper are basically linear regression models that can be derived without the knowledge of VAEs. The guarantee of the exact recovery still relies on the RIP conditions and the limiting scenario when the variance converges to zero. This does not explain how VAEs work in practice and how to design better VAEs.", "methods_and_evaluation_criteria": "It is expected to compare the proposed method with sparse Bayesian learning approaches such as Tipping’s and EM algorithms given the fact that they yield much better performance than Lasso. However, such comparisons are missing in the paper.", "theoretical_claims": "The reviewer did not verify the correctness of the proof.", "experimental_designs_or_analyses": "Similar to the above argument, it is hard to see the performance of the proposed method due to the lack of comparison to spare Bayesian learning approaches.", "relation_to_broader_scientific_literature": "The main theorems of this paper are related to the field of spare signal recovery in signal processing. On the machine learning side, the connections to VAEs and generative models are weak.", "essential_references_not_discussed": "Reference adequate.", "other_strengths_and_weaknesses": "Strengths:\n1. The paper is well-written and easy to follow.\n2. The background knowledge is well presented.\n\nMain weaknesses:\n1. There are some clarity issues in the paper. In Theorem 4.2, the optimal sparse solution in shown in (15). However, it still depends on $\\hat{w}_x$ and no algorithm is given to solve for $\\hat{w}_x$. When the variance converges to zero, how to you solve the optimal $\\hat{w}_x$? Is this still an NP-hard problem? Both Theorem 4.2 and 4.4 have the same issue.\n2. The connections to VAEs and generative models are weak. These concepts seem redundant to this paper as the paper studies the optimization problems in (14) and (18). It is not clear to the reader how these findings can motivate better design of VAEs to model complex real-world datasets.\n3. SBL algorithms provide much better support recovery performance than Lasso but comparison to SBL is missing. The numerical results in their current form are insufficient to determine the goodness of the proposed method.", "other_comments_or_suggestions": "1. Notations in Line 112 and 116 are not consistent with Eq. (2).\n2. The function $g$ in (6) needs to follow a set of properties to be a valid diversity measure. Perhaps the authors can briefly clarify how to design $g$.", "questions_for_authors": "1. When the variance converges to zero, how to solve the optimal $\\hat{w}_x$? Is this still an NP-hard problem?\n2. How does the proposed VAE method compare to SBL approaches such as Tipping’s and EM algorithms?\n3. How to train the VAE models and how to generate data?\n4. What is the distribution of ground truth $z^*$ used in the simulation? Is the proposed method sensitive to distribution?\n5. The SNR seems to be fixed in Section 5. Is the proposed method robust to different SNR levels?", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Meta-review: The reviewers overall appreciated the value of this theoretical contribution supported by experiments. The authors satisfactory answered the reviewers requests and I therefore recommend acceptance with the request to incorporate the results provided during the discussion period.
Decision: Accept (poster)