alphaFeedback

WorksComputer Science

Efficient and Optimal Learning of Discrete Distributions with Person-Level Privacy

AI contributions
Not recorded for this paper
View details

Abstract

We study learning a discrete distribution under person-level differential privacy in the batched setting. Given nn users, each contributing mm i.i.d. samples from an unknown distribution μμ over [k][k], we seek an estimate of μμ with total-variation error αα. We give polynomial-time algorithms under both pure and approximate differential privacy. Under pure (ε,0)(\varepsilon,0)-DP, we achieve n=O~(k/(α2m)+k/(αmε)+k/ε)n = \widetilde O(k/(α^2 m)+k/(α\sqrt{m}\varepsilon)+k/\varepsilon), the first polynomial-time pure-DP guarantee matching the information-theoretic optimum up to logarithmic factors. Under approximate (ε,δ)(\varepsilon,δ)-DP, we achieve n=O~(k/(α2m)+k/(αmε)+k+log⁡(1/δ)/ε)n = \widetilde O(k/(α^2 m)+k/(α\sqrt{m}\varepsilon)+k+\log(1/δ)/\varepsilon). At δ=2−Θ(k)δ=2^{-Θ(k)}, this is O~(k)\widetilde O(k) for fixed α,ε,mα,\varepsilon,m and failure probability. Our algorithms use a new degree-6 sum-of-squares estimator for learning from untrusted batches. Its key ingredient is a trace-bounded diagonal majorizer for the difference between the empirical covariance of the repaired batch averages and the multinomial covariance predicted by their mean. We prove that clean data admit this certificate through semidefinite-programming duality and a new application of the stronger symmetric form of Grothendieck's inequality due to Friedland and Lim. The certificate preserves the mean-dependent variance of multinomial batch averages, yielding the near-optimal robust rate O(ηlog⁡(1/η)/m)O(η\sqrt{\log(1/η)/m}) and providing the score required by the privacy reduction. We also prove a statistical query lower bound ruling out a uniformly smaller order of error under fixed polynomial SQ resource bounds.

*New York University ([email protected]). Supported by an NSERC Discovery Grant and an Ontario Early Researcher Award.

†Massachusetts Institute of Technology ([email protected]).

‡Massachusetts Institute of Technology ([email protected]). Supported in part by DARPA expMath, a Microsoft Trustworthy AI Grant, NSF-CCF 2430381, an ONR grant, and a David and Lucile Packard Fellowship.

§University of Texas at Austin and University of Waterloo ([email protected]). Supported by an Ontario Early Researcher Award and a David R. Cheriton Graduate Scholarship.

¶Northeastern University ([email protected]). Supported by NSF CNS-2232692 and CNS-2247484.

Introduction

Federated learning [MMR$^{+}$17, KMA$^{+}$21] is motivated by the tension between two important goals in modern machine learning:

  1. to train machine learning models from large and diverse data sets, and

  1. while doing so, to preserve the data privacy, security, and ownership of the data, since data is increasingly distributed across a network of devices.

Motivated by such considerations, Qiao and Valiant [QV18] introduced the following problem which they called learning from untrusted batches. There exists an unknown discrete distribution μ\mu on [k][k] and data is drawn in nn batches, each of size mm. When all batches are drawn i.i.d. from μ\mu and can be used without restriction, the empirical distribution achieves total-variation error α\alpha, provided that the number of batches satisfies

n=Θ(k+log⁡(1/β)α2m),n = \Theta\left(\frac{k + \log(1/\beta)}{\alpha^{2}m}\right),

where β\beta is the failure probability. This follows from the classical bound for nmnm independent samples [14].

