# Composite Difference-Max Programs for Modern Statistical Estimation Problems

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

## Key facts

- Cited by 10 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 1 Mar 2018.

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

- [Faster Algorithms for Learning Convex Functions](https://mlsanity.com/paper/2111.01348/) (2021)
- [Non-geodesically-convex optimization in the Wasserstein space](https://mlsanity.com/paper/2406.00502/) (2024)
- [Data-driven Piecewise Affine Decision Rules for Stochastic Programming with Covariate Information](https://mlsanity.com/paper/2304.13646/) (2023)
- [Linearization Algorithms for Fully Composite Optimization](https://mlsanity.com/paper/2302.12808/) (2023)
- [DC-LA: Difference-of-Convex Langevin Algorithm](https://mlsanity.com/paper/2601.22932/) (2026)
- [A stochastic smoothing framework for nonconvex-nonconcave minEmax problems with applications to Wasserstein distributionally robust optimization](https://mlsanity.com/paper/2502.17602/) (2025)
- [A proximal-proximal majorization-minimization algorithm for nonconvex tuning-free robust regression problems](https://mlsanity.com/paper/2106.13683/) (2021)
- [Consistent Approximations in Composite Optimization](https://mlsanity.com/paper/2201.05250/) (2022)
- [Change-Point Detection via Piecewise Linear Fitting Using MIP](https://mlsanity.com/paper/2602.11947/) (2026)
- [RA-DCA: A Randomized Active-Set DCA for Directional Stationarity in Max-Structured DC Programs](https://mlsanity.com/paper/2605.23550/) (2026)

## Abstract (arXiv)

Many modern statistical estimation problems are defined by three major components: a statistical model that postulates the dependence of an output variable on the input features; a loss function measuring the error between the observed output and the model predicted output; and a regularizer that controls the overfitting and/or variable selection in the model. We study the sampling version of this generic statistical estimation problem where the model parameters are estimated by empirical risk minimization, which involves the minimization of the empirical average of the loss function at the data points weighted by the model regularizer. In our setup we allow all three component functions discussed above to be of the difference-of-convex (dc) type and illustrate them with a host of commonly used examples, including those in continuous piecewise affine regression and in deep learning (where the activation functions are piecewise affine). We describe a nonmonotone majorization-minimization (MM) algorithm for solving the unified nonconvex, nondifferentiable optimization problem which is formulated as a specially structured composite dc program of the pointwise max type, and present convergence results to a directional stationary solution. An efficient semismooth Newton method is proposed to solve the dual of the MM subproblems. Numerical results are presented to demonstrate the effectiveness of the proposed algorithm and the superiority of continuous piecewise affine regression over the standard linear model.