# Inference and Interference: The Role of Clipping, Pruning and Loss
Landscapes in Differentially Private Stochastic Gradient Descent

Lauren Watson,1 Eric Gan,2 Mohan Dantam ,1 Baharan Mirzasoleiman,2 Rik Sarkar
1
1School of Informatics, University of Edinburgh
2University of California, Los Angeles
<EMAIL_ADDRESS><EMAIL_ADDRESS><EMAIL_ADDRESS>
###### Abstract

Differentially private stochastic gradient descent (DP-SGD) is known to have
poorer training and test performance on large neural networks, compared to
ordinary stochastic gradient descent (SGD). In this paper, we perform a
detailed study and comparison of the two processes and unveil several new
insights. By comparing the behavior of the two processes separately in early
and late epochs, we find that while DP-SGD makes slower progress in early
stages, it is the behavior in the later stages that determines the end result.
This separate analysis of the clipping and noise addition steps of DP-SGD
shows that while noise introduces errors to the process, gradient descent can
recover from these errors when it is not clipped, and clipping appears to have
a larger impact than noise. These effects are amplified in higher dimensions
(large neural networks), where the loss basin occupies a lower dimensional
space. We argue theoretically and using extensive experiments that magnitude
pruning can be a suitable dimension reduction technique in this regard, and
find that heavy pruning can improve the test accuracy of DPSGD.

##  1 INTRODUCTION

The wide-ranging potential applications of deep learning models trained on
large datasets has recently raised concerns about the privacy properties of
these models. The current method to enforce privacy while training such models
is differential privacy (Dwork,, 2006). The most popular of these methods is
Differentially Private Stochastic Gradient Descent (DP-SGD) (Abadi et al.,,
2016). By restricting the maximum gradient norm and adding suitable noise at
every step of ordinary Stochastic Gradient Descent (SGD), it ensures the
rigorous privacy properties of differential privacy and defends against
privacy attacks (Shokri et al.,, 2017; Fredrikson et al.,, 2015; Nasr et al.,,
2019; Carlini et al.,, 2019).

The perturbations produced by noise addition and gradient clipping come at the
cost of reduced utility, and the practical performance of DP-SGD – as measured
by common loss and accuracy measures – is found to be consistently inferior to
that of SGD, even on standard benchmark tasks (Papernot et al.,, 2021). This
gap is governed by several entities including the class of models, the
gradients generated by SGD, the perturbation induced by DP-SGD, and the loss
landscape over the space of models $\mathcal{H}$ where the training process
takes place. The relations between these entities are complex, and are the
subject of this paper. It has been conjectured that the primary weakness of
DP-SGD is in the early rounds, where the noise may inhibit it from identifying
a good basin (Ganesh et al.,, 2023) within the loss landscape. Having missed
the opportunity, it is constrained to the quality of the basin it finds. On
the other hand, studies on the SGD process have found that it is often
possible to arrive at equally good minima from different starting points of
SGD (Frankle et al.,, 2020) and for some common learning tasks, these
different loss basin floors are connected (Garipov et al.,, 2018). The
performance of DP-SGD is known to deteriorate with the dimension of
$\mathcal{H}$, or equivalently, with the number of parameters of the model,
since to privatize a greater number of parameters requires greater noise.
Thus, several methods have been proposed to reduce the number of parameters by
pruning, gradient sparsification and others (Luo et al.,, 2021; Li et al.,,
2022; Zhou et al.,, 2021).

###  1.1 Contributions

We provide several insights into the behavior of DP-SGD by comparing it with
the fine grained behavior of ordinary SGD. The results include observations
about the nature of the loss basins, why DP-SGD fails to find a floor
(minimum) of the basin as effectively as SGD does, how clipping and noise
addition contribute to the process, and how pruning improves the performance.
Below, we summarize these findings.

If the early rounds of training are decisive, as suggested in (Ganesh et al.,,
2023) then the process – SGD or DP-SGD – used in the first few (say $k$
epochs) will determine the quality of the model, irrespective of the process
operating in later epochs. To test this idea, we divided the $T$ step training
process into Phase 1 (first $k$ epochs) and Phase 2 (remaining $T-k$ epochs).
Then four models were trained corresponding to using SGD or DP-SGD in each of
the phases. The results consistently show that the process used in Phase 2 has
a larger impact. In Figure 2, the loss and accuracy levels at the end of Phase
1 are clearly different for SGD and DP-SGD. But in Phase 2, the results
change, so that the SGD processes in Phase 2 converge to similar low losses,
while the processes running DP-SGD in Phase 2 converge to higher loss. Thus,
contrary to the conjecture in Ganesh et al., (2023), it is the Phase 2 process
that is decisive, suggesting that the perturbations prevent DP-SGD from
finding a good solution irrespective of initial steps. Similar results on
other models are found in Section 4.

Figure 1: Loss Basins with $1$-D Basin floors (shown as blue lines). Loss
basin dimension is low compared to ambient dimension. SGD finds and stays at
the floor. DP-SGD finds it hard to stay at the floor as the large magnitude of
random noise easily throws it far from the floor, and loss increases rapidly
in random directions.

Next, we turn to studying the loss landscape and loss basins that guide the
training process. In experiments (also seen in (Frankle et al.,, 2020; Garipov
et al.,, 2018)), SGD usually finds a model at the floor (or plateau) of a loss
basin. At the floor, there are a few directions where the loss stays flat. We
find that in most other directions, the loss rises rapidly. The conclusion
from this result is that while the ambient dimension (the number of parameters
or weights) of a neural network is large, a loss basin lies only in a
relatively lower dimensional subspace. The idea is shown schematically in
Figure 1, where one dimensional loss basins are embedded in $3D$ space. In
almost any direction from a basin floor, the loss rises rapidly. When the
number of orthogonal dimensions are larger, the effect is more pronounced, and
has major consequences for DP-SGD: since the noise induced by DP-SGD is a
random vector drawn from a high dimensional Gaussian, and therefore of large
magnitude. The result is that DP-SGD cannot find the basin floor or remain
close to it. (Figure 1).

Further, even with quite short lengths of Phase 1, SGD can find its basin,
after which SGD processes end on the same basin floor. However, when DP-SGD is
used in Phase 2, processes usually do not end in the same basin. In fact, in
many cases, DP-SGD jumps from one basin to another. Even when models do
converge to the same basin, DP-SGD does not find a floor that SGD does
consistently.

We then examine the effects of clipping and noise addition separately. In
experiments, while SGD can tolerate noise addition of the same scale as that
required to guarantee $\epsilon=1$ differential privacy, clipping to the same
level as an $\epsilon=1$ DP-SGD model significantly reduces SGD test accuracy.
We use analysis at both small scales (a few training steps) and larger scales
(a full training run) to provide evidence that the clipping operation prevents
the DP-SGD model from recovering from noise addition that would otherwise have
little impact on the training ability for the model.

Given this understanding of the low dimensional loss basins, and the impact of
clipping and noise addition on finding these solutions, we show that suitable
pruning can mitigate these effects. As with previous work ((Luo et al.,,
2021)) we find that appropriate pruning improves the accuracy of DP-SGD and
that pruned DP-SGD models better replicate the low dimensional behavior of SGD
models. Even when the pruning is carried out using only $5\%$ of the data or
with a different dataset, DP-SGD on the pruned network generalizes better than
DP-SGD on the full network. Separate experiments on clipping and noise
addition show that pruning significantly reduces the impact of the clipping
operation.

Theoretically, while it is clear from previous work that the effect of noise
increases with the number of parameters (Bassily et al.,, 2014) and therefore
pruning will reduce the impact of noise, the effect of clipping and the
corresponding potential benefits of pruning are less immediate. We show that
pruning can in fact reduce the harmful effects of clipping, by defining a term
$R$ based on the variance along each dimension and the true gradient norm,
which decreases with improvement in clipped gradient. The reduction of this
term with pruning is verified empirically.

##  2 TECHNICAL BACKGROUND

###  2.1 Differential privacy and Stochastic Gradient Descent

Differential privacy as outlined in Definition 2.2 guarantees that the
presence or absence of a single datapoint in the underlying training dataset
will have a limited impact on the output model, with lower values of
$\epsilon$ corresponding to stronger privacy guarantees.

######  Definition 2.1 (Neighboring Databases).

Two databases $D,D^{\prime}$ are neighboring if $H(D,D^{\prime})\leq 1$, where
$H(\cdot,\cdot)$ represents the hamming distance.

######  Definition 2.2 (Differential Privacy (Dwork,, 2006)).

A randomized algorithm $M$ satisfies $(\epsilon,\delta)$-differential privacy
if for all neighboring databases $D$ and $D^{\prime}$ and for all possible
outputs $O\subseteq\text{Range}(M)$,  $\Pr[M(D)\in O]\leq
e^{\epsilon}\cdot\Pr[M(D^{\prime})\in O]+\delta$

Differentially private algorithms often rely on carefully calibrated noise
addition to provably ensure differential privacy (Dwork et al.,, 2006). Abadi
et al., (2016) introduced a differentially private variant of the stochastic
gradient descent algorithm (DP-SGD). Given data distribution
$\mathcal{Z}=\mathcal{X}\times\mathcal{Y}$, loss function
$L:(\mathbf{\theta},\mathbf{z})\rightarrow\mathbb{R}$ for any
$\mathbf{z}\in\mathcal{Z}$, learning rate $\eta\in\mathbb{R}^{+}$, and model
parameters $\mathbf{\theta}_{t}$ at training step $t$, SGD calculates the
gradient $\mathbf{g}_{t}=\nabla_{\mathbf{\theta}_{t}}L(\theta_{t},\mathbf{z})$
and updates the model parameters to
$\mathbf{\theta}_{t+1}=\mathbf{\theta}_{t}-\eta\mathbf{g}_{t}$. In contrast,
DP-SGD performs each update step with a perturbed gradient,
$\tilde{\mathbf{g}}_{t}$. The perturbation of the true gradient follows two
distinct steps. Firstly, the gradient norm of $\mathbf{g}_{t}$ is clipped to
have maximum norm $C$, with
$\hat{\mathbf{g}}_{t}=\frac{\mathbf{g}_{t}}{\text{max}(1,\frac{\lVert\mathbf{g}_{t}\rVert_{2}}{C})}$.
Then Gaussian noise with scale $\sigma$ is added where $\sigma$ is determined
by the required privacy guarantee $\epsilon$, with
$\tilde{\mathbf{g}}_{t}=\hat{\mathbf{g}}_{t}+\mathcal{N}(0,C\sigma^{2}\mathbb{I})$.
Finally, the update is performed:
$\theta_{t+1}=\theta_{t}-\eta\tilde{\mathbf{g}}_{t}$.

###  2.2 Linear mode connectivity

Loss basins that contain different models (say, $\theta_{0}$ and $\theta_{1}$)
can be compared using a technique called Linear Mode Connectivity (Frankle et
al.,, 2020). In this technique, the loss values are computed for convex
combinations of the two models: $(1-\alpha)*\theta_{0}+\alpha\theta_{1}$ for
$\alpha\in[0,1]$, that lie along the linear segment joining the two models. In
practice losses are computed at discrete points, usually $30$ (Frankle et
al.,, 2020). Figure 3 shows the typical such linear mode loss profile for two
SGD models. The differences in initialization and inherent randomness in SGD
data processing can cause the models to end in different basins with higher
loss in between, as seen. It has been shown by (Garipov et al.,, 2018) that
the loss basins may be connected via non-linear paths. The linear mode
connectivity technique is best suited to find models that are in the same
linearly connected (convex) parts of a basin – where the loss profile at all
interpolated points are below some threshold above the loss at the end points,
that is, there is no pronounced peak of loss in between the models. The height
of this peak loss relative to the loss at the end points is called the
instability of the training process. More formally, suppose
$\mathcal{E}(\theta)$ is the training or test loss for model $\theta$ and
$\mathcal{E}_{\alpha}(\theta_{0},\theta_{1})=\mathcal{E}((1-\alpha)\theta_{0}+\alpha\theta_{1})$
for $\alpha\in[0,1]$ is the loss for a convex combination of the two models .

######  Definition 2.3 (Linear Interpolation Instability).