However, in federated learning, we can rarely assume that all the batches are sampled i.i.d. from μ\mu, and instead must consider the possibility that some are corrupted, possibly in an adversarial way. To address this question, Qiao and Valiant studied the problem with the twist that an η\eta-fraction of the batches are adversarially corrupted. Again, it is helpful to compare to a naive baseline. If we ignore the batch structure and treat the data as a single dataset of nmnm samples, then it is easy to see that we cannot learn the distribution to accuracy better than η\eta in total variation distance, no matter how much data we have. Qiao and Valiant demonstrated that when we exploit the batched structure of the data, it is possible to do much better. In particular, they showed that it is information-theoretically possible to achieve error O(η/m)O(\eta/\sqrt{m}), and that this is the best possible. Batch information makes it possible to robustly distinguish distributions at much finer scale. Without batch information, we cannot distinguish two distributions μ\mu and μ~\tilde{\mu} that are γ\gamma-close in total variation distance in the face of an adversary, because they can convert one distribution to the other by moving just a γ\gamma fraction of the probability mass. But when data is batched and the adversary’s corruptions must respect the batch structure, the total variation distance between μ⊗m\mu^{\otimes m} and μ~⊗m\tilde{\mu}^{\otimes m} grows at least as Ω(min⁡{1,γm})\Omega(\min\{1,\gamma\sqrt{m}\}), meaning the adversary has to corrupt a much larger fraction of batches to make these distributions indistinguishable.

Qiao and Valiant gave two algorithms that solve the learning from untrusted batches problem, running in time exponential in kk or mm, respectively. Jain and Orlitsky [JO20b] gave a semidefinite-programming algorithm based on Grothendieck’s inequality that roughly matches the information-theoretic bounds and runs in polynomial time. In independent and concurrent work, Chen, Li, and Moitra [19] gave similar algorithms and explored extensions to more complex settings, including improving sample complexity when there are shape constraints on μ\mu.

Qiao and Valiant motivated their model by the need to learn from batches supplied by potentially malicious agents. Privacy, communication, and computational costs are also central concerns in federated learning. Keeping raw data local does not by itself ensure privacy: shared gradients can still leak private training data [ZLH19].

In this work, we revisit the learning from batches problem using the lens of differential privacy [30]. There is an unknown discrete distribution μ\mu on [k][k] and data is drawn in $n batches of size mm. As is common in federated learning, we think of each batch of data as belonging to one person (e.g. a batch consists of the data on one person’s device), and want to design a batch-level differentially private1 algorithm that, informally, hides the information of any one batch of data. Formally, two datasets are adjacent if they differ in one person’s entire batch. Batch-level privacy protects a person’s entire contribution, whereas sample-level privacy protects only one data item. Differential privacy bounds how much the output distribution can change when one person’s data is replaced.

We pursue three goals. First, we require the strong guarantee of pure batch-level differential privacy, formally (ε,0)(\varepsilon, 0)-DP.2 Second, we seek the information-theoretically optimal user complexity. Prior work established that, up to logarithmic factors, the optimum for learning to total-variation error α\alpha is [GKK+23b, Theorem 43]

n=O~(kα2m+kαmε+kε).n = \widetilde{O}\left(\frac{k}{\alpha^{2}m}+\frac{k}{\alpha\sqrt{m}\varepsilon}+\frac{k}{\varepsilon}\right).

Our final goal is to attain this bound in polynomial time.

Several groups have considered private learning from batches, but none give an algorithm satisfying all three goals. Liu et al. [?] introduced the problem, giving an efficient algorithm achieving the weaker notion of approximate differential privacy, or, formally, (ε,δ)(\varepsilon,\delta)-differential privacy. One can strengthen the privacy guarantee of their algorithm to (ε,0)(\varepsilon,0)-differentially private by appealing to basic composition of pure differential privacy instead of advanced composition of approximate differential privacy [31], but doing so would increase the required number of batches by a poly⁡(k)\operatorname{poly}(k) factor and would not achieve optimal sample complexity. Ghazi, Kamath, Kumar, Manurangsi, Meka, and Zhang [?] presented a pure differentially private algorithm with the information-theoretically optimal sample complexity, but their stated construction applies private hypothesis selection over an exponentially large cover and is not polynomial-time.

