REVIEW 2 major objections 6 minor 23 references
Differentially Private Random Block Coordinate Descent
T0 review · 2 major / 6 minor · reviewed 2026-08-11 · deepseek-v4-flash
Pith's one-line read This paper introduces DP-SkGD, a private random block coordinate descent method that samples several coordinates per iteration via a sketch, and proves it generalizes DP-CD and DP-SGD, matching their utility and improving on both via…
desk verdict Solid new DP block-coordinate descent theory with two fixable presentation issues: an ambiguous strong-convexity assumption and a promised-but-missing experiments section. 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 central object is the unbiased diagonal sketch $C = \operatorname{Diag}(c_1,\dots,c_d)$ with $c_j = 1/p_j$ if $j \in S$ and $c_j = 0$ otherwise, so that $\mathbb{E}[C x] = x$ for every vector $x$. The update $\theta_{k+1} = \theta_k - \Gamma C(\nabla f(\theta_k)+\eta)$ therefore stays unbiased in expectation, and the diagonal step-size matrix $\Gamma = P M^{-1}$ couples the sampling probabilities $p_j$ with the component-wise smoothness constants $M_j$. The privacy analysis converts component Lipschitzness into the sensitivity bound $\Delta_U(\nabla \ell) \le 2 L_U$ (Lemma 3.9), which fixes the Gaussian noise scale $\sigma_U$ for each block $U$. All of these choices are summarized by the scalar $\Sigma_S^2 = \mathbb{E}[\| C L_S \mathbf{1} \|_{P M^{-1}}^2]$, which controls both the privacy-noise contribution and the convergence rate, and which the paper evaluates for full, single-coordinate, uniform-block, and importance-sampled-block strategies.
What would settle it
Take a concrete convex quadratic $f(w)=\frac12\|w\|^2_M$ with known $M$ and $L_U$, run DP-SkGD with the prescribed step sizes and noise scales for a range of $n,\varepsilon,\delta$, and measure $E[f(w_{\rm priv})-f^*]$; the theorem predicts the excess risk follows $O(\Sigma_S R_{M P^{-1}} n^{-1}\varepsilon^{-1}\sqrt{\log(1/\delta)})$, so a systematic deviation, such as an extra $\sqrt{d}$ factor or a different dependence on $\varepsilon$, would refute the claimed rate. For the privacy claim, compute the Rényi divergence between the algorithm's outputs on two datasets differing in one point and verify the $(\varepsilon,\delta)$-DP guarantee; a violation for some $U$ would indicate the sensitivity bound $2L_U$ is not tight under Assumption 3.7.
Extended reading notes
Core claim
On its own terms, the central claim is Theorem 4.1 together with Theorem 4.2: Algorithm 1, called DP-SkGD, with step sizes $\Gamma = P M^{-1}$ and per-block noise scales $\sigma_U^2 = 12 L_U^2 K T \log(1/\delta)/(n^2 \varepsilon^2)$, is $(\varepsilon,\delta)$-differentially private for losses that are differentiable, convex, and component-Lipschitz, and its utility is $O(\Sigma_S R_{M P^{-1}} n^{-1} \varepsilon^{-1} \sqrt{\log(1/\delta)})$ in the convex case and $\tilde O(\mu^{-1} \max_i\{M_i/p_i\} \Sigma_S^2 n^{-2} \varepsilon^{-2} \log(1/\delta))$ in the strongly convex case. The quantity $\Sigma_S^2 = \mathbb{E}[\| C L_S \mathbf{1} \|_{P M^{-1}}^2]$ is the effective privacy cost of the chosen sampling distribution: it appears linearly in the convex rate and quadratically in the strongly convex rate. Full-set sampling gives $\Sigma_S^2 = L^2 \operatorname{Tr}(M^{-1})$, recovering DP-SGD, while uniform single-coordinate sampling gives $\Sigma_S^2 = \|L\|_{M^{-1}}^2$, recovering DP-CD; the paper further specializes these bounds to uniform and importance-sampled block partitions in Table 1.
Load-bearing premise
The load-bearing premise is that, for every coordinate block the sampler can draw, the loss changes by at most a block-dependent Lipschitz constant $L_U$; the privacy proof converts this into the sensitivity bound $\Delta_U(\nabla\ell)\le 2L_U$, so if $L_U$ is large or grows with block size, the noise needed for privacy grows and the utility guarantees weaken, and without this assumption the privacy analysis does not go through.
Editorial extensions
If this is right
- DP-SkGD interpolates between DP-CD and DP-SGD: uniform single-coordinate sampling recovers DP-CD and full-set sampling recovers DP-SGD, so the guarantees proved here apply to both prior algorithms as special cases.
- For block sampling the convex excess risk is $O(\|L_{\{A_1,\dots,A_b\}}\|_{M^{-1}} R_{M P^{-1}} \sqrt{\log(1/\delta)}/(n\varepsilon))$; with uniform block probabilities this becomes $O(\|L\|_{M^{-1}} R_M \sqrt{b}/(n\varepsilon))$, so the block count $b$ enters only through a square root in the convex case.
- Importance sampling with $q_i = \max_{j\in A_i} M_j / \sum_i \max_{j\in A_i} M_j$ replaces the factor $\max_i\{M_i/p_i\}$ by $\sum_i \max_{j\in A_i} M_j$, which is the mechanism behind the claimed up-to-$\sqrt{d}$ speedups over DP-CD and DP-SGD in heterogeneous problems.
- In the strongly convex regime, the noise term is $\tilde O(\mu^{-1} \max_i\{M_i/p_i\}\Sigma_S^2 n^{-2}\varepsilon^{-2}\log(1/\delta))$, so choosing block probabilities proportional to block-wise smoothness gives a strictly better dependence on the smoothness constants than uniform sampling.
- The utility analysis covers plain ERM without a separable regularizer; the authors explicitly leave composite ERM with non-separable regularizers and general-matrix smoothness to future work.
Reading between the lines
- Editorial inference: the proof structure suggests a general design rule—minimize $\Sigma_S R_{M P^{-1}}$ (convex) or $\max_i\{M_i/p_i\}\Sigma_S^2$ (strongly convex) over the sampling distribution—which could be applied to non-block sketch families such as nice sampling; the paper only analyzes block, single-coordinate, and full sampling.
- Editorial inference: the same mechanism would allow an adaptive-privacy variant in which coordinates with small estimated $L_U$ are updated more often and receive less noise; the paper does not analyze adaptive budgets, but the per-block noise scales it introduces make such a variant natural.
- Editorial inference: the paper's numerical appendix states that experiments will be shown during rebuttal, so the predicted speedups remain unverified; a direct check would compare measured excess risk on a quadratic with known $M$ and $L_U$ against the $\Sigma_S$-dependent rates.
- Editorial inference: if the analysis extends to data-dependent sketches and variance reduction, as the authors list for future work, DP-SkGD could plausibly provide differentially private composite coordinate descent with rates close to non-private SkGD.
Signed reviews
Editorial analysis
A structured set of objections, weighed in public.
Referee Report
Summary. This paper introduces DP-SkGD, a differentially private random block coordinate descent algorithm based on unbiased diagonal sketches. At each inner iteration the algorithm samples a random subset of coordinates, computes the corresponding gradient coordinates, and adds Gaussian noise calibrated to coordinate-wise Lipschitz constants. The paper proves a privacy guarantee via RDP composition (Theorem 4.1) and utility bounds for convex and strongly convex ERM (Theorem 4.2). It also analyzes block sampling and importance sampling, compares the resulting rates with DP-CD, DP-SGD, and DP-SVRG, and summarizes them in Table 1. Proofs are provided in appendices.
Significance. If correct, the proposed framework unifies private coordinate descent (DP-CD) and private gradient descent (DP-SGD) and offers a principled way to exploit coordinate-wise smoothness to reduce the privacy cost, with potential speedups up to a factor of sqrt(d). The paper gives explicit non-asymptotic (up to log factors) utility rates and identifies regimes of improvement. However, the manuscript currently contains no experiments despite a claim to that effect in Section 2.1, and the strongly convex statement in Theorem 4.2 is ambiguous about the norm used in the strong convexity assumption. These issues affect the completeness and the central claims of the paper as submitted.
major comments (2)
- [Theorem 4.2, Assumption 3.5, Appendix E.2] The strongly convex case of Theorem 4.2 states 'Assume f is µ-strongly convex (Assumption 3.5)' and gives a rate O~( (1/µ) max_i {M_i/p_i} Σ_S^2 log(1/δ)/(n^2 ε^2) ). However, Assumption 3.5 defines strong convexity with respect to the norm ||·||_M, while the proof in Appendix E.2 uses the Euclidean inequality f(w) ≥ f(w*) + (µ/2)||w-w*||^2. If Assumption 3.5 is taken literally, the proof is not justified: µ_M-strong convexity w.r.t. ||·||_M only yields Euclidean strong convexity with parameter at least µ_M * min_i M_i, so the rate would carry an extra factor of 1/min_i M_i or require replacing the norm in the statement. The appendix's parenthetical '(µ = µI, Assumption 3.5)' suggests the intended meaning is Euclidean strong convexity, but this is not stated in the main theorem. This ambiguity affects the strongly convex entries in Table 1 and the claimed reduction to DP-SGD, so it needs to be resolved explicitly.
- [Section 2.1 and Appendix B] The contributions list in Section 2.1 states that 'In Appendix B, we evaluate the practical performance of our algorithm through extensive experiments.' Appendix B, however, contains only the sentence 'We will show the experimental results during the rebuttal.' Thus the advertised experimental evaluation is absent from the manuscript. This is an explicit gap: either the experiments must be included in a revision, or the claim must be removed from the contributions.
minor comments (6)
- [Section 4.1] The phrase 'the theorem bellow' should read 'the theorem below.'
- [Section 4.3.1] The phrase 'strongly strongly convex' contains a duplicated word and should be 'strongly convex.'
- [Section 4.2.1] The sentence 'For each i ∈ [n], let B(i) indicate which block i belongs to' uses [n] for what is a coordinate index; it should be i ∈ [d].
- [Section 3.5, after Lemma D.7] The sentence 'Since this result holds for any α it is possible to find the minimum with respect to it' is a fragment; please rephrase.
- [Section 4.2 and Assumption 3.7] The quantity L_S in Theorem 4.2 is used as a scalar, while Assumption 3.7 defines L_U for each U; consider clarifying the relationship to avoid confusion.
- [Section 3.4] Assumption 3.7 is central to the privacy analysis, but the paper does not discuss how L_U scales with the block size for typical losses; a brief discussion of examples satisfying the assumption would improve the paper's applicability.
Circularity Check
No circularity: DP-SkGD's privacy and utility bounds are derived in closed form from stated component-Lipschitz/smoothness assumptions and standard RDP composition; the only self-citations are attributional and not load-bearing.
full rationale
Walking the derivation chain: Algorithm 1's update (theta_{k+1} = theta_k - Gamma C(nabla f(theta_k) + eta)) is combined with Assumption 3.7's component Lipschitzness to derive sensitivity Delta_U(nabla ell) <= 2 L_U in Lemma 3.9; Theorem 4.1 then calibrates sigma_U^2 via standard RDP composition (Mironov; Mangold et al. Lemma D.8). No fitted quantity appears: sigma_U, K, and T are set in closed form from L_U, n, epsilon, delta, Sigma_S, and R_{M P^{-1}}; K is chosen to minimize the algebraically derived right-hand side, not to match the stated rate. The utility proofs in Appendix E use only stated convexity/M-smoothness and the unbiased-sketch variance lemma, and Sigma_S is a computed norm term, not a parameter fitted to the target bound. The importance-sampling probabilities q_i are chosen from the smoothness constants M_j (minimizing an upper bound on R_{M P^{-1}}), not from the target utility rate; the improvement claim is a genuine comparison of the resulting closed-form bounds. The only self-citations (Safaryan et al. for SkGD, Hanzely et al., and Richtarik's coordinate descent work) are motivational or algorithmic attribution; no load-bearing theorem is imported from them, and the proofs are self-contained. The strong-convexity norm-mismatch raised by the skeptic is a correctness issue (Euclidean versus M-norm strong convexity in Theorem 4.2), not a circularity issue; even under either reading the bound is derived from assumptions rather than being assumed. Hence no step reduces by construction to its own input.
Assumptions & free parameters
assumptions (6)
- domain assumption Each loss ell(.;zeta) is differentiable and convex (Assumptions 3.3 and 3.4).
- domain assumption f is M-component-smooth (Assumption 3.6).
- domain assumption ell is L_S-component-Lipschitz for every U in Range(S) (Assumption 3.7).
- domain assumption In the strongly convex case, f is mu-strongly convex (Assumption 3.5 with mu = mu I).
- standard math Central model of DP and standard RDP composition theorems (Mironov, 2017).
- domain assumption Sampling distribution S is proper and nonvacuous (Assumption 3.1).
Cite this review
Pith. "Pith review of Differentially Private Random Block Coordinate Descent." pith.science (2026). https://pith.science/paper/ZJXW5TUF
@misc{pith2026241217054,
author = {Pith},
title = {Pith review of: Differentially Private Random Block Coordinate Descent},
year = {2026},
howpublished = {\url{https://pith.science/paper/ZJXW5TUF}},
note = {Machine review of arXiv:2412.17054}
}
read the original abstract
Coordinate Descent (CD) methods have gained significant attention in machine learning due to their effectiveness in solving high-dimensional problems and their ability to decompose complex optimization tasks. However, classical CD methods were neither designed nor analyzed with data privacy in mind, a critical concern when handling sensitive information. This has led to the development of differentially private CD methods, such as DP-CD (Differentially Private Coordinate Descent) proposed by Mangold et al. (ICML 2022), yet a disparity remains between non-private CD and DP-CD methods. In our work, we propose a differentially private random block coordinate descent method that selects multiple coordinates with varying probabilities in each iteration using sketch matrices. Our algorithm generalizes both DP-CD and the classical DP-SGD (Differentially Private Stochastic Gradient Descent), while preserving the same utility guarantees. Furthermore, we demonstrate that better utility can be achieved through importance sampling, as our method takes advantage of the heterogeneity in coordinate-wise smoothness constants, leading to improved convergence rates.
Reference graph
Works this paper leans on
-
[1]
Bassily, R., Smith, A., and Thakurta, A. (2014). Private empirical risk minimization: Efficient algorithms and tight error bounds. In 2014 IEEE 55th annual symposium on foundations of computer science , pages 464--473. IEEE
work page 2014
-
[2]
Chaudhuri, K., Monteleoni, C., and Sarwate, A. D. (2011). Differentially private empirical risk minimization. Journal of Machine Learning Research , 12(3)
2011
-
[3]
Dwork, C. (2008). Differential privacy: A survey of results. In International conference on theory and applications of models of computation , pages 1--19. Springer
work page 2008
-
[4]
Dwork, C., Roth, A., et al. (2014). The algorithmic foundations of differential privacy. Foundations and Trends in Theoretical Computer Science , 9(3--4):211--407
work page 2014
-
[5]
Fercoq, O. and Richt \'a rik, P. (2015). Accelerated, parallel, and proximal coordinate descent. SIAM Journal on Optimization , 25(4):1997--2023
work page 2015
-
[6]
Hanzely, F., Kovalev, D., and Richtarik, P. (2020). Variance reduced coordinate descent with acceleration: New method with a surprising application to finite-sum problems. In International Conference on Machine Learning , pages 4039--4048. PMLR
work page 2020
-
[7]
Hanzely, F., Mishchenko, K., and Richt \'a rik, P. (2018). Sega: Variance reduction via gradient sketching. Advances in Neural Information Processing Systems , 31
work page 2018
-
[8]
Liese, F. and Vajda, I. (1987). Convex statistical distances. (No Title)
work page 1987
Show all 23 references
-
[9]
Lin, Q., Lu, Z., and Xiao, L. (2014). An accelerated proximal coordinate gradient method. Advances in Neural Information Processing Systems , 27
2014
-
[10]
Mangold, P., Bellet, A., Salmon, J., and Tommasi, M. (2022). Differentially private coordinate descent for composite empirical risk minimization. In Chaudhuri, K., Jegelka, S., Song, L., Szepesvari, C., Niu, G., and Sabato, S., editors, Proceedings of the 39th International Co...
2022
-
[11]
Mironov, I. (2017). R \'e nyi differential privacy. In 2017 IEEE 30th computer security foundations symposium (CSF) , pages 263--275. IEEE
2017
-
[12]
Nesterov, Y. (2012). Efficiency of coordinate descent methods on huge-scale optimization problems. SIAM Journal on Optimization , 22(2):341--362
2012
-
[13]
and Stich, S
Nesterov, Y. and Stich, S. U. (2017). Efficiency of the accelerated coordinate descent method on structured optimization problems. SIAM Journal on Optimization , 27(1):110--123
2017
-
[14]
R \'e nyi, A. (1961). On measures of entropy and information. In Proceedings of the fourth Berkeley symposium on mathematical statistics and probability, volume 1: contributions to the theory of statistics , volume 4, pages 547--562. University of California Press
1961
-
[15]
and Tak \'a c , M
Richt \'a rik, P. and Tak \'a c , M. (2016). Parallel coordinate descent methods for big data optimization. Mathematical Programming , 156:433--484
2016
-
[16]
Safaryan, M., Hanzely, F., and Richt \'a rik, P. (2021). Smoothness matrices beat smoothness constants: Better communication compression techniques for distributed optimization. Advances in Neural Information Processing Systems , 34:25688--25702
2021
-
[17]
and Zhang, T
Shalev-Shwartz, S. and Zhang, T. (2013a). Accelerated mini-batch stochastic dual coordinate ascent. Advances in Neural Information Processing Systems , 26
2013
-
[18]
and Zhang, T
Shalev-Shwartz, S. and Zhang, T. (2013b). Stochastic dual coordinate ascent methods for regularized loss minimization. Journal of Machine Learning Research , 14(1)
2013
-
[19]
M., Tu, S., Xu, Y., and Yin, W
Shi, H.-J. M., Tu, S., Xu, Y., and Yin, W. (2016). A primer on coordinate descent algorithms. arXiv preprint arXiv:1610.00040
2016 arXiv
-
[20]
Shokri, R., Stronati, M., Song, C., and Shmatikov, V. (2017). Membership inference attacks against machine learning models. In 2017 IEEE symposium on security and privacy (SP) , pages 3--18. IEEE
2017
-
[21]
and Harremos, P
Van Erven, T. and Harremos, P. (2014). R \'e nyi divergence and kullback-leibler divergence. IEEE Transactions on Information Theory , 60(7):3797--3820
2014
-
[22]
Wang, D., Ye, M., and Xu, J. (2017). Differentially private empirical risk minimization revisited: Faster and more general. Advances in Neural Information Processing Systems , 30
2017
-
[23]
Wright, S. J. (2015). Coordinate descent algorithms. Mathematical programming , 151(1):3--34
2015
Reviewed August 11, 2026 · model on record in the stance chip above.
Discussion (0). Continue with ORCID to comment.