\section{Introduction}
Deep convolutional neural networks (CNN) \cite{fukushima1982neocognitron,lecun1998gradient} are the backbone in vision-related tasks, including image classification \cite{krizhevsky2012imagenet}, object detection \cite{redmon2016you}, image generation \cite{goodfellow2014generative}, video recognition \cite{simonyan2014two}, and audio classification \cite{hershey2017cnn}. A closer look at the dominating success of deep CNNs reveals its basis on two factors.

The first factor is the strong capacity of the convolutional neural networks, usually characterized by the enormous model size. Recent state-of-the-art progresses usually result from very large models, with millions to billions of trainable parameters. For example, ImageNet \cite{deng2009imagenet} accuracy grows when larger VGGs \cite{simonyan2014very} (increasing 11 to 19 layers$\Longrightarrow$69\% to 74\% accuracy) or ResNets \cite{he2016deep} (increasing 18 to 152 layers$\Longrightarrow$70\% to 78\% accuracy) are used \cite{pytorchvision}. Consequently, the eager to use larger models for better accuracy naturally draws people's attention to the scalability and efficiency of training.

The second factor is the availability of big data, which oftentimes contain private and sensitive information. The usage of such data demands rigorous protection against potential privacy attacks. In fact, one standard approach to guarantee the protection is by differentially private (DP) \cite{dwork2006calibrating,dwork2014algorithmic} training of the models. Since \cite{abadi2016deep}, CNNs have achieved promising results under strong DP guarantee: CIFAR10 achieves 92.4\% accuracy in \cite{tramer2020differentially} and ImageNet achieves 81.1\% accuracy in \cite{de2022unlocking}.

Unifying the two driving factors of CNNs leads to the DP training of large CNNs. However, the following challenges are hindering our application of large and private CNNs in practice.

\textbf{Challenge 1: Time and space efficiency in DP training.}
DP training can be extremely inefficient in memory and speed. For example, a straightforward implementation in Tensorflow Privacy library shows that DP training can be $1000\times$ slower than the non-DP training, even on a small RNN \cite{bu2021fast}; other standard DP libraries, Opacus \cite{opacus} and JAX \cite{kurakin2022toward,subramani2021enabling}, which trade off memory for speed, could not fit a single datapoint into GPU on GPT2-large \cite{li2021large}; addtionally, $3\sim 9\times$ slowdown of DP training has been reported in \cite{kurakin2022toward,de2022unlocking,subramani2021enabling} using JAX.

The computational bottleneck comes from the per-sample gradient clipping at each iteration (see \eqref{eq:privatized grad}), a necessary step in DP deep learning. I.e., denoting the loss as $\sum_i\mathcal{L}_i$, we need to clip the per-sample gradient $\{\frac{\partial \mathcal{L}_i}{\partial \mathbf{W}}\}_i$ individually. This computational issue is even more severe when we apply a large batch size, which is necessary to achieve high accuracy of DP neural networks. In \cite{li2021large,kurakin2022toward,mehta2022large}, it is shown that the optimal batch size for DP training is significantly larger than for regular training. For instance, DP ResNet18 achieves best performance on ImageNet when batch size is 64*1024 \cite{kurakin2022toward}; and DP ResNet152 and ViT-Large use a batch size $2^{20}$ in \cite{mehta2022large}. As a result, an efficient implementation of per-sample gradient clipping is much-needed to fully leverage the benefit of large batch training.


\textbf{Challenge 2: Do large DP vision models necessarily harm accuracy?}
An upsetting observation in DP vision models is that, over certain relatively small model size, larger DP CNNs seem to underperform smaller ones. This is observed in models that are either pre-trained or trained from scratch \cite{klause2022differentially,abadi2016deep}. As an example of the pre-trained cases, previously state-of-the-art CIFAR10 is obtained from a small DP linear model \cite{tramer2020differentially}, and the fine-tuned DP ResNet50 underperforms DP ResNet18 on ImageNet \cite{kurakin2022toward}. On the contrary, the empirical evidence in DP language models shows that larger models can consistently achieve better accuracy \cite{li2021large}. Interestingly, we empirically demonstrate that the trend in \cite{li2021large} can possibly hold in vision models as well.


\subsection{Contributions}
In this work, we propose new algorithms to efficiently train large-scale CNNs with DP optimizers. To be specific, our contributions are as follows.
\begin{enumerate}
    \item We propose a novel implementation, termed as the \textbf{\textit{mixed ghost clipping}}, of the per-sample gradient clipping for 1D$\sim$3D convolutional layers. The mixed ghost clipping is the first method that can \textbf{\textit{implement per-sample gradient clipping without per-sample gradients}} of the convolutional layers. It works with any DP optimizer and any clipping function almost as memory efficiently as in standard training, thus significantly outperforming existing implementation like Opacus \cite{opacus}.
    
    \item In some tasks, mixed ghost clipping also claims supremacy on speed using a fixed batch size. The speed can be further boosted (say $1.7\times$ faster than the fastest alternative DP algorithms and only $2\times$ slower than the non-private training) when the memory saved by our method is used to fit the largest possible batch size.
    
    \item We provide the first complexity analysis of mixed ghost clipping in comparison to other training algorithms. This analysis clearly indicates the necessity of our layerwise decision principle, without which the existing methods suffer from high memory burden.

    \item Leveraging our algorithms, we can efficiently train large DP models, such as VGG, ResNet, Wide-ResNet, DenseNet, and Vision Transformer (ViT).
    Using DP ViTs at ImageNet scale, we are the first to train convolutional ViTs under DP and achieve dominating SOTA on CIFAR10/100 datasets, thus bringing new insights that larger vision models can consistently achieve better accuracy under DP.
\end{enumerate}

