Research map / Learning theory and algorithms / Matrix and tensor methods

Convergence of Online Learning Algorithm for a Mixture of Multiple Linear Regressions

ICML 2024 · Learning theory and algorithms › Matrix and tensor methods · approach: Nonconvex low-rank and sparse optimization

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.

Proposes an online projected-EM algorithm for mixed linear regression with arbitrary mixing weights and proves almost-sure convergence (via Ljung's ODE method) without i.i.d. regressors, plus a convergence rate and clustering guarantees.

Problem

Parameter estimation and online clustering for mixed linear regression with multiple sub-models and unknown, unequal mixing weights, when the streaming regressors are non-i.i.d.

Approach

An online EM-style recursive algorithm (recursive least squares weighted by posterior responsibilities, with projection onto initialization regions) whose convergence is analyzed with Ljung's ODE method and a Lyapunov function under only asymptotically stationary and ergodic regressors, rather than i.i.d. Gaussian inputs.

Key results

• Simulation with 3 sub-models and non-i.i.d. AR(1) regressors shows estimation error and within-cluster error converging over about 2000-3000 iterations.
• Theorem 3.1: almost sure convergence of the online projected-EM estimates to the true parameters and mixing weights without the i.i.d. regressor assumption.
• Theorem 3.8: almost sure convergence rate O(k^(-1/2+eta)) for parameter and weight estimation errors; Theorem 3.9: clustering correctness bound and within-cluster error at most sigma^2.

Limitations

• Convergence is local, relying on a good initialization region obtained by a tensor method.
• Requires asymptotically stationary and ergodic regressors, and Gaussian noise; global convergence not established.
• Tensor-based initialization under the non-i.i.d. assumption is left to future work.

Experimental setup

Datasets: synthetic MLR data from a linear dynamical regressor system

Benchmarks: synthetic MLR simulation

Metrics: estimation error ||beta_k - beta*|| within-cluster error

Baselines: robust tensor method

Builds on: EM algorithm Ljung's ODE method population EM for mixed linear regression recursive least squares

Closest papers by meaning

• A Wasserstein Minimax Framework for Mixed Linear Regression (ICML 2021 · similarity 0.86)
• A Short and Unified Convergence Analysis of the SAG, SAGA, and IAG Algorithms (ICML 2026 · similarity 0.84)
• Unveiling the Cycloid Trajectory of EM Iterations in Mixed Linear Regression (ICML 2024 · similarity 0.83)
• Toward Global Convergence of Gradient EM for Over-Paramterized Gaussian Mixture Models (NeurIPS 2024 · similarity 0.83)
• Mixture of Experts Provably Detect and Learn the Latent Cluster Structure in Gradient-Based Learning (ICML 2025 · similarity 0.82)
• On the Convergence of Loss and Uncertainty-based Active Learning Algorithms (NeurIPS 2024 · similarity 0.82)