We use the efficient robustness-to-privacy reduction of Hopkins, Kamath, Majid, and Narayanan [?]. Our contribution is to identify the robust certificate that makes this reduction work for discrete batches. It is a single degree-66 sum-of-squares (SoS) certificate that represents discarded batches, mean feasibility, and the mean-dependent covariance of multinomial batch averages. This certificate simultaneously yields a robust estimator and the score used for privacy.

Results

Our certificate is satisfied by clean data at the right scale, forces every feasible pseudo-mean to be close to the truth, remains stable when batches are discarded, and admits polynomial-time optimization. It yields the robust estimator in Theorem 1.1 and, through the reduction of Hopkins et al. [?], the private algorithms in Theorem 1.3.

Theorem 1.1 (Robust SoS Estimation from Discrete Batches). Let μ∈Δk−1\mu\in\Delta^{k-1}, β∈(0,1)\beta\in(0,1), and m∈Nm \in\mathbb{N}. Let η>0\eta> 0 be smaller than a sufficiently small absolute constant. Then there exists a polynomial-time algorithm, obtained by solving a degree-66 SoS relaxation, that takes in nn user batches of size mm forming an η\eta-corruption of independent clean batches

Bi⋆=(Ui,1⋆,…,Ui,m⋆),Ui,1⋆,…,Ui,m⋆∼iidμ,B_i^\star= (U_{i,1}^\star,\ldots,U_{i,m}^\star), \qquad U_{i,1}^\star,\ldots,U_{i,m}^\star\mathrel{\overset{\mathrm{iid}}{\sim}} \mu,

and outputs an estimate μ^\widehat{\mu} such that, with probability at least 1−β1-\beta,

∥μ^−μ∥TV≤O(ηlog⁡(1/η)m)\lVert\widehat{\mu}-\mu\rVert_{\mathrm{TV}} \le O\left(\eta\sqrt{\frac{\log(1/\eta)}{m}}\right)

provided that

n=Ω(k+log⁡(1/β)α2m)n=\Omega\left(\frac{k+\log(1/\beta)}{\alpha^{2}m}\right)

for α=Θ(ηlog⁡(1/η)/m)\alpha=\Theta\left(\eta\sqrt{\log(1/\eta)/m}\right).

Remark 1.2 (Robustness to per-batch distribution shift). Our robust estimator also tolerates mild heterogeneity across the clean batches, with the modified covariance allowance in Corollary 3.11. Namely, in addition to the η\eta-corruption model in Theorem 1.1, one may allow the samples in each clean batch ii to be drawn i.i.d. from a distribution μi\mu_i satisfying ∥μi−μ∥TV≤ω\lVert\mu_i-\mu\rVert_{\mathrm{TV}}\le\omega. In that case the guarantee worsens by only an additive O(ω)O(\omega) term, giving

∥μ^−μ∥TV≤O(ηlog⁡(1/η)m+ω).\lVert\widehat{\mu}-\mu\rVert_{\mathrm{TV}}\le O\left(\eta\sqrt{\frac{\log(1/\eta)}{m}}+\omega\right).

The diagonal-majorizer certificate defines a low-sensitivity, quasi-convex score (Definition 4.5), so the efficient robustness-to-privacy reduction gives the private guarantees stated next.

Theorem 1.3 (Main Result, Private Estimation from Discrete Batches). Let μ∈Δk−1\mu\in\Delta^{k-1} be a discrete distribution over [k][k]. Let α,β∈(0,1)\alpha,\beta\in(0,1), ε>0\varepsilon>0, and m∈Nm\in\mathbb{N}. Suppose that the batches are independent across users and each of the nn users contributes a batch

Bi=(Ui,1,…,Ui,m),Ui,1,…,Ui,m∼iidμ.B_i=(U_{i,1},\ldots,U_{i,m}),\qquad U_{i,1},\ldots,U_{i,m}\mathrel{\overset{\mathrm{iid}}{\sim}}\mu.

Then the following guarantees hold.

