Pith. sign in

REVIEW 2 major objections 4 minor 46 references

Adapting to Linear Separable Subsets with Large-Margin in Differentially Private Learning

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

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

Pith's one-line read This paper claims that one efficient differentially private gradient-descent algorithm can automatically match the risk of the best large-margin subset of the data, without knowing the margin or the outlier set in advance.

desk verdict A genuine adaptivity result for DP large-margin learning, with a clean inlier-outlier analysis; the high-probability theorem leans on an unverified external last-iterate SGD bound that a referee should check. read the letter →

arxiv 2505.24737 v1 pith:IMKAHJ6J submitted 2025-05-30 cs.LG stat.ML

Erchi Wang , Yuqing Zhu , Yu-Xiang Wang This is my paper
classification cs.LGstat.ML MSC 68P2768T0568Q32
keywords differentialprivacylarge-marginhalfspacesDP-ERMagnosticlearningJohnson-Lindenstraussprojectionprivatehyperparametertuningmarginoutlierszero-onerisk
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

Learning halfspaces with differential privacy typically pays a fixed agnostic rate that ignores favorable data geometry. This paper tries to show that a single efficient algorithm can instead adapt to any large-margin “clean” subset: if all but $|S_{\mathrm{out}}|$ points are separable with geometric margin $\gamma$, then its empirical and population zero-one risk are both $\tilde{O}(1/(n\gamma^2\min\{\varepsilon,1\}) + |S_{\mathrm{out}}|/(\gamma n))$, simultaneously for every such subset, with no need to know $\gamma$ or $S_{\mathrm{out}}$. If this is right, the realizable-case fast rate $\tilde{O}(1/(n\gamma^2\varepsilon))$ is recovered for free, and when $|S_{\mathrm{out}}|=o(\sqrt{n})$ the best prior efficient agnostic bound improves by a $\sqrt{n}$ factor. The authors support the claim with an inlier-outlier convergence analysis, random projections, and private selection over a logarithmic margin grid.

What carries the argument

The margin-inlier/outlier pair (Definition 6.1) is the central object: $S_{\mathrm{in}}(\gamma)$ is the family of subsets with geometric margin at least $\gamma$, and $S_{\mathrm{out}}(\gamma)$ is the complement of one such subset. The governing inequality is Eq. (2): for a fixed $\gamma$, choosing hinge loss parameter $c \le \gamma$ makes the $c$-hinge loss on a max-margin inlier set zero, bounding total loss by $O(|S_{\mathrm{out}}(\gamma)|/c)$ plus the optimizer’s excess risk. A Johnson-Lindenstrauss projection to dimension $O(\log(n/\beta)/\gamma^2)$ preserves the margin with high probability, so the analysis runs in low dimension without paying $d$, and private selection across the grid picks the best $\gamma$ without extra privacy loss beyond a logarithmic factor.

What would settle it

Fix a concrete instance: $n=10^4$ points in $\mathbb{R}^{50}$, a centrally separable core of size $n-m$ with geometric margin $\gamma=0.1$, and $m=100$ outliers placed adversarially. Run Algorithm 3 with $\varepsilon=0.1$, $\delta=10^{-6}$ many times and record the empirical zero-one risk of the last iterate. Theorem 4.1 predicts a high-probability bound of order $\tilde{O}(1/(\gamma^2\varepsilon n)+m/(\gamma n))$; if the observed risk consistently exceeds that by a polynomial factor, or if the rate degrades from $n^{-1}$ to $n^{-1/2}$, the claim is falsified. A cheaper, direct check is to test the cited last-iterate noisy-SGD convergence theorem on the non-smooth $c$-hinge loss with Algorithm 5’s step-size schedule, since the paper does not verify its conditions.

Watch

Extended reading notes

Core claim

The central discovery is that the geometric margin can be replaced by a per-level decomposition: for any margin threshold $\gamma$, split the sample into margin inliers $S_{\mathrm{in}}(\gamma)$, subsets that are $\gamma$-separable, and margin outliers $S_{\mathrm{out}}(\gamma)$. Running noisy projected gradient descent with hinge parameter $c \le \gamma$ makes the loss vanish on $S_{\mathrm{in}}(\gamma)$, so the only nonzero optimization cost is proportional to $|S_{\mathrm{out}}(\gamma)|/c$. A private selection over the doubling grid $\Gamma = \{1/n, 2/n, \ldots, 1\}$ then finds the $\gamma$ that minimizes the resulting bound, giving Theorem 4.1’s simultaneous empirical and population guarantees. The same mechanism recovers the known realizable fast rate and, when $|S_{\mathrm{out}}|=o(\sqrt{n})$, improves the efficient agnostic rate by a $\sqrt{n}$ factor.

