mlsanityData to 14 Oct 2026

Locally Near Optimal Piecewise Linear Regression in High Dimensions via Difference of Max-Affine Functions

arXiv 2605.06959 ↗First posted 7 May 2026stat.ML cs.LG math.STcited by 0

Not on the map. Why?

Abstract (arXiv)

This paper presents a parametric solution to piecewise linear regression through the Adaptive Block Gradient Descent (ABGD) algorithm. The heart of the method is the parametrization of piecewise linear functions as the difference of max-affine (DoMA) functions. A non-asymptotic local convergence analysis for ABGD is provided under sub-Gaussian covariate and noise distributions. To initialize ABGD, we adapt a prior algorithm originally developed for the simpler setting of max-affine functions. When suitably initialized, ABGD converges linearly to an ε-accurate estimate given tildeO(dmax(σz/ε,1)2) observations where σz2 denotes the noise variance. This implies exact recovery given tildeO(d) samples in the noiseless case. Also, such a rate is shown to be minimax optimal up to logarithmic factors. Synthetic numerical results corroborate the theoretical guarantees for ABGD. We also observe competitive performance compared to the state-of-the-art methods on real-world datasets.

Key facts. No citing papers in the map yet (data through 14 Oct 2026). Builds on 15 of its 33 references that are in the map. First posted on arXiv 7 May 2026.

Builds on

15 of 33 references.

References · 15

  1. 2017Convergence Analysis of Two-layer Neural Networks with ReLU Activationcited by 137
  2. 2014Phase Retrieval via Wirtinger Flow: Theory and Algorithmscited by 125
  3. 2018Tropical Geometry of Deep Neural Networkscited by 95
  4. 2023On Learning Gaussian Multi-index Models with Gradient Flowcited by 57
  5. 2023Training Neural Networks is NP-Hard in Fixed Dimensioncited by 23
  6. 2018A comparison of deep networks with ReLU activation function and linear spline-type methodscited by 18
  7. 2017Phase Retrieval via Randomized Kaczmarz: Theoretical Guaranteescited by 15
  8. 2019Max-Affine Regression: Provable, Tractable, and Near-Optimal Statistical Estimationcited by 15
  9. 2020Piecewise Linear Regression via a Difference of Convex Functionscited by 14
  10. 2018A convex formulation for high-dimensional sparse sliced inverse regressioncited by 5
  11. 2021Faster Algorithms for Learning Convex Functionscited by 5
  12. 2023Max-affine regression via first-order methodscited by 3
3 more
  1. 2018Optimal Bounds on the VC-dimensioncited by 2
  2. 2019Parametric versus Semi and Nonparametric Regression Modelscited by 2
  3. 2024Sparse Max-Affine Regressioncited by 1

Built on by

Not cited yet.