Under a fixed privacy budget, the utility of differentially private (DP) training is ultimately determined by its optimization efficiency. Standard first-order DP optimizers like DP-SGD rely solely on local gradients and ignore the underlying loss curvature. This geometric blindness causes severe zigzagging in ill-conditioned landscapes, wasting precious privacy budgets on inefficient iterations.
Practitioners are thus trapped in a bind: either stop training prematurely or inject massive per-step noise, both of which critically compromise final model utility. Natural Gradient Descent (NGD) resolves this by preconditioning gradients with curvature, aligning updates with the loss geometry and extracting more efficient signals from every noisy step, offering a principled pathway to break the privacy-utility bottleneck.
However, directly integrating NGD with DP introduces fundamental challenges: curvature estimation consumes prohibitive privacy budgets, isotropic DP operations conflict with the anisotropic scaling of NGD, and inverse curvature catastrophically amplifies parameter updates in flat directions, causing training instability.
We propose DP-NGD, a practical framework that systematically addresses these obstacles by decoupling curvature estimation from private data, reconciling isotropic DP constraints with anisotropic second-order optimization via a whitened-space mechanism, and dynamically clamping curvature to stabilize training. Extensive experiments on standard benchmarks demonstrate that DP-NGD achieves state-of-the-art accuracy, breaking through the utility ceilings of first-order baselines while delivering up to a $10\times$ convergence speedup under the same privacy budget.