Learning Mixtures of Linear Regressions in Subexponential Time via Fourier Moments

Introduction

where $\eta\sim{\mathcal{N}}(0,\varsigma^{2})$. This model has applications to problems ranging from trajectory clustering [GS99] to phase retrieval [BCE06, CSV13, NJS13] and is also widely studied as a natural non-linear generative model for supervised data [FS10, CYC13, CL13, YCS14, YCS16, ZJD16, SJA16, KYB17, BWY17, KQC+18, LL18, KC19].

Despite the apparent simplicity of the problem, efficiently learning MLRs given samples has proven to be a surprisingly challenging task. Even in the special case where $\varsigma=0$, that is, we assume that there is no noise on the samples, the fastest algorithms for this problem run in time depending on $k^{\Omega(k)}$ [LL18, ZJD16]. It turns out that there are good reasons for this barrier.

Previous algorithms for this problem with end-to-end provable guarantees—and indeed, the vast majority of statistical learning algorithms in general—build in some form or another on the method of moments paradigm. At a high level, these methods require that there exists some statistic which depends only on low degree moments of the unknown distribution, so that a sufficiently good estimate of this statistic will uniquely identify the parameters of the distribution. This includes widely-used techniques based on tensor decomposition [CL13, YCS16, ZJD16, SJA16], and SDP hierarchies such as the Sum-of-Squares meta-algorithm [KKK19, RY19]. If degree $t$ moments are necessary to devise such a statistic, then these methods require $\exp(\Omega(t))$ sample and computational complexity.

Unfortunately, for MLRs, it is not hard to demonstrate pairs of mixtures some of whose parameters are far apart from each other, where all moments of degree at most $2k-1$ of the two mixtures agree exactly (see Appendix A for more details). As a result, any moment-based estimator would need to use moments of degree at least $\Omega(k)$, and hence require a runtime of $\exp(\Omega(k))$. This imposes a natural bottleneck: any algorithm that hopes to achieve sub-exponential time must somehow incorporate additional information about the geometry of the underlying learning problem.

A related problem, which shares a similar bottleneck, is the problem of learning mixtures of Gaussians under the assumption of angular separation. A concrete instantiation of this problem is a model we call learning mixtures of hyperplanes. A mixture of hyperplanes is parameterized by mixing weights $p_{1},\ldots,p_{k}$, a separation parameter $\Delta>0$, and $k$ unit vectors $v_{1},\ldots,v_{k}$ satisfying $\|v_{i}\pm v_{j}\|_{2}\geq\Delta$ for all $i\neq j$ (note that the reason for the $\pm$ is that the directions of a mixture of hyperplanes are only identifiable up to sign). To draw a sample, we first draw $i\in[k]$ with probability $p_{i}$, and then draw a sample from ${\mathcal{N}}(0,\mathbf{I}-v_{i}v_{i}^{\top})$.

As before, the corresponding learning question is the following: given samples from an unknown mixture of hyperplanes, can one recover the underlying parameters? This problem can be thought of as a particularly hard case of the well-studied problem of subspace recovery, where current techniques would require time which is exponential in $k$.

In this paper, we give algorithms which are able to achieve strong recovery guarantees for the problems of learning MLRs and learning mixtures of hyperplanes, and which run in time which is sub-exponential in $k$. To the best of our knowledge, this is the first algorithm for the basic problem of learning MLRs which achieves sub-exponential runtime without placing strong additional assumptions on the model. At a high level, our key insight is that while low degree moments of the MLR are unable to robustly identify the instance, low degree moments of suitable projections of the Fourier transform of the MLR can be utilized to extract non-trivial information about the regressors. We then give efficient algorithms for computing such “Fourier moments” by leveraging algorithms for univariate density estimation [CDSS14, ADLS17]. This allows us to dramatically improve the runtime and sample complexity of the moment descent algorithm of [LL18], and allows us to obtain our desired sub-exponential runtime. We believe that this sort of algorithmic application of the continuous Fourier transform and of univariate density estimation to a high dimensional learning problem is novel, and may be of independent interest.

Here, we describe our contributions in more detail. For simplicity of exposition, in this section we will assume that the mixing weights are uniform, i.e. $p_{i}=1/k$ for all $i\in[k]$, although as we show, our algorithms can handle non-uniform mixing weights.

Our main results for learning MLRs are twofold. Throughout the paper we let $\widetilde{O}(f)=O(f\log^{c}(f))$ for some universal constant $c$. First, in the well-studied case where there is no regression noise, we show:

By combining this “warm start” with the boosting result of [LL18], we can also obtain arbitrarily good accuracy with minimal overhead in both the sample complexity and runtime. See Section 7 for more details.

Secondly, in the case when the noise rate $\varsigma$ is large, we can also obtain a similar result, though with an additional exponential dependence on $\Delta$:

Finally, for the problem of learning mixtures of hyperplanes, we are able to obtain qualitatively similar results. Again, for simplicity of exposition, we assume the mixing weights are uniform just in the current section. We obtain:

2 Related Work

Mixtures of linear regressions were introduced in [DV89], and later by [JJ94], under the name of hierarchical mixtures of experts, and have been studied extensively in the theory and ML communities ever since. Previous work on the problem with provable guarantees can roughly speaking be divided into three groups. Some of the previous work focuses on special cases of the problem, in particular, when the number of components is small [CYC13, KYB17, BWY17, KQC+18]. In contrast, we focus on the setting where $k$ is quite large, which is the setting which is typically true in applications, but is also much more algorithmically complicated.

Another line of work has focused on demonstrating local convergence guarantees for non-convex methods such as expectation maximization or alternating minimization [FS10, YCS14, YCS16, ZJD16, KYB17, BWY17, KQC+18, LL18, KC19]. These papers demonstrate that given a sufficiently good warm start, non-convex methods are able to boost this warm start to arbitrarily good accuracy. These results should be viewed as largely complementary to our results, as our main result is a method which is able to provably achieve a good warm start. That said, we also demonstrate new algorithms for learning given a warm start that work under a weaker initialization and can tolerate more regression noise than was previously known in the literature.

The final class of results use moment-based methods to learn MLRs. Here, the literature has focused largely on the case of $\varsigma=0$ and spherical covariates, that is, covariates all drawn from ${\mathcal{N}}(0,\mathbf{I})$. To the best of our knowledge, the primary exception to this is [LL18], which considered noise-less MLRs whose components’ covariates are drawn from arbitrary unknown Gaussians satisfying some condition number bounds and obtained a $d\cdot\exp(k^{2})$ algorithm in this setting. A line of work has studied tensor decomposition-based methods [CL13, YCS16, ZJD16, SJA16]. However, these require additional non-degeneracy conditions on the MLR instance beyond separation. Indeed, as we argued in the Introduction, and more formally in Appendix A, moment based methods cannot obtain runtime which is sub-exponential in $k$. The work that is closest to ours, and that we build off of, is that of [LL18], which demonstrates an algorithm which runs in $2^{\widetilde{O}(k)}$ for learning a MLR under separation conditions. However, as their warm start algorithm is ultimately moment based, since it interacts through the samples through the moment-based univariate GMM learning algorithm of [MV10], it cannot achieve runtime sub-exponential in $k$.

It is not hard to see that given a uniform MLR instance, if we feed it into an algorithm for list-decodable regression, the list must contain something which is close to each of the regressors in the MLR instance, as each mixture component is an equally valid solution to the list-decodable regression problem. Thus one could hope that these algorithms for list-decodable regression could yield improved algorithms for learning MLRs as well.