(i) There is a polynomial-time (ε,0)(\varepsilon,0)-DP algorithm that outputs μ^\widehat{\mu} satisfying ∥μ^−μ∥TV≤α\lVert\widehat{\mu}-\mu\rVert_{\mathrm{TV}}\le\alpha with probability at least 1−β1-\beta, provided

n=O~(k+log⁡(1/β)α2m+k+log⁡(1/β)αm ε+k+log⁡(1/β)ε).n=\widetilde{O}\left(\frac{k+\log(1/\beta)}{\alpha^{2}m}+\frac{k+\log(1/\beta)}{\alpha\sqrt{m}\,\varepsilon}+\frac{k+\log(1/\beta)}{\varepsilon}\right).

(ii) For every δ∈(0,1)\delta\in(0,1), there is a polynomial-time (ε,δ)(\varepsilon,\delta)-DP algorithm with the same accuracy and failure probability, provided

n=O~(k+k+log⁡(1/β)α2m+k+log⁡(1/β)αm ε+log⁡(1/δ)+log⁡(1/β)ε).n=\widetilde{O}\left(k+\frac{k+\log(1/\beta)}{\alpha^{2}m}+\frac{k+\log(1/\beta)}{\alpha\sqrt{m}\,\varepsilon}+\frac{\log(1/\delta)+\log(1/\beta)}{\varepsilon}\right).

The O~\widetilde{O} notation suppresses logarithmic factors in 1/α1/\alpha; Remark 4.16 gives explicit bounds, including the square-root logarithm in the approximate-DP privacy term. Our pure-DP rate matches known lower bounds up to logarithmic factors [LSY+20, GKK+23b]; Theorem B.5 gives the dependence on the failure probability explicitly.

Prior polynomial-time approximate-DP results cover different user regimes. Suppressing logarithmic factors other than those displayed below, the relevant privacy terms and user-count requirements are

Liu et al. [LSY+20]:

klog⁡(1/δ)αεm,n≳klog⁡(1/δ)ε.\frac{k\sqrt{\log(1/\delta)}}{\alpha\varepsilon\sqrt{m}},\qquad n\gtrsim\frac{\sqrt{k\log(1/\delta)}}{\varepsilon}.

(few users) Esfandiari et al. [32]:

klog⁡(k/δ)log⁡(1/δ)log⁡(kn/β)αεm,n≳log⁡(1/(βδ))ε.\frac{k\log(k/\delta)\sqrt{\log(1/\delta)\log(kn/\beta)}}{\alpha\varepsilon\sqrt{m}},\qquad n\gtrsim\frac{\log(1/(\beta\delta))}{\varepsilon}.

Esfandiari et al.’s few-user guarantee removes the dimension-dependent user floor required by Liu et al. Their all-regime result combines this guarantee with earlier algorithms for the high-user regime; its larger logarithmic factor is the cost of reaching the few-user regime. For negligible approximate-privacy parameters δ=2−kΩ(1)\delta= 2^{-k^{\Omega(1)}} and fixed α,ε,m\alpha,\varepsilon,m, the privacy terms of both Liu et al. and Esfandiari et al. are superlinear in kk. Our bound has additive dependence on log⁡(1/δ)\log(1/\delta) and includes a O~(k)\widetilde{O}(k) user term for clean-data feasibility. At δ=2−Θ(k)\delta= 2^{-\Theta(k)}, our bound is O~(k)\widetilde{O}(k) for fixed α,ε,m\alpha,\varepsilon,m, and failure probability.

Dependence on the batch size. For constant failure probability and 0<ε≤10 < \varepsilon\le1, when αm≤1\alpha\sqrt{m} \le1, the term k/(αm ε)k/(\alpha\sqrt{m}\,\varepsilon) absorbs k/εk/\varepsilon, so the pure-DP theorem already gives the approximate-DP rate up to logarithmic factors. When αm≥1\alpha\sqrt{m} \ge1, we cap the internal corruption parameter at a sufficiently small constant. The robust error is then at most α\alpha, giving a pure-DP rate of O~(k/ε)\widetilde{O}(k/\varepsilon).

