Research map / Learning theory and algorithms / Sample complexity
Agnostic Learning of Mixed Linear Regressions with EM and AM Algorithms
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.
Shows that gradient AM (min-loss) and gradient EM (soft-min loss) converge to population loss minimizers for agnostic mixed linear regression, with dimension-independent O(1) initialization under separation and misspecification conditions.
Problem
Agnostic learning of mixed linear regression without a generative model: find k linear predictors minimizing a population min-loss or soft-min loss, with EM/AM-type iterations that need good initialization and rigorous convergence guarantees.
Approach
Analyzes gradient AM (min-loss, with fresh sample splitting each iteration) and gradient EM (soft-min loss, soft-min probability weights) in the agnostic setting using restricted-Gaussian covariate properties, obtaining dimension-independent Theta(1) initialization versus the prior O(1/sqrt(d)) requirement.
Key results
- Gradient AM contracts parameter error by factor (1 - c*gamma*pi_min^3) per iteration plus an error floor, with sample complexity n' >= C d log(1/pi_min)/pi_min^3.
- Gradient EM converges with rate rho = 1 - 2 gamma c (1-eta) pi_min^3 under initialization c_ini below a misspecification-dependent threshold, with no separation requirement beyond the EM conditions.
- Initialization needed is Theta(1), improving on the O(1/sqrt(d)) radius of prior agnostic gradient AM analysis.
Limitations
- Analysis assumes standard Gaussian covariates; sample splitting across iterations is used and is not desirable.
- Sample complexity is suboptimal in k (1/pi_min^3 dependence).
- Gradient AM requires separation Delta exceeding lambda plus a term growing with sqrt(log k).
Experimental setup
Metrics: parameter estimation error convergence rate
Baselines: gradient AM with O(1/sqrt(d)) initialization (prior agnostic work)
Builds on: alternating minimization for mixed linear regression EM for mixed linear regression restricted Gaussian analysis
Closest papers by meaning
- Unveiling the Cycloid Trajectory of EM Iterations in Mixed Linear Regression (ICML 2024 · similarity 0.88)
- Is $\sqrt{d}$ Separation Necessary for Gradient EM to Learn Gaussian Mixtures in High Dimensions? (NeurIPS 2026 · similarity 0.84)
- Linear Regression using Heterogeneous Data Batches (NeurIPS 2024 · similarity 0.84)
- Toward Global Convergence of Gradient EM for Over-Paramterized Gaussian Mixture Models (NeurIPS 2024 · similarity 0.83)
- Sample-Efficient Linear Representation Learning from Non-IID Non-Isotropic Data (ICLR 2024 · similarity 0.83)
- Revisiting Agnostic Boosting (NeurIPS 2025 · 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.