\subsection{Previous arts}
The straightforward yet highly inefficient way of per-sample gradient clipping is to use batch size 1 and compute gradients with respect to each individual loss. Recently, more advanced methods have significantly boosted the efficiency by avoiding such a naive approach. The most widely applied method is implemented in the Opacus library \cite{opacus}, which is fast but memory costly as per-sample gradients $\bm{g}_i=\frac{\partial \mathcal{L}_i}{\partial \mathbf{W}}$ are instantiated to compute the weighted gradient $\sum_i C_i\cdot \bm{g}_i$ in \eqref{eq:privatized grad}. A more efficient method, FastGradClip \cite{lee2020scaling}, is to use a second back-propagation with weighted loss $\sum_i C_i\cdot \mathcal{L}_i$ to indirectly derive the weighted gradient. 

In all above-mentioned methods and \cite{rochette2019efficient}, the per-sample gradients are instantiated, whereas this can be much inefficient and not necessary according to the `ghost clipping' technique, as to be detailed in \Cref{sec:ghost clipping}. In other words, ghost clipping proves that the claim `DP optimizers require access to the per-sample gradients' is wrong. Note that ghost clipping is firstly proposed by \cite{goodfellow2015efficient} for linear layers, and then extended by \cite{li2021large} to sequential data and embedding layers for language models. However, the ghost clipping has not been extended to convolutional layers, due to the complication of the convolution operation and the high dimension of data (text data is mostly 2D, yet image data are 3D and videos are 4D). In fact, we will show that even ghost clipping alone is not satisfactory for CNNs, and therefore propose the mixed ghost clipping, that narrows the efficiency gap between DP training and the regular training.

\section{Preliminaries}
\subsection{Differential privacy}
Differential privacy (DP) has become the standard approach to provide privacy guarantee for modern machine learning models. The privacy level is characterized through a pair of privacy quantities $(\epsilon,\delta)$, where smaller $(\epsilon,\delta)$ means stronger protection.
\begin{definition}[\cite{dwork2014algorithmic}]\label{def:DP}
A randomized algorithm $M$ is $ (\varepsilon, \delta)$-DP if for any neighboring datasets $ S, S^{\prime} $ that differ by one arbitrary sample, and for any event $E$, it holds that
\begin{align*}
 \mathbb{P}[M(S) \in E] \leqslant \mathrm{e}^{\varepsilon} \mathbb{P}\left[M\left(S^{\prime}\right) \in E\right]+\delta.
\end{align*}
\end{definition}

In deep learning where the number of parameters are large, the Gaussian mechanism \cite[Theorem A.1]{dwork2014algorithmic} is generally applied to achieve DP at each training iteration, i.e. we use regular optimizers on the following privatized gradient:
\begin{align}
\widetilde \bm{g}=\sum_i C(\|\bm{g}_i\|;R) \cdot \bm{g}_i+\sigma R\cdot\mathcal{N}(0,\mathbf{I})=\sum_i C_i\bm{g}_i+\sigma R\cdot\mathcal{N}(0,\mathbf{I})
\label{eq:privatized grad}
\end{align}
where $C$ is any function whose output is upper bounded by $R/\|\bm{g}_i\|$ and $R$ is known as the clipping norm. To name a few examples of $C$, we have the Abadi's clipping $\min(R/\|\bm{g}_i\|,1)$ in \cite{abadi2016deep} and the global clipping $\mathbb{I}(\|\bm{g}_i\|<Z)\cdot R/Z$ for any constant $Z$ in \cite{bu2021convergence}. Here $\sigma$ is the noise multiplier that affects the privacy loss $(\epsilon,\delta)$, but $R$ only affects the convergence, not the privacy.

In words, DP training switches from updating with $\sum_i \bm{g}_i$ to updating with the private gradient $\widetilde \bm{g}$: SGD with private gradient is known as DP-SGD; Adam with private gradient is known as DP-Adam.

Algorithmically speaking, the Gaussian mechanism can be decomposed into two parts: the per-sample gradient clipping and the Gaussian noise addition. From the viewpoint of computational complexity, the per-sample gradient clipping is the bottleneck, while the noise addition costs negligible overhead.

In this work, our focus is the implementation of per-sample gradient clipping \eqref{eq:privatized grad}. We emphasize that our implementation is only on the algorithmic level, not affecting the mathematics and thus not the performance of DP optimizers. That is, our mixed ghost clipping provides exactly the same accuracy results as Opacus, FastGradClip, etc.

\vspace{-0.2cm}
\subsection{Per-sample gradient for free during standard back-propagation}




In DP training, the per-sample gradient is a key quantity which can be derived for free from the standard back-propagation. We briefly introduce the back-propagation on linear layers, following the analysis from \cite{goodfellow2015efficient,li2021large}, so as to prepare our new clipping implementation for convolutional layers. Note that the convolutional layers can be viewed as equivalent to the linear layers in \Cref{sec:conv as linear}.

Let the input of a hidden layer be $\a\in\ensuremath{\mathbb{R}}^{B\times \cdots\times d}$ (a.k.a. post-activation).  Here $\a$ can be in high dimension: for sequential data such as text, $\a\in\ensuremath{\mathbb{R}}^{B\times T\times d}$ where $T$ is the sequence length; for image data, $\a\in\ensuremath{\mathbb{R}}^{B\times H\times W\times d}$ where $(H,W)$ is the dimension of image and $d$ is number of channels; for 3D objects or video data, $\a\in\ensuremath{\mathbb{R}}^{B\times H\times W\times D\times d}$ where $D$ is the depth or time length, respectively. 

Denote the weight of a linear layer as  $\mathbf{W}\in \ensuremath{\mathbb{R}}^{d\times p}$, its bias as $\b \in \ensuremath{\mathbb{R}}^{p}$ and its output (a.k.a. pre-activation) as $\mathbf{s} \in \ensuremath{\mathbb{R}}^{B\times \cdots\times p}$, where $B$ is the batch size and $p$ is the output dimension. 

