# Online Sensitivity Optimization in Differentially Private Learning

Filippo Galli, Catuscia Palamidessi, Tommaso Cucinotta

► To cite this version:

Filippo Galli, Catuscia Palamidessi, Tommaso Cucinotta. Online Sensitivity Optimization in Differentially Private Learning. AAAI 2024 - National Conference on Artificial Intelligence, Feb 2024, Vancouver, Canada. pp.12109-12117, 10.1609/aaai.v38i11.29099 . hal-04941814

HAL Id: hal-04941814

https://inria.hal.science/hal-04941814v1

Submitted on 26 Feb 2025

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_1.png" /></figure>
# Online Sensitivity Optimization in Differentially Private Learning

Filippo Galli,¹,⁴ Catuscia Palamidessi,²,³ Tommaso Cucinotta⁴

¹Scuola Normale Superiore

²INRIA, Palaiseau, France

³École Polytechnique, Palaiseau, France

⁴Scuola Superiore Sant'Anna, Pisa, Italy

filippo.galli@sns.it, catuscia@lix.polytechnique.fr, tommaso.cucinotta@santannapisa.it

## Abstract

Training differentially private machine learning models requires constraining an individual's contribution to the optimization process. This is achieved by clipping the 2-norm of their gradient at a predetermined threshold prior to averaging and batch sanitization. This selection adversely influences optimization in two opposing ways: it either exacerbates the bias due to excessive clipping at lower values, or augments sanitization noise at higher values. The choice significantly hinges on factors such as the dataset, model architecture, and even varies within the same optimization, demanding meticulous tuning usually accomplished through a grid search. In order to circumvent the privacy expenses incurred in hyper-parameter tuning, we present a novel approach to dynamically optimize the clipping threshold. We treat this threshold as an additional learnable parameter, establishing a clean relationship between the threshold and the cost function. This allows us to optimize the former with gradient descent, with minimal repercussions on the overall privacy analysis. Our method is thoroughly assessed against alternative fixed and adaptive strategies across diverse datasets, tasks, model dimensions, and privacy levels. Our results indicate that it performs comparably or better in the evaluated scenarios, given the same privacy requirements.

## Introduction

The widespread adoption of machine learning techniques has led to increased concerns about user privacy. Users who share their data with service providers are becoming more cautious due to the exposure of various privacy attacks, observed in both academic and industrial contexts (Carlini et al. 2021, 2023; Papernot et al. 2018). As a result, there is a growing effort to enhance training methods that can provide strong and quantifiable privacy guarantees.

In the privacy-preserving machine learning community, differential privacy (Dwork 2006) has emerged as the predominant framework for defining privacy requirements and strategies. Essentially, training a model with differential privacy requires bounding the contribution of a single individual to the overall procedure, to guarantee that the trained model will be probabilistically indistinguishable compared to the same model trained without including any one specific user in the dataset. In the context of gradient-based learning, this is achieved by introducing a parameter *C* called the *clipping threshold* (Abadi et al. 2016). This parameter controls

the magnitude of gradients from each user (or sample) before they are averaged with contributions from other users. Subsequently, the result undergoes a process of differential privacy sanitization, which involves the addition of random Gaussian noise proportional to the value of *C*.

The choice of the clipping threshold *C* is crucial: on the one hand, large values introduce noise levels that may slow down or hinder the optimization altogether; on the other hand, small values introduce a bias in the average clipped gradient with respect to the true average gradient and may leave the optimization stuck in bad local minima. Figure 1 exemplifies the issue. Note that the clipping bias is not only directed toward zero (as bounding the 2-norm may lead to believe), but depends, in general, on the distribution of the per-sample gradients around the expectation (Chen, Wu, and Hong 2020). Achieving an optimal trade-off remains an ongoing challenge. Historically, researchers have treated the clipping threshold as a parameter to be optimized, often through a grid or random search, in order to assess the performance of privacy preserving models in the ideal conditions in which an oracle provides the optimal values for the hyperparameters. However, it is worth noting that every additional gradient-query to the dataset for optimization purposes introduces a certain degree of privacy leakage. Of late though, the implications of not accounting for privacy leakage over multiple runs of a grid search have drawn more attention, leading to different accounting strategies (Papernot and Steinke 2022; Mohapatra et al. 2022; Liu and Talwar 2019). The inherent challenges of increased privacy leakage and computational overhead resulting from extensive hyper-parameter searches persist, necessitating further innovations to encourage broader adoption of differentially private machine learning techniques. Therefore, we set out to find a strategy for the online optimization of the clipping threshold that is privacy preserving and computationally inexpensive, while maintaining comparable or better performance on a set of tasks, datasets, and model architectures.

**Our contributions:** i) We investigate the sensitivity trade-off in differentially private learning in terms of cosine similarity between the sanitized and true gradients, showing that at every iteration it is possible to determine a fairly prominent optimal value, ii) we elaborate a strategy for the online optimization of the sensitivity, taking from the literature in online learning rate optimization and extending it to opti-
<figure><img src="image_2.png" /><figcaption>Figure 1: The choice of clipping threshold C requires trading off a higher clipping bias at small values, for larger Gaussian noise at large values. Here the clipped, averaged, noised gradient of a CNN for character recognition is compared with the true average gradient at different training iterations $t \in \{100, 250, 500, 750, 950\}$. Note that for some values the sanitized gradient may even have components pointing in the opposite direction w.r.t the true gradient, corresponding to negative cosine similarity. The reported figure of cosine similarity is an average over 20 realizations of the Gaussian mechanism.</figcaption></figure>

mize the clipping threshold, iii) we establish the corresponding techniques for doing so privately, which require allocating a marginal privacy budget and iii) we provide experimental results to validate our algorithm in multiple contexts and against a number of relevant state-of-the-art strategies for private hyperparameter optimization.

## Background

Gradient-based optimization of supervised machine learning models typically implies finding the optimal set of parameters $\theta \in \mathbb{R}^n$ to fit a function $f_\theta: \mathcal{X} \to \mathcal{Y}$ to a dataset $D \in \mathcal{D}$ of pairs $z_i = (x_i, y_i) \in \mathcal{X} \times \mathcal{Y}$, by minimizing an error function $\ell: \mathbb{R}^n \times \mathcal{D} \to \mathbb{R}_{\ge 0}$. At time $t$, the iterative optimization process computes the cost of mismatched predictions and updates the parameters towards the nearest local minimum of $\ell$ by repeated applications of the (stochastic) gradient descent algorithm $\theta_{t+1} \leftarrow \theta_t - \rho g_t$, with $\rho$ the learning rate, and

$$g_t = \frac{1}{|B|} \sum_{z_i \in B} \nabla_{\theta_t} \ell(f_{\theta_t}(x_i), y_i) \quad (1)$$

being the average gradient of the error function with respect to the parameters, computed over the samples $z_i = (x_i, y_i)$ of the minibatch $B \subseteq D$.

As is now commonplace in the machine learning literature, privacy guarantees are provided within the framework of Differential Privacy (DP):

**Definition 1 (Differential Privacy (Dwork 2006))** A randomized mechanism $\mathcal{M}: \mathcal{D} \to \mathcal{R}$ with domain $\mathcal{D}$ and range $\mathcal{R}$ satisfies $(\varepsilon, \delta)$ differential privacy if for any two datasets $D, D' \in \mathcal{D}$ differing in at most one sample, and for any outputs $S \subseteq \mathcal{R}$ it holds that

