Pith. sign in

REVIEW 3 major objections 4 minor 40 references

The Role of Randomness in Stability

T0 review · 3 major / 4 minor · reviewed 2026-08-08 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗

Pith's one-line read For any statistical task, the number of random bits needed for replicable or differentially private algorithms matches, up to a single bit, the negative log of its global stability; in PAC learning this pins down exactly which classes are…

desk verdict Strong and likely-correct paper unifying global stability, certificate complexity, and DP randomness, with a fixable proof slip in Theorem 4.1 and an unproved external parameter claim in Theorem 6.1. read the letter →

arxiv 2502.08007 v1 pith:IQXGDLXE submitted 2025-02-11 cs.LG stat.ML

Max Hopkins , Shay Moran This is my paper · ORCID
classification cs.LGstat.ML MSC 68Q3268P2768W20
keywords replicabilitydifferentialprivacyrandomnesscomplexityglobalstabilityLittlestonedimensionPAClearningcertificateagnostic
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

This paper establishes that the number of random bits needed for algorithmic stability is not an independent resource: for any statistical task it is governed, up to a single bit, by the best replication probability that any deterministic algorithm can achieve for that task, a quantity called global stability that is universally capped at $1/2$ for every non-trivial task. The paper proves a weak-to-strong boosting theorem: any task with global stability $\eta$ can be solved by a $\rho$-replicable algorithm using only $\log(1/\eta) + \log(1/\rho)$ shared random bits, and the same $\eta$ controls the randomness cost of differential privacy under mild conditions on the privacy parameters. Applied to agnostic PAC learning, this yields an exact characterization: a hypothesis class admits a stable, replicable, or private learner exactly when its Littlestone dimension is finite, with certificate complexity $\mathrm{poly}(d) + O(\mathrm{VC}(H)\log(1/\alpha))$ and randomness growing only logarithmically in the inverse error. This resolves a previously open question about error-dependent list-replicability, and it matters because in the learnable regime stability is nearly free in the resource that matters most: randomness.

What carries the argument

The load-bearing machinery is the measured comparison between two quantities: global stability, defined as the best collision probability $\eta$ that any deterministic algorithm solving the task can achieve (so $C_{\mathrm{Glob}} = \log(1/\eta)$), and certificate complexity, the fewest shared random bits $C_{\mathrm{Rep}}$ on which a better-than-half replicable algorithm exists. The bridge between them has four parts: (1) the heavy-hitter list of any $\eta$-globally stable algorithm, which has at most $1/\eta$ elements and drives both directions of the equivalence; (2) a randomness-efficient thresholding booster (Algorithm 1), which estimates empirical output densities, draws a random threshold from a grid of size about $2^{C_{\mathrm{Glob}}}/\rho$, and returns the first hypothesis above the threshold, converting deterministic stability into replicability at the cost of one extra bit; (3) the small-support sampling observation that any distribution over a support of size $T$ can be sampled within total-variation distance $\delta$ using $\log T + \log(1/\delta)$ random bits, which is what makes the stability-to-DP transform randomness-efficient; and (4) the realizable list-stable learner that outputs a list of $\exp(\mathrm{poly}(d))\alpha^{-O(1)}$ hypotheses containing a fixed $\Omega(1/d)$-heavy hitter, which feeds the agnostic-to-realizable reduction behind the PAC characterization. A preliminary result (Theorem 3.2) shows heavy-hitter global stability and full replication global stability are exactly equivalent, not merely within a quadratic factor as previously known, and this equivalence is what lets the paper move freely between randomized and deterministic guarantees.

What would settle it

Two concrete checks would settle the central claims: first, identify any statistical task for which $C_{\mathrm{Rep}} > C_{\mathrm{Glob}} + 1$ (for instance, compute both quantities for the $d$-coin bias-estimation tasks previously studied for certificate and DP complexity), which would refute Theorem 1.1; second, inspect the realizable list-stable learner used as input to the agnostic reduction and determine whether its list size is really $\exp(\mathrm{poly}(d))\alpha^{-O(1)}$ with a fixed $\Omega(1/d)$-heavy hitter achievable in $\mathrm{poly}(d, \alpha^{-1}, \log(1/\beta))$ samples, since a class of finite Littlestone dimension whose list size or sample bound must be exponential in $1/\alpha$ would break the PAC characterization's upper bound.