Load-bearing premise

The high-probability and population-risk halves of the main theorem borrow a last-iterate convergence result for noisy stochastic gradient descent from another paper, and they do not verify that the non-smooth hinge loss and step-size schedule used here satisfy that theorem’s assumptions.

Editorial extensions

If this is right

  • In the fully separable case, the algorithm recovers the known $\tilde{O}(1/(n\gamma^2\varepsilon))$ rate without being given $\gamma$, so the usual margin-assumption input is no longer needed.
  • In the agnostic case with $|S_{\mathrm{out}}|=o(\sqrt{n})$ outliers, the bound improves on the best previous efficient DP halfspace learner by a factor of $\sqrt{n}$.
  • The same guarantee holds simultaneously for every subset $S_{\mathrm{out}}$ with $\gamma>0$, so the algorithm competes with the best subset without paying a $\log(2^n)$ adaptation cost.
  • The risk analysis is dimension-free, and the algorithm runs in polynomial time; replacing full-batch gradient descent with any black-box DP-ERM optimizer preserves the bound.
  • When the data are not confined to the unit ball but $\|x\| \le b$, the bound becomes $\tilde{O}(b^2/(n\gamma^2\varepsilon) + b|S_{\mathrm{out}}|/(\gamma n))$, and the algorithm still needs no bounded parameter domain.

Reading between the lines

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

  • Beyond the paper, the inlier-outlier decomposition is a reusable analysis tool: any private ERM whose loss is smooth and Lipschitz could be split at the hypothesis’s zero-loss set, replacing worst-case bounds with subset-adaptive ones.
  • A practical reading of the bound is that data “removability” is a private-learning resource: the $|S_{\mathrm{out}}|/(\gamma n)$ term tells a practitioner how many hard points can be tolerated before the large-margin benefit disappears, which could guide feature engineering before spending privacy budget.
  • One testable extension suggested by the paper’s CIFAR-10 removal experiment: on features that become separable after removing about 0.1% of points, the algorithm should show the predicted gap over DP-SGD, and the gap should vanish once $|S_{\mathrm{out}}|$ reaches $\Theta(\sqrt{n})$.
  • Because the margin grid is data-independent and the selection is private, the same wrapper could be applied to other base learners, such as DP-SGD for deep features, to inherit an adaptive margin guarantee at the price of a logarithmic privacy overhead.
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

2 major / 4 minor

Summary. The paper proposes a differentially private algorithm M* (Algo. 3) for binary linear classification that adapts to datasets containing a large-margin linearly separable subset, without knowing the margin or the outlier set in advance. The main result (Theorem 4.1) states that M* is (ε,δ)-DP and, with high probability, achieves empirical and population zero-one risk bounds of order 1/(γ² n min{ε,1}) + |S_out|/(γ n) for every subset S_out whose removal leaves margin γ > 0. The algorithm combines a Johnson-Lindenstrauss projection with dimension O(log n/γ²), full-batch noisy gradient descent on the c-hinge loss, a logarithmic margin grid, and private hyperparameter selection. The appendix contains most proofs; the in-expectation empirical analysis is self-contained, while the high-probability and population results rely on an external last-iterate SGD convergence theorem cited as Lemma C.2.

Significance. If the main theorem is fully established, this is a significant advance: it provides the first efficient DP algorithm that adapts to large-margin separable subsets without prior knowledge of the margin, removes the bounded-parameter-space assumption of prior work, and improves the agnostic population risk by a sqrt(n) factor when the outlier set is small. The inlier-outlier decomposition (Eq. 2) and the use of JL projections for margin preservation are elegant and potentially reusable. The in-expectation empirical bound is a self-contained, credible contribution. However, the high-probability empirical bound and the population risk bound depend on Lemma C.2, whose applicability to the non-smooth c-hinge loss with constant step size is not verified; this makes the central high-probability claim not yet fully supported.