In the $l$-th layer of a neural network with $L$ layers in total, we denote its weight, bias, input and output as $\mathbf{W}_{(l)}, \b_{(l)},\a_{(l)}, \mathbf{s}_{(l)}$ respectively, and the activation function as $\phi$. Consider
\begin{align}
\a_{(l+1),i} = \phi (\mathbf{s}_{(l),i})  = \phi(\a_{(l),i}\mathbf{W}_{(l)}+\b_{(l)}).
\label{eq:linear forward}
\end{align}

Clearly the $i$-th sample's \textit{hidden feature} $\a_{(l),i}$ at layer $l$ is freely extractable during the forward pass. 

Let $\mathcal{L}=\sum_{i=1}^n \mathcal{L}_i$ be the total loss  and $\mathcal{L}_i$ be the per-sample loss with respect to the $i$-th sample. During a standard back-propagation, the following \textit{partial product} is maintained,
\begin{align}
\frac{\partial \mathcal{L}}{\partial \mathbf{s}_{(l),i}}
=&
\frac{\partial \mathcal{L}}{\partial \a_{(L),i}}\circ \frac{\partial \a_{(L),i}}{\partial \mathbf{s}_{(L-1),i}}\cdot
\frac{\partial \mathbf{s}_{(L-1),i}}{\partial \a_{(L-1),i}}\circ\cdots\frac{\partial \a_{(l+1),i}}{\partial \mathbf{s}_{(l),i}}= \frac{\partial \mathcal{L}}{\partial \mathbf{s}_{(l+1),i}}\mathbf{W}_{(l+1)}\circ\phi^{\prime}(\mathbf{s}_{(l),i})
\label{eq:back prop1}
\end{align}

so as to compute the standard gradient $\frac{\partial \mathcal{L}}{\partial \mathbf{W}_{(l)}}=\sum_i\frac{\partial \mathcal{L}_i}{\partial \mathbf{W}_{(l)}}$ in \eqref{eq:outer product linear}. Here $\circ$ is the Hadamard product and $\cdot$ is the matrix product. Therefore, $\frac{\partial \mathcal{L}}{\partial \mathbf{s}_{(l),i}}$ is also available for free from \eqref{eq:back prop1} and extractable by Pytorch hooks, which allows us compute the per-sample gradient by
\begin{align}
\frac{\partial \mathcal{L}_i}{\partial \mathbf{W}_{(l)}}=\frac{\partial \mathcal{L}_i}{\partial \mathbf{s}_{(l),i}}^\top\frac{\partial \mathbf{s}_i}{\partial \mathbf{W}_{(l)}}=\frac{\partial \mathcal{L}}{\partial \mathbf{s}_{(l),i}}^\top\a_{(l),i}, 
\quad\frac{\partial \mathcal{L}_i}{\partial \b_{(l)}}=\frac{\partial \mathcal{L}_i}{\partial \mathbf{s}_{(l),i}}^\top\frac{\partial \mathbf{s}_{(l),i}}{\partial \b_{(l)}}=\frac{\partial \mathcal{L}}{\partial \mathbf{s}_{(l),i}}^\top\mathbf{1}.
\label{eq:outer product linear}
\end{align}


\vspace{-0.2cm}
\subsection{Equivalence between convolutional and linear layer}
\label{sec:conv as linear}
In a convolutional layer\footnote{See a detailed explanation in \Cref{app:explain conv} for the $U,F$ operation and the dimension formulae in convolution.}, the forward pass is
\begin{align}
\a_{(l+1),i} = \phi (\mathbf{s}_{(l),i})  = \phi(F(U(\a_{(l),i})\mathbf{W}_{(l)}+\b_{(l)}))
\label{eq:conv forward}
\end{align}
in which $F$ is the folding operation and $U$ is the unfolding operation. To be clear, we consider a 2D convolution that $\a_{(l,i)}\in\ensuremath{\mathbb{R}}^{ H_\text{in}\times W_\text{in}\times d_{(l)}}$ is the input of hidden feature, $(H_\text{in},W_\text{in})$ is the input dimension, $d_{(l)}$ is the number of input channels. Then $U$ unfolds the hidden feature from dimension $(H_\text{in}, W_\text{in}, d_{(l)})$ to $(H_\text{out} W_\text{out}, d_{(l)}k_H k_W)$, where $k_H,k_W$ are the kernel sizes and $(H_\text{out},W_\text{out})$ is the output dimension. After the matrix multiplication with $\mathbf{W}_{(l)}\in\ensuremath{\mathbb{R}}^{d_{(l)}k_H k_W\times p_{(l)}}$, the intermediate output $\mathbf{s}_{(l),i}$ is folded by $F$ from dimension $(H_\text{out}W_\text{out}, p_{(l)})$ to $(H_\text{out},W_\text{out}, p_{(l)})$.

To present concisely, we ignore the layer index $l$ and write the per-sample gradient of weight for the convolutional layer, in analogy to the linear layer in \eqref{eq:outer product linear},
\begin{align}
\frac{\partial \mathcal{L}_i}{\partial \mathbf{W}}=\frac{\partial \mathcal{L}}{\partial F^{-1}(\mathbf{s}_i)}^\top U(\a_i)=F^{-1}\left(\frac{\partial \mathcal{L}}{\partial\mathbf{s}_i}\right)^\top U(\a_i).
\label{eq:outer product conv}
\end{align}
Here $F^{-1}$ is the inverse operation of $F$ and simply flattens all dimensions except the last one: from $(H_\text{out},W_\text{out}, p_{(l)})$ to $(H_\text{out}W_\text{out}, p_{(l)})$. From \eqref{eq:outer product conv}, we derive the per-sample gradient norm for the convolutional layers from the same formula as in \cite[Appendix F]{li2021large},
\begin{align}
\left\|\frac{\partial \mathcal{L}_i}{\partial \mathbf{W}}\right\|_\text{Fro}^2=\text{vec}(U(\a_i )U(\a_i)^\top)\text{vec}\left(F^{-1}\left(\frac{\partial \mathcal{L}}{\partial \mathbf{s}_i}\right)F^{-1}\left(\frac{\partial \mathcal{L}}{\partial \mathbf{s}_i}\right)^\top\right).
\label{eq:ghost norm conv}
\end{align}