$$\mathrm{Pr}[\mathcal{M}(D) \in S] \le e^{\varepsilon} \mathrm{Pr}[\mathcal{M}(D') \in S] + \delta \quad (2)$$

To fit machine learning optimization within the definition of a differentially private random mechanism (intended here in a broad sense to also include later generalizations (Dwork and Rothblum 2016; Mironov 2017)) the average gradient in Equation (1) is sanitized by means of the Gaussian mechanism (Dwork, Roth et al. 2014). In particular, if $h: \mathcal{X} \to \mathbb{R}^n$ is a function with 2-norm sensitivity $S_h$, the DP approximation $\tilde{h}(x)$ of $h(x)$, $x \in \mathcal{X}$, can be found as

$$\tilde{h}(x) = h(x) + \eta, \quad \eta \sim \mathcal{N}(0, \sigma^2 I = S_h^2 \nu^2 I) \quad (3)$$

with $\nu$ the noise multiplier which depends only on the privacy parameters, and $\mathcal{N}$ being a random normal distribution. Tuning the additive Gaussian noise implies tuning its standard deviation proportionally to the 2-norm sensitivity of the query $g_t$ over the minibatch $B$. As, in general, $\|g_t\|_2$ is not bounded a priori, the per-sample gradients of the error function are clipped in norm to a certain value $C_t$ (Song, Chaudhuri, and Sarwate 2013; Bassily, Smith, and Thakurta 2014; Shokri and Shmatikov 2015; Abadi et al. 2016) by applying the transformation

$$\bar{g}_t(z_i) = \frac{g_t(z_i)}{\max\left(1, \frac{\|g_t(z_i)\|_2}{C_t}\right)} \quad (4)$$

from which follows the sensitivity of the average clipped gradient, allowing for the sanitization of the query at the $t^{th}$ iteration. The Gaussian mechanism lends itself to a refined analysis of the privacy leakage incurred in its repeated application, which is essential in practical machine learning with stochastic gradient descent to keep the overall privacy expenditure to a minimum over multiple training epochs (Abadi et al. 2016; Wang, Balle, and Kasiviswanathan 2019). A similar procedure can be utilized to account for multiple runs with different configurations in a grid search (Mohapatra et al. 2022).

## Related Works

This work draws from two main lines of research, namely hyperparameter optimization in non-private settings and sensitivity optimization in differentially private machine learning.

**Hyperparameter Optimization** Sub-gradient minimization strategies such as SGD iteratively approach the optimal solution by taking steps in the direction of steepest descent of a cost function. For this heuristic to be effective, the length of each step needs to be tuned by controlling the learning rate, which has been considered the “simple most important hyperparameter” (Bengio 2012). Many works have introduced strategies for its adaptive tuning, such as (Lydia and Francis 2019; Kingma and Ba 2014), which adjust the per-parameter value w.r.t. a common value
still defined a priori. Conversely, other research has exploited automatic differentiation to concurrently optimize the parameters and hyperparameters (Maclaurin, Duvenaud, and Adams 2015) via SGD. In particular, explicitly deriving the partial derivative of the cost function with respect to the learning rate has been demonstrated to be an effective strategy, and it has been discovered independently at different times (Almeida et al. 1999; Baydin et al. 2018). These works do not explore the private setting and introduce general methods that are almost exclusively applied to learning rate optimization, without addressing the choice of other hyperparameters. In (Mohapatra et al. 2022) instead, the authors study adaptive optimizers in the differentially private setting, by analyzing the estimate of the raw second moment of the gradient at convergence. Their objective is to reduce the privacy cost of tuning the learning rate in a grid search, but the clipping threshold is still treated as an additional hyper-parameter.

**Sensitivity Optimization** As discussed in the Introduction and Background sections, establishing the value of the clipping threshold $C_t$ is critical in differentially private machine learning, and treating this value as a hyperparameter has largely been the preferred strategy in the literature (Song, Chaudhuri, and Sarwate 2013; Bassily, Smith, and Thakurta 2014; Shokri and Shmatikov 2015; Abadi et al. 2016). Grid searching over the candidate values can be tricky as gradient norms may span many orders of magnitude and the effects of more aggressive clipping are not easily predicted before running an optimization. Considering also the increased privacy costs of running multiple configurations, hyperparameter selection under privacy constraints is a thriving research area (Papernot and Steinke 2022; Liu and Talwar 2019; Mohapatra et al. 2022).

Adaptive clipping strategies have also been considered. (Andrew et al. 2021) updates $C_t$ during training to match a target quantile of the gradient norms, which is fixed beforehand. Although the optimal quantile is still a hyperparameter, its domain is limited to the $[0, 1] \subset \mathbb{R}$ interval. Moreover, (Andrew et al. 2021) shows that adaptively updating $C_t$ outperforms even the best fixed-clipping strategy. Additionally, as DP training has shown to disproportionately favor majority classes in a dataset (Suriyakumar et al. 2021), tuning a target quantile instead of a fixed clipping threshold may help at least in quantifying the issue, if not in solving it. Note that although this strategy was introduced to train differentially private *federated* machine learning models, the attacker is still modelled as an *honest-but-curious* adversary and thus it relies on a central trusted server to provide DP guarantees. Therefore, the clipping strategy in (Andrew et al. 2021) can be used to train *centralized* machine learning models just by switching from user-level to sample-level differential privacy (McMahan et al. 2018b). To further stress this point, note that although in (Andrew et al. 2021) each single user clips the update and sends statistics to the central server, from a differential privacy point of view this is identical to the server performing these operations itself on the true per-user gradients.

## Method

Inspired by the literature on online hyperparameter optimization discussed in the Related Works, the idea behind this method is to optimize the clipping threshold based on the chain rule for derivatives, so that we can find what change in $C_t$ will induce a decrease in the cost function $\ell(\theta_t)$. Although this strategy works in general for sub-gradient methods, we are going to explicitly derive the results for DP-SGD. Given the SGD update rule with gradient clipping:

$$ \theta_{t+1} = \theta_t - \rho \nabla \ell(\theta_t) \quad (5) $$

$$ = \theta_t - \rho \frac{1}{|B_t|} \sum_{z_i \in B_t} \frac{g_t(z_i)}{\max(1, \|g_t(z_i)\|_2 / C_t)} \quad (6) $$

we want to find

$$ \frac{\partial \ell(\theta_t)}{\partial C_t} = \frac{\partial \ell(\theta_t)^\top}{\partial \theta_t} \frac{\partial \theta_t}{\partial C_t} \quad (7) $$

$$ = \nabla \ell(\theta_t)^\top \frac{\partial \theta_t}{\partial C_t} \quad (8) $$

$$ = -\rho \nabla \ell(\theta_t)^\top \frac{\partial \nabla \ell(\theta_{t-1})}{\partial C_{t-1}} \quad (9) $$

where in the last equality we exploit $\theta_t = \theta_{t-1} - \rho \nabla \ell(\theta_{t-1})$ and assume $C_t \approx C_{t-1}$. To find an explicit form for Equation (9), we notice that the rightmost term is differentiable almost everywhere, with:

$$ \frac{\partial \nabla \ell(\theta_{t-1})}{\partial C_{t-1}} = q_{t-1} = \frac{1}{|B_{t-1}|} \sum_{z_i \in B_{t-1}} q_{t-1}(z_i) \quad (10) $$

and

$$ q_{t-1}(z_i) = \begin{cases} \frac{g_{t-1}(z_i)}{\|g_{t-1}(z_i)\|_2} & \text{if } \|g_{t-1}(z_i)\|_2 > C_{t-1} \\ 0 & \text{otherwise} \end{cases} \quad (11) $$

where we highlight that $\|q_{t-1}(z_i)\|_2 \in \{0, 1\}, \forall z_i \in B_{t-1}$ by definition of the clipping function. Thus we find:

$$ \frac{\partial \ell(\theta_t)}{\partial C_t} = -\rho \nabla \ell(\theta_t)^\top \frac{1}{|B_{t-1}|} \sum_{z_i \in B_{t-1}} q_{t-1}(z_i) \quad (12) $$

resulting in the gradient descent update rule for the clipping threshold:

$$ C_{t+1} = C_t + \rho_c \rho \nabla \ell(\theta_t)^\top \frac{1}{|B_{t-1}|} \sum_{z_i \in B_{t-1}} q_{t-1}(z_i) \quad (13) $$

which is the dot product of the current average gradient with a masked version of last iteration's average gradient, where all per-sample gradients have either norm 0 or 1.

Taking into account the coupled dynamics of the learning rate and the clipping threshold (Mohapatra et al. 2022), having an adaptive clipping strategy may still slow down convergence if the learning rate is kept fixed at the starting value. Thus, we use the same method to derive an update strategy for the learning rate $\rho_t$, as in (Almeida et al. 1999; Baydin et al. 2018):

$$ \frac{\partial \ell(\theta_t)}{\partial \rho_t} = \frac{\partial \ell(\theta_t)^\top}{\partial \theta_t} \frac{\partial \theta_t}{\partial \rho_t} \quad (14) $$

$$ = \nabla \ell(\theta_t)^\top \nabla \ell(\theta_{t-1}) \quad (15) $$
which results in the dot product of the current and past clipped gradients, yielding:

$$ \rho_{t+1} = \rho_t + \rho_r \rho \nabla \ell(\theta_t)^\top \nabla \ell(\theta_{t-1}) \quad (16) $$

We do not further expand this result for brevity and because computing these quantities does not require a dedicated procedure, as they are already a byproduct of SGD to optimize $\theta_t$, even in a non-private setting.

## Privacy Analysis

When assuming a time-dependent $C_t$ such as in (Andrew et al. 2021), it is particularly useful to decouple the contributions of the sensitivity from contributions of the privacy parameters $(\epsilon, \delta)$ to the variance of the Gaussian mechanism, as in Equation (3). Then, within the framework of Rényi DP and given the results in (Mironov 2017; Wang, Balle, and Kasiviswanathan 2019) one can efficiently determine ahead of training-time the values of noise multiplier to be applied at each iteration independently of the current value of $C_t$. At the $t^{th}$ iteration there may be two sources of differential privacy leakage: the computation of $\theta_{t+1}$ in Equation (5) and the computation of $C_{t+1}$ in Equation (13). Both can be sanitized with the DP approximation already discussed, but the latter needs special attention. To sanitize $C_{t+1}$ with the Gaussian mechanism (for reasons detailed in Proposition 1) we may utilize $\nabla \ell(\theta_t) \approx \nabla \tilde{\ell}(\theta_t)$, effectively repurposing the sanitized gradient with respect to $\theta_t$. We focus now on the non-privatized term $\partial \nabla \ell(\theta_{t-1}) / \partial C_{t-1}$. Naturally, it still involves the sanitization of a sum of vectors, with the fortunate benefit of having all the terms in the summation be of norm either 0 or 1, as shown in Equation (11), resulting in the unit sensitivity of the query. Thus, this step does not introduce the need to develop any further “higher order” (adaptive) clipping strategies. With the considerations above, from a privacy perspective, the two privatized parallel queries behave as a single query sanitized with the Gaussian mechanism. This result is formalized in Proposition 1, which follows from the joint clipping strategy described in (McMahan et al. 2018a).

**Proposition 1** The Gaussian approximations $\tilde{q}_t$ and $\tilde{g}_t$ of $\sum_{z_i \in B_{t-1}} q_{t-1}(z_i)$ and $\sum_{z_i \in B_t} \tilde{g}_t(z_i)$ with noise multipliers, respectively, $\nu_q$ and $\nu_g$, is equivalent (as far as privacy accounting is concerned) to the application of a single Gaussian mechanism with noise multiplier $\nu$ if $\nu_g = (\nu^{-2} - \nu_q^{-2})^{-1/2}$.

Compared to Theorem 1 in (Andrew et al. 2021), we lose a factor of 2 in the reduction of the standard deviation $\sigma_q = 1 \cdot \nu_q$ and since $\nu_q$ is used here to sanitize a sum of vectors in $\mathbb{R}^n$ (whereas (Andrew et al. 2021) only need to sanitize a scalar quantity) we cannot relegate as much differentially private noise to the computation of $\tilde{q}_t$. Nonetheless, we can derive a rule of thumb, which, together with practical considerations introduced in the next section, allow to have working estimates of the true $\partial \ell(\theta_t) / \partial C_t$. In particular, if we allow a 1% increase in $\nu_q$ over $\nu$, we can rearrange the result in Proposition 1 to find $\nu_q \approx 7.124 \cdot \nu$. Figure 2 shows an example of these trade-offs for the MNIST dataset discussed in Experiments section.

<figure><img src="image_3.png" /><figcaption>Figure 2: The Pareto frontiers of the noise multipliers to sanitize $\tilde{q}_t$ and $\tilde{g}_t$, and the chosen values given the heuristic described in the Privacy Analysis section, at different privacy requirements. This particular instance comes from the MNIST experiments described in the Experiments section.</figcaption></figure>

To complete the privacy analysis, we highlight that from a DP point of view, the updates to the learning rate described in Equation (16) come with no additional privacy expenditure with respect to DP-SGD, exploiting the sanitized $\tilde{q}_t$ and $\tilde{g}_{t-1}$.

## The OSO-DPSGD Algorithm

The algorithm keeps track of two sanitized quantities at each iteration, that is:

$$ \tilde{q}_t = \frac{1}{|B_t|} \sum_{z_i \in B_t} q_t(z_i) + \eta, \quad \eta \sim \mathcal{N}(0, \nu_q^2 I) \quad (17) $$

$$ \tilde{g}_t = \frac{1}{|B_t|} \sum_{z_i \in B_t} \bar{g}_t(z_i) + \eta, \quad \eta \sim \mathcal{N}(0, C_t^2 \nu_g^2 I) \quad (18) $$

from which one can privately compute the parameter update and $\partial \tilde{\ell}(\theta_t) / \partial C_t = -\rho \tilde{q}_t^\top \tilde{q}_{t-1}$, which requires to store $\tilde{q}_{t-1}$ from the last iteration. Note that storing vectors from past iterations is a common strategy even in non-privatized learning, as e.g. it is required by every optimizer with momentum(s). In order to cater to the wide range of values $C_t$ might take, spanning orders of magnitude (Andrew et al. 2021), instead of relying on the additive update rule in Equation (13), we first consider the scale-invariant Equation (19) proposed in (Rubio 2017), which converges with a logarithmic number of steps, instead of linearly

$$ C_{t+1} = C_t \cdot \left( 1 + \rho_c \frac{\tilde{q}_t^\top \tilde{q}_{t-1}}{\|\tilde{q}_t\|_2 \|\tilde{q}_{t-1}\|_2} \right) \quad (19) $$

We briefly experimented with Equation (19) and found the proportional update step $\tilde{q}_t^\top \tilde{q}_{t-1} / \|\tilde{q}_t^\top \tilde{q}_{t-1}\|_2 =$
sign($\tilde{g}_t^\top \tilde{q}_{t-1}$) to be more robust w.r.t. the Gaussian noise and less dependent on the particular choice of $\rho_c$. Noticing that $1+x \approx e^x$ for small values of $x$, we converge to an exponential update rule for the optimization of both $C_t$ and $\rho_t$, similar to (Andrew et al. 2021):

$$C_{t+1} = C_t \cdot \exp(\rho_c \text{sign}(\tilde{g}_t^\top \tilde{q}_{t-1})) \quad (20)$$

$$\rho_{t+1} = \rho_t \cdot \exp(\rho_r \text{sign}(\tilde{g}_t^\top \tilde{q}_{t-1})) \quad (21)$$

Although we provide the result for vanilla SGD, deriving the update rule for the case with first order momentum is trivial and only adds a multiplicative factor to $\partial\ell/\partial C$, depending on the specific implementation of momentum. The same analysis for Adam is more involved and most importantly it results in the summation in $\partial\nabla\ell(\theta_{t-1})/\partial C_{t-1}$ to lose the appealing property of unitary sensitivity. Considering also the disparate results of Adam as a DP optimizer (Mohapatra et al. 2022; Andrew et al. 2021), we leave this analysis for future work. Finally, Algorithm 1 outlines the online optimization strategy presented above, which we call OSO-DPSGD.

<caption>Algorithm 1: Differentially private optimization with OSO-DPSGD</caption>

1: **Inputs** Samples $z_i \in D$; $\rho$; $T$; $C_0$; $\theta_0$; $|B|$; per-iteration noise multiplier $\nu$; $\nu_q$; $\rho_c$; $\rho_r$; $\tilde{q}_0 = \tilde{g}_0 = 0$.
2: $\nu_g \leftarrow (\nu^{-2} - \nu_q^{-2})^{-1/2}$
3: **for** $t \in \{1, \dots, T\}$ **do**
4: &nbsp;&nbsp;&nbsp;&nbsp; $B_t \leftarrow \text{draw } |B|$ samples uniformly from D
5: &nbsp;&nbsp;&nbsp;&nbsp; **for** $z_i \in B_t$ **in parallel do**
6: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; $g_t(z_i) \leftarrow \nabla_{\theta_t} \ell(\theta_t, z_i)$
7: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; $\bar{g}_t(z_i) \leftarrow g_t(z_i)/\max(1, \frac{\|g_t(z_i)\|_2}{C_t})$
8: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; $q_t(z_i) \leftarrow \frac{g_t(z_i)}{\|g_t(z_i)\|_2}$ if $\|g_t(z_i)\|_2 > C_t$ else 0
9: **end for**
10: $\sigma_g \leftarrow \nu_g C_t$
11: $\tilde{g}_t \leftarrow \frac{1}{|B|} (\sum_{z_i \in B_t} \bar{g}_t(z_i) + N(0, I\sigma_g^2))$
12: $\theta_{t+1} \leftarrow \theta_t - \rho \hat{g}_t$
13: $\tilde{q}_t \leftarrow \frac{1}{|B|} (\sum_{z_i \in B_t} q_t(z_i) + N(0, I\nu_g^2))$
14: $C_{t+1} \leftarrow C_t \exp(\rho_c \text{sign}(\tilde{g}_t^\top \tilde{q}_{t-1}))$
15: $\rho_{t+1} \leftarrow \rho_t \exp(\rho_r \text{sign}(\tilde{g}_t^\top \tilde{q}_{t-1}))$
16: **end for**

In Algorithm 1 we list the learning rates of $C_t$ and $\rho$ as hyperparameters. In practice, especially considering the exponential update rule in Equations (20) and (21), they can be set to the same value. After a qualitative exploration of reasonable values for both, we settle on $\rho_c = \rho_r = 2.5 \cdot 10^{-3}$ for all the experiments.

## Experiments

In the following Section we proceed to assess Algorithm 1 on a range of experiments on different datasets, tasks, and model sizes. In particular, we explore how online sensitivity optimization can be an effective tool in reducing the privacy and computational costs of running large grid searches. In an effort to draw conclusions that can be as general as possible,

<table><caption>Table 1: Dataset and model information shared throughout the experiments.</caption><thead><tr><th></th><th>AG News</th><th>MNIST</th><th>Fashion MNIST</th></tr></thead><tbody><tr><td>Dataset Size</td><td>120000</td><td>60000</td><td>60000</td></tr><tr><td>Batch Size</td><td>512</td><td>512</td><td>512</td></tr><tr><td>Model Size</td><td>113156</td><td>551322</td><td>48705</td></tr></tbody></table>

we identify three vastly adopted datasets in the literature: MNIST (LeCun et al. 1998), FashionMNIST (Xiao, Rasul, and Vollgraf 2017), and AG News (Gulli 2005) (Zhang, Zhao, and LeCun 2015). They are used to train, respectively, a convolutional neural network for image classification, a convolutional autoencoder and a bag of words fully connected neural network for text classification. For further details on the models and their architecture, refer to the Appendix.

Considering the computational burden of benchmarking multiple grid searches, we devise the following pipeline:

* Define the different learning algorithms; to compare OSO-DPSGD with relevant strategies, we also include in our experiments the FixedThreshold of (Song, Chaudhuri, and Sarwate 2013) (Shokri and Shmatikov 2015) (Abadi et al. 2016) among others and FixedQuantile of (Andrew et al. 2021). As reported by the respective authors, hyperparameter optimization is performed via grid search over the learning rates and threshold values for the former and over the learning rates and the quantiles for the latter. Even though (Mohapatra et al. 2022) introduce AdamWOSM for the DP adaptive optimization of the learning rate, it still tackles the challenge of reducing the number of hyperparameters in a privacy-aware grid search, and therefore we include it.

* Establish the corresponding grid search ranges. In all of our experiments, we fix the ranges of the hyperparameters to the same values. Considering the variety of experiments, and without assuming any particular domain knowledge of the task at hand, we opt for large ranges: $C \in [10^{-2}, 10^2]$ for the clipping threshold, $\rho \in [10^{-2.5}, 10^{1.5}]$ for the learning rate and $\gamma \in [0.1, 0.9]$ for the target quantile.

* Define grid searches with different granularity. Given the ranges defined in the last step, DP training introduces possibly yet another hyperparameter. In fact, increasing the granularity inevitably results in more candidates, and an additional trade off to consider is that of increased fine tuning at the cost of additional privacy leakage. In our experiments, we evaluate 3 grid searches with different granularity, i.e. from the $\rho$ and $C$ ranges in the last step we take $k \in \{5, 7, 9\}$ values uniformly separated in a logarithmic scale. For the experiments with the FixedQuantile strategy we keep the values
$\gamma \in [0.1, 0.3, 0.5, 0.7, 0.9]$ defined by the authors in (Andrew et al. 2021), as well as setting the learning rate for the exponential update rule for $C$ to 0.2. The initial value for the clipping threshold in both FixedQuantile and Online is set to $C_0 = 0.1$.

* Execute private hyperparameter optimization at different privacy levels. For the same $\delta$, we explore with increasing values of $\varepsilon$. Following (Mohapatra et al. 2022), the privacy budgets we establish are per-grid, and not per-run. That is, algorithms that need extra fine-tuning and additional parameters, resulting in more runs, will effectively reduce the per-run privacy budget. Although this setting may not conform to most past literature, we are motivated by approaching DP machine learning from the practitioner point of view, where an oracle providing the optimal hyperparameters may not be a reasonable assumption. As in (Mohapatra et al. 2022), we utilize the moment accountant to distribute the privacy budget among the configurations, as we do not have a large number of candidates.

On top of comparing DP learning strategies, we provide a baseline in the non-private setting, where we iterate only over the learning rate values and initial weights. To limit the contribution of the Gaussian random noise in the DP setting, each configuration is executed with 5 different seeds, and the results are averaged. Runs with different seeds are not accounted for in terms of privacy budget. Given the large number of runs, we validate each model at training time every 50 iterations on the full test set, and pick the model checkpoint at the best value as representative of the corresponding configuration. Each configuration runs for 10 epochs regardless of when the best performance is registered. Given the model size and datasets, the total number of epochs is enough to have most configurations converge. Nevertheless, we don't expect every combination of hyperparameters to saturate learning, e.g. when training with $C$ and $\rho$ both set at the lowest value available in the corresponding ranges. In Tables 2, 3, 4, we list the hyperparameters leading to the best results in the grid search with granularity $k = 7$ for the corresponding datasets and models. For brevity, we include detailed results only for this specific setting in the main paper. Results for the remaining granularity values, as well as the numerical results shown graphically only for $k = 7$, are deferred to the Appendix.

**Discussion** Figure 3 shows the accuracy of the models in the best configurations, among those tested, on the MNIST dataset. Even though at higher privacy levels (low $\varepsilon$) Online and AdamWOSM appear to be equivalent in terms of results, we can see the former showing better results when the privacy requirements are relaxed. A possible explanation may be found in Table 2 by noticing that the best $C$ value for AdamWOSM is fairly large compared to the other strategies. We believe that a larger initial value for $C$ may be positive to take long strides towards the direction of the average gradient at the early stages of the optimization, but may be detrimental towards the end when reducing the Gaussian noise may help the optimization. Nevertheless, we consider both strategies to be roughly equivalent in this experiment. The

<table><caption>Table 2: Best hyperparameters for the MNIST dataset with grid search granularity $k = 7$. Values with * are scaled ×10³ for better readability. Best NoDP result for $\rho = 0.003162$.</caption><thead><tr><th></th><th>Online</th><th>Fixed Threshold</th><th>Fixed Quantile</th><th>Adam WOSM</th></tr></thead><tbody><tr><td>ε</td><td>ρ</td><td>ρ</td><td>C</td><td>ρ*</td><td>γ</td></tr><tr><td>3</td><td>0.3162</td><td>0.01467</td><td>1.0</td><td>3.162</td><td>0.5</td></tr><tr><td>5</td><td>1.467</td><td>0.003162</td><td>4.64</td><td>3.162</td><td>0.7</td></tr><tr><td>7</td><td>1.467</td><td>6.812</td><td>0.010</td><td>3.162</td><td>0.7</td></tr><tr><td>9</td><td>1.467</td><td>6.812</td><td>0.010</td><td>3.162</td><td>0.7</td></tr></tbody></table>

<table><caption>Table 3: Best hyperparameters for the Fashion MNIST dataset with grid search granularity $k = 7$. Best NoDP result for $\rho = 0.01467$. All FixedQuantile runs diverge for $\varepsilon = 1$.</caption><thead><tr><th></th><th>Online</th><th>Fixed Threshold</th><th>Fixed Quantile</th><th>Adam WOSM</th></tr></thead><tbody><tr><td>ε</td><td>ρ</td><td>ρ</td><td>C</td><td>ρ*</td><td>γ</td></tr><tr><td>1</td><td>0.3162</td><td>0.0681</td><td>0.010</td><td>-</td><td>-</td></tr><tr><td>2</td><td>1.467</td><td>1.467</td><td>0.010</td><td>0.3162</td><td>0.3</td></tr><tr><td>3</td><td>1.467</td><td>6.812</td><td>0.010</td><td>1.467</td><td>0.1</td></tr><tr><td>4</td><td>1.467</td><td>1.467</td><td>0.0464</td><td>1.467</td><td>0.3</td></tr></tbody></table>

results for FixedThreshold and FixedQuantile are consistently lower, most likely due to both strategies needing a larger grid search, which in turn limits the per-run privacy budget. Perhaps more surprisingly, the adaptive strategy FixedQuantile does not seem to show better results compared to fixing the clipping threshold at the initial value. The improved results that are found in (Andrew et al. 2021) in the federated setting do not seem to translate in centralized learning, with the experiments we conducted.

Figure 4 shows the best results in terms of mean squared error on the FashionMNIST dataset, where a model is trained to encode and decode the input images of clothing items. The chosen architecture is based on a convolutional autoencoder, and it has the smallest number of parameters among those considered in this work, as in Table 1. The privacy regimes are then chosen accordingly. Firstly, we notice that for $\varepsilon = 1$ the FixedQuantile strategy does not con-

<table><caption>Table 4: Best hyperparameters for the AG News dataset. Values with * are scaled ×10³ for better readability. $k = 7$. Best NoDP result for $\rho = 0.003162$.</caption><thead><tr><th></th><th>Online</th><th>Fixed Threshold</th><th>Fixed Quantile</th><th>Adam WOSM</th></tr></thead><tbody><tr><td>ε</td><td>ρ</td><td>ρ</td><td>C</td><td>ρ*</td><td>γ</td></tr><tr><td>3</td><td>0.06812</td><td>1.467</td><td>0.01</td><td>3.162</td><td>0.5</td></tr><tr><td>5</td><td>0.06812</td><td>1.467</td><td>0.010</td><td>3.162</td><td>0.5</td></tr><tr><td>7</td><td>0.06812</td><td>1.467</td><td>0.010</td><td>3.162</td><td>0.7</td></tr><tr><td>9</td><td>0.06812</td><td>0.03162</td><td>0.0464</td><td>3.162</td><td>0.7</td></tr></tbody></table>
<figure><img src="image_4.png" /><figcaption>Figure 3: Accuracy on the MNIST dataset. Higher is better.</figcaption></figure>

verge with any of the available hyperparameters. To justify this result, we highlight how in Table 3 all other strategies adopt aggressive clipping strategies with small *C*'s. We thus believe that for very high privacy regimes even running with $\gamma = 0.1$ (the lowest value for the target quantile) may induce large swings in the exponential updates of $C_t$, disrupting the optimization. Nevertheless, for $\varepsilon \in \{2, 3, 4\}$ this strategy shows the second best results. Conversely, AdamWOSM may be penalized by the choice of the initial $\rho_0 = 10^{-3}$, as suggested by the authors in (Mohapatra et al. 2022). In fact, we notice from Table 4 that the optimal clipping threshold is very small in all competing strategies, and the combination of small *C* and small $\rho_0$ may render the optimization excessively slow to converge within the set number of epochs. Further, it may suggest that adapting the learning rate on a per-parameter basis, as in AdamWOSM, can be effective as long as the base learning rate is itself carefully selected. Thus, optimizing $\rho_t$ in the grid search, and then adaptively tuning it within the same run, as done in Online, seems to show better results.

Figure 5 plots the accuracy on the AG News dataset, where a bag of words model with a fully connected neural network is used to classify a selection of news in one of four classes. In this experiment we notice that AdamWOSM performs the best, with Online being marginally below. Still, as with the MNIST dataset, we take both strategies to be comparable in these two settings, as the average of one roughly fits within a standard deviation of the other.

Conclusion

This work studies differentially private machine learning in the context of hyperparameter optimization, where the privacy cost of running a grid search is accounted for. Under these conditions, algorithms that require one less parameter may be preferable. Thus we explore strategies for the adaptive tuning of the clipping threshold *C*, and derive a result inspired by online learning rate optimization. With the proposed strategy, which we incorporate in the OSO-DPSGD algorithm, the clipping threshold is updated at each iteration

<figure><img src="image_5.png" /><figcaption>Figure 4: Mean Squared Error on the Fashion MNIST dataset. Lower is better. All runs for $\varepsilon = 1$ of FixedQuantile result in a diverging optimization and are therefore not included.</figcaption></figure>

<figure><img src="image_6.png" /><figcaption>Figure 5: Accuracy on the AG News dataset. Higher is better.</figcaption></figure>

based on the direction of steepest descent of the cost function. The resulting update rule is particularly clean, and results in the dot product between two sanitized vector queries: the average gradient at time *t*, and the derivative w.r.t. *C* of the gradient at time *t* − 1. With the former already needed in standard DP-SGD, and the latter resulting in a query with unitary sensitivity, the additional computational and privacy burden is minimal. Our range of experiments seems to encourage further research in this area, as online sensitivity optimization shows comparable results with one less parameter when assessed against standard state of the art algorithms, if the privacy guarantees are required at a grid search level, and not just within a single run. In the future, we hope to refine our analysis and algorithm, to possibly achieve better results even in this latter setting of per-run privacy requirements.
Acknowledgments

The work of Catuscia Palamidessi was supported by the Eu-
ropean Research Council (ERC) grant Hypatia (grant agree-
ment N. 835294) under the European Union’s Horizon 2020
research and innovation programme.

References

Abadi, M.; Chu, A.; Goodfellow, I.; McMahan, H. B.; Mironov, I.; Talwar, K.; and Zhang, L. 2016. Deep learning with differential privacy. In *Proceedings of the 2016 ACM SIGSAC conference on computer and communications security*, 308–318.

Almeida, L. B.; Langlois, T.; Amaral, J. D.; and Plakhov, A. 1999. Parameter adaptation in stochastic optimization. In *On-line learning in neural networks*, 111–134.

Andrew, G.; Thakkar, O.; McMahan, B.; and Ramaswamy, S. 2021. Differentially private learning with adaptive clipping. *Advances in Neural Information Processing Systems*, 34: 17455–17466.

Bassily, R.; Smith, A.; and Thakurta, A. 2014. Private empirical risk minimization: Efficient algorithms and tight error bounds. In *2014 IEEE 55th annual symposium on foundations of computer science*, 464–473. IEEE.

Baydin, A. G.; Cornish, R.; Rubio, D. M.; Schmidt, M.; and Wood, F. 2018. Online Learning Rate Adaptation with Hypergradient Descent. In *International Conference on Learning Representations*.

Bengio, Y. 2012. Practical recommendations for gradient-based training of deep architectures. In *Neural Networks: Tricks of the Trade: Second Edition*, 437–478. Springer.

Carlini, N.; Hayes, J.; Nasr, M.; Jagielski, M.; Sehwag, V.; Tramer, F.; Balle, B.; Ippolito, D.; and Wallace, E. 2023. Extracting training data from diffusion models. *arXiv preprint arXiv:2301.13188*.

Carlini, N.; Tramer, F.; Wallace, E.; Jagielski, M.; Herbert-Voss, A.; Lee, K.; Roberts, A.; Brown, T.; Song, D.; Erlingson, U.; et al. 2021. Extracting training data from large language models. In *30th USENIX Security Symposium (USENIX Security 21)*, 2633–2650.

Chen, X.; Wu, S. Z.; and Hong, M. 2020. Understanding gradient clipping in private SGD: A geometric perspective. *Advances in Neural Information Processing Systems*, 33: 13773–13782.

Dwork, C. 2006. Differential privacy. In *International colloquium on automata, languages, and programming*, 1–12. Springer.

Dwork, C.; Roth, A.; et al. 2014. The algorithmic foundations of differential privacy. *Foundations and Trends® in Theoretical Computer Science*, 9(3–4): 211–407.

Dwork, C.; and Rothblum, G. 2016. Concentrated differential privacy.

Gulli, A. 2005. The anatomy of a news search engine. In *Special interest tracks and posters of the 14th international conference on World Wide Web*, 880–881.

Kingma, D. P.; and Ba, J. 2014. Adam: A method for stochastic optimization. *arXiv preprint arXiv:1412.6980*.

LeCun, Y.; Bottou, L.; Bengio, Y.; and Haffner, P. 1998. Gradient-based learning applied to document recognition. *Proceedings of the IEEE*, 86(11): 2278–2324.

Liu, J.; and Talwar, K. 2019. Private selection from private candidates. In *Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing*, 298–309.

Lydia, A.; and Francis, S. 2019. Adagrad—an optimizer for stochastic gradient descent. *Int. J. Inf. Comput. Sci*, 6(5): 566–568.

Maclaurin, D.; Duvenaud, D.; and Adams, R. 2015. Gradient-based hyperparameter optimization through reversible learning. In *International conference on machine learning*, 2113–2122. PMLR.

McMahan, H. B.; Andrew, G.; Erlingsson, U.; Chien, S.; Mironov, I.; Papernot, N.; and Kairouz, P. 2018a. A general approach to adding differential privacy to iterative training procedures. *arXiv preprint arXiv:1812.06210*.

McMahan, H. B.; Ramage, D.; Talwar, K.; and Zhang, L. 2018b. Learning Differentially Private Recurrent Language Models. In *International Conference on Learning Representations*.

Mironov, I. 2017. Rényi differential privacy. In *2017 IEEE 30th computer security foundations symposium (CSF)*, 263–275. IEEE.

Mohapatra, S.; Sasy, S.; He, X.; Kamath, G.; and Thakkar, O. 2022. The role of adaptive optimizers for honest private hyperparameter selection. In *Proceedings of the AAAI conference on artificial intelligence*, volume 36, 7806–7813.

Papernot, N.; McDaniel, P.; Sinha, A.; and Wellman, M. P. 2018. Sok: Security and privacy in machine learning. In *2018 IEEE European Symposium on Security and Privacy (EuroS&P)*, 399–414. IEEE.

Papernot, N.; and Steinke, T. 2022. Hyperparameter Tuning with Renyi Differential Privacy. In *International Conference on Learning Representations*.

Pennington, J.; Socher, R.; and Manning, C. D. 2014. GloVe: Global Vectors for Word Representation. In *Empirical Methods in Natural Language Processing (EMNLP)*, 1532–1543.

Rubio, D. M. 2017. Convergence analysis of an adaptive method of gradient descent. *University of Oxford, Oxford, M. Sc. thesis*.

Shokri, R.; and Shmatikov, V. 2015. Privacy-preserving deep learning. In *Proceedings of the 22nd ACM SIGSAC conference on computer and communications security*, 1310–1321.

Song, S.; Chaudhuri, K.; and Sarwate, A. D. 2013. Stochastic gradient descent with differentially private updates. In *2013 IEEE global conference on signal and information processing*, 245–248. IEEE.

Suriyakumar, V. M.; Papernot, N.; Goldenberg, A.; and Ghassemi, M. 2021. Chasing your long tails: Differentially private prediction in health care settings. In *Proceedings of the 2021 ACM Conference on Fairness, Accountability, and Transparency*, 723–734.
Wang, Y.-X.; Balle, B.; and Kasiviswanathan, S. P. 2019. Subsampled rényi differential privacy and analytical moments accountant. In *The 22nd International Conference on Artificial Intelligence and Statistics*, 1226–1235. PMLR.

Xiao, H.; Rasul, K.; and Vollgraf, R. 2017. Fashion-mnist: a novel image dataset for benchmarking machine learning algorithms. *arXiv preprint arXiv:1708.07747*.

Zhang, X.; Zhao, J.; and LeCun, Y. 2015. Character-level convolutional networks for text classification. *Advances in neural information processing systems*, 28.
# Appendix - Models and Experiments

As mentioned in the corresponding Section of the main paper, we provide additional details about the model architectures, datasets, and results of experiments at different granularity levels. The model architectures are outlined in Tables 5, 6, 7. All datasets go through minor pre-processing, that is pixel values are mapped to the [0, 1] interval, while the text-based dataset AG News first goes through word embedding, using an embedding size of 50 for up to the first 25 words. To speed up development, we use the pre-trained word embeddings from (Pennington, Socher, and Manning 2014). Next, we report the results for granularity $k = 5$ in Tables 11, 12, 13 and Figures 9, 10 and 11. For $k = 9$, results are presented in Tables 8, 9, 10 and Figures 6, 7 and 8.

<table><caption>Table 5: CNN</caption><thead><tr><th colspan="4">CNN</th></tr><tr><th>layer</th><th>kernel size<br>output size</th><th>stride</th><th>non<br>linearity</th></tr></thead><tbody><tr><td>2D Conv</td><td>16 × 8 × 8</td><td>1 × 1</td><td>ReLU</td></tr><tr><td>2D MaxPool</td><td>2 × 2</td><td>1 × 1</td><td>-</td></tr><tr><td>2D Conv</td><td>32 × 4 × 4</td><td>1 × 1</td><td>ReLU</td></tr><tr><td>Linear</td><td>32</td><td>-</td><td>ReLU</td></tr><tr><td>Linear</td><td>10</td><td>-</td><td>ReLU</td></tr></tbody></table>

<table><caption>Table 6: AutoEncoder</caption><thead><tr><th colspan="4">AutoEncoder</th></tr><tr><th>layer</th><th>kernel size<br>output size</th><th>stride</th><th>non<br>linearity</th></tr></thead><tbody><tr><td>2D Conv</td><td>8 × 3 × 3</td><td>1 × 1</td><td>LeakyReLU</td></tr><tr><td>2D Conv</td><td>16 × 3 × 3</td><td>1 × 1</td><td>LeakyReLU</td></tr><tr><td>2D Conv</td><td>32 × 3 × 3</td><td>1 × 1</td><td>LeakyReLU</td></tr><tr><td>2D Conv</td><td>64 × 3 × 3</td><td>1 × 1</td><td>LeakyReLU</td></tr><tr><td>2D Transpose Conv</td><td>32 × 3 × 3</td><td>1 × 1</td><td>LeakyReLU</td></tr><tr><td>2D Transpose Conv</td><td>16 × 3 × 3</td><td>1 × 1</td><td>LeakyReLU</td></tr><tr><td>2D Transpose Conv</td><td>8 × 3 × 3</td><td>1 × 1</td><td>LeakyReLU</td></tr><tr><td>2D Transpose Conv</td><td>1 × 3 × 3</td><td>1 × 1</td><td>Sigmoid</td></tr></tbody></table>

<table><caption>Table 7: Bag of Words model architecture with a fully connected neural network.</caption><thead><tr><th colspan="3">BagOfWords - FC</th></tr><tr><th>layer</th><th>output size</th><th>non<br>linearity</th></tr></thead><tbody><tr><td>Linear</td><td>128</td><td>LeakyReLU</td></tr><tr><td>Linear</td><td>128</td><td>LeakyReLU</td></tr><tr><td>Linear</td><td>4</td><td>LeakyReLU</td></tr></tbody></table>

<figure><img src="image_7.png" /><figcaption>Figure 6: $k = 9$. Accuracy on the MNIST dataset. Higher is better. Refer to Table 8 for numeric results and optimized hyperparameters.</figcaption></figure>

<figure><img src="image_8.png" /><figcaption>Figure 7: $k = 9$. Mean Squared Error on the Fashion MNIST dataset. Lower is better. Refer to Table 9 for numeric results and optimized hyperparameters.</figcaption></figure>
<table><caption>Table 8: MNIST, k = 9, best NODP for ρ = 0.003162, * values are scaled ×10³.</caption><thead><tr><th rowspan="2">ε</th><th colspan="3">Online</th><th colspan="4">Fixed Threshold</th><th colspan="3">Fixed Quantile</th><th colspan="3">Adam WOSM</th></tr><tr><th>ρ</th><th>acc</th><th>std dev</th><th>ρ</th><th>C</th><th>acc</th><th>std dev</th><th>ρ*</th><th>γ</th><th>acc</th><th>std dev</th><th>C</th><th>acc</th><th>std dev</th></tr></thead><tbody><tr><td>3</td><td>0.316</td><td>90.69</td><td>0.53</td><td>100.0</td><td>0.1000</td><td>86.83</td><td>0.70</td><td>3.162</td><td>0.5</td><td>85.48</td><td>0.39</td><td>10.0</td><td>90.62</td><td>0.52</td></tr><tr><td>5</td><td>1.00</td><td>91.62</td><td>0.83</td><td>3.162</td><td>3.162</td><td>88.69</td><td>0.57</td><td>3.162</td><td>0.5</td><td>88.13</td><td>0.59</td><td>10.0</td><td>91.60</td><td>0.39</td></tr><tr><td>7</td><td>1.00</td><td>92.94</td><td>0.90</td><td>3162.0</td><td>0.0100</td><td>90.04</td><td>0.49</td><td>3.162</td><td>0.7</td><td>90.73</td><td>0.72</td><td>31.62</td><td>92.19</td><td>0.37</td></tr><tr><td>9</td><td>1.00</td><td>93.62</td><td>0.91</td><td>3.162</td><td>10.00</td><td>90.72</td><td>0.47</td><td>3.162</td><td>0.7</td><td>91.09</td><td>0.51</td><td>31.62</td><td>92.53</td><td>0.33</td></tr></tbody></table>

<table><caption>Table 9: FashionMNIST, k = 9, best NODP for ρ = 0.003162.</caption><thead><tr><th rowspan="2">ε</th><th colspan="3">Online</th><th colspan="4">Fixed Threshold</th><th colspan="3">Fixed Quantile</th><th colspan="3">Adam WOSM</th></tr><tr><th>ρ</th><th>mse ×10<sup>2</sup></th><th>std dev</th><th>ρ</th><th>C</th><th>mse ×10<sup>2</sup></th><th>std dev</th><th>ρ</th><th>γ</th><th>mse ×10<sup>2</sup></th><th>std dev</th><th>C</th><th>mse ×10<sup>2</sup></th><th>std dev</th></tr></thead><tbody><tr><td>1</td><td>0.100</td><td>2.57</td><td>0.29</td><td>0.0316</td><td>0.01</td><td>11.32</td><td>1.46</td><td>-</td><td>-</td><td>-</td><td>-</td><td>0.0100</td><td>4.48</td><td>0.83</td></tr><tr><td>2</td><td>1.000</td><td>0.94</td><td>0.13</td><td>0.100</td><td>0.01</td><td>12.35</td><td>1.87</td><td>0.316</td><td>0.3</td><td>2.17</td><td>0.25</td><td>0.0100</td><td>2.35</td><td>0.16</td></tr><tr><td>3</td><td>3.162</td><td>0.74</td><td>0.10</td><td>0.3162</td><td>0.10</td><td>1.54</td><td>0.04</td><td>1.000</td><td>0.1</td><td>1.26</td><td>0.04</td><td>0.0316</td><td>1.97</td><td>0.13</td></tr><tr><td>4</td><td>3.162</td><td>0.76</td><td>0.02</td><td>1.000</td><td>0.10</td><td>1.37</td><td>0.10</td><td>1.000</td><td>0.3</td><td>1.05</td><td>0.10</td><td>0.0316</td><td>1.76</td><td>0.10</td></tr></tbody></table>

<figure><img src="image_9.png" /><figcaption>Figure 8: k = 9. Accuracy on the AG News dataset. Higher is better. Refer to Table 10 for numeric results and optimized hyperparameters.</figcaption></figure>

<figure><img src="image_10.png" /><figcaption>Figure 9: k = 5. Accuracy on the MNIST dataset. Higher is better. Refer to Table 11 for numeric results and optimized hyperparameters.</figcaption></figure>
<table><caption>Table 10: AG News, $k = 9$, * values are scaled ×10³, best NODP for $ρ = 0.003162$.</caption><thead><tr><th rowspan="2">ε</th><th colspan="3">Online</th><th colspan="3">Fixed Threshold</th><th colspan="3">Fixed Quantile</th><th colspan="3">Adam WOSM</th></tr><tr><th>ρ</th><th>acc</th><th>std dev</th><th>ρ</th><th>C</th><th>acc</th><th>std dev</th><th>ρ*</th><th>γ</th><th>acc</th><th>std dev</th><th>C</th><th>acc</th><th>std dev</th></tr></thead><tbody><tr><td>3</td><td>0.1</td><td>85.70</td><td>0.15</td><td>1.000</td><td>0.0100</td><td>84.23</td><td>0.29</td><td>3.162</td><td>0.5</td><td>83.67</td><td>0.48</td><td>0.0100</td><td>85.82</td><td>0.11</td></tr><tr><td>5</td><td>0.1</td><td>86.12</td><td>0.05</td><td>0.316</td><td>0.0316</td><td>85.27</td><td>0.25</td><td>3.162</td><td>0.5</td><td>84.49</td><td>0.31</td><td>0.0100</td><td>86.13</td><td>0.05</td></tr><tr><td>7</td><td>0.1</td><td>86.34</td><td>0.12</td><td>0.100</td><td>0.1000</td><td>85.59</td><td>0.23</td><td>3.162</td><td>0.7</td><td>85.19</td><td>0.17</td><td>0.0100</td><td>86.33</td><td>0.03</td></tr><tr><td>9</td><td>0.1</td><td>86.43</td><td>0.08</td><td>0.316</td><td>0.0316</td><td>85.74</td><td>0.20</td><td>3.162</td><td>0.7</td><td>85.65</td><td>0.15</td><td>0.0316</td><td>86.43</td><td>0.05</td></tr></tbody></table>

<table><caption>Table 11: MNIST, $k = 5$, * values are scaled ×10³, best NODP for $ρ = 0.003162$.</caption><thead><tr><th rowspan="2">ε</th><th colspan="3">Online</th><th colspan="3">Fixed Threshold</th><th colspan="3">Fixed Quantile</th><th colspan="3">Adam WOSM</th></tr><tr><th>ρ</th><th>acc</th><th>std dev</th><th>ρ*</th><th>C</th><th>acc</th><th>std dev</th><th>ρ*</th><th>γ</th><th>acc</th><th>std dev</th><th>C</th><th>acc</th><th>std dev</th></tr></thead><tbody><tr><td>3</td><td>0.316</td><td>91.19</td><td>0.51</td><td>3.162.0</td><td>0.01</td><td>89.2</td><td>0.39</td><td>3.162</td><td>0.5</td><td>87.91</td><td>0.62</td><td>10.0</td><td>91.27</td><td>0.46</td></tr><tr><td>5</td><td>0.316</td><td>91.66</td><td>0.50</td><td>3.162</td><td>10.00</td><td>90.9</td><td>0.49</td><td>3.162</td><td>0.7</td><td>90.71</td><td>0.69</td><td>10.0</td><td>92.16</td><td>0.38</td></tr><tr><td>7</td><td>3.162</td><td>92.96</td><td>0.90</td><td>3.162</td><td>10.00</td><td>91.4</td><td>0.43</td><td>3.162</td><td>0.7</td><td>91.16</td><td>0.49</td><td>10.0</td><td>92.76</td><td>0.52</td></tr><tr><td>9</td><td>3.162</td><td>94.11</td><td>0.63</td><td>3.162</td><td>10.00</td><td>91.7</td><td>0.42</td><td>3.162</td><td>0.7</td><td>91.21</td><td>0.47</td><td>10.0</td><td>93.22</td><td>0.70</td></tr></tbody></table>

<table><caption>Table 12: Fashion MNIST, $k = 5$, best NODP for $ρ = 0.003162$.</caption><thead><tr><th rowspan="2">ε</th><th colspan="3">Online</th><th colspan="3">Fixed Threshold</th><th colspan="3">Fixed Quantile</th><th colspan="3">Adam WOSM</th></tr><tr><th>ρ</th><th>mse ×10<sup>2</sup></th><th>std dev</th><th>ρ</th><th>C</th><th>mse ×10<sup>2</sup></th><th>std dev</th><th>ρ</th><th>γ</th><th>mse ×10<sup>2</sup></th><th>std dev</th><th>C</th><th>mse ×10<sup>2</sup></th><th>std dev</th></tr></thead><tbody><tr><td>3</td><td>0.316</td><td>1.56</td><td>0.10</td><td>0.0316</td><td>0.01</td><td>12.88</td><td>2.37</td><td>-</td><td>-</td><td>-</td><td>-</td><td>0.01</td><td>3.43</td><td>0.26</td></tr><tr><td>5</td><td>3.162</td><td>0.77</td><td>0.05</td><td>3.162</td><td>0.01</td><td>1.44</td><td>0.08</td><td>0.316</td><td>0.3</td><td>1.71</td><td>0.08</td><td>0.01</td><td>2.09</td><td>0.18</td></tr><tr><td>7</td><td>3.162</td><td>0.67</td><td>0.09</td><td>0.3162</td><td>0.10</td><td>1.54</td><td>0.10</td><td>3.162</td><td>0.1</td><td>1.06</td><td>0.03</td><td>0.01</td><td>1.81</td><td>0.18</td></tr><tr><td>9</td><td>3.162</td><td>0.64</td><td>0.07</td><td>3.162</td><td>0.01</td><td>1.25</td><td>0.14</td><td>3.162</td><td>0.1</td><td>0.84</td><td>0.08</td><td>0.01</td><td>1.51</td><td>0.11</td></tr></tbody></table>

<table><caption>Table 13: AG News, $k = 5$, best NODP for $ρ = 0.003162$.</caption><thead><tr><th rowspan="2">ε</th><th colspan="3">Online</th><th colspan="3">Fixed Threshold</th><th colspan="3">Fixed Quantile</th><th colspan="3">Adam WOSM</th></tr><tr><th>ρ</th><th>acc</th><th>std dev</th><th>ρ</th><th>C</th><th>acc</th><th>std dev</th><th>ρ</th><th>γ</th><th>acc</th><th>std dev</th><th>C</th><th>acc</th><th>std dev</th></tr></thead><tbody><tr><td>3</td><td>0.0316</td><td>85.82</td><td>0.18</td><td>3.162</td><td>0.01</td><td>84.37</td><td>0.25</td><td>3.162</td><td>0.5</td><td>84.32</td><td>0.34</td><td>0.01</td><td>86.07</td><td>0.05</td></tr><tr><td>5</td><td>0.3162</td><td>86.12</td><td>0.11</td><td>3.162</td><td>0.01</td><td>85.49</td><td>0.10</td><td>3.162</td><td>0.7</td><td>85.20</td><td>0.17</td><td>0.01</td><td>86.33</td><td>0.03</td></tr><tr><td>7</td><td>0.3162</td><td>86.32</td><td>0.09</td><td>3.162</td><td>0.01</td><td>85.97</td><td>0.07</td><td>3.162</td><td>0.7</td><td>85.71</td><td>0.18</td><td>0.01</td><td>86.51</td><td>0.06</td></tr><tr><td>9</td><td>0.3162</td><td>86.38</td><td>0.12</td><td>3.162</td><td>0.01</td><td>86.18</td><td>0.07</td><td>3.162</td><td>0.7</td><td>85.93</td><td>0.18</td><td>0.01</td><td>86.57</td><td>0.11</td></tr></tbody></table>
<figure><img src="image_11.png" /><figcaption>Figure 10: $k = 5$. Mean Squared Error on the Fashion MNIST dataset. Lower is better. Refer to Table 12 for numeric results and optimized hyperparameters.</figcaption></figure>

<figure><img src="image_12.png" /><figcaption>Figure 11: $k = 5$. Accuracy on the AGNEWS dataset. Higher is better. Refer to Table 13 for numeric results and optimized hyperparameters.</figcaption></figure>