Research map / Learning theory and algorithms / Kernels and regression theory
Unveiling the Cycloid Trajectory of EM Iterations in Mixed Linear Regression
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Derives closed-form Bessel-function expressions for population and finite-sample EM updates for two-component mixed linear regression across all SNR regimes, showing noiseless EM iterates trace a cycloid and converge super-linearly (quadratically in angle).
Problem
Understanding the trajectory and convergence rate of EM iterations for two-component mixed linear regression (2MLR), including the exponent of super-linear convergence and finite-sample statistical error, especially with unbalanced mixing weights.
Approach
Uses modified Bessel function closed forms for EM updates under all SNR regimes; in the noiseless setting derives a recurrence on the sub-optimality angle (tan φ^t = tan φ^{t-1} + φ^{t-1}(tan²φ^{t-1}+1)) showing iterates lie on a cycloid, giving a trajectory-based convergence analysis.
Key results
- Population EM iterates in the noiseless setting lie on a cycloid with parameter ||theta*||/pi, verified numerically for d=2,3,50 at SNR=1e8.
- Quadratic (super-linear) convergence of the sub-optimality angle: tan phi^t >= golden ratio times tan phi^{t-1}, and quadratic once phi >= arctan 1.5, extending the quadratic region from 1/10 to about 0.22.
- Finite-sample statistical error bound O(sqrt(d/n) v log(1/delta)/n v sqrt(log(1/delta)/n)) with probability 1 - T delta, improving on prior O(sqrt(d/n) log(n/delta)).
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Vary the true mixing weights | EM regression-parameter updates in 2MLR · 2MLR, noiseless and high SNR | regression parameter ℓ2 error | No clear effect |
| Use the trajectory-based analysis of population EM in the noiseless setting | 2MLR population EM · 2MLR, noiseless population | regression parameter convergence rate: extends the region of quadratic convergence from 1/10 to ... ≈ 0.22 | Helped |
| Use Easy EM for initialization, then standard EM | Finite-sample EM for 2MLR · 2MLR, noiseless finite-sample | regression parameter error: \mathcal{O} ( \sqrt{\frac{d}{n}} \vee \frac{\log\frac{1}{\delta}}{n} \vee \sqrt{\frac{\log \frac{1}{\delta}}{n}} ) \less | Helped |
Surprising findings
- With phi^0 = 0 the update may converge to saddle points rather than global optima.
- The regression-parameter EM update is independent of the true mixing weights in the noiseless setting, while the mixing-weight error depends on the angle.
Limitations
- Main results restricted to the noiseless (SNR to infinity) setting; finite-SNR cycloid not established.
- Finite-sample results require d/n bounded below 1 and the initialization to exceed a statistical-error threshold.
- Experiments are small synthetic simulations only.
Experimental setup
Datasets: synthetic Gaussian covariates (d=2,3,50)
Benchmarks: synthetic 2MLR simulations
Metrics: cosine/angle to true parameter l2 estimation error l1 mixing-weight error convergence slope of pi/2(tan phi - pi/4)
Baselines: Alternating Minimization (AM) for 2MLR standard EM for 2MLR
Builds on: EM algorithm Alternating Minimization for 2MLR Gordon state evolution
Closest papers by meaning
- Agnostic Learning of Mixed Linear Regressions with EM and AM Algorithms (ICML 2024 · similarity 0.88)
- On the Global Convergence of (Fast) Incremental Expectation Maximization Methods (NeurIPS 2019 · similarity 0.87)
- MixLasso: Generalized Mixed Regression via Convex Atomic-Norm Regularization (NeurIPS 2018 · similarity 0.86)
- Toward Global Convergence of Gradient EM for Over-Paramterized Gaussian Mixture Models (NeurIPS 2024 · similarity 0.85)
- Convergence of Online Learning Algorithm for a Mixture of Multiple Linear Regressions (ICML 2024 · similarity 0.83)
- Big Learning Expectation Maximization (AAAI 2024 · similarity 0.83)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.