mlsanityData to 14 Oct 2026

Private Isotonic Regression

arXiv 2210.15175 ↗First posted 27 Oct 2022cs.LG cs.CR stat.MLcited by 0

Not on the map. Why?

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.

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

14 of 52 references.

References · 14

  1. 2017On Calibration of Modern Neural Networkscited by 4,960
  2. 2018Differentially Private Empirical Risk Minimization Revisited: Faster and More Generalcited by 128
  3. 2018Private PAC learning implies finite Littlestone dimensioncited by 74
  4. 2014Private Learning and Sanitization: Pure vs. Approximate Differential Privacycited by 63
  5. 2017Deep Lattice Networks and Partial Monotonic Functionscited by 63
  6. 2015Differentially Private Release and Learning of Threshold Functionscited by 60
  7. 2015Between Pure and Approximate Differential Privacycited by 56
  8. 2020Certified Monotonic Neural Networkscited by 51
  9. 2020Counterexample-Guided Learning of Monotonic Neural Networkscited by 34
  10. 2020Differentially Private Simple Linear Regressioncited by 34
  11. 2014Sample Complexity Bounds on Differentially Private Learning via Communication Complexitycited by 31
  12. 2019Privately Learning Thresholds: Closing the Exponential Gapcited by 31
2 more
  1. 2016Online Isotonic Regressioncited by 9
  2. 2021Tight Bounds for Differentially Private Anonymized Histogramscited by 2

Built on by

Not cited yet.