\vspace{-0.2cm}
\section{Ghost clipping for Convolutional Layers}
\label{sec:ghost clipping}

\vspace{-0.2cm}
Leveraging our derivation in \eqref{eq:ghost norm conv}, we propose the ghost clipping to compute the clipped gradient without ever generating the per-sample gradient $\frac{\partial \mathcal{L}_i}{\partial \mathbf{W}}$. The entire procedure is comprised of the ghost norm computation and the second back-propagation, as demonstrated in \Cref{fig:flowcharts}.

\begin{figure}[!htp]
    \centering
   
    \includegraphics[scale=0.32]{images/diagram1.pdf}
   
    \caption{Per-sample gradient clipping for convolutional layers. \textbf{Left: Opacus} = Back-propagation + Gradient instantiation + Weighted gradient. \textbf{Middle: FastGradClip} = Back-propagation + Gradient instantiation + Second back-propagation. \textbf{Right: Ghost clipping} = Back-propagation + Ghost norm + Second back-propagation. See \Cref{sec:complexity} for their complexity analysis.}
    \label{fig:flowcharts}
\end{figure}

\vspace{-0.2cm}
\subsection{Ghost norm: computing gradient norm without the gradient}

The per-sample gradient norm is required to compute the per-sample $C_i$ in \eqref{eq:privatized grad}. While it is natural to instantiate the per-sample gradients and then compute their norms \cite{rochette2019efficient,lee2020scaling,opacus,de2022unlocking,mehta2022large}, this is not always optimal nor necessary. Instead, we can leverage \eqref{eq:ghost norm conv}, the ghost norm, to compute the per-sample gradient norm and avoid the possibly expensive per-sample gradient. Put differently, when $T=H_\text{out}W_\text{out}$ is small, the multiplication $U(\a_i)U(\a_i)^\top$ plus $F^{-1}\left(\frac{\partial \mathcal{L}}{\partial \mathbf{s}_i}\right)F^{-1}\left(\frac{\partial \mathcal{L}}{\partial \mathbf{s}_i}\right)^\top$ is cheap, but the multiplication $F^{-1}\left(\frac{\partial\mathcal{L}}{\partial\mathbf{s}_i}\right)^\top U(\a_i)$ is expensive. We demonstrate the ghost clipping's supremacy over complexity empirically in \Cref{tab:cifar10 fixed 256} and theoretically in \Cref{tab:complexity}.

\subsection{Second back-propagation: weighted loss leads to weight gradient}
We conduct a second back-propagation with the weighted loss $\sum_i C_i\mathcal{L}_i$ to derive the weighted gradient $\sum_i C_i\bm{g}_i$ in \eqref{eq:privatized grad}, which costs extra time. In contrast, Opacus \cite{opacus} and JAX \cite{de2022unlocking,subramani2021enabling} generate and store the per-sample gradient $\bm{g}_i$ for all $i\in[B]$. Thus the weighted gradient is directly computable from $\bm{g}_i$ as the memory is traded off for faster computation. However, in some cases like \Cref{tab:imagenet} on ImageNet and \Cref{tab:cifar100ViT} on CIFAR100, we can use larger batch size to compensate the slowdown of the second back-propagation.


\vspace{-0.2cm}
\section{Mixed Ghost Clipping: To be a ghost or not, that is the question}
\vspace{-0.5cm}

\begin{algorithm}[H]
	\caption{Mixed Ghost Clipping (single iteration)}\label{alg:dpsgd1}

    \textbf{Parameters:} number of layers $L$, gradient clipping norm $R$.
\begin{algorithmic}[0]
\vspace{-0.4cm}
\Statex\tikzmark{begin}
\For{$l = 1,2, \ldots, L$}
\If{$2T_{(l)}^2<p_{(l)}d_{(l)}$}
\Statex {\hspace{1.1cm}}
$\mathbf{W}_{(l)}.\text{ghost\_norm}=\text{True}$
\Comment \textcolor{red}{Forward pass}
\EndIf
\Statex {\hspace{0.55cm}}
Compute $\a_{(l+1),i} = \phi(F(U(\a_{(l),i})\mathbf{W}_{(l)}+\b_{(l)}))$
\EndFor
\tikzmark{end}
\drawredbox

\Statex
Compute per-sample losses $\mathcal{L}_i$.

\vspace{-0.3cm}
\tikzmark{begin}
\For{$l = L,L-1, \ldots, 1$}
\Statex {\hspace{0.55cm}}
Compute $\frac{\partial \mathcal{L}}{\partial \mathbf{s}_{(l),i}}
= \frac{\partial \mathcal{L}}{\partial \mathbf{s}_{(l+1),i}}\mathbf{W}_{(l+1)}\circ\phi^{\prime}(\mathbf{s}_{(l),i})$
\Comment{\textcolor{cyan}{Mixed ghost norm in first back-propagation}}
\If{$\mathbf{W}_{(l)}.\text{ghost\_norm}=\text{True}$}
\Statex {\hspace{1.1cm}}
$\|\frac{\partial \mathcal{L}_i}{\partial W_{(l)}}\|_\text{Fro}^2=\text{vec}(U(\a_{(l),i} )U(\a_{(l),i})^\top)\text{vec}\left(\frac{\partial \mathcal{L}}{\partial F^{-1}(\mathbf{s}_{(l),i})}\frac{\partial \mathcal{L}}{\partial F^{-1}(\mathbf{s}_{(l),i})}^\top\right)$
\Else
\Statex {\hspace{1.1cm}}
$\frac{\partial \mathcal{L}_i}{\partial W_{(l)}}=F^{-1}(\frac{\partial \mathcal{L}}{\partial\mathbf{s}_{(l),i}})U(\a_{(l),i}) \longrightarrow \|\frac{\partial \mathcal{L}_i}{\partial W_{(l)}}\|_\text{Fro}^2$
\EndIf
\EndFor
\tikzmark{end}
\drawcyanbox