Let
$\mathcal{E}_{sup}(\theta_{0},\theta_{1})=\sup_{\alpha}\mathcal{E}_{\alpha}(\theta_{0},\theta_{1})$
be the highest loss attained while interpolating between models $\theta_{0}$
and $\theta_{1}$ with $\alpha\in[0,1]$. Let
$\bar{\mathcal{E}}_{\alpha}(\theta_{0},\theta_{1})=\text{Mean}(\mathcal{E}(\theta_{0}),\mathcal{E}(\theta_{1}))$
represent the mean loss of these models. Then the linear interpolation
instability is given by
$\mathcal{E}_{sup}(\theta_{0},\theta_{1})-\bar{\mathcal{E}}_{\alpha}(\theta_{0},\theta_{1})$.

High values of instability caused by a peak as in Figure 3, imply that the
models do not both lie on the floor of the same local basin.

##  3 THEORETICAL ANALYSIS

In this section, we quantify the effect of clipping in gradient descent and
show an example setting where pruning helps reduce this effect.

###  3.1 Measuring the effect of clipping

One possible way to analyse the change in the gradient step caused due to
clipping is to measure the change in direction compared to the true gradient.
Intuitively, if the direction doesn’t change too much, it can be thought of as
taking a smaller step compared to the true gradient in a similar direction. To
this end, we observe that the projection of the clipped gradient onto the true
gradient can be lower bounded by a quantity which depends on the variance of
each dimension over data points and gradient norm. We denote it by $R$ which
is defined below.

######  Definition 3.1.

Let $\mathcal{G}=\\{\bm{g}^{(i)}\\}_{i=1}^{n}$ be per example gradients, with
mean $\bar{\bm{g}}=\frac{1}{n}\sum\bm{g}^{(i)}$. Then define

$\displaystyle
R=\frac{\operatorname{Tr}(Cov(\mathcal{G}))}{\left\lVert\bar{\bm{g}}\right\rVert^{2}}=\frac{\frac{1}{n}\sum\left\lVert\bm{g}^{(i)}-\bar{\bm{g}}\right\rVert^{2}}{\left\lVert\bar{\bm{g}}\right\rVert^{2}}$
(1)

Consider the gradients $\bm{g}^{(i)}$ from 3.1. The clipped gradient $\bm{c}$
with clipping norm $C$ is the mean of per example clipped gradients i.e.,

$\displaystyle\bm{\tilde{g}}^{(i)}$
$\displaystyle=\bm{g}^{(i)}\cdot\min\left(1,\frac{C}{\left\lVert\bm{g}^{(i)}\right\rVert}\right)$
(2) $\displaystyle\bm{c}$ $\displaystyle=\frac{1}{n}\sum\bm{\tilde{g}}^{(i)}$
(3)

However, to simplify the analysis and based on the empirical observation that
most per-example gradients are larger than the clipping norm throughout the
training in the standard noise settings of DP-SGD, we make the assumption that
$C\leqslant\left\lVert\bm{g}^{(i)}\right\rVert$ for every $i$. This simplifies
$\bm{c}$ to

$\bm{c}=\frac{C}{n}\sum\frac{\bm{g}^{(i)}}{\left\lVert\bm{g}^{(i)}\right\rVert}$
(4)

######  Theorem 3.2.

Assume that $\bar{\bm{g}}\neq 0$ and $\bm{g}^{(i)}\neq 0$ for all $i=1,\dots
n$. Let the clipped gradient with clipping norm $C$ be as above and $R$ from
3.1.

Then

$\displaystyle\bm{c}\cdot\frac{\bar{\bm{g}}}{\left\lVert\bar{\bm{g}}\right\rVert}\geq
C\left(1-\frac{R}{2}\right)$ (5)

From 3.2 we can observe that the smaller the ratio $R$, the more aligned the
accumulated clipped gradient is with the actual direction.

###  3.2 Pruning to improve DPSGD

We construct a theoretical example in which performing pruning clips non-
important weights, so that the true target function can still be learned by
the pruned model. Later, we confirm empirically that in this scenario pruning
reduces $R$, thereby minimizing the effect of clipping from DP-SGD.

Formally, we consider a binary classification dataset $\mathcal{D}$, where
each example $\bm{x}^{(i)}$ is a vector in $\mathbbm{R}^{d},d=d_{s}+d_{n}$,
which consists of a signal part and a noise part. The signal part contains a
key vector $\bm{v}$ which determines the label plus Gaussian noise. The noise
part consists of only Gaussian noise. The labels $y^{(i)}$ are drawn from
$\\{-1,1\\}$.

$\displaystyle\bm{x}^{(i)}$
$\displaystyle=(\bm{x}_{s}^{(i)},\bm{x}_{n}^{(i)})$ (6)
$\displaystyle\bm{x}_{s}^{(i)}$
$\displaystyle\in\mathbbm{R}^{d_{s}},\bm{x}_{n}^{(i)}\in\mathbbm{R}^{d_{n}}$
(7) $\displaystyle\bm{x}_{s}^{(i)}$
$\displaystyle\sim\mathcal{N}(y_{i}\bm{v},\sigma^{2}\bm{I}_{d_{s}})$ (8)
$\displaystyle\bm{x}_{n}^{(i)}$
$\displaystyle\sim\mathcal{N}(0,\sigma^{2}\bm{I}_{d_{n}})$ (9)

For simplicity we will consider training on the entire population, but similar
results can be obtained for training on a sufficiently large sample using
standard concentration inequalities.

Consider training a two layer linear model with hidden layer of size $m$

$\displaystyle f(\bm{x})=\bm{W}_{2}\bm{W}_{1}\bm{x},$ (10)
$\displaystyle\bm{W}_{2}\in\mathbbm{R}^{1\times
m},\bm{W}_{1}\in\mathbbm{R}^{m\times d}$ (11)

to minimize the mean squared error

$\displaystyle\mathcal{L}=\mathbbm{E}_{(\bm{x},y)\sim\mathcal{D}}\left[\frac{1}{2}\|f(\bm{x}^{(i)})-\bm{y}^{(i)}\|^{2}\right]$
(12)

To aid in our analysis, we decompose

$\displaystyle\bm{W}_{1}=\begin{pmatrix}\bm{W}_{s}&\bm{W}_{n}\end{pmatrix}$
(13) $\displaystyle\bm{W}_{s}\in\mathbbm{R}^{m\times
d_{s}},\bm{W}_{n}\in\mathbbm{R}^{m\times d_{n}}$ (14)

Intuitively, $\bm{W}_{s}$ consists of connections to the signal part of the
input and $\bm{W}_{n}$ consists of connections to the noise part of the input
which correspond to non-important weights with regards to pruning.

We will consider clipping the first layer, as clipping the second layer is
similar to reducing the dimension of the hidden layer $m$.

Under this setting, we obtain the following

######  Theorem 3.3.

Suppose that at initialization the following holds:
$\bm{W}_{2}^{\top}\bm{W}_{2}=\bm{W}_{1}\bm{W}_{1}^{\top}$. Further assume that
we train using gradient flow and converge to a global minimum. Then at this
point

$\displaystyle\bm{W}_{n}=\bm{0}$ (15)

The initialization assumption has been used in previous theoretical works
((Arora et al.,, 2018)). Moreover, the convergence to a global minima is not
restrictive as it has been shown that for linear networks all local minima are
global minima ((Kawaguchi,, 2016)).

In general, this Theorem 3.3 shows that the weights in $\bm{W}_{n}$ are
expected to be small, hence will be clipped by magnitude pruning.

##  4 EXPERIMENTS

In this section we provide empirical evidence for the hypothesized behavior
and weaknesses of DP-SGD as discussed above. We also empirically demonstrate
the benefits of pruning.

Datasets and Models.  All experiments in this section use the publicly
available CIFAR10 and CIFAR100 datasets (Krizhevsky et al.,, 2009) using a
Resnet18 model architecture (He et al.,, 2016). For DP-SGD, the Opacus library
(Yousefpour et al.,, 2021) was used to replace batch normalization layers with
group normalization layers, as is required to maintain privacy guarantees.
Experiments were also performed on the LeNet (CNN) (LeCun et al.,, 1998)
architecture to illustrate that behaviors persist across drastically different
model sizes ($\approx 11$ million parameters for Resnet18 vs $\approx 50,000$
for LeNet). Please see the Appendix for further experiments.

Training.  Models trained via SGD used batch size 128 and learning rate 0.1
without momentum or data augmentation. Models trained with DP-SGD used batch
size 1024 and learning rate 0.5. All models were trained using cross entroy
loss on NVIDIA RT2080Ti 11GB GPUs. Reported results are averaged over 3-5
training runs of 30 epochs. All DP-SGD guarantees are for $\delta=1\times
10^{-5}$. See the Appendix for detailed descriptions of hyperparameter
choices.

Pruning.  Magnitude pruning was used to prune each network. Given the
initialization point of the model to be pruned, this model was then trained
for 20 epochs using the pre-training datasets outlined in Figure 13. For
pruning level $p\in[0,1]$, the smallest $(1-p)$ proportion of weights by
magnitude were pruned in each layer. The remaining weights were reset to their
initialization values.

###  4.1 Properties of DP-SGD, SGD and Loss basins in high dimensional spaces

####  4.1.1 Importance of early Vs late epochs

To test the conjecture in (Ganesh et al.,, 2023) that the poor performance of
DP-SGD arises in the early stages of optimization, we divide the
training/optimization process into Phase 1 ($k$ epochs) and Phase 2 ($T-k$
epochs). Two models are trained using SGD and DP-SGD for Phase 1, and then
separate copies of each are trained with SGD and DP-SGD for Phase 2.

Figure 2(a) demonstrates the loss results for the CNN model. Clearly, the
losses are determined by the mode of operation in Phase 2. The two Phase 2
sequences that use SGD converge rapidly to similar losses, while the SGD-DPSGD
sequence has its loss increase to appear at a similar level as the DPSGD-DPSGD
sequence. Corresponding test accuracy are shown in Figure 2(b), and results
for Resnet18 (Figure 2 c) and d)) show analogous patterns. These results show
that contrary to the suggestion in (Ganesh et al.,, 2023), the early phases
are not entirely decisive, and the inability to find a good solution even in a
good basin is a major weak point of DP-SGD.

|
---|---
a) Train. Loss(CNN) | b) Test Acc.(CNN)
|
c) Train. Loss(Resnet18) | d) Test Acc.(Resnet18)
Figure 2: Performance with different Phase 1 and Phase 2 training methods.
Later training epochs determine the final performance of both models for
CIFAR10. DP-SGD used noise multiplier $\sigma=0.55$ and maximum gradient norm
$C=1.0$ in each epoch, with $\epsilon\approx 7$ after training. $k=15$ for CNN
and $k=3$ for Resnet18.

####  4.1.2 Loss basin dimensions

By carrying out multiple runs of SGD we identify many basin locations with
equal levels of loss at the basin floor. Figure 3 shows that the linear mode
interpolations between different SGD solutions contain a large barrier in
between, suggesting that these are different loss basins, or parts of basins
not linearly connected. The basin floors are at equally low loss levels,
implying that there are many good solutions and initialization is not
decisive.

To further evaluate the shape of the basins, we carried out experiments where
two different models ($\theta_{0},\theta_{1}$) were trained in Phase 2
starting from the same Phase 1 model with $k=5$. The linear mode interpolation
profile between $\theta_{0}$ and $\theta_{1}$ shows an almost flat line,
showing that the basin floor is almost flat (Figure 4). On the other hand, the
interpolation in a random direction starting from $\theta_{0}$ shows the loss
to rise rapidly. This was observed consistently on 100 random directions,
where the maximum cosine similarity between the directions was $0.0012$,
implying that the directions are mainly orthogonal, as expected when sampling
random vectors in high dimensions.

This observation implies that the loss basin floor containing $\theta_{0}$ and
$\theta_{1}$ is low dimensional compared to the ambient dimension (number of
parameters). Any random vector – such as the noise vector generated by DP-SGD
– from a model on the basin floor will take the process along a path of steep
rise in loss. Note that the dimension of the loss basin itself is not critical
to this observation, as long as a number of directions exist where loss
increases rapidly.