Watch

Extended reading notes

Core claim

The central claim, stated on the paper's own terms, is a weak-to-strong boosting theorem for stability. If a statistical task has a deterministic algorithm whose collision probability is $\eta$ (its global stability), then that algorithm can be boosted to one that is $\rho$-replicable with only $\log(1/\eta) + \log(1/\rho)$ shared random bits, and conversely any better-than-half replicable algorithm on $\ell$ bits yields a deterministic algorithm with collision probability roughly $2^{-\ell}$. Consequently, for every statistical task $C_{\mathrm{Glob}} \le C_{\mathrm{Rep}} \le C_{\mathrm{Glob}} + 1$, where $C_{\mathrm{Glob}}$ is the negative log of the best achievable global stability and $C_{\mathrm{Rep}}$ is the fewest shared random bits needed to beat $1/2$ replication probability. The same global-stability parameter controls differential privacy: a globally stable algorithm boosts into an $(\varepsilon, \delta)$-DP algorithm using $\log(1/\eta) + \log(1/\varepsilon) + \log(1/\delta)$ random bits, with user-level DP giving the parameter-free statement, and any sufficiently private algorithm has a heavy hitter that converts back into a deterministic globally stable algorithm. For agnostic PAC learning the paper resolves an open question in the positive direction: a class with Littlestone dimension $d$ admits a better-than-half replicable learner with certificate complexity $\mathrm{poly}(d) + O(\mathrm{VC}(H) \log(1/\alpha))$ and sample complexity $\exp(\mathrm{poly}(d))\cdot \mathrm{poly}(1/\alpha, \log 1/\beta)$, while a class with infinite Littlestone dimension admits no replicable, globally stable, or private learner with error below $1/2$, i.e. none better than random guessing.

Load-bearing premise

The upper bound of Theorem 6.1 assumes that the quoted realizable list-stable learner (Theorem 6.2, attributed to prior work) really delivers, within $\mathrm{poly}(d, \alpha^{-1}, \log(1/\beta))$ samples, a list of size $\exp(\mathrm{poly}(d))\alpha^{-O(1)}$ that contains a fixed $\Omega(1/d)$-heavy hitter; the paper takes the polynomial-in-$\alpha$ part of that guarantee to be immediate from the cited work without proving it, and if that parameter claim fails, the agnostic learner's sample and certificate bounds do not go through.

Editorial extensions

