mlsanityData to 7 Oct 2026

Max-affine regression via first-order methods

arXiv 2308.08070 ↗First posted 15 Aug 2023stat.ML cs.IT cs.LGcited by 3

Not on the map. Why?

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.

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

Builds on

25 of 55 references.

References · 25

  1. 2017Model-Agnostic Meta-Learning for Fast Adaptation of Deep Networkscited by 4,861
  2. 2019Advances and Open Problems in Federated Learningcited by 3,021
  3. 2021Convex optimizationcited by 2,479
  4. 2016Optimization Methods for Large-Scale Machine Learningcited by 1,140
  5. 2017How to Escape Saddle Points Efficientlycited by 284
  6. 2017The Power of Interpolation: Understanding the Effectiveness of SGD in Modern Over-parametrized Learningcited by 150
  7. 2013Stochastic Gradient Descent, Weighted Sampling, and the Randomized Kaczmarz algorithmcited by 132
  8. 2019Dynamics of stochastic gradient descent for two-layer neural networks in the teacher-student setupcited by 112
  9. 2017Recovery Guarantees for One-hidden-layer Neural Networkscited by 94
  10. 2018Tight Analyses for Non-Smooth Stochastic Gradient Descentcited by 94
  11. 2018Escaping Saddles with Stochastic Gradientscited by 66
  12. 2017Learning ReLUs via Gradient Descentcited by 54
13 more
  1. 2018Learning One-hidden-layer ReLU Networks via Gradient Descentcited by 50
  2. 2020Learning a Single Neuron with Gradient Methodscited by 50
  3. 2019Online Stochastic Gradient Descent with Arbitrary Initialization Solves Non-smooth, Non-convex Phase Retrievalcited by 34
  4. 2016Learning Simple Auctionscited by 23
  5. 2021Learning a Single Neuron with Bias Using Gradient Descentcited by 17
  6. 2017Phase Retrieval via Randomized Kaczmarz: Theoretical Guaranteescited by 15
  7. 2019Max-Affine Regression: Provable, Tractable, and Near-Optimal Statistical Estimationcited by 15
  8. 2020Sharp Rate of Convergence for Deep Neural Network Classifiers under the Teacher-Student Settingcited by 11
  9. 2019Fitting ReLUs via SGD and Quantized SGDcited by 10
  10. 2019Optimality of Maximum Likelihood for Log-Concave Density Estimation and Bounded Convex Regressioncited by 10
  11. 2021Faster Algorithms for Learning Convex Functionscited by 5
  12. 2019Learning to Approximate a Bregman Divergencecited by 3
  13. 2018Optimal Bounds on the VC-dimensioncited by 2

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2025: 1; 2026: 2.

3 papers.

  1. 2025Input Convex Kolmogorov Arnold Networkscited by 4
  2. 2026Locally Near Optimal Piecewise Linear Regression in High Dimensions via Difference of Max-Affine Functionscited by 0
  3. 2026Structure-Preserving Reconstruction of Convex Lipschitz Functionals on Hilbert Spaces from Finite Samplescited by 0