Unveiling the Cycloid Trajectory of EM Iterations in Mixed Linear Regression

• URL: http://arxiv.org/abs/2405.18237v2
• Date: Tue, 4 Jun 2024 00:56:22 GMT
• Title: Unveiling the Cycloid Trajectory of EM Iterations in Mixed Linear Regression
• Authors: Zhankun Luo, Abolfazl Hashemi,
• Abstract summary: We study the trajectory of iterations and the convergence rates of the Expectation-Maximization (EM) algorithm for two-component Mixed Linear Regression (2MLR) Recent results have established the super-linear convergence of EM for 2MLR in the noiseless and high SNR settings.
• Score: 5.883916678819683
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: We study the trajectory of iterations and the convergence rates of the Expectation-Maximization (EM) algorithm for two-component Mixed Linear Regression (2MLR). The fundamental goal of MLR is to learn the regression models from unlabeled observations. The EM algorithm finds extensive applications in solving the mixture of linear regressions. Recent results have established the super-linear convergence of EM for 2MLR in the noiseless and high SNR settings under some assumptions and its global convergence rate with random initialization has been affirmed. However, the exponent of convergence has not been theoretically estimated and the geometric properties of the trajectory of EM iterations are not well-understood. In this paper, first, using Bessel functions we provide explicit closed-form expressions for the EM updates under all SNR regimes. Then, in the noiseless setting, we completely characterize the behavior of EM iterations by deriving a recurrence relation at the population level and notably show that all the iterations lie on a certain cycloid. Based on this new trajectory-based analysis, we exhibit the theoretical estimate for the exponent of super-linear convergence and further improve the statistical error bound at the finite-sample level. Our analysis provides a new framework for studying the behavior of EM for Mixed Linear Regression.

Related papers

• Max-affine regression via first-order methods [7.12511675782289]
  The max-affine model ubiquitously arises in applications in signal processing and statistics. We present a non-asymptotic convergence analysis of gradient descent (GD) and mini-batch gradient descent (SGD) for max-affine regression.
  arXiv  Detail & Related papers  (2023-08-15T23:46:44Z)
• Mixed Regression via Approximate Message Passing [16.91276351457051]
  We study the problem of regression in a generalized linear model (GLM) with multiple signals and latent variables. In mixed linear regression, each observation comes from one of $L$ signal vectors (regressors), but we do not know which one. In max-affine regression, each observation comes from the maximum of $L$ affine functions, each defined via a different signal vector.
  arXiv  Detail & Related papers  (2023-04-05T04:59:59Z)
• Sharp analysis of EM for learning mixtures of pairwise differences [14.01151780845689]
  We consider a symmetric mixture of linear regressions with random samples from the pairwise comparison design. We establish that the sequence converges linearly, providing an $ell_infty$-norm guarantee on the estimation error of the iterates. We show that the limit of the EM sequence achieves the sharp rate of estimation in the $ell$-norm, matching the information-theoretically optimal constant.
  arXiv  Detail & Related papers  (2023-02-20T16:13:19Z)
• Stochastic Mirror Descent for Large-Scale Sparse Recovery [13.500750042707407]
  We discuss an application of quadratic Approximation to statistical estimation of high-dimensional sparse parameters. We show that the proposed algorithm attains the optimal convergence of the estimation error under weak assumptions on the regressor distribution.
  arXiv  Detail & Related papers  (2022-10-23T23:23:23Z)
• Nonconvex Stochastic Scaled-Gradient Descent and Generalized Eigenvector Problems [98.34292831923335]
  Motivated by the problem of online correlation analysis, we propose the emphStochastic Scaled-Gradient Descent (SSD) algorithm. We bring these ideas together in an application to online correlation analysis, deriving for the first time an optimal one-time-scale algorithm with an explicit rate of local convergence to normality.
  arXiv  Detail & Related papers  (2021-12-29T18:46:52Z)
• On the Double Descent of Random Features Models Trained with SGD [78.0918823643911]
  We study properties of random features (RF) regression in high dimensions optimized by gradient descent (SGD) We derive precise non-asymptotic error bounds of RF regression under both constant and adaptive step-size SGD setting. We observe the double descent phenomenon both theoretically and empirically.
  arXiv  Detail & Related papers  (2021-10-13T17:47:39Z)
• On the Convergence of Stochastic Extragradient for Bilinear Games with Restarted Iteration Averaging [96.13485146617322]
  We present an analysis of the ExtraGradient (SEG) method with constant step size, and present variations of the method that yield favorable convergence. We prove that when augmented with averaging, SEG provably converges to the Nash equilibrium, and such a rate is provably accelerated by incorporating a scheduled restarting procedure.
  arXiv  Detail & Related papers  (2021-06-30T17:51:36Z)
• A Wasserstein Minimax Framework for Mixed Linear Regression [69.40394595795544]
  Multi-modal distributions are commonly used to model clustered data in learning tasks. We propose an optimal transport-based framework for Mixed Linear Regression problems.
  arXiv  Detail & Related papers  (2021-06-14T16:03:51Z)
• Benign Overfitting of Constant-Stepsize SGD for Linear Regression [122.70478935214128]
  inductive biases are central in preventing overfitting empirically. This work considers this issue in arguably the most basic setting: constant-stepsize SGD for linear regression. We reflect on a number of notable differences between the algorithmic regularization afforded by (unregularized) SGD in comparison to ordinary least squares.
  arXiv  Detail & Related papers  (2021-03-23T17:15:53Z)
• Estimation, Confidence Intervals, and Large-Scale Hypotheses Testing for High-Dimensional Mixed Linear Regression [9.815103550891463]
  This paper studies the high-dimensional mixed linear regression (MLR) where the output variable comes from one of the two linear regression models with an unknown mixing proportion. We propose an iterative procedure for estimating the two regression vectors and establish their rates of convergence. A large-scale multiple testing procedure is proposed for testing the regression coefficients and is shown to control the false discovery rate (FDR) algorithmally.
  arXiv  Detail & Related papers  (2020-11-06T21:17:41Z)
• Estimation of Switched Markov Polynomial NARX models [75.91002178647165]
  We identify a class of models for hybrid dynamical systems characterized by nonlinear autoregressive (NARX) components. The proposed approach is demonstrated on a SMNARX problem composed by three nonlinear sub-models with specific regressors.
  arXiv  Detail & Related papers  (2020-09-29T15:00:47Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.