# Near-optimal Delta-convex Estimation of Lipschitz Functions

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 11 of its 53 references that are in the map.
- First posted on arXiv 19 Nov 2025.

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

- [XGBoost: A Scalable Tree Boosting System](https://mlsanity.com/paper/1603.02754/) (2016)
- [Convex optimization](https://mlsanity.com/paper/2106.01946/) (2021)
- [Maxout Networks](https://mlsanity.com/paper/1302.4389/) (2013)
- [Clarabel: An interior-point solver for conic programs with quadratic objectives](https://mlsanity.com/paper/2405.12762/) (2024)
- [Piecewise Linear Regression via a Difference of Convex Functions](https://mlsanity.com/paper/2007.02422/) (2020)
- [scikit-fda: A Python Package for Functional Data Analysis](https://mlsanity.com/paper/2211.02566/) (2022)
- [Convex Regression in Multidimensions: Suboptimality of Least Squares Estimators](https://mlsanity.com/paper/2006.02044/) (2020)
- [Subgradient Regularized Multivariate Convex Regression at Scale](https://mlsanity.com/paper/2005.11588/) (2020)
- [A Parallelizable Dual Smoothing Method for Large Scale Convex Regression Problems](https://mlsanity.com/paper/1608.02227/) (2016)
- [Chaining Bounds for Empirical Risk Minimization](https://mlsanity.com/paper/1609.01872/) (2016)
- [Convex Regression with a Penalty](https://mlsanity.com/paper/2509.19788/) (2025)

## Abstract (arXiv)

This paper presents a tractable algorithm for estimating an unknown Lipschitz function from noisy observations and establishes an upper bound on its convergence rate. The approach extends max-affine methods from convex shape-restricted regression to the more general Lipschitz setting. A key component is a nonlinear feature expansion that maps max-affine functions into a subclass of delta-convex functions, which act as universal approximators of Lipschitz functions while preserving their Lipschitz constants. Leveraging this property, the estimator attains the minimax convergence rate (up to logarithmic factors) with respect to the intrinsic dimension of the data under squared loss and subgaussian distributions in the random design setting. The algorithm integrates adaptive partitioning to capture intrinsic dimension, a penalty-based regularization mechanism that removes the need to know the true Lipschitz constant, and a two-stage optimization procedure combining a convex initialization with local refinement. The framework is also straightforward to adapt to convex shape-restricted regression. Experiments demonstrate competitive performance relative to other theoretically justified methods, including nearest-neighbor and kernel-based regressors.