major comments (2)
  1. [Appendix C.3, Lemma C.2 and Lemma D.3] Lemma C.2 is a verbatim citation of Theorem 3.5 of Liu and Zhou (2024), but the paper neither proves it nor checks that the theorem's hypotheses hold for Algorithm 5 when the loss is the non-smooth c-hinge loss, the step size is constant, and the noise is additive Gaussian. Lemma D.3 uses Lemma C.2 to control the last iterate of ANGD, and Theorems 6.5(2), 6.7, and Theorem 4.1(2) depend on that control. As written, the high-probability empirical and population risk claims lack proof support. Please provide a self-contained proof of Lemma C.2 in this setting, or explicitly verify the smoothness, step-size, and noise conditions of the cited theorem; otherwise the main high-probability claims should be removed or downgraded.
  2. [Appendix B.3, Lemma 6.2] The statement of Lemma 6.2 promises a margin-preservation guarantee for every S_in in S_in(γ), but the proof only handles a largest inlier set S*_γ in argmax_{S' in S_in(γ)} |S'|. Later results (Corollary D.2, Lemma 6.3) need the arbitrary-S_in form. The gap is easily repaired by applying Lemma B.2 directly to the given S_in rather than to the largest set, but the current proof does not establish the stated lemma.
minor comments (4)
  1. [Appendix H.1, proof of Lemma H.2] The sentence 'the additive Gaussian noise has distribution N(0, 1/µ²)' conflicts with Algorithm 2, line 5, where the noise scale is σ = Δ√(2|Θ|)/µ; the subsequent algebra uses the correct scale, so this appears to be a typographical inconsistency that should be corrected.
  2. [Theorem 7.1 and abstract] Theorem 7.1 states the advanced tuning algorithm satisfies (ε+δ,δ)-DP, while the abstract and Section 7 discussion say (ε,δ)-DP; please clarify the exact privacy guarantee for the APrivTune variant.
  3. [Appendix C.3, Lemma C.2] The learning rate in Lemma C.2 differs from that in Lemma C.1 by a log(1/β) factor in the denominator; please state explicitly that the high-probability analysis uses a different step-size schedule, since otherwise the two lemmas appear inconsistent.
  4. [General] There are several typos and small errors: 'assme' in Appendix G.1, 'fauilure' in Lemma 7.2, 'Initilize' in Algorithm 6, 'Lemm 6.3' in Appendix K.5, and 'the for' in Lemma A.9; these should be cleaned up before publication.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity: the adaptive-margin bound follows from a self-contained inlier-outlier analysis with standard external tools; the external last-iterate citation is a support risk, not a circular reduction.

full rationale

The central derivation is not circular. Eq. (2) and Lemmas D.1/D.3 bound the excess empirical risk relative to the normalized max-margin separator of an arbitrary gamma-separable subset S_in, and the final bound min_{S_out} [1/(n gamma^2 epsilon) + |S_out|/(gamma n)] follows from the definition of margin outliers (Def. 6.1) and a doubling grid argument (Lemma 6.4); the conclusion is not assumed in the definition. The JL margin-preservation step (Lemma 6.2/B.2) relies on standard, data-oblivious Johnson-Lindenstrauss results (Larsen-Nelson; Bassily et al. Lemma A.3), and the expectation version of the noisy-GD convergence (Lemma C.1) is proved in the appendix. The high-probability and population-risk branch (Theorems 6.5(2), 6.7) depends on Lemma C.2, quoted as Theorem 3.5 of Liu and Zhou (2024); the authors do not verify that theorem's smoothness, noise, or step-size conditions for the non-smooth c-hinge loss. That is a genuine external-support and correctness risk, but it is a citation to independent prior work, not a reduction of the paper's result to its own inputs, and it is not a self-citation. Self-citations (Zhu and Wang 2020; Wang et al. 2024; Koskela et al. 2024) are contextual or provide auxiliary privacy lemmas for the advanced tuning section; the main Theorem 4.1 does not reduce to them. No fitted parameter is renamed as a prediction, and no uniqueness or ansatz is imported from the authors' prior work to force the chosen estimator.

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

The central claim rests on standard background: i.i.d. sampling from a distribution on the unit ball (domain assumption), the JL lemma, GDP composition and conversion, noisy GD convergence (one part self-proven, one part cited), and uniform convergence bounds for halfspaces. None of these are ad hoc to this paper; they are standard tools in the DP learning literature. The free parameter list is empty because all hyperparameters are set analytically from the desired privacy and confidence parameters. The paper introduces a mathematical definition (margin inliers/outliers) but no graviton-type physical entity.

assumptions (6)
  • domain assumption Training set S is sampled i.i.d. from an unknown distribution D on B_d(1) × {±1}.
    Section 3 states this sampling assumption; the risk bounds are with respect to this D.
  • standard math Johnson-Lindenstrauss lemma with random Rademacher matrices preserves pairwise distances and inner products with distortion 1±e/3 with high probability.
    Lemma B.1, from Bassily et al. (2022); used in Lemma 6.2 to guarantee margin preservation after projection.
  • standard math Gaussian Differential Privacy composition: composing μ_i-GDP mechanisms yields sqrt(sum μ_i^2)-GDP, and a Gaussian mechanism with sensitivity Δ and noise σ is Δ/σ-GDP.
    Remark 2.3 and Definition 2.2; used throughout the privacy analyses of Algorithms 1-4.
  • standard math Noisy gradient descent (Algo. 5) converges in expectation at rate O(||w_ref-w_0||Δ√d/μ) for convex Lipschitz losses.
    Lemma C.1, proven in Appendix C.2 using convexity of the hinge loss; the proof is included in the paper.
  • standard math Last-iterate noisy SGD satisfies the high-probability bound O(||w_ref-w_0||Δ√(d log(1/β))/μ), as stated in Theorem 3.5 of Liu and Zhou (2024).
    Lemma C.2, cited from Liu and Zhou (2024). This is external and its applicability to non-smooth hinge loss is not checked.
  • standard math Uniform convergence for halfspaces: with probability 1-β, R_D(w) ≤ R_S(w) + O(sqrt(R_S(w) VC log n / n) + VC log n / n).
    Lemma I.2, cited from Bassily et al. (2022); used to convert empirical bounds to population bounds in Theorem 6.7.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Adapting to Linear Separable Subsets with Large-Margin in Differentially Private Learning." pith.science (2026). https://pith.science/paper/IMKAHJ6J

@misc{pith2026250524737,
  author       = {Pith},
  title        = {Pith review of: Adapting to Linear Separable Subsets with Large-Margin in Differentially Private Learning},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/IMKAHJ6J}},
  note         = {Machine review of arXiv:2505.24737}
}
abstract

