Efficient Agnostic Learning of Univariate Densities Under Local Differential Privacy

Introduction

• Model misspecification motivates agnostic learning, which measures error against the best approximation within the chosen class rather than requiring the true distribution to belong to it.The paper focuses on computationally efficient agnostic learning for structured distributions.Source: §1 · p. 1
• Samples may reveal sensitive information about individuals, motivating distribution learners that combine privacy protection with agnostic accuracy guarantees.Differential privacy limits the effect of any individual’s data on the learner’s output.Source: §1 · p. 2
• Prior work learned structured distributions through piecewise polynomials without privacy and in the central model, but no such algorithm was known in the local model.Piecewise-polynomial methods apply to classes including Gaussian mixtures and mixtures of log-concave distributions [CDSS14; ADLS17]; the paradigm was extended to central differential privacy.Source: §1 · p. 2
• The motivating questions ask whether LDP learning of structured distributions can be sample-efficient, agnostic, time-efficient, and non-interactive.Source: §1 · p. 2

Summary of our contribution

• The paper’s framework gives the first sample-efficient, non-interactive LDP learners for structured univariate distributions approximable by piecewise polynomials, with agnostic guarantees and computational efficiency.Its applications include bounded-parameter Gaussian mixture models and mixtures of log-concave distributions.Source: §1 · p. 2

Locally private agnostic learning of distributions

• An ε-local randomizer bounds the probability of any report event by a factor e^ε between any two possible inputs.Source: §2 · p. 3
• A non-interactive ε-LDP algorithm applies independently randomized local reports to users’ data, then aggregates those reports.Source: §2 · p. 3
• The agnostic task takes independent samples from arbitrary P and seeks a non-interactive ε-LDP output distribution satisfying the approximation guarantee with probability at least 1−β.The output may lie outside F; when P belongs to F, the guarantee reduces to total variation error at most α.Source: §2 · p. 3
• Unbounded classes such as unbounded univariate Gaussians lack a uniform LDP sample-complexity upper bound, so the paper restricts attention to classes with boundedness assumptions on parameters.The cited pure-DP packing lower bounds apply in both central and local models.Source: §2 · p. 3
• The (R, δ)-discretization error measures the worst-case L1 difference between a class density and its grid histogram, including two tail bins.The grid has step size δ on [−R, R].Source: §2 · p. 3
• A function in P_s,d is nonnegative and integrable, and is polynomial of degree at most d on each of at most s intervals partitioning R.The class’s (s, d)-piecewise-polynomial approximation error is the worst-case, over F, best L1 approximation by a function in P_s,d.Source: §2 · pp. 3–4

Main results and contributions

• Under a discretization-error condition, an efficient non-interactive ε-LDP algorithm generates O(1/α) synthetic samples with Kolmogorov accuracy Θ(α).The stated success probability is at least 0.9.Source: §3 · p. 4
• A lazy adaptation of a range-query mechanism answers queries in time polylogarithmic in domain size, enabling efficient private synthetic data generation.The passage contrasts this with existing sample-efficient mechanisms that require processing the entire domain.Source: §3 · p. 4
• Bounded-parameter mixtures of log-concave distributions and Gaussians admit computationally efficient, non-interactive ε-LDP (10, α, 0.1)-agnostic learners.The supplied theorem passages do not expose the full sample-complexity expressions.Source: §3 · pp. 4–5
• The GMM lower bound is Ω(m²), matches the upper bound’s dependence on m, ε, and α up to logarithmic factors, and requires parameter restrictions for uniform finite sample complexity.The lower bound holds even in the realizable setting with non-proper outputs and also applies to mixtures of log-concave distributions.Source: §3 · p. 5
• For univariate Gaussians, the framework provides agnostic total-variation guarantees with sample-complexity rates matching realizable mean estimation up to logarithmic factors.The specialized Gaussian learner improves the dependence on α in both sample complexity and running time over the Gaussian-mixture-as-log-concave-mixture approach.Source: §3 · p. 5
• For discrete and sparse distributions embedded as piecewise-constant densities, the framework gives agnostic guarantees while losing only logarithmic factors in sample complexity.The passages identify both classes as applications of the framework.Source: §3 · p. 5
• The learners are non-proper; conversion to proper learners preserves asymptotic sample complexity but can increase the agnostic approximation factor and make the algorithm inefficient.Source: §3 · p. 5
• The framework achieves an exponential sample-complexity improvement over generic LDP hypothesis-selection methods for proper learning of structured distributions.Source: §3 · p. 6

4 Related Work

