Full-Model Optimality for Tunable Linear Generative Priors in Compressed Sensing

• URL: http://arxiv.org/abs/2609.02790v1
• Date: Wed, 02 Sep 2026 16:22:26 GMT
• Title: Full-Model Optimality for Tunable Linear Generative Priors in Compressed Sensing
• Abstract summary: We establish theory for compressed sensing in the setting of a tunable family of linear generative priors.<n>We prove that in noiseless compressed sensing, the full-dimensional linear prior attains the minimum expected reconstruction error.<n>This result indicates that the experimental benefits of tunability in compressed sensing with neural network priors arises due to nonlinearities in the generative models.
• Score: 2.0737159978603925
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Generative models have been studied experimentally and theoretically as priors for inverse problems such as compressed sensing. Recent work by Gunn et al. studied the use of generative priors with tunable complexity, where a family of generative priors with varying complexity is maintained and a specific complexity can be selected at inversion time. They demonstrated that lower reconstruction errors can be experimentally attained for a variety of inverse problems by appropriately tuning the complexity of the generative prior. In the present paper, we establish theory for compressed sensing in the setting of a tunable family of linear generative priors naturally related through their singular value decompositions. We prove that in noiseless Gaussian compressed sensing, the full-dimensional linear prior attains the minimum expected reconstruction error over the entire family of linear priors. Thus, in this idealized linear noiseless setting, tuning to a lower-complexity prior does not improve the expected reconstruction error. This result is in contract to the behavior of denoising, where lower complexity priors attain lower reconstruction errors due to a standard bias-variance tradeoff. This result indicates that the experimental benefits of tunability in compressed sensing with neural network priors arises due to nonlinearities in the generative models.

Related papers

• Latent Generative Models with Tunable Complexity for Compressed Sensing and other Inverse Problems [7.111209122554222]
  We develop tunable-complexity priors for solving inverse problems.<n>We show empirically that tunable priors consistently achieve lower reconstruction errors than fixed-complexity baselines.<n>This work demonstrates the potential of tunable-complexity generative priors and motivates both the development of supporting theory and their application across a wide range of inverse problems.
  arXiv  Detail & Related papers  (2026-03-07T21:41:46Z)
• The Hidden Cost of Approximation in Online Mirror Descent [56.99972253009168]
  Online mirror descent (OMD) is a fundamental algorithmic paradigm that underlies many algorithms in optimization, machine learning and sequential decision-making.<n>In this work we initiate a systematic study into inexact OMD, and uncover an intricate relation between regularizer smoothness and robustness to approximation errors.
  arXiv  Detail & Related papers  (2025-11-27T10:09:07Z)
• Error Feedback under $(L_0,L_1)$-Smoothness: Normalization and Momentum [56.37522020675243]
  We provide the first proof of convergence for normalized error feedback algorithms across a wide range of machine learning problems. We show that due to their larger allowable stepsizes, our new normalized error feedback algorithms outperform their non-normalized counterparts on various tasks.
  arXiv  Detail & Related papers  (2024-10-22T10:19:27Z)
• Stable Nonconvex-Nonconcave Training via Linear Interpolation [51.668052890249726]
  This paper presents a theoretical analysis of linearahead as a principled method for stabilizing (large-scale) neural network training. We argue that instabilities in the optimization process are often caused by the nonmonotonicity of the loss landscape and show how linear can help by leveraging the theory of nonexpansive operators.
  arXiv  Detail & Related papers  (2023-10-20T12:45:12Z)
• The Inductive Bias of Flatness Regularization for Deep Matrix Factorization [58.851514333119255]
  This work takes the first step toward understanding the inductive bias of the minimum trace of the Hessian solutions in deep linear networks. We show that for all depth greater than one, with the standard Isometry Property (RIP) on the measurements, minimizing the trace of Hessian is approximately equivalent to minimizing the Schatten 1-norm of the corresponding end-to-end matrix parameters.
  arXiv  Detail & Related papers  (2023-06-22T23:14:57Z)
• The Predictive Normalized Maximum Likelihood for Over-parameterized Linear Regression with Norm Constraint: Regret and Double Descent [12.929639356256928]
  We show that modern machine learning models do not obey a trade-off between the complexity of a prediction rule and its ability to generalize. We use the recently proposed predictive normalized maximum likelihood (pNML) which is the min-max regret solution for individual data. We demonstrate the use of the pNML regret as a point-wise learnability measure on synthetic data and that it can successfully predict the double-decent phenomenon.
  arXiv  Detail & Related papers  (2021-02-14T15:49:04Z)
• CASTLE: Regularization via Auxiliary Causal Graph Discovery [89.74800176981842]
  We introduce Causal Structure Learning (CASTLE) regularization and propose to regularize a neural network by jointly learning the causal relationships between variables. CASTLE efficiently reconstructs only the features in the causal DAG that have a causal neighbor, whereas reconstruction-based regularizers suboptimally reconstruct all input features.
  arXiv  Detail & Related papers  (2020-09-28T09:49:38Z)
• Compressive Phase Retrieval: Optimal Sample Complexity with Deep Generative Priors [12.989855325491163]
  We show that generative priors can lead to a fundamental advance by permitting optimal sample complexity by a tractable algorithm in a challenging inverse problem. These results provide support for generative priors as a new paradigm for signal recovery in a variety of contexts.
  arXiv  Detail & Related papers  (2020-08-24T17:40:04Z)
• Sample Complexity Bounds for 1-bit Compressive Sensing and Binary Stable Embeddings with Generative Priors [52.06292503723978]
  Motivated by advances in compressive sensing with generative models, we study the problem of 1-bit compressive sensing with generative models. We first consider noiseless 1-bit measurements, and provide sample complexity bounds for approximate recovery under i.i.d.Gaussian measurements. We demonstrate that the Binary $epsilon$-Stable Embedding property, which characterizes the robustness of the reconstruction to measurement errors and noise, also holds for 1-bit compressive sensing with Lipschitz continuous generative models.
  arXiv  Detail & Related papers  (2020-02-05T09:44:10Z)
• Invertible generative models for inverse problems: mitigating representation error and dataset bias [6.07645721775351]
  Trained generative models have shown remarkable performance as priors for inverse problems in imaging.<n>We demonstrate that invertible neural networks, which have zero representation error by design, can be effective natural signal priors at inverse problems.
  arXiv  Detail & Related papers  (2019-05-28T08:27:53Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.