If this is right

  • Any statistical task whose best deterministic algorithm has collision probability $2^{-C_{\mathrm{Glob}}}$ can be made $\rho$-replicable with $C_{\mathrm{Glob}} + \log(1/\rho)$ random bits, so beating $1/2$ replication probability costs at most one bit beyond the deterministic baseline.
  • Agnostic PAC learning of a class with Littlestone dimension $d$ is possible with a replicable learner using $\mathrm{poly}(d) + O(\mathrm{VC}(H)\log(1/\alpha))$ random bits and $\exp(\mathrm{poly}(d))\cdot\mathrm{poly}(1/\alpha, \log 1/\beta)$ samples, so randomness scales only logarithmically in the excess error.
  • No replicable, globally stable, or differentially private agnostic learner exists for classes of infinite Littlestone dimension at error below $1/2$; stable learning and classic (non-stable) learning diverge exactly at this boundary.
  • Under mild privacy parameters ($\varepsilon \lesssim 1/\sqrt{T\log T}$, $\delta \lesssim 1/T$), user-level DP randomness complexity and global stability agree up to additive constants, so upper and lower bounds on one translate to the other.
  • In the replicable regime, the paper's learner uses $\exp(\mathrm{poly}(d))$ samples while a heavy-hitter-only stable learner uses only $\mathrm{poly}(d, 1/\alpha, \log 1/\beta)$; the paper leaves open whether sample efficiency and randomness efficiency can be achieved simultaneously.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

  • The one-bit equivalence suggests a transfer principle: any future stability notion whose deterministic version is capped at $1/2$ replication probability (as any distribution-free guarantee for non-trivial tasks must be) will inherit the same randomness profile as replicability, so the theorem likely generalizes to other stability definitions based on divergences between two runs.
  • The certificate bound $\mathrm{poly}(d) + O(\mathrm{VC}(H)\log(1/\alpha))$ suggests the active randomness in stable learning is sample-driven hypothesis selection plus a committed coin flip; a testable question is whether matching lower bounds force at least $\Omega(\mathrm{VC}(H)\log(1/\alpha))$ bits.
  • The gap between the heavy-hitter learner's $\mathrm{poly}(d, 1/\alpha, \log 1/\beta)$ sample bound and the replicable learner's $\exp(\mathrm{poly}(d))$ samples hints that the exponential sample term is an artifact of the reduction rather than intrinsic, and a direct replicable learner matching the realizable sample complexity may exist, which the paper explicitly flags as open.
  • In federated settings, the user-level DP equivalence implies that $T$ users can solve any task privately at randomness cost $C_{\mathrm{Glob}} + O(1)$ whenever $\varepsilon \le c/\sqrt{T\log T}$, which would mean per-user randomness well below $\log T$ bits is sufficient in the statistical regime; whether practical mechanisms can reach this bound is a concrete engineering question.
Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Referee Report

3 major / 4 minor

Summary. The paper studies the number of random bits needed for stable algorithms in statistical tasks. Its first main result (Theorem 1.1 / Theorem 4.1) is a 'weak-to-strong' boosting theorem: for any statistical task, the global-stability complexity CGlob and the certificate complexity CRep differ by at most 1, and rho-replicability can be achieved with at most CGlob + log(1/rho) random bits. The second set of results (Theorems 1.2, 1.3 / 5.1, 5.2) gives two-way quantitative transformations between global stability and the randomness complexity of (user-level) differential privacy. The third set (Theorems 1.4 / 6.1) characterizes the randomness complexity of agnostic PAC learning: a class has bounded certificate complexity if and only if it has finite Littlestone dimension, with sample complexity exp(poly(d)) poly(1/alpha, log(1/beta)) and certificate complexity poly(d) + O(VC(H) log(d/alpha)); classes of infinite Littlestone dimension admit no better-than-half replicable or globally stable learner. The arguments are based on a random-threshold discretization, a bounded-support DP-selection transform, a perfect-generalization step, and an agnostic-to-realizable reduction.

Significance. If the results hold, Theorem 1.1 provides a clean parameter-free equivalence between global stability and certificate complexity, and Theorems 5.1-5.2 give the first general comparisons between DP randomness complexity and global stability. Theorem 6.1 resolves an open question of Chase et al. (STOC 2024) in the equivalent list-replicability language, with explicit though large sample/randomness bounds. The paper is generally careful about parameter dependencies and clearly separates parameter-free and parametrized notions. The main positive PAC result, however, rests on a strong external realizable list-stable learner (Theorem 6.2) whose quantitative guarantees are stated but only partially proved or cited, and the proof of Theorem 6.1 contains an internal inconsistency in the heavy-hitter bound. These issues are fixable but require real work.