Figure 3: SGD models with different initialization have similar losses
($\theta_{0}$ at interpolation=0 and $\theta_{1}$ at interpolation=1) but are
not linear mode connected, implying that they are in different basins, or
different regions of a non-convex basin. Figure 4: Comparison of the linear
mode interpolation profiles of models $\theta_{0},\theta_{1}$ in the same
linearly connected basin at distance of 15 units, with a model obtained by
moving from $\theta_{0}$ 15 units along a random vector in the ambient space.
Evaluated with $100$ random vectors, with maximum cosine similarity of 0.0012.
In random directions, loss increases rapidly.

####  4.1.3 Comparison of SGD and DP-SGD solutions with linear mode
interpolations

The linear interpolation instability for pairs of SGD models trained from the
same Phase 1 model (for varying $k$) is shown in Figure 5(a). Clearly, SGD
finds its basin early. However, DP-SGD shows high values of instability,
implying that two runs of DP-SGD almost never end in the same linear basin,
except perhaps for high values of both $k$ and $\epsilon$. When the two models
are trained by SGD and DP-SGD respectively in Phase 2, the differences in loss
profile can be seen in Figure 6 – suggesting that the two models do not end in
the same basin unless $\epsilon$ and $k$ are large. The corresponding results
where Phase 1 uses DP-SGD are shown in Figure7 In this case, since the
starting point is at a high loss and far from the basin floor, the Phase 2 DP-
SGD always ends in a different basin.

In fact, as shown in Figure 8, If we interpolate the Phase 1 model with Phase
2 model, we see that in all cases, DP-SGD does not stay in the same basin as
in Phase 1 ($k=10$), and always ends at a different basin.

|
---|---
a) SGD | b) DP-SGD ($\epsilon$=1)
|
c) DP-SGD ($\epsilon$=5) | d) DP-SGD ($\epsilon$=50)
Figure 5: SGD and DP-SGD Instability. Linear interpolation stability is shown using 30 values of $\alpha$ between two models trained with different copies after Phase 1. Higher y-values represent less linear mode stability. |
---|---
a) k=20 | b) $\epsilon=5$
Figure 6: Linear model interpolation between models $\theta_{0}$ trained for 20 epochs with SGD in Phase 2 and $\theta_{1}$ trained for 20 epochs with DP-SGD in Phase 2. Phase 1 was trained with SGD. |
---|---
a) k=20 | b) $\epsilon=5$
Figure 7: Linear mode interpolation. $\theta_{0}$ trained for 20 epochs with SGD in Phase 2, and $\theta_{1}$ trained for 20 epochs with DP-SGD in Phase 2. Phase 1 trained with DP-SGD. |
---|---
a) P1: DPSGD; P2: SGD | b) P1 & 2: DP-SGD
|
c) P1 & 2: SGD | d) P1: SGD; P2: DPSGD
Figure 8: Linear mode interpolation. $\theta_{0}$ is model at end of Phase 1;
$\theta_{1}$ is model at end of phase 2. SGD Phase 1 followed by also SGD
Phase 2 is the only setting where the model clearly stays on the same
optimization basin.

####  4.1.4 Comparing Noise and Clipping

We now examine the effects of clipping and noise separately, observing that
noise alone does not degrade model performance as larger gradients can be used
to recover the unwanted deviations, whereas clipping impacts model performance
by slowing progress. The combination of both clipping and noise in DP-SGD is
the worst case scenario, where clipping inhibits recovery from the
perturbation created by noise.

In Figure 9, we observe the loss and gradient norm for clipped SGD, noisy SGD,
DP-SGD and SGD, both at model initialization and later in model training. For
a fixed training batch $B$, we take $t=5$ steps with clipping set to $C=1.0$,
learning rate $0.1$, batch size $128$ and a noise scale of $0.4$. The mean and
average values over batches of size $128$ is reported. At initialization in
Figure 9 a), SGD achieves the lowest loss. Both clipping and noise reduce loss
improvement, but DP-SGD has significantly worse performance than any other
method. The gradient norms in Figure 9 b) shed light on this, with low noisy
and DP-SGD gradient norms suggesting that these methods have not located a
basin to optimize within quickly.

|
---|---
a) Loss | b) Gradient Norm
|
c) Loss | d) Gradient Norm
Figure 9: Training loss and gradient norms after 5 training steps with a fixed
training batch of size 128. The value before training is shown by the red
dashed line. The top row starts training from initialization, the bottom row
begins training from a model that has been trained for 10 epochs with SGD.

When we instead begin from a model pre-trained for 10 epochs with SGD, Figure
9 c) shows similar loss trends to an untrained model, but the gradient norm
behavior in Figure 9 d) differs. In this case, the gradient norm is largest
for DP-SGD and the clipped model, with all variants having a larger gradient
norm than SGD. This suggests that clipping as well as noise contributes to
gradient norm increases over training, and therefore increased distortion of
the true gradient at each step. See the Appendix for a comparison of gradient
norms throughout training for DP-SGD vs SGD, the larger gradient norms
observed in Figure 9 persist.

Figure 10 shows the accuracy of clipping with maximum gradient norm $1.0$ and
noise addition with scale $2.4$, settings equivalent to those for DP-SGD with
$\epsilon=1$. If we directly compare the effects of noise and clipping for a
given learning rate, batch size and number of epochs, then clipping
significantly impacts training performance by slowing progress when gradient
norms increase after the first few epochs, whereas noisy SGD attains the same
final test accuracy as SGD. This further supports the idea that clipping plays
a significant role in preventing DP-SGD from recovering from the required
noise addition that would otherwise not be detrimental to performance.

|
---|---
a) Noisy SGD | b) Clipped SGD
Figure 10: Noisy-SGD Accuracy test accuracy comparison with $\sigma=2.4$ and
Clipped-SGD with maximum gradient norm $1.0$ for Resnet18 with Cifar10.

###  4.2 Pruning

Given the hypothesized benefits of pruning in both reducing the random noise
added during DP-SGD training and reducing the impact of clipping, we now test
these hypotheses empirically. In Figure 11 we confirm that in the setting
described in Section 3.2, pruning reduces the ratio $R$, better aligning the
clipped gradient with the original gradient direction.

Figure 11: Ratio $R$ reduced by pruning.

This behavior is further evidenced in Figure 12 a) which demonstrates how
pruning alleviates the reduction in accuracy caused by clipping SGD for
Resnet18, even when there is no noise present. In contrast, Figure 12 b) shows
that pruning can help the network to train faster for noisy SGD on Resnet18
but not attain higher test accuracy, note that pruning also helps SGD without
noise train more quickly and therefore this behavior is not unique to noisy
SGD.

|
---|---
a) | b)
Figure 12: a) Clipped-SGD Test Accuracy comparison with $C=1.0$ for Resnet18 with Cifar10 pre-training. This clipping scale corresponds to the maximum gradient norm used for $\epsilon=1$ and $\epsilon=2$ experiments. b) Noisy-SGD Accuracy comparison with $\sigma=2.4$. This noise scale corresponds to the noise level for $\epsilon=1$. Training accuracy plots show the same trends. |
---|---
a) | b)
|
c) | d)
|
e) | f)
Figure 13: DP-SGD Test Accuracy comparison with $\epsilon=1$ for Resnet18. Top
row: magnitude pruning via non-private Cifar10 Phase 1. Middle row: magnitude
pruning via non-private Cifar10 using 5$\%$ of Cifar10. Bottom row: magnitude
pruning via Cifar100.

Given, these results, the dramatic improvement in test accuracy for DP-SGD
with pruning shown Figure 13is unsurprising, demonstrating that pruning
increases DP-SGD accuracy, with the same trend as Figure 11 where 0.7 pruning
has the strongest performance. The large improvement of around $23\%$ seen in
Figure 13 a) and b) using non-private pruning implies that if pruning can be
effectively implemented in a privacy preserving manner the benefits of pruning
can be significant. Figure 13 e) and f) shows an example of how to achieve
this, by pruning using Cifar100. See (Luo et al.,, 2021) for further evidence
of the potential test accuracy benefits of pruning for DP-SGD test accuracy.
Another notable aspect addressed by pruning is that of DP-SGD trained models
residing significantly further from the origin than SGD models (e.g.
$1.7\times$). In the Appendix we see that pruning reduces this difference,
with parameter distributions for pruned DP-SGD models more closely replicating
those of SGD models. See the Appendix for further results, including ablation
studies.

##  5 RELATED WORKS

Since its initial proposal, Differentially Private Stochastic Gradient Descent
has been studied for its convergence properties (Abadi et al.,, 2016; Bassily
et al.,, 2014). More recent theoretical works have studied clipping for its
impact on convergence (Xiao et al.,, 2023; Chen et al.,, 2020). Theoretical
approaches of sparsifying gradients to improve the performance of DPSGD have
been developed, where sparsification is carried out individually for each
gradient at runtime (Zhou et al.,, 2021; Yu et al.,, 2021). In contrast to
gradient sparsification, pruning can be viewed as a one time pre-
sparsification of both the network and gradients. Pruning of the normalization
layers of Resnet has been found to improve performance of DPSGD (Luo et al.,,
2021).

In contrast to these works, we use mechanisms such as Linear mode connectivity
(Frankle et al.,, 2020) to study the loss basins and make fine grained
comparisons of DPSGD models with SGD models. We demonstrate the individual
impacts of clipping and noise and the low dimensionality of loss basins, and
provide theoretical justifications for pruning.

##  6 CONCLUSION

This paper has provided several new insights theoretically and experimentally
into the operation of DP-SGD. While it does not quite solve the problem of
training private models that are almost as good as non-private ones, the
insights from this research should help us to develop better private training
algorithms in future.

## References

  * Abadi et al., (2016) 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, pages 308–318.
  * Arora et al., (2018) Arora, S., Cohen, N., and Hazan, E. (2018).  On the optimization of deep networks: Implicit acceleration by overparameterization.  In International Conference on Machine Learning, pages 244–253. PMLR.
  * Bassily et al., (2014) 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, pages 464–473. IEEE.
  * Carlini et al., (2019) Carlini, N., Liu, C., Erlingsson, Ú., Kos, J., and Song, D. (2019).  The secret sharer: Evaluating and testing unintended memorization in neural networks.  In 28th USENIX Security Symposium (USENIX Security 19), pages 267–284.
  * Chen et al., (2020) 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, (2006) Dwork, C. (2006).  Differential privacy.  In Automata, Languages and Programming, pages 1–12. ICALP.
  * Dwork et al., (2006) Dwork, C., McSherry, F., Nissim, K., and Smith, A. (2006).  Calibrating noise to sensitivity in private data analysis.  In Theory of Cryptography: Third Theory of Cryptography Conference, TCC 2006, New York, NY, USA, March 4-7, 2006. Proceedings 3, pages 265–284. Springer.
  * Frankle et al., (2020) Frankle, J., Dziugaite, G. K., Roy, D., and Carbin, M. (2020).  Linear mode connectivity and the lottery ticket hypothesis.  In International Conference on Machine Learning, pages 3259–3269. PMLR.
  * Fredrikson et al., (2015) Fredrikson, M., Jha, S., and Ristenpart, T. (2015).  Model inversion attacks that exploit confidence information and basic countermeasures.  In Proceedings of the 22nd ACM SIGSAC conference on computer and communications security, pages 1322–1333.
  * Ganesh et al., (2023) Ganesh, A., Haghifam, M., Nasr, M., Oh, S., Steinke, T., Thakkar, O., Thakurta, A. G., and Wang, L. (2023).  Why is public pretraining necessary for private model training?  In International Conference on Machine Learning, pages 10611–10627. PMLR.
  * Garipov et al., (2018) Garipov, T., Izmailov, P., Podoprikhin, D., Vetrov, D. P., and Wilson, A. G. (2018).  Loss surfaces, mode connectivity, and fast ensembling of dnns.  Advances in neural information processing systems, 31.
  * He et al., (2016) He, K., Zhang, X., Ren, S., and Sun, J. (2016).  Deep residual learning for image recognition.  In Proceedings of the IEEE conference on computer vision and pattern recognition, pages 770–778.
  * Kawaguchi, (2016) Kawaguchi, K. (2016).  Deep learning without poor local minima.
  * Krizhevsky et al., (2009) Krizhevsky, A., Hinton, G., et al. (2009).  Learning multiple layers of features from tiny images.
  * LeCun et al., (1998) 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.
  * Li et al., (2022) Li, X., Liu, D., Hashimoto, T. B., Inan, H. A., Kulkarni, J., Lee, Y.-T., and Guha Thakurta, A. (2022).  When does differentially private learning not suffer in high dimensions?  Advances in Neural Information Processing Systems, 35:28616–28630.
  * Luo et al., (2021) Luo, Z., Wu, D. J., Adeli, E., and Fei-Fei, L. (2021).  Scalable differential privacy with sparse network finetuning.  In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pages 5059–5068.
  * Nasr et al., (2019) Nasr, M., Shokri, R., and Houmansadr, A. (2019).  Comprehensive privacy analysis of deep learning: Passive and active white-box inference attacks against centralized and federated learning.  In 2019 IEEE symposium on security and privacy (SP), pages 739–753. IEEE.
  * Papernot et al., (2021) Papernot, N., Thakurta, A., Song, S., Chien, S., and Erlingsson, Ú. (2021).  Tempered sigmoid activations for deep learning with differential privacy.  In Proceedings of the AAAI Conference on Artificial Intelligence, volume 35, pages 9312–9321.
  * Shokri et al., (2017) Shokri, R., Stronati, M., Song, C., and Shmatikov, V. (2017).  Membership inference attacks against machine learning models.  In 2017 IEEE symposium on security and privacy (SP), pages 3–18. IEEE.
  * Xiao et al., (2017) Xiao, H., Rasul, K., and Vollgraf, R. (2017).  Fashion-mnist: a novel image dataset for benchmarking machine learning algorithms.  CoRR, abs/1708.07747.
  * Xiao et al., (2023) Xiao, H., Xiang, Z., Wang, D., and Devadas, S. (2023).  A theory to instruct differentially-private learning via clipping bias reduction.  In 2023 IEEE Symposium on Security and Privacy (SP), pages 2170–2189. IEEE Computer Society.
  * Yousefpour et al., (2021) Yousefpour, A., Shilov, I., Sablayrolles, A., Testuggine, D., Prasad, K., Malek, M., Nguyen, J., Ghosh, S., Bharadwaj, A., Zhao, J., et al. (2021).  Opacus: User-friendly differential privacy library in pytorch.  arXiv preprint arXiv:2109.12298.
  * Yu et al., (2021) Yu, D., Zhang, H., Chen, W., and Liu, T.-Y. (2021).  Do not let privacy overbill utility: Gradient embedding perturbation for private learning.  In International Conference on Learning Representations.
  * Zhou et al., (2021) Zhou, Y., Wu, S., and Banerjee, A. (2021).  Bypassing the ambient dimension: Private {sgd} with gradient subspace identification.  In International Conference on Learning Representations.

