acceptodds
Withdrawn from ICLR 2027

Growth Geometry Reduces Gradient Complexity in Differentially Private Empirical Risk Minimization Optimization

Withdrawn from ICLR 2027, so left out of the paper lists and the map.

Abstract

As a core problem in differentially private (DP) machine learning, DP empirical risk minimization (DP-ERM) has been intensively studied in the last decade. However, from the efficiency perspective, most existing work focuses on the running time or gradient complexity required to achieve optimal statistical utility, which does not fully characterize the gradient complexity for a general target optimization accuracy. Recently, Menart and Nikolov (2026) introduced the private-proxy oracle model to study this question for general nonsmooth Lipschitz convex objectives. It remains unclear how additional geometry of the objective changes the oracle complexity. In this work, we study convex finite-sum objectives with globally -Lipschitz convex components whose average satisfies the growth condition, also called the Tsybakov noise condition, with . Let denote the dimension, bound the distance from feasible points to the minimizer set, the conditional per-reply zero-concentrated differential privacy (zCDP) parameter of the proxy, the maximum batch size, and the target expected excess empirical risk. In the growth-active regime , and under additional accuracy and dimension conditions, we prove a lower bound with a non-private optimization term and privacy-dependent terms and We then give a restarted private-proxy method using component first-order evaluations. Under the same conditions, these bounds match up to constant factors when . Thus, growth improves the optimization dependence from to . In particular, quadratic growth gives an dependence.

Primary area:
alignment, fairness, safety, privacy, and societal considerations
Keywords:
DP-ERM, gradient complexity

Reviews

Among:
Shape:
1234this paper, Bottom 10%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 1.67 over 3 reviews, above 10% of the others.
Reviewer_W5hhOpenReview ↗
Rating
2
Confidence
3
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

The paper studies the gradient complexity of DP-ERM under (θ,λ)(\theta, \lambda) 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 ρ\rho-zCDP. The authors provide both lower bound and upper bound for the complexity which is tight when ρ=Ω(d)\rho = \Omega(d). The authors also show that the growth condition improve the accuracy dependence of the optimization term from α−2\alpha^{-2} to α−2(θ−1)/θ\alpha^{-2(\theta-1)/\theta}.

Critical strengths
  1. 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.
  2. The paper establishes matching upper and lower bounds in the regime (18), which is an interesting result for this model.
  3. The paper is well-written with self-contained proofs and clear statement on the limitation of their results.
Critical weaknesses
  1. 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 lα=log⁡(2+Kθ,λ)l_\alpha = \log(2+\sqrt{K_{\theta, \lambda}}). Compared with general convex case, the difference is only on the log scale.
  2. 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.
  3. The upper bound and lower bounds match only with in a very weak privacy regime. In Algorithm 1, the bounds are tight when ρ=Ω(d)\rho = \Omega(d), 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 dd versus Kθ,λK_{\theta,\lambda}, ρ\rho and mˉ\bar m, and show the gaps explicitly.
  4. 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 α\alpha". This is not true since existing excess-risk bounds can be converted into gradient complexities for any α\alpha by solving for the sample size.

Questions for authors
  1. Can the authors explain the relationship between query-level and record-level privacy? Suppose both settings run DP-SGD, how is per-reply ρ\rho related to the record-level privacy parameter of the whole training? Can one be converted to the other?
  2. 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.
Reviewer_zDbjOpenReview ↗
Rating
1
Confidence
3
Informativeness
2
Presentation
1
Soundness
3
Read review
Paper summary

The paper studies the gradient complexity of differentially private optimization under the private-proxy oracle model introduced by Menart and Nikolov (COLT 2026). It considers a narrower class of nonsmooth, convex, Lipschitz objectives satisfying an additional growth condition, which includes strongly convex objectives as a special case. The authors establish upper and lower bounds on the number of component-gradient evaluations required to achieve a target expected optimization error. The upper bounds are achieved by a restarted noisy stochastic subgradient method that exploits the growth condition to progressively localize the iterates. The lower bounds use information-theoretic arguments and hard optimization instances adapted to the growth setting. The upper and lower bounds match in certain parameter regimes, but not generally.

Critical strengths

The problem is interesting, and understanding how favorable objective geometry affects the computational cost of privacy-preserving optimization is a reasonable research direction. The authors establish nontrivial upper and lower bounds, including privacy-dependent lower bounds. The lower-bound constructions, especially the refined results in Appendix B.4, appear to be the more interesting technical contribution.

Critical weaknesses

Critical Weaknesses

  1. Limited novelty of the algorithmic upper bound and unclear significance of the lower bounds.

The upper-bound algorithm combines standard ingredients from stochastic convex optimization under growth conditions, including localization and restarted subgradient descent, with Gaussian noisy-gradient estimation. The improved dependence on target accuracy under the growth condition is already well known in nonprivate optimization, and related localization techniques have been extensively studied in private optimization (e.g., Asi et al., 2021). The resulting upper bound seems like a relatively straightforward combination of existing techniques.