major comments (3)
  1. [Section 6, Theorem 6.2 and its use in the proof of Theorem 6.1] The positive direction of the PAC characterization is entirely dependent on the quantitative guarantees of the external realizable list-stable learner: sample complexity poly(d, alpha^{-1}, log(1/beta)), list size exp(poly(d)) alpha^{-O(1)}, and a fixed Omega(1/d)-heavy-hitter in the list. The first two of these are asserted in footnote 9 to be 'immediate from [GGKM21]' without any derivation, and the third is stated without proof. These parameters are load-bearing: the reduction's pruning step bounds |Pruned| by d times n(alpha/8, beta1)^{O(VC)} times the list size, and the heavy-hitter h_D is used to argue that a fixed good hypothesis appears Omega(T/d) times. If the actual guarantee had list size exp(poly(d)) alpha^{-O(d)} or heavy-hitter probability 1/poly(d, 1/alpha), the stated sample complexity and certificate complexity of Theorem 6.1 would not follow. The manuscript should either prove these parameter claims from [GGKM21, GKM21] or give a precise theorem-and-lemma citation with the exact statement.
  2. [Section 6, proof of Theorem 6.1, paragraph after the pruning step] The proof states that the resulting algorithm has an Omega(exp(poly(d)) alpha^{-O(1)}) heavy hitter, but the preceding calculation gives |Pruned(C)| <= d n(alpha/8, beta1)^{O(VC)} exp(poly(d)) with n(alpha/8, beta1) = poly(d, alpha^{-1}), so the probability of outputting the fixed good hypothesis h_D is at most the inverse of this quantity, i.e. exp(-poly(d)) alpha^{O(VC)}. This discrepancy is not cosmetic: it determines the certificate-complexity additive term (VC log(1/alpha), not O(log(1/alpha))) and the sample overhead incurred when applying Theorem 4.1. The statement of Theorem 6.1 and the proof should be made consistent; the certificate bound stated in the theorem is in fact compatible with the corrected heavy-hitter bound, but the sample-complexity notation should then explicitly allow polynomial-in-(1/alpha) factors of degree depending on VC(H).
  3. [Section 4, proof of Theorem 4.1 (upper bound, Algorithm 1)] The replicability argument needs an explicit choice of the threshold offset gamma. As written, the assertion that at most 1/eta hypotheses have empirical weight greater than eta - T gamma is not generally true, because T can be as large as (2^{CGlob}-1)/rho and eta - T gamma may be negative unless gamma << eta/T. The proof should state a concrete condition such as gamma <= c eta / T (or gamma <= c 2^{-2 CGlob} for constant rho) and verify that, with this choice, the number of 'bad' thresholds is at most 1/eta - 1 as claimed. This is a local fix, but it is load-bearing for the upper bound in Theorem 1.1.
minor comments (4)
  1. [Section 4, lower-bound proof of Theorem 4.1] After defining the majority-amplified algorithm Amaj-T, the collision probability is computed for A rather than for Amaj-T; the two uses of the random string (shared within a run, independent between runs) should be stated explicitly to avoid confusion.
  2. [Section 5, Lemma 5.5] The bounded-support property states |Supp(ADP(S))| <= T, but the proof gives at most T+1 (the T outputs of AList plus the dummy hypothesis). The constants in the lemma and proof should be adjusted to match.
  3. [Section 6, proof of Theorem 6.1] The line 'Fix beta1 = exp(poly(d)) alpha^{-O(1)} to be sufficiently smaller than the list size' should read 'sufficiently smaller than the heavy-hitter probability Omega(1/d)', since the argument needs the heavy hitter h_D to be correct, not merely the list size to be large.
  4. [Section 5, Theorem 5.1] The displayed statement of Theorem 5.1 has overlapping or missing expressions (for example, in the condition on beta), which makes it difficult to verify the parameter trade-offs. The statement should be typeset cleanly.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity: the main theorems are proved by black-box reductions from definitions and external prior results; the only flagged gap is an unproved external parameter claim, which is a support issue, not circularity.

full rationale

