Constant-Expansion Suffices for Compressed Sensing with Generative
Priors
- URL: http://arxiv.org/abs/2006.04237v2
- Date: Fri, 26 Jun 2020 16:08:09 GMT
- Title: Constant-Expansion Suffices for Compressed Sensing with Generative
Priors
- Authors: Constantinos Daskalakis, Dhruv Rohatgi, Manolis Zampetakis
- Abstract summary: We prove a novel uniform concentration for random functions that might not beschitz but satisfy a relaxed notion of Lipe-theoreticalness.
Since the WDC is a fundamental concentration inequality inequality of all existing theoretical guarantees on this problem, our bound improvements in all known results in the heart on with priors, including one, low-bit recovery, and more.
- Score: 26.41623833920794
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: Generative neural networks have been empirically found very promising in
providing effective structural priors for compressed sensing, since they can be
trained to span low-dimensional data manifolds in high-dimensional signal
spaces. Despite the non-convexity of the resulting optimization problem, it has
also been shown theoretically that, for neural networks with random Gaussian
weights, a signal in the range of the network can be efficiently, approximately
recovered from a few noisy measurements. However, a major bottleneck of these
theoretical guarantees is a network expansivity condition: that each layer of
the neural network must be larger than the previous by a logarithmic factor.
Our main contribution is to break this strong expansivity assumption, showing
that constant expansivity suffices to get efficient recovery algorithms,
besides it also being information-theoretically necessary. To overcome the
theoretical bottleneck in existing approaches we prove a novel uniform
concentration theorem for random functions that might not be Lipschitz but
satisfy a relaxed notion which we call "pseudo-Lipschitzness." Using this
theorem we can show that a matrix concentration inequality known as the Weight
Distribution Condition (WDC), which was previously only known to hold for
Gaussian matrices with logarithmic aspect ratio, in fact holds for constant
aspect ratios too. Since the WDC is a fundamental matrix concentration
inequality in the heart of all existing theoretical guarantees on this problem,
our tighter bound immediately yields improvements in all known results in the
literature on compressed sensing with deep generative priors, including one-bit
recovery, phase retrieval, low-rank matrix recovery, and more.
Related papers
- Efficient Bound of Lipschitz Constant for Convolutional Layers by Gram
Iteration [122.51142131506639]
We introduce a precise, fast, and differentiable upper bound for the spectral norm of convolutional layers using circulant matrix theory.
We show through a comprehensive set of experiments that our approach outperforms other state-of-the-art methods in terms of precision, computational cost, and scalability.
It proves highly effective for the Lipschitz regularization of convolutional neural networks, with competitive results against concurrent approaches.
arXiv Detail & Related papers (2023-05-25T15:32:21Z) - Sharper analysis of sparsely activated wide neural networks with
trainable biases [103.85569570164404]
This work studies training one-hidden-layer overparameterized ReLU networks via gradient descent in the neural tangent kernel (NTK) regime.
Surprisingly, it is shown that the network after sparsification can achieve as fast convergence as the original network.
Since the generalization bound has dependence on the smallest eigenvalue of the limiting NTK, this work further studies the least eigenvalue of the limiting NTK.
arXiv Detail & Related papers (2023-01-01T02:11:39Z) - Robust Training and Verification of Implicit Neural Networks: A
Non-Euclidean Contractive Approach [64.23331120621118]
This paper proposes a theoretical and computational framework for training and robustness verification of implicit neural networks.
We introduce a related embedded network and show that the embedded network can be used to provide an $ell_infty$-norm box over-approximation of the reachable sets of the original network.
We apply our algorithms to train implicit neural networks on the MNIST dataset and compare the robustness of our models with the models trained via existing approaches in the literature.
arXiv Detail & Related papers (2022-08-08T03:13:24Z) - Signal Recovery with Non-Expansive Generative Network Priors [1.52292571922932]
We study compressive sensing with a deep generative network prior.
We prove that a signal in the range of a Gaussian generative network can be recovered from a few linear measurements.
arXiv Detail & Related papers (2022-04-24T18:47:32Z) - Bayesian neural network priors for edge-preserving inversion [3.2046720177804646]
A class of prior distributions based on the output of neural networks with heavy-tailed weights is introduced.
We show theoretically that samples from such priors have desirable discontinuous-like properties even when the network width is finite.
arXiv Detail & Related papers (2021-12-20T16:39:05Z) - Heavy Tails in SGD and Compressibility of Overparametrized Neural
Networks [9.554646174100123]
We show that the dynamics of the gradient descent training algorithm has a key role in obtaining compressible networks.
We prove that the networks are guaranteed to be '$ell_p$-compressible', and the compression errors of different pruning techniques become arbitrarily small as the network size increases.
arXiv Detail & Related papers (2021-06-07T17:02:59Z) - A Convergence Theory Towards Practical Over-parameterized Deep Neural
Networks [56.084798078072396]
We take a step towards closing the gap between theory and practice by significantly improving the known theoretical bounds on both the network width and the convergence time.
We show that convergence to a global minimum is guaranteed for networks with quadratic widths in the sample size and linear in their depth at a time logarithmic in both.
Our analysis and convergence bounds are derived via the construction of a surrogate network with fixed activation patterns that can be transformed at any time to an equivalent ReLU network of a reasonable size.
arXiv Detail & Related papers (2021-01-12T00:40:45Z) - Linear Convergent Decentralized Optimization with Compression [50.44269451541387]
Existing decentralized algorithms with compression mainly focus on compressing DGD-type algorithms.
Motivated by primal-dual algorithms, this paper proposes first underlineLinunderlineEAr convergent.
underlineDecentralized with compression, LEAD.
arXiv Detail & Related papers (2020-07-01T04:35:00Z) - Revisiting Initialization of Neural Networks [72.24615341588846]
We propose a rigorous estimation of the global curvature of weights across layers by approximating and controlling the norm of their Hessian matrix.
Our experiments on Word2Vec and the MNIST/CIFAR image classification tasks confirm that tracking the Hessian norm is a useful diagnostic tool.
arXiv Detail & Related papers (2020-04-20T18:12:56Z)
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.