REVIEW 3 major objections 5 minor 61 references
Beyond Ordinary Lipschitz Constraints: Differentially Private Stochastic Optimization with Tsybakov Noise Condition
T0 review · 3 major / 5 minor · reviewed 2026-08-05 · deepseek-v4-flash
Pith's one-line read For heavy-tailed losses satisfying the Tsybakov Noise Condition, differentially private stochastic convex optimization can achieve rates that do not depend on the Lipschitz constant, with a near-matching private lower bound.
desk verdict The upper bounds are a genuine advance in heavy-tailed DP-SCO under TNC, but the Theorem 4 lower bound is broken as written: the zero-atom construction violates the paper's own Assumption 1. read the letter →
The pith
A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.
The reading
What carries the argument
The load-bearing object is the localized noisy clipped gradient method (LNC-GM): data are split into log n disjoint blocks; on block i, a clipped, strongly regularized empirical objective is minimized over a ball of exponentially shrinking radius around the previous iterate, and Gaussian noise is calibrated from the stability of the clipped gradient descent rather than from a Lipschitz constant. The clip threshold is set by r_{2k,n_i} and the privacy budget, so both bias and stability depend on moment terms instead of L_f. The Tsybakov Noise Condition enters through a phase recursion: each phase halves the distance to the optimum, and the distance-accuracy trade-off is converted to excess ri
What would settle it
A concrete check is to evaluate the lower-bound construction in Theorem 4 for the atom x=0: on that draw, sup_{w in B_r} ||grad f(w,x)|| equals r^{theta-1}, which is positive, so the proof's bound E[sup_W ||grad f||^k] <= E[||2x||^k] does not account for the zero atom's contribution. If that inequality fails for the constructed distributions, the lower-bound theorem needs a corrected construction or a revised moment argument.
Extended reading notes
Core claim
The central claim is that DP-SCO rates under the Tsybakov Noise Condition are governed by gradient moments rather than by the Lipschitz parameter. Let r_k denote the k-th root of the k-th moment of the gradient norm. For Lipschitz losses with theta >= 2, the localized noisy clipped gradient method (Algorithm 4) yields F(w)-F(w*) = O~((R_{2k,n}(n^{-1/2}+(sqrt(d log(1/delta))/(eps n))^{(k-1)/k}))^{theta/(theta-1)}) with probability 1-beta, and the Lipschitz constant never appears in the bound. Iterating the same base algorithm (Algorithm 5) extends this to theta >= theta-bar > 1. When eps is small, the non-Lipschitz PNCA-SGD (Algorithm 6) attains the same rate with r_k replacing R_{2k,n}, in e
Load-bearing premise
The load-bearing premise is Assumption 1: the k-th moment of the worst-case gradient over the whole parameter space, E[sup_{w in W} ||grad f(w,x)||^k], must be finite; moreover, in the Lipschitz theorems the Lipschitz constant must grow at most polynomially in n.
Editorial extensions
If this is right
- For theta=2, which covers strongly convex population risks, the bound matches the known nearly optimal heavy-tailed DP-SCO rate while removing the Lipschitz dependence.
- Losses such as l1/l4-norm linear regression and l2-regularized logistic regression, which satisfy TNC, inherit these rates even when their gradients are heavy-tailed.
- The lower bound shows that any rho-zCDP algorithm must pay at least this rate, so the polynomial structure (1/sqrt(n) + (sqrt(d)/(n eps))^{(k-1)/k}) with the theta/(theta-1) exponent is intrinsic to the problem.
- When epsilon is sufficiently small, Lipschitzness is unnecessary; the same rate is achievable for non-Lipschitz smooth losses, removing a long-standing assumption in DP-SCO.
- The upper-bound algorithms are one-pass and use Gaussian noise, so they extend to zCDP by replacing sqrt(log(1/delta))/eps with 1/sqrt(rho), as the paper notes.
Reading between the lines
- Editorial inference: the remaining gap between r_{2k} in the upper bounds and r_k in the lower bounds suggests the Lipschitz-case upper bound may be improvable to r_k, possibly by a variance-reduced or sharper localization of the base algorithm.
- Editorial inference: Assumption 1 places the supremum over the whole parameter space inside the expectation; we suspect the rates still hold under pointwise moment bounds E[||grad f(w,x)||^k] <= r_k for each w, which would cover unbounded domains, but the current proof would need a different high-probability stability argument.
- Editorial inference: since TNC with theta near 1 produces very slow rates and the algorithms require a known lower bound theta-bar, a natural extension is an online or adaptive estimator of theta that avoids fixing theta-bar in advance.
- Editorial inference: the lower-bound construction uses sparse distributions with an atom at zero, so empirically the rate may be driven by rare large-gradient events; a synthetic experiment with such distributions could test whether the predicted rates appear in practice before deploying on real heavy-tailed data.
Editorial analysis
A structured set of objections, weighed in public.
Referee Report
Summary. The paper studies differentially private stochastic convex optimization (DP-SCO) when the population risk satisfies the Tsybakov Noise Condition (TNC) and the loss is not uniformly Lipschitz, but the supremum of the gradient over the domain has a bounded k-th moment (Assumption 1). It proposes localized clipped/noisy SGD algorithms (Algorithms 3--5) giving high-probability excess-population-risk bounds of order (\tilde{r}_{2k}(1/\sqrt{n} + (\sqrt{d}/(n\varepsilon))^{(k-1)/k}))^{\theta/(\theta-1)}, and a shuffled clipped accelerated SGD (Algorithms 6--7) for the non-Lipschitz case when \varepsilon is small. It also claims a \rho-zCDP minimax lower bound of order (\tilde{r}_k(1/\sqrt{n} + (\sqrt{d}/(n\sqrt{\rho}))^{(k-1)/k}))^{\theta/(\theta-1)} for \theta \ge 2. The abstract and introduction present the upper and lower bounds as establishing near-optimal private minimax rates under TNC.
Significance. If the results were correct, they would constitute a substantial advance: DP-SCO rates under TNC would no longer depend on the Lipschitz constant, high-probability (rather than expectation) guarantees would be obtained for heavy-tailed gradients, and the rates would match known lower bounds up to the moment-index gap. The algorithmic ideas—localized regularization together with clipping and stability-based privacy analysis—are interesting and potentially useful. However, the lower-bound construction in Theorem 4 fails to satisfy the paper's own Assumption 1, so the claimed near-optimality is not established. Since the lower bound is a central advertised contribution and is used to justify the title's claim, this is a load-bearing error rather than a presentation issue.
major comments (3)
- [Theorem 4, Eq. (16)] The construction does not satisfy Assumption 1. For x=0 (probability 1-p), sup_{w in W} ||∇f(w,0)|| = r^{θ-1} = p^{-1/k} r_k/2, since ∇f(w,0)=||w||^{θ-2}w and W=B_r. Hence E[sup_w ||∇f(w,x)||^k] ≥ (1-p)(p^{-1/k}r_k/2)^k ≈ r_k^k/(2^k p), which blows up as p → 0. For x≠0, sup_w ||∇f(w,x)|| = ||x|| + r^{θ-1} ≈ p^{-1/k}r_k, while ||2x|| = p^{-1/k}r_k/√d, so the inequality in Eq. (16) also fails pointwise on the support. The distribution Q_v therefore does not belong to F^θ_k with parameter r_k, and Theorem 4's Ω((r_k(√d/(n√ρ))^{(k-1)/k})^{θ/(θ-1)}) lower bound is unproven.
- [Theorem 1, privacy proof] The privacy accounting is internally inconsistent. The proof states that each iterate w_i is ε^2/2-zCDP and hence (2ε√log(1/δ), δ)-DP, then says that by the assumption ε ≤ √log(1/δ) 'the mechanism is (ε^2, δ)-DP, by taking ε'=ε^2.' This does not establish the claimed (ε,δ)-DP guarantee; it redefines the privacy parameter. Since Theorems 1--5 and 7 rely on this privacy guarantee, the proof needs a corrected and unambiguous composition argument.
- [Theorems 1--3, Assumption on L_f] The advertised independence of the Lipschitz constant is qualified in a way that needs stating. The theorems require L_f ≤ n^{p/2} R_{2k,n}(1/√n + (√(d log(1/δ))/(ε n))^{(k-1)/k}) with p a free hyperparameter. Because Algorithm 3 sets T_i = Θ(1/(λ_i η_i)) = Θ(n_i^p), letting p grow with L_f to cover non-polynomial Lipschitz constants makes the iteration count super-polynomial; if p is fixed, L_f is at most polynomial in n. The manuscript should clarify this trade-off explicitly. Separately, Assumption 1 is a sup-over-W moment condition, which is much stronger than pointwise gradient moment bounds; the lower-bound construction shows that this difference is not innocuous.
minor comments (5)
- [Section 2] The sentence 'A comparison to the non-private setting will be included in the final version of the paper' is a placeholder that should have been resolved before publication; if the comparison is already present elsewhere, it should be cited explicitly.
- [Table 1] The lower-bound rows for 'This paper' use ε in the displayed rates, while Theorem 4 is stated for ρ-zCDP with √ρ. The table should consistently use ρ and should indicate that the lower bound is for zCDP rather than (ε,δ)-DP.
- [Theorem 4, Eq. (16)] Even ignoring the zero-atom issue, E[||2x||^k] for the stated distribution equals r_k^k/d^{k/2}, not r_k^k, because ||2x|| = p^{-1/k}r_k/√d on the nonzero atom. The displayed identity is therefore doubly incorrect.
- [Proof of Lemma 2] The notation is confusing: the statement mixes ilde r(k), ilde e_k^1, and r^{(k)}. The intended chain of inequalities should be written as ilde r(k)= ilde e_1^{(k)} ≥ ilde e_2^{(k)} ≥ ... ≥ r^{(k)}.
- [Throughout] There are numerous typos and spelling errors ('deomenstrate', 'Thorem', 'especilally', 'paratemter', 'dateset', 'Comparion', 'withour'). A careful proofreading pass is needed.
Circularity Check
No circular derivation: core bounds follow from stated assumptions and external lemmas; the lower-bound Assumption 1 issue is a correctness gap, not circularity.
full rationale
I walked the derivation chain. The upper bounds (Theorems 1-3, 6-7) are obtained from a new localized clipped-gradient algorithm, the TNC definition, Assumption 1, and external stability/privacy tools (Feldman-Vondrak, Bun-Steinke, Feldman et al. shuffling, Lowy-Razaviyayn Prop. 40). The moment terms r~2k and r~k enter as hypotheses of the function class, not as fitted values; the bounds are not rearrangements of the definitions. The lower bounds use standard packing/Fano arguments with a constructed distribution whose scale is deliberately tuned to make E||2x||^k = r~k^k; tuning a hard instance to the class parameter is normal minimax practice, not a self-definitional collapse. The paper's self-citations (Wang et al. 2020; Hu et al. 2022; Su et al.; Ding et al.) are related-work context and none is load-bearing for the main theorems; the central claims rely on external lemmas. The admitted gap between r~2k and r~k and between high-probability and expectation forms is a tightness/correctness concern, not circularity. One genuine mathematical flaw does appear in the lower bound: Eq. (16) asserts E[sup_W ||grad f||^k] <= E||2x||^k = r~k^k, but at x=0 the supremum over W is positive, so the constructed Q_v does not satisfy Assumption 1; this is a false inequality and an unproven lower bound, but it is a correctness gap, not a reduction of the theorem to its own inputs. Under the circularity rubric, therefore, score 0.
Assumptions & free parameters
free parameters (1)
- p (Lipschitz growth exponent) =
chosen by the algorithm designer to satisfy L_f <= n^{p/2} R_{2k,n}(...)
assumptions (6)
- domain assumption Assumption 1: E[sup_{w in W} ||grad f(w,x)||^k] <= r(k) for some k>=2
- domain assumption (theta,lambda)-Tsybakov Noise Condition: F(w)-F(w*) >= lambda ||w-w*||^theta
- domain assumption Loss f(x, .) is alpha-smooth for every x
- ad hoc to paper Lipschitz constant satisfies L_f <= n^{p/2} R_{2k,n}(1/sqrt(n) + (sqrt(d log(1/delta))/(eps n))^{(k-1)/k})
- ad hoc to paper For the non-Lipschitz results, epsilon = O(sqrt(log(n/delta))/n)
- domain assumption The constraint set W is bounded with diameter D
Cite this review
Pith. "Pith review of Beyond Ordinary Lipschitz Constraints: Differentially Private Stochastic Optimization with Tsybakov Noise Condition." pith.science (2026). https://pith.science/paper/IZP5RJCM
@misc{pith2026250904668,
author = {Pith},
title = {Pith review of: Beyond Ordinary Lipschitz Constraints: Differentially Private Stochastic Optimization with Tsybakov Noise Condition},
year = {2026},
howpublished = {\url{https://pith.science/paper/IZP5RJCM}},
note = {Machine review of arXiv:2509.04668}
}
abstract
We study Stochastic Convex Optimization in the Differential Privacy model (DP-SCO). Unlike previous studies, here we assume the population risk function satisfies the Tsybakov Noise Condition (TNC) with some parameter $\theta>1$, where the Lipschitz constant of the loss could be extremely large or even unbounded, but the $\ell_2$-norm gradient of the loss has bounded $k$-th moment with $k\geq 2$. For the Lipschitz case with $\theta\geq 2$, we first propose an $(\varepsilon, \delta)$-DP algorithm whose utility bound is $\Tilde{O}\left(\left(\tilde{r}_{2k}(\frac{1}{\sqrt{n}}+(\frac{\sqrt{d}}{n\varepsilon}))^\frac{k-1}{k}\right)^\frac{\theta}{\theta-1}\right)$ in high probability, where $n$ is the sample size, $d$ is the model dimension, and $\tilde{r}_{2k}$ is a term that only depends on the $2k$-th moment of the gradient. It is notable that such an upper bound is independent of the Lipschitz constant. We then extend to the case where $\theta\geq \bar{\theta}> 1$ for some known constant $\bar{\theta}$. Moreover, when the privacy budget $\varepsilon$ is small enough, we show an upper bound of $\tilde{O}\left(\left(\tilde{r}_{k}(\frac{1}{\sqrt{n}}+(\frac{\sqrt{d}}{n\varepsilon}))^\frac{k-1}{k}\right)^\frac{\theta}{\theta-1}\right)$ even if the loss function is not Lipschitz. For the lower bound, we show that for any $\theta\geq 2$, the private minimax rate for $\rho$-zero Concentrated Differential Privacy is lower bounded by $\Omega\left(\left(\tilde{r}_{k}(\frac{1}{\sqrt{n}}+(\frac{\sqrt{d}}{n\sqrt{\rho}}))^\frac{k-1}{k}\right)^\frac{\theta}{\theta-1}\right)$.
Figures
Figures from the paper (3 more)
Reference graph
Works this paper leans on
-
[1]
Deep learning with differential privacy
Martin Abadi, Andy Chu, Ian Goodfellow, H Brendan McMahan, Ilya Mironov, Kunal Talwar, and Li Zhang. Deep learning with differential privacy. In Proceedings of the 2016 ACM SIGSAC conference on computer and communications security, pp.\ 308--318, 2016
2016
-
[2]
Differentially private assouad, fano, and le cam
Jayadev Acharya, Ziteng Sun, and Huanyu Zhang. Differentially private assouad, fano, and le cam. In Algorithmic Learning Theory, pp.\ 48--78. PMLR, 2021
work page 2021
-
[3]
Private adaptive gradient methods for convex optimization
Hilal Asi, John Duchi, Alireza Fallah, Omid Javidbakht, and Kunal Talwar. Private adaptive gradient methods for convex optimization. In International Conference on Machine Learning, pp.\ 383--392. PMLR, 2021 a
work page 2021
-
[4]
Adapting to function difficulty and growth conditions in private optimization
Hilal Asi, Daniel L \'e vy, and John C Duchi. Adapting to function difficulty and growth conditions in private optimization. Advances in Neural Information Processing Systems, 34: 0 19069--19081, 2021 b
work page 2021
-
[5]
Private stochastic convex optimization with heavy tails: Near-optimality from simple reductions
Hilal Asi, Daogao Liu, and Kevin Tian. Private stochastic convex optimization with heavy tails: Near-optimality from simple reductions. Advances in Neural Information Processing Systems, 37: 0 59174--59215, 2024
work page 2024
-
[6]
Rina Foygel Barber and John C. Duchi. Privacy and statistical risk: Formalisms and minimax bounds. arXiv preprint arXiv:1412.4451, 2014
arXiv 2014
-
[7]
Private empirical risk minimization: Efficient algorithms and tight error bounds
Raef Bassily, Adam Smith, and Abhradeep Thakurta. 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
work page 2014
-
[8]
Private stochastic convex optimization with optimal rates
Raef Bassily, Vitaly Feldman, Kunal Talwar, and Abhradeep Thakurta. Private stochastic convex optimization with optimal rates. arXiv preprint arXiv:1908.09970, 2019
arXiv 1908
Show all 61 references
-
[9]
Statistical advances in the biomedical science
Atanu Biswas, Sujay Datta, Jason P Fine, and Mark R Segal. Statistical advances in the biomedical science. Wiley Online Library, 2007
2007
-
[10]
A method for finding projections onto the intersection of convex sets in hilbert spaces
James P Boyle and Richard L Dykstra. A method for finding projections onto the intersection of convex sets in hilbert spaces. In Advances in order restricted statistical inference, pp.\ 28--47. Springer, 1986
1986
-
[11]
Propose, test, release: Differentially private estimation with high probability
Victor-Emmanuel Brunel and Marco Avella-Medina. Propose, test, release: Differentially private estimation with high probability. arXiv preprint arXiv:2002.08774, 2020
2002 arXiv
-
[12]
Concentrated differential privacy: Simplifications, extensions, and lower bounds
Mark Bun and Thomas Steinke. Concentrated differential privacy: Simplifications, extensions, and lower bounds. In Theory of Cryptography Conference, pp.\ 635--658. Springer, 2016
2016
-
[13]
Differentially private empirical risk minimization
Kamalika Chaudhuri, Claire Monteleoni, and Anand D Sarwate. Differentially private empirical risk minimization. Journal of Machine Learning Research, 12 0 (3), 2011
2011
-
[14]
Quantizing heavy-tailed data in statistical estimation:(near) minimax rates, covariate quantization, and uniform recovery
Junren Chen, Michael K Ng, and Di Wang. Quantizing heavy-tailed data in statistical estimation:(near) minimax rates, covariate quantization, and uniform recovery. IEEE Transactions on Information Theory, 70 0 (3): 0 2003--2038, 2023
2003
-
[15]
Revisiting differentially private relu regression
Meng Ding, Mingxi Lei, Liyang Zhu, Shaowei Wang, Di Wang, and Jinhui Xu. Revisiting differentially private relu regression. Advances in Neural Information Processing Systems, 37: 0 55470--55506, 2024
2024
-
[16]
Nearly optimal differentially private relu regression
Meng Ding, Mingxi Lei, Shaowei Wang, Tianhang Zheng, Di Wang, and Jinhui Xu. Nearly optimal differentially private relu regression. In The 41st Conference on Uncertainty in Artificial Intelligence, 2025
2025
-
[17]
Calibrating noise to sensitivity in private data analysis
Cynthia Dwork, Frank McSherry, Kobbi Nissim, and Adam Smith. Calibrating noise to sensitivity in private data analysis. In Theory of cryptography conference, pp.\ 265--284. Springer, 2006
2006
-
[18]
An algorithm for restricted least squares regression
Richard L Dykstra. An algorithm for restricted least squares regression. Journal of the American Statistical Association, 78 0 (384): 0 837--842, 1983
1983
-
[19]
High probability generalization bounds for uniformly stable algorithms with nearly optimal rate
Vitaly Feldman and Jan Vondrak. High probability generalization bounds for uniformly stable algorithms with nearly optimal rate. In Conference on Learning Theory, pp.\ 1270--1279. PMLR, 2019
2019
-
[20]
Private stochastic convex optimization: optimal rates in linear time
Vitaly Feldman, Tomer Koren, and Kunal Talwar. Private stochastic convex optimization: optimal rates in linear time. In Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing, pp.\ 439--449, 2020
2020
-
[21]
Hiding among the clones: A simple and nearly optimal analysis of privacy amplification by shuffling
Vitaly Feldman, Audra McMillan, and Kunal Talwar. Hiding among the clones: A simple and nearly optimal analysis of privacy amplification by shuffling. In 2021 IEEE 62nd Annual Symposium on Foundations of Computer Science (FOCS), pp.\ 954--964. IEEE, 2022
2021
-
[22]
Train faster, generalize better: Stability of stochastic gradient descent
Moritz Hardt, Benjamin Recht, and Yoram Singer. Train faster, generalize better: Stability of stochastic gradient descent. arXiv e-prints, pp.\ arXiv--1509, 2015
2015
-
[23]
High dimensional differentially private stochastic optimization with heavy-tailed data
Lijie Hu, Shuo Ni, Hanshen Xiao, and Di Wang. High dimensional differentially private stochastic optimization with heavy-tailed data. In Proceedings of the 41st ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems, pp.\ 227--236, 2022
2022
-
[24]
Pairwise learning with differential privacy guarantees
Mengdi Huai, Di Wang, Chenglin Miao, Jinhui Xu, and Aidong Zhang. Pairwise learning with differential privacy guarantees. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 34, pp.\ 694--701, 2020
2020
-
[25]
Heavy-tailed distributions and robustness in economics and finance, volume 214
Marat Ibragimov, Rustam Ibragimov, and Johan Walden. Heavy-tailed distributions and robustness in economics and finance, volume 214. Springer, 2015
2015
-
[26]
Private mean estimation of heavy-tailed distributions
Gautam Kamath, Vikrant Singhal, and Jonathan Ullman. Private mean estimation of heavy-tailed distributions. In Proceedings of 33rd Conference on Learning Theory (COLT), pp.\ 2204--2235, 2020
2020
-
[27]
Improved rates for differentially private stochastic convex optimization with heavy-tailed data
Gautam Kamath, Xingtu Liu, and Huanyu Zhang. Improved rates for differentially private stochastic convex optimization with heavy-tailed data. arXiv preprint arXiv:2106.01336, 2021
2021 arXiv
-
[28]
Improved rates for differentially private stochastic convex optimization with heavy-tailed data
Gautam Kamath, Xingtu Liu, and Huanyu Zhang. Improved rates for differentially private stochastic convex optimization with heavy-tailed data. In International Conference on Machine Learning, pp.\ 10633--10660. PMLR, 2022
2022
-
[29]
Linear convergence of gradient and proximal-gradient methods under the polyak- ojasiewicz condition
Hamed Karimi, Julie Nutini, and Mark Schmidt. Linear convergence of gradient and proximal-gradient methods under the polyak- ojasiewicz condition. In Joint European Conference on Machine Learning and Knowledge Discovery in Databases, pp.\ 795--811. Springer, 2016
2016
-
[30]
Efficient private empirical risk minimization for high-dimensional learning
Shiva Prasad Kasiviswanathan and Hongxia Jin. Efficient private empirical risk minimization for high-dimensional learning. In International Conference on Machine Learning, pp.\ 488--497, 2016
2016
-
[31]
Private convex empirical risk minimization and high-dimensional regression
Daniel Kifer, Adam Smith, and Abhradeep Thakurta. Private convex empirical risk minimization and high-dimensional regression. In Conference on Learning Theory, pp.\ 25--1, 2012
2012
-
[32]
Fast rates for exp-concave empirical risk minimization
Tomer Koren and Kfir Y Levy. Fast rates for exp-concave empirical risk minimization. In NIPS, pp.\ 1477--1485, 2015
2015
-
[33]
Fast rates of erm and stochastic approximation: Adaptive to error bound conditions
Mingrui Liu, Xiaoxuan Zhang, Lijun Zhang, Rong Jin, and Tianbao Yang. Fast rates of erm and stochastic approximation: Adaptive to error bound conditions. arXiv preprint arXiv:1805.04577, 2018
2018 arXiv
-
[34]
Robust and differentially private mean estimation
Xiyang Liu, Weihao Kong, Sham Kakade, and Sewoong Oh. Robust and differentially private mean estimation. arXiv preprint arXiv:2102.09159, 2021
2021 arXiv
-
[35]
Private stochastic optimization with large worst-case lipschitz parameter: Optimal rates for (non-smooth) convex losses and extension to non-convex losses
Andrew Lowy and Meisam Razaviyayn. Private stochastic optimization with large worst-case lipschitz parameter: Optimal rates for (non-smooth) convex losses and extension to non-convex losses. In International Conference on Algorithmic Learning Theory, pp.\ 986--1054. PMLR, 2023
2023
-
[36]
Privacy integrated queries: an extensible platform for privacy-preserving data analysis
Frank D McSherry. Privacy integrated queries: an extensible platform for privacy-preserving data analysis. In Proceedings of the 2009 ACM SIGMOD International Conference on Management of data, pp.\ 19--30, 2009
2009
-
[37]
Optimal rates for first-order stochastic convex optimization under tsybakov noise condition
Aaditya Ramdas and Aarti Singh. Optimal rates for first-order stochastic convex optimization under tsybakov noise condition. arXiv preprint arXiv:1207.3012, 2012
2012 arXiv
-
[38]
Algorithmic connections between active learning and stochastic convex optimization
Aaditya Ramdas and Aarti Singh. Algorithmic connections between active learning and stochastic convex optimization. In International Conference on Algorithmic Learning Theory, pp.\ 339--353. Springer, 2013
2013
-
[39]
Is interaction necessary for distributed private learning? In 2017 IEEE Symposium on Security and Privacy (SP), pp.\ 58--77
Adam Smith, Abhradeep Thakurta, and Jalaj Upadhyay. Is interaction necessary for distributed private learning? In 2017 IEEE Symposium on Security and Privacy (SP), pp.\ 58--77. IEEE, 2017
2017
-
[40]
Faster rates of private stochastic convex optimization
Jinyan Su, Lijie Hu, and Di Wang. Faster rates of private stochastic convex optimization. In International Conference on Algorithmic Learning Theory, pp.\ 995--1002. PMLR, 2022
2022
-
[41]
Differentially private stochastic convex optimization in (non)-euclidean space revisited
Jinyan Su, Changhong Zhao, and Di Wang. Differentially private stochastic convex optimization in (non)-euclidean space revisited. In Uncertainty in Artificial Intelligence, pp.\ 2026--2035. PMLR, 2023
2026
-
[42]
Faster rates of differentially private stochastic convex optimization
Jinyan Su, Lijie Hu, and Di Wang. Faster rates of differentially private stochastic convex optimization. Journal of Machine Learning Research, 25 0 (114): 0 1--41, 2024
2024
-
[43]
Private stochastic convex optimization and sparse learning with heavy-tailed data revisited
Youming Tao, Yulian Wu, Xiuzhen Cheng, and Di Wang 0015. Private stochastic convex optimization and sparse learning with heavy-tailed data revisited. In IJCAI, pp.\ 3947--3953, 2022 a
2022
-
[44]
Optimal rates of (locally) differentially private heavy-tailed multi-armed bandits
Youming Tao, Yulian Wu, Peng Zhao, and Di Wang. Optimal rates of (locally) differentially private heavy-tailed multi-armed bandits. In International Conference on Artificial Intelligence and Statistics, pp.\ 1546--1574. PMLR, 2022 b
2022
-
[45]
Differentially private sparse linear regression with heavy-tailed responses
Xizhi Tian, Meng Ding, Touming Tao, Zihang Xiang, and Di Wang. Differentially private sparse linear regression with heavy-tailed responses. arXiv preprint arXiv:2506.06861, 2025
2025 arXiv
-
[46]
Fast rates in statistical and online learning
Tim van Erven, Peter D Gr \"u nwald, Nishant A Mehta, Mark D Reid, and Robert C Williamson. Fast rates in statistical and online learning. Journal of Machine Learning Research, 16: 0 1793--1861, 2015
2015
-
[47]
Differentially private _1 -norm linear regression with heavy-tailed data
Di Wang and Jinhui Xu. Differentially private _1 -norm linear regression with heavy-tailed data. In 2022 IEEE International Symposium on Information Theory (ISIT), pp.\ 1856--1861. IEEE, 2022
2022
-
[48]
Private least absolute deviations with heavy-tailed data
Di Wang and Jinhui Xu. Private least absolute deviations with heavy-tailed data. Theoretical Computer Science, 1030: 0 115071, 2025
2025
-
[49]
Differentially private empirical risk minimization revisited: Faster and more general
Di Wang, Minwei Ye, and Jinhui Xu. Differentially private empirical risk minimization revisited: Faster and more general. In Advances in Neural Information Processing Systems, pp.\ 2722--2731, 2017
2017
-
[50]
Empirical risk minimization in non-interactive local differential privacy revisited
Di Wang, Marco Gaboardi, and Jinhui Xu. Empirical risk minimization in non-interactive local differential privacy revisited. In Advances in Neural Information Processing Systems, pp.\ 965--974, 2018
2018
-
[51]
Differentially private empirical risk minimization with non-convex loss functions
Di Wang, Changyou Chen, and Jinhui Xu. Differentially private empirical risk minimization with non-convex loss functions. In International Conference on Machine Learning, pp.\ 6526--6535, 2019 a
2019
-
[52]
Noninteractive locally private learning of linear models via polynomial approximations
Di Wang, Adam Smith, and Jinhui Xu. Noninteractive locally private learning of linear models via polynomial approximations. In Algorithmic Learning Theory, pp.\ 897--902, 2019 b
2019
-
[53]
On differentially private stochastic convex optimization with heavy-tailed data
Di Wang, Hanshen Xiao, Srinivas Devadas, and Jinhui Xu. On differentially private stochastic convex optimization with heavy-tailed data. In International Conference on Machine Learning, pp.\ 10081--10091. PMLR, 2020
2020
-
[54]
Statistical methods for the analysis of biomedical data, volume 371
Robert F Woolson and William R Clarke. Statistical methods for the analysis of biomedical data, volume 371. John Wiley & Sons, 2011
2011
-
[55]
Bolt-on differential privacy for scalable stochastic gradient descent-based analytics
Xi Wu, Fengan Li, Arun Kumar, Kamalika Chaudhuri, Somesh Jha, and Jeffrey Naughton. Bolt-on differential privacy for scalable stochastic gradient descent-based analytics. In Proceedings of the 2017 ACM International Conference on Management of Data, pp.\ 1307--1322. ACM, 2017
2017
-
[56]
Differentially private episodic reinforcement learning with heavy-tailed rewards
Yulian Wu, Xingyu Zhou, Sayak Ray Chowdhury, and Di Wang. Differentially private episodic reinforcement learning with heavy-tailed rewards. In International Conference on Machine Learning, pp.\ 37880--37918. PMLR, 2023
2023
-
[57]
On private and robust bandits
Yulian Wu, Xingyu Zhou, Youming Tao, and Di Wang. On private and robust bandits. Advances in Neural Information Processing Systems, 36, 2024
2024
-
[58]
Stochastic convex optimization: Faster local growth implies faster global convergence
Yi Xu, Qihang Lin, and Tianbao Yang. Stochastic convex optimization: Faster local growth implies faster global convergence. In International Conference on Machine Learning, pp.\ 3821--3830. PMLR, 2017
2017
-
[59]
Differentially private pairwise learning revisited
Zhiyu Xue, Shaoyang Yang, Mengdi Huai, and Di Wang. Differentially private pairwise learning revisited. In 30th International Joint Conference on Artificial Intelligence, IJCAI 2021, pp.\ 3242--3248. International Joint Conferences on Artificial Intelligence Organization, 2021
2021
-
[60]
A simple analysis for exp-concave empirical minimization with arbitrary convex regularizer
Tianbao Yang, Zhe Li, and Lijun Zhang. A simple analysis for exp-concave empirical minimization with arbitrary convex regularizer. In International Conference on Artificial Intelligence and Statistics, pp.\ 445--453. PMLR, 2018
2018
-
[61]
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 gl...
Reviewed August 5, 2026 · model on record in the stance chip above.
Discussion (0). Sign in to comment.