Information theoretic limits of learning a sparse rule

• URL: http://arxiv.org/abs/2006.11313v2
• Date: Tue, 27 Oct 2020 20:36:08 GMT
• Title: Information theoretic limits of learning a sparse rule
• Abstract summary: We prove a variational formula for the mutual information per sample when the system size grows to infinity. We find that, for such signals and suitable scalings of the sparsity and vanishing rate, the MMSE is nonincreasing piecewise constant. We discuss an all-or-nothing phenomenon for the generalization error with a sublinear set of training examples.
• Score: 22.10167304165091
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We consider generalized linear models in regimes where the number of nonzero components of the signal and accessible data points are sublinear with respect to the size of the signal. We prove a variational formula for the asymptotic mutual information per sample when the system size grows to infinity. This result allows us to derive an expression for the minimum mean-square error (MMSE) of the Bayesian estimator when the signal entries have a discrete distribution with finite support. We find that, for such signals and suitable vanishing scalings of the sparsity and sampling rate, the MMSE is nonincreasing piecewise constant. In specific instances the MMSE even displays an all-or-nothing phase transition, that is, the MMSE sharply jumps from its maximum value to zero at a critical sampling rate. The all-or-nothing phenomenon has previously been shown to occur in high-dimensional linear regression. Our analysis goes beyond the linear case and applies to learning the weights of a perceptron with general activation function in a teacher-student scenario. In particular, we discuss an all-or-nothing phenomenon for the generalization error with a sublinear set of training examples.

Related papers

• Posterior Information Dynamics of Diffusion Models for Linear Inverse Problems [11.548853370822343]
  We study the process through the smoothed likelihood force, the difference between exact posterior and prior scores at each noise level.<n>Averaging over measurements yields an information--minimum mean-square error (I-MMSE) identity linking information gain to denoising-error reduction.
  arXiv  Detail & Related papers  (2026-08-22T00:53:42Z)
• A Geometric Measure of Linear Separability for Neural Representations [12.476368894025233]
  We introduce the directional linear separability measure (LSM), a finite-sample diagnostic for one-sided affine separability.<n>For a target class A and a competing set B, LSM measures the smallest competing-sample intrusion that must remain on the target side, normalized by |A|.
  arXiv  Detail & Related papers  (2026-06-07T16:31:54Z)
• Nearly Instance-Optimal Parameter Recovery from Many Trajectories via Hellinger Localization [19.74516565968901]
  We extend the scope of instance-optimal rates in multi-trajectory settings via the Hellinger localization framework.<n>We instantiate our framework across four diverse case studies.<n>Our bounds nearly match the instance-optimal rates from normality, substantially improving over standard reductions.
  arXiv  Detail & Related papers  (2025-10-07T20:12:04Z)
• Fundamental limits of Non-Linear Low-Rank Matrix Estimation [18.455890316339595]
  Bayes-optimal performances are characterized by an equivalent Gaussian model with an effective prior. We show that to reconstruct the signal accurately, one requires a signal-to-noise ratio growing as $Nfrac 12 (1-1/k_F)$, where $k_F$ is the first non-zero Fisher information coefficient of the function.
  arXiv  Detail & Related papers  (2024-03-07T05:26:52Z)
• Max-affine regression via first-order methods [7.12511675782289]
  The max-affine model ubiquitously arises in applications in signal processing and statistics. We present a non-asymptotic convergence analysis of gradient descent (GD) and mini-batch gradient descent (SGD) for max-affine regression.
  arXiv  Detail & Related papers  (2023-08-15T23:46:44Z)
• Mixed Regression via Approximate Message Passing [16.91276351457051]
  We study the problem of regression in a generalized linear model (GLM) with multiple signals and latent variables. In mixed linear regression, each observation comes from one of $L$ signal vectors (regressors), but we do not know which one. In max-affine regression, each observation comes from the maximum of $L$ affine functions, each defined via a different signal vector.
  arXiv  Detail & Related papers  (2023-04-05T04:59:59Z)
• Instance-Dependent Generalization Bounds via Optimal Transport [51.71650746285469]
  Existing generalization bounds fail to explain crucial factors that drive the generalization of modern neural networks. We derive instance-dependent generalization bounds that depend on the local Lipschitz regularity of the learned prediction function in the data space. We empirically analyze our generalization bounds for neural networks, showing that the bound values are meaningful and capture the effect of popular regularization methods during training.
  arXiv  Detail & Related papers  (2022-11-02T16:39:42Z)
• On the Effective Number of Linear Regions in Shallow Univariate ReLU Networks: Convergence Guarantees and Implicit Bias [50.84569563188485]
  We show that gradient flow converges in direction when labels are determined by the sign of a target network with $r$ neurons. Our result may already hold for mild over- parameterization, where the width is $tildemathcalO(r)$ and independent of the sample size.
  arXiv  Detail & Related papers  (2022-05-18T16:57:10Z)
• On the Double Descent of Random Features Models Trained with SGD [78.0918823643911]
  We study properties of random features (RF) regression in high dimensions optimized by gradient descent (SGD) We derive precise non-asymptotic error bounds of RF regression under both constant and adaptive step-size SGD setting. We observe the double descent phenomenon both theoretically and empirically.
  arXiv  Detail & Related papers  (2021-10-13T17:47:39Z)
• Benign Overfitting of Constant-Stepsize SGD for Linear Regression [122.70478935214128]
  inductive biases are central in preventing overfitting empirically. This work considers this issue in arguably the most basic setting: constant-stepsize SGD for linear regression. We reflect on a number of notable differences between the algorithmic regularization afforded by (unregularized) SGD in comparison to ordinary least squares.
  arXiv  Detail & Related papers  (2021-03-23T17:15:53Z)
• On maximum-likelihood estimation in the all-or-nothing regime [14.192301094399765]
  The analysis is carried out in the sparse setting, where the underlying signal has a support that scales sublinearly with the total number of dimensions. We show that for Bernoulli distributed signals, the MLE undergoes an emphall-or-nothing (AoN) phase transition, already established for the minimum mean-square-error estimator (MMSE) in the same problem.
  arXiv  Detail & Related papers  (2021-01-25T10:20:36Z)
• The Generalized Lasso with Nonlinear Observations and Generative Priors [63.541900026673055]
  We make the assumption of sub-Gaussian measurements, which is satisfied by a wide range of measurement models. We show that our result can be extended to the uniform recovery guarantee under the assumption of a so-called local embedding property.
  arXiv  Detail & Related papers  (2020-06-22T16:43:35Z)
• All-or-nothing statistical and computational phase transitions in sparse spiked matrix estimation [35.035853993422506]
  We analyze the approximate message passing algorithm in a sparse regime. We find all-or-nothing phase transitions for the minimum and mean-square errors. In the sparse regime the statistical-to-algorithmic gap diverges indicating that sparse recovery is hard for approximate message passing.
  arXiv  Detail & Related papers  (2020-06-14T18:38:34Z)
• On Linear Stochastic Approximation: Fine-grained Polyak-Ruppert and Non-Asymptotic Concentration [115.1954841020189]
  We study the inequality and non-asymptotic properties of approximation procedures with Polyak-Ruppert averaging. We prove a central limit theorem (CLT) for the averaged iterates with fixed step size and number of iterations going to infinity.
  arXiv  Detail & Related papers  (2020-04-09T17:54:18Z)

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.