pith. sign in

arxiv: 2605.15943 · v1 · pith:RT5JXJYJnew · submitted 2026-05-15 · 🧮 math.ST · stat.ML· stat.TH

Node-private community estimation in stochastic block models: Tractable algorithms and lower bounds

Laurentiu Marchis , Ethan D'souza , Tom\'a\v{s} Fl\'idr , Po-Ling Loh This is my paper

Pith reviewed 2026-05-19 19:06 UTC · model grok-4.3

classification 🧮 math.ST stat.MLstat.TH
keywords node differential privacystochastic block modelscommunity recoveryspectral clusteringgraph projectionsexponential mechanismlower boundspolynomial time algorithms
0
0 comments X

The pith

Consistent community recovery in stochastic block models is achievable under node differential privacy using new polynomial-time algorithms that require the privacy parameter epsilon to grow at a controlled rate.

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

The paper examines community recovery in stochastic block models where the graph must remain stable against changes to any single node's connections, a requirement formalized as node differential privacy. Straightforward applications of private spectral clustering or matrix methods demand that the privacy parameter epsilon increase rapidly with the number of nodes to maintain accuracy, which limits practicality. To address this, the authors introduce algorithms that sample from an exponential mechanism equipped with a Lipschitz extension and construct smooth projections mapping general undirected graphs onto bounded-degree graphs that can then use existing edge-private routines. These procedures run in time polynomial in the number of nodes and preserve the consistency of community estimates once epsilon grows sufficiently fast. The work also supplies matching lower bounds on the necessary growth rate of epsilon and notes technical issues that appear when analyzing privacy guarantees in the regime where epsilon tends to infinity.

Core claim

The central claim is that novel node-private algorithms based on exponential-mechanism sampling with Lipschitz extensions and on smooth projections from the space of undirected graphs to bounded-degree graphs can be combined with edge-private methods to achieve consistent community estimation in stochastic block models with a fixed number of communities, provided the privacy parameter epsilon grows at a rate sufficient to overcome the added sensitivity of node-level changes; polynomial-time computability holds for all proposed procedures, and lower bounds establish the minimal growth rate of epsilon needed for consistency.

What carries the argument

The central mechanism is a general framework for constructing smooth projections from the space of undirected graphs to the space of bounded-degree graphs, which reduces node-private problems to edge-private ones while preserving algorithmic tractability.

If this is right

  • Consistent community labeling is possible under node privacy whenever epsilon grows faster than the lower bound rate, using only polynomial-time procedures.
  • The same projection framework can be paired with multiple existing edge-private community estimators to obtain node-private versions.
  • Lower bounds show that epsilon must grow at least as fast as a specific function of the number of nodes to guarantee consistency.
  • Technical tools developed for the non-standard scaling epsilon to infinity may apply to other private estimation tasks on graphs.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • The projection technique could be tested on real social networks to measure how much the bounded-degree restriction distorts recovered communities compared with non-private baselines.
  • Similar smoothness-based reductions might simplify privacy analysis for other graph inference problems such as link prediction or ranking under node privacy.
  • The lower-bound construction suggests concrete regimes where node privacy forces a noticeable accuracy gap relative to edge privacy, which could be checked in small-scale synthetic experiments.

Load-bearing premise

The analysis assumes that the stochastic block model parameters permit consistent community recovery even without privacy, so that the privacy mechanisms need only preserve that non-private consistency once epsilon grows fast enough.

What would settle it

Observe whether, for any sequence of graphs drawn from a stochastic block model with fixed community number, every algorithm that keeps epsilon growing slower than the derived lower bound fails to output a community labeling whose agreement with the true partition tends to one with high probability as the number of nodes tends to infinity.

read the original abstract