##  7 Appendix

###### Proof of Theorem 3.2.

Decompose
$\bm{g}_{i}=a_{i}\frac{\bar{\bm{g}}}{\|\bar{\bm{g}}\|}+b_{i}\bm{u}_{i}$, where
$\bm{u}_{i}$ is a unit vector orthogonal to $\bar{\bm{g}}$. Then the desired
inequality becomes

$\displaystyle\frac{1}{n}\sum_{i=1}^{n}\frac{a_{i}}{\sqrt{a_{i}^{2}+b_{i}^{2}}}\geq
1-\frac{\frac{1}{n}\sum_{i=1}^{n}a_{i}^{2}+b_{i}^{2}-\bar{a}^{2}}{2\bar{a}^{2}}$
(16)

where $\bar{a}$ is shorthand for $\frac{1}{n}\sum_{i=1}^{n}a_{i}$, and we know
$\bar{a}>0$.

Define the function $f$ by

$\displaystyle f(a_{1},\dots,a_{n},b_{1},\dots,b_{n})$
$\displaystyle=\frac{2}{n}\sum_{i=1}^{n}\frac{a_{i}}{\sqrt{a_{i}^{2}+b_{i}^{2}}}+\frac{1}{n\bar{a}^{2}}\left(\sum_{i=1}^{n}a_{i}^{2}+b_{i}^{2}\right)$
(17)

For any $0<\alpha<3\alpha<\beta,0<\gamma$, let
$J_{\alpha}=\\{(a_{1},\dots,a_{n},b_{1},\dots,b_{n})\in\mathbbm{R}^{2n}:\bar{a}\geq\alpha\\}$
and let
$I_{\alpha,\beta,\gamma}=J_{\alpha}\cap\left(([-\beta,-\alpha]\cup[\alpha,\beta])^{n}\times[-\gamma,\gamma]^{n}\right)$.
We claim that $f\geq 3$ on $I_{\alpha,\beta,\gamma}$. Since
$I_{\alpha,\beta,\gamma}$ is compact, $f$ has a minimum on
$I_{\alpha,\beta,\gamma}$. It suffices to consider the critical points $f$ and
the boundary of $I_{\alpha,\beta,\gamma}$.

We first find the critical points of $f$. For such critical points, calculate
that

$\displaystyle\frac{\partial f}{\partial a_{j}}$
$\displaystyle=\frac{2}{n}\frac{b_{j}^{2}}{(a_{j}^{2}+b_{j}^{2})^{\frac{3}{2}}}+\frac{2a_{j}}{n\bar{a}^{2}}-\frac{2}{n^{2}\bar{a}^{3}}\left(\sum_{i=1}^{n}a_{i}^{2}+b_{i}^{2}\right)=0$
(18) $\displaystyle\frac{\partial f}{\partial b_{j}}$
$\displaystyle=-\frac{2}{n}\frac{a_{j}b_{j}}{(a_{j}^{2}+b_{j}^{2})^{\frac{3}{2}}}+\frac{2b_{j}}{n\bar{a}^{2}}=0\
$ (19)

Suppose that $b_{k_{1}}=b_{k_{2}}=0$ for some $k_{1},k_{2}$. Then we must have

$\displaystyle\frac{2a_{k_{1}}}{n\bar{a}^{2}}-\frac{2}{n^{2}\bar{a}^{3}}\left(\sum_{i=1}^{n}a_{i}^{2}+b_{i}^{2}\right)=\frac{2a_{k_{2}}}{n\bar{a}^{2}}-\frac{2}{n^{2}\bar{a}^{3}}\left(\sum_{i=1}^{n}a_{i}^{2}+b_{i}^{2}\right)$
(20)

which implies that $a_{k_{1}}=a_{k_{2}}=A_{1}$ for some constant $A_{1}$.

Suppose that for some $k,b_{k}\neq 0$. Then equation 19 implies that

$\bar{a}^{2}a_{k}=(a_{k}^{2}+b_{k}^{2})^{\frac{3}{2}}$ (21)

which also implies

$b_{k}^{2}=\bar{a}^{\frac{4}{3}}a_{k}^{\frac{2}{3}}-a_{k}^{2}$ (22)

Substituting into Equation 18,

$\displaystyle 0$
$\displaystyle=\frac{2}{n}\cdot\frac{\bar{a}^{\frac{4}{3}}a_{k}^{\frac{2}{3}}-a_{k}^{2}}{\bar{a}^{2}a_{k}}+\frac{2a_{k}}{n\bar{a}^{2}}-\frac{2}{n^{2}\bar{a}^{3}}\left(\sum_{i=1}^{n}a_{i}^{2}+b_{i}^{2}\right)$
(23)
$\displaystyle=\frac{2}{n\bar{a}^{2}}\left(\frac{\bar{a}^{\frac{4}{3}}a_{k}^{\frac{2}{3}}}{a_{k}}\right)-\frac{2}{n^{2}\bar{a}^{3}}\left(\sum_{i=1}^{n}a_{i}^{2}+b_{i}^{2}\right)$
(24)
$\displaystyle=\frac{2}{n\bar{a}^{\frac{2}{3}}a_{k}^{\frac{1}{3}}}-\frac{2}{n^{2}\bar{a}^{3}}\left(\sum_{i=1}^{n}a_{i}^{2}+b_{i}^{2}\right)$
(25)

It follows that for any $k_{1},k_{2}$ with $b_{k_{1}},b_{k_{2}}\neq 0$, we
must have $a_{k_{1}}=a_{k_{2}}=A_{2}$ for some constant $A_{2}$. Moreover, we
must have
$\frac{2}{n\bar{a}^{\frac{2}{3}}A_{2}^{\frac{1}{3}}}=\frac{2A_{1}}{n\bar{a}^{2}}$
which gives

$A_{1}^{3}A_{2}=\bar{a}^{4}$ (26)

Consider two cases. If all the $a_{i}$ are equal, then
$a_{i}=A_{1}=A_{2}=\bar{a}>0$, and also

$b_{i}^{2}=\bar{a}^{\frac{4}{3}}a_{i}^{\frac{2}{3}}-a_{i}^{2}=0,$ (27)

so $b_{i}=0$ for all $i$. One can check that $f$ at such a point is equal to
3.

Now suppose for the sake of contradiction not all the $a_{i}$ are equal. The
one of them, WLOG let it be $a_{1}$, satisfies $a_{1}>\bar{a}$. Then
$a_{1}\bar{a}^{2}<(a_{1}^{2}+b_{1}^{2})^{\frac{3}{2}}$, so the only way
Equation 19 is satisfied is if $b_{1}=0$. But then $a_{1}=A_{1}$. It follows
from Equation 26 $0<A_{2}<\bar{a}<A_{1}$.

Now let $n_{1}$ be the number of $a_{i}$ equal to $A_{1}$ and $A_{2}$. We must
have

$\displaystyle\bar{a}$
$\displaystyle=\frac{n_{1}}{n}A_{1}+(1-\frac{n_{1}}{n})A_{2}$ (28)
$\displaystyle=\frac{n_{1}}{n}A_{1}+(1-\frac{n_{1}}{n})\frac{\bar{a}^{4}}{A_{1}^{3}}$
(29)

Set $\lambda=\frac{A_{1}}{\bar{a}}>1$. Then

$\displaystyle 1$
$\displaystyle=\frac{n_{1}}{n}\lambda+(1-\frac{n_{1}}{n})\frac{1}{\lambda^{3}}$
(30) $\displaystyle(\lambda^{3}-1)$
$\displaystyle=(\lambda^{4}-1)\frac{n_{1}}{n}$ (31)
$\displaystyle\frac{n_{1}}{n}$
$\displaystyle=\frac{\lambda^{3}-1}{\lambda^{4}-1}$ (32)

Now evaluating $f$,

$\displaystyle f(a_{1},\dots,a_{n},b_{1},\dots,b_{n})$
$\displaystyle=\frac{2}{n}\left(n_{1}+n_{2}\frac{A_{2}}{A_{2}^{\frac{1}{3}}\bar{a}^{\frac{2}{3}}}\right)+\frac{1}{n\bar{a}^{2}}\left(n_{1}A_{1}^{2}+A_{2}^{\frac{2}{3}}\bar{a}^{\frac{4}{3}}\right)$
(33)
$\displaystyle=2\left(\frac{\lambda^{3}-1}{\lambda^{4}-1}+(1-\frac{\lambda^{3}-1}{\lambda^{4}-1})\frac{1}{\lambda^{2}}\right)+\left(\frac{\lambda^{3}-1}{\lambda^{4}-1}\lambda^{2}+(1-\frac{\lambda^{3}-1}{\lambda^{4}-1})\frac{1}{\lambda^{2}}\right)$
(34)

It is not hard to show that the RHS is greater than $3$ for $\lambda>1$. Thus
we have shown that $f\geq 3$ at all critical points.

It remains to check the boundary points. Notice that the dominant term in $f$
as $|b_{i}|\to\infty$ is $b_{i}^{2}$. Hence using sufficiently large $\gamma$
guarantees that no point with $b_{i}=\gamma$ for some $i$ can be a minimum. On
the other hand, suppose of the $a_{i}$ take a boundary value. We consider a
few cases:

Case 1: $a_{i}=-\beta$. If $b_{i}\neq 0$, then $\frac{\partial f}{\partial
b_{i}}\neq 0$, so we can adjust $b_{i}$ to decrease $f$. If $b_{i}=0$, then 18
shows that increasing $a_{i}$ will decrease the value of $f$.

Case 2: If the only boundary values are of the form $a_{i}=\pm\alpha$ observe
that $f$ is scale-invariant, so scaling all inputs by $1+\delta$ shows that
$f$ has the same value at some interior point of $I_{\alpha,\beta,\gamma}$,
which we already know is not a minimum or greater than 3.

