# Max-Affine Regression: Provable, Tractable, and Near-Optimal Statistical Estimation

arXiv: https://arxiv.org/abs/1906.09255 · HTML: https://mlsanity.com/paper/1906.09255/

## Key facts

- Cited by 15 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 21 Jun 2019.

## Built on by (most cited first, 15 of 15)

- [Sharp global convergence guarantees for iterative nonconvex optimization: A Gaussian process perspective](https://mlsanity.com/paper/2109.09859/) (2021)
- [On Learning Mixture of Linear Regressions in the Non-Realizable Setting](https://mlsanity.com/paper/2205.13166/) (2022)
- [Model Selection for Generic Contextual Bandits](https://mlsanity.com/paper/2107.03455/) (2021)
- [What Makes A Good Fisherman? Linear Regression under Self-Selection Bias](https://mlsanity.com/paper/2205.03246/) (2022)
- [On Solution Functions of Optimization: Universal Approximation and Covering Number Bounds](https://mlsanity.com/paper/2212.01314/) (2022)
- [Faster Algorithms for Learning Convex Functions](https://mlsanity.com/paper/2111.01348/) (2021)
- [Input Convex Kolmogorov Arnold Networks](https://mlsanity.com/paper/2505.21208/) (2025)
- [On the Minimal Error of Empirical Risk Minimization](https://mlsanity.com/paper/2102.12066/) (2021)
- [Max-affine regression via first-order methods](https://mlsanity.com/paper/2308.08070/) (2023)
- [Max-Linear Regression by Convex Programming](https://mlsanity.com/paper/2103.07020/) (2021)
- [Model Selection for Generic Reinforcement Learning](https://mlsanity.com/paper/2107.05849/) (2021)
- [Model Selection in Reinforcement Learning with General Function Approximations](https://mlsanity.com/paper/2207.02992/) (2022)
- [Agnostic Learning of Mixed Linear Regressions with EM and AM Algorithms](https://mlsanity.com/paper/2406.01149/) (2024)
- [Expectation Maximization (EM) Converges for General Agnostic Mixtures](https://mlsanity.com/paper/2604.05842/) (2026)
- [Locally Near Optimal Piecewise Linear Regression in High Dimensions via Difference of Max-Affine Functions](https://mlsanity.com/paper/2605.06959/) (2026)

## Abstract (arXiv)

Max-affine regression refers to a model where the unknown regression function is modeled as a maximum of k unknown affine functions for a fixed k ≥ 1. This generalizes linear regression and (real) phase retrieval, and is closely related to convex regression. Working within a non-asymptotic framework, we study this problem in the high-dimensional setting assuming that k is a fixed constant, and focus on estimation of the unknown coefficients of the affine functions underlying the model. We analyze a natural alternating minimization (AM) algorithm for the non-convex least squares objective when the design is random. We show that the AM algorithm, when initialized suitably, converges with high probability and at a geometric rate to a small ball around the optimal coefficients. In order to initialize the algorithm, we propose and analyze a combination of a spectral method and a random search scheme in a low-dimensional space, which may be of independent interest. The final rate that we obtain is near-parametric and minimax optimal (up to a poly-logarithmic factor) as a function of the dimension, sample size, and noise variance. In that sense, our approach should be viewed as a direct and implementable method of enforcing regularization to alleviate the curse of dimensionality in problems of the convex regression type. As a by-product of our analysis, we also obtain guarantees on a classical algorithm for the phase retrieval problem under considerably weaker assumptions on the design distribution than was previously known. Numerical experiments illustrate the sharpness of our bounds in the various problem parameters.