{"id":"2db6bed1-b1d2-49f3-8fcf-2d59e3b4247f","arxiv_id":"2412.17054","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":6.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"DP-SkGD adds calibrated Gaussian noise to sketched block coordinate descent, recovers DP-SGD and DP-CD as special cases, and gets faster rates via importance sampling.","lead":"This paper proposes DP-SkGD, a differentially private optimization algorithm that updates random blocks of coordinates using sketch matrices, and proves privacy and convergence guarantees. It unifies earlier private coordinate descent and private gradient descent, and shows that importance sampling can improve convergence when coordinate smoothness is heterogeneous.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Strong-convexity norm mismatch in Theorem 4.2 can change the utility rate by a condition-number factor.","rationale":"The paper's central convex utility claim appears mathematically sound: the privacy composition is standard RDP, the sensitivity bound from component Lipschitzness is correctly derived via Lemma C.1, and the convex utility recursion in Lemma E.1 is valid (even though its proof has a minor sign slip, the stated bound is looser and still true). The reader's identified weakest assumption, Assumption 3.7, is indeed load-bearing because L_U enters both the noise scale and the Σ_S term, but the rates are honestly stated in terms of L_U; if L_U grows with block size, the utility bounds degrade transparently. The missing experiments in Appendix B are a support gap for the practical claims, not a threat to the theorem. The strongest genuine risk to the stated central claim is the ambiguity in the strongly convex part of Theorem 4.2: the proof uses Euclidean strong convexity while citing an M-norm assumption. If the intended assumption is M-strong convexity, the rate as written is optimistic by at least a factor of M_min. This is fixable but must be clarified before the result can be accepted as stated. The reader's CONDITIONAL verdict remains appropriate, hence UNCHANGED.","tokens_in":19341,"tokens_out":51892,"duration_ms":409443,"concrete_test":"Independently re-derive the strongly convex recursion in Appendix E.2 using Assumption 3.5 as written: start from the M-strong convexity inequality f(w) >= f(w*) + (µ_M/2)||w-w*||_M^2, and derive the contraction factor for K = 2(1 + (1/µ_M) max_i{M_i/p_i}). Check whether the resulting rate equals the stated one or acquires an extra factor 1/M_min (or requires µ to be redefined as the Euclidean strong convexity constant). Then restate Theorem 4.2 with the assumption actually used.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The strongly convex statement of Theorem 4.2 says 'Assume f is µ-strongly convex (Assumption 3.5).' Assumption 3.5 defines µ_M-strong convexity with respect to ||·||_M, but the proof in Appendix E.2 (and the comparison in Section 4.3.1) uses the Euclidean inequality f(w) >= f(w*) + (µ/2)||w-w*||^2, which corresponds to M=I in Assumption 3.5. These two readings are not interchangeable: if f is µ_M-strongly convex w.r.t. ||·||_M, then the Euclidean strong convexity parameter is only guaranteed to be at least µ_M * M_min (since ||w||_M^2 >= M_min ||w||^2). Substituting the proof's Euclidean step introduces an unaccounted factor of 1/M_min, or requires replacing Σ_S and the norm in the rate. The stated rate O~( (1/µ) max_i{M_i/p_i} Σ_S^2 log(1/δ)/(n^2 ε^2) ) and its DP-SGD reduction in Table 1 therefore depend on which definition is meant. Because the theorem cites Assumption 3.5, the default reading is the M-norm one, under which the proof's Euclidean contraction is not justified. This directly affects the second half of the central claim, not just constants.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","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.","tokens_in":19580,"tokens_out":15845,"duration_ms":127190,"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":[{"comment":"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":"Theorem 4.2, Assumption 3.5, Appendix E.2"},{"comment":"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.","section":"Section 2.1 and Appendix B"}],"minor_comments":[{"comment":"The phrase 'the theorem bellow' should read 'the theorem below.'","section":"Section 4.1"},{"comment":"The phrase 'strongly strongly convex' contains a duplicated word and should be 'strongly convex.'","section":"Section 4.3.1"},{"comment":"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":"Section 4.2.1"},{"comment":"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":"Section 3.5, after Lemma D.7"},{"comment":"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":"Section 4.2 and Assumption 3.7"},{"comment":"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.","section":"Section 3.4"}],"recommendation":"major_revision","confidential_remarks":"The missing experiments are a serious completeness issue for a journal submission; if the authors cannot provide them, the contribution statement should be amended accordingly. The strong convexity norm ambiguity is a fixable but load-bearing issue that must be addressed before the paper can be accepted."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Colleague,\n\nThe short version: this is a solid theory paper that deserves peer review, but it ships with two issues that need fixing before I'd trust the stated rates: an ambiguous strong-convexity assumption and an empty experiments appendix.\n\nWhat's new: the DP-SkGD algorithm, which adds Gaussian noise to a sketched gradient so you can update blocks of coordinates with varying probabilities under differential privacy. The reductions to DP-CD and DP-SGD are explicit, and the block-sampling analysis is genuinely new. The noise scaling works because the sketch divides by sampling probabilities and the sensitivity bound from component Lipschitzness (Lemma 3.9) feeds cleanly into RDP composition. The utility recursions in Appendix E check out for the convex case. The importance-sampling rates in Table 1 are a real improvement over uniform sampling, matching the known CD acceleration story.\n\nWhere it's soft. First, the strong-convexity statement of Theorem 4.2 cites Assumption 3.5, which defines µ_M-strong convexity with respect to the M-norm, but the proof in E.2 uses the Euclidean inequality f(w) ≥ f(w*) + (µ/2)||w−w*||^2. The appendix parenthetical '(µ=µ_I)' suggests Euclidean was intended, but the main text doesn't say that. If the reader uses the M-norm reading, the proof doesn't justify the contraction step, and the rate can change by a factor on the order of 1/M_min. This needs a one-line fix, but it's load-bearing for the strongly convex claim. Second, Appendix B is empty: the text promises 'extensive experiments' and the appendix says they will be shown 'during the rebuttal.' For a math paper that's not disqualifying, but it undercuts the 'demonstrate better utility' phrasing. Third, the comparisons to DP-SGD and DP-CD in Section 4.3 are heuristic, not worst-case; the √d speedup is a real effect under the stated coordinate heterogeneity, but it is not a universal improvement.\n\nWho it's for: people working on private ERM and private first-order methods. It introduces a useful new primitive, and the block-sampling analysis will be referenced. I would send it to review; the fixes are presentation-level, not structural.\n\nRecommendation: engage with it, but ask for a revision that resolves the norm ambiguity and either adds experiments or clearly states they are absent.","headline":"Solid new DP block-coordinate descent theory with two fixable presentation issues: an ambiguous strong-convexity assumption and a promised-but-missing experiments section.","tokens_in":20147,"tokens_out":6049,"would_cite":true,"duration_ms":49440,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["90C25","90C06","68W20"],"pacs":[],"model":"deepseek-v4-flash","headline":"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…","keywords":["differential privacy","random block coordinate descent","sketched gradient descent","importance sampling","empirical risk minimization","Rényi differential privacy","smoothness matrix","convergence rate"],"falsifier":"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.","tokens_in":19142,"feed_emoji":"🔒","tokens_out":15182,"duration_ms":117209,"temperature":0.7,"pith_summary":"Coordinate descent methods are fast on high-dimensional problems but were not designed to protect data privacy. This paper proposes DP-SkGD, a differentially private random block coordinate descent method that updates a randomly chosen subset of coordinates at each step using an unbiased sketch matrix and per-block Gaussian noise. Under a component-wise Lipschitzness assumption it proves the method is $(\\varepsilon,\\delta)$-differentially private and, for convex objectives, reaches expected suboptimality $O(\\Sigma_S R_{M P^{-1}} n^{-1} \\varepsilon^{-1} \\sqrt{\\log(1/\\delta)})$; for strongly convex objectives it gives $\\tilde O\\!\\left(\\mu^{-1} \\max_i \\{M_i/p_i\\}\\, \\Sigma_S^2\\, n^{-2} \\varepsilon^{-2} \\log(1/\\delta)\\right)$. The same algorithm reduces to DP-CD when a single coordinate is sampled uniformly and to DP-SGD when the full set is always sampled, so the paper claims to unify the two prior methods. By choosing sampling probabilities through importance sampling, the rates improve when smoothness varies across coordinates, which the authors show can yield up to a $\\sqrt{d}$ speedup over DP-CD and DP-SGD.","feed_headline":"One private descent algorithm unifies DP-CD and DP-SGD","feed_subtitle":"Choosing blocks by importance sampling preserves the same utility guarantees and can speed convergence by up to sqrt(d).","key_machinery":"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.","core_discovery":"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.","pith_inferences":["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."],"forward_implications":["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."],"supporting_citations":[{"why":"Defines DP-CD, the single-coordinate baseline this method generalizes, and provides the RDP-to-DP conversion lemma used in the privacy proof.","marker":"Mangold et al. (2022)"},{"why":"Supplies the SkGD sketched-gradient framework and smoothness-matrix viewpoint that DP-SkGD adapts to the private setting.","marker":"Safaryan et al. (2021)"},{"why":"Establishes DP-SGD and its utility guarantees; DP-SkGD reduces to this method when the sketch always selects the full set.","marker":"Bassily et al. (2014)"},{"why":"Provides the Rényi differential privacy definitions and composition theorems underlying Theorem 4.1.","marker":"Mironov (2017)"},{"why":"Supplies the Gaussian mechanism and sensitivity-calibration background used to convert component Lipschitzness into noise scales.","marker":"Dwork et al. (2014)"},{"why":"Gives the DP-SVRG baseline compared in Table 1.","marker":"Wang et al. (2017)"}],"fun_headline_variants":["Private block descent: a single rule for DP-CD and DP-SGD","Importance sampling speeds up private block coordinate descent","Unified private CD: generalizes DP-CD and DP-SGD","DP block CD: covers CD and SGD via sketch matrices","One private block descent to cover CD and SGD"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"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.","fun_headline_variants_meta":{"raw":{"variants":["Private block descent: a single rule for DP-CD and DP-SGD","Importance sampling speeds up private block coordinate descent","Unified private CD: generalizes DP-CD and DP-SGD","DP block CD: covers CD and SGD via sketch matrices","One private block descent to cover CD and SGD"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000926,"raw_usage":{"total_tokens":4013,"prompt_tokens":1032,"completion_tokens":2981,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":648,"completion_tokens_details":{"reasoning_tokens":2899}},"tokens_in":648,"tokens_out":2981,"duration_ms":19559,"temperature":1.0,"reasoning_tokens":2899,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-11T05:50:49.069866+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"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.","supporting_citations":[{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Defines DP-CD, the single-coordinate baseline this method generalizes, and provides the RDP-to-DP conversion lemma used in the privacy proof."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Supplies the SkGD sketched-gradient framework and smoothness-matrix viewpoint that DP-SkGD adapts to the private setting."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Establishes DP-SGD and its utility guarantees; DP-SkGD reduces to this method when the sketch always selects the full set."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Supplies the Gaussian mechanism and sensitivity-calibration background used to convert component Lipschitzness into noise scales."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Gives the DP-SVRG baseline compared in Table 1."}],"review_version":1}