The lower bounds appear more interesting, but their technical novelty relative to Menart and Nikolov (2026) is not sufficiently explained. In particular, it is difficult to identify the genuinely new proof ideas, which difficulties arise specifically from imposing the growth condition, and how these are overcome.

Moreover, the upper and lower bounds do not generally match, and the paper does not adequately contextualize this gap. The simplest matching regime is one in which the per-reply privacy parameter is sufficiently large that privacy imposes no additional asymptotic gradient complexity. This seems substantially less interesting than obtaining matching bounds in privacy-dominated regimes.

  1. Restrictive oracle model

The private-proxy oracle model is quite restrictive relative to general DP optimization. In particular, it limits the optimizer's access to private first-order information through a prescribed private oracle, rather than encompassing general DP optimization algorithms such as output perturbation, objective perturbation, or exponential-mechanism-based methods. Furthermore, as explicitly acknowledged in Remark 3.10, privacy is guaranteed separately for individual proxy replies, without requiring the final optimizer to satisfy dataset-level DP. This considerably limits the implications of the results for the computational complexity of DP-ERM more generally.

  1. Poor presentation.

The paper is unnecessarily difficult to read. The abstract is extremely notation-heavy and does little to communicate the intuition or significance of the main results. The introduction presents complicated bounds without adequately explaining their terms, the important parameter regimes, or the gap between upper and lower bounds. The theorem statements contain substantial technical detail, but there is relatively little high-level discussion of the ideas behind the results.

For example, it would be much more informative to explain the implications for quadratic growth/strong convexity in a few representative privacy and dimension regimes. Similarly, the distinction between regimes in which privacy incurs an additional computational cost and those where the complexity matches the nonprivate rate should be emphasized.

Overall, the presentation makes it difficult to assess the significance and technical novelty of the contributions.

In light of these weaknesses (particulary 3), I recommend rejection. Although the problem is potentially interesting, I find the contribution insufficiently compelling in its current form. The upper-bound algorithm largely combines standard techniques, the lower bounds do not generally match in the most interesting privacy regimes, and the restrictive private-proxy oracle model limits the broader significance of the results.

More importantly, the paper does a poor job communicating its contributions. The results are presented through complicated theorem statements and notation-heavy bounds without sufficient interpretation, intuition, or comparison to prior work. In particular, the main technical challenges and novel ideas underlying the lower bounds are not clearly articulated. Even after reading the paper, I found it difficult to understand precisely what the principal advances are over Menart and Nikolov (2026), or why the results should be considered significant. I believe that clearly explaining the novelty, significance, and limitations of the results is essential. I do not think the paper meets that standard in its present form.

Questions for authors

What are the main new technical ingredients in the lower-bound proofs relative to Menart and Nikolov (2026)? Which obstacles arise specifically from the growth assumption, and how are they overcome?

How substantial is the gap between the upper and lower bounds in privacy-dominated regimes? Can the authors provide simplified bounds for quadratic growth in representative parameter regimes and identify where the results establish a genuine characterization of privacy-induced computational overhead?

Appendix B.5 claims a counterexample to a published lower-bound theorem of Menart and Nikolov (2026). This appears potentially important, but is barely discussed in the main text. Can the authors elaborate on the significance of this counterexample and its relationship to the new lower-bound techniques developed here?

Reviewer_RbgBOpenReview ↗
Rating
2
Confidence
2
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

This paper studies the gradient complexity of differentially private empirical risk minimization (DP-ERM) under the private-proxy oracle model when the objective satisfies the (θ,λ)(\theta,\lambda) growth condition. It establishes lower bounds on the component first-order evaluations required to achieve a target optimization accuracy and proposes a restarted private-proxy subgradient method with improved complexity guarantees. The theoretical analysis shows that the growth condition improves the dependence on the target accuracy from α−2\alpha^{-2} to α−2(θ−1)/θ\alpha^{-2(\theta-1)/\theta}, with matching upper and lower bounds under additional conditions. Experiments on synthetic objectives and regularized hinge-loss ERM provide empirical support for the proposed complexity analysis.

Critical strengths
  • The paper provides a theoretically grounded analysis of how growth geometry affects gradient complexity in the private-proxy model.
  • The proposed restarted private-proxy subgradient method provides a constructive approach to achieving the improved complexity bound.
  • The paper also includes experiments with different growth exponents, privacy parameters, and batch sizes, as well as evaluations on two real-world datasets, to illustrate the theoretical findings.
Critical weaknesses
  • The practical relevance of the theoretical results to standard DP-ERM requires further clarification. As stated in Remark 3.10, the private-proxy model only guarantees conditional per-reply privacy rather than dataset-level differential privacy for the complete optimization procedure.
  • The experimental evaluation does not sufficiently validate the central contribution of repeated restarting. most experiments reach the target accuracy before the first restart, meaning that the reported improvements mainly reflect differences in optimization schedules rather than the benefit of progressively reducing the effective optimization radius.
  • The matching upper and lower bounds are established only under relatively restrictive conditions on dimension, accuracy, and privacy parameters. In particular, the main lower bound requires a sufficiently large dimension relative to the optimization scale
Questions for authors

See weaknesses.

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Discussion (0)

Sign in to comment.