• Existing central-DP work connects private Kolmogorov approximation to structured learning, but its threshold-release reduction relies on a mechanism unlike the local setting.That reduction uses the approximately differentially private threshold-release algorithm of Bun et al..Source: §4 · p. 6
• Locally private hypothesis selection achieves sample complexity eO(|F|^3/2/(ε^2α^2)) in a later result, with a worst-case lower bound Ω(|F|/(ε^2α^2)) even for interactive protocols.Earlier work gives eO(|F|^2/(ε^2α^2)).Source: §4 · p. 6
• Locally private hypothesis selection has sample and runtime costs polynomial in class size, while finite covers for Gaussian mixtures can be exponential in the component count.The framework instead exploits distributional structure for sample complexity and runtime polynomial in m and polylogarithmic in D.Source: §4 · p. 6

5 Preliminaries

• Total variation is half the L1 distance between distributions, while Kolmogorov distance is the supremum difference between their CDFs.The paper measures runtime in a unit-cost RAM model with exact real arithmetic and constant-time basic operations.Source: §5 · pp. 6–7

5.1 Locally private prefix frequencies

• A prefix can be decomposed into at most log2 N disjoint dyadic intervals, with at most one interval per depth, enabling its frequency to be obtained by summing interval frequencies.The decomposition takes O(log N) time; Hadamard randomized response is used to estimate dyadic interval frequencies.Source: §5.1 · pp. 7–8

5.2 A deterministic non-private piecewise polynomial learner

• A deterministic adaptation of Acharya et al.’s learner operates on synthetic data when its empirical distribution is sufficiently close in Kolmogorov distance to a target density.It returns a nonnegative piecewise-polynomial function supported on the given interval.Source: §5.2 · p. 8

6 Efficient locally private synthetic data generation

• The section’s two-stage construction first answers prefix queries on a fixed dataset, then uses the oracle to generate synthetic data approximating the discretized input in Kolmogorov distance.The synthetic data is designed to provide the approximation guarantee needed by the downstream non-private piecewise-polynomial learner.Source: §6 · p. 9

6.1 Lazy dyadic prefix mechanism

• PrefixQuery estimates all prefix frequencies to additive error α simultaneously with probability at least 1 − β, and each query takes O(n + log D) time.The server evaluates requested prefixes lazily, giving O(q(n + log D)) time for q queries rather than materializing the full hierarchy.Source: §6.1 · pp. 9–10

6.2 Efficient LDP synthetic dataset generation

• The synthetic-data algorithm places equally weighted points near quantile levels, using estimated CDF values and interpolation within bins to match those levels.Its privacy and utility theorem concerns Kolmogorov distance to the discretized input distribution; parameter choices relate that guarantee to the original distribution through tail and binning bounds.Source: §6.2 · pp. 11–12

7 Efficient LDP agnostic piece-wise polynomial learner

• The framework feeds private synthetic data into a deterministic adaptation of Acharya et al.’s piecewise-polynomial learner, accounting for discretization and target-class approximation error.The resulting guarantee combines these two sources of error.Source: §7 · p. 12
• Theorem 7.1 gives a non-interactive ε-LDP algorithm that outputs a distribution with a nonnegative piecewise-polynomial density and an agnostic guarantee relative to the best member of the known class.The theorem also provides a total running-time bound, including user preprocessing and server-side computation.Source: §7 · p. 12

8 Efficient LDP Agnostic Learning of Mixtures of Log-concave distributions

• The mixture class includes Gaussian mixtures and mixtures of uniform, exponential, Laplace, and logistic distributions, including mixtures with components from different families.Uniform finite sample-complexity bounds in the non-interactive LDP setting require bounded component parameter ranges.Source: §8 · p. 12

8.1 Mixture distributions

• Mixture approximation and discretization errors reduce to bounding the corresponding errors for the component class.The section controls truncation error with log-concave tail bounds and discretization error using unimodality and a density bound.Source: §8.1 · p. 13, §8.2 · pp. 13–14

8.2 An upper bound for mixtures of log-concave distributions

• The component class is defined by a log-concave density whose mean has absolute value at most R and whose standard deviation lies in [σmin, σmax].The discretization bound for this class, together with its piece-wise linear approximation bound, supplies the ingredients for applying the framework’s LDP learner.Source: §8.2 · pp. 13–14
• Theorem 8.5 gives an efficient non-interactive ε-LDP (10, α, β)-agnostic learner for mixtures of bounded-parameter log-concave distributions.Its output is a nonnegative piece-wise linear density with eO(m/√α) pieces.Source: §8.2 · p. 13
• For bounded-parameter log-concave distributions, piece-wise linear approximation achieves error at most α with s_α = eO(1/√α) pieces.The eO notation hides logarithmic factors in 1/α.Source: §8.2 · p. 14