Unfortunately, all known techniques, including the state of the art [KKK19, RY19], either are too weak to be applied to our setting, or use the Sum-of-Squares SDP hierarchy and again interact through the data via estimating high-degree moments of the distribution. As a result, these latter algorithms still suffer runtimes which are exponential in $k$.

The mixtures of hyperplanes problem we consider in this paper can be thought of as a special case of the subspace clustering or hyperplane clustering problem, where data is thought of as being drawn from a union of linear subspaces. In our problem, we additionally assume that the data is Gaussian within each subspace. The literature on subspace clusterings is vast and we cannot do it justice here; see [PHL04, Vid11, EV13] and references therein for a more complete treatment. On the one hand, the mixture of hyperplanes problem arises naturally in practical contexts of projective motion segmentation [VH07] and hybrid system identification [Bak11]. On the other, it also corresponds to a challenging setting of the problem due to the low codimensionality of the subspaces. Indeed, essentially all algorithms for subspace clustering with provable guarantees either run in time exponential in the dimension of the subspaces (e.g. RANSAC [FB81], algebraic subspace clustering [VMS05], spectral curvature clustering [LLY+12]) or require the codimension to be at least some small but constant fraction of the ambient dimension [EV13, CSV13, LMZ+12, TV15]. To our knowledge the only work which addresses the codimension 1 case is [TV17], though their setting and guarantees are quite different from ours.

One of our main algorithmic tools will be the univariate (continuous) Fourier transform, as a way to estimate Fourier moments of our distribution. In recent years, the question of learning the Fourier transform of a function has attracted a considerable amount of interest in theoretical computer science [HIKP12, IK14, Moi15, PS15, Kap16, CKPS16, Kap17, NSW19]. Our application is somewhat different in that we have explicit access to the function we will take the Fourier transform of.

In the context of distribution learning, the discrete Fourier transform has been used to learn families of distributions such as sums of independent integer random variables [DKS16b], Poisson Binomial distributions [DKS16c], and Poisson multinomial distributions [DKS16b, DKS16a]. These algorithms typically work by exploiting Fourier sparsity of the underlying distribution. However, the way we use the Fourier transform is quite different: we only use it to compute different statistics of the data, namely, the Fourier moments of our distribution.

Another important algorithmic primitive we use is univariate density estimation and specifically, the piecewise polynomial-based estimators given in [CDSS14, ADLS17]. Univariate density estimation has a long history in statistics, ML, and theoretical computer science, and a full literature review of the field is out of the scope of this paper; see e.g. [Dia16] for a more comprehensive overview of the literature. However, to the best of our knowledge, there are few previous cases where univariate density estimation has been used as a key tool for a high dimensional learning task.

Preliminaries

In this section, we give some basic technical preliminaries.

In this section, we formally define the models we consider throughout this paper, namely, mixtures of linear regression and hyperplanes, and some important parameters for these models:

When $\varsigma=0$, we say that the MLR is noiseless.

We now turn our attention to mixtures of hyperplanes. Formally:

2 Miscellaneous Notation

We will occasionally use notation like $x=[c_{1},c_{2}]\cdot y$ and $x=1\pm\delta$ to mean $c_{1}y\leq x\leq c_{2}y$ and $1-\delta\leq x\leq 1+\delta$ respectively.

We will sometimes refer to a univariate mixture $\mathcal{F}$ of zero-mean Gaussians with mixing weights $p\in\Delta^{k}$ and variances $\sigma^{2}_{1},...,\sigma^{2}_{k}$ as a mixture of $k$ univariate zero-mean Gaussians “with parameters $(\{p_{i}\}_{i\in[k]},\{\sigma_{i}\}_{i\in[k]})$.” We will define $\sigma_{\min}(\mathcal{F})\triangleq\min_{i\in[k]}\sigma_{i}$ and $\sigma_{\max}(\mathcal{F})\triangleq\max_{i\in[k]}\sigma_{i}$ and refer to $\sigma_{\min}(\mathcal{F})^{2}$ and $\sigma_{\max}(\mathcal{F})^{2}$ as the minimum and maximum variance of $\mathcal{F}$, respectively.

Overview of Techniques

We first describe our techniques that achieve Theorem 1.1, before describing how to adapt these techniques to achieve Theorems 1.2 and 1.3.

The main bottleneck in this routine is the univariate learning step. Specifically, the algorithm of [MV10] relies on the method of moments to learn the parameters of the univariate mixture of Gaussians, and as a result, takes $k^{O(k)}$ samples and time. In fact, this is inherent: [MV10] demonstrates that $k^{\Omega(k)}$ samples are necessary to learn the parameters of a mixture of Gaussians, precisely by leveraging moment matching instances.

However, all we need is an estimate of the minimum variance of the mixture of Gaussians. One can first observe that it is possible to estimate the maximum variance of a component in a univariate mixture of Gaussians based on a sufficiently high degree moment. This is because the $p$-th moment of a uniform mixture of Gaussians $\mathcal{F}$ with variances $s_{1}^{2},\ldots,s_{k}^{2}$ has the following form, for $p$ even:

for $\sigma_{\max}(\mathcal{F})\triangleq\max_{i\in[k]}s_{i}$ and some universal constant $c>0$. Therefore, for any $\kappa>0$, if we set $p=\Theta(\log k/\log(1+\kappa))=\Theta(\kappa^{-1}\log k)$, we have that

which yields a $(1+\kappa)$ approximation to the maximum variance approximation to the largest variance of $\mathcal{F}$. Moreover, we can estimate the left-hand side in $p^{O(p)}=2^{\widetilde{O}(\kappa^{-1}\log k)}$ samples:

For clarity of exposition, we defer the proof of this lemma to Section C.1.

Unfortunately, a priori this argument says nothing about estimating the minimum variance. It is easy to see that two mixtures of univariate zero-mean Gaussians $D_{1},D_{2}$ can have very similar $p$-th moments but wildly different minimum variances (e.g. take $D_{1}$ to be a single Gaussian ${\mathcal{N}}(0,k^{100})$, and take $D_{2}$ to be a uniform mixture of ${\mathcal{N}}(0,k^{100})$ and ${\mathcal{N}}(0,1)$).

The key insight is that while higher-degree moments of a mixture $D$ of zero-mean Gaussians tell us nothing about the minimum variance, those of its Fourier transform do. The reason is because of the following observation:

If the components of $D$ have variances $s^{2}_{1},...,s^{2}_{k}$ and mixing weights $p_{1},...,p_{k}$, the Fourier transform of the density of $D$ is a new (unnormalized) mixture of Gaussians with variances $\Theta(s^{-2}_{1}),$ $\cdots,$ $\Theta(s^{-2}_{k})$ and mixing weights proportional to $p_{1}/s_{1},...,p_{k}/s_{1}$ (see Fact 5.2).

In particular, if we have a sufficiently good estimate of the maximum variance of any component in the Fourier transform of $D$, then by inverting this estimate, we can estimate the minimum variance of any component in $D$. So if we had access to the Fourier transform of $D$, we could then use the moments of this distribution to estimate the maximum variance of any component of the Fourier transform, which would allow us to learn the minimum variance of $D$.