Case 3: $a_{i}$ on the boundary are only of the form $a_{i}=\beta$. A similar
argument as the previous case but scaling down works.

Case 4: Some $a_{i}=\alpha$ and some $a_{j}=\beta$. But then from Equation 18
we see that $\frac{\partial f}{\partial a_{i}}<\frac{\partial f}{\partial
a_{j}}$, so either $\frac{\partial f}{\partial a_{i}}<0$ or $\frac{\partial
f}{\partial a_{j}}>0$. This means that either increasing $a_{i}$ or decreasing
$a_{j}$ decreases the value of $f$, so this cannot be a minimum.

Case 5: Some $a_{i}=-\alpha$ and some $a_{j}=\beta$. If $b_{i}\neq 0$ then
$\frac{\partial f}{\partial b_{i}}\neq 0$ by 19 and we can adjust $b_{i}$
appropriately to decrease $f$. A similar argument handles the case that
$b_{j}\neq 0$.

Suppose $b_{i}=b_{j}=0$. Set
$a_{i}^{\prime}=\alpha,a_{j}^{\prime}=\beta-2\alpha$. Then

$\displaystyle f(a_{1},\dots,a_{i}^{\prime},\dots,a_{j}^{\prime},\dots
a_{n},b_{1},\dots,b_{n})-f(a_{1},\dots,a_{n},b_{1},\dots b_{n})$
$\displaystyle=\frac{2}{n}(1-(-1))+\frac{1}{n\bar{a}^{2}}((\beta-2\alpha)^{2}-\beta^{2})$
(35)
$\displaystyle=\frac{4}{n}\left(1-\frac{\beta(\beta-\alpha)}{\bar{a}^{2}}\right)$
(36)

Taking $\beta>n\alpha$ guarantees that $\beta>\beta-\alpha>\bar{a}$, so for
$\beta$ sufficiently large the RHS is less than 0, showing that the original
point is not a minimum.

The final boundary condition is if $\bar{a}=\alpha$. We have already
considered the condition where any of the $a_{i}$ are equal to $\pm\alpha$, so
the only way this is possible if there exists some $i$ s.t. $a_{i}<-\alpha$.
If $b_{i}\neq 0$, we can decrease $|b_{i}|$ to decrease $f$ by 19. If
$b_{i}=0$, then 18 shows that increasing $\alpha_{i}$ will decrease the value
of $f$. Thus such a point cannot be a minimum. This proves that $f\geq 3$ on
$I_{\alpha,\beta,\gamma}$.

Now since $\alpha,\beta,\gamma$ work for any $\beta,\gamma$ sufficiently
large, we conclude that $f\geq 3$ on
$\\{(a_{1},\dots,a_{n},b_{1},\dots,b_{n})\in\mathbbm{R}^{2n}:\bar{a}>0\\}\cap((\mathbbm{R}\setminus\\{0\\})^{n}\times\mathbbm{R}^{n})$.
We can extend to the possibility that some of the $a_{i}$ are zero by
continuity. This completes the proof.

∎

###### Proof of 3.3.

Collect the input examples into a matrix $\bm{X}=[x^{(1},\dots,x^{(n)}]$ and
let $\bm{Z}=f(\bm{X})\in\mathbbm{R}^{1\times n}$ be the matrix of model
outputs on the dataset. Then the gradients are

$\displaystyle\frac{\partial\mathcal{L}}{\partial\bm{W}_{1}}$
$\displaystyle=\bm{W}_{2}^{\top}\frac{\partial\mathcal{L}}{\partial\bm{Z}}\bm{X}^{\top}$
$\displaystyle\frac{\partial\mathcal{L}}{\partial\bm{W}_{2}}$
$\displaystyle=\frac{\partial\mathcal{L}}{\partial\bm{Z}}\bm{X}^{\top}\bm{W}_{1}^{\top}$

In addition, observe that using the rule of gradient flow,

$\displaystyle\frac{d}{dt}(\bm{W}_{1}\bm{W}_{1}^{\top})$
$\displaystyle=\bm{W}_{1}\left(\frac{d\bm{W}_{1}}{\partial
t}\right)^{\top}+\frac{d\bm{W}_{1}}{\partial t}\bm{W}_{1}^{\top}$
$\displaystyle=-\bm{W}_{1}\left(\frac{\partial\mathcal{L}}{\partial\bm{W}_{1}}\right)^{\top}-\frac{\partial\mathcal{L}}{\partial\bm{W}_{1}}\bm{W}_{1}^{\top}$
$\displaystyle\frac{d}{dt}(\bm{W}_{2}^{\top}\bm{W}_{2})$
$\displaystyle=\bm{W}_{2}\left(\frac{d\bm{W}_{2}}{\partial
t}\right)^{\top}+\frac{d\bm{W}_{2}}{\partial t}\bm{W}_{2}^{\top}$
$\displaystyle=-\left(\frac{\partial\mathcal{L}}{\partial\bm{W}_{2}}\right)^{\top}\bm{W}_{2}-\bm{W}_{2}^{\top}\frac{\partial\mathcal{L}}{\partial\bm{W}_{2}}.$

Substituting, we see that
$\frac{d}{dt}(\bm{W}_{1}\bm{W}_{1}^{\top})=\frac{d}{dt}(\bm{W}_{2}^{\top}\bm{W}_{2})$.
Since we assumed that that
$\bm{W}_{1}\bm{W}_{1}^{\top}=\bm{W}_{2}^{\top}\bm{W}_{2}$, it follows that
equality holds throughout training.

Now the model is linear in $\bm{W}=\bm{W}_{2}\bm{W}_{1}$, so by well known
results on linear regression, the optimal model $\bm{W}_{2}^{*}\bm{W}_{1}^{*}$
on the entire dataset satisfies

$\displaystyle\bm{W}_{2}^{*}\bm{W}_{1}^{*}$
$\displaystyle=\mathbbm{E}_{\bm{x}\sim\mathcal{D}}[y\bm{x}^{\top}]\left(\mathbbm{E}_{\bm{x}\sim\mathcal{D}}[\bm{x}\bm{x}^{\top}]\right)^{\dagger}$
$\displaystyle=\bm{v}^{\top}(\bm{v}\bm{v}^{\top}+\sigma^{2}\bm{I})^{\dagger}$
$\displaystyle=\frac{\|\bm{v}\|}{\|\bm{v}\|^{2}+\sigma^{2}}\bm{v}^{\top}$

Combined with the fact that
$\bm{W}_{1}^{*}(\bm{W}_{1}^{*})^{\top}=(\bm{W}_{2}^{*})^{\top}\bm{W}_{2}^{*}$,
it follows that $\bm{W}_{1}^{*},\bm{W}_{2}^{*}$ are both rank 1 matrices with
singular value $\sqrt{\frac{\|\bm{v}\|}{(\|\bm{v}\|^{2}+\sigma^{2})}}$, and
the left singular vector of $\bm{W}_{1}$ corresponds to the right singular
vector of $\bm{W}_{2}$ In particular,

$\displaystyle\bm{W}_{1}^{*}$
$\displaystyle=\sqrt{\frac{1}{\|\bm{v}\|(\|\bm{v}\|^{2}+\sigma^{2})}}\bm{\alpha}\bm{v}^{\top}$
(37) $\displaystyle\bm{W}_{2}^{*}$
$\displaystyle=\sqrt{\frac{\|\bm{v}\|}{(\|\bm{v}\|^{2}+\sigma^{2})}}\bm{\alpha}^{\top}$
(38)

for some unit vector $\alpha\in\mathbbm{R}^{m}$. From this expression it is
easy to see that $\bm{W}_{n}^{*}=\bm{0}$. ∎

##  8 Experimental Details

We now outline further experimental results and provide further details about
experiments included in the main body of text.

Previous Experiment Details: In Figure 13 c), the Cifar100 Resnet18 model used
to prune the model was trained using SGD with data augmentation (horizontal
flipping and random cropping), momentum=0.9, learning rate 0.02 and batch size
512 for 100 epochs. For DP-SGD, unless $\sigma$ is explicitly stated, then
$\sigma$ has been calculated automatically by the Opacus package for the fixed
$\epsilon$ and $\delta$ values reported using the make_private_with_epsilon
function.

Additional Models and Datasets: In this section, in addition to Cifar10 and
Cifar100 as used previously, we also provide results using the MNIST (LeCun et
al.,, 1998) and FashionMNIST (Xiao et al.,, 2017) datasets. Table 1 shows
hyperparameters for SGD and DP-SGD variants of the model and dataset
combinations included in this Appendix. Hyperparameters described in Table 1
were selected via hyperparameter sweeps for DP-SGD and SGD with learning rates
$\\{0.01,0.05,0.1,0.5,1.0\\}$ and batch sizes $\\{32,64,128,512,1024\\}$.
Pruned variants were then trained using the same fixed hyperparameters.

Model | Dataset | SGD | DP-SGD
---|---|---|---
$\eta$ | Batch Size | $\eta$ | Batch Size
CNN (LeNet) | MNIST | 0.1 | 128 | 1.0 | 512
FashionMNIST | 0.1 | 64 | 0.5 | 512
Table 1: Hyperparameter choices for experiments included in this section

##  9 Further Experiments

Further results for Resnet18: Figures 14 demonstrates the performance of
pruning for Cifar10 and Resnet18 with $\epsilon=2$. As with $\epsilon=1$,
pruning using non-private pre-training on Cifar10 results in the highest final
test accuracy for DP-SGD with a pruning proportion of 0.7. As before, pruning
using Cifar100 or 5% of Cifar10 also improves the test accuracy of the model.

Pruning percentages: Figure 15 shows that for Cifar10 and Resnet18, increasing
the pruning proportion past 0.7 does not further improve performance.

|
---|---
a) | b)
|
c) | d)
|
e) | f)
Figure 14: DPSGD Test Accuracy comparison with $\epsilon=2$ for Resnet18 with Cifar10. a) and b) show pruning via non-private training with Cifar10 c) and d) show pruning via non-private training with 5$\%$ of Cifar10. e) and f) show pruning via training with Cifar100. |
---|---
Figure 15: Sweep over higher pruning percentages for Cifar10 and Resnet18.

Parameter and Gradient Norm Distributions: Gradient norms are larger during
training for DP-SGD in comparison to SGD, as seen in Figure 16. This will
result in more severe clipping of the gradient than would otherwise have been
necessary. Figure 17 shows that pruned DP-SGD models better replicate the
parameter distribution of SGD models. DP-SGD models have significantly fewer
parameters close to 0 than SGD models, their L2 distance from the origin is
correspondingly around $1.7\times$ larger. Pruning reduces this to $1.2\times$
larger.

((a))

((b))

((c))

Figure 16: Top row: Average gradient norm over training data batches of size 128 for SGD vs DP-SGD with Resnet18 and Cifar10. Bottom row: histogram comparisons of the gradient norms after 1 epoch of training (b) and 30 epochs of training (c). |
---|---
Figure 17: DP-SGD models for $\epsilon=1$ have fewer parameters closer to 0
than SGD models, implying again that they occupy different regions of the
parameter space. We find that SGD models have an L2 distance from the origin
of $86\pm 0.5$ in comparison to $142\pm 0.01$ for DP-SGD models. With pruning
the DP-SGD distance reduces to $100\pm 0.02$.

Other Models and Datasets: In Figures 18 and 19 we demonstrate that magnitude
pruning increases the test accuracy of DP-SGD for a significantly smaller
model (LeNet) using both the MNIST and FashionMNIST tasks.

Varying the Phase 1 Training Duration: In Figure 20, we provide examples of
different lengths of Phase 1 training ($k$) from Figure 2. In all cases we see
similar trends, with the DP-SGD model under-performing in comparison to SGD
during the first few epochs, but also negatively impacting model performance
later in training (Phase 2) when the model is initially trained with SGD.

