# Private Isotonic Regression

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 14 of its 52 references that are in the map.
- First posted on arXiv 27 Oct 2022.

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

- [On Calibration of Modern Neural Networks](https://mlsanity.com/paper/1706.04599/) (2017)
- [Differentially Private Empirical Risk Minimization Revisited: Faster and More General](https://mlsanity.com/paper/1802.05251/) (2018)
- [Private PAC learning implies finite Littlestone dimension](https://mlsanity.com/paper/1806.00949/) (2018)
- [Private Learning and Sanitization: Pure vs. Approximate Differential Privacy](https://mlsanity.com/paper/1407.2674/) (2014)
- [Deep Lattice Networks and Partial Monotonic Functions](https://mlsanity.com/paper/1709.06680/) (2017)
- [Differentially Private Release and Learning of Threshold Functions](https://mlsanity.com/paper/1504.07553/) (2015)
- [Between Pure and Approximate Differential Privacy](https://mlsanity.com/paper/1501.06095/) (2015)
- [Certified Monotonic Neural Networks](https://mlsanity.com/paper/2011.10219/) (2020)
- [Counterexample-Guided Learning of Monotonic Neural Networks](https://mlsanity.com/paper/2006.08852/) (2020)
- [Differentially Private Simple Linear Regression](https://mlsanity.com/paper/2007.05157/) (2020)
- [Sample Complexity Bounds on Differentially Private Learning via Communication Complexity](https://mlsanity.com/paper/1402.6278/) (2014)
- [Privately Learning Thresholds: Closing the Exponential Gap](https://mlsanity.com/paper/1911.10137/) (2019)
- [Online Isotonic Regression](https://mlsanity.com/paper/1603.04190/) (2016)
- [Tight Bounds for Differentially Private Anonymized Histograms](https://mlsanity.com/paper/2111.03257/) (2021)

## Abstract (arXiv)

In this paper, we consider the problem of differentially private (DP) algorithms for isotonic regression. For the most general problem of isotonic regression over a partially ordered set (poset) X and for any Lipschitz loss function, we obtain a pure-DP algorithm that, given n input points, has an expected excess empirical risk of roughly width(X) · log|X| / n, where width(X) is the width of the poset. In contrast, we also obtain a near-matching lower bound of roughly (width(X) + log |X|) / n, that holds even for approximate-DP algorithms. Moreover, we show that the above bounds are essentially the best that can be obtained without utilizing any further structure of the poset. In the special case of a totally ordered set and for ℓ1 and ℓ22 losses, our algorithm can be implemented in near-linear running time; we also provide extensions of this algorithm to the problem of private isotonic regression with additional structural constraints on the output function.