Core derivation chain: Section 4 proves Theorem 1.1 by (i) averaging over the CRep random strings of a >1/2-replicable algorithm to produce a 2^{-CRep} heavy hitter, and (ii) a thresholding procedure over empirical densities of a 2^{-CGlob}-globally stable algorithm. Neither step identifies CRep with CGlob by definition; the equivalence is the content of the proof, not an artifact of the definitions. Section 3's equivalence between collision-based global stability and heavy-hitter global stability is proved directly, rather than imported. The differential-privacy results in Section 5 are explicit black-box compositions of external primitives: DP Selection [KKMN09, BNS16, BDRS18], small-support sampling [CSV24, Lemma 2.10], and perfect generalization [GKK+24, Theorem 31], with no fitted constants or target-dependent normalizations. The PAC-learning result in Section 6 is a transparent reduction from agnostic learning to the external realizable list-stable learner of [GGKM21, GKM21] (Theorem 6.2); the sample and certificate bounds are computed from the stated parameters of that learner together with the Sauer-Shelah-Perles lemma, and are not restatements of the learner's guarantees. Self-citations [CMY23], [CCMY24], and [BGH+23] appear as motivation, framing, and tools, but the load-bearing positive claims do not reduce to an unverified self-citation: the crucial realizable list-stable learner [GGKM21, GKM21] has no author overlap with the present paper. One caveat belongs in a correctness pass rather than a circularity verdict: footnote 9 asserts without proof that the polynomial-in-alpha list size and Omega(1/d) heavy-hitter parameters are 'immediate from [GGKM21]'; if that external quantitative claim fails, the positive bounds of Theorem 6.1 would need revision. That is an unsupported external premise, not a circular derivation.

Assumptions & free parameters 0 free parameters · 8 assumptions · 0 invented entities

The paper contributes symbolic reductions and does not fit any numerical constants to data. The free-parameter list is empty. The axioms listed are external theorems and modeling choices that the central claims depend on; most are standard and published, but the [GGKM21] list-stable learner parameter regime is the most sensitive external input.

assumptions (8)
  • standard math Standard concentration inequalities and the Sauer-Shelah lemma
    Used throughout Sections 4-6 for Chernoff/Hoeffding bounds and to bound the number of labelings of a sample by a VC-dimension-d class.
  • domain assumption Statistical task framework (Definition 2.1)
    The whole paper treats learning problems as tasks with accepted solution sets; all complexity measures are defined relative to this model.
  • domain assumption Realizable list-stable learner of [GGKM21, GKM21] (Theorem 6.2)
    Provides the Omega(1/d)-heavy-hitter and polynomial sample complexity in the realizable case; the positive side of Theorem 6.1 is built on it.
  • domain assumption Perfect generalization theorem of [GKK+24] (Theorem 5.7)
    Used to derive DP-to-stability (Theorem 5.1(2) and 5.2(2)) by showing any sufficiently private algorithm has a heavy hitter.
  • domain assumption DP Selection theorem [KKMN09, BNS16, BDRS18] (Theorem 5.4)
    Used in Lemma 5.5 to convert heavy-hitter datasets into bounded-support DP algorithms.
  • domain assumption Small-support distribution sampling lemma of [CSV24] (Lemma 5.3)
    Allows approximating any distribution with small support using few random bits, giving the randomness bound in the stability-to-DP direction.
  • domain assumption Impossibility of private PAC learning for infinite Littlestone dimension [ALMM19]
    Used in the converse of Theorem 6.1: a replicable agnostic learner would imply a private realizable learner, contradicting this result.
  • domain assumption Global stability cap at 1/2 [CMY23]
    Establishes the barrier that motivates certificate complexity; the paper's positive results are stated relative to this guarantee.

how reviews work

0 comments
Cite this review

Pith. "Pith review of The Role of Randomness in Stability." pith.science (2026). https://pith.science/paper/IQXGDLXE

@misc{pith2026250208007,
  author       = {Pith},
  title        = {Pith review of: The Role of Randomness in Stability},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/IQXGDLXE}},
  note         = {Machine review of arXiv:2502.08007}
}
abstract