\Statex
Compute per-sample gradient norm $\|\frac{\partial \mathcal{L}_i}{\partial W}\|_\text{Fro}^2=\sum_l \|\frac{\partial \mathcal{L}_i}{\partial W_{(l)}}\|_\text{Fro}^2$

\Statex 
Compute weighted loss $\mathcal{L}_\text{weighted}=\sum_i C(\|\frac{\partial \mathcal{L}_i}{\partial W}\|_\text{Fro};R) \cdot\mathcal{L}_i$

\Statex \textcolor{blue}{Second back-propagation} with $\mathcal{L}_\text{weighted}$ to generate $\sum_i C_i\frac{\partial \mathcal{L}_i}{\partial \mathbf{W}}$

	\end{algorithmic}
	\label{alg:mixed ghost}
\end{algorithm}

While the ghost norm offers the direct computation gradient norm at the cost of an indirect computation of the weighted gradient, we will show that ghost clipping alone may not be sufficient for efficient DP training, as we demonstrate in \Cref{tab:cifar10 fixed 256} and \Cref{fig:max bs and throughput}. In \Cref{tab:complexity}, we give the first fine-grained analysis of the space and time complexity for DP training algorithms. Our analysis gives the precise condition when the per-sample gradient instantiation (adopted in Opacus \cite{opacus}) is more or less efficient than our ghost norm method. To take the advantage of both methods, we propose the mixed ghost clipping method in \Cref{alg:mixed ghost}, which applies the ghost clipping or non-ghost clipping by a layerwise decision.


We highlight that the key reason supporting the success of mixed ghost clipping method is its layerwise adaptivity to the dimension parameters, $(p_{(l)}, d_{(l)}, T_{(l)},k_{H},k_{W})$, which vary largely across different layers (see \Cref{fig:vgg11}). The variance results from the fact that images are non-sequential data, and that the convolution and pooling can change the size ($T=H_\text{out}W_\text{out}$) of hidden features drastically.



In the next two sections, we will analyze rigorously the time and memory complexities of the regular training and the DP training, using ghost or non-ghost clippings. 
\begin{remark}
In \Cref{alg:mixed ghost}, we present the mixed ghost clipping that prioritizes the space complexity by \eqref{eq:memory priority}. We also derive and implement a speed-priority version by comparing the time complexity of ghost norm and gradient instantiation in \Cref{tab:block complexity}. However, the efficiency difference is empirically insignificant. 
\end{remark}

\subsection{Complexity analysis}
\label{sec:complexity}

We now break each clipping method into operation modules and analyze their complexities. A similar but coarse analysis from \cite{li2021large} only claims, on sequential layers, $O(BT^2)$ space complexity with ghost clipping and $O(Bpd)$ without ghost clipping. The time complexity and/or convolutional layers are not analyzed until this work.



\begin{table}[!htb]
    \centering
    \setlength\tabcolsep{2.5pt}
    \begin{tabular}{c|c|c|c|c}
    \hline
         Complexity &Back-propagation&Ghost norm &Grad instantiation&Weighted grad \\\hline
        Time &$2BTD(2p+1)$&$2BT^2(D+p+1)-B$&$2B(T+1)pD$&$2BpD$ \\\hline
        Space&$BTp+2BTD+pD$&$B(2T^2+1)$&$B(pD+1)$&0 \\\hline
    \end{tabular}
    \caption{Complexities of operation modules in per-sample gradient clipping methods, contributed by a single 2D convolutional layer.}
    \label{tab:block complexity}
\end{table}

Here $B$ is the batch size, $D=dk_H k_W$ where $d$ is the number of input channels, $k$ is the kernel sizes, $p$ is the number of output channels, and $T=H_\text{out}W_\text{out}$. We leave the detailed complexity computation in \Cref{app:complexity}. Leveraging \Cref{tab:block complexity}, we give the complexities of different clipping algorithms in \Cref{tab:complexity}.