|
---|---
Figure 18: Training and test accuracies for a CNN (LeNet) model with MNIST for $\epsilon=1$. Magnitude pruning performed via pre-training with MNIST.  |
---|---
Figure 19: Training and test accuracies for a CNN (LeNet) model with FashionMNIST for $\epsilon=1$. Magnitude pruning performed via pre-training with FashionMNIST.  |
---|---
a) $k=5$ | b) $k=5$
|
c) $k=25$ | d) $2k=5$
|
e) $k=50$ | f) $k=50$
Figure 20: Performance with different Phase 1 and Phase 2 training methods.
Later training epochs determine the final performance of both models for
CIFAR10. DP-SGD used noise multiplier $\sigma=0.55$ and maximum gradient norm
$C=1.0$ in each epoch, with $\epsilon\approx 7$ after training.


# Vaughan–Lee’s nilpotent loop of size $12$ is finitely based

Peter Mayr  Department of Mathematics, University of Colorado, Boulder,
Colorado, USA<EMAIL_ADDRESS>
(Date: March 2, 2022)

###### Abstract.

From work of Vaughan–Lee in [7] it follows that if a finite nilpotent loop
splits into a direct product of factors of prime power order, then its
equational theory has a finite basis. Whether the condition on the direct
decomposition is necessary has remained open since. In the same paper,
Vaughan–Lee gives an explicit example of a nilpotent loop of order $12$ that
does not factor into loops of prime power order and asks whether it is
finitely based.

We give a finite basis for his example by explicitly characterizing its term
functions. This also allows us to show that the subpower membership problem
for this loop can be solved in polynomial time.

###### Key words and phrases:

nilpotent Mal’cev algebra, finite basis problem, subpower membership problem

###### 2010 Mathematics Subject Classification:

08B05, 20N05, 08A40

This material is based upon work supported by the National Science Foundation
grant no. DMS 1500254

##  1\. Introduction

In [7] Vaughan–Lee showed that every finite nilpotent Mal’cev algebra of
finite type that has an equationally defined constant and splits into a direct
product of algebras or prime power order is finitely based. In [3] Freese and
McKenzie generalized this result by removing the assumption that the algebra
has a constant. Hence a finite nilpotent Mal’cev algebra ${\mathbf{A}}$ has a
finite basis for its equational theory if it satisfies one of the following
equivalent conditions for some $n\in{\mathbb{N}}$:

  1. (1)

${\mathbf{A}}$ is a direct product of algebras of prime power order;

  2. (2)

all _commutator terms_ on ${\mathbf{A}}$, i.e., term functions satisfying
$c(x_{1},\dots,x_{k},z)=z$ whenever $x_{i}=z$ for some $i\leq k$, have
essential arity at most $n+1$;

  3. (3)

${\mathbf{A}}$ is $n$-_supernilpotent_ , i.e., $[1_{A},\dots,1_{A}]=0_{A}$ for
the $(n+1)$-ary _higher commutator_.

The equivalence (1)$\Leftrightarrow$(2) follows from [5, Theorem 3.14] and
(1)$\Leftrightarrow$(3) from [1, Lemma 7.6].

Vaughan–Lee, Freese and McKenzie proved their finite basis results
syntactically by developing normal forms for terms with respect to commutator
terms and then making crucial use of the bounded arity of the latter. Since
their work in the 1980s, it remains open whether conditions (1)-(3) above are
necessary, that is:

######  Question 1.1.

Is every finite nilpotent Mal’cev algebra of finite type finitely based?

Unlike for groups, not every finite nilpotent Mal’cev algebra is isomorphic to
a direct product of algebras of prime power order. Already in [7] Vaughan–Lee
gave the following example of an indecomposable $12$-element nilpotent loop
$\mathbf{L}$ and asked whether it is finitely based.

For $x\in{\mathbb{Z}}_{12}$ and $C:=4{\mathbb{Z}}_{12}$, let $\bar{x}:=x+C$.
Define binary operations

$t\colon{\mathbb{Z}}_{12}^{2}\to C,(x,y)\mapsto\begin{cases}4&\text{if
}(x,y)\in\bar{1}\times\bar{3}\cup\bar{3}\times\bar{1},\\\
0&\text{else},\end{cases}$

and

$x\cdot y:=x+y+t(x,y)\quad\text{ for }x,y\in{\mathbb{Z}}_{12}.$

Then $\mathbf{L}:=\langle{{\mathbb{Z}}_{12}},{\cdot}\rangle$ is a commutative
$2$-nilpotent loop with center $C$. The congruences of $\mathbf{L}$ are
induced by the normal subloops $0,C,2{\mathbb{Z}}_{12},{\mathbb{Z}}_{12}$. In
particular $\mathbf{L}$ is subdirectly irreducible and does not split into a
direct product of loops of prime power orders. Consequently it is not
supernilpotent.

To the best of our knowledge there are no published results on the equational
bases for any nilpotent, not supernilpotent Mal’cev algebras. We present a
detailed analysis of Vaughan–Lee’s loop $\mathbf{L}$ as a test case and
starting point for a future, hopefully more systematic approach to Question
1.1.

First we note that $\mathbf{L}$ has the group
$\langle{{\mathbb{Z}}_{12}},{+}\rangle$ as reduct, and we explicitly
characterize its set of $k$-ary term functions $\mathrm{Clo}_{k}(\mathbf{L})$
for any $k\in{\mathbb{N}}$.

######  Theorem 1.2.

For $k\in{\mathbb{N}}$ let

$W_{k}:=\\{w\colon{\mathbb{Z}}_{12}^{k}\to C\ :\
w(2{\mathbb{Z}}_{12}^{k})=0,w(x)=w(-x)\text{ for all
}x\in{\mathbb{Z}}_{12}^{k}\\}.$

Then
$\mathrm{Clo}_{k}(\mathbf{L})=\mathrm{Clo}_{k}(\langle{{\mathbb{Z}}_{12}},{+}\rangle)\oplus
W_{k}$.

Here $\oplus$ denotes the direct sum in the group of all $k$-ary functions
$\langle{{\mathbb{Z}}_{12}},{+}\rangle^{{\mathbb{Z}}_{12}^{k}}$. The proof of
Theorem 1.2 makes up all of Section 2.

From Theorem 1.2 we obtain normal forms for term functions and terms on
$\mathbf{L}$ and eventually a finite basis in Section 4.

######  Theorem 1.3.

$\mathbf{L}$ is finitely based.

A description of the term clone as above also has computational applications.
The _Subpower Membership Problem_ $\mathrm{SMP}$ for an algebra ${\mathbf{A}}$
is the following decision problem:

| $\mathrm{SMP}({\mathbf{A}})$
---|---
|  Input: |  $a_{1},\ldots,a_{k},b\in A^{n}$
|  Problem: |  Is $b$ in the subalgebra $\langle a_{1},\ldots,a_{k}\rangle$ of ${\mathbf{A}}^{n}$ generated by $a_{1},\ldots,a_{k}$?

Willard observed that the Subpower Membership Problem for finite groups and
rings can be solved in polynomial time and asked whether it is in P for any
finite algebra with cube term (in particular, for every Mal’cev algebra) [4].
This question remains open in general but there are some partial results.
Together with Bulatov and Szendrei, the author showed that
$\mathrm{SMP}({\mathbf{A}})$ is in NP for every finite algebra ${\mathbf{A}}$
with a cube term [2]. In [6] we gave a polynomial time algorithm for
$\mathrm{SMP}$ for finite supernilpotent Mal’cev algebras using commutator
terms and the techniques developed by Vaughan–Lee, Freese and McKenzie for
their finite basis results. Like the answer for the finite basis question, we
do not know the computational complexity of subpower membership for nilpotent,
not supernilpotent Mal’cev algebras (even for loops) in general.

However, using the explicit description of term functions in Theorem 1.2, it
is not hard to reduce $\mathrm{SMP}$ for Vaughan–Lee’s loop $\mathbf{L}$ to
$\mathrm{SMP}$ of the group $\langle{{\mathbb{Z}}_{12}},{+}\rangle$. Hence we
obtain the following in Section 3:

######  Theorem 1.4.

$\mathrm{SMP}(\mathbf{L})$ is in $P$.

We mention without proof that similar but somewhat less involved arguments
show that all nilpotent loops of order $6$ or $10$ are finitely based and have
tractable $\mathrm{SMP}$ as well.

Our approach in this paper is tailored to the particular example we consider
and has obvious limitations. In general a full characterization of term
functions of arbitrary nilpotent Mal’cev algebras as in Theorem 1.2 may not be
feasible even when restricting the nilpotence degree. Furthermore, a
description of the term clone does not automatically yield a finite basis for
the algebra as we see from the proof of Theorem 1.3.

Still our admittedly limited evidence leads us to propose the following
problems as steps towards a possible positive solution of Question 1.1.

######  Question 1.5.

Does every finite nilpotent Mal’cev algebra have a supernilpotent reduct?

######  Question 1.6.

Is every nilpotent expansion of a finite abelian (more generally
supernilpotent) Mal’cev algebra finitely based?

For $n\in{\mathbb{N}}$, let $[n]:=\\{0,\dots,n-1\\}$.

##  2\. The clone of term operations (proof of Theorem 1.2)

We split the proof of Theorem 1.2 into several lemmas. First we show that
$\mathbf{L}$ has a group reduct.

######  Lemma 2.1.

$\mathbf{L}$ is term equivalent to $\langle{{\mathbb{Z}}_{12}},{+,t}\rangle$.

###### Proof.

Let $x,y\in{\mathbb{Z}}_{12}$. Note that $x^{2}=2x$ and consequently

$(xy)^{4}=4x+4y+t(x,y).$

Further $\cdot$ and $+$ are equal on $2{\mathbb{Z}}_{12}$ which yields

$(xy)^{4}\cdot x^{8}\cdot y^{8}=t(x,y).$

Hence $t$ is a term operation on $\mathbf{L}$ and the assertion follows. ∎

Note that $\mathrm{Clo}_{k}(\langle{{\mathbb{Z}}_{12}},{+}\rangle)$ and
$W_{k}$ are subgroups of ${\mathbb{Z}}_{12}^{{\mathbb{Z}}_{12}^{k}}$ by their
definitions. We claim that

(2.1) $\text{ the sum
}\mathrm{Clo}_{k}(\langle{{\mathbb{Z}}_{12}},{+}\rangle)+W_{k}\text{ is
direct}.$

Let $w\in\mathrm{Clo}_{k}(\langle{{\mathbb{Z}}_{12}},{+}\rangle)\cap W_{k}$.
Then $w(x)=\sum_{i=1}^{k}a_{i}x_{i}$ for some
$a_{1},\dots,a_{k}\in{\mathbb{Z}}$. Now $w({\mathbb{Z}}_{12}^{k})\subseteq C$
and $w(2{\mathbb{Z}}_{12}^{k})=0$ imply that all coefficients
$a_{1},\dots,a_{k}$ are multiples of $4$ and of $6$, hence of $12$. Thus $w=0$
and (2.1) is proved.

For

(2.2)
$\mathrm{Clo}_{k}(\mathbf{L})\subseteq\mathrm{Clo}_{k}(\langle{{\mathbb{Z}}_{12}},{+}\rangle)+W_{k},$

it suffices that
$\mathrm{Clo}_{k}(\langle{{\mathbb{Z}}_{12}},{+}\rangle)+W_{k}$ is closed
under $+$ and $t$. Only closure under $t$ remains to be shown. Note that for
any $a_{1},\dots,a_{k},b_{1},\dots,b_{k}\in{\mathbb{Z}}$ and $w,v\in W_{k}$,

$g(x):=t(\sum_{i=1}^{k}a_{i}x_{i}+w(x),\sum_{i=1}^{k}b_{i}x_{i}+v(x))=t(\sum_{i=1}^{k}a_{i}x_{i},\sum_{i=1}^{k}b_{i}x_{i})$

satisfies $g(2{\mathbb{Z}}_{12}^{k})=0$ and $g(x)=g(-x)$ for all
$x\in{\mathbb{Z}}_{12}^{k}$ by the definition of $t$. Hence $g\in W_{k}$ and
(2.2) follows.

The converse containment $\supseteq$ in Theorem 1.2 will follow from Lemma 2.4
after establishing some more auxiliary results. First note that $W_{k}$ forms
a vector space over the $3$-element field ${\mathbf{F}}_{3}$ of dimension
$(4^{k}-2^{k})/2$. To obtain normal forms for the functions in $W_{k}$ we
construct a basis of term functions.

######  Lemma 2.2.