The additional kk in the approximate-DP bound is inherent in using our robust estimator at its stated accuracy. For any fixed sufficiently small corruption fraction η\eta, Theorem 1.1 guarantees error O(ηlog⁡(1/η)/m)=O(1/m)O(\eta\sqrt{\log(1/\eta)/m}) = O(1/\sqrt{m}), which requires Ω(k)\Omega(k) users even without corruptions or privacy. Indeed, the nonprivate sample bound Ω(k/(α2m))\Omega(k/(\alpha^{2}m)) becomes Ω(k)\Omega(k) at this accuracy. This requirement is already implicit in the robust theorem through α=Θ(ηlog⁡(1/η)/m)\alpha= \Theta(\eta\sqrt{\log(1/\eta)/m}), and is absorbed by k/εk/\varepsilon for pure DP. It appears explicitly for approximate DP because the other terms can be smaller than kk.

For larger batches, the target error α\alpha can be much larger than 1/m1/\sqrt{m}, and approximate DP can use fewer than kk users [32]. Exploiting this regime through robustness-to-privacy requires a robust guarantee adapted to the coarser target accuracy. Remark 4.17 describes how splitting batches reduces the user requirement while retaining additive dependence on log⁡(1/δ)\log(1/\delta), and how to combine our estimator with that of Esfandiari et al. using only the public parameters.

On optimality under efficient computation. Our polynomial-time robust algorithm achieves error O(ηlog⁡(1/η)/m)O(\eta\sqrt{\log(1/\eta)/m}), while the information-theoretic optimum is O(η/m)O(\eta/\sqrt{m}) [QV18]. Such an extra log⁡(1/η)\sqrt{\log(1/\eta)} factor has precedent in statistical query (SQ) lower bounds for robust estimation of binary product distributions [28] and Gaussians [27]. In § 5, we prove a lower bound directly for categorical batches. For every fixed integer t≥1t \ge1, we give a query–tolerance tradeoff at error a constant ct>0c_t > 0 times

ηmin⁡{1,log⁡(1/η)m}.\eta\min\left\{1,\sqrt{\frac{\log(1/\eta)}{m}}\right\}.