AI Disclosure

• The authors report using AI to identify a connection to Cormode et al., check proofs, and identify algorithmic and theorem-statement edge cases, which they addressed.They state that all text, theorems, and proofs were written by the authors, with AI writing assistance limited to language and grammar refinement.Source: AI Disclosure · p. 14

A More on the related work

• Unlike prior LDP density estimators for specified Sobolev or Besov smoothness classes, the framework gives agnostic TV guarantees for bounded-parameter mixtures, including unbounded support or discontinuities.The prior works cited require the sampling density to belong to a specified smoothness class on a fixed bounded interval.Source: A More on the related work · p. 19
• Under the stated Huber contamination model, the framework implies dTV( P̂, F) ≤ (C + 1)η + α, but does not provide the stronger L2 or L∞ guarantees of Li et al..Their cited results assume the clean and contaminating distributions are supported on [0, 1], and the clean density belongs to a Sobolev class.Source: A More on the related work · p. 19
• Central-DP mixture learners can access the dataset jointly, whereas each user in this paper’s non-interactive local algorithms privatizes their own sample independently.The paper’s results are efficient agnostic learners for bounded-parameter univariate mixtures, with only logarithmic factors in component parameter ranges.Source: A More on the related work · p. 20

B Non-private piece-wise polynomial learner with synthetic data

• A suitable Kolmogorov-distance bound lets the deterministic adaptations of Acharya et al. operate on a supplied multiset instead of sampling from the unknown distribution.The Ak-distance condition established in the paper is what permits their error analyses to apply.Source: B Non-private piece-wise polynomial… · pp. 20–21
• CDF error controls Ak-distance: for the choice k = (C + 1)(d + 1)s, the proof obtains an Ak-distance bound of η.The proof applies Lemma B.2 to the CDF error bound in Proposition 5.4.Source: B Non-private piece-wise polynomial… · p. 20
• The adapted deterministic algorithms output a density with at most Cs pieces of degree at most d, with running time following from their algorithms on M input points.Converting Kolmogorov distance in the analysis requires no additional computation.Source: B Non-private piece-wise polynomial… · p. 21

C Omitted proofs from sections 5 and 6

• The canonical dyadic decomposition selects pairwise disjoint nodes whose union is exactly the prefix [1, j].The construction processes each depth once and builds the cover in O(log D) time.Source: C Omitted proofs from sections 5 and 6 · pp. 21–22
• The local randomizer is ε-LDP, and server-side prefix queries are post-processing of users’ independently generated transcripts, so the protocol remains non-interactive ε-LDP.The likelihood ratio for differing randomized-response signs is at most e^ε.Source: C Omitted proofs from sections 5 and 6 · pp. 22–23
• The prefix estimator is unbiased for each queried prefix indicator, and its per-user contribution is bounded in magnitude by L/θ_ε.The proof uses the disjoint dyadic cover and Hadamard orthogonality.Source: C Omitted proofs from sections 5 and 6 · p. 23
• Hoeffding’s inequality and a union bound over prefixes yield the stated simultaneous prefix-accuracy guarantee under the theorem’s sample-size condition.Clipping the estimates to [0, 1] does not increase their distance from the true prefix frequencies.Source: C Omitted proofs from sections 5 and 6 · pp. 23–24
• For q ≥ 1 prefix queries, the server-side protocol takes O(q(n + log D)) total time, including user preprocessing.Each user’s report takes O(1) time and space; one query scans n reports and constructs a dyadic cover.Source: C Omitted proofs from sections 5 and 6 · p. 24
• The discretization grid has D = ⌈2R/δ⌉ + 2 bins and L = O(log(R/δ)) levels when δ ≤ R/2.The stated condition is used only to simplify the bounds.Source: C Omitted proofs from sections 5 and 6 · pp. 24, 26
• The synthetic-data generator’s output CDF is within α of the discretized distribution’s CDF for every x, without requiring estimated prefix values to be monotone.The proof combines prefix-estimation accuracy with interpolation between grid points.Source: C Omitted proofs from sections 5 and 6 · pp. 25–26
• The synthetic-data algorithm uses M binary searches, each with at most L prefix queries, to construct its output.Computing interval indices and generating local randomized responses each take O(1) time per user.Source: C Omitted proofs from sections 5 and 6 · p. 26