Let $k\in{\mathbb{N}}$, and

$g_{k}\colon{\mathbb{Z}}_{12}^{k}\to C,\ x\mapsto\begin{cases}4&\text{if
}x_{1}\in 1+2{\mathbb{Z}}_{12},x_{2},\dots,x_{k}\in C,\\\
0&\text{else}.\end{cases}$

Then $g_{k}$ is a term operation of $\mathbf{L}$.

###### Proof.

We use induction on $k$. Note that $g_{1}(x)=t(x,-x)$ and
$g_{2}(x,y)=t(x,3x+y)$ are term operations of $\mathbf{L}$ by Lemma 2.1. So
assume $k\geq 3$ in the following. By induction assumption we have the term
function $h:=g_{k-1}$. We claim that

$\displaystyle g_{k}(x_{1},\dots,x_{k})=$
$\displaystyle\sum_{b\in[4]}h(x_{1},x_{2}+bx_{3},x_{4},\dots,x_{k})$
$\displaystyle+\sum_{a\in\\{0,2\\}}h(x_{1},ax_{2}+x_{3},x_{4}\dots,x_{k})$
$\displaystyle+\sum_{(a,b)\in\\{0,2\\}^{2}}h(x_{1},ax_{2}+bx_{3},x_{4},\dots,x_{k}).$

By definition the functions on either side of the equation are $0$ whenever
$x_{1}\in 2{\mathbb{Z}}_{12}$ or $x_{4},\dots,x_{k}\not\in C$. Further they
are constant for $x_{1}\in 1+2{\mathbb{Z}}_{12}$ and overall constant on
$C$-blocks. So it suffices to consider the graphs for the functions on the
right hand side of the equation for $x_{1}=1$ and $x_{4}=\dots=x_{k}=0$. We
give the second argument $ax_{2}+bx_{3}$ and the table for
$h(1,ax_{2}+bx_{3},0,\dots,0)$ on $C$-blocks where $x_{2}$ runs through the
representatives $0,2,1,3$ left to right and $x_{3}$ runs through $0,2,1,3$
bottom to top.

$\begin{array}[]{cccccc}x_{2}+0x_{3}&x_{2}+1x_{3}&x_{2}+2x_{3}&x_{2}+3x_{3}&0x_{2}+x_{3}&2x_{2}+x_{3}\\\
&\\\ \begin{smallmatrix}4&0&0&0\\\ 4&0&0&0\\\ 4&0&0&0\\\ 4&0&0&0\\\
\end{smallmatrix}&\begin{smallmatrix}0&0&4&0\\\ 0&0&0&4\\\ 0&4&0&0\\\
4&0&0&0\\\ \end{smallmatrix}&\begin{smallmatrix}0&4&0&0\\\ 0&4&0&0\\\
4&0&0&0\\\ 4&0&0&0\\\ \end{smallmatrix}&\begin{smallmatrix}0&0&0&4\\\
0&0&4&0\\\ 0&4&0&0\\\ 4&0&0&0\\\
\end{smallmatrix}&\begin{smallmatrix}0&0&0&0\\\ 0&0&0&0\\\ 0&0&0&0\\\
4&4&4&4\\\ \end{smallmatrix}&\begin{smallmatrix}0&0&0&0\\\ 0&0&0&0\\\
0&0&4&4\\\ 4&4&0&0\\\ \end{smallmatrix}\end{array}$

$\begin{array}[]{cccc}0x_{2}+0x_{3}&0x_{2}+2x_{3}&2x_{2}+0x_{3}&2x_{2}+2x_{3}\\\
&\\\ \begin{smallmatrix}4&4&4&4\\\ 4&4&4&4\\\ 4&4&4&4\\\ 4&4&4&4\\\
\end{smallmatrix}&\begin{smallmatrix}0&0&0&0\\\ 0&0&0&0\\\ 4&4&4&4\\\
4&4&4&4\\\ \end{smallmatrix}&\begin{smallmatrix}4&4&0&0\\\ 4&4&0&0\\\
4&4&0&0\\\ 4&4&0&0\\\ \end{smallmatrix}&\begin{smallmatrix}0&0&4&4\\\
0&0&4&4\\\ 4&4&0&0\\\ 4&4&0&0\\\ \end{smallmatrix}\end{array}$

Adding the tables in the first row yields

$\begin{smallmatrix}4&4&4&4\\\ 4&4&4&4\\\ 8&8&4&4\\\ 0&8&4&4\\\
\end{smallmatrix}$

and adding those in the second row yields

$\begin{smallmatrix}8&8&8&8\\\ 8&8&8&8\\\ 4&4&8&8\\\ 4&4&8&8\\\
\end{smallmatrix}$

Their sum is the table of $g_{k}(1,x_{2},x_{3},0,\dots,0)$,

$\begin{smallmatrix}0&0&0&0\\\ 0&0&0&0\\\ 0&0&0&0\\\ 4&0&0&0\\\
\end{smallmatrix}$

This proves that $g_{k}$ is a term function. ∎

To simplify the description of term functions on $\mathbf{L}$ we show that
$\mathbf{L}$ is term equivalent to the expansion of the group
$\langle{{\mathbb{Z}}_{12}},{+}\rangle$ with the binary function $g_{2}$ from
the previous lemma. We mention without proof that $\mathbf{L}$ is not
equivalent to an expansion of $\langle{{\mathbb{Z}}_{12}},{+}\rangle$ with
unary functions.

######  Lemma 2.3.

Let $f:=g_{2}$. Then $\mathbf{L}$ is term equivalent to
$\langle{{\mathbb{Z}}_{12}},{+,f}\rangle$.

###### Proof.

This follows from $f(x,y)=t(x,3x+y)$ and $t(x,y)=f(x,x+y)$ for all
$x,y\in{\mathbb{Z}}_{12}$. ∎

Finally we define a simple basis of $W_{k}$.

######  Lemma 2.4.

Let $k\in{\mathbb{N}}$, and let $R_{k}$ contain exactly one generator for
every cyclic subgroup of order $4$ of
$\langle{{\mathbb{Z}}_{12}/C},{+}\rangle^{k}$. For $\bar{r}\in R_{k}$, define

$f_{\bar{r}}\colon{\mathbb{Z}}_{12}^{k}\to C,\ x\mapsto\begin{cases}4&\text{if
}x\in\bar{r}\cup-\bar{r},\\\ 0&\text{else}.\end{cases}$

Then

  1. (1)

$f_{\bar{r}}\in\mathrm{Clo}_{k}(\mathbf{L})$ and

  2. (2)

$\\{f_{\bar{r}}\ :\ \bar{r}\in R_{k}\\}$ is a basis for $W_{k}$ as a vector
space over ${\mathbf{F}}_{3}$. In particular
$W_{k}\subseteq\mathrm{Clo}_{k}(\mathbf{L})$.

###### Proof.

For (1) note that $f_{(\bar{1},\bar{0},\dots,\bar{0})}=g_{k}$ is a term
function by Lemma 2.2. For every $\bar{r}\in R_{k}$ there exists an
automorphism $\bar{\varphi}$ on the group $({\mathbb{Z}}_{12}/C)^{k}$ that
maps $\bar{r}$ to $(\bar{1},\bar{0},\dots,\bar{0})$. There exist $k$-ary term
functions $\varphi_{1},\dots,\varphi_{k}$ on
$\langle{{\mathbb{Z}}_{12}},{+}\rangle$ such that
$\varphi(x):=(\varphi_{1}(x),\dots,\varphi_{k}(x))$ induces $\bar{\varphi}$.
Hence
$f_{\bar{r}}(x)=f_{(\bar{1},\bar{0},\dots,\bar{0})}(\varphi_{1}(x),\dots,\varphi_{k}(x))$
is a term function as well.

For (2) note that for distinct $\bar{r},\bar{s}\in R_{k}$ the supports of
$f_{\bar{r}}$ and $f_{\bar{s}}$ are disjoint. Hence $B:=\\{f_{\bar{r}}\ :\
\bar{r}\in R_{k}\\}$ is linearly independent. Further $W_{k}$ consists exactly
of the functions that are constant on the supports of $f_{\bar{r}}$ for
$\bar{r}\in R_{k}$. Thus $B$ spans $W_{k}$ and is a basis. ∎

By Lemma 2.4 we have that
$\mathrm{Clo}(\langle{{\mathbb{Z}}_{12},+},{)}\rangle+W_{k}$ is contained in
$\mathrm{Clo}(\mathbf{L})$, which concludes the proof of Theorem 1.2. Further
every $h\in\mathrm{Clo}_{k}(\mathbf{L})$ has a unique normal form

(2.3) $h(x)=\sum_{i=1}^{k}a_{i}x_{i}+\sum_{\bar{r}\in
R_{k}}b_{\bar{r}}f_{\bar{r}}$

for coefficients $a_{i}\in[12],b_{\bar{r}}\in[3]$.

##  3\. Subpower membership (Proof of Theorem 1.4)

Let $a_{1},\dots,a_{k},b\in{\mathbb{Z}}_{12}^{n}$ be the input of
$\mathrm{SMP}(\mathbf{L})$. Define an equivalence relation $\sim$ on
$\\{1,\dots,n\\}$ by

$i\sim j\text{ if }(a_{1i},\dots,a_{ki})\equiv\pm(a_{1j},\dots,a_{kj})\bmod
C^{k}.$

Equivalently $i\sim j$ iff the classes of $(a_{1i},\dots,a_{ki})$ and of
$(a_{1j},\dots,a_{kj})$ in $({\mathbb{Z}}_{12}/C)^{k}$ generate the same
cyclic subgroup.

For $i\leq n$ with $(a_{1i},\dots,a_{ki})\not\in 2{\mathbb{Z}}_{12}^{k}$
define

$b_{i}\in{\mathbb{Z}}_{12}^{n}\text{ by }b_{ij}:=\begin{cases}4&\text{if
}i\sim j,\\\ 0&\text{else.}\end{cases}$

Then $b_{i}=f_{\bar{r}}(a_{1},\dots,a_{k})$ for $\bar{r}$ the coset of
$(a_{1i},\dots,a_{ki})$ modulo $C$ and $f_{\bar{r}}$ as defined in Lemma 2.4.
Let $\\{b_{i_{1}},\dots,b_{i_{\ell}}\\}$ be the set of tuples obtained in this
way. Note that $\ell\leq n$. By Theorem 1.2 and the normal form given in (2.3)
we see that the subloop of $\mathbf{L}^{n}$ that is generated by
$a_{1},\dots,a_{k}$ is equal to the subgroup of
$\langle{{\mathbb{Z}}_{12}},{+}\rangle^{n}$ generated by
$a_{1},\dots,a_{k},b_{i_{1}},\dots,b_{i_{\ell}}$. Since membership for the
latter can be checked in polynomial time in $(k+\ell)n$, that is, in $kn$, by
linear algebra, so can membership for the former. This proves Theorem 1.4.

##  4\. Equational basis (Proof of Theorem 1.3)

Since $\mathbf{L}$ and
${\mathbf{A}}:=\langle{{\mathbb{Z}}_{12}},{+,-,0,f}\rangle$ are term
equivalent by Lemma 2.3, it suffices to show that the latter is finitely
based. We claim that the standard identities for the abelian group
$\langle{{\mathbb{Z}}_{12}},{+,-,0}\rangle$ together with the following form a
finite basis for the equational theory of ${\mathbf{A}}$:

  1. (1)

$f(x+f(u,v),y+f(r,s))=f(x,y)$

  2. (2)

$f(x+2u,y+4v)=f(x,y)$

  3. (3)

$3f(x,y)=0$

  4. (4)

$f(0,y)=0$

  5. (5)

$f(x,3y)=f(x,y)$

  6. (6)

$f(x+y,y)=f(x,y)$

  7. (7)

$f(x+y,z)=f(x,2x+2y+2z)+f(x,2y+z)-f(x,2y)+f(x,2z)+f(y,z)$

  8. (8)

$f(x,2x+y)=f(x,2y)-f(x,y)$

  9. (9)

$f(x,2y+z)=f(x,z)-f(y,z)+f(y,2x+z)$

Identities (1) to (6) are immediate from the definition of

