Many fairness and robustness objectives are min-max games. A model minimizes a loss while an adversary reweights the data to maximize it. When such a model must be trained under differential privacy (a guarantee that the output barely changes if any one person's record is removed), theory now offers an algorithm with provably optimal error. That algorithm is recursive regularization, due to Bassily, Guzmán and Menart. It splits the data into disjoint chunks, and in each chunk it solves a version of the game that adds a quadratic penalty pulling the solution toward the previous chunk's answer. The penalty makes each subproblem well-conditioned. Because the chunks are disjoint, no record is used twice, so the privacy cost does not compound. The resulting guarantee is on the strong gap: how far the specific returned model and adversary are from an equilibrium. The paper proves an optimal rate of $\tilde{O}(1/\sqrt{n} + \sqrt{d}/(n\epsilon))$, where $n$ is the sample size, $d$ the dimension and $\epsilon$ the privacy budget. It contains no experiments at all.
This proposal runs the first finite-sample test of that algorithm and pulls apart its two ingredients, the moving proximal anchor and the disjoint data partitioning. Our hypothesis is that at realistic sizes ($n$ from $10^3$ to $10^6$), partitioning is the expensive part. Each round sees only a fraction of the data. The anchor is the useful part, and it costs no privacy, because its gradient does not touch the data. If this holds, a variant that keeps the anchors but reuses all data in every round should beat the theoretical algorithm below a crossover sample size $n^\ast$ that we will measure. Above $n^\ast$, the theoretical algorithm should take over. Locating $n^\ast$, and measuring how far the theory's prescribed constants sit from tuned ones, is the concrete contribution. It answers in one well-instrumented case the general complaint that private-learning theory proves error bounds whose constants are never checked (Cohen-Addad et al.).
Core Claim
Recursive regularization solves, in round $k$ on data chunk $S_k$, the penalized game
$$\min_{u}\max_{v}\; f_{S_k}(u,v) + \frac{\rho_k}{2}\|u-u_{k-1}\|^2 - \frac{\rho_k}{2}\|v-v_{k-1}\|^2 .$$
Here $u$ is the model, $v$ the adversary, $f_{S_k}$ the empirical game on chunk $S_k$, and $\rho_k$ a penalty weight that changes across rounds. The anchors $(u_{k-1}, v_{k-1})$ are the previous round's output. The penalty terms depend only on the anchors and the current iterate, never on any record. Adding them is therefore free in privacy terms.
Partitioning, by contrast, buys clean privacy accounting at the price of $n/K$ samples per round, where $K$ is the number of rounds. The alternative is to reuse the full dataset in every round and pay for $K$-fold composition (the rule that privacy losses add up across repeated data access). For a fixed total budget, that inflates the noise in each round by roughly $\sqrt{K}$ under Rényi-style accounting.
So two variants compete. The partitioned one loses statistical signal per round. The reuse variant loses signal to extra noise. Which one wins depends on constants the theory suppresses. Our claim is that this tradeoff has a measurable crossover, that the anchor helps on both sides of it, and that the paper's asymptotic statement is silent on which side typical private-learning datasets fall.
Why This Instance, and What Prior Work Does
Several private algorithms built on proximal ideas share the same empirical silence. These include recursive regularization; regularized private bilevel optimization by Lowy and Liu; and the momentum method of Tran and Cutkosky, which exploits the fact that consecutive iterates stay close in order to reduce sensitivity. These papers motivate the study; none supplies a validation.
We pick the saddle-point case for two reasons. The bilevel method relies on high-dimensional grid-walk sampling, and the momentum method's reconstruction costs $O(N^{11/3}/d^{2/3})$. Both are impractical to run faithfully. Recursive regularization, in contrast, is nearly linear-time for smooth games and calls ordinary gradient descent-ascent as a black box. We can therefore implement it exactly as written.
The second reason is that its target quantity, the strong gap, can be computed exactly on convex-concave problems. That makes it possible to compare theory and practice on the very metric the theorem bounds, not on a proxy.
One paper shows that this kind of validation is feasible and informative. Mangold et al. paired private proximal coordinate descent with experiments on Electricity and California Housing. They found an order-of-magnitude lower error than private gradient descent, along with a stated failure mode on correlated features. We adopt their standard of testing on real tabular data, but on a min-max problem with a moving anchor rather than a separable penalty.
Zhang et al. supply the closest empirical evidence that a moving proximal anchor stabilizes noisy stochastic training: 74% versus about 80% on CIFAR-100 at batch size 8. Their setting is non-private and single-player, so it suggests the anchor's value without establishing it under privacy noise.
Research Program
The testbed is private group distributionally robust classification. The model $u$ is a logistic regression vector. The adversary $v$ is a distribution over $G$ groups, with a quadratic penalty on $v$ that makes the game strongly concave in $v$. With this setup, the adversary's best response has a closed form, and the model's best response is a convex logistic fit. The strong gap of any output pair can then be computed to high precision on held-out data.
The adversary's gradient is a vector of group losses. Its sensitivity is bounded once per-example losses are clipped. Both players are privatized with the Gaussian mechanism.
We will implement four algorithms on identical code paths:
- Recursive regularization as written. Disjoint partitions, the theoretical $\rho_k$ schedule, and private stochastic gradient descent-ascent as the inner solver.
- The reuse variant. The same anchors and schedule, but full data in every round, with privacy accounted by Rényi composition.
- A partition-without-anchor variant. Rounds restart from the previous output with no penalty.
- Plain private gradient descent-ascent. Returns either the last or the averaged iterate. These are the outputs that prior weak-gap analyses cover.
Every method is run twice. The first run uses the constants the theory prescribes. The second uses constants tuned under a fixed budget of configurations. The ratio between the two runs' strong gaps is our direct measurement of the "hidden constant" cost.
Tuning itself leaks privacy, a problem the file notes is ignored in large-scale empirical work such as TAN Without a Burn. We handle it in two ways and report both:
- Proxy tuning. Hyperparameters are tuned on a disjoint, treated-as-public split.
- Accounted tuning. Tuning runs on private data, and its cost is charged to the reported $\epsilon$.
We will sweep $n$ by subsampling each dataset geometrically, sweep $\epsilon \in \{0.5, 1, 2, 4, 8\}$, and sweep $K$. The aim is to trace each method's strong gap as a function of $n$ and to read off $n^\ast$ where the partitioned and reuse curves cross. Theory predicts that the partitioned method's curve eventually has the better slope; the experiment measures where.
As a secondary probe of the convexity assumption the theorem relies on, we will repeat the comparison with a two-layer network in place of logistic regression. There, the strong gap is no longer computable, so we report worst-group test accuracy instead.
Data
All datasets come from the file. Electricity and California Housing (as used by Mangold et al.) define groups by quantile bins of a salient feature. The California Housing target is binarized at its median. real-sim and rcv1 from Catalyst supply sizes up to $7.8\times10^5$, which lets us reach the regime where theory should win.
ckn-cifar from Kulunchakov and Mairal is CIFAR-10 represented by fixed convolutional-kernel features, with $n=50{,}000$ and $p=9{,}216$. It gives a high-dimensional convex instance with classes as groups. The dimension matters because the $\sqrt{d}/(n\epsilon)$ privacy term dominates there.
Baselines
Reference points. The floor is the trivial output: the anchor at initialization paired with a uniform adversary. The ceiling is the non-private equilibrium, computed by deterministic gradient descent-ascent to tolerance. Every private method's strong gap is reported as the fraction of this floor-to-ceiling range it closes.
Plain private gradient descent-ascent. This is the strongest existing competitor. It is what a practitioner would actually run, its averaged iterate is what earlier weak-gap analyses cover, and it uses every sample once per pass with no partitioning loss. We give it the same privacy budget, the same total number of per-example gradient evaluations, the same clipping search and the same configuration budget. We report its best of last iterate and averaged iterate.
No reported result was found on Lacuna for the strong gap of any private saddle-point method on any benchmark, so there is no published number to quote. The point of this baseline is to establish that number. Recursive regularization "beats" it if its tuned strong gap is lower at matched $\epsilon$ across at least three seeds with non-overlapping intervals.
Fixed-anchor regularization. This is weight decay toward the origin, plus the matching penalty on $v$, applied with the same strength schedule. It isolates whether the benefit comes from strong convexity alone or from the anchor moving.
Partition-without-anchor variant. This ablation isolates the anchor's contribution while holding the data split fixed.
Reuse variant. This ablation isolates the partitioning ingredient. It is the proposal's key comparison, not a strawman.
Why not just…?
Why not just run private gradient descent-ascent and average the iterates? This is the real threat. On smooth, well-conditioned convex-concave problems, averaged iterates may already have a small strong gap at moderate $n$, which would make the recursion pure overhead. The theory's argument against it concerns worst-case games where the weak and strong gaps diverge, and we do not know whether tabular group robustness is such a case. The $n$-sweep settles this directly. If the averaged baseline matches or beats every recursive variant at all $n$ and $\epsilon$ tested, that is the finding. We would then report that the optimality result has no practical regime on these problems.
Why not just add weight decay? Weight decay gives strong convexity and costs no inner loop. But its fixed center at the origin biases the solution for good, whereas the moving anchor's bias disappears as the anchor tracks the iterate, as Zhang et al. argue in the non-private case. Whether that bias matters at private noise levels is unknown. The fixed-anchor baseline measures it, with its strength tuned under the same budget.
Why not just tune hyperparameters harder instead of following the theory? That is partly what we propose. The theory-versus-tuned comparison quantifies how much tuning matters. The catch is that tuning on private data consumes privacy. A method that needs fifty configurations to work may lose to one that works at its prescribed constants once tuning is charged. Reporting both proxy tuning and accounted tuning shows which methods are robust to this.
Why not just use partitioning, since the theorem says it is optimal? Optimality is asymptotic. At $n/K$ samples per round, small datasets like gene-scale problems can leave each round with too few points to estimate group losses. The reuse variant and the crossover $n^\ast$ test exactly this.
Decisive Checks
The study succeeds if it delivers three things on Electricity, California Housing, real-sim, rcv1 and ckn-cifar:
- Strong-gap curves over $n$ and $\epsilon$ for all methods.
- A measured crossover $n^\ast$, or a demonstration that none exists in the tested range.
- The theory-to-tuned constant ratio for each method.
Three outcomes would be decisive.
The anchor-only hypothesis is confirmed if the reuse variant beats the written algorithm below some $n^\ast$ and loses above it, while both beat the partition-without-anchor ablation.
The hypothesis fails if partitioning wins at every $n$. In that case, the theory's constants are better than feared, which is a positive validation worth publishing.
The recursion is unnecessary in practice if averaged private gradient descent-ascent dominates everywhere.
The non-convex probe then indicates whether whichever conclusion holds extends beyond the setting the theorem covers.
References
- Differentially Private Algorithms for the Stochastic Saddle Point Problem with Optimal Rates for the Strong Gap
- Perturb-and-Project: Differentially Private Similarities and Marginals
- Differentially Private Bilevel Optimization: Efficient Algorithms with Near-Optimal Rates
- Momentum Aggregation for Private Non-convex ERM
- Differentially Private Coordinate Descent for Composite Empirical Risk Minimization
- Taming the Noisy Gradient: Train Deep Neural Networks with Small Batch Sizes
- TAN Without a Burn: Scaling Laws of DP-SGD
- A Universal Catalyst for First-Order Optimization
- A Generic Acceleration Framework for Stochastic Composite Optimization