We study the classical problem of community recovery in stochastic block models with a fixed number of communities, with a twist: We seek algorithms that are stable with respect to node-wise changes in the graph structure, formally defined as a differential privacy constraint. The algorithms we develop are based on spectral clustering, where we introduce privacy to the community recovery pipeline in the form of directly privatizing the adjacency matrix; private PCA; private convex optimization; private low-rank matrix estimation; and private approximate subspace estimation. Straightforward applications of existing private algorithms lead to a rapid increase in the privacy parameter $\epsilon$ in order to ensure consistent estimation under node differential privacy, in contrast with the simpler setting of edge privacy. To alleviate these issues, we develop novel algorithms based on (1) sampling from an exponential mechanism with a Lipschitz extension and (2) a general framework for constructing smooth projections from the space of undirected graphs to the space of bounded-degree graphs, which can then be combined with various edge-private algorithms. Importantly, the methods we develop are all computable in polynomial-time as a function of the number of nodes in the graph. We also develop novel lower bounds on the growth rate of $\epsilon$ required in order to achieve consistent community estimation under node privacy. On a technical note, our paper highlights the complications that arise when analyzing private algorithms under the non-standard scaling $\epsilon \rightarrow \infty$ and proposes some solutions. We also provide a novel application of the HGR maximal correlation from information theory in the context of accuracy amplification in PAC learning, which may be of independent interest.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

1 major / 3 minor

Summary. The manuscript studies community recovery in stochastic block models with a fixed number of communities under node differential privacy. It develops polynomial-time algorithms that privatize the adjacency matrix via private PCA, convex optimization, low-rank estimation, and approximate subspace methods, but observes that direct applications of existing techniques force ε to grow rapidly for consistency. Novel contributions include sampling from an exponential mechanism equipped with a Lipschitz extension and a general framework for smooth projections from undirected graphs onto bounded-degree graphs, which can then be paired with edge-private algorithms. The paper also derives lower bounds on the growth rate of ε needed for consistent node-private estimation, analyzes technical complications in the non-standard regime ε → ∞, and introduces a novel application of the HGR maximal correlation for accuracy amplification in PAC learning.

Significance. If the central claims hold, the work is significant for advancing the privacy-utility tradeoff in graph algorithms. It supplies the first set of tractable, polynomial-time node-DP algorithms for SBM community estimation together with matching lower bounds, addressing a stricter privacy model than the more common edge-DP setting. The Lipschitz-extension exponential mechanism and the smooth-projection framework are technically substantive and reusable; the explicit treatment of the ε → ∞ regime and the HGR-correlation technique for accuracy amplification constitute additional strengths with potential independent interest.

major comments (1)
  1. [§3.2] §3.2, the smooth-projection framework: the argument that the projection preserves the spectral gap (or likelihood properties) required for consistent recovery under the stated ε scaling appears to depend on a Lipschitz constant that grows with the imposed degree bound; this dependence must be tracked explicitly to confirm that the overall ε requirement remains sub-linear in n and matches the lower bound.
minor comments (3)
  1. [Abstract and §1] The abstract and §1 state that all methods are polynomial-time, but the computational cost of the Lipschitz extension sampling step should be stated with explicit dependence on n and the degree bound.
  2. [§4] Notation for the privacy parameter in the lower-bound section occasionally switches between ε and ε_n without a clear global definition; a single consistent symbol would improve readability.
  3. [Experimental section] Figure 2 (or the corresponding simulation table) reports recovery error versus ε but does not include error bars or the number of Monte-Carlo repetitions; this makes it difficult to assess variability of the empirical results.

Simulated Author's Rebuttal

1 responses · 0 unresolved

We thank the referee for the positive assessment and for identifying this point in §3.2. We will revise the manuscript to make the dependence explicit.

read point-by-point responses

  1. Referee: [§3.2] §3.2, the smooth-projection framework: the argument that the projection preserves the spectral gap (or likelihood properties) required for consistent recovery under the stated ε scaling appears to depend on a Lipschitz constant that grows with the imposed degree bound; this dependence must be tracked explicitly to confirm that the overall ε requirement remains sub-linear in n and matches the lower bound.

    Authors: We agree that the Lipschitz constant L of the smooth projection scales with the imposed degree bound D. In the current draft this dependence is implicit rather than fully expanded. In the revision we will add an explicit calculation showing L = O(D) (or the precise factor arising from the construction) and substitute the chosen D = polylog(n) into the spectral-gap perturbation bound. The resulting additive error remains o(1) under the same ε = o(log n) regime already stated, thereby preserving consistency and matching the lower bound derived later in the paper. The updated argument will appear in the revised §3.2 together with a short lemma isolating the L(D) factor. revision: yes

