Lune

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) X\mathcal{X} and for any Lipschitz loss function, we obtain a pure-DP algorithm that, given nn input points, has an expected excess empirical risk of roughly width(X)⋅log⁡∣X∣/n\mathrm{width}(\mathcal{X}) \cdot \log|\mathcal{X}| / n, where width(X)\mathrm{width}(\mathcal{X}) is the width of the poset. In contrast, we also obtain a near-matching lower bound of roughly (width(X)+log⁡∣X∣)/n(\mathrm{width}(\mathcal{X}) + \log |\mathcal{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\ell_1 and ℓ22\ell_2^2 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.

Questions to start from

Lune can draw on

the full paper · related work

Get the answer

Free to start. No credit card required.

Lineage

  • Certified Monotonic Neural Networks cites Counterexample-Guided Learning of Monotonic Neural Networks
Builds onCited byLeft to right by year; the more cited, the higher.

Builds on2

  1. Certified Monotonic Neural NetworksXingchao Liu, Xing Han, Na Zhang, Qiang LiuNeurIPS 2020 · 116 citations
  2. Counterexample-Guided Learning of Monotonic Neural NetworksAishwarya Sivaraman, Golnoosh Farnadi, Todd D. Millstein, Guy Van den BroeckNeurIPS 2020 · 68 citations

Related papers

  1. Differentially Private Approximate QuantilesHaim Kaplan, Shachar Schnapp, Uri StemmerICML 2022 · 23 citations
  2. Differentially Private Generalized Linear Models RevisitedRaman Arora, Raef Bassily, Cristóbal Guzmán, Michael Menart et al.NeurIPS 2022 · 24 citations
  3. 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
  4. Differentially Private Stochastic Optimization: New Results in Convex and Non-Convex SettingsRaef Bassily, Cristóbal Guzmán, Michael MenartNeurIPS 2021 · 68 citations
  5. Optimal Private Median Estimation under Minimal Distributional AssumptionsChristos Tzamos, Emmanouil V. Vlatakis-Gkaragkounis, Ilias ZadikNeurIPS 2020 · 25 citations
Dusk over the sea between two cliffs drawn in fine vertical lines