Sparse Regression and Support Recovery bounds for Orthogonal Matching Pursuit

Presented at Microsoft Research Lab - India, Bengaluru, India, 2018

\newcommand{\sstar}{s^*} \newcommand{\x}{\mathbf{x}} \newcommand{\y}{\mathbf{y}} \newcommand{\z}{\mathbf{z}} \newcommand{\g}{\mathbf{g}} \newcommand{\e}{\mathbf{e}} \newcommand{\q}{\mathbf{q}} \newcommand{\w}{\mathbf{w}} \newcommand{\p}{\mathbf{p}} \newcommand{\h}{\mathbf{h}} \newcommand{\etavec}{\boldsymbol{\eta}} \newcommand{\avec}{\mathbf{a}} \newcommand{\bvec}{\mathbf{b}} \newcommand{\dvec}{\mathbf{d}} \newcommand{\uvec}{\mathbf{u}} \newcommand{\xvec}{\mathbf{x}} \newcommand{\vvec}{\mathbf{v}} \newcommand{\xhat}{\mathbf{\hat{x}}} \newcommand{\xbar}{\mathbf{\bar{x}}} \newcommand{\xhatomp}[1]{\xhat^{\text{OMP}}_{#1}} \newcommand{\wopt}[1]{\mathbf{w}^{(#1)}} \newcommand{\res}{\mathbf{r}} \newcommand{\rss}[1]{\rho^+_{#1}} \newcommand{\rsc}[1]{\rho^-_{#1}} \newcommand{\cond}[1]{\kappa_{#1}} \newcommand{\generalizationError}{\mathcal{P}1} \newcommand{\recovery}{\mathcal{P}2} \newcommand{\A}{\mathbf{A}} \newcommand{\X}{\mathbf{X}} \newcommand{\Y}{\mathbf{Y}} \newcommand{\Q}{\mathbf{Q}} \newcommand{\G}{\mathbf{G}} \newcommand{\B}{\mathbf{B}} \newcommand{\U}{\mathbf{U}} \newcommand{\W}{\mathbf{W}} \newcommand{\M}{\mathbf{M}} \newcommand{\D}{\mathbf{D}} \newcommand{\I}{\mathbf{I}} \newcommand{\C}{\mathcal{C}} \newcommand{\V}{\mathcal{V}} \newcommand{\Rmat}{\mathbf{R}} \newcommand{\SIGMA}{\mathbf{\Sigma}} \newcommand{\LAMBDA}{\mathbf{\Lambda}} \newcommand{\BigO}[1]{O\left(#1\right)} \newcommand{\zero}{\mathbf{0}} \newcommand{\one}[1]{\mathbf{1}_{#1}} \newcommand{\Sum}{\sum_{i = 1}^{n}} \newcommand{\Sumi}[1]{\sum\limits_{i = 1}^{#1}} \newcommand{\Sumt}[1]{\sum\limits_{t = 1}^{#1}} \newcommand{\abs}[1]{\left\lvert#1\right\rvert} \newcommand{\norm}[2]{\left\lVert#2\right\rVert_{#1}} \newcommand{\esqnorm}[1]{\left\lVert#1\right\rVert_2^2} \newcommand{\enorm}[1]{\left\lVert#1\right\rVert_2} \newcommand{\infnorm}[1]{\left\lVert#1\right\rVert_\infty} \newcommand{\lznorm}[1]{\left\lVert#1\right\rVert_0} \newcommand{\eqdef}{\stackrel{\mathrm{def}}{=}} \DeclareMathOperator*{\argmin}{arg\,min} \DeclareMathOperator*{\argmax}{arg\,max} \newcommand{\R}{\mathbb{R}} \newcommand{\Rd}[1]{\mathbb{R}^{#1}} \newcommand{\inner}[1]{\left\langle#1\right\rangle} \newcommand{\E}[1]{\mathbb{E}\left[#1\right]} \newcommand{\Var}[1]{\text{Var}\left[#1\right]} \newcommand{\Prob}[1]{P\left\lbrace#1\right\rbrace} \newcommand{\Exp}[2]{\mathbb{E}_{#1}\left[#2\right]} \newcommand{\inv}[1]{\frac{1}{#1}} \newcommand{\indicator}[2]{\mathbbm{1}_{#1}(#2)} \newcommand{\BOX}[1]{\fbox{\parbox{\linewidth}{\centering#1}}} \newcommand{\prox}[2]{\text{prox}_{#1}\left(#2\right)} \newcommand{\Avgi}[1]{\inv{#1}\Sumi{#1}} \newcommand{\dodo}[2]{\frac{\partial #1}{\partial #2}} \newcommand{\Cov}{\mathbf{\Sigma}} \newcommand{\sparsity}[1]{\left\lVert#1\right\rVert_0} \newcommand{\supp}[1]{\text{supp}(#1)} \newcommand{\half}{\inv{2}} \newcommand{\kappas}[1]{\widetilde{\kappa}_{#1}} \newcommand{\Sset}{\mathbf{S}} \newcommand{\Si}[1]{\mathbf{S}_{#1}} \newcommand{\Sstar}{\mathbf{S}^*} \newcommand{\ASstar}{\A_{\Sstar}} \newcommand{\roundbrack}[1]{\left( #1 \right)} \newcommand{\curlybrack}[1]{\left\lbrace #1 \right\rbrace} \newcommand{\squarebrack}[1]{\left\lbrack #1 \right\rbrack} \newcommand{\textequal}[1]{\stackrel{\text{#1}}{=}} \newcommand{\textleq}[1]{\stackrel{\text{#1}}{\leq}} \newcommand{\textgeq}[1]{\stackrel{\text{#1}}{\geq}} \newcommand{\slr}{\textsf{SLR}} \newcommand{\brackeps}{\roundbrack{\epsilon}}We study the problem of Sparse Regression, a landmark problem in the domain of Machine Learning, Statistics and Optimization which finds numerous applications in Compressed Sensing, model compression, high dimensional statistics, bio-informatics, resource constrained machine learning and more. Sparse Regression can be written down as an optimization problem as

x¯=argmin‖x‖0≤s∗⁡f(x)\xbar = \argmin\limits_{\lznorm{\x}\leq \sstar} f(\x)

where x∈Rd\x\in\Rd{d}, s∗\sstar much smaller than dd, the ambient dimension, ‖⋅‖0\lznorm{\cdot} is the ℓ0\ell_0 norm that denotes the number of non-zero elements of its arguments, and ff is a real valued function.

Our focus has been on the linear version of the problem where given nn samples of dd dimensional data A∈Rn×d\A\in\Rd{n\times d} and a response vector y∈Rd\y\in\Rd{d}, we want to recover a s∗\sstar-sparse vector x¯\xbar that minimizes the squared loss function ‖Ax−y‖22\esqnorm{\A\x-\y}. However, this problem can be shown to be NP-hard via a reduction to 3-set cover, nonetheless this problem has been studied under a variety of assumptions such as the ones below

  1. Mutual Incoherence - Implies that the |⟨Ai,Aj⟩|\abs{\inner{\A_i,\A_j}} should be bounded by some small positive real number MM for all i≠ji\neq j. In specific it can be shown OMP (which we will discuss in detail below) can recover x¯\xbar in exactly s∗\sstar steps if M≤12s∗−1M\leq \inv{2\sstar-1}. Refer Theorem 5.14, Foucart and Rauhut for a short proof. Note that this can be equivalently written as ‖vec(ATA−Id)‖∞≤M. \infnorm{vec(\A^T\A - \I_{d})} \leq M.
  2. Restricted Isometry Property (RIP) - Instead of enforcing an element-wise restcriction on the off-diagonals of the matrix ATA\A^T\A, RIP (at a level ss) requries a more general assumption that all ss-sized principal block sub-matrices of ATA\A^T\A are δs\delta_s close to Is\I_s in the operator norm, i.e., ‖ASTAS−Is‖2≤δs\enorm{\A_\Sset^T\A_\Sset-\I_s} \leq \delta_s. Note that this also implies the below inequality (1−δs)‖v‖22≤‖Av‖22≤(1+δs)‖v‖22 ∀ v∈Rd s.t. ‖v‖0≤s.(1-\delta_s)\esqnorm{\vvec} \leq \esqnorm{\A\vvec} \leq (1+\delta_s)\esqnorm{\vvec} \ \forall\ \vvec \in\Rd{d} \text{ s.t. } \lznorm{\vvec} \leq s. It can be easily shown that Mutual Incoherence ⟹\implies RIP via (δs≤M(s−1) ∀ s≥2)\roundbrack{\delta_s\leq M(s-1) \ \forall\ s\geq 2}. Refer Lemma A.1, Donoho, Elad, Temlyakov for a short proof.
  3. Restricted Null Space property - Implies that all the vectors in the null space of A\A (except 0\zero) are far from being sparse. This property essentially characterizes when ℓ1\ell_1 based sparse recovery algorithms work. Formally it requires {v∈Rd∣Av=0}∩{v∈Rd∣‖vSc‖1≤‖vS‖1}=0. \curlybrack{\vvec\in\Rd{d} \mid \A\vvec = \zero}\cap\curlybrack{\vvec \in \Rd{d} \mid \norm{1}{\vvec_{\Sset^\mathsf{c}}} \leq \norm{1}{\vvec_\Sset}} = \zero. Restricted Null Space property an even weaker assumption than RIP.
  4. Restricted Strong Convexity (RSC) - This is a generalization of RIP as in the contraction that A\A as an operator can perform on any ss-sparse vector v\vvec can be arbitrariliy small (but not 00). It essentiall means that there is a significant difference (in the ℓ2\ell_2 norm sense) in the responses of 2 candidate sparse vectors which differ in their support by at most ss. Formally, ‖Ax−Az‖22≥ρs−‖x−z‖22∀ x,z∈Rd s.t. ‖x−z‖0≤s\esqnorm{\A\x-\A\z} \geq \rsc{s}\esqnorm{\x-\z}\quad \forall\ \x,\z\in\Rd{d} \text{ s.t. } \lznorm{\x-\z} \leq s where ρs−\rsc{s} is the RSC constant at the level ss. RSC is the weakest and the most popular asumption of all mentioned for sparse regression problems studied in the context of various algorithms.

Mutual Incoherence ⟹\implies RIP ⟹\implies Restricted Null Space Property ⟹\implies RSC.

The Linear form of Sparse Linear Regression (SLR)\roundbrack{\slr} is a representative problem and results typically extend easily to the general case. We consider the statistical setting of SLR\slr where the response is corrupted by adding an i.i.d. gaussian noise vector. We attempt to study this problem under the RSC assumption for a greedy algorithm Orthogonal Matching Pursuit algorithm.

y=Ax¯+η=AS∗x¯S∗+η\y = \A\xbar + \etavec = \A_{\Sstar}\xbar_{\Sstar} + \etavec

where η∼N(0,σ2In)\etavec\sim \mathcal{N}\roundbrack{\zero,\sigma^2 \I_n} has i.i.d. normally distributed elements with variance σ2\sigma^2, and supp(x¯)=s∗\text{supp}(\xbar) = \sstar.

Questions of interest

  1. For any sparse regression algorithm, bounding the generalization error under a statistical model is a major machine learning goal. Here, the generalization error is defined as G(x)=1n‖Ax−y‖22G(\x) = \inv{n}\esqnorm{\A\x-\y} where the rows of A\A are i.i.d. samples from some data distribution.
  2. Bounding the generalization error alone does not guarantee that the algorithm recovers the true support. This can be loosely answered by arguing if the algorithm can output a support set S\Sset such that S⊇S∗\Sset \supseteq \Sstar. Ideally one would like to have the smallest such set S\Sset satisfying the superset condition.

It is to note that given support recovery, smaller the support set size, lower is generalization error. Recovering the true support is a fundamentally harder problem as strong support recovery results usually tend to provide strong generalization error bounds.

Below we describe the 2 algorithms we looked at during the project span.

Algorithms for Sparse Linear Regression

Broadly, existing sparse regression algorithms can be broadly categorized into 3 categories.

  1. ℓ1\ell_1 minimization or LASSO based algorithms. E.g. - Dantzig selector etc.
  2. Non-convex penalty based. E.g. - Iterative Hard Thresholding, Penalty based methods like SCAD penalty, Log-sum penalty etc.
  3. Greedy methods. E.g. - Orthogonal Matching Pursuit (OMP) etc.

Iterative Hard Thresholding

Iterative Hard Thresholding as from the name suggests, takes a dense gradient step from the current ss-sparse iterate at each iteration, and projects the dense iterate back to the ss-sparse set by keeping only the top ss elements in terms of their absolute values. We fix a learning rate, and start at x0=0\x_0 = \zero. At the ttht^{th} iteration

  1. xt+1=Ps(xt−η∇xf(xt))\x_{t+1} = \mathcal{P}_s\roundbrack{\x_t - \eta\nabla_{\x}f(\x_t)}.

where Ps\mathcal{P}_s is the operator that projects its arguments to the ss-sized ℓ0\ell_0 ball. This can be easily done via sorting the elements of the argument vector based on their absolute values. The algorithm starts at 0\zero and refines the solution at each step keeping only the ss dominant values in its iterates.

Orthogonal Matching Pursuit

As a greedy algorithm, OMP is one of the most simple and classical algorithm that works in an incremental fashion such that at each step, one feature is added to the support set based on a criterion, and so the size of the support set of equal to the number of steps OMP is run.

We start with the null set with the initial estimate of the solution being 0\zero. At each step, we compute the residual and look at the remaining features to see which feature best explains the residual and include the feature into the support set. The next iterate is the one which best optimizes the convex quadratic loss with the support of the variable restricted to the current support set. This can be easily computed using a least squares solver.

Compactly, with S0=ϕ\Sset_0 = \phi, x0=0\x_0 = \zero, r0=y−Ax0=y\res_0 = \y-\A\x_0 = \y. At the kthk^{th} iteration,

  1. j←argmaxi∉Sk−1⁡|AiTrk−1|j \gets \argmax\limits_{i\not\in\Sset_{k-1}} \abs{\A_i^T\res_{k-1}}
  2. Sk←Sk−1∪{j}\Sset_k \gets \Sset_{k-1} \cup \curlybrack{j}
  3. xk←argminsupp(x)⊆Sk⁡‖Ax−y‖22\x_k \gets \argmin\limits_{\text{supp}(\x)\subseteq\Sset_k} \esqnorm{\A\x-\y}
  4. rk←y−Axk=y−ASkxk\res_k \gets \y - \A\x_k = \y - \A_{\Sset_k}\x_k

Interestingly, note that |AiTrk−1|∝[∇f(xk−1)]i\abs{\A_i^T\res_{k-1}} \propto \squarebrack{\nabla f(\x_{k-1})}_i for f(x)=‖Ax−y‖22f(\x) = \esqnorm{\A\x-\y} and the algorithm can be easily modified for a general function ff for which step 3 is cheap.

Quantities of interest

To formalize the problem, let us define some key problem dependent quantities on which the problem depends on

  1. Restricted Smoothness (ρs+)(\rss{s}) and Restricted Strong Convexity (ρs−)(\rsc{s}) - ρs−‖x−z‖22≤‖Ax−Az‖22≤ρs+‖x−z‖22∀ x,z s.t. ‖x−z‖0≤s. \rsc{s}\esqnorm{\x-\z} \leq \esqnorm{\A\x-\A\z} \leq \rss{s}\esqnorm{\x-\z}\qquad \forall\ \x,\z \text{ s.t. }\lznorm{\x-\z}\leq s.
  2. Restricted Condition number (κ~s\kappas{s}) - κ~s=ρ1+ρs− \kappas{s} = \frac{\rss{1}}{\rsc{s}}
  3. We also define the quantity similar to usual condition number where both the Restricted Smoothness and the Restricted Strong Convexity are at the same level ss κs=ρs+ρs−≥κ~s \kappa_{s} = \frac{\rss{s}}{\rsc{s}} \geq \kappas{s}

The Restricted Condition number is essentially a normalized way of referring to the inverse Restricted Strong Convexity, and therefore is a measure that determines the hardness of the problem.

Lower bounds for Fast Rate

Let us say for a moment that one can actually find the best minimizer to the SLR\slr problem. Let x^ℓ0\xhat_{\ell_0} be the best ℓ0\ell_0 estimate in the set of all s∗\sstar-sparse vectors. Then one can show that the expected generalization error for the worst problem is upper bounded by the fast rate, that is

sup‖x¯‖0≤s∗E[‖A(x^ℓ0−x¯)‖22]≲1nσ2s∗log⁡d\sup\limits_{\lznorm{\xbar}\leq \sstar}\E{\esqnorm{\A(\xhat_{\ell_0}-\xbar)}} \lesssim \inv{n}\sigma^2\sstar\log d

But the question than one might ask is how can one compute the estimate x^ℓ0\xhat_{\ell_0}? Because this problem is NP-hard, one trivial way therefore is to search over all (ds∗){d \choose \sstar} s∗\sstar sized subsets of [d]\squarebrack{d}. This is practically infeasible due to its complexity, therefore bounding the generalization error under the restriction that the estimate is polynomial time computable is a more practical question to ask.

Y. Zhang, M. Wainwright & M. Jordan’ 2014 come up with a lower bound proving that there exists a bad design matrix Abad\A_{\text{bad}}, such that if x^poly\xhat_{\text{poly}} is the output of any polynomial time algorithm, then the generalization error is lower bounded by a similar quantity but with an extra factor of κ~s∗\kappas{\sstar}.

sup‖x¯‖0≤s∗E[‖Abad(x^poly−x¯)‖22]≳1nσ2κ~s∗s∗log⁡d\sup\limits_{\lznorm{\xbar}\leq \sstar}\E{\esqnorm{\A_{\text{bad}}(\xhat_{\text{poly}}-\xbar)}} \gtrsim \inv{n}\sigma^2\kappas{\sstar}\sstar\log d

As a consequence to their work, any estimator x^\xhat that achieves the fast rate must either not be polynomial time computable, or must not return a s∗\sstar-sparse vector.

The tightest upper bounds on the generalization error known before this work for algorithms like IHT, OMP and Lasso were at least κ~\kappas{} times worse than this lower bound. A question then arises from this gap is whether the lower bound is itself loose or if there exists an algorithm for which we can have a better upper bound matching the known lower bound up to constants.

Attempts with IHT

To understand the gap better, we first started off by trying to tighten the upper bound proven by Jain et. al. for a candidate algorithm, Iterative Hard Thresholding. Their analysis requires IHT to be run at a level s≥Ω(κs2s∗)s\geq \mathcal{\Omega}(\kappa_s^2\sstar) for linear convergence in the function space. Bringing it down to s≥Ω(κss∗)s\geq \mathcal{\Omega}(\kappa_s\sstar) would result in a much better generalization error bound than the ones they have. We tried incorporating several variants of acceleration into IHT to bring down the required expansion to at least s≥Ω(κss∗)s\geq \mathcal{\Omega}(\kappa_s\sstar) but the trivial analysis breaks down at certain points. However, there are strong empirical instances where Gradient Descent based IHT is inferior to Accelerated IHT.

GD-IHT vs Acc IHT

The above plot describes how the error ‖Ax^s−y‖2\enorm{\A\xhat_s-\y} changes when we run IHT up to convergence at level ss (on the x-axis). The blue-dashed line represents the Euclidean norm of the noise. We see that Accelerated IHT uniformly achieves lower function value and dips earlier than the vanilla IHT. It was also observed that the rate of convergence of Accelerated IHT is much better than vanilla IHT and exhibits an oscillation behavior just like the error dynamics in the usual Nesterov’s acceleration.

Attempts with OMP

We restart exploring this gap by considering the classical algorithm OMP. Because OMP is a greedy algorithm, coming up with a lower bound instance for the support recovery is easy. For this we need to construct a matrix M\M such that it has a controlled Restricted Condition number κ~s\kappas{s} but still with high probability, at each step OMP ends up picking incorrect features and recovers the true support at the near end. Because the generalization error typically increases as the algorithm picks incorrect features, the generalization error incurred by OMP would be high.

Lower bound instance construction

We construct a parameterized matrix M(ϵ)∈Rn×d(d≤n)\M^\brackeps\in\Rd{n\times d} (d\leq n) by 0≤ϵ≤10\leq \epsilon\leq 1 such that all the s∗\sstar columns of the true support S∗\Sstar are orthogonal and the remaining columns are linear combinations of the mean of the true features and vectors orthogonal to their subspace. Precisely,

  1. M1:s∗(ϵ)\M^\brackeps_{1:\sstar} are random s∗\sstar orthgonal vectors s.t. ‖Mi(ϵ)‖22=n ∀ i∈[s∗]\esqnorm{\M^\brackeps_i} = n \ \forall\ i\in\squarebrack{\sstar}.
  2. Mi(ϵ)=1−ϵ[1s∗∑j=1s∗Mj(ϵ)]+ϵgi ∀i∉[s∗]\M^\brackeps_i = \sqrt{1-\epsilon}\squarebrack{\inv{\sqrt{\sstar}}\sum\limits_{j=1}^{\sstar} \M^\brackeps_j} + \sqrt{\epsilon}\g_i \ \forall i\not\in\squarebrack{\sstar} where gi\g_i’s are orthogonal to each other and M1:s∗(ϵ)\M^\brackeps_{1:\sstar} with ‖gi‖22=n\esqnorm{\g_i} = n.

Below is a sketch to illustrate an example with n=d=3,s∗=2n=d=3, \sstar=2 and ϵ=0.25\epsilon=0.25.

M_eps

Note that by tuning ϵ\epsilon, we can either make the incorrect features very close to the subspace spanned by the correct features or keep then almost orthogonal. This is evident if we take the dot product of a correct feature i∈S∗i\in\Sstar with an incorrect feature k∉S∗k\not\in\Sstar.

⟨Mi(ϵ),Mk(ϵ)⟩=⟨Mi(ϵ),1−ϵ[1s∗∑j=1s∗Mj(ϵ)]+ϵgk⟩=⟨Mi(ϵ),1−ϵ1s∗Mi(ϵ)⟩=n1−ϵs∗ \begin{align} \inner{\M^\brackeps_i,\M^\brackeps_k} &= \inner{\M^\brackeps_i,\sqrt{1-\epsilon}\squarebrack{\inv{\sqrt{\sstar}}\sum\limits_{j=1}^{\sstar} \M^\brackeps_j} + \sqrt{\epsilon}\g_k}\\ &= \inner{\M^\brackeps_i,\sqrt{1-\epsilon}\inv{\sqrt{\sstar}} \M^\brackeps_i}\\ &= n\sqrt{\frac{1-\epsilon}{\sstar}} \end{align}

Therefore higher ϵ\epsilon implies lower cross-set inner products, which in turn implies lower Restricted Condition number. We cannot set ϵ\epsilon to be very high as we will not be able to fool OMP into picking up incorrect features. Therefore we can solve for the interval of ϵ\epsilon so that OMP at each step picks up an incorrect feature.

We easily show that under the noiseless setting (σ=0)(\sigma = 0), if OMP is run on M(ϵ)\M^\brackeps for ϵ<1−1s∗\epsilon<1-\inv{\sstar}, then OMP will continue including incorrect features until only the correct ones are left. Because we want Restricted Condition number to be as low as possible so that OMP fails, any value of ϵ=1−αs∗\epsilon = 1-\frac{\alpha}{\sstar} is good for constant α>1\alpha>1.

Upper Bounding Generalization Error

The tightest known upper bounds for polynomial time algorithms like IHT, OMP and Lasso were at least κ~\kappas{} times worse than the fast rate lower bound. Lemma A.5, T. Zhang’ 10 have the loose upper bound on the sub-optimality gap but after only s=Θ(κ~slog⁡κss∗)s=\Theta\roundbrack{\kappas{s}\log\kappa_s \sstar} steps. This result gives a hint and a hope for a stronger generalization error because of the lower order of iterations. We exploit their line of analysis and tighten their sub-optimality gap by a factor of κs\kappa_s

Result directly using T. Zhang’s bound - If x^s\xhat_s is the outout of OMP after s=Θ(κ~slog⁡κss∗)s=\Theta\roundbrack{\kappas{s}\log\kappa_s \sstar} iterations, then with high probability

1n‖A(x^s−x¯)‖22≲1nσ2s∗κ~s+s∗2log⁡κs+s∗log⁡d\begin{equation} \inv{n}\esqnorm{\A(\xhat_s-\xbar)} \lesssim \inv{n}\sigma^2\sstar\kappas{s+\sstar}^2\log\kappa_{s+\sstar}\log d \end{equation}

Upon slight modifications and tightening T. Zhang’s analysis, we prove a better generalization bound that matches the fast rate up to logarithmic factors in κ\kappa.

Result after modifying T. Zhang’s analysis - If x^s\xhat_s is the outout of OMP after s=Θ(κ~slog⁡κss∗)s=\Theta\roundbrack{\kappas{s}\log\kappa_s \sstar} iterations, then with high probability

1n‖A(x^s−x¯)‖22≲1nσ2s∗κ~s+s∗log⁡κs+s∗log⁡d\begin{equation} \inv{n}\esqnorm{\A(\xhat_s-\xbar)} \lesssim \inv{n}\sigma^2\sstar\kappas{s+\sstar}\log\kappa_{s+\sstar}\log d \end{equation}

Gaussian Ensemble upper bounds

We can instantiate the above results for Gaussian ensembles, i.e. when the rows of A\A are sampled from a multivariate Gaussian distribution N(0,Σ)\mathcal{N}\roundbrack{\zero,\SIGMA}. If σmax\sigma_\max and σmin\sigma_\min are the maximum and minimum singular values of Σ\SIGMA, and κ(Σ)=σmax/σmin\kappa(\SIGMA) = \sigma_\max/\sigma_\min is its condition number, then we achieve the best known generalization error guarantee in terms of the dependence on κ(Σ)\kappa(\SIGMA).

Generalization error for Gaussian Ensemble - If Σii≤1 ∀ i∈[d]\SIGMA_{ii} \leq 1 \ \forall\ i\in\squarebrack{d}, n=Ω(slog⁡dσmin)n = \mathcal{\Omega}\roundbrack{\frac{s\log d}{\sigma_\min}} and if x^s\xhat_s is the output of OMP after s=Θ(κ(Σ)log⁡κ(Σ)s∗)s=\Theta\roundbrack{\kappa(\SIGMA)\log\kappa(\SIGMA) \sstar} iterations where S=supp(x^s)\Sset = \supp{\xhat_s}, then with high probability,

1n‖A(x^s−x¯)‖22≤1nσ2κ(Σ)log⁡κ(Σ)s∗log⁡d\inv{n}\esqnorm{\A(\xhat_s-\xbar)} \leq \inv{n}\sigma^2\kappa(\SIGMA)\log \kappa(\SIGMA) \sstar \log d

This result is a corollary of the general generalization upper bound result using some concentration results.

Support Recovery upper bound

Loh’ 14 have strong support recovery results on non-convex regularization based algorithms that use SCAD/MCP like penalty, but they require the mutual incoherence of the matrix A\A to be bounded by 11 which is independent of any problem parameter and is too much to ask for. For greedy algorithms like HTP and PHT however, we have doubts about the correctness of the analysis in the latter result.

We prove and exploit a crucial property for OMP that if at any iteration there is a true feature that is not recovered and if the smallest absolute value of the true solution x¯\xbar that is |x¯min|\abs{\bar{x}_{\min}} is greater than an appropriate noise level, then there is a significant decrease in the objective function. Precisely, we have that

Large decrease in objective - If x^s\xhat_s is the output of OMP after s=Ω(κ~slog⁡κss∗)s = \Omega\roundbrack{\kappas{s}\log\kappa_s \sstar} iterations s.t. S∗∖S≠ϕ\Sstar\setminus\Sset \neq \phi and |x¯min|≳σγρ1+ρs+s∗−\abs{\bar{x}_{\min}} \gtrsim \frac{\sigma\gamma\sqrt{\rss{1}}}{\rsc{s+\sstar}}, then with high probability

‖Ax^s−y‖22−‖Ax^s+1−y‖22≳σ2log⁡d\begin{equation} \esqnorm{\A\xhat_s-\y} - \esqnorm{\A\xhat_{s+1}-\y} \gtrsim \sigma^2\log d \end{equation}

where ‖AS∗∖STAS(ASTAS)−1‖∞≤γ\infnorm{\A_{\Sstar\setminus\Sset}^T\A_\Sset\roundbrack{\A_\Sset^T\A_\Sset}^{-1} }\leq \gamma and S=supp(x^s)\Sset = \supp{\xhat_s}.

We note that the γ\gamma in this result is similar to the mutual incoherence condition and is not required to be bounded by a universal constant and can be very large. This crucially helps us to show that the condition that there are some true features are left out, cannot be true for very long because if it is true then at each step we have a good decrease in the function value and because the function value is non negative and nicely lower bounded, all the true features must be included in the support and we must have supp(x^s+k⊇S∗)\supp{\xhat_{s+k}\supseteq\Sstar} for a small value of kk. In fact, it can be shown that k=Θ(s)k = \Theta(s) suffices which allows us to prove the following theorem

Support recovery upper bound - If x^s\xhat_s is the output of OMP after s=Ω(κ~slog⁡κss∗)s = \Omega\roundbrack{\kappas{s}\log\kappa_s \sstar} iterations, ‖AS∗∖STAS(ASTAS)−1‖∞≤γ\infnorm{\A_{\Sstar\setminus\Sset}^T\A_\Sset\roundbrack{\A_\Sset^T\A_\Sset}^{-1} }\leq \gamma, S=supp(x^s)\Sset = \supp{\xhat_s}, and |x¯min|≳σγρ1+ρs+s∗−\abs{\bar{x}_{\min}} \gtrsim \frac{\sigma\gamma\sqrt{\rss{1}}}{\rsc{s+\sstar}} then with high probability S∗⊆supp(x^s)\Sstar \subseteq \supp{\xhat_s}.

It is to note that the assumption on |x¯min|\abs{\bar{x}_{\min}} satistically relaxes out with increasing number of data points nn. This is because both ρ+\rss{} and ρ−\rsc{} have a factor of nn in them amd the bound depends on ρ1+ρs+s∗−∝1n\frac{\sqrt{\rss{1}}}{\rsc{s+\sstar}} \propto \inv{\sqrt{n}}.

ρs−‖v‖22≤‖Av‖22=vTATAv=nvT1nATAv=nvTΣ^vρs+‖v‖22≥‖Av‖22=vTATAv=nvT1nATAv=nvTΣ^v \begin{align} \rsc{s}\esqnorm{\vvec} &\leq \esqnorm{\A\vvec} = \vvec^T\A^T\A\vvec = n\vvec^T\inv{n}\A^T\A\vvec = n\vvec^T\hat{\SIGMA}\vvec\\ \rss{s}\esqnorm{\vvec} &\geq \esqnorm{\A\vvec} = \vvec^T\A^T\A\vvec = n\vvec^T\inv{n}\A^T\A\vvec = n\vvec^T\hat{\SIGMA}\vvec \end{align}

for ‖v‖0≤s\lznorm{\vvec}\leq s. Σ^\hat{\SIGMA} is the empirical second order moment matrix of A\A and converges to the true second order moment as nn increases.

Using this support recovery result, we can also bound the element-wise error i.e., ‖x^s−x¯‖∞\infnorm{\xhat_s-\xbar}.

Infinity norm error bound - As a consequence of support recovery from the above theorem under the same assumptions, we have

‖x^−x¯‖∞≲σlog⁡sρs−\infnorm{\xhat-\xbar} \lesssim \sigma\sqrt{\frac{\log s}{\rsc{s}}}

Note that the bound on the infinity norm requires support recovery and is κ~\sqrt{\kappas{}} lower the known bounds in other works. We currently are trying to bound the infinity norm even if support recovery has not taken place. This essentially requires to prove that the infinity norm of the true solution on the unrecovered support set is bounded. Such a result is an interesting approximation because in practice we might not know if full support recovery has taken place but still an element-wise bound would hold and one can think of pruning down the elements of the estimate to get better support sets or even come up with a stronger algorithm in practice.

Matching lower bounds for generalization error and support recovery

It turns out that the simple matrix M(ϵ)\M^\brackeps and x¯\xbar construction, as discussed earlier leads to lower bounds for both generalization and support recovery for OMP or proper choices of ϵ\epsilon. To show this, we first analyze how the Restricted Condition number κs\kappa_s and γ\gamma depends on ss and ϵ\epsilon and then we can choose proper ϵ∈(0,1)\epsilon \in \roundbrack{0,1} so that the assumptions of the upper bound theorems are satisfied and still OMP fails to have good generalization error as well as support recovery in good number of steps.

The matrix class M(ϵ)\M^\brackeps satisfies

  1. κ~s(M(ϵ))≤4(1+2(1−ϵ)s)=O(s)\kappas{s}\roundbrack{\M^\brackeps} \leq 4(1+2(1-\epsilon)s) = \BigO{s}, and
  2. γ(M(ϵ))≤1s∗(1−ϵ)\gamma\roundbrack{\M^\brackeps} \leq \inv{\sqrt{\sstar(1-\epsilon)}} for S∩S∗=ϕ\Sset\cap\Sstar = \phi

Proving a lower bound for the noiseless version of SLR\slr is relatively easier and the below theorem states the result

Lower bound for noiseless SLR\slr - For all s∗≤d≤n\sstar\leq d\leq n, there exists a design matrix M(ϵ)\M^\brackeps and a s∗\sstar-sparse vector x¯\xbar such that when OMP is executed on the corresponding SLR\slr problem, then for s≤d−s∗s\leq d-\sstar we have

  1. κ~s(M(ϵ))≤O(ss∗)(or s≥Ω(κ~ss∗))\kappas{s}\roundbrack{\M^\brackeps} \leq \BigO{\frac{s}{\sstar}} \quad (\text{or } s \geq \mathcal{\Omega}(\kappas{s}\sstar)) and γ≤O(1)\gamma \leq \BigO{1}, and
  2. S∗∩supp(x^s)=ϕ\Sstar \cap \supp{\xhat_s} = \phi

The result indeed tells that for OMP one needs to at least go till a level of s≥Ω(κ~ss∗)s \geq \mathcal{\Omega}\roundbrack{\kappas{s}\sstar} to uniformly guarantee support recovery. The lower bound result in Y. Zhang, M. Wainwright & M. Jordan’ 2014 does not hold for OMP because the sparsity of the estimate of OMP is equal to the number of iterations to which it has been run, and their lower bound holds for algorithms which exactly outputs a s∗\sstar-sparse estimate. Our lower bound construction is specific for OMP. We also look at the bad matrix constructed in Y. Zhang’s work and find that for our uniform x¯\xbar construction, OMP recovers the true support in O(s∗)\BigO{\sstar} steps with n=Θ(s∗log⁡d)n = \Theta(\sstar \log d) samples despite the fact that the restricted condition number of their bad matrix is high. So in general, large condition number alone does not imply difficulty in recovery for OMP.

For noiseless SLR\slr, the question of generalization error does not arise because σ=0\sigma=0. For the noisy case, we again have the same matrix construction M(ϵ)\M^\brackeps with an appropriate ϵ\epsilon so that with high probability we do not recover the full support and also the generalization error is large. The proof that there is no support recovered by OMP until the near end (s≤d1−αs\leq d^{1-\alpha} for α=o(1)\alpha = o(1)), involves an intricate argument of order statistics of correlated Gaussian random variables, which is non-trivial.

Lower bound for noisy SLR\slr - For s∗≥8\sstar\geq 8 and d≥Ω(1)d\geq \mathcal{\Omega}(1), there exists a design matrix M(ϵ)\M^\brackeps and a s∗\sstar-sparse vector x¯\xbar s.t. if OMP is run on the corresponding SLR\slr problem, then for s≤d1−αs\leq d^{1-\alpha} for some α=o(1)\alpha = o(1), with high probability,

  1. κ~s(M(ϵ))≤O(ss∗)(or s≥Ω(κ~ss∗))\kappas{s}\roundbrack{\M^\brackeps} \leq \BigO{\frac{s}{\sstar}} \quad (\text{or } s \geq \mathcal{\Omega}(\kappas{s}\sstar)) and γ≤O(1)\gamma \leq \BigO{1},
  2. 1n‖A(x^s−x¯)‖22≳1nσ2κ~s+s∗s∗log⁡d\inv{n}\esqnorm{\A(\xhat_s-\xbar)} \gtrsim \inv{n}\sigma^2\kappas{s+\sstar}\sstar\log d, and
  3. S∗∩supp(x^s)=ϕ\Sstar \cap \supp{\xhat_s} = \phi.

We think that the condition s≤d1−αs\leq d^{1-\alpha} is important because of the randomness in the support selection step of the algorithm introduced because of the noise vector η\eta and one might not expect complete disjointness until the very end, i.e., s≤d−s∗s\leq d-\sstar, supp(x^s)∩S∗=ϕ\supp{\xhat_s}\cap\Sstar=\phi. In specific, one can think of α≃log⁡log⁡dlog⁡d\alpha \simeq \frac{\log\log d}{\log d} which would require d≥55d\geq 55 as a mild assumption in our analysis.

Simulations

We also verify our results by performing some simulations. We generate our lower bound matrix M(ϵ)∈R1000×100\M^\brackeps \in \Rd{1000\times 100} and a fixed s∗=10\sstar=10-sparse vector x¯\xbar with S∗=supp(x¯)\Sstar = \supp{\xbar}. The response y\y is generated as y=M(ϵ)x¯+η\y = \M^\brackeps\xbar + \etavec where η∼N(0,σ2In)\eta \sim \mathcal{N}\roundbrack{\zero,\sigma^2\I_n}. We denote s^(ϵ)\hat{s}(\epsilon) as the support set size when full support recovery takes place, i.e., s^(ϵ)=supp(x^)\hat{s}(\epsilon) = \supp{\xhat} is the smallest integer such that supp(x^s^(ϵ))⊇S∗\supp{\xhat_{\hat{s}(\epsilon)}}\supseteq \Sstar holds. Because of the explicit construction of M(ϵ)\M^\brackeps, we can compute the exact κ~(M(ϵ))\kappas{}\roundbrack{\M^\brackeps} which will be a function of ϵ\epsilon. In general, the Restricted Condition number of M(ϵ)\M^\brackeps increases with decreasing ϵ\epsilon as noted earlier. We vary ϵ\epsilon, which varies κ~(M(ϵ))\kappas{}\roundbrack{\M^\brackeps} and plot s^(ϵ)\hat{s}(\epsilon) for σ2=0,0.5\sigma^2 = 0, 0.5 and 11.

Varying condition number

We clearly see the criticality of κ~\kappas{} for OMP’s support recovery property on our lower bound instance M(ϵ)\M^\brackeps for an appropriate ϵ\epsilon, when for the noiseless case (σ2=0\sigma^2 = 0), we observe that there is a sharp threshold of κ~\kappas{} before which OMP takes exactly s∗\sstar steps to recover the support and after which OMP recovers the full support at the very end (dthd^{th} iterate).

Because M(ϵ)\M^\brackeps is explicitly constructed so that OMP on the noiseless version of SLR\slr version drastically fails, implies that addition of noise in the corresponding SLR\slr problem will only help OMP because of the noise introduced in the selection step of OMP and one would expect that when noise is very high, the selection step of OMP tends to become a random selector. This behaviour is clearly observed when we plot s^(ϵ)=supp(x^)\hat{s}(\epsilon) = \supp{\xhat} with respect to σ2\sigma^2 after sufficient averaging.

Varying condition number

We see that when the noise is low, OMP struggles to capture the complete support. As we slowly increase the noise, the randomness introduced helps OMP recover the correct features; when the noise is very high, OMP’s selection step essentially tends to become a uniform random selector. This is represented by the red dashed horizontal line with equation limσ2→∞Eη∼N(0,σ2In)[s^(ϵ)]=s∗s∗+1d\lim\limits_{\sigma^2\to \infty}\Exp{\etavec\sim \mathcal{N}\roundbrack{\zero,\sigma^2\I_n}}{\hat{s}(\epsilon)} = \frac{\sstar}{\sstar+1}d. This behavior exactly matches what is expected from our upper and lower bound results on OMP’s support recovery.

The work was presented at Microsoft Research India Labs after the work on OMP got selected for a spotlight presentation at NeurIPS 2018. Find the presentation here.

Publication resources:

  1. NeurIPS poster.
  2. Proceedings and paper.
  3. Spotlight slides.
  4. Spotlight video presentation (from 1:36:20).