This paper studies the problem of differentially private empirical risk minimization (DP-ERM) for binary linear classification. We obtain an efficient $(\varepsilon,\delta)$-DP algorithm with an empirical zero-one risk bound of $\tilde{O}\left(\frac{1}{\gamma^2\varepsilon n} + \frac{|S_{\mathrm{out}}|}{\gamma n}\right)$ where $n$ is the number of data points, $S_{\mathrm{out}}$ is an arbitrary subset of data one can remove and $\gamma$ is the margin of linear separation of the remaining data points (after $S_{\mathrm{out}}$ is removed). Here, $\tilde{O}(\cdot)$ hides only logarithmic terms. In the agnostic case, we improve the existing results when the number of outliers is small. Our algorithm is highly adaptive because it does not require knowing the margin parameter $\gamma$ or outlier subset $S_{\mathrm{out}}$. We also derive a utility bound for the advanced private hyperparameter tuning algorithm.

Figures

Figures reproduced from arXiv: 2505.24737 by the authors.

Figure 1
Figure 1. Margin is unstable after changing one point (marked by the green square), thus hard to design a data-dependent DP-mechanism using standard techniques (e.g., smoothed sensitivity (Nissim et al., 2007) or propose-test-release (Dwork & Lei, 2009)). 1 arXiv:2505.24737v1 [cs.LG] 30 May 2025 [PITH_FULL_IMAGE:figures/full_fig_p001_1.png] view at source ↗
Figure 2
Figure 2. The number of removed points (in percentage of n) vs normalized margin. Classes 1 and 9 from the CIFAR10 training set are used. As more points are removed, the margin increases. We include more implementation details in Appendix N. After approximately 0.1% of points are removed, the remaining data becomes linearly separable for both ViT and ResNet-50-based features. This phenomenon also relates to neural collapse th… view at source ↗
Figure 3
Figure 3. The number of removed points (in percentage of n) vs normalized margin. The classes from the CIFAR10 training set are labeled in each subtitle. As more points are removed, the margin increases. 38 [PITH_FULL_IMAGE:figures/full_fig_p038_3.png] view at source ↗