\begin{table}[!htb]
    \centering
    \begin{tabular}{c|c|c}
    \hline
     Complexity &Time&Space \\\hline\hline
    Opacus \cite{opacus}&$6BTpD$&$B(pd+Tp+2TD)$*
    \\\hline
    FastGradClip \cite{lee2020scaling}&$10BTpD$&$B(pD+Tp+2TD)$\\\hline
    Ghost clipping (ours) &$8BTpD+2BT^2(p+D)$&$B(2T^2+Tp+2TD)$ \\\hline
    Mixed ghost clipping (ours)&SEE CAPTION&$B(\min(2T^2, pD)+Tp+2TD)$
    \\\hline
    \end{tabular}
    \caption {Complexity of different implementations of per-sample gradient clipping by a single 2D convolutional layer. Only highest order terms are listed. * indicates that Opacus stores the per-sample gradients of all layers, thus a per-layer space complexity does not accurately characterize its memory burden, since other methods only store the intermediate variables one layer at a time. The mixed ghost clipping's time complexity is between FastGradClip and ghost clipping, depending on which of $(2T^2,pD)$ is smaller.}
    \label{tab:complexity}
\end{table}



\subsection{Layerwise decision in mixed clipping}



From the space complexity in \Cref{tab:complexity}, we derive the layerwise decision that selects the more memory efficient of FastGradClip (gradient instantiation) and ghost clipping (ghost norm):
\begin{align}
\text{Choose ghost norm over per-sample gradient instantiation if } 2T^2<pD=pd k_H k_W.
\label{eq:memory priority}
\end{align}

\begin{minipage}[b]{.35\textwidth}
\hspace{1cm}
\centering
\includegraphics[width=2.5cm,height=7cm]{images/vgg11.pdf}
\captionof{figure}{VGG-11 architecture on ImageNet ($224\times 224$).}
\label{fig:vgg11}
\end{minipage}
\hspace{0.3cm}
\begin{minipage}[b]{.64\textwidth}
\begin{tabular}{c|c|c}
 \hline
  & Ghost norm & Non-ghost norm \\ \hline
    Space& \multirow{2}{*}{$2T_{(l)}^2=2H_\text{out}^2W_\text{out}^2$}& \multirow{2}{*}{$p_{(l)} d_{(l)}k_{H}k_{W}$} \\
    Complexity&&\\\hline\hline
         conv1&$5.0\times 10^9$ & \cellcolor{green!25}$\bm{1.7\times 10^3}$ \\ \hline
         conv2&$3.0\times 10^8$ & \cellcolor{green!25}$\bm{7.3\times 10^4}$ \\ \hline
         conv3&$2.0\times 10^7$ & \cellcolor{green!25}$\bm{2.9\times 10^5}$ \\ \hline
         conv4&$2.0\times 10^7$ & \cellcolor{green!25}$\bm{5.8\times 10^5}$ \\ \hline
         conv5&$1.2\times 10^6$ & \cellcolor{green!25}$\bm{1.1\times 10^6}$ \\ \hline
         conv6&\cellcolor{green!25}$\bm{1.2\times 10^6}$ & $2.3\times 10^6$ \\ \hline
         conv7&\cellcolor{green!25}$\bm{7.6\times 10^4}$ & $2.3\times 10^6$ \\ \hline
         conv8&\cellcolor{green!25}$\bm{7.6\times 10^4}$ & $2.3\times 10^6$ \\ \hline
         fc9&\cellcolor{green!25}$\bm{2}$ & $1.0\times 10^8$ \\ \hline
         fc10&\cellcolor{green!25}$\bm{2}$ & $1.6\times 10^7$ \\ \hline
         fc11&\cellcolor{green!25}$\bm{2}$ & $4.1\times 10^6$\\ \hline
    \end{tabular}
    \captionof{table}{Layerwise decision of mixed ghost clipping on VGG-11. Green background indicates being selected.}
    \label{tab:layerwise decision}
\end{minipage}

Therefore, our mixed ghost clipping is a mixup of FastGradClip and the ghost clipping (c.f. \Cref{fig:flowcharts}). We note that the decision by the mixed ghost clipping \eqref{eq:memory priority} depends on different dimensions: the ghost clipping depends on the size of hidden features (height $H$ and width $W$) which in turn depends on kernel size, stride, dilation and padding (see \Cref{app:explain conv} for introduction of convolution), while only the non-ghost clipping depends on the number of channels. In ResNet and VGG, the hidden feature size decreases as layer depth increases, due to the shrinkage from the convolution and pooling operation; on the opposite, the number of channels increases in deeper layers.

\begin{remark}[Ghost clipping favors bottom layers]
As a consequence of decreasing hidden feature size and increasing number of channels, there exists a depth threshold beyond which the ghost clipping is preferred in bottom layers, where the save in complexity is substantial. In \Cref{fig:vgg11} and \Cref{tab:layerwise decision}, as the layer of VGG 11 goes deeper, the hidden feature size shrinks from $224\to 112\to\cdots\to 14$ and the number of channels increases from $3\to 64\to\cdots\to 512$.
\end{remark}

\vspace{-0.3cm}
\section{Performance}
\vspace{-0.3cm}
We compare our ghost clipping and mixed ghost clipping methods to state-of-the-art clipping algorithms, namely Opacus \cite{opacus} and FastGradClip \cite{lee2020scaling}, which are implemented in Pytorch. We are aware of but will not compare to implementations of these two algorithms in JAX \cite{jax2018github}, e.g. \cite{kurakin2022toward,subramani2021enabling,de2022unlocking}, so as to only focus on the algorithms rather than the operation framework.
All experiments run on one Tesla V100 GPU (16GB RAM). 

We highlight that switching from the regular training to DP training only needs a few lines of code using our privacy engine (see \Cref{app:privacy engine}). For CNNs, we use models from \url{https://github.com/kuangliu/pytorch-cifar} on CIFAR10 \cite{krizhevsky2009learning} and models from Torchvision \cite{pytorchvision} on ImageNet \cite{deng2009imagenet}. For ViTs, regardless of datasets, we use models from PyTorch Image Models \cite{rw2019timm}.



\vspace{-0.3cm}
\subsection{Time and memory efficiency (fixed batch size)}
\vspace{-0.2cm}
We first measure the time and space complexities when the physical batch size is fixed. Here we define the physical batch size (or the virtual batch size) as the number of samples actually fed into the memory, which is different from the logical batch size. For example, if we train with batch size 1000 but can only feed 40 samples to GPU at one time, we back-propagate 25 times before updating the weights for 1 time. This technique is known as the gradient accumulation and is widely applied in large batch training, which particularly benefits the accuracy of DP training \cite{,li2021large,kurakin2022toward,de2022unlocking,mehta2022large}.


\begin{table}[!htb]
\setlength\tabcolsep{3pt}
\centering
    \begin{tabular}{|c|c|c|c|c|}
    \hline
    Dataset& Model \& \# Params&Package& Time (sec) / Epoch& Active Memory (GB)
    \\\hline
    \multirow{15}{*}{CIFAR10} &\multirow{5}{*}{CNN \cite{tramer2020differentially,papernot2020tempered}}&Opacus&12&1.37
    \\\cline{4-5}
    &&FastGradClip&11&0.94
    \\\cline{4-5}
&&Ghost (ours)&11&2.47
    \\\cline{4-5}
    &0.551M &Mixed (ours)&7&0.79
    \\\cline{4-5}
&&Non-DP&5&0.66
    \\\cline{2-5}
    &&Opacus&OOM / \textcolor{blue}{OOM} / \textcolor{red}{OOM}&OOM / \textcolor{blue}{OOM} / \textcolor{red}{OOM}
    \\\cline{4-5}
    &&FastGradClip& 45 / \textcolor{blue}{80} / \textcolor{red}{OOM}&6.32 / \textcolor{blue}{7.65} / \textcolor{red}{OOM}
    \\\cline{4-5}
    
    &ResNet 18 / \textcolor{blue}{34} / \textcolor{red}{50}&Ghost (ours)&59 / \textcolor{blue}{98} / \textcolor{red}{158}&4.00 / \textcolor{blue}{4.90} / \textcolor{red}{9.62}
    \\\cline{4-5}
    &11M / \textcolor{blue}{21M} / \textcolor{red}{23.5M}&Mixed (ours)&37 / \textcolor{blue}{66} / \textcolor{red}{119}&3.31 / \textcolor{blue}{4.13} / \textcolor{red}{9.62}
    \\\cline{4-5}
&&Non-DP&14 / \textcolor{blue}{24} / \textcolor{red}{49}&3.30 / \textcolor{blue}{4.12} / \textcolor{red}{9.56}
    \\\cline{2-5}
&&Opacus&OOM / \textcolor{blue}{OOM} / \textcolor{red}{OOM}&OOM / \textcolor{blue}{OOM} / \textcolor{red}{OOM}
    \\\cline{4-5}
&&FastGradClip&18 / \textcolor{blue}{25} / \textcolor{red}{33}&5.17 / \textcolor{blue}{5.45} / \textcolor{red}{5.61}
    \\\cline{4-5}
    
&VGG 11 / \textcolor{blue}{13} / \textcolor{red}{16}&Ghost (ours)&14 / \textcolor{blue}{25} / \textcolor{red}{29}&2.58 / \textcolor{blue}{3.30} / \textcolor{red}{3.41}
    \\\cline{4-5}
    &9M / \textcolor{blue}{9.4M} / \textcolor{red}{14.7M}
&Mixed (ours)&13 / \textcolor{blue}{18} / \textcolor{red}{23}&2.58 / \textcolor{blue}{2.76} / \textcolor{red}{2.84}
\\\cline{4-5}
&&Non-DP&5 / \textcolor{blue}{6} / \textcolor{red}{8}&2.54 / \textcolor{blue}{2.73} / \textcolor{red}{2.81}
    \\\hline
    \end{tabular}
    \caption{Time and memory of selected models on CIFAR10, with physical batch size 256. Additional models are in \Cref{tab:cifar10 extend}. Out of memory (OOM) means the total memory exceeds 16GB.}
    \label{tab:cifar10 fixed 256}
\end{table}



    
    
    

From \Cref{tab:cifar10 fixed 256} and the extended \Cref{tab:cifar10 extend}, we see a clear advantage of mixed ghost clipping: our clipping only incurs $\leq 1\%$ memory overhead than the regular training, and is the fastest DP training algorithm. In contrast on ResNet18, Opacus uses $5\times$ memory, and FastGradClip uses $2\times$ memory. Even the ghost clipping uses $1.2\times$ memory of regular training, while being slower than both Opacus and FastGradClip. Similar phenomenon is observed on ImageNet in \Cref{tab:imagenet}.


\subsection{Maximum batch size and throughput}
Importantly, the speed efficiency in \Cref{tab:cifar10 fixed 256} can be further boosted, if we use up the saved memory to increase the batch size. To stress test the maximum physical batch size and the throughput of each clipping method, we train ResNet \cite{he2016deep}, VGG \cite{simonyan2014very}, MobileNet\cite{howard2017mobilenets}, ResNeXt \cite{xie2017aggregated},AlexNet\cite{krizhevsky2014one},Wide-ResNet\cite{zagoruyko2016wide}, DenseNet\cite{huang2017densely} and ViTs on CIFAR10 and ImageNet, as summarized partially in \Cref{fig:max bs and throughput} and in \Cref{tab:imagenet}, respectively. For example, on VGG19 and CIFAR10, the mixed ghost clipping has a maximum batch size $18\times$ bigger (thus $3\times$ faster) than Opacus, $3\times$ bigger (thus $1.7\times$ faster) than FastGradClip, and $2\times$ bigger (thus $1.3\times$ faster) than the ghost clipping.
Similarly, on Wide-ResNet50 and ImageNet, the mixed ghost clipping has a maximum batch size $5\times$ bigger than Opacus, and $<0.3\%$ more memory costly than the non-private training.

\vspace{-0.2cm}
\begin{figure}[!htb]
    \centering
    \includegraphics[width=0.48\linewidth]{cifar_resnet_memory.pdf}
    \includegraphics[width=0.48\linewidth]{cifar_resnet_speed.pdf}
    \vspace{-0.2cm}
    \caption{Memory (left) and speed (right) comparison of DP clipping algorithms on CIFAR10.
   
    }
    \label{fig:max bs and throughput}
\end{figure}


\vspace{-0.3cm}
\subsection{Vision transformers with convolution on ImageNet scale}
\label{sec:vit}
\vspace{-0.2cm}

In addition to training large-scale CNNs such as ResNet152, we apply our mixed ghost clipping to train ViTs, which substantially outperform existing SOTA on CIFAR10 and CIFAR100. Notice that the ViTs are pretrained on ImageNet scale, by which we resize CIFAR images (from $32\times 32$ pixels to $224\times 224$ pixels).

It is worth mentioning that ViT \cite{dosovitskiy2020image} is originally proposed as a substitute of CNN. Hence it and many variants do not contain convolutional layers. Here we specifically consider the convolutional ViTs, including ScalableViT\cite{yang2022scalablevit}, XCiT\cite{ali2021xcit}, Visformer\cite{chen2021visformer}, CrossVit\cite{chen2021crossvit}, NesT\cite{zhang2022nested}, CaiT\cite{touvron2021going}, DeiT\cite{touvron2021training}, BEiT\cite{bao2021beit}, PiT\cite{heo2021rethinking}, and ConViT\cite{d2021convit}.

Performance of these ViTs on CIFAR10 and CIFAR100 are listed in \Cref{app:ViT} for a single-epoch DP training and several ViTs already beat previous SOTA, even though we do not apply additional techniques as in \cite{de2022unlocking,mehta2022large} (e.g. learning rate schedule or random data augmentation).

\begin{table}[!htb]
    \centering
\def0.9{0.9}
\begin{tabular}{lc@{\hskip 15pt}c@{\hskip 15pt}c}
\toprule [0.15em]
 &
 \multirow{2}{*}{$\varepsilon$}
 &
 \multicolumn{2}{c}{Test Accuracy (\%)} \\
 \cmidrule{3-4}
 &  & CIFAR-10 & CIFAR-100 \\
 \midrule [0.1em]
 \multirow{2}{*}{Yu et al. \cite{yu2021not} (ImageNet1k)} & 1 & 94.3 & --  \\
 & 2 & 94.8 & --  \\
 \midrule
 Tramer et al. \cite{tramer2020differentially} (ImageNet1k)& 2 & 92.7 & --  \\
 \midrule
 \multirow{2}{*}{De et al. \cite{de2022unlocking}} & 1 & 94.8 & 67.4\\
 & 2 & 95.4 & 74.7 \\
 \multirow{2}{*}{(ImageNet1k)}& 4 & 96.1 & 79.2 \\
 & 8 & 96.6 & 81.8 \\
  \midrule
\multirow{2}{*}{Our CrossViT base (104M params)} & 1 & 95.5 & 71.9  \\
 & 2 & 96.1  & 74.3\\
 \multirow{2}{*}{(ImageNet1k)}& 4 & 96.2 & 76.7\\
 & 8 & 96.5  &77.8 \\
  \midrule
\multirow{2}{*}{Our BEiT large (303M params)} & 1 & 96.7& 83.0 \\
 & 2 & 97.1&86.2 \\
 \multirow{2}{*}{(ImageNet21k)}& 4 & 97.2& 87.7 \\
 & 8 & 97.4 &88.4 \\
 \bottomrule [0.15em]
\end{tabular}
    \caption{CIFAR-10 and CIFAR-100 test accuracies when fine-tuning with DP-SGD. We train CrossViT base for 5 epochs, lr 0.002, optim. We train BEiT large for 3 epochs lr 0.001. Here batch size is 1000 and clipping norm is 0.1. `( )' indicates the pretrained datasets.}
    \label{table:imagenet_cifar_transfer}
\vspace{-0.7cm}
\end{table}

By training multiple epochs with best performing ViTs in \Cref{tab:cifar10ViT} and \Cref{tab:cifar100ViT}, we achieve new SOTA under DP in \Cref{table:imagenet_cifar_transfer}, with substantial improvement especially for strong privacy guarantee (e.g. $\epsilon<2$). Our DP training is at most $2\times$ slower and $10\%$ more memory expensive than the non-private training, even on BEiT large, thus significantly improving the $9\times$ slowdown reported in \cite{de2022unlocking}.

\vspace{-0.4cm}
\begin{figure}[!htb]
    \centering
\hspace{-0.8cm}
\includegraphics[width=0.52\linewidth]{images/CIFAR100_ViT_memory.pdf}
\hspace{-0.7cm}
\includegraphics[width=0.52\linewidth]{images/CIFAR100_ViT_speed.pdf}   
\hspace{-0.8cm}
\vspace{-0.2cm}
\caption{Memory (left) and speed (right) comparison of DP and non-DP training on CIFAR100 with convolutional ViTs. Note that CIFAR10 has an almost identical pattern.}
\label{fig:CIFAR ViT}
\end{figure}



\section{Discussion}
\vspace{-0.2cm}
We have shown that DP training can be efficient for large CNNs and ViTs with convolutional layers. For example, in comparison to non-private training, we reduce the training time to $<2\times$ and the memory overhead to $<10\%$ for all vision models examined (up to 303.4 million parameters), including BEiT that achieves SOTA accuracy on CIFAR100 ($+15.6\%$ absolutely at $\epsilon=1$). We have observed that for many tasks and large CNNs and ViTs, the memory overhead of DP training can be as low as less than 1\%.

We emphasize that our DP training only improves the efficiency, not affecting the accuracy, and therefore is generally applicable, e.g. with SOTA data augmentations in \cite{de2022unlocking}. With efficient training algorithms, we look forward to applying DP CNNs to generation tasks \cite{goodfellow2014generative} , seq-to-seq learning \cite{gehring2017convolutional}, text classification \cite{zhang2015character}, reinforcement learning \cite{mnih2013playing}, and multi-modal learning. Further reducing time complexity and prioritizing speed in DP training is another future direction.

In particular, our layerwise decision principle in \eqref{eq:memory priority} highlights the advantages of ghost clipping when $T=HW$ is small. This advocates the use of large kernel sizes in DP learning, as they shrink the hidden feature aggressively, and have been shown to be highly accurate on non-private tasks \cite{he2016deep,ding2022scaling,peng2017large}.

\bibliographystyle{abbrv}