What remains is to estimate moments of the Fourier transform of $D$ using solely samples from $D$. Here we use existing primitives for univariate density estimation [CDSS14, ADLS17] to obtain an explicit approximation $\widetilde{D}$ to the density of $D$, after which we can explicitly compute moments of the Fourier transform of $\widetilde{D}$. We defer the technical details of how to argue that its moments are close to those of the Fourier transform of $D$ to Section 6.1, as they are rather involved. In short, this allows us to achieve the same sorts of guarantees for estimating min-variance as for estimating max-variance: for any $\kappa>0$, we can learn the minimum variance of the mixture to multiplicative error $1+O(\kappa)$ with $2^{\widetilde{O}(\kappa^{-1}\log k)}$ samples and time.

and moreover, this is tight. In particular, this says that we would need to take $\kappa=\Omega(1/k)$ in the discussion above, which would result in a $2^{\Theta(k)}$ runtime, which we wish to avoid.

However, we show that with subexponentially large probability, the difference is sufficiently large so that we can detect this difference using subexponentially many samples. In particular, observe that for any constant $0<c<1/2$, if $z$ is a random unit vector in the span of $\{w_{i}-a_{t}\}$, then with probability $\exp(-k^{1-2c})$ we have that

in which case if we define $a^{\prime}_{(t+1)}$ as previously, we get that with probability $\exp(-k^{1-2c})$,

So by trying super-polynomially many random directions $z$ at every step, we ensure with high probability that one of those directions will make $1-\Omega(k^{-2c})$ progress, for some $c<1$. By combining this with our certification procedure as described above, we show that we can make non-trivial progress in the algorithm after only sub-exponentially many samples.

By iteratively applying this update, we are able to obtain an $a_{T}$ so that

in subexponential time. We call this subroutine Fourier moment descent, and it allows us to learn a single regressor to good accuracy. For technical reasons, the complexity of this approach grows as we get closer to $w_{i}$, however, it allows us to obtain a very good “warm start”. In the noiseless case, this can be combined with the boosting procedure from [LL18] to obtain arbitrarily high accuracy.

This technology now allows us to learn a single regressor to very high accuracy. In the noiseless setting, this allows us to “peel off” the samples from this component almost completely, and we can now repeat this process on the sub-mixture with this component removed to learn another component, and iterate to eventually learn all of the regressors.

That said, as we shall see, this is much trickier in the presence of noise.

2 Learning With Regression Noise

What changes when we assume that there is a significant amount of noise $\varsigma$? From the perspective of our Fourier moment descent algorithm, it turns out not much does, at least to a certain extent: in fact, essentially the same argument goes through and allows us to learn a single component to error at most

where $\varsigma$ is the standard deviation of the white noise.

However, learning all components becomes substantially more difficult. In particular, the peeling process no longer works: the fact that there is regression noise does not allow us to perfectly remove the influence of a component that we have learned from the rest of the mixture. As a result, it is no longer clear how to go from an algorithm that can learn a single component to one that can learn all components.

To avoid this, we circumvent the need for peeling altogether. By a delicate analysis, we will show that with decent probability, we can control the dynamics of the Fourier moment descent algorithm, so that it will converge to the regressor that it was initially closest to. This is the key technical ingredient behind getting Fourier moment descent to handle regression noise.

As mentioned previously, in the noiseless setting, the boosting algorithm of [LL18] allows us to bootstrap our warm start, obtained via Fourier moment descent, to arbitrarily high accuracy. It turns out that in the noisy setting, their boosting algorithm also allows one to go slightly below $O(\varsigma)$. Interestingly, motivated again by the connection to Fourier analysis, we demonstrate an improved boosting algorithm that is able to tolerate substantially more noise as well as a much weaker warm start.

The boosting algorithm of [LL18] is based on stochastic gradient descent on a regularized form of gravitational potential, which was notably used in [HPZ18]. While this objective is concave, they demonstrate that in a small neighborhood around the true regressors, SGD updates based on this objective contract in expectation, and hence they make progress.

3 Learning Mixtures of Hyperplanes

As we will see, mixtures of hyperplanes share enough qualitative features with MLRs that an appropriate instantiation of our techniques also suffices for this problem.

then the progress measure contracts. One can show this already suffices to get a $\widetilde{O}(d)\cdot\exp(\widetilde{O}(k))$-time algorithm for learning mixtures of hyperplanes.

To learn all components, we would like to implement some kind of boosting procedure. Our approach here is to regard $\mathcal{D}$ in a certain way as a non-spherical MLR with well-conditioned covariances, at which point we can invoke, e.g., the boosting algorithm of [LL18]. We defer these details to Section 9.4. Once we are able to refine an estimate for a direction of $\mathcal{D}$ to arbitrary precision, we can carry out the “peeling” procedure outlined at the end of Section 3.1 to learn all components.

Roadmap

Here we give a brief overview of the organization of the rest of the paper. In Section 5 we give some additional technical preliminaries we will need in the paper. In Section 6 we present our Fourier moment descent algorithm for learning a single component. In Section 7 we show how to use this to learn all the components, when there is no regression noise. In Section 8 we demonstrate a modification of our algorithm to learn all the components in the presence of regression noise. In Section 9 we demonstrate our subexponential time algorithm for learning a mixture of hyperplanes. Finally, in Section 10 we demonstrate our improved boosting algorithm based on the cosine integral objective. Deferred proofs appear in the Appendix, as well as our moment-matching example.

Additional Technical Preliminaries

In this section we give a number of miscellaneous facts that we will require throughout the paper. For clarity of exposition we defer the proofs of these facts to Appendix C. The first is a monotonicity property of moments of Gaussians, restricted to the tails of the Gaussian:

The following fact about Fourier transforms of Gaussian pdfs is standard.

We will require the following standard estimate for Gaussian tails, see e.g. Proposition 2.1.2 in [Ver18].

We also have the following standard concentration inequality.

Facts 5.3 and 9 imply the following pair of inequalities about the correlation between a Gaussian vector and a given unit vector.

for $\underline{\beta}=f(\underline{\alpha})$ and $\overline{\beta}=f(\overline{\alpha})$.

It will also be useful to obtain a similar bounds for the probability that the inner products of a random vector with two orthogonal directions are simultaneously in a particular range.

For any $\alpha_{1},\alpha_{2}>0$, we have that for sufficiently large $d$,

Finally, we also use the following approximate $k$-SVD algorithm as a black-box:

We next collect some elementary matrix perturbation bounds.

By Lemma 5.8, $\left\lVert(\mathbf{I}_{d}-\mathbf{U}\mathbf{U}^{\top})\widehat{\mathbf{U}}\right\rVert_{2}\leq\epsilon/\lambda$. We can write

Warm Start via Fourier Moment Descent

Here we propose a technique for moment descent based on approximating the minimum variance of a component in a mixture of univariate zero-mean Gaussians. The main result of this section is an algorithm, which we call FourierMomentDescent, for learning a single component of a mixture of $k$ linear regressions in time and sample complexity sub-exponential in $k$:

In Section 2.2 we give an algorithm for estimating the minimum variance of a mixture of univariate, zero-mean Gaussians via its Fourier transform. In Section 6.2 we show how to leverage this technology to obtain our algorithm FourierMomentDescent and then give a proof of Theorem 6.1.

Here we give the key primitive underlying all of the algorithmic results of this work: an algorithm for estimating the minimum variance of a mixture of zero-mean Gaussians. This requires some setup regarding existing technology for density estimation.

Our main density estimation tool will be to use piecewise polynomials. We favor them because there are clean algorithms for density estimation via piecewise polynomials, and moreover, the form of the estimator will be useful for us later on. Formally:

We will use the following algorithm as a black box:

