English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Global: Zendy Plus annual

Presents the access of premium content as premium feature

Premium Content

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Global: Zendy Plus monthly

Global: Zendy Tools annual

Global: Zendy Tools monthly

Global: Zendy Free Plan

We consider a sparse linear regression model Y=X\beta^{*}+W where X has aGaussian entries, W is the noise vector with mean zero Gaussian entries, and\beta^{*} is a binary vector with support size (sparsity) k. Using a novelconditional second moment method we obtain a tight up to a multiplicativeconstant approximation of the optimal squared error\min_{\beta}\|Y-X\beta\|_{2}, where the minimization is over all k-sparsebinary vectors \beta. The approximation reveals interesting structuralproperties of the underlying regression problem. In particular, a) We establishthat n^*=2k\log p/\log (2k/\sigma^{2}+1) is a phase transition point with thefollowing "all-or-nothing" property. When n exceeds n^{*},(2k)^{-1}\|\beta_{2}-\beta^*\|_0\approx 0, and when n is below n^{*},(2k)^{-1}\|\beta_{2}-\beta^*\|_0\approx 1, where \beta_2 is the optimalsolution achieving the smallest squared error. With this we prove that n^{*} isthe asymptotic threshold for recovering \beta^* information theoretically. b)We compute the squared error for an intermediate problem\min_{\beta}\|Y-X\beta\|_{2} where minimization is restricted to vectors \betawith \|\beta-\beta^{*}\|_0=2k \zeta, for \zeta\in [0,1]. We show that a lowerbound part \Gamma(\zeta) of the estimate, which corresponds to the estimatebased on the first moment method, undergoes a phase transition at threedifferent thresholds, namely n_{\text{inf,1}}=\sigma^2\log p, which isinformation theoretic bound for recovering \beta^* when k=1 and \sigma islarge, then at n^{*} and finally at n_{\text{LASSO/CS}}. c) We establish acertain Overlap Gap Property (OGP) on the space of all binary vectors \betawhen n\le ck\log p for sufficiently small constant c. We conjecture that OGP isthe source of algorithmic hardness of solving the minimization problem\min_{\beta}\|Y-X\beta\|_{2} in the regime n<n_{\text{LASSO/CS}}.

High-Dimensional Regression with Binary Coefficients. Estimating Squared Error and a Phase Transition