Discussion (0). Sign in to comment.

Reference graph

Works this paper leans on

46 extracted references · 37 canonical work pages

  1. [1]

    write newline

    " write newline "" before.all 'output.state := FUNCTION n.dashify 't := "" t empty not t #1 #1 substring "-" = t #1 #2 substring "--" = not "--" * t #2 global.max substring 't := t #1 #1 substring "-" = "-" * t #2 global.max substring 't := while if t #1 #1 substring * t #2 global.max substring 't := if while FUNCTION format.date year duplicate empty "emp...

  2. [2]

    Differentially private generalized linear models revisited

    Arora, R., Bassily, R., Guzm \'a n, C., Menart, M., and Ullah, E. Differentially private generalized linear models revisited. Advances in Neural Information Processing Systems, 35: 0 22505--22517, 2022

    work page 2022

  3. [3]

    Private empirical risk minimization: Efficient algorithms and tight error bounds

    Bassily, R., Smith, A., and Thakurta, A. Private empirical risk minimization: Efficient algorithms and tight error bounds. In 2014 IEEE 55th annual symposium on foundations of computer science, pp.\ 464--473. IEEE, 2014

    2014

  4. [4]

    Bassily, R., Mohri, M., and Suresh, A. T. Differentially private learning with margin guarantees. Advances in Neural Information Processing Systems, 35: 0 32127--32141, 2022

    work page 2022

  5. [5]

    L., and Sorrell, J

    Bun, M., Carmosino, M. L., and Sorrell, J. Efficient, noise-tolerant, and private learning via boosting. In Proceedings of Thirty Third Conference on Learning Theory, volume 125 of Proceedings of Machine Learning Research, pp.\ 1031--1077. PMLR, 09--12 Jul 2020

    work page 2020

  6. [6]

    Learning noisy halfspaces with a margin: Massart is no harder than random

    Chandrasekaran, G., Kontonis, V., Stavropoulos, K., and Tian, K. Learning noisy halfspaces with a margin: Massart is no harder than random. In The Thirty-eighth Annual Conference on Neural Information Processing Systems, 2024

    work page 2024

  7. [7]

    Chaudhuri, K., Monteleoni, C., and Sarwate, A. D. Differentially private empirical risk minimization. Journal of Machine Learning Research, 12 0 (3), 2011

    work page 2011

  8. [8]

    Classification under misspecification: Halfspaces, generalized linear models, and evolvability

    Chen, S., Koehler, F., Moitra, A., and Yau, M. Classification under misspecification: Halfspaces, generalized linear models, and evolvability. In Larochelle, H., Ranzato, M., Hadsell, R., Balcan, M., and Lin, H. (eds.), Advances in Neural Information Processing Systems, volume 33, pp.\ 8391--8403. Curran Associates, Inc., 2020

    work page 2020

