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

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 $L$-Lipschitz convex components whose average satisfies the $(\theta ,\lambda )$ growth condition, also called the Tsybakov noise condition, with $\theta \ge 2$. Let $d$ denote the dimension, $R$ bound the distance from feasible points to the minimizer set, $\rho >0$ the conditional per-reply zero-concentrated differential privacy (zCDP) parameter of the proxy, $\bar{m}$ the maximum batch size, and $\alpha >0$ the target expected excess empirical risk. In the growth-active regime $\alpha \le \lambda R^{\theta }$, and under additional accuracy and dimension conditions, we prove a lower bound with a non-private optimization term $\Omega \left(L^2{\lambda }^{-2/\theta }{\alpha }^{-2(\theta -1)/\theta }\right)$ and privacy-dependent terms $\Omega \left(\sqrt{\frac{d\log \left(2+L{\lambda }^{-1/\theta }{\alpha }^{-(\theta -1)/\theta }\right)}{\rho }}\right)$ and $\Omega \left(\frac{d\log \left(2+L{\lambda }^{-1/\theta }{\alpha }^{-(\theta -1)/\theta }\right)}{\bar{m}\rho }\right).$ We then give a restarted private-proxy method using $O\left(L^2{\lambda }^{-2/\theta }{\alpha }^{-2(\theta -1)/\theta }\max \left(1,\sqrt{\frac{d}{\rho }},\frac{d}{\bar{m}\rho }\right)\right)$ component first-order evaluations. Under the same conditions, these bounds match up to constant factors when $\rho \gtrsim d$. Thus, growth improves the optimization dependence from ${\alpha }^{-2}$ to ${\alpha }^{-2(\theta -1)/\theta }$. In particular, quadratic growth $(\theta =2)$ gives an ${\alpha }^{-1}$ dependence.