$f\colon{\mathbb{Z}}_{12}^{2}\to 4{\mathbb{Z}}_{12},\
(x,y)\mapsto\begin{cases}4&\text{if }x\in 1+2{\mathbb{Z}}_{12},y\in
4{\mathbb{Z}}_{12},\\\ 0&\text{else.}\end{cases}$

The remaining equations may appear less intuitive at first glance but they
actually arise naturally when interpolating ternary functions in $W_{3}$ using
the binary $f$ and linear maps on ${\mathbb{Z}}_{12}$. For showing their
correctness, let $C=4{\mathbb{Z}}_{12}$ and $D:=2{\mathbb{Z}}_{12}$.

For (8) note that both sides of the equation vanish if $x\in D$. So assume
$x\in 1+D$. Then the left hand side $f(1,2+y)$ is $4$ if $y\in 2+C$ and $0$
else. This is equal to the right hand side $f(1,2y)-f(1,y)$.

Next (9) is immediate by (2) if $x\in D$ or $y\in D$. So assume $x,y\in 1+D$.
Then $2x,2y\in 2+C$ and (2) yields $f(x,z)=f(y,z)$ as well as
$f(x,2y+z)=f(y,2x+z)$. Hence (9) follows.

Finally (7) follows from (2) if $x\in D$ because then all but the last summand
on the right hand side vanish. If $y\in D$, then $2y\in C$ and by (2) the
right hand side reduces to

$\underbrace{f(x,2x+2z)}_{=f(x,0)-f(x,2z)\text{
by}~{}\eqref{it:x,2x+y}}+f(x,z)-f(x,0)+f(x,2z)+\underbrace{f(0,z)}_{=0}=f(x,z),$

same as the left hand side. So assume $x,y\in 1+D$. Then $2x,2y\in 2+C$ and
the right hand side simplifies to

$f(x,2z)+\underbrace{f(x,2x+z)}_{=f(x,2z)-f(x,z)\text{
by}~{}\eqref{it:x,2x+y}}-\underbrace{f(x,2)}_{=0}+f(x,2z)+f(x,z)=0.$

Since $x+y\in D$, the left hand side $f(x+y,z)$ yields $0$ as well. Thus (7)
is proved.

Next we show that using the identities of the group ${\mathbb{Z}}_{12}$
together with (1)-(9) we can transform terms into normal forms. By (1) and (2)
every $k$-ary term in the language of ${\mathbf{A}}$ can be transformed into a
sum of variables and terms

$f(\sum_{i=1}^{k}v_{i}x_{i},\sum_{j=1}^{k}w_{j}x_{j})\text{ with
}v_{1},\dots,v_{k}\in[2],w_{1},\dots,w_{k}\in[4].$

The latter can be rewritten into a sum of

$f(x_{i},\sum_{j=1}^{k}w_{j}x_{j})\text{ for }i\leq k,w_{1},\dots,w_{k}\in[4]$

by (4) and (7). By (8) we may assume that $w_{i}\in[2]$. To show that $w_{j}$
can be chosen to be in $[2]$ for all $j\leq i$ above, consider the smallest
$r$ such that $1\leq r<i$ and $w_{r}\in\\{2,3\\}$. For
$z:=(w_{r}-2)x_{r}+\sum_{j\neq r}w_{j}x_{j}$ equation (9) yields

$f(x_{i},2x_{r}+z)=f(x_{i},z)-f(x_{r},z)+f(x_{r},2x_{i}+z).$

For all $j\leq r$ the coefficients of $x_{j}$ in $z$ are in $\\{0,1\\}$.
Repeating this procedure for $f(x_{i},z)$ if necessary, eventually yields that
every term of ${\mathbf{A}}$ can be written as sum of variables and

$f(x_{i},\sum_{j=1}^{i-1}a_{j}x_{j}+bx_{i}+\sum_{j=i+1}^{k}c_{j}x_{j})\text{
for }i\leq k,a_{1},\dots,a_{i-1},b\in[2],c_{i+1},\dots,c_{k}\in[4].$

We can give further restrictions on the coefficients $a_{j},c_{j}$ above
depending on whether $b$ is $0$ or $1$.

Case $b=0$: Note that

$\displaystyle f(x,y+3z)$ $\displaystyle=f(x,3y+z)\text{ by }\eqref{it:x,3y}$
$\displaystyle=f(x,2y+\underline{y+z})$
$\displaystyle=f(x,\underline{y+z})-f(y,\underline{y+z})+f(y,2x+\underline{y+z})\text{
by }\eqref{it:x,2y+z}.$

Let $c:=(c_{i+1},\dots,c_{k})\in[4]^{k-i}\setminus\\{0,2\\}^{k-i}$. Then
$3c\not\equiv c\bmod 4$. Using the identity above for
$x=x_{i},y=\sum_{j=1}^{i-1}a_{j}x_{j},z=\sum_{j=i+1}^{k}c_{j}x_{j}$ together
with (7) we have that

$f(x_{i},\sum_{j=1}^{i-1}a_{j}x_{j}+3\sum_{j=i+1}^{k}c_{j}x_{j})$

can be expressed as a sum of
$f(x_{i},\sum_{j=1}^{i-1}a_{j}x_{j}+\sum_{j=i+1}^{k}c_{j}x_{j})$ and terms
$f(x_{j},\dots)$ for $j<i$.

Case $b=1$: Note that

$\displaystyle f(x,x+y+3z)=$ $\displaystyle f(x,3x+3y+z)\text{ by
}\eqref{it:x,3y}$ $\displaystyle=$ $\displaystyle f(x,2x+\underline{x+3y+z})$
$\displaystyle=$ $\displaystyle f(x,2x+\underline{2y+2z})-f(x,x+3y+z)\text{ by
}\eqref{it:x,2x+y}$ $\displaystyle=$
$\displaystyle[f(x,0)-f(x,2y+\underline{2z})]-f(x,2y+\underline{x+y+z})\text{
by }\eqref{it:x,2x+y}$ $\displaystyle=$ $\displaystyle
f(x,0)-[f(x,2z)-f(y,2z)+f(y,2x+2z)]$
$\displaystyle-[f(x,x+y+z)-f(y,x+y+z)+f(y,3x+y+z)]\text{ by
}\eqref{it:x,2y+z}.$

Let $c:=(c_{i+1},\dots,c_{k})\in[4]^{k-i}\setminus\\{0,2\\}^{k-i}$. Then
$3c\not\equiv c\bmod 4$. Using the identity above for
$x=x_{i},y=\sum_{j=1}^{i-1}a_{j}x_{j},z=\sum_{j=i+1}^{k}c_{j}x_{j}$ together
with (7) we have that

$f(x_{i},\sum_{j=1}^{i-1}a_{j}x_{j}+x_{i}+3\sum_{j=i+1}^{k}c_{j}x_{j})$

can be expressed as a sum of
$f(x_{i},0),f(x_{i},2\sum_{j=i+1}^{k}c_{j}x_{j}),f(x_{i},\sum_{j=1}^{i-1}a_{j}x_{j}+x_{i}+\sum_{j=i+1}^{k}c_{j}x_{j})$
and terms $f(x_{j},\dots)$ for $j<i$.

If $c_{i+1},\dots,c_{k}\in\\{0,2\\}$, then by (6) and (2)

$\displaystyle
f(x_{i},\sum_{j=1}^{i-1}a_{j}x_{j}+x_{i}+\sum_{j=i+1}^{k}c_{j}x_{j})$
$\displaystyle=f(\sum_{j=1}^{i-1}a_{j}x_{j},\sum_{j=1}^{i-1}a_{j}x_{j}+x_{i}+\sum_{j=i+1}^{k}c_{j}x_{j})$

with the latter expressible as a sum of terms $f(x_{j},\dots)$ for $j<i$ by
(7).

For $\ell\in{\mathbb{N}}$ define an equivalence relation $\sim$ on
$[4]^{\ell}\setminus\\{0,2\\}^{\ell}$ by $c\sim d$ if $c\equiv\pm d\bmod 4$.
Let $R_{\ell}$ be a transversal for $\sim$. Note that this is essentially the
same set as defined in Lemma 2.4. Again $|R_{\ell}|=(4^{\ell}-2^{\ell})/2$.

In summary, using the identities of the group ${\mathbb{Z}}_{12}$ and (1) to
(9) as well as recursion on $i\in[k]$, we managed to rewrite any $k$-ary term
$h$ of ${\mathbf{A}}$ as a sum of variables and terms

$\displaystyle s_{a,c}$
$\displaystyle:=f(x_{i},\sum_{j=1}^{i-1}a_{j}x_{j}+\sum_{j=i+1}^{k}c_{j}x_{j})\text{
for }i\in[k],a\in[2]^{i-1},c\in R_{k-i}\cup\\{0,2\\}^{k-i},$ $\displaystyle
t_{a,c}$
$\displaystyle:=f(x_{i},\sum_{j=1}^{i-1}a_{j}x_{j}+x_{i}+\sum_{j=i+1}^{k}c_{j}x_{j})\text{
for }i\in[k],a\in[2]^{i-1},c\in R_{k-i}.$

We claim that this representation is a normal form for $h$, more precisely,
for $u_{i}\in[12],v_{a,c},w_{a,c}\in[3]$ we have

$\sum_{i}u_{i}x_{i}+\sum_{a,c}v_{a,c}s_{a,c}+\sum_{a,c}w_{a,c}t_{a,c}=0\text{
iff all }u_{i},v_{a,c},w_{a,c}\text{ are }0.$

Assume that the term on the lefthand side induces the constant $0$-function on
${\mathbf{A}}$. From the direct decomposition in Theorem 1.2 we see
$u_{1}=\dots=u_{k}=0$. The functions induced by $s_{a,c},t_{a,c}$ span $W_{k}$
by their construction and by Lemma 2.4. To see that this spanning set for
$W_{k}$ actually forms a basis it suffices to determine its size. For fixed
$i\in[k]$ the number of choices for $a,c$ in $s_{a,c}$ and in $t_{a,c}$
together is

$2^{i-1}[(4^{k-i}-2^{k-i})/2+2^{k-i}]+2^{i-1}[(4^{k-i}-2^{k-i})/2]=2^{i-1}\cdot
4^{k-i}=2^{k-1}\cdot 2^{k-i}.$

Hence summing up over all $i\in[k]$ we have

$2^{k-1}\cdot\sum_{i=1}^{k}2^{k-i}=2^{k-1}(2^{k}-1)=\dim W_{k}$

functions. Hence they are linearly independent over ${\mathbf{F}}_{3}$, and
$\sum_{a,c}v_{a,c}s_{a,c}+\sum_{a,c}w_{a,c}t_{a,c}=0$ only if all coefficients
$v_{a,c},w_{a,c}$ are $0$.

Thus every $k$-ary term function on ${\mathbf{A}}$ can be rewritten into a
uniquely determined normal form using the finitely many identities given
above, and ${\mathbf{A}}$ is finitely based. Theorem 1.3 is proved.

## References

  * [1] E. Aichinger and N. Mudrinski.  Some applications of higher commutators in Mal’cev algebras.  Algebra Universalis, 63(4):367–403, 2010.
  * [2] A. Bulatov, P. Mayr, and Á. Szendrei.  The subpower membership problem for finite algebras with cube terms.  Log. Methods Comput. Sci., 15(1):Paper No. 11, 48 pp., 2019.
  * [3] R. Freese and R. N. McKenzie.  Commutator Theory for Congruence Modular Varieties, volume 125 of London Math. Soc. Lecture Note Ser. Cambridge University Press, 1987.  Available from `http://math.hawaii.edu/~ralph/Commutator/comm.pdf`.
  * [4] P. Idziak, P. Marković, R. McKenzie, M. Valeriote, and R. Willard.  Tractability and learnability arising from algebras with few subpowers.  SIAM J. Comput., 39(7):3023–3037, 2010.
  * [5] K. Kearnes.  Congruence modular varieties with small free spectra.  Algebra Universalis, 42(3):165–181, 1999.
  * [6] P. Mayr.  The subpower membership problem for Mal′cev algebras.  Internat. J. Algebra Comput., 22(7):1250075, 23, 2012.
  * [7] M. R. Vaughan-Lee.  Nilpotence in permutable varieties.  In Universal algebra and lattice theory (Puebla, 1982), volume 1004 of Lecture Notes in Math., pages 293–308. Springer, Berlin, 1983.