1.2 Minimum Variance Via Fourier Transform Moments

We now show how to use an $L_{2}$-close estimator for the density of a mixture $\mathcal{F}$ of zero-mean univariate Gaussians to approximate $\sigma_{\min}(\mathcal{F})$. As a first step, we show how to use an $L_{2}$-close estimator to estimate high moments of $\mathcal{F}$:

and define $L\triangleq\sum_{i=1}^{k}p_{i}$. Let $\overline{\sigma}>0$ be any number for which $\overline{\sigma}\geq\max_{i\in[k]}\sigma_{i}$.

We would like to pick the truncation threshold $\tau$ so that

For this, it suffices to take $\tau$ for which

where the first step follows from definition of $\mathcal{F}(x)$, the second step follows from Fact 5.1, and the third step follows from Eq. (16).

We conclude that for $\tau=8\overline{\sigma}^{2}\cdot\max\{p,\ln(4L/\xi)\}$, Eq. (17) holds.

We can now complete the proof of (14). We may write $|\mathcal{M}_{p}(\mathcal{F})-\mathcal{M}_{p}(\mathcal{G}^{\prime})|$ as

where the second step follows from triangle inequality, the third step follows by (15) and the last step follows if we take $\eta=\frac{\xi^{2}p}{8\tau^{2p+1}}$. ∎

This is useful as good estimates of high moments of the mixture allow us to approximate the maximum variance of any component well, as components with large variance contribute significantly more to the high moments than do the components with small variance. However, we wish to estimate the minimum variance of our mixture. We now show that we can do so by taking high moments of the Fourier transform of our $L_{2}$-close estimator. As an important subroutine, we show that it is efficient to compute the Fourier moments of our density estimate, by using the fact that it is piecewise polynomial. Specifically:

We defer the description of this algorithm as well as the proof of correctness to Appendix B. With this primitive, we can now show:

Let $\mathcal{F}$ be a mixture of $k$ univariate zero-mean Gaussians with parameters $(\{p_{i}\}_{i\in[k]},\{\sigma_{i}\}_{i\in[k]})$. Let $\overline{\sigma}\geq\sigma_{\max}(\mathcal{F})$, $\underline{\sigma}\leq\sigma_{\min}(\mathcal{F})$. Then with probability at least $1-\delta$, EstimateMinVariance($p,\mathcal{F},\overline{\sigma},\underline{\sigma},\delta$) (Algorithm 2) takes

samples, runs in time $\widetilde{O}(N)$, and outputs a number $\sigma^{*}$ for which

Note that in the pseudocode our choice of $\eta$ is given by

Consequently, the runtime and sample complexity bounds for general $p$ just follow from the fact that these quantities are dominated by the cost of running L2Estimate($\mathcal{F},\underline{\sigma},\eta,\delta$) for $\eta$ as defined in (19). By Corollary 6.4, if we run L2Estimate($\mathcal{F},\underline{\sigma},\eta,\delta$) and produce the piecewise polynomial $\mathcal{G}$, we know that $\left\lVert\mathcal{F}-\mathcal{G}\right\rVert^{2}_{2}\leq\eta$. By Plancherel’s theorem [PL10], this means that $\|\widehat{\mathcal{F}}-\widehat{\mathcal{G}}\|^{2}_{2}\leq\eta$. To apply Lemma 6.5, first note that by Fact 5.2,

So $\widehat{\mathcal{F}}$ is an affine linear combination of Gaussian densities, and its coefficients sum to

where the last step follows by our choice of $L$ in EstimateMinVariance.

So by Lemma 6.5, if we define $\widehat{\mathcal{G}}^{\prime}$ by

If we had $\xi=(2\pi)^{-p-1/2}p^{p/2}\xi^{\prime}$ for some $\xi^{\prime}>0$, then we get by (21) and (6.1.2) that

so $\sigma^{*}\triangleq\left(\frac{\mathcal{M}_{p}(\widehat{\mathcal{G}})}{(2\pi)^{-p-1/2}p^{p/2}}\right)^{-1/(p-1)}$ satisfies (18).

We now identify two specific parameter settings for this algorithm which will be useful later on. First, if we take the degree $p$ to be relatively small, we are able to get a constant approximation to the minimum variance very efficiently:

Let $0<\kappa_{1}<\kappa_{2}\leq 1$, and let $\mathcal{F}_{1}$ and $\mathcal{F}_{2}$ be two mixtures of $k$ univariate zero-mean Gaussians with parameters $(\{p_{i}\},\{\sigma^{(1)}_{i}\})$ and $(\{p_{i}\},\{\sigma^{(2)}_{i}\})$ respectively. Let $\overline{\sigma}\geq\max(\sigma_{\max}(\mathcal{F}_{1}),\sigma_{\max}(\mathcal{F}_{2}))$, $\underline{\sigma}\leq\min(\sigma_{\min}(\mathcal{F}_{1}),\sigma_{\min}(\mathcal{F}_{2}))$. Then, with probability $1-\delta$, the algorithm CompareMinVariances($\mathcal{F}_{1},\mathcal{F}_{2},\overline{\sigma},\underline{\sigma},\kappa_{1},\kappa_{2},\delta$) (Algorithm 3) satisfies:

If $\sigma_{\min}(\mathcal{F}_{1})\geq\left(1+\kappa_{2}\right)\sigma_{\min}(\mathcal{F}_{2})$, then it outputs $\mathsf{true}$.

If $\sigma_{\min}(\mathcal{F}_{1})\leq(1+\kappa_{1})\sigma_{\min}(\mathcal{F}_{2})$, then it outputs $\mathsf{false}$.

samples and runs in time $\widetilde{O}(N)$.

Let $\sigma^{*}_{j}$ be the estimate produced by

Now for the first part of the lemma, by hypothesis $\frac{\sigma_{\min}(\mathcal{F}_{1})}{\sigma_{\min}(\mathcal{F}_{2})}\geq 1+\kappa_{2}$, so by the lower bound in (25) we conclude that

For the second part of the lemma, by hypothesis $\frac{\sigma_{\min}(\mathcal{F}_{1})}{\sigma_{\min}(\mathcal{F}_{2})}\leq 1+\kappa_{1}$, so by the upper bound in (25) we conclude that

The content of this lemma is that the right-hand side of (6.1.2) is strictly greater than the right-hand side of (6.1.2). Indeed, we need to check that

2 Moment Descent

In this section we will show how to obtain a warm start using the CompareMinVariances subroutine of the previous section.

for $(x_{1},y_{1}),...,(x_{N},y_{N})$ i.i.d. samples from $\mathcal{D}$. Notice there is a matrix-vector oracle for $\widehat{\mathbf{M}}^{(N)}_{a}$ which runs in time $O(Nd)$.

Furthermore, for any $\beta,\delta>0$ and

Then $\textsc{ApproxBlockSVD}(\widehat{\mathbf{M}}^{(N)},1/10,\delta/2)$ runs in time $\widetilde{O}\left(k\cdot N\cdot d\right)$ and outputs a matrix $\mathbf{U}$ so that with probability at least $1-\delta$,

We are now ready to analyze the amount of progress each step of moment descent makes.

Then we have that with probability at least $1-\delta$,

There exists at least one $j\in[M]$ for which $\left\lVert w_{i^{*}}-a_{t}-\eta\cdot v_{j}\right\rVert^{2}_{2}\leq\left(1-\frac{1}{5\sqrt{k}}\right)\sigma_{t}^{2}$.

