Private Isotonic Regression
Abstract
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) and for any Lipschitz loss function, we obtain a pure-DP algorithm that, given input points, has an expected excess empirical risk of roughly , where is the width of the poset. In contrast, we also obtain a near-matching lower bound of roughly , 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 and 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.
Ask Lune
Know this paper in minutes, not an afternoon.
Lune can read every page of it and the top-tier papers that cite it, and gives you its claims, its evidence and its limits, each one cited to the paper it comes from. No skimming, no AI slop.
Lineage
Builds on2
Related papers
- Differentially Private Approximate QuantilesHaim Kaplan, Shachar Schnapp, Uri StemmerICML 2022 · 23 citations
- Differentially Private Generalized Linear Models RevisitedRaman Arora, Raef Bassily, Cristóbal Guzmán, Michael Menart et al.NeurIPS 2022 · 24 citations
- Faster Rates of Convergence to Stationary Points in Differentially Private OptimizationRaman Arora, Raef Bassily, Tomás González, Cristóbal Guzmán et al.ICML 2023 · 37 citations
- Differentially Private Stochastic Optimization: New Results in Convex and Non-Convex SettingsRaef Bassily, Cristóbal Guzmán, Michael MenartNeurIPS 2021 · 68 citations
- Optimal Private Median Estimation under Minimal Distributional AssumptionsChristos Tzamos, Emmanouil V. Vlatakis-Gkaragkounis, Ilias ZadikNeurIPS 2020 · 25 citations
