We develop a new approach to learn the parameters of regression models with hidden variables. In a nutshell, we estimate the gradient of the regression function at a set of random points, and cluster the estimated gradients. The centers of the clusters are used as estimates for the parameters of hidden units. We justify this approach by studying a toy model, whereby the regression function is a linear combination of sigmoids. We prove that indeed the estimated gradients concentrate around the parameter vectors of the hidden units, and provide non-asymptotic bounds on the number of required samples. To the best of our knowledge, no comparable guarantees have been proven for linear combinations of sigmoids.
Typical approaches to learning mixtures, like EM come with no guarantees, and suffer from convergence to local minima. Providing guarantees for even the idealized case of learning mixtures of Gaussians is non-trivial, and has been the subject of several recent studies . There are relatively few rigorous results that guarantee learning for regression models with latent variables. @cite_3 consider mixtures of linear regressions. In this setting, they show that regressing the response from second and third order tensors of the covariates yields coefficients, also higher order tensors, whose decomposition reveals the model parameters. A different approach, relying only on the second-order tensor (i.e., the covariance) and alternating minimization is followed by @cite_7 , for a mixture composed of two linear models in the absence of noise; the same setting, in the presence of noise, is studied by @cite_10 . None of these approaches can be applied to our model: our components are non-linear (sigmoids), while the above works focus on linear components; moreover, both @cite_7 and @cite_10 limit their analysis to @math hidden units.
@cite_10 @cite_7 @cite_3
2964207716 2949960673 2953030775
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. Discriminative latent-variable models are typically learned using EM or gradient-based optimization, which suffer from local optima. In this paper, we develop a new computationally efficient and provably consistent estimator for a mixture of linear regressions, a simple instance of a discriminative latent-variable model. Our approach relies on a low-rank linear regression to recover a symmetric tensor, which can be factorized into the parameters using a tensor power method. We prove rates of convergence for our estimator and provide an empirical evaluation illustrating its strengths relative to local optimization (EM).