Circularity Check

0 steps flagged

No significant circularity in derivation chain

full rationale

The paper's algorithms are built from standard differential-privacy primitives (exponential mechanism with Lipschitz extension, smooth projections to bounded-degree graphs) applied to spectral clustering and related estimators for SBM community recovery. Lower bounds are information-theoretic and rest on the standard non-private consistency regime for SBM parameters. No load-bearing step reduces by construction to a fitted parameter from the same data, a self-citation chain, or an ansatz smuggled via prior work by the same authors. The analysis explicitly separates the non-private consistency assumption from the privacy overhead and shows polynomial-time computability without internal redefinition of the target quantities.

Axiom & Free-Parameter Ledger

0 free parameters · 2 axioms · 0 invented entities

The paper rests on the standard definition of node differential privacy and the usual stochastic block model generative assumptions (fixed number of communities, constant edge-probability parameters). No new free parameters are introduced beyond the privacy budget ε itself; no invented entities appear.

axioms (2)
  • domain assumption Stochastic block model with fixed number of communities and edge probabilities that permit consistent recovery in the non-private regime
    Invoked in the problem statement to define the target of consistent estimation under privacy.
  • standard math Standard definition of node differential privacy (adjacent graphs differ by one node and its incident edges)
    Used throughout to formalize the privacy constraint.

pith-pipeline@v0.9.0 · 5835 in / 1482 out tokens · 57203 ms · 2026-05-19T19:06:07.531719+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Lean theorems connected to this paper

Citations machine-checked in the Pith Canon. Every link opens the source theorem in the public Lean library.

What do these tags mean?
matches
The paper's claim is directly supported by a theorem in the formal canon.
supports
The theorem supports part of the paper's argument, but the paper may add assumptions or extra steps.
extends
The paper goes beyond the formal theorem; the theorem is a base layer rather than the whole result.
uses
The paper appears to rely on the theorem as machinery.
contradicts
The paper's claim conflicts with a theorem or certificate in the canon.
unclear
Pith found a possible connection, but the passage is too broad, indirect, or ambiguous to say the theorem truly supports the claim.

Reference graph

Works this paper leans on

