Source-linked AI summary
Typical Stability
Raef Bassily, Yoav Freund
TL;DR
Differential-privacy-based approaches to generalization typically assume bounded-sensitivity queries and i.i.d. data. This paper introduces typical stability, which uses concentration instead, and shows it can control generalization in adaptive analysis with dependent data and non-bounded-sensitivity queries.
Problem
Prior differential-privacy approaches to generalization for real-valued queries assume bounded sensitivity and i.i.d. samples.
Source: §1 · p. 2Method
Typical stability requires output distributions to be close on a high-probability set of datasets and uses query concentration to support real-valued answer release.
Source: §1 · p. 2Results
Typically stable interactions give high-probability small generalization error for γn-concentrated queries, and the paper characterizes parameter degradation under adaptive composition.
Source: §1 · p. 3Takeaways & Limitations
The framework provides statistical accuracy guarantees for sequences of adaptively chosen concentrated queries, including settings with dependent samples and queries not necessarily of bounded sensitivity.
Source: §1 · p. 4The composition analysis in Section 4.1 is restricted to pure typical stability (τ = 0).
Source: §4.1 · p. 9
Abstract
from arXiv · showhide
In this paper, we introduce a notion of algorithmic stability called typical stability. When our goal is to release real-valued queries (statistics) computed over a dataset, this notion does not require the queries to be of bounded sensitivity -- a condition that is generally assumed under differential privacy [DMNS06, Dwork06] when used as a notion of algorithmic stability [DFHPRR15a, DFHPRR15b, BNSSSU16] -- nor does it require the samples in the dataset to be independent -- a condition that is usually assumed when generalization-error guarantees are sought. Instead, typical stability requires the output of the query, when computed on a dataset drawn from the underlying distribution, to be concentrated around its expected value with respect to that distribution. We discuss the implications of typical stability on the generalization error (i.e., the difference between the value of the query computed on the dataset and the expected value of the query with respect to the true data distribution). We show that typical stability can control generalization error in adaptive data analysis even when the samples in the dataset are not necessarily independent and when queries to be computed are not necessarily of bounded-sensitivity as long as the results of the queries over the dataset (i.e., the computed statistics) follow a distribution with a "light" tail. Examples of such queries include, but not limited to, subgaussian and subexponential queries. We also discuss the composition guarantees of typical stability and prove composition theorems that characterize the degradation of the parameters of typical stability under $k$-fold adaptive composition. We also give simple noise-addition algorithms that achieve this notion. These algorithms are similar to their differentially private counterparts, however, the added noise is calibrated differently.
1 Introduction
Typical stability offers an alternative to stability approaches that assume bounded-sensitivity queries and independent samples: it relies instead on concentration of query outputs and supports generalization in adaptive analysis.
1 Introduction
- Typical stability replaces bounded-sensitivity and i.i.d. requirements with concentration around the query’s expected value and closeness of outputs on typical datasets.Outputs should conceal which typical dataset was used while revealing information shared across those datasets.Source: §1 · p. 2
- Subgaussian, sub-exponential, and jointly Gaussian queries are examples of concentrated query classes considered in the paper [RZ15] [WLF16].Concentration is defined through a high-probability bound on the query’s generalization error.Source: §1 · p. 3
- Typical stability is closed under post-processing and composition, with a theorem characterizing parameter degradation under adaptive composition.The theorem covers sequences of arbitrarily and adaptively chosen typically stable algorithms operating on the same dataset.Source: §1 · p. 3
- Typically stable interactions yield high-probability small generalization error for γn-concentrated queries, so those queries do not overfit to the dataset.The paper presents this as a generalization guarantee that also applies when samples are dependent and queries are not necessarily bounded-sensitivity.Source: §1 · pp. 2–3
- Laplace and Gaussian noise mechanisms achieve pure and approximate typical stability, with noise calibrated to the query answer’s confidence interval rather than sensitivity.The mechanisms resemble their differential-privacy counterparts, but use a different calibration.Source: §1 · p. 3
- Typical stability’s properties and accuracy guarantees provide an approach to answering adaptively chosen concentrated queries with statistical accuracy, even for dependent data.The paper notes correlated graph nodes as an example of dependent dataset entries whose computed statistics may still be well concentrated.Source: §1 · pp. 3–4
- Perfect generalization is a special case of typical stability for i.i.d. datasets, while typical stability differs from distributional privacy’s without-replacement setting.The paper states that its positive results therefore apply to perfect generalization as well [CLN+26].Source: §1 · p. 4
2 Definitions
The section defines typical stability through indistinguishability of algorithm outputs on typical datasets, then formalizes concentrated queries whose values stay near their distributional means. It relates these queries to familiar classes, including classes that extend beyond low-sensitivity queries.
2 Definitions
- (η,τ)-indistinguishability requires each measurable event's probability under either distribution to be at most e^η times the other's, plus τ.Source: §2 · p. 4
2.1 Typical Stability
- Typical stability compares an algorithm's output on a dataset drawn from P with an oracle output depending only on P, except with probability ν.Source: §2.1 · p. 5
- The pairwise formulation compares outputs on two independent datasets, and the oracle-based definition implies it with parameters (2η,3τ,2ν).Source: §2.1 · p. 5
2.2 Queries
- A γ_n-concentrated query lies within α of its expectation under P with probability at least 1−e^−γ_n(α).Source: §2.2 · p. 5
- Subgaussian and subexponential queries can be concentrated without bounded sensitivity, making the γ_n-concentrated class strictly larger than low-sensitivity queries.Such concentration can also occur for non-product distributions, including correlated-node graphs under suitable assumptions.Source: §2.2 · p. 6
3 Basic Properties of Typical Stability
The section establishes closure and composition properties of typical stability, then uses a near-independence result to connect stable interactions with generalization guarantees for concentrated queries.
3.1 Closure under post-processing and non-adaptive composition
- Post-processing preserves (η,τ,ν)-typical stability, while non-adaptive composition of k algorithms with independent random coins gives parameters (kη,kτ,kν).Source: §3.1 · pp. 6–7
3.2 Typical stability and the Near-Independence property
- Typical stability makes the joint distribution of dataset and algorithm output close to the product of their marginal distributions.Source: §3.2 · p. 7
3.3 Generalization via Typical Stability
- A typically stable algorithm that outputs a γ_n-concentrated query bounds its generalization error by α with high probability when ν=e^−γ_n(α).Source: §3.3 · p. 8
4 Adaptive Composition of Typically Stable Algorithms
The section characterizes how typical-stability parameters change under adaptive composition, treating pure and approximate stability separately. Its proof controls bad input-output pairs across successive rounds, with the approximate case requiring additional bad-set handling.
4.1 Composition of pure typically stable algorithms
- Under k-fold adaptive composition, pure typically stable algorithms remain typically stable with parameters η*, τ*, and ν* specified by the composition theorem.The theorem assumes k ≥ 2, η > 0, 0 ≤ ν < 1, and 0 < τ′ < 1.Source: §4.1 · p. 9
- For pure stability, ν* does not scale linearly with k; a simple union bound is inappropriate because conditioning on prior outputs changes the data distribution.The theorem’s proof prunes bad input-output pairs at each step and uses Azuma’s inequality to control the joint distribution.Source: §4.1 · pp. 9–10
4.1.1 Proof of Theorem 4.2
- The pure-composition proof inductively bounds the additional bad measure at each round, then uses a conditioning lemma to establish typical stability.It compares each algorithm’s output distribution with an oracle output distribution and prunes pairs that fail the indistinguishability condition.Source: §4.1 · pp. 9–10
4.2 Composition of approximate typically stable algorithms
- For approximate stability, k-fold composition also yields typical stability with theorem-specified parameters, under η ∈ (0, 3/2], τ ∈ (0, η/50], ν ∈ (0, 1), and τ′ ∈ (0, 1).The proof follows the pure-case paradigm but accounts for an additional sequence of bad sets because τ > 0.Source: §4.2 · p. 14
5 Typically Stable Algorithms for Answering Concentrated Queries
The paper gives Laplace and Gaussian noise-adding mechanisms for answering concentrated real-valued queries. Their noise is calibrated to query concentration rather than global sensitivity, and the mechanisms satisfy pure or approximate typical stability.
Approximate Gaussian mechanism
- For the Gaussian mechanism, the noise standard deviation is approximately α/η, where α is the concentration scale described for the query.The mechanism’s noise is proportional to the width of the query answer’s confidence interval, rather than global or smoothed local sensitivity.Source: §5 · p. 15
Pure Laplace mechanism
- The Laplace mechanism answers γn-concentrated queries with pure typical stability, and its noise is calibrated to how concentrated the query output is around its expectation.The paper contrasts this calibration with differential privacy’s global-sensitivity calibration.Source: §5 · p. 15
- With probability at least 1 − β, the Laplace mechanism’s output satisfies |w − q(x)| < α ln(1/β).This is the stated empirical-error bound for Algorithm 2.Source: §5 · p. 16
Approximate Gaussian mechanism
- The Gaussian mechanism answers γn-concentrated queries with approximate typical stability by adding Gaussian noise calibrated to query concentration.The theorem states that Algorithm 3 is (η, τ, ν)-typically stable for any distribution P over X^n.Source: §5 · pp. 15–16
- With probability at least 1 − β over Algorithm 3’s random coins, its output is within the theorem’s stated error threshold of q(x).The supplied theorem passage gives the probability statement but not the threshold value.Source: §5 · p. 16
6 Applications in Adaptive Data Analysis
The section applies typical stability to answering adaptively chosen concentrated queries. It states a high-probability upper bound on the worst true error across the answers, drawing on generalization, adaptive composition, and mechanism guarantees.
6 Applications in Adaptive Data Analysis
- The interaction proceeds for k rounds: the analyst chooses each query using prior queries and answers, and Algorithm 2 returns an answer.Figure 1 depicts this adaptive interaction.Source: §6 · p. 17, Figure 1 · p. 17
- The bound combines typical stability’s generalization guarantees, adaptive-composition guarantees, and the accuracy guarantees of Algorithm 2.The section notes that similar guarantees can also be obtained for Algorithm 3.Source: §6 · p. 17
- Theorem 6.1 bounds the worst true error across the answers to k adaptively chosen γn-concentrated queries.The theorem’s probability covers randomness in the analyst’s query choices, the algorithm’s answers, and the input dataset X ∼ P.Source: §6 · p. 17
Appendix A Proof of Theorem 4.8
The appendix proves the approximate adaptive-composition theorem by adapting the pure-case proof. It introduces additional bad-set controls for approximate stability and uses induction to complete the argument.
Appendix A Proof of Theorem 4.8
- The argument begins with a lemma that plays a role similar to Lemma 4.3 in the proof of Theorem 4.2, although its statement and proof differ from Lemma 4.3.Source: Appendix A · p. 20
- The proof defines sequences of sets for input-output pairs and a set of good inputs and outputs, then establishes lemmas that support the induction.The stated lemma premise involves a bound with μ* ≥ j(ν + τ̂).Source: Appendix A · p. 20
- The proof completes the approximate-composition theorem by combining its lemmas and inducting from the base case j = 1.The appendix identifies Lemma A.1, A.4, and A.5 as the lemmas used.Source: Appendix A · pp. 23–24