Mixture-of-Experts (MoE) is a widely popular model for ensemble learning and is a basic building block of highly successful modern neural networks as well as a component in Gated Recurrent Units (GRU) and Attention networks. However, present algorithms for learning MoE including the EM algorithm, and gradient descent are known to get stuck in local optima. From a theoretical viewpoint, finding an efficient and provably consistent algorithm to learn the parameters remains a long standing open problem for more than two decades. In this paper, we introduce the first algorithm that learns the true parameters of a MoE model for a wide class of non-linearities with global consistency guarantees. While existing algorithms jointly or iteratively estimate the expert parameters and the gating paramters in the MoE, we propose a novel algorithm that breaks the deadlock and can directly estimate the expert parameters by sensing its echo in a carefully designed cross-moment tensor between the inputs and the output. Once the experts are known, the recovery of gating parameters still requires an EM algorithm; however, we show that the EM algorithm for this simplified problem, unlike the joint EM algorithm, converges to the true parameters. We empirically validate our algorithm on both the synthetic and real data sets in a variety of settings, and show superior performance to standard baselines.
The simplified versions of MoE, M-GLMs, are widely studied in the literature. The key techiques for parameter inference in M-GLMs include EM algorithm, spectral methods, convex relaxations, and their variants. @cite_1 @cite_10 prove convergence of EM for @math -mixtures of linear regressions; in contrast, we handle @math mixtures for a wide class of non-linearities and provide global convergence. @cite_6 construct a @math -order super symmetric tensor containing the regressors as its rank- @math components. However, this approach fails to generalize for MoE. @cite_2 use a similar tensor construction followed by EM to learn the parameters; however, they can only handle linear noiseless mixtures and no gating parameters. In contrast, our algorithms can handle non-linearities and the gating parameters. @cite_9 use a convex objective to learn the regressors for a special setting of @math -mixtures of linear regressions. Similar to earlier approaches, this relaxation too does not generalize to @math .
@cite_9 @cite_1 @cite_6 @cite_2 @cite_10
2964207716 2138967244 1486307571 2550703763
We consider the mixed regression problem with two components, under adversarial and stochastic noise. We give a convex optimization formulation that provably recovers the true solution, and provide upper bounds on the recovery errors for both arbitrary noise and stochastic noise settings. We also give matching minimax lower bounds (up to log factors), showing that under certain assumptions, our algorithm is information-theoretically optimal. Our results represent the first tractable algorithm guaranteeing successful recovery with tight bounds on recovery errors and sample complexity. Mixed linear regression involves the recovery of two (or more) unknown vectors from unlabeled linear measurements; that is, where each sample comes from exactly one of the vectors, but we do not know which one. It is a classic problem, and the natural and empirically most popular approach to its solution has been the EM algorithm. As in other settings, this is prone to bad local minima; however, each iteration is very fast (alternating between guessing labels, and solving with those labels). In this paper we provide a new initialization procedure for EM, based on finding the leading two eigenvectors of an appropriate matrix. We then show that with this, a re-sampled version of the EM algorithm provably converges to the correct vectors, under natural assumptions on the sampling distribution, and with nearly optimal (unimprovable) sample complexity. This provides not only the first characterization of EM's performance, but also much lower sample complexity as compared to both standard (randomly initialized) EM, and other methods for this problem. We consider the problem of learning associative mixtures for classification and regression problems, where the output is modeled as a mixture of conditional distributions, conditioned on the input. In contrast to approaches such as expectation maximization (EM) or variational Bayes, which can get stuck in bad local optima, we present a tensor decomposition method which is guaranteed to correctly recover the parameters. The key insight is to learn score function features of the input, and employ them in a moment-based approach for learning associative mixtures. Specifically, we construct the cross-moment tensor between the label and higher order score functions of the input. We establish that the decomposition of this tensor consistently recovers the components of the associative mixture under some simple non-degeneracy assumptions. Thus, we establish that feature learning is the critical ingredient for consistent estimation of associative mixtures using tensor decomposition approaches. In this paper, we study the mixed linear regression (MLR) problem, where the goal is to recover multiple underlying linear models from their unlabeled linear measurements. We propose a non-convex objective function which we show is locally strongly convex in the neighborhood of the ground truth. We use a tensor method for initialization so that the initial models are in the local strong convexity region. We then employ general convex optimization algorithms to minimize the objective function. To the best of our knowledge, our approach provides first exact recovery guarantees for the MLR problem with @math components. Moreover, our method has near-optimal computational complexity @math as well as near-optimal sample complexity @math for constant @math . Furthermore, we show that our non-convex formulation can be extended to solving the subspace clustering problem as well. In particular, when initialized within a small constant distance to the true subspaces, our method converges to the global optima (and recovers true subspaces) in time linear in the number of points. Furthermore, our empirical results indicate that even with random initialization, our approach converges to the global optima in linear time, providing speed-up of up to two orders of magnitude.