# Max-Linear Regression by Convex Programming

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

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- Builds on 12 of its 36 references that are in the map.
- First posted on arXiv 12 Mar 2021.

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

- [Mad Max: Affine Spline Insights into Deep Learning](https://mlsanity.com/paper/1805.06576/) (2018)
- [The Geometry of Deep Networks: Power Diagram Subdivision](https://mlsanity.com/paper/1905.08443/) (2019)
- [A Deterministic Linear Program Solver in Current Matrix Multiplication Time](https://mlsanity.com/paper/1910.11957/) (2019)
- [PhaseMax: Convex Phase Retrieval via Basis Pursuit](https://mlsanity.com/paper/1610.07531/) (2016)
- [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)
- [Phase Retrieval Meets Statistical Learning Theory: A Flexible Convex Relaxation](https://mlsanity.com/paper/1610.04210/) (2016)
- [Max-Affine Spline Insights into Deep Generative Networks](https://mlsanity.com/paper/2002.11912/) (2020)
- [Learning to Approximate a Bregman Divergence](https://mlsanity.com/paper/1905.11545/) (2019)
- [Solving Equations of Random Convex Functions via Anchored Regression](https://mlsanity.com/paper/1702.05327/) (2017)
- [Generalized notions of sparsity and restricted isometry property. Part I: A unified framework](https://mlsanity.com/paper/1706.09410/) (2017)
- [Estimation from Non-Linear Observations via Convex Programming with Application to Bilinear Regression](https://mlsanity.com/paper/1806.07307/) (2018)

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

- [Faster Algorithms for Learning Convex Functions](https://mlsanity.com/paper/2111.01348/) (2021)
- [Sample-Efficient Linear Regression with Self-Selection Bias](https://mlsanity.com/paper/2402.14229/) (2024)

## Abstract (arXiv)

We consider the multivariate max-linear regression problem where the model parameters boldsymbolβ1,dotsc,boldsymbolβk∈ℝp need to be estimated from n independent samples of the (noisy) observations y = max1≤ j ≤ k boldsymbolβj^mathsfT boldsymbolx + noise. The max-linear model vastly generalizes the conventional linear model, and it can approximate any convex function to an arbitrary accuracy when the number of linear models k is large enough. However, the inherent nonlinearity of the max-linear model renders the estimation of the regression parameters computationally challenging. Particularly, no estimator based on convex programming is known in the literature. We formulate and analyze a scalable convex program given by anchored regression (AR) as the estimator for the max-linear regression problem. Under the standard Gaussian observation setting, we present a non-asymptotic performance guarantee showing that the convex program recovers the parameters with high probability. When the k linear components are equally likely to achieve the maximum, our result shows a sufficient number of noise-free observations for exact recovery scales as k4p up to a logarithmic factor.  This sample complexity coincides with that by alternating minimization (Ghosh et al., 2021). Moreover, the same sample complexity applies when the observations are corrupted with arbitrary deterministic noise. We provide empirical results that show that our method performs as our theoretical result predicts, and is competitive with the alternating minimization algorithm particularly in presence of multiplicative Bernoulli noise. Furthermore, we also show empirically that a recursive application of AR can significantly improve the estimation accuracy.