Ising Model Selection Using $\ell_{1}$-Regularized Linear Regression

• URL: http://arxiv.org/abs/2102.03988v1
• Date: Mon, 8 Feb 2021 03:45:10 GMT
• Title: Ising Model Selection Using $\ell_{1}$-Regularized Linear Regression
• Authors: Xiangming Meng and Tomoyuki Obuchi and Yoshiyuki Kabashima
• Abstract summary: We show that despite model misspecification, the $ell_1$-regularized linear regression ($ell_1$-LinR) estimator can successfully recover the graph structure of the Ising model with $N$ variables. We also provide a computationally efficient method to accurately predict the non-asymptotic performance of the $ell_1$-LinR estimator with moderate $M$ and $N$.
• Score: 13.14903445595385
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We theoretically investigate the performance of $\ell_{1}$-regularized linear regression ($\ell_1$-LinR) for the problem of Ising model selection using the replica method from statistical mechanics. The regular random graph is considered under paramagnetic assumption. Our results show that despite model misspecification, the $\ell_1$-LinR estimator can successfully recover the graph structure of the Ising model with $N$ variables using $M=\mathcal{O}\left(\log N\right)$ samples, which is of the same order as that of $\ell_{1}$-regularized logistic regression. Moreover, we provide a computationally efficient method to accurately predict the non-asymptotic performance of the $\ell_1$-LinR estimator with moderate $M$ and $N$. Simulations show an excellent agreement between theoretical predictions and experimental results, which supports our findings.

Related papers

• Scaling Laws in Linear Regression: Compute, Parameters, and Data [86.48154162485712]
  We study the theory of scaling laws in an infinite dimensional linear regression setup. We show that the reducible part of the test error is $Theta(-(a-1) + N-(a-1)/a)$. Our theory is consistent with the empirical neural scaling laws and verified by numerical simulation.
  arXiv  Detail & Related papers  (2024-06-12T17:53:29Z)
• Turnstile $\ell_p$ leverage score sampling with applications [56.403488578703865]
  We develop a novel algorithm for sampling rows $a_i$ of a matrix $AinmathbbRntimes d$, proportional to their $ell_p$ norm, when $A$ is presented in a turnstile data stream. Our algorithm not only returns the set of sampled row indexes, it also returns slightly perturbed rows $tildea_i approx a_i$, and approximates their sampling probabilities up to $varepsilon$ relative error. For logistic regression, our framework yields the first algorithm that achieves a $
  arXiv  Detail & Related papers  (2024-06-01T07:33:41Z)
• Almost Linear Constant-Factor Sketching for $\ell_1$ and Logistic Regression [74.28017932704704]
  We improve upon previous oblivious sketching and turnstile streaming results for $ell_1$ and logistic regression. We also give a tradeoff that yields a $1+varepsilon$ approximation in input sparsity time. Our sketch can be extended to approximate a regularized version of logistic regression where the data-dependent regularizer corresponds to the variance of the individual logistic losses.
  arXiv  Detail & Related papers  (2023-03-31T18:12:33Z)
• Streaming Sparse Linear Regression [1.8707139489039097]
  We propose a novel online sparse linear regression framework for analyzing streaming data when data points arrive sequentially. Our proposed method is memory efficient and requires less stringent restricted strong convexity assumptions.
  arXiv  Detail & Related papers  (2022-11-11T07:31:55Z)
• What Makes A Good Fisherman? Linear Regression under Self-Selection Bias [32.6588421908864]
  In the classical setting of self-selection, the goal is to learn $k$ models, simultaneously from observations $(x(i), y(i))$. In this work, we present the first computationally and statistically efficient estimation algorithms for the most standard setting of this problem where the models are linear.
  arXiv  Detail & Related papers  (2022-05-06T14:03:05Z)
• $p$-Generalized Probit Regression and Scalable Maximum Likelihood Estimation via Sketching and Coresets [74.37849422071206]
  We study the $p$-generalized probit regression model, which is a generalized linear model for binary responses. We show how the maximum likelihood estimator for $p$-generalized probit regression can be approximated efficiently up to a factor of $(1+varepsilon)$ on large data.
  arXiv  Detail & Related papers  (2022-03-25T10:54:41Z)
• Statistical Query Lower Bounds for List-Decodable Linear Regression [55.06171096484622]
  We study the problem of list-decodable linear regression, where an adversary can corrupt a majority of the examples. Our main result is a Statistical Query (SQ) lower bound of $dmathrmpoly (1/alpha)$ for this problem.
  arXiv  Detail & Related papers  (2021-06-17T17:45:21Z)
• Estimating Stochastic Linear Combination of Non-linear Regressions Efficiently and Scalably [23.372021234032363]
  We show that when the sub-sample sizes are large then the estimation errors will be sacrificed by too much. To the best of our knowledge, this is the first work that and guarantees for the lineartext+Stochasticity model.
  arXiv  Detail & Related papers  (2020-10-19T07:15:38Z)
• Truncated Linear Regression in High Dimensions [26.41623833920794]
  In truncated linear regression, $(A_i, y_i)_i$ whose dependent variable equals $y_i= A_irm T cdot x* + eta_i$ is some fixed unknown vector of interest. The goal is to recover $x*$ under some favorable conditions on the $A_i$'s and the noise distribution. We prove that there exists a computationally and statistically efficient method for recovering $k$-sparse $n$-dimensional vectors $x*$ from $m$ truncated samples.
  arXiv  Detail & Related papers  (2020-07-29T00:31:34Z)
• Optimal Robust Linear Regression in Nearly Linear Time [97.11565882347772]
  We study the problem of high-dimensional robust linear regression where a learner is given access to $n$ samples from the generative model $Y = langle X,w* rangle + epsilon$ We propose estimators for this problem under two settings: (i) $X$ is L4-L2 hypercontractive, $mathbbE [XXtop]$ has bounded condition number and $epsilon$ has bounded variance and (ii) $X$ is sub-Gaussian with identity second moment and $epsilon$ is
  arXiv  Detail & Related papers  (2020-07-16T06:44:44Z)
• Online Robust Regression via SGD on the l1 loss [19.087335681007477]
  We consider the robust linear regression problem in the online setting where we have access to the data in a streaming manner. We show in this work that the descent on the $ell_O( 1 / (1 - eta)2 n )$ loss converges to the true parameter vector at a $tildeO( 1 / (1 - eta)2 n )$ rate which is independent of the values of the contaminated measurements.
  arXiv  Detail & Related papers  (2020-07-01T11:38:21Z)

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.