For all $j\in[M]$ and $i\in[k]$, $\left\lVert w_{i}-a_{t}-\eta\cdot v_{j}\right\rVert^{2}_{2}\geq\left(1-\frac{9}{\sqrt{k}}\right)\sigma_{t}^{2}$.

Define $\widetilde{w}_{i}\triangleq\frac{w_{i}-a_{t}}{\left\lVert w_{i}-a_{t}\right\rVert_{2}}$. For every $j\in[M]$, let $A_{j}$ be the event that $\langle v_{j},\widetilde{w}_{i^{*}}\rangle\geq\frac{1}{2}k^{-1/4}$. For every $j\in[M]$ and $i\in[k]$, let $B_{j}[i]$ be the event that $\langle v_{j},\widetilde{w}_{i}\rangle\leq 3k^{-1/4}$. We would like to condition on the event that $\mathcal{E}\triangleq\left(\bigvee_{j\in[M]}A_{j}\right)\wedge\left(\bigwedge_{i\in[k],j\in[M]}B_{j}[i]\right)$.

We first verify that conditioned on $\mathcal{E}$, 1) and 2) of the lemma hold. We get that there is at least one $j\in[M]$ for which

where the first step follows from the fact that we have conditioned on $A_{j}$ and also $\left\lVert w_{i^{*}}-a_{t}\right\rVert_{2}=\sigma_{t}$ by definition, and the third step follows from $\sigma^{*}/\sigma_{t}\in[0.9,1.1]$.

where the first step follows from the fact that we have conditioned on $B_{j}[i]$ and also $\left\lVert w_{i}-a_{t}\right\rVert_{2}\leq\sigma_{t}$ by definition.

Finally, we show that $\Pr[\mathcal{E}]\geq 1-\delta$. For any $j\in[M]$ and $i\in[k]$, by Corollary 5.5, with probability at least $e^{-\sqrt{k}}$ we have that

and $\left\lVert\mathbf{U}g_{j}\right\rVert_{2}=\left\lVert g_{j}\right\rVert_{2}$ by orthonormality of the columns of $\mathbf{U}$, we can rewrite the left-hand side of (32) as

where the inequality follows by the lower bound in (30). So by taking $i=i^{*}$, we conclude that $\Pr[A_{j}]\geq e^{-\sqrt{k}}$. The probability that $\bigvee_{j\in[M]}A_{j}$ does not occur is thus

On the other hand, by the same analysis, this time invoking the second part of Corollary 5.5 and the upper bound in (30), we see that $\Pr[B_{j}[i]]\geq e^{-3\sqrt{k}}$, so the probability that $\bigwedge B_{j}[i]$ does not occur is

So by taking $M=e^{\sqrt{k}}\ln(2/\delta)$ and noting that for this choice of $M$, $kMe^{-3\sqrt{k}}<\delta/2$ because $\delta>e^{-\sqrt{k}}$, we get that $\Pr[\mathcal{E}]\geq 1-\delta$ as claimed. ∎

Let $\sigma_{t}\triangleq\min_{i\in[k]}\left\lVert w_{i}-a_{t}\right\rVert_{2}$. Because $a_{0}=0$, we have that $\sigma_{0}\leq\max_{i\in[k]}\left\lVert w_{i}\right\rVert_{2}\leq 1$.

By a simple union bound, we first upper bound the probability that the steps of moment descent in the $t$-th iteration of the outer loop in FourierMomentDescent all succeed.

Let $i\in[S]$. With probability at least $1-\delta$, the randomized components of the $t$-th iteration of the outer loop in FourierMomentDescent all succeed.

Each $t$-th iteration of the outer loop in FourierMomentDescent (Algorithm 4) has the following randomized components: computing $\widehat{\mathbf{M}}^{(N_{1})}_{a_{t}}$, running EstimateMinVariance (Algorithm 2), trying the Gaussian vectors $g$ in the inner loop over $j\in[M]$, running ApproxBlockSVD, and running CompareMinVariances (Algorithm 3) in this inner loop.

Because the failure probability $\delta^{\prime}$ for the first four of these tasks was chosen to be $\frac{\delta}{5T}$, and the failure probability $\delta^{\prime\prime}$ for the last task was chosen to be $\frac{\delta}{5MT}$, we can bound the overall failure probability by $\delta$. ∎

Call the event in Claim 6.14 $\mathcal{E}$. Next, we show that provided $\mathcal{E}$ occurs, $\sigma_{t}$ can be naively bounded by a constant.

Let $0\leq t<T$ and condition on $\mathcal{E}$. Then $\sigma_{t}\leq 4$.

At the start of the $t$-th step, our initial estimate $a_{t-1}$ is at distance at most 1 from some $w_{i^{*}}$ (this is a very loose bound). After the $t$-th step, the new estimate $a_{t}$ satisfies $\left\lVert w_{i^{**}}-a_{t}\right\rVert_{2}\leq\left\lVert w_{i^{*}}-a_{t-1}\right\rVert_{2}\leq 1$ for some $i^{**}\in[k]$. So we have that $\left\lVert w_{i}-a_{t}\right\rVert_{2}\leq\left\lVert w_{i^{**}}-w_{i}\right\rVert_{2}+\left\lVert w_{i^{**}}-a_{t}\right\rVert_{2}\leq 3$. Recalling that $\sigma^{2}_{t}=\min_{i\in[k]}\left\lVert w_{i}-a_{t}\right\rVert^{2}_{2}+\varsigma^{2}$ and noting that $\varsigma<1$, we conclude that $\overline{\sigma}=4$ is a valid upper bound on the standard deviation of any component of any univariate mixture of Gaussians $\mathcal{F}_{t}$ or $\mathcal{F}^{\prime(j)}_{t}$ encountered during the course of FourierMomentDescent. ∎

Next, we show that provided $\mathcal{E}$ occurs, then we can bound the extent to which every iteration of the outer loop in FourierMomentDescent contracts $\sigma^{2}_{t}$.

Let $0\leq t<T$ and condition on $\mathcal{E}$. Suppose $\varsigma^{2}\leq\frac{1}{5}\left\lVert w_{i}-a_{t}\right\rVert^{2}_{2}$ for any $i\in[k]$. Then

(Completeness) Either $\left\lVert w_{i}-a_{t}\right\rVert_{2}\leq\epsilon$ already, or there exists some $j\in[M]$ for which CompareMinVariances($\mathcal{F}_{t},\mathcal{F}^{\prime(j)}_{t},\overline{\sigma},\underline{\sigma},\kappa,2\kappa,\delta^{\prime\prime}$) outputs $\mathsf{true}$ for $\kappa=\frac{1}{24\sqrt{k}}$.

(Soundness) For any such $j\in[M]$ for which CompareMinVariances outputs $\mathsf{true}$,

We first show completeness. Suppose $\left\lVert w_{i}-a_{t}\right\rVert_{2}\geq\epsilon$ for all $i\in[k]$. By the first part of Lemma 6.12, there exists some $j\in[M]$ for which

where in the last step we used the assumption that $\varsigma^{2}\leq\frac{1}{5}\left\lVert w_{i}-a_{t}\right\rVert^{2}_{2}$ for any $i\in[k]$.