• The proof obtains a synthetic multiset Z of size M on IR,δ and conditions on an event that holds with probability at least 1 − β.Source: D Proof of the main theorem from… · p. 26
• The deterministic piece-wise polynomial learner returns a nonnegative Q with ∥Q − eP∥1 ≤ 4 inf P′∈Ps,d ∥P′ − eP∥1 + 4α.Source: D Proof of the main theorem from… · p. 26
• The fit is compared with the best piece-wise polynomial approximation using ∥Q − eP∥1 ≤ 4α + 4 Poly-Approxs,d(F) + 4 Disc-ErrR,δ(F) + 4∥F − P∥1.Source: D Proof of the main theorem from… · p. 27
• Normalizing Q by its integral, or using Unif(IR,δ) when that integral is zero, yields an output whose L1 error is at most 2∥Q − eP∥1 and remains piece-wise polynomial.Source: D Proof of the main theorem from… · p. 27
• The final L1 error is bounded by 8α + 10∥F − P∥1 + 9 Disc-ErrR,δ(F) + 8 Poly-Approxs,d(F), with the bound then infimized over F ∈ F.Source: D Proof of the main theorem from… · p. 27
• Privacy and non-interactivity follow because fitting and normalization are post-processing; integration and normalization take O(s(d + 1)) additional operations absorbed in the runtime bound.Source: D Proof of the main theorem from… · p. 28

E Omitted proofs from section 8

• For log-concave mixtures, componentwise approximation and discretization bounds extend to mixtures; the resulting learner outputs eO(m/√α) linear pieces and is private and non-interactive.A log-concave density has a piecewise-linear approximation with error α and eO(1/√α) pieces, using Lemma 27 of Chan et al..Source: E Omitted proofs from section 8 · pp. 28, 30, 31

F Upper bound for GMMs

• For GMMs, the learner is non-interactive ε-LDP and (10, α, β)-agnostic, with output density using O(m) pieces of degree O(log(2/α)).Gaussian-specific approximation uses a number of pieces independent of α, yielding optimal sample dependence on accuracy; the stated running-time bound suppresses logarithmic factors in m and 1/α.Source: F Upper bound for GMMs · pp. 31–32

G Lower bound for LDP-learning of GMMs

• When Λ := R/σmin + log(σmax/σmin) is sufficiently large relative to m, non-interactive ε-LDP learning of m-component GMMs requires Ω(m^2) samples, even for non-proper learners.This lower bound matches the upper bound's dependence on the number of components, accuracy, and privacy up to logarithmic factors, and also applies to mixtures of log-concave distributions; it improves on pure-DP packing lower bounds.Source: G Lower bound for LDP-learning of GMMs · p. 33

H Discussion on proper learning and connections to Private Hypothesis Selection

• Proper projection preserves the non-proper learner's sample bound up to accuracy rescaling, but increases the agnostic approximation factor and can be computationally inefficient.For GMMs, the proper result has quadratic dependence on m up to logarithmic factors, polylogarithmic dependence on component-range parameters, and approximation factor 21; the finite cover affects projection computation, not sample complexity.Source: H Discussion on proper learning and… · p. 35
• For GMMs, finite-cover hypothesis selection has exponential sample complexity in m and polynomial dependence on R/(ασmin), unlike the paper's proper learner.The cited alternatives have sample bounds eO(|C|/(ε^2α^2)) with approximation factor 9 for Pour et al., and eO(|C|^(3/2)/(ε^2α^2)) with factor 13 for Kamath et al..Source: H Discussion on proper learning and… · p. 35
• A non-proper (C, α, β)-agnostic learner can be converted to a proper (2C + 1, 4α, β)-agnostic learner using the same samples and O(|C|(Tdist + 1)) additional time.The conversion approximately projects the learner’s output onto C by estimating its distance to each candidate and returning the closest; it preserves non-interactive ε-LDP by post-processing.Source: H Discussion on proper learning and… · pp. 35–36
• A non-interactive ε-LDP (21, α, β)-agnostic proper learner exists for bounded-parameter Gaussian mixtures, but is not claimed to be computationally efficient.The result combines the proper conversion, the finite cover, and Theorem F.2.Source: H Discussion on proper learning and… · p. 36
• For target additive error τ, the conversion with α = τ/4 and a τ/4-cover yields a proper (2C + 1, τ, β)-agnostic learner using nA(τ/4, β) samples.The simplex cover is formed by partitioning [0, 1]^m into cells and selecting a point from each cell intersecting the simplex.Source: H Discussion on proper learning and… · pp. 36–37
• The GMM cover discretizes weights, means, and standard deviations, with the resulting candidate mixtures belonging to the target class.Weights use an α/m-cover of the simplex; means use a grid on [−R, R], and standard deviations use a multiplicative grid over [σmin, σmax].Source: H Discussion on proper learning and… · p. 37