References

  1. [1][ABMT25] Prashanti Anderson, Ainesh Bakshi, Mahbod Majid, and Stefan Tiegel. Sample-optimal private regression in polynomial time. In Proceedings of the 57th Annual ACM Symposium on the Theory of Computing, STOC ’25, pages 2341–2349. ACM, 2025.arxiv.org/abs/2503.24321
  2. [2][AKM+25] Sushant Agarwal, Gautam Kamath, Mahbod Majid, Argyris Mouzakis, Rose Silver, and Jonathan Ullman. Private mean estimation with person-level differential privacy. In Proceedings of the 36th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA ’25, pages 2819–2880. SIAM, 2025.arxiv.org/abs/2405.20405
  3. [3][AKT+23] Daniel Alabi, Pravesh K Kothari, Pranay Tankala, Prayaag Venkat, and Fred Zhang. Privately estimating a Gaussian: Efficient, robust, and optimal. In Proceedings of the 55th Annual ACM Symposium on the Theory of Computing, STOC ’23, pages 483–496. ACM, 2023.arxiv.org/abs/2212.08018
  4. [4][AL22] Hassan Ashtiani and Christopher Liaw. Private and polynomial time algorithms for learning Gaussians and beyond. In Proceedings of the 35th Annual Conference on Learning Theory, volume 178 of Proceedings of Machine Learning Research, pages 1075–1076. PMLR, 2022.arxiv.org/abs/2111.11320
  5. [6][ALS23] Jayadev Acharya, Yuhan Liu, and Ziteng Sun. Discrete distribution estimation under user-level local differential privacy. In Proceedings of the 26th International Conference on Artificial Intelligence and Statistics, volume 206 of Proceedings of Machine Learning Research, pages 8561–8585. PMLR, 2023.arxiv.org/abs/2211.03757
  6. [7][AM20] Marco Avella-Medina. The role of robust statistics in private data analysis. Chance, 33(4):37–42, 2020.
  7. [8][AM21] Marco Avella-Medina. Privacy-preserving parametric inference: a case for robust statistics. Journal of the American Statistical Association, 116(534):969–983, 2021.
  8. [9][AMN24] Hassan Ashtiani, Mahbod Majid, and Shyam Narayanan. Sample-efficient private learning of mixtures of Gaussians. In Advances in Neural Information Processing Systems 37, NeurIPS ’24, pages 98994–99039. Curran Associates, Inc., 2024.arxiv.org/abs/2411.02298
  9. [10][AUZ23] Hilal Asi, Jonathan Ullman, and Lydia Zakynthinou. From robustness to privacy and back. In Proceedings of the 40th International Conference on Machine Learning, volume 202 of Proceedings of Machine Learning Research, pages 1121–1146. PMLR, 2023.arxiv.org/abs/2302.01855
  10. [12]Mark Bun, Gautam Kamath, Thomas Steinke, and Zhiwei Steven Wu. Private hypothesis selection. In Advances in Neural Information Processing Systems 32, NeurIPS ’19, pages 156–167. Curran Associates, Inc., 2019.arxiv.org/abs/1905.13229
  11. [14]Clément L. Canonne. A short note on learning discrete distributions. arXiv preprint arXiv:2002.11457, 2020.arxiv.org/abs/2002.11457
  12. [15]Hongjie Chen, Jingqiu Ding, Tommaso d’Orsi, Yiding Hua, Chih-Hung Liu, and David Steurer. Private graphon estimation via sum-of-squares. In Proceedings of the 56th Annual ACM Symposium on the Theory of Computing, STOC ’24, pages 172–182. ACM, 2024.arxiv.org/abs/2403.12213
  13. [16]Hongjie Chen, Jingqiu Ding, Yiding Hua, and David Steurer. Private edge density estimation for random graphs: Optimal, efficient and robust. In Advances in Neural Information Processing Systems 37, NeurIPS ’24, pages 90771–90817. Curran Associates, Inc., 2024.arxiv.org/abs/2405.16663
  14. [17]Sitan Chen, Jingqiu Ding, Mahbod Majid, and Walter McKelvie. Computation-utility-privacy tradeoffs in Bayesian estimation. In Proceedings of the 58th Annual ACM Symposium on the Theory of Computing, STOC ’26, pages 1616–1626. ACM, 2026.
  15. [18]Rachel Cummings, Vitaly Feldman, Audra McMillan, and Kunal Talwar. Mean estimation with user-level privacy under data heterogeneity. In Advances in Neural Information Processing Systems 35, NeurIPS ’22, pages 29139–29151. Curran Associates, Inc., 2022.
  16. [19]Sitan Chen, Jerry Li, and Ankur Moitra. Efficiently learning structured distributions from untrusted batches. In Proceedings of the 52nd Annual ACM Symposium on the Theory of Computing, STOC ’20, pages 960–973. ACM, 2020.
  17. [20]Sitan Chen, Jerry Li, and Ankur Moitra. Learning structured distributions from untrusted batches: Faster and simpler. In Advances in Neural Information Processing Systems 33, NeurIPS ’20, pages 4512–4523. Curran Associates, Inc., 2020.
  18. [21]Julien Chhor and Flore Sentenac. Robust estimation of discrete distributions under local differential privacy. In Proceedings of the 34th International Conference on Algorithmic Learning Theory, volume 201 of Proceedings of Machine Learning Research, pages 411–446. PMLR, 2023.
  19. [22]Ilias Diakonikolas, Moritz Hardt, and Ludwig Schmidt. Differentially private learning of structured discrete distributions. In Advances in Neural Information Processing Systems 28, NIPS ’15, pages 2566–2574. Curran Associates, Inc., 2015.
  20. [23]Abhimanyu Das, Ayush Jain, Weihao Kong, and Rajat Sen. Efficient list-decodable regression using batches. In Proceedings of the 40th International Conference on Machine Learning, volume 202 of Proceedings of Machine Learning Research, pages 7025–7065. PMLR, 2023.arxiv.org/abs/2211.12743
  21. [24]Ilias Diakonikolas and Daniel M. Kane. Algorithmic High-Dimensional Robust Statistics. Cambridge University Press, 2023.DOI
  22. [25]Ilias Diakonikolas, Gautam Kamath, Daniel M. Kane, Jerry Li, Ankur Moitra, and Alistair Stewart. Robust estimators in high dimensions without the computational intractability. In Proceedings of the 57th Annual IEEE Symposium on Foundations of Computer Science, FOCS ’16, pages 655–664. IEEE Computer Society, 2016. Journal version: SIAM Journal on Computing, 48(2):742–864, 2019.arxiv.org/abs/1604.06443
  23. [26]Ilias Diakonikolas, Daniel Kane, Sushrut Karmalkar, Sihan Liu, and Thanasis Pittas. Batch list-decodable linear regression via higher moments. In Proceedings of the 42nd International Conference on Machine Learning, volume 267 of Proceedings of Machine Learning Research, pages 13622–13642. PMLR, 2025.arxiv.org/abs/2503.09802
  24. [27]Ilias Diakonikolas, Daniel M. Kane, and Alistair Stewart. Statistical query lower bounds for robust estimation of high-dimensional Gaussians and Gaussian mixtures. In Proceedings of the 58th Annual IEEE Symposium on Foundations of Computer Science, FOCS ’17, pages 73–84. IEEE Computer Society, 2017.arxiv.org/abs/1611.03473
  25. [28]Ilias Diakonikolas, Daniel M. Kane, and Yuxin Sun. Optimal SQ lower bounds for robustly learning discrete product distributions and Ising models. In Proceedings of the 35th Annual Conference on Learning Theory, volume 178 of Proceedings of Machine Learning Research, pages 3936–3978. PMLR, 2022.arxiv.org/abs/2206.04589
  26. [29]Cynthia Dwork and Jing Lei. Differential privacy and robust statistics. In Proceedings of the 41st Annual ACM Symposium on the Theory of Computing, STOC ’09, pages 371–380. ACM, 2009.DOI
  27. [30]Cynthia Dwork, Frank McSherry, Kobbi Nissim, and Adam Smith. Calibrating noise to sensitivity in private data analysis. In Proceedings of the 3rd Conference on Theory of Cryptography, TCC ’06, pages 265–284, Berlin, Heidelberg, 2006. Springer. Journal version: Journal of Privacy and Confidentiality, 7(3):17–51, 2017.
  28. [31]Cynthia Dwork, Guy N. Rothblum, and Salil Vadhan. Boosting and differential privacy. In Proceedings of the 51st Annual IEEE Symposium on Foundations of Computer Science, FOCS ’10, pages 51–60. IEEE Computer Society, 2010.DOI
  29. [32]Hossein Esfandiari, Vahab Mirrokni, and Shyam Narayanan. Tight and robust private mean estimation with few users. In Proceedings of the 39th International Conference on Machine Learning, volume 162 of Proceedings of Machine Learning Research, pages 16383–16412. PMLR, 2022.arxiv.org/abs/2110.11876
  30. [33]Shmuel Friedland and Lek-Heng Lim. Symmetric Grothendieck inequality. arXiv preprint arXiv:2003.07345, 2020.arxiv.org/abs/2003.07345
  31. [34]Antonious M Girgis, Deepesh Data, and Suhas Diggavi. Distributed user-level private mean estimation. In Proceedings of the 2022 IEEE International Symposium on Information Theory, ISIT ’22, pages 2196–2201. IEEE, 2022.DOI

Paper details

vlnc:W_5m2zmfqb
v1 · latestHistory (1)

published · Fresh — added to the Hub within the last 30 days

added ·

Usage

views · 0

downloads · 0

A view counts once per browser per day, a download each time the PDF is requested.

CC BY 4.0

Original source

  • Computer Science

Not recorded for this paper · View statement →

Looking for related papers…
Contents