74 extracted references · 74 canonical work pages · 6 internal anchors

  1. [1]

    E. Abbe. Community detection and stochastic block models: recent developments.Journal of Machine Learning Research, 18(177):1–86, 2018

    work page 2018

  2. [2]

    On Maximal Correlation, Hypercontractivity, and the Data Processing Inequality studied by Erkip and Cover

    V. Anantharam, A. Gohari, S. Kamath, and C. Nair. On maximal correlation, hypercontractivity, and the data processing inequality studied by Erkip and Cover.arXiv preprint arXiv:1304.6133, 2013

    work page internal anchor Pith review Pith/arXiv arXiv 2013

  3. [3]

    Avella-Medina

    M. Avella-Medina. Privacy-preserving parametric inference: A case for robust statistics.Journal of the American Statistical Association, 116(534):969–983, 2021

    work page 2021

  4. [4]

    Avella-Medina, C

    M. Avella-Medina, C. Bradshaw, and P. Loh. Differentially private inference via noisy optimization. The Annals of Statistics, 51(5):2067–2092, 2023

    work page 2067

  5. [5]

    Blocki, A

    J. Blocki, A. Blum, A. Datta, and O. Sheffet. The Johnson-Lindenstrauss transform itself preserves differential privacy. In2012 IEEE 53rd Annual Symposium on Foundations of Computer Science, pages 410–419. IEEE, 2012

    work page 2012

  6. [6]

    Blocki, A

    J. Blocki, A. Blum, A. Datta, and O. Sheffet. Differentially private data analysis of social networks via restricted sensitivity. InProceedings of the 4th conference on Innovations in Theoretical Computer Science, pages 87–96, 2013

    work page 2013

  7. [7]

    A. Blum, J. Hopcroft, and R. Kannan.Foundations of Data Science. Cambridge University Press, 2020

    work page 2020

  8. [8]

    Borgs, J

    C. Borgs, J. Chayes, and A. Smith. Private graphon estimation for sparse graphs.Advances in Neural Information Processing Systems, 28, 2015

    work page 2015

  9. [9]

    Private Algorithms Can Always Be Extended

    C. Borgs, J. Chayes, A. Smith, and I. Zadik. Private algorithms can always be extended.arXiv preprint arXiv:1810.12518, 2018

    work page internal anchor Pith review Pith/arXiv arXiv 2018

  10. [10]

    Borgs, J

    C. Borgs, J. Chayes, A. Smith, and I. Zadik. Revealing network structure, confidentially: Improved rates for node-private graphon estimation. In2018 IEEE 59th Annual Symposium on Foundations of Computer Science (FOCS), pages 533–543. IEEE, 2018

    work page 2018

  11. [11]

    Bun and T

    M. Bun and T. Steinke. Concentrated differential privacy: Simplifications, extensions, and lower bounds. InTheory of Cryptography Conference, pages 635–658. Springer, 2016

    work page 2016

  12. [12]

    T. T. Cai, Y. Wang, and L. Zhang. The cost of privacy: Optimal rates of convergence for parameter estimation with differential privacy.The Annals of Statistics, 49(5):2825–2850, 2021. 74

    work page 2021

  13. [13]

    Chakraborty, S

    A. Chakraborty, S. Chatterjee, and S. Nandy. PriME: Privacy-aware Membership profile Estimation in networks.arXiv preprint arXiv:2406.02794, 2024

    work page arXiv 2024

  14. [14]

    Chaudhuri, A

    K. Chaudhuri, A. D. Sarwate, and K. Sinha. A near-optimal algorithm for differentially-private principal components.Journal of Machine Learning Research, 14, 2013

    work page 2013

  15. [15]

    H. Chen, V. Cohen-Addad, T. d’Orsi, A. Epasto, J. Imola, D. Steurer, and S. Tiegel. Private estimation algorithms for stochastic block models and mixture models.Advances in Neural Information Processing Systems, 36:68134–68183, 2023

    work page 2023

  16. [16]

    H. Chen, J. Ding, T. d’Orsi, Y. Hua, C. Liu, and D. Steurer. Private graphon estimation via sum-of- squares. InProceedings of the 56th Annual ACM Symposium on Theory of Computing, pages 172–182, 2024

    work page 2024

  17. [17]

    Chen and S

    S. Chen and S. Zhou. Recursive mechanism: Towards node differential privacy and unrestricted joins. InProceedings of the 2013 ACM SIGMOD International Conference on Management of Data, pages 653–664, 2013

    work page 2013

  18. [18]

    Decelle, F

    A. Decelle, F. Krzakala, C. Moore, and L. Zdeborov´ a. Asymptotic analysis of the stochastic block model for modular networks and its algorithmic applications.Physical Review E—Statistical, Nonlinear, and Soft Matter Physics, 84(6):066106, 2011

    work page 2011

  19. [19]

    J. Dong, A. Roth, and W. J. Su. Gaussian differential privacy.Journal of the Royal Statistical Society Series B: Statistical Methodology, 84(1):3–37, 2022

    work page 2022

  20. [20]

    d’Orsi and G

    T. d’Orsi and G. Novikov. Tight differentially private PCA via matrix coherence.arXiv preprint arXiv:2510.26679, 2025

    work page arXiv 2025

  21. [21]

    J. C. Duchi, M. I. Jordan, and M. J. Wainwright. Local privacy and statistical minimax rates. In2013 IEEE 54th Annual Symposium on Foundations of Computer Science, pages 429–438. IEEE, 2013

    work page 2013

  22. [22]

    J. C. Duchi, M. I. Jordan, and M. J. Wainwright. Minimax optimal procedures for locally private estimation.Journal of the American Statistical Association, 113(521):182–201, 2018

    work page 2018

  23. [23]

    C. Dwork. Differential privacy. In M. Bugliesi, B. Preneel, V. Sassone, and I. Wegener, editors,Au- tomata, Languages and Programming, pages 1–12, Berlin, Heidelberg, 2006. Springer Berlin Heidelberg

    work page 2006

  24. [24]

    C. Dwork. Differential privacy: A survey of results. InInternational Conference on Theory and Appli- cations of Models of Computation, pages 1–19. Springer, 2008

    work page 2008

  25. [25]

    Dwork and J

    C. Dwork and J. Lei. Differential privacy and robust statistics. InProceedings of the Forty-First Annual ACM Symposium on Theory of Computing, pages 371–380, 2009

    work page 2009

  26. [26]

    Dwork, F

    C. Dwork, F. McSherry, K. Nissim, and A. Smith. Calibrating noise to sensitivity in private data analysis. InTheory of Cryptography Conference, pages 265–284. Springer, 2006

    work page 2006

  27. [27]

    Dwork and A

    C. Dwork and A. Roth. The algorithmic foundations of differential privacy.Foundations and Trends® in Theoretical Computer Science, 9(3–4):211–407, 2014

    work page 2014

  28. [28]

    Dwork, G

    C. Dwork, G. N. Rothblum, and S. Vadhan. Boosting and differential privacy. In2010 IEEE 51st Annual Symposium on Foundations of Computer Science, pages 51–60. IEEE, 2010

    work page 2010

  29. [29]

    C. Gao, Z. Ma, A. Y. Zhang, and H. H. Zhou. Achieving optimal misclassification proportion in stochastic block models.Journal of Machine Learning Research, 18(60):1–45, 2017

    work page 2017

  30. [30]

    R. Ge, H. Lee, J. Lu, and A. Risteski. Efficient sampling from the Bingham distribution. InAlgorithmic Learning Theory, pages 673–685. PMLR, 2021. 75

    work page 2021

  31. [31]

    Gupta, A

    A. Gupta, A. Roth, and J. Ullman. Iterative constructions and private data release. InTheory of Cryptography Conference, pages 339–356. Springer, 2012

    work page 2012

  32. [32]

    Hajek, Y

    B. Hajek, Y. Wu, and J. Xu. Achieving exact cluster recovery threshold via semidefinite programming. IEEE Transactions on Information Theory, 62(5):2788–2797, 2016

    work page 2016

  33. [33]

    Hardt and E

    M. Hardt and E. Price. The noisy power method: A meta algorithm with applications.Advances in Neural Information Processing Systems, 27, 2014

    work page 2014

  34. [34]

    M. Hay, C. Li, G. Miklau, and D. Jensen. Accurate estimation of the degree distribution of private networks. In2009 Ninth IEEE International Conference on Data Mining, pages 169–178. IEEE, 2009

    work page 2009

  35. [35]

    Hehir, A

    J. Hehir, A. Slavkovi´ c, and X. Niu. Consistent spectral clustering of network block models under local differential privacy.The Journal of Privacy and Confidentiality, 12(2), 2022

    work page 2022

  36. [36]

    Hoeffding

    W. Hoeffding. Probability inequalities for sums of bounded random variables.Journal of the American Statistical Association, 58(301):13–30, 1963

    work page 1963

  37. [37]

    P. D. Hoff. Simulation of the matrix Bingham–von Mises–Fisher distribution, with applications to multivariate and relational data.Journal of Computational and Graphical Statistics, 18(2):438–456, 2009

    work page 2009

  38. [38]

    P. W. Holland, K. B. Laskey, and S. Leinhardt. Stochastic blockmodels: First steps.Social Networks, 5(2):109–137, 1983

    work page 1983

  39. [39]

    S. Janson. Large deviation inequalities for sums of indicator variables.arXiv preprint arXiv:1609.00533, 2016

    work page internal anchor Pith review Pith/arXiv arXiv 2016

  40. [40]

    C. R. Johnson.Matrix Theory and Applications, volume 40. American Mathematical Soc., 1990

    work page 1990

  41. [41]

    Kairouz, S

    P. Kairouz, S. Oh, and P. Viswanath. The composition theorem for differential privacy. InInternational Conference on Machine Learning, pages 1376–1385. PMLR, 2015

    work page 2015

  42. [42]

    Kamath, A

    G. Kamath, A. Mouzakis, V. Singhal, T. Steinke, and J. Ullman. A private and computationally-efficient estimator for unbounded Gaussians. InConference on Learning Theory, pages 544–572. PMLR, 2022

    work page 2022

  43. [43]

    Kapralov and K

    M. Kapralov and K. Talwar. On differentially private low rank approximation. InProceedings of the Twenty-Fourth Annual ACM-SIAM Symposium on Discrete Algorithms, pages 1395–1414. SIAM, 2013

    work page 2013

  44. [44]

    Karwa, S

    V. Karwa, S. Raskhodnikova, A. Smith, and G. Yaroslavtsev. Private analysis of graph structure. Proceedings of the VLDB Endowment, 4(11):1146–1157, 2011

    work page 2011

  45. [45]

    Karwa and A

    V. Karwa and A. B. Slavkovi´ c. Differentially private graphical degree sequences and synthetic graphs. InInternational Conference on Privacy in Statistical Databases, pages 273–285. Springer, 2012

    work page 2012

  46. [46]

    S. P. Kasiviswanathan, K. Nissim, S. Raskhodnikova, and A. Smith. Analyzing graphs with node differential privacy. InTheory of Cryptography Conference, pages 457–476. Springer, 2013

    work page 2013

  47. [47]

    J. T. Kent, A. M. Ganeiber, and K. V. Mardia. A new method to simulate the Bingham and related distributions in directional data analysis with applications.arXiv preprint arXiv:1310.8110, 2013

    work page internal anchor Pith review Pith/arXiv arXiv 2013

  48. [48]

    Node-Private Community Detection in Stochastic Block Models

    O. Klopp and I. Zadik. Node-private community detection in stochastic block models.arXiv preprint arXiv:2604.09078, 2026

    work page internal anchor Pith review Pith/arXiv arXiv 2026

  49. [49]

    Koskela, M

    A. Koskela, M. Seif, and A. J. Goldsmith. On the price of differential privacy for spectral clustering over stochastic block models.IEEE Transactions on Network Science and Engineering, 13:5176–5191, 2025. 76

    work page 2025

  50. [50]

    Lei and A

    J. Lei and A. Rinaldo. Consistency of spectral clustering in stochastic block models.The Annals of Statistics, pages 215–237, 2015

    work page 2015

  51. [51]

    F. Liao, J. L. Kim, C. Barnum, and A. Kyrillidis. On the error-propagation of inexact Hotelling’s de- flation for principal component analysis. InForty-First International Conference on Machine Learning, 2024

    work page 2024

  52. [52]

    Mahpud and O

    B. Mahpud and O. Sheffet. A differentially private linear-time FPTAS for the minimum enclosing ball problem.Advances in Neural Information Processing Systems, 35:31640–31652, 2022

    work page 2022

  53. [53]

    McSherry and K

    F. McSherry and K. Talwar. Mechanism design via differential privacy. In48th Annual IEEE Symposium on Foundations of Computer Science (FOCS’07), pages 94–103. IEEE, 2007

    work page 2007

  54. [54]

    M. S. Mohamed, D. Nguyen, A. Vullikanti, and R. Tandon. Differentially private community detection for stochastic block models. InInternational Conference on Machine Learning, pages 15858–15894. PMLR, 2022

    work page 2022

  55. [55]

    Moitra, W

    A. Moitra, W. Perry, and A. S. Wein. How robust are reconstruction thresholds for community detection? InProceedings of the Forty-Eighth Annual ACM Symposium on Theory of Computing, pages 828–841, 2016

    work page 2016

  56. [56]

    A. Naor. Metric embeddings and lipschitz extensions [lecture notes], 2015

    work page 2015

  57. [57]

    Nguyen and A

    D. Nguyen and A. K. Vullikanti. Differentially private exact recovery for stochastic block models. In International Conference on Machine Learning, pages 37798–37839. PMLR, 2024

    work page 2024

  58. [58]

    Nissim, S

    K. Nissim, S. Raskhodnikova, and A. Smith. Smooth sensitivity and sampling in private data analysis. InProceedings of the Thirty-Ninth Annual ACM Symposium on Theory of Computing, pages 75–84, 2007

    work page 2007

  59. [59]

    Oliveira, A

    D. Oliveira, A. Cerqueira, and R. Oliveira. Counting communities in weighted stochastic block models via semidefinite programming.arXiv preprint arXiv:2502.15891, 2025

    work page arXiv 2025

  60. [60]

    Polyanskiy and Y

    Y. Polyanskiy and Y. Wu.Information Theory: From Coding to Learning. Cambridge University Press, 2025

    work page 2025

  61. [61]

    Efficient Lipschitz Extensions for High-Dimensional Graph Statistics and Node Private Degree Distributions

    S. Raskhodnikova and A. Smith. Efficient Lipschitz extensions for high-dimensional graph statistics and node private degree distributions.arXiv preprint arXiv:1504.07912, 2015

    work page internal anchor Pith review Pith/arXiv arXiv 2015

  62. [62]

    K. Rohe, S. Chatterjee, and B. Yu. Spectral clustering and the high-dimensional stochastic blockmodel. The Annals of Statistics, pages 1878–1915, 2011

    work page 1915

  63. [63]

    Shalev-Shwartz and S

    S. Shalev-Shwartz and S. Ben-David.Understanding Machine Learning: From Theory to Algorithms. Cambridge University Press, 2014

    work page 2014

  64. [64]

    Singhal and T

    V. Singhal and T. Steinke. Privately learning subspaces.Advances in Neural Information Processing Systems, 34:1312–1324, 2021

    work page 2021

  65. [65]

    S. Vadhan. The complexity of differential privacy. InTutorials on the Foundations of Cryptography: Dedicated to Oded Goldreich, pages 347–450. Springer, 2017

    work page 2017

  66. [66]

    V. Q. VU and J. LEI. Minimax sparse principal subspace estimation in high dimensions.The Annals of Statistics, 41(6):2905–2947, 2013

    work page 2013

  67. [67]

    M. J. Wainwright.High-Dimensional Statistics: A Non-Asymptotic Viewpoint, volume 48. Cambridge University Press, 2019. 77

    work page 2019

  68. [68]

    Wasserman and S

    L. Wasserman and S. Zhou. A statistical framework for differential privacy.Journal of the American Statistical Association, 105(489):375–389, 2010

    work page 2010

  69. [69]

    Whitehouse, A

    J. Whitehouse, A. Ramdas, R. Rogers, and S. Wu. Fully-adaptive composition in differential privacy. InInternational Conference on Machine Learning, pages 36990–37007. PMLR, 2023

    work page 2023

  70. [70]

    H. S. Witsenhausen. On sequences of pairs of dependent random variables.SIAM Journal on Applied Mathematics, 28(1):100–113, 1975

    work page 1975

  71. [71]

    M. Xu, V. Jog, and P. Loh. Optimal rates for community estimation in the weighted stochastic block model.The Annals of Statistics, 48(1):183–204, 2020

    work page 2020

  72. [72]

    Y. Yu, T. Wang, and R. J. Samworth. A useful variant of the Davis–Kahan theorem for statisticians. Biometrika, 102(2):315–323, 2015

    work page 2015

  73. [73]

    Yun and R

    Y. Yun and R. Dudeja. High-dimensional asymptotics of differentially private PCA.arXiv preprint arXiv:2511.07270, 2025

    work page arXiv 2025

  74. [74]

    Y. Zhao, E. Levina, and J. Zhu. Consistency of community detection in networks under degree-corrected stochastic block models.The Annals of Statistics, pages 2266–2292, 2012. 78

    work page 2012