- Rating
- 2
- Confidence
- 3
- Informativeness
- 2
- Presentation
- 2
- Soundness
- 2
Read review
Paper summary
The paper studies the gradient complexity of DP-ERM under growth condition with the private-proxy oracle model from Menart & Nikolov (2026). In this model, the optimizer accesses first-order information through proxy replies, each of which is -zCDP. The authors provide both lower bound and upper bound for the complexity which is tight when . The authors also show that the growth condition improve the accuracy dependence of the optimization term from to .
Critical strengths
- The question of how growth condition changes gradient complexity in the private-proxy model is natural, and that the restarted method shows that it can provide non-trivial improvement on the accuracy dependence.
- The paper establishes matching upper and lower bounds in the regime (18), which is an interesting result for this model.
- The paper is well-written with self-contained proofs and clear statement on the limitation of their results.
Critical weaknesses
- The lower bound in Theorem 4.1 only improve little from the general convex case, thus it is hard to find out how the grow condition affects the hardness of DP-ERM. In particular, Theorem 4.1 is built upon the results in Theorem B4 on the general convex case. The growth condition is reflected via . Compared with general convex case, the difference is only on the log scale.
- The non-private term of the lower bound follows direct from the String Guessing construction of Braun et al. (2017), thus does not add much to the novelty of the paper.
- The upper bound and lower bounds match only with in a very weak privacy regime. In Algorithm 1, the bounds are tight when , which is uncommon in practice. This seriously limits the significance of the tightness result. I suggest that the authors compare the upper and lower bounds across all regimes in the main text, for example in a table organized by versus , and , and show the gaps explicitly.
- Algorithm 1 combines the restart scheme standard for objectives with growth condition with a Gaussian minibatch estimator which is also common in DP literature. The algorithmic contribution is also limited, especially consider the lower/upper bounds gap stated in Weakness 3.
Minor:
In line 55, the author claims that existing results "do not determine the gradient complexity for a general target ". This is not true since existing excess-risk bounds can be converted into gradient complexities for any by solving for the sample size.
Questions for authors
- Can the authors explain the relationship between query-level and record-level privacy? Suppose both settings run DP-SGD, how is per-reply related to the record-level privacy parameter of the whole training? Can one be converted to the other?
- How are the lower bounds results in this paper related to the ones in Menart & Nikolov (2026)? It would be helpful if the authors can state their bounds explicitly and make a detailed comparison with them both in constructions and final rates.