Show all 46 references
  1. [9]

    and Vapnik, V

    Cortes, C. and Vapnik, V. Support-vector networks. Machine Learning, 20: 0 273--297, 1995

    1995

  2. [10]

    Complexity theoretic limitations on learning halfspaces

    Daniely, A. Complexity theoretic limitations on learning halfspaces. In Proceedings of the Forty-Eighth Annual ACM Symposium on Theory of Computing, STOC '16, pp.\ 105–117, 2016

    2016

  3. [11]

    L., and Balle, B

    De, S., Berrada, L., Hayes, J., Smith, S. L., and Balle, B. Unlocking high-accuracy differentially private image classification through scale. arXiv preprint arXiv:2204.13650, 2022

    2022 arXiv

  4. [12]

    and Zarifis, N

    Diakonikolas, I. and Zarifis, N. A near-optimal algorithm for learning margin halfspaces with massart noise. In The Thirty-eighth Annual Conference on Neural Information Processing Systems, 2024

    2024

  5. [13]

    Distribution-independent pac learning of halfspaces with massart noise

    Diakonikolas, I., Gouleakis, T., and Tzamos, C. Distribution-independent pac learning of halfspaces with massart noise. Advances in Neural Information Processing Systems, 32, 2019

    2019

  6. [14]

    Dong, J., Roth, A., and Su, W. J. Gaussian Differential Privacy . Journal of the Royal Statistical Society Series B: Statistical Methodology, 84 0 (1): 0 3--37, 02 2022

    2022

  7. [15]

    An image is worth 16x16 words: Transformers for image recognition at scale

    Dosovitskiy, A., Beyer, L., Kolesnikov, A., Weissenborn, D., Zhai, X., Unterthiner, T., Dehghani, M., Minderer, M., Heigold, G., Gelly, S., Uszkoreit, J., and Houlsby, N. An image is worth 16x16 words: Transformers for image recognition at scale. In International Conference on...

    2021

  8. [16]

    and Lei, J

    Dwork, C. and Lei, J. Differential privacy and robust statistics. In Proceedings of the forty-first annual ACM symposium on Theory of computing, pp.\ 371--380, 2009

    2009

  9. [17]

    Calibrating noise to sensitivity in private data analysis

    Dwork, C., McSherry, F., Nissim, K., and Smith, A. Calibrating noise to sensitivity in private data analysis. In Proceedings of the Third Conference on Theory of Cryptography, TCC'06, pp.\ 265–284, 2006

    2006

  10. [18]

    N., and Vadhan, S

    Dwork, C., Naor, M., Reingold, O., Rothblum, G. N., and Vadhan, S. On the complexity of differentially private data release: efficient algorithms and hardness results. In Proceedings of the Forty-First Annual ACM Symposium on Theory of Computing, STOC '09, pp.\ 381–390, 2009

    2009

  11. [19]

    The algorithmic foundations of differential privacy

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

    2014

  12. [20]

    Feldman, V., Gopalan, P., Khot, S., and Ponnuswami, A. K. New results for learning noisy parities and halfspaces. In 2006 47th Annual IEEE Symposium on Foundations of Computer Science (FOCS'06), 2006

    2006

  13. [21]

    and Schapire, R

    Freund, Y. and Schapire, R. E. A decision-theoretic generalization of on-line learning and an application to boosting. Journal of Computer and System Sciences, 55 0 (1): 0 119--139, 1997

    1997

  14. [22]

    Robust and private learning of halfspaces

    Ghazi, B., Kumar, R., Manurangsi, P., and Nguyen, T. Robust and private learning of halfspaces. In International Conference on Artificial Intelligence and Statistics, pp.\ 1603--1611. PMLR, 2021

    2021

  15. [23]

    and Raghavendra, P

    Guruswami, V. and Raghavendra, P. Hardness of learning halfspaces with noise. SIAM Journal on Computing, 39 0 (2): 0 742--765, 2009

    2009

  16. [24]

    Deep residual learning for image recognition

    He, K., Zhang, X., Ren, S., and Sun, J. Deep residual learning for image recognition. In Proceedings of the IEEE conference on computer vision and pattern recognition, pp.\ 770--778, 2016

    2016

  17. [25]

    B., Lindenstrauss, J., and Schechtman, G

    Johnson, W. B., Lindenstrauss, J., and Schechtman, G. Extensions of lipschitz maps into banach spaces. Israel Journal of Mathematics, 54 0 (2): 0 129--138, 1986

    1986

  18. [26]

    and Kulkarni, T

    Koskela, A. and Kulkarni, T. D. Practical differentially private hyperparameter tuning with subsampling. Advances in Neural Information Processing Systems, 36, 2024

    2024

  19. [27]

    E., and Wang, Y.-X

    Koskela, A., Redberg, R. E., and Wang, Y.-X. Privacy profiles for private selection. In Forty-first International Conference on Machine Learning, 2024

    2024

  20. [28]

    Larsen, K. G. and Nelson, J. Optimality of the johnson-lindenstrauss lemma. In 2017 IEEE 58th Annual Symposium on Foundations of Computer Science (FOCS), pp.\ 633--638. IEEE, 2017

    2017

  21. [29]

    and Talwar, K

    Liu, J. and Talwar, K. Private selection from private candidates. In Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing, pp.\ 298--309, 2019

    2019

  22. [30]

    and Zhou, Z

    Liu, Z. and Zhou, Z. Revisiting the last-iterate convergence of stochastic gradient methods. In The Twelfth International Conference on Learning Representations, 2024

    2024

  23. [31]

    and Talwar, K

    McSherry, F. and Talwar, K. Mechanism design via differential privacy. In 48th Annual IEEE Symposium on Foundations of Computer Science (FOCS'07), pp.\ 94--103, 2007 a

    2007

  24. [32]

    and Talwar, K

    McSherry, F. and Talwar, K. Mechanism design via differential privacy. In 48th Annual IEEE Symposium on Foundations of Computer Science (FOCS'07), pp.\ 94--103, 2007 b

    2007

  25. [33]

    Foundations of machine learning

    Mohri, M., Rostamizadeh, A., and Talwalkar, A. Foundations of machine learning. MIT press, 2018

    2018

  26. [34]

    Near, J. P. and Abuah, C. Programming Differential Privacy, volume 1. 2021

    2021

  27. [35]

    L., Ullman, J., and Zakynthinou, L

    Nguy\ \^ e n, H. L., Ullman, J., and Zakynthinou, L. Efficient P rivate A lgorithms for L earning L arge- M argin H alfspaces. In Kontorovich, A. and Neu, G. (eds.), In the 31st International Conference on Algorithmic Learning Theory, volume 117 of Proceedings of Machine Learn...

    2020

  28. [36]

    Smooth sensitivity and sampling in private data analysis

    Nissim, K., Raskhodnikova, S., and Smith, A. Smooth sensitivity and sampling in private data analysis. In Proceedings of the thirty-ninth annual ACM symposium on Theory of computing, pp.\ 75--84, 2007

    2007

  29. [37]

    Proceedings of the symposium on the mathematical theory of automata

    Novikoff, A. Proceedings of the symposium on the mathematical theory of automata. pp.\ 615--622, 1962

    1962

  30. [38]

    and Tsampouka, P

    Panagiotakopoulos, C. and Tsampouka, P. The perceptron with dynamic margin. In Algorithmic Learning Theory: 22nd International Conference, pp.\ 204--218, 2011

    2011

  31. [39]

    and Steinke, T

    Papernot, N. and Steinke, T. Hyperparameter tuning with renyi differential privacy. In International Conference on Learning Representations, 2022

    2022

  32. [40]

    Papyan, V., Han, X., and Donoho, D. L. Prevalence of neural collapse during the terminal phase of deep learning training. Proceedings of the National Academy of Sciences, 117 0 (40): 0 24652--24663, 2020

    2020

  33. [41]

    and Smith, A

    Raskhodnikova, S. and Smith, A. Lipschitz extensions for node-private graph statistics and the generalized exponential mechanism. In 2016 IEEE 57th Annual Symposium on Foundations of Computer Science (FOCS), pp.\ 495--504, 2016

    2016

  34. [42]

    The perceptron: A probabilistic model for information storage and organization in the brain

    Rosenblatt, F. The perceptron: A probabilistic model for information storage and organization in the brain. Psychological Review, 65: 0 386--408, 1958

    1958

  35. [43]

    and Verdu, S

    Sason, I. and Verdu, S. f-divergence inequalities. IEEE Transactions on Information Theory, 62 0 (11): 0 5973–6006, November 2016. ISSN 1557-9654

    2016

  36. [44]

    Statistical learning theory

    Vapnik, V. Statistical learning theory. 1998

    1998

  37. [45]

    J., and Wang, Y.-X

    Wang, C., Zhu, Y., Su, W. J., and Wang, Y.-X. Neural collapse meets differential privacy: Curious behaviors of N oisy GD with near-perfect representation learning. In Proceedings of the 41st International Conference on Machine Learning, volume 235 of Proceedings of Machine Lea...

    2024

  38. [46]

    and Wang, Y.-X

    Zhu, Y. and Wang, Y.-X. Improving sparse vector technique with renyi differential privacy. In Larochelle, H., Ranzato, M., Hadsell, R., Balcan, M., and Lin, H. (eds.), Advances in Neural Information Processing Systems, volume 33, pp.\ 20249--20258, 2020

    2020

Pith tools

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