We conclude that $\sigma^{(j)}_{t}\triangleq\min_{i\in[k]}\left\{\varsigma^{2}+\left\lVert w_{i}-a^{\prime(j)}_{t}\right\rVert_{2}\right\}$ satisfies $(\sigma^{(j)}_{t})^{2}\leq\left(1-\frac{1}{6\sqrt{k}}\right)(\sigma_{t})^{2}$, and because $1-\frac{1}{6\sqrt{k}}\leq\left(\frac{1}{1+2\kappa}\right)^{2}$ for $\kappa=\frac{1}{24\sqrt{k}}$, CompareMinVariances($\mathcal{F}_{t},\mathcal{F}^{\prime(j)}_{t},\overline{\sigma},\underline{\sigma},\kappa,2\kappa,\delta^{\prime\prime}$) would return $\mathsf{true}$, completing the proof of completeness.

For soundness, if CompareMinVariances($\mathcal{F}_{t},\mathcal{F}^{\prime(j)}_{t},\overline{\sigma},\underline{\sigma},\kappa,2\kappa,\delta^{\prime\prime}$) returns $\mathsf{true}$ for some $j\in[M]$, by Corollary 6.9 this means

where the second step follows from $\kappa\in(0,1)$, which gives the upper bound in (33).

Finally, for the lower bound in (33), note that the second part of Lemma 6.12 tells us that

We are now ready to complete the proof of Lemma 6.13. Let $\rho=1.1/0.9$ and condition on $\mathcal{E}$.

If there does not exist $0\leq t<T$ for which we have that

then because $\varsigma^{2}\leq\epsilon^{2}/10$, we get that $\left\lVert w_{i}-a_{t}\right\rVert^{2}_{2}\geq\epsilon^{2}/2$. So $\varsigma^{2}\leq\frac{1}{5}\left\lVert w_{i}-a_{t}\right\rVert^{2}_{2}$, and by completeness and soundness in Claim 6.16, $\sigma^{2}_{t}$ has contracted by at least a factor of $(1-1/48\sqrt{k})$ and by at most a factor of $(1-9/\sqrt{k})$ at every step. So if we take $T=\Omega(\sqrt{k}\cdot\ln(1/\epsilon))$, we are guaranteed that

On the other hand, if (36) holds for some $0\leq t<T$, then

so FourierMomentDescent breaks out at Line 14 and correctly outputs $a_{t}$.

Conversely, if FourierMomentDescent breaks out at Line 14 because $\sigma^{*}_{t}\leq 0.99\epsilon$, this implies that

so $\min_{i\in[k]}\left\lVert w_{i}-a_{t}\right\rVert_{2}\leq\epsilon$.

The last thing to check is that $\underline{\sigma}=\epsilon/3$ is always a valid lower bound for any $\sigma_{t}$. If (36) holds for some $t$, $t$ is necessarily the first (and last) $t$ in FourierMomentDescent for which (36) holds because of Line 14. So it must be that

and thus, by the fact that $\sigma_{t}\geq(1-9/\sqrt{k})\sigma_{t-1}\geq 0.99\sigma_{t-1}$, we conclude that $\sigma_{t}>\epsilon/3$ as desired. ∎

Lastly, we calculate the runtime and sample complexity of FourierMomentDescent.

Then FourierMomentDescent (Algorithm 4) requires sample complexity $\widetilde{O}(\sqrt{k}e^{\sqrt{k}}(N_{1}+N))$ and runs in time $\widetilde{O}(\sqrt{k}e^{\sqrt{k}}(dN_{1}+N))$.

We defer the proof of Lemma 6.17 to Appendix C.6.

We can now complete the proof of Theorem 6.1.

Learning All Components Under Zero Noise

In this short section we briefly describe how to use FourierMomentDescent in conjunction with existing techniques for boosting to learn all components in a mixture of linear regressions. We remark that the arguments in this section are fairly standard.

We will make use of the following local convergence result of [LL18].

Given $\delta,\epsilon>0$ and a mixture of spherical linear regressions $\mathcal{D}$ with separation $\Delta$ and zero noise, with probability at least $1-\delta$, LearnWithoutNoise($\mathcal{D},\delta,\epsilon$) (Algorithm 5) returns a list of vectors $\mathcal{L}\triangleq\{\widetilde{w}_{1},...,\widetilde{w}_{k}\}$ for which there is a permutation $\pi:[k]\to[k]$ for which $\left\lVert\widetilde{w}_{i}-w_{\pi(i)}\right\rVert_{2}\leq\epsilon$ for all $i\in[k]$. Furthermore, LearnWithoutNoise requires sample complexity

Learning All Components Under Noise

In this section, we describe how to learn all components under the much more challenging setting where there is regression noise. We show that, at the extra cost of running in time exponential in $1/\Delta^{2}$ in addition to $\sqrt{k}$, there is an algorithm, which we call LearnWithNoise, that can learn mixtures of linear regressions to error $\epsilon$ when $\varsigma=O(\epsilon)$.

Given $\delta,\epsilon>0$ and a mixture of spherical linear regressions $\mathcal{D}$ with regressors $\{w_{1},...,w_{k}\}$, separation $\Delta$, and noise rate $\varsigma=O(\epsilon)$, with probability at least $1-\delta$, LearnWithNoise ($\mathcal{D},\delta,\epsilon$) (Algorithm 5) returns a list of vectors $\mathcal{L}\triangleq\{\widetilde{w}_{1},...,\widetilde{w}_{k}\}$ for which there is a permutation $\pi:[k]\to[k]$ for which $\left\lVert\widetilde{w}_{i}-w_{\pi(i)}\right\rVert_{2}\leq\epsilon$ for all $i\in[k]$. Furthermore, LearnWithNoise requires sample complexity

In Section 8.1 we prove the key technical ingredient behind our proof of Theorem 8.1, Lemma 8.4, which allows us to carefully control the dynamics of Fourier moment descent. In Section 8.2 we describe how to get an initialization which satisfies the hypotheses of Lemma 8.4. In Section 8.3 we give the full specification of LearnWithNoise. In Section 8.4 we prove Theorem 8.1. Finally, in Section 8.5, we briefly describe how to leverage the local convergence result of [KC19] in conjunction with our algorithm to get improved noise tolerance in the setting where the mixing weights are a priori known.

The main result of this section and the primary technical component behind Theorem 8.1 is Lemma 8.4 below. This is a substantially more refined version of Lemma 6.12 in which we control not only the probability we make progress in the $t$-th step of moment descent, but also the probability that the the component $a_{t+1}$ is closest to is the same as the one $a_{t}$ is closest to.

We first introduce some preliminary notation and facts that we will use in the proof of Lemma 8.4.

Let $\sigma^{2}_{t}\triangleq\varsigma^{2}+\min_{i\in[k]}\left\lVert w_{i}-a_{t}\right\rVert_{2}$. Denote the minimizing index $i$ by $i^{*}$.

By Lemma 6.10 and Fact 5.7, with probability $1-\delta^{\prime}$ we can ensure that

Lastly, the following elementary fact will be useful:

The solutions to $x+x^{-1}=2+2\beta^{2}$ are

Then with probability at least $1-\delta$ over the randomness of $g_{1},...,g_{M}$ as well as over the behavior of all runs of CompareMinVariances, the following events hold:

(Progress detected) If $\min_{i\in[k]}\left\lVert w_{i}-a_{t}\right\rVert^{2}_{2}\geq\epsilon^{2}/2$, then

outputs $\mathsf{true}$ for at least one $j\in[M]$.

Let $j^{*}$ be the smallest such $j$, and define

(Make at least some amount of progress) If $\min_{i\in[k]}\left\lVert w_{i}-a_{t}\right\rVert^{2}_{2}\geq\epsilon^{2}/2$, then

(Make at most some amount of progress) Regardless of whether $\min_{i\in[k]}\left\lVert w_{i}-a_{t}\right\rVert^{2}_{2}\leq\epsilon^{2}/2$,

($i^{*}$ remains closest by same margin) If $\min_{i\in[k]}\left\lVert w_{i}-a_{t}\right\rVert^{2}_{2}\geq\epsilon^{2}/2$, then for all $i\neq i^{*}$,

We emphasize that the main content of Lemma 8.4 is part 4.

Henceforth we will say that “CompareMinVariances succeeds and outputs $\mathsf{true}$/$\mathsf{false}$ on direction $v$” to mean that a single run of

is successful (in the language of Corollary 6.9, this happens with probability $1-\delta/3M$) and outputs $\mathsf{true}$/$\mathsf{false}$.

Let $\nu_{A},\nu_{B},\nu_{C}>0$ be absolute constants, and suppose $\nu_{A}<\nu_{B}$. For $i\in[k]$ and $j\in[M]$, define the following events:

Let $A_{j}[i]$ be the event that $\gamma^{(j)}_{i^{*}}\geq\nu_{A}\Delta k^{-1/4}$.

Let $B_{j}[i]$ be the event that $\gamma^{(j)}_{i}\leq\nu_{B}\Delta k^{-1/4}$.

Let $C_{j}$ be the event that $A_{j}[i^{*}]$ occurs and also $\langle v_{j},\text{\textdelta}^{\perp}_{i}\rangle\leq\nu_{C}\Delta^{2}k^{-1/2}\left\lVert\text{\textdelta}^{\perp}_{i}\right\rVert_{2}$ for all $i\neq i^{*}$.

For $j\in[M]$, also let $B_{j}$ denote the event that $B_{j}[i]$ occurs for every $i\in[k]$.

First, we compute the exact distance to $v_{i^{*}}$ after walking along $v_{j}$ and, provided the events $B_{j}[i]$ occur, lower bound the distances to all other components $v_{i}$.

Let $i\in[k],j\in[M]$, and suppose $B_{j}[i]$ occurs. Then

with equality when $i=i^{*}$. Furthermore, when $i\neq i^{*}$ we get from (47) that

The right-hand side of (52), as a function of $\left\lVert\text{\textdelta}_{i^{*}}\right\rVert_{2}$, is decreasing as long as

When $i\neq i^{*}$, we additionally know that $\left\lVert\text{\textdelta}_{i}\right\rVert_{2}\geq\left(1+c\Delta^{2}k^{-1/2}\right)\cdot\left\lVert\text{\textdelta}_{i^{*}}\right\rVert_{2}$. So by the fact that the right-hand side of (52) is decreasing as a function of $\left\lVert\text{\textdelta}_{i^{*}}\right\rVert_{2}$ for $\left\lVert\text{\textdelta}_{i^{*}}\right\rVert_{2}\in(-\infty,\left\lVert\text{\textdelta}_{i}\right\rVert_{2}]$, we get (51). ∎

Using (50) of Claim 51, which is an equality when $i=i^{*}$, we can upper bound the distance to $v_{i^{*}}$ after walking along $v_{j}$, provided events $A_{j}[i^{*}]$ and $B_{j}[i]$ occur.

Let $j\in[M]$, and suppose $A_{j}[i^{*}]$ and $B_{j}[i^{*}]$ occur. Then there is an absolute constant $\underline{\beta}^{\prime}>0$ for which

By (50) which is an equality when $i=i^{*}$,

Next, using (51) of Claim 51, we argue that the only way to make progress towards a different component $i\neq i^{*}$ by an amount comparable to that of Claim 53, is if $A_{j}[i]$ has occurred. In particular, the following claim is the contrapositive of this.

Let $i\neq i^{*}$ and $j\in[M]$, and suppose $B_{j}[i]$ occurs and $A_{j}[i]$ does not occur. Then

Because $A_{j}[i]$ does not occur, $\gamma^{(j)}_{i}<\nu_{A}k^{-1/4}$. So by (51),

Henceforth, let $\kappa_{1}=\left(\underline{\beta}^{\prime}-\frac{3c}{2}\right)\Delta^{2}k^{-1/2}$ and $\kappa_{2}=\left(\underline{\beta}^{\prime}-\frac{c}{2}\right)\Delta^{2}k^{-1/2}$. In Lemma 8.4, we will take $\underline{\beta}\triangleq\underline{\beta}^{\prime}-\frac{3c}{2}$.

Claims 53 and 55 now imply the following about the behavior of CompareMinVariances. The upshot of the following two corollaries is that for any $j\in[M]$, if $B_{j}[i]$ occurs for every $i$ and CompareMinVariances succeeds and outputs $\mathsf{true}$ on direction $v_{j}$, the conditional probability of $A_{j}[i^{*}]$ happening is at least the conditional probability of $A_{j}[i]$ happening for any $i\neq i^{*}$.

Let $j\in[M]$, and suppose $A_{j}[i^{*}]$ and $B_{j}[i^{*}]$ occur. Then CompareMinVariances succeeds and outputs $\mathsf{true}$ on direction $v_{j}$.

By adding $\varsigma^{2}$ to both sides of (53) in Claim 53, we see that

Let $i\neq i^{*}$ and $j\in[M]$, and suppose $B_{j}[i]$ holds and CompareMinVariances succeeds and outputs $\mathsf{true}$ on direction $v_{j}$. Then $A_{j}[i]$ has also occurred.

and $B_{j}[i]$ occurs, then $A_{j}[i]$ occurs. We would like to show that (57) then implies that CompareMinVariances, if it succeeds, outputs $\mathsf{true}$ on direction $v_{j}$. Adding $\varsigma^{2}$ to both sides of this, we conclude that

We also give an upper bound to the amount of progress that any $v_{j}$ could make in any direction $i$, provided $B_{j}[i]$ holds.

Let $i\in[k],j\in[M]$, and suppose $B_{j}[i]$ occurs. Then there is an absolute constant $\overline{\beta}>\underline{\beta}$ for which $\left\lVert\text{\textdelta}_{i}-\eta v_{j}\right\rVert^{2}_{2}\geq\left\lVert\text{\textdelta}_{i^{*}}\right\rVert^{2}_{2}\cdot(1-\overline{\beta}\Delta^{2}k^{-1/2})$.

At this point, we could already use Corollary 8.8 and Claim 8.10, together with straightforward bounds on the probabilities of the events $A_{j}[i^{*}]$ and $B_{j}[i]$ (see Claims 8.12 and 8.13 below) to show that parts 1), 2), and 3) of the lemma hold with the claimed probability. Note that the proofs of these steps do not use (47), so in particular parts 1), 2), and 3) of the lemma hold with the claimed probability without assuming (47).

Let $j\in[M]$ and suppose $C_{j}$ and $B_{j}[i]$ occur for all $i\in[k]$. Then

for all $i\neq i^{*}$. Then by (50), we would conclude that

We now describe the intuition for the remaining argument. (61) is not hard to show when the unit vector $\widehat{\text{\textdelta}_{i}}$ is somewhat far from $\widehat{\text{\textdelta}_{i^{*}}}$, in which case it is reasonable to imagine a sizable cone of directions around $\text{\textdelta}_{i^{*}}$ such that if $v_{j}$ lies in that cone, (61) holds. On the other hand, suppose $\widehat{\text{\textdelta}_{i}}$ is close to $\text{\textdelta}_{i^{*}}$. Then (61) can actually be false. But because their non-normalized counterparts $\text{\textdelta}_{i}$ and $\text{\textdelta}_{i^{*}}$ are assumed to be $\Delta$-separated, $\text{\textdelta}_{i}$ and $\text{\textdelta}_{i^{*}}$ must therefore be nearly collinear, in which case there must exist a gap between $\left\lVert\text{\textdelta}_{i}\right\rVert_{2}$ and $\left\lVert\text{\textdelta}_{i^{*}}\right\rVert_{2}$ that’s even bigger than the one assumed in (47), and furthermore walking in $v_{j}$ cannot reduce this gap to below that of (47) in the next step.

We now proceed with the formal details. First note that

Now if $\langle\widehat{\text{\textdelta}}_{i},\widehat{\text{\textdelta}}_{i^{*}}\rangle\leq 0$, then by event $C_{j}$, $\gamma^{(j)}_{i}\leq\langle\text{\textdelta}^{\perp}_{i},v_{j}\rangle\leq\nu_{C}\Delta^{2}k^{-1/2}\cdot\left\lVert\text{\textdelta}^{\perp}_{i}\right\rVert_{2}<\gamma^{(j)}_{i^{*}}$ and we’d be done. On the other hand, if $\langle\widehat{\text{\textdelta}}_{i},\widehat{\text{\textdelta}}_{i^{*}}\rangle>0$, then we get that

In this case, to show the desired inequality (61), it would suffice to show that

In particular, because event $A_{j}$ holds so that $\gamma^{(j)}_{i^{*}}\geq\nu_{A}\Delta k^{-1/4}$, we just need to show that

After squaring both sides of (65), making the substitution $\left\lVert\text{\textdelta}^{\perp}_{i}\right\rVert^{2}_{2}=1-\left\langle\widehat{\text{\textdelta}}_{i},\widehat{\text{\textdelta}}_{i^{*}}\right\rangle^{2}$, and rearranging, (65) becomes

This is merely a univariate inequality for a quadratic polynomial in $\left\langle\widehat{\text{\textdelta}}_{i},\widehat{\text{\textdelta}}_{i^{*}}\right\rangle$. Let $\nu_{CA}\triangleq\nu_{C}/\nu_{A}$. One can compute the smaller of the two zeros of the left-hand side of (66) and see that the inequality is satisfied provided that $\left\langle\widehat{\text{\textdelta}}_{i},\widehat{\text{\textdelta}}_{i^{*}}\right\rangle$ is at most

for absolute constant $a_{\text{Del}}\triangleq\frac{2\nu^{2}_{CA}}{1+\nu^{2}_{CA}\Delta^{2}k^{-1/2}}$.

It remains to consider the case where $\left\langle\widehat{\text{\textdelta}}_{i},\widehat{\text{\textdelta}}_{i^{*}}\right\rangle\geq 1-a_{\text{Del}}\cdot\Delta^{2}k^{-1/2}$. This is where we use the fact that $\left\lVert\text{\textdelta}_{i}-\text{\textdelta}_{i^{*}}\right\rVert_{2}=\left\lVert w_{i}-w_{i^{*}}\right\rVert_{2}\geq\Delta$ to argue that, even though (66) does not hold and we cannot obtain (61), $\left\lVert\text{\textdelta}_{i^{*}}\right\rVert_{2}$ is so much smaller than $\left\lVert\text{\textdelta}_{i}\right\rVert_{2}$ that, conditioned on the event $B_{j}[i]$ for all $j\in[M]$, $\left\lVert\text{\textdelta}_{i}-\eta v_{j}\right\rVert_{2}$ is far larger than $\left\lVert\text{\textdelta}_{i^{*}}-\eta v_{j}\right\rVert_{2}$ for any $j$.

But because event $C_{j}$ involves $A_{j}[i^{*}]$ happening, we certainly have that $\left\lVert\text{\textdelta}_{i^{*}}\right\rVert_{2}\leq\left\lVert\text{\textdelta}_{i^{*}}-\eta v_{j}\right\rVert^{2}_{2}$, so we are done. ∎

where $g\sim{\mathcal{N}}(0,\mathbf{I}_{k})$ and the last step follows by the second part of Lemma 8.2. The random variable $\left\langle\frac{g}{\left\lVert g\right\rVert_{2}},\frac{\mathbf{U}\text{\textdelta}_{i}}{\left\lVert\mathbf{U}\text{\textdelta}_{i}\right\rVert_{2}}\right\rangle$ is merely the correlation of a random unit vector with a fixed unit vector; call this random variable $X$ (clearly it does not depend on the fixed vector).

We can now lower bound the probabilities of $A_{j}[i^{*}]$ and $B_{j}[i]$.

We next lower bound the probability of event $C_{j}$ relative to that of $A_{j}[i^{*}]$. Equivalently, provided $A_{j}[i^{*}]$ happens, we lower bound the conditional probability that the gap of (47) is preserved. In this proof, we would like to use the fact that $\text{\textdelta}^{\perp}_{i}$ is orthogonal to $\widehat{\text{\textdelta}}_{i^{*}}$ for all $i\neq i^{*}$ to argue that $\langle g\mathbf{U},\text{\textdelta}^{\perp}_{i}\rangle$ and $\langle g\mathbf{U},\text{\textdelta}_{i^{*}}\rangle$ are independent. Again, this is only true if $\mathbf{U}$ is exactly the projector to the span of $\{w_{i}-a_{t}\}$, and we need to argue that it suffices to take $\mathbf{U}$ an approximation to that projector.

By Corollary 5.6, for any absolute constant $a_{\text{perp}}>0$, with probability at least

In particular, if this happens, then by (73) we get that

Next, we would like to show that for any $j\in[M]$, if we condition on the events $B_{j}[i]$ holding for all $i\in[k]$, then the conditional probability of $A_{j}[i]$ is not much more than that of $A_{j}[i^{*}]$. Note that by rotational invariance, these conditional probabilities would be identical if $\mathbf{U}$ were exactly the projector to the span of $\{w_{i}-a_{t}\}$, and here it is straightforward to see that it suffices to take $\mathbf{U}$ a sufficiently good approximation to that projector.

Let $B_{v}$ be the event that $\Pr[\langle\widehat{\text{\textdelta}}_{i},v\rangle]\leq\nu_{B}\Delta k^{-1/4}$ for all $i\in[k]$. Let $\mathsf{detect-progress}_{v}$ be the event that $B_{v}$ occurs and additionally that CompareMinVariances succeeds and outputs $\mathsf{true}$ on direction $v$. Let $\mathsf{gap-preserved}_{v}$ be the event that $B_{v}$ occurs and additionally $\left\lVert\text{\textdelta}_{i}-\eta v\right\rVert_{2}\geq\left(1+c\Delta^{2}k^{-1/2}\right)\cdot\left\lVert\text{\textdelta}_{i^{*}}-\eta v\right\rVert_{2}$ for all $i\neq i^{*}$. Then

For every $i\in[k]$, let $S_{i}$ denote the set of all $v$ for which $B_{v}$ occurs, CompareMinVariances succeeds and outputs $\mathsf{true}$ on direction $v$, and $\left\lVert\text{\textdelta}_{i^{\prime}}-\eta v\right\rVert_{2}\geq\left(1+c\Delta^{2}k^{-1/2}\right)\cdot\left\lVert\text{\textdelta}_{i}-\eta v\right\rVert_{2}$ for all $i^{\prime}\neq i$.