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

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

## 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 (most cited first, 15 of 15)

- [Convergence Analysis of Two-layer Neural Networks with ReLU Activation](https://mlsanity.com/paper/1705.09886/) (2017)
- [Phase Retrieval via Wirtinger Flow: Theory and Algorithms](https://mlsanity.com/paper/1407.1065/) (2014)
- [Tropical Geometry of Deep Neural Networks](https://mlsanity.com/paper/1805.07091/) (2018)
- [On Learning Gaussian Multi-index Models with Gradient Flow](https://mlsanity.com/paper/2310.19793/) (2023)
- [Training Neural Networks is NP-Hard in Fixed Dimension](https://mlsanity.com/paper/2303.17045/) (2023)
- [A comparison of deep networks with ReLU activation function and linear spline-type methods](https://mlsanity.com/paper/1804.02253/) (2018)
- [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)
- [Piecewise Linear Regression via a Difference of Convex Functions](https://mlsanity.com/paper/2007.02422/) (2020)
- [A convex formulation for high-dimensional sparse sliced inverse regression](https://mlsanity.com/paper/1809.06024/) (2018)
- [Faster Algorithms for Learning Convex Functions](https://mlsanity.com/paper/2111.01348/) (2021)
- [Max-affine regression via first-order methods](https://mlsanity.com/paper/2308.08070/) (2023)
- [Optimal Bounds on the VC-dimension](https://mlsanity.com/paper/1807.07924/) (2018)
- [Parametric versus Semi and Nonparametric Regression Models](https://mlsanity.com/paper/1906.10221/) (2019)
- [Sparse Max-Affine Regression](https://mlsanity.com/paper/2411.02225/) (2024)

## 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.