Stability is a central property in learning and statistics promising the output of an algorithm $A$ does not change substantially when applied to similar datasets $S$ and $S'$. It is an elementary fact that any sufficiently stable algorithm (e.g.\ one returning the same result with high probability, satisfying privacy guarantees, etc.) must be randomized. This raises a natural question: can we quantify how much randomness is needed for algorithmic stability? We study the randomness complexity of two influential notions of stability in learning: replicability, which promises $A$ usually outputs the same result when run over samples from the same distribution (and shared random coins), and differential privacy, which promises the output distribution of $A$ remains similar under neighboring datasets. The randomness complexity of these notions was studied recently in (Dixon et al. ICML 2024) and (Cannone et al. ITCS 2024) for basic $d$-dimensional tasks (e.g. estimating the bias of $d$ coins), but little is known about the measures more generally or in complex settings like classification. Toward this end, we prove a `weak-to-strong' boosting theorem for stability: the randomness complexity of a task $M$ (either under replicability or DP) is tightly controlled by the best replication probability of any deterministic algorithm solving the task, a weak measure called `global stability' that is universally capped at $\frac{1}{2}$ (Chase et al. FOCS 2023). Using this, we characterize the randomness complexity of PAC Learning: a class has bounded randomness complexity iff it has finite Littlestone dimension, and moreover scales at worst logarithmically in the excess error of the learner. This resolves a question of (Chase et al. STOC 2024) who asked for such a characterization in the equivalent language of (error-dependent) `list-replicability'.

Figures

Figures reproduced from arXiv: 2502.08007 by the authors.

Figure 1
Figure 1. Thresholding procedure for CGlob “ 2 and T “ 7. Blue dots denote the 4 heavy hitters, one of which ppy1q is known to be far from any threshold. This leaves 4 (green) thresholds with no nearby heavy-hitters out of 7, so ρ « 4{7 ą 1 2 , and CRep ď 3. 1.4.2 Global Stability and Differential Privacy We now overview the main ideas behind Theorem 1.2 and Theorem 1.3 in more detail. We start with the forward direction: giv… view at source ↗

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

40 extracted references · 36 canonical work pages

  1. [1]

    852--860

    Noga Alon, Roi Livni, Maryanthe Malliaris, and Shay Moran, Private pac learning implies finite littlestone dimension, Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing, 2019, pp. 852--860

    work page 2019

  2. [2]

    Borja Balle, Gilles Barthe, and Marco Gaboardi, Privacy amplification by subsampling: Tight analyses via couplings and divergences, Advances in neural information processing systems 31 (2018)

    work page 2018

  3. [3]

    Mark Bun, Cynthia Dwork, Guy N. Rothblum, and Thomas Steinke, Composable and versatile privacy via truncated CDP , Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2018, Los Angeles, CA, USA, June 25-29, 2018 (Ilias Diakonikolas, David Kempe, and Monika Henzinger, eds.), ACM , 2018, pp. 74--86

    work page 2018

  4. [4]

    Raef Bassily and Yoav Freund, Typicality-based stability and privacy, CoRR abs/1604.03336 (2016)

    arXiv 2016

  5. [5]

    Mark Bun, Marco Gaboardi, Max Hopkins, Russell Impagliazzo, Rex Lei, Toniann Pitassi, Jessica Sorrell, and Satchit Sivakumar, Stability is stable: Connections between replicability, privacy, and adaptive generalization, arXiv preprint arXiv:2303.12921 (2023)

    work page Pith review arXiv 2023

  6. [6]

    Ari Blonda, Shan Gao, Hamed Hatami, and Pooya Hatami, Stability and list-replicability for agnostic learners, arXiv preprint arXiv:2501.05333 (2025)

    work page Pith review arXiv 2025

  7. [7]

    389--402

    Mark Bun, Roi Livni, and Shay Moran, An equivalence between private classification and online prediction, 2020 IEEE 61st Annual Symposium on Foundations of Computer Science (FOCS), IEEE, 2020, pp. 389--402

    work page 2020

  8. [8]

    369--380

    Mark Bun, Kobbi Nissim, and Uri Stemmer, Simultaneous private learning of multiple concepts, Proceedings of the 2016 ACM Conference on Innovations in Theoretical Computer Science, 2016, pp. 369--380

    work page 2016

Show all 40 references
  1. [9]

    1769--1780

    Zachary Chase, Bogdan Chornomaz, Shay Moran, and Amir Yehudayoff, Local borsuk-ulam, stability, and replicability, Proceedings of the 56th Annual ACM Symposium on Theory of Computing, 2024, pp. 1769--1780

    2024

  2. [10]

    49, JMLR.org, 2016, pp

    Rachel Cummings, Katrina Ligett, Kobbi Nissim, Aaron Roth, and Zhiwei Steven Wu, Adaptive learning with robust generalization guarantees, Proceedings of the 29th Conference on Learning Theory, COLT 2016, New York, USA, June 23-26, 2016 (Vitaly Feldman, Alexander Rakhlin, and O...

    2016

  3. [11]

    Zachary Chase, Shay Moran, and Amir Yehudayoff, Replicability and stability in learning, arXiv preprint arXiv:2304.03757 (2023)

    2023 arXiv

  4. [12]

    Cl \'e ment L Canonne, Francis E Su, and Salil P Vadhan, The randomness complexity of differential privacy

  5. [13]

    Petersburg, Russia, May 28-June 1, 2006

    Cynthia Dwork, Krishnaram Kenthapadi, Frank McSherry, Ilya Mironov, and Moni Naor, Our data, ourselves: Privacy via distributed noise generation, Advances in Cryptology-EUROCRYPT 2006: 24th Annual International Conference on the Theory and Applications of Cryptographic Techniq...

    2006

  6. [14]

    265--284

    Cynthia Dwork, Frank McSherry, Kobbi Nissim, and Adam Smith, Calibrating noise to sensitivity in private data analysis, Theory of cryptography conference, Springer, 2006, pp. 265--284

    2006

  7. [15]

    Peter Dixon, A Pavan, Jason Vander Woude, and NV Vinodchandran, List and certificate complexities in replicable learning, arXiv preprint arXiv:2304.02240 (2023)

    2023 arXiv

  8. [16]

    Eric Eaton, Marcel Hussing, Michael Kearns, and Jessica Sorrell, Replicable reinforcement learning, Advances in Neural Information Processing Systems 36 (2024)

    2024

  9. [17]

    Hossein Esfandiari, Alkis Kalavasis, Amin Karbasi, Andreas Krause, Vahab Mirrokni, and Grigoris Velegkas, Replicable bandits, arXiv preprint arXiv:2210.01898 (2022)

    2022 arXiv

  10. [18]

    Hossein Esfandiari, Amin Karbasi, Vahab Mirrokni, Grigoris Velegkas, and Felix Zhou, Replicable clustering, Advances in Neural Information Processing Systems 36 (2024)

    2024

  11. [19]

    183--196

    Badih Ghazi, Noah Golowich, Ravi Kumar, and Pasin Manurangsi, Sample-efficient proper pac learning with approximate differential privacy, Proceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing, 2021, pp. 183--196

    2021

  12. [20]

    Badih Ghazi, Pritish Kamath, Ravi Kumar, Pasin Manurangsi, Raghu Meka, and Chiyuan Zhang, User-level differential privacy with few examples per user, Advances in Neural Information Processing Systems 36 (2024)

    2024

  13. [21]

    Dauphin, Percy Liang, and Jennifer Wortman Vaughan, eds.), 2021, pp

    Badih Ghazi, Ravi Kumar, and Pasin Manurangsi, User-level differentially private learning via correlated sampling, Advances in Neural Information Processing Systems 34: Annual Conference on Neural Information Processing Systems 2021, NeurIPS 2021, December 6-14, 2021, virtual ...

    2021

  14. [22]

    931--942

    Shafi Goldwasser, Michael P Kim, Vinod Vaikuntanathan, and Or Zamir, Planting undetectable backdoors in machine learning models, 2022 IEEE 63rd Annual Symposium on Foundations of Computer Science (FOCS), IEEE, 2022, pp. 931--942

    2022

  15. [23]

    Simson L Garfinkel and Philip Leclerc, Randomness concerns when deploying differential privacy, Proceedings of the 19th Workshop on Privacy in the Electronic Society, 2020, pp. 73--86

    2020

  16. [24]

    Max Hopkins, Russell Impagliazzo, Daniel Kane, Sihan Liu, and Christopher Ye, Replicability in high dimensional statistics, arXiv preprint arXiv:2406.02628 (2024)

    2024 arXiv

  17. [25]

    Max Hopkins, Daniel M. Kane, Shachar Lovett, and Gaurav Mahajan, Realizable learning is all you need, Conference on Learning Theory, 2-5 July 2022, London, UK (Po - Ling Loh and Maxim Raginsky, eds.), Proceedings of Machine Learning Research, vol. 178, PMLR , 2022, pp. 3015--3069

    2022

  18. [26]

    818--831

    Russell Impagliazzo, Rex Lei, Toniann Pitassi, and Jessica Sorrell, Reproducibility in learning, STOC '22: 54th Annual ACM SIGACT Symposium on Theory of Computing, Rome, Italy, June 20 - 24, 2022 (Stefano Leonardi and Anupam Gupta, eds.), ACM , 2022, pp. 818--831

    2022

  19. [27]

    Junpei Komiyama, Shinji Ito, Yuichi Yoshida, and Souta Koshino, Replicability is asymptotically free in multi-armed bandits, arXiv preprint arXiv:2402.07391 (2024)

    2024 arXiv

  20. [28]

    Alkis Kalavasis, Amin Karbasi, Kasper Green Larsen, Grigoris Velegkas, and Felix Zhou, Replicable learning of large-margin halfspaces, arXiv preprint arXiv:2402.13857 (2024)

    2024

  21. [29]

    171--180

    Aleksandra Korolova, Krishnaram Kenthapadi, Nina Mishra, and Alexandros Ntoulas, Releasing search queries and clicks privately, Proceedings of the 18th international conference on World wide web, 2009, pp. 171--180

    2009

  22. [30]

    15586--15622

    Alkis Kalavasis, Amin Karbasi, Shay Moran, and Grigoris Velegkas, Statistical indistinguishability of learning algorithms, International Conference on Machine Learning, PMLR, 2023, pp. 15586--15622

    2023

  23. [31]

    Aryeh Kontorovich and Amichai Painsky, Distribution estimation under the infinity norm, arXiv preprint arXiv:2402.08422 (2024)

    2024 arXiv

  24. [32]

    Amin Karbasi, Grigoris Velegkas, Lin Yang, and Felix Zhou, Replicability in reinforcement learning, Advances in Neural Information Processing Systems 36 (2023), 74702--74735

    2023

  25. [33]

    Daniel Levy, Ziteng Sun, Kareem Amin, Satyen Kale, Alex Kulesza, Mehryar Mohri, and Ananda Theertha Suresh, Learning with user-level privacy, Advances in Neural Information Processing Systems 34 (2021), 12466--12479

    2021

  26. [34]

    Shay Moran, Hilla Schefler, and Jonathan Shafer, The bayesian stability zoo, Advances in Neural Information Processing Systems 36 (2023), 61725--61746

    2023

  27. [35]

    1, 145--147

    Norbert Sauer, On the density of families of sets, Journal of Combinatorial Theory, Series A 13 (1972), no. 1, 145--147

    1972

  28. [36]

    1, 247--261

    Saharon Shelah, A combinatorial problem; stability and order for models and theories in infinitary languages, Pacific Journal of Mathematics 41 (1972), no. 1, 247--261

    1972

  29. [37]

    436--445

    Leslie G Valiant, A theory of the learnable, Proceedings of the sixteenth annual ACM symposium on Theory of computing, ACM, 1984, pp. 436--445

    1984

  30. [38]

    Vapnik and A.Ya

    V.N. Vapnik and A.Ya. Chervonenkis, On the uniform convergence of relative frequencies of events to their probabilities., Theory of Probability and Its Applications (1971)

    1971

  31. [39]

    Vladimir Vapnik and Alexey Chervonenkis, Theory of pattern recognition, 1974

    1974

  32. [40]

    Jason Vander Woude, Peter Dixon, A Pavan, Jamie Radcliffe, and NV Vinodchandran, Geometry of rounding: Near optimal bounds and a new neighborhood sperner's lemma, arXiv preprint arXiv:2304.04837 (2023)

    2023 arXiv

Pith tools

Reviewed August 8, 2026 · model on record in the stance chip above.