Training a model privately on a data stream means adding noise to every update, and the amount of noise depends on one hyperparameter: the clipping threshold, the cap placed on each example's gradient before noise is added. Set the cap too low and the learner throws away signal. Set it too high and the noise drowns the signal. Offline, practitioners find the cap by search. In a single-pass stream they cannot, because the data cannot be revisited and the right cap changes whenever the scale of the data drifts. This note asks a precise question. How much extra error must any differentially private streaming learner pay for not knowing the gradient scale in advance? Differential privacy (DP) here means the guarantee that changing one example barely changes the distribution of everything the algorithm releases.
Our conjecture is that this cost is additive and charged per drift event, not multiplicative and charged over the whole stream. If the gradient scale changes $S$ times over a stream of length $T$, a learner that spends privacy budget on its hyperparameter only when the scale actually shifts should pay roughly $S/\epsilon$ extra regret on top of what a learner told the true scale would pay. No private learner should be able to do better than that. We will prove matching upper and lower bounds where possible, build the algorithm, and test it against the obvious simpler alternatives. The most important of these is running a grid of learners with different caps in parallel and privately picking the winner.
Core Claim
Consider private online convex optimization: the learner picks $w_t$ from a set of diameter $D$, then sees a convex loss whose per-example gradients have norm about $G_t$. A learner that knows $G_t$ and uses a tree-based noisy-sum mechanism of the kind generalized in Differentially Private Histograms under Continual Observation gets regret of order
$$R^\star(T) \approx G D\left(\sqrt{T} + \frac{\sqrt{d}\,\mathrm{polylog}(T)}{\epsilon}\right),$$
where $d$ is the dimension and $\epsilon$ the privacy parameter. If the cap $C$ is off from $G$ by a factor $\kappa$, one term grows by roughly $\kappa$. A cap that is too high multiplies the noise term. A cap that is too low adds bias that, under linear losses, can cost a constant fraction of $GD$ per round. We conjecture that when $G_t$ is piecewise constant with $S$ changes inside a known range $[G_{\min}, G_{\max}]$, the following bound holds, with $L = \log_2(G_{\max}/G_{\min})$ the number of scale levels:
$$R^\star(T) + \Omega\!\left(\frac{S\, G_{\max} D}{\epsilon}\right) \;\le\; R(T) \;\le\; R^\star(T) + O\!\left(\frac{S\, G_{\max} D \log T \log L}{\epsilon}\right).$$
The lower bound comes from group privacy. Two streams that differ only in the scale of the roughly $1/\epsilon$ rounds after a change point are nearly indistinguishable to any $\epsilon$-DP learner. On those rounds the learner must therefore either under-clip in one world or over-clip in the other. The upper bound comes from a tracker that pays a sparse-vector cost only when it detects a change.
Two contrasts make this new. Asi et al.'s lower bound in Private Online Learning via Lazy Algorithms counts switches of the model and assumes a pre-tuned step size and batch size. We count switches of a hyperparameter and make it unknown. Online Sensitivity Optimization in Differentially Private Learning already adapts the cap in one pass, but it updates the cap every batch, has no lower bound, and is evaluated only on static datasets read as streams. Under drift it has no mechanism that ties privacy spending to the number of real changes.
Research Program
The algorithm has two parts. The first is a learner in the follow-the-regularized-leader style, which plays the minimizer of past gradients plus a regularizer. It privatizes the running gradient sum with a base-$r$ tree mechanism, since Cardoso et al. report that bases $r \in [3,10]$ cut noise standard deviation by 15% relative to binary trees. Its cap is restricted to a geometric ladder $C \in \{G_{\min} 2^j\}$.
The second part is a tracker that watches one scalar, the fraction of recent gradients that hit the cap. It does this through AboveThreshold, the sparse-vector test that spends budget only when a noisy statistic crosses a noisy threshold. When the clipped fraction rises too high or falls too low, the tracker moves one rung on the ladder. At that point the tree for the old cap is collapsed into a single noisy prefix sum and a fresh tree is started.
This monitor-and-update pattern is borrowed from two places. One is the relative-error continual release work in Differentially Private Continual Release with Relative Error, which supplies the method. The other is SparseGumb in Cardoso et al., which also supplies the method. Memory stays at $O(d\log T)$ plus one prefix sum per epoch. With a counter, it never stores raw examples.
The theory has three parts. First, prove the upper bound above for piecewise-stochastic streams with $S$ scale changes. Second, prove the group-privacy lower bound for that same class. Third, confront the adaptivity problem directly. The lower bound in Differentially Private Continual Release with Relative Error shows that for adaptive adversarial streams, monitor-and-update selection cannot beat roughly $T^{1/3}/\epsilon^{2/3}$ error. A learner's gradient norms depend on its own past outputs, so the statistic our tracker watches is generated adaptively. This paper constrains the design. Our claim must therefore be stated for streams where the scale is set by the data distribution in each segment, not by an adversary reacting to the learner. We will also try to show that an adversary who controls the scale forces the $T^{1/3}$ regime even for a single scalar statistic. If that holds, it separates "drift" from "adversarial scale" cleanly, and we consider it a result in its own right.
Step size is handled the same way only to the extent the theory allows. In this learner the regularizer strength scales with $C$, so tracking the scale fixes the step size as well. We do not attempt adaptive optimizers. The file documents that both linear scaling (Koskela & Kulkarni) and unitary-sensitivity clipping updates (Galli et al.) break for DP-Adam.
Baselines
The naive reference point is a fixed cap $C=1$ with step size $\eta_0/\sqrt{t}$, the default a practitioner would use without tuning. Galli et al. report that fixed caps chosen this way stall at $\epsilon=1$ on Fashion-MNIST. Above this sits an oracle that is told the true scale in each segment. It defines $R^\star$ and bounds what any method can achieve. Beating the naive baseline is required. Coming within a small additive gap of the oracle, a gap that grows with $S$ but not with $T$, is the target.
The strongest existing tuning-free competitor is OSO-DPSGD (Galli et al.). It updates the cap every batch with an exponential rule driven by cosine alignment and clipping frequency. The file records only qualitative results for it: "competitive with optimally tuned fixed thresholds" on MNIST and with grid search on AG News. No reported result was found on Lacuna for OSO-DPSGD as a numeric accuracy, so we will rerun it. It gets the same stream, the same total $\epsilon$ and $\delta$, and its initial cap drawn from the same ladder. Its own learning-rate initialization gets a grid budget equal to ours.
The strongest selection-based competitor is a ladder of $L$ parallel learners, one per cap, with a private choice of which one to follow. We adapt the ex-post selection of Private Hyperparameter Tuning with Ex-Post Guarantee to periodic continual selection. On Twitter Usage linear regression, that paper reports an average privacy budget of $\epsilon=0.28$ to reach target utility, against 0.55 for doubling and 0.77 for Brownian baselines. That 0.28 is the number to beat. We will rerun Twitter Usage as a stream and report the $\epsilon$ each method needs to reach the same target loss. Beating 0.28 under single-pass constraints, or matching it while using a $1/L$ fraction of the memory, counts as a win.
We also compare against per-example normalization as in HyFreeDP (Liu & Bu), which removes the cap entirely. We include its private curvature step-size probe at the reported $<1\%$ budget share.
The key ablation replaces the sparse-vector tracker with a tracker that privately releases the clipped fraction at every step through its own tree mechanism. This isolates the claim that spending budget only on detected switches is what makes the tuning tax scale with $S$ rather than with $T$.
Why not just…?
Why not just pre-tune the cap on public or proxy data? This works when the stream never drifts and the proxy matches it. Neither assumption survives contact with the evidence in the file. Koskela & Kulkarni find that hyperparameters tuned on subsamples need explicit scaling to transfer, and that the scaling rule itself fails for DP-Adam. Our drift-injected streams test this directly by tuning on the first segment and freezing. We expect the frozen learner's regret to grow linearly after the first scale change.
Why not just normalize every gradient and forget the cap? This is a real threat. HyFreeDP reports it working well in deep networks, at about 10% compute overhead on Llama2-7B. The weakness is that normalization discards per-example magnitude, which biases the update whenever norms are heterogeneous within a segment. Heterogeneous norms are common in linear and logistic regression on raw features. We will test this on KDD Cup '99 logistic regression and covtype with heavy-tailed feature norms. If normalization matches our tracker there, we will narrow the claim to the regimes where it does not, and report that.
Why not just run a grid of learners and select privately? Because the ladder has only $L$ rungs, the memory cost is a factor of $L$, which is modest rather than fatal. So the real question is privacy. Splitting budget across $L$ learners inflates each learner's noise term by roughly $\sqrt{L}$ under Gaussian composition. Continual re-selection pays again at every selection round unless it is itself made sparse. The Twitter Usage comparison against the 0.28 figure settles whether this matters in practice. If the grid wins, the honest conclusion is that the tax is multiplicative but small, and our lower bound becomes the main contribution.
Why not just use OSO-DPSGD, which already adapts the cap online? It spends on the cap every batch whether or not anything changed, and its dependence on initialization is documented. The every-step ablation and a sweep over initial caps will show whether its regret gap to the oracle grows with $T$ on drifting streams, as we predict, or stays flat.
Proposed Experiments
The streams are Twitter Usage (linear regression, as in Ghazi et al.), KDD Cup '99 (logistic regression, as in Fay et al.), and covtype and kddcup99 read once in order (as in ABACOC), plus MNIST and Fashion-MNIST for comparability with OSO-DPSGD. On each stream we inject $S \in \{0,1,4,16\}$ scale changes by rescaling features piecewise by factors up to $2^5$. We also build synthetic linear-loss streams that instantiate the lower-bound construction.
We report three things. The first is cumulative regret against the per-segment oracle, or prequential accuracy for the classification streams. The second is the $\epsilon$ needed to reach a target loss. The third is peak memory.
Three checks decide the claim. First, the gap between our learner and the oracle should grow roughly linearly in $S/\epsilon$ and stay flat in $T$ at fixed $S$. The every-step ablation's gap should instead grow with $T$. Second, on the lower-bound streams, every method's excess regret should sit above the predicted $S/\epsilon$ floor. Third, on a stream where an adversary sets the scale in response to the learner's past outputs, our tracker's advantage should collapse toward the $T^{1/3}$ behavior. Seeing that collapse would confirm that the adaptive-release lower bound marks the true boundary of the claim. Not seeing it would mean the lower bound does not transfer to a single scalar statistic, which would also be worth knowing.
References
- Differentially Private Histograms under Continual Observation: Streaming Selection into the Unknown
- Private Online Learning via Lazy Algorithms
- Online Sensitivity Optimization in Differentially Private Learning
- Differentially Private Continual Release with Relative Error
- Practical Differentially Private Hyperparameter Tuning with Subsampling
- Private Hyperparameter Tuning with Ex-Post Guarantee
- Towards hyperparameter-free optimization with differential privacy
- The ABACOC Algorithm: A Novel Approach for Nonparametric Classification of Data Streams