Fundamental limits and algorithms for sparse linear regression with sublinear sparsity

• URL: http://arxiv.org/abs/2101.11156v6
• Date: Sat, 8 Apr 2023 20:17:56 GMT
• Title: Fundamental limits and algorithms for sparse linear regression with sublinear sparsity
• Authors: Lan V. Truong
• Abstract summary: We establish exact expressions for the normalized mutual information and minimum mean-square-error (MMSE) of sparse linear regression. We show how to modify the existing well-known AMP algorithms for linear regimes to sub-linear ones.
• Score: 16.3460693863947
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: We establish exact asymptotic expressions for the normalized mutual information and minimum mean-square-error (MMSE) of sparse linear regression in the sub-linear sparsity regime. Our result is achieved by a generalization of the adaptive interpolation method in Bayesian inference for linear regimes to sub-linear ones. A modification of the well-known approximate message passing algorithm to approach the MMSE fundamental limit is also proposed, and its state evolution is rigorously analyzed. Our results show that the traditional linear assumption between the signal dimension and number of observations in the replica and adaptive interpolation methods is not necessary for sparse signals. They also show how to modify the existing well-known AMP algorithms for linear regimes to sub-linear ones.

Related papers

• Global Convergence of Online Identification for Mixed Linear Regression [1.9295130374196499]
  Mixed linear regression (MLR) is a powerful model for characterizing nonlinear relationships. This paper investigates the online identification and data clustering problems for two basic classes of MLRs. It introduces two corresponding new online identification algorithms based on the expectation-maximization principle.
  arXiv  Detail & Related papers  (2023-11-30T12:30:42Z)
• Low-rank extended Kalman filtering for online learning of neural networks from streaming data [71.97861600347959]
  We propose an efficient online approximate Bayesian inference algorithm for estimating the parameters of a nonlinear function from a potentially non-stationary data stream. The method is based on the extended Kalman filter (EKF), but uses a novel low-rank plus diagonal decomposition of the posterior matrix. In contrast to methods based on variational inference, our method is fully deterministic, and does not require step-size tuning.
  arXiv  Detail & Related papers  (2023-05-31T03:48:49Z)
• Discrete-Time Nonlinear Feedback Linearization via Physics-Informed Machine Learning [0.0]
  We present a physics-informed machine learning scheme for the feedback linearization of nonlinear systems. We show that the proposed PIML outperforms the traditional numerical implementation.
  arXiv  Detail & Related papers  (2023-03-15T19:03:23Z)
• Offline Policy Optimization in RL with Variance Regularizaton [142.87345258222942]
  We propose variance regularization for offline RL algorithms, using stationary distribution corrections. We show that by using Fenchel duality, we can avoid double sampling issues for computing the gradient of the variance regularizer. The proposed algorithm for offline variance regularization (OVAR) can be used to augment any existing offline policy optimization algorithms.
  arXiv  Detail & Related papers  (2022-12-29T18:25:01Z)
• Linear Convergence of Natural Policy Gradient Methods with Log-Linear Policies [115.86431674214282]
  We consider infinite-horizon discounted Markov decision processes and study the convergence rates of the natural policy gradient (NPG) and the Q-NPG methods with the log-linear policy class. We show that both methods attain linear convergence rates and $mathcalO (1/epsilon2)$ sample complexities using a simple, non-adaptive geometrically increasing step size.
  arXiv  Detail & Related papers  (2022-10-04T06:17:52Z)
• On Optimal Interpolation In Linear Regression [22.310861786709538]
  We show that the optimal way to interpolate in linear regression is to use functions that are linear in the response variable. We identify a regime where the minimum-norm interpolator provably generalizes arbitrarily worse than the optimal response-linear achievable interpolator. We extend the notion of optimal response-linear to random features regression under a linear data-generating model.
  arXiv  Detail & Related papers  (2021-10-21T16:37:10Z)
• Predicting Flat-Fading Channels via Meta-Learned Closed-Form Linear Filters and Equilibrium Propagation [38.42468500092177]
  Predicting fading channels is a classical problem with a vast array of applications. In practice, the Doppler spectrum is unknown, and the predictor has only access to a limited time series of estimated channels. This paper proposes to leverage meta-learning in order to mitigate the requirements in terms of training data for channel fading prediction.
  arXiv  Detail & Related papers  (2021-10-01T14:00:23Z)
• 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)
• Understanding Implicit Regularization in Over-Parameterized Single Index Model [55.41685740015095]
  We design regularization-free algorithms for the high-dimensional single index model. We provide theoretical guarantees for the induced implicit regularization phenomenon.
  arXiv  Detail & Related papers  (2020-07-16T13:27:47Z)
• To Each Optimizer a Norm, To Each Norm its Generalization [31.682969645989512]
  We study the implicit regularization of optimization methods for linear models interpolating the training data in the under-parametrized and over-parametrized regimes. We argue that analyzing convergence to the standard maximum l2-margin is arbitrary and show that minimizing the norm induced by the data results in better generalizations.
  arXiv  Detail & Related papers  (2020-06-11T21:07:38Z)
• Multiscale Non-stationary Stochastic Bandits [83.48992319018147]
  We propose a novel multiscale changepoint detection method for the non-stationary linear bandit problems, called Multiscale-LinUCB. Experimental results show that our proposed Multiscale-LinUCB algorithm outperforms other state-of-the-art algorithms in non-stationary contextual environments.
  arXiv  Detail & Related papers  (2020-02-13T00:24:17Z)

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.