# Faster Algorithms for Learning Convex Functions

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

## Key facts

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

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

- [PyTorch: An Imperative Style, High-Performance Deep Learning Library](https://mlsanity.com/paper/1912.01703/) (2019)
- [XGBoost: A Scalable Tree Boosting System](https://mlsanity.com/paper/1603.02754/) (2016)
- [Convex optimization](https://mlsanity.com/paper/2106.01946/) (2021)
- [Input Convex Neural Networks](https://mlsanity.com/paper/1609.07152/) (2016)
- [f-GAIL: Learning f-Divergence for Generative Adversarial Imitation Learning](https://mlsanity.com/paper/2010.01207/) (2020)
- [A Computational Framework for Multivariate Convex Regression and its Variants](https://mlsanity.com/paper/1509.08165/) (2015)
- [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)
- [Composite Difference-Max Programs for Modern Statistical Estimation Problems](https://mlsanity.com/paper/1803.00205/) (2018)
- [Learning to Approximate a Bregman Divergence](https://mlsanity.com/paper/1905.11545/) (2019)
- [Subgradient Regularized Multivariate Convex Regression at Scale](https://mlsanity.com/paper/2005.11588/) (2020)
- [Max-Linear Regression by Convex Programming](https://mlsanity.com/paper/2103.07020/) (2021)

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

- [Asymmetric Certified Robustness via Feature-Convex Neural Networks](https://mlsanity.com/paper/2302.01961/) (2023)
- [Neural Bregman Divergences for Distance Learning](https://mlsanity.com/paper/2206.04763/) (2022)
- [Max-affine regression via first-order methods](https://mlsanity.com/paper/2308.08070/) (2023)
- [Privacy Amplification by Iteration for ADMM with (Strongly) Convex Objective Functions](https://mlsanity.com/paper/2312.08685/) (2023)
- [Locally Near Optimal Piecewise Linear Regression in High Dimensions via Difference of Max-Affine Functions](https://mlsanity.com/paper/2605.06959/) (2026)

## Abstract (arXiv)

The task of approximating an arbitrary convex function arises in several learning problems such as convex regression, learning with a difference of convex (DC) functions, and learning Bregman or f-divergences. In this paper, we develop and analyze an approach for solving a broad range of convex function learning problems that is faster than state-of-the-art approaches. Our approach is based on a 2-block ADMM method where each block can be computed in closed form. For the task of convex Lipschitz regression, we establish that our proposed algorithm converges with iteration complexity of  O(n√d/ε) for a dataset bm X ∈ mathbb Rn× d and ε > 0. Combined with per-iteration computation complexity, our method converges with the rate O(n3 d1.5/ε+n2 d2.5/ε+n d3/ε). This new rate improves the state of the art rate of O(n5d2/ε) if d = o( n4). Further we provide similar solvers for DC regression and Bregman divergence learning. Unlike previous approaches, our method is amenable to the use of GPUs. We demonstrate on regression and metric learning experiments that our approach is over 100 times faster than existing approaches on some data sets, and produces results that are comparable to state of the art.