# Max-affine regression via first-order methods

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

## Key facts

- Cited by 3 papers in the map (data through 14 Oct 2026).
- Builds on 25 of its 55 references that are in the map.
- First posted on arXiv 15 Aug 2023.

## Builds on (most cited first, 25 of 25)

- [Model-Agnostic Meta-Learning for Fast Adaptation of Deep Networks](https://mlsanity.com/paper/1703.03400/) (2017)
- [Advances and Open Problems in Federated Learning](https://mlsanity.com/paper/1912.04977/) (2019)
- [Convex optimization](https://mlsanity.com/paper/2106.01946/) (2021)
- [Optimization Methods for Large-Scale Machine Learning](https://mlsanity.com/paper/1606.04838/) (2016)
- [How to Escape Saddle Points Efficiently](https://mlsanity.com/paper/1703.00887/) (2017)
- [The Power of Interpolation: Understanding the Effectiveness of SGD in Modern Over-parametrized Learning](https://mlsanity.com/paper/1712.06559/) (2017)
- [Stochastic Gradient Descent, Weighted Sampling, and the Randomized Kaczmarz algorithm](https://mlsanity.com/paper/1310.5715/) (2013)
- [Dynamics of stochastic gradient descent for two-layer neural networks in the teacher-student setup](https://mlsanity.com/paper/1906.08632/) (2019)
- [Tight Analyses for Non-Smooth Stochastic Gradient Descent](https://mlsanity.com/paper/1812.05217/) (2018)
- [Recovery Guarantees for One-hidden-layer Neural Networks](https://mlsanity.com/paper/1706.03175/) (2017)
- [Escaping Saddles with Stochastic Gradients](https://mlsanity.com/paper/1803.05999/) (2018)
- [Learning ReLUs via Gradient Descent](https://mlsanity.com/paper/1705.04591/) (2017)
- [Learning One-hidden-layer ReLU Networks via Gradient Descent](https://mlsanity.com/paper/1806.07808/) (2018)
- [Learning a Single Neuron with Gradient Methods](https://mlsanity.com/paper/2001.05205/) (2020)
- [Online Stochastic Gradient Descent with Arbitrary Initialization Solves Non-smooth, Non-convex Phase Retrieval](https://mlsanity.com/paper/1910.12837/) (2019)
- [Learning Simple Auctions](https://mlsanity.com/paper/1604.03171/) (2016)
- [Learning a Single Neuron with Bias Using Gradient Descent](https://mlsanity.com/paper/2106.01101/) (2021)
- [Phase Retrieval via Randomized Kaczmarz: Theoretical Guarantees](https://mlsanity.com/paper/1706.09993/) (2017)
- [Max-Affine Regression: Provable, Tractable, and Near-Optimal Statistical Estimation](https://mlsanity.com/paper/1906.09255/) (2019)
- [Sharp Rate of Convergence for Deep Neural Network Classifiers under the Teacher-Student Setting](https://mlsanity.com/paper/2001.06892/) (2020)
- [Fitting ReLUs via SGD and Quantized SGD](https://mlsanity.com/paper/1901.06587/) (2019)
- [Optimality of Maximum Likelihood for Log-Concave Density Estimation and Bounded Convex Regression](https://mlsanity.com/paper/1903.05315/) (2019)
- [Faster Algorithms for Learning Convex Functions](https://mlsanity.com/paper/2111.01348/) (2021)
- [Learning to Approximate a Bregman Divergence](https://mlsanity.com/paper/1905.11545/) (2019)
- [Optimal Bounds on the VC-dimension](https://mlsanity.com/paper/1807.07924/) (2018)

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

- [Input Convex Kolmogorov Arnold Networks](https://mlsanity.com/paper/2505.21208/) (2025)
- [Locally Near Optimal Piecewise Linear Regression in High Dimensions via Difference of Max-Affine Functions](https://mlsanity.com/paper/2605.06959/) (2026)
- [Structure-Preserving Reconstruction of Convex Lipschitz Functionals on Hilbert Spaces from Finite Samples](https://mlsanity.com/paper/2605.08559/) (2026)

## Abstract (arXiv)

We consider regression of a max-affine model that produces a piecewise linear model by combining affine models via the max function. The max-affine model ubiquitously arises in applications in signal processing and statistics including multiclass classification, auction problems, and convex regression. It also generalizes phase retrieval and learning rectifier linear unit activation functions. We present a non-asymptotic convergence analysis of gradient descent (GD) and mini-batch stochastic gradient descent (SGD) for max-affine regression when the model is observed at random locations following the sub-Gaussianity and an anti-concentration with additive sub-Gaussian noise. Under these assumptions, a suitably initialized GD and SGD converge linearly to a neighborhood of the ground truth specified by the corresponding error bound. We provide numerical results that corroborate the theoretical finding. Importantly, SGD not only converges faster in run time with fewer observations than alternating minimization and GD in the noiseless scenario but also outperforms them in low-sample scenarios with noise.