# H-Net: Unsupervised Attention-based Stereo Depth Estimation Leveraging
Epipolar Geometry

Baoru Huang1
Baoru Huang and Jian-Qing Zheng contribute equally to this paper Jian-Qing
Zheng2∗<EMAIL_ADDRESS>Stamatia Giannarou1 Daniel S. Elson1
1The Hamlyn Centre for Robotic Surgery, Imperial College London, U.K.
2The Kennedy Institute of Rheumatology, University of Oxford, U.K

###### Abstract

Depth estimation from a stereo image pair has become one of the most explored
applications in computer vision, with most of the previous methods relying on
fully supervised learning settings. However, due to the difficulty in
acquiring accurate and scalable ground truth data, the training of fully
supervised methods is challenging. As an alternative, self-supervised methods
are becoming more popular to mitigate this challenge. In this paper, we
introduce the H-Net, a deep-learning framework for unsupervised stereo depth
estimation that leverages epipolar geometry to refine stereo matching. For the
first time, a Siamese autoencoder architecture is used for depth estimation
which allows mutual information between the rectified stereo images to be
extracted. To enforce the epipolar constraint, the mutual epipolar attention
mechanism has been designed which gives more emphasis to correspondences of
features which lie on the same epipolar line while learning mutual information
between the input stereo pair. Stereo correspondences are further enhanced by
incorporating semantic information to the proposed attention mechanism. More
specifically, the optimal transport algorithm is used to suppress attention
and eliminate outliers in areas not visible in both cameras. Extensive
experiments on KITTI2015 and Cityscapes show that our method outperforms the
state-of-the-art unsupervised stereo depth estimation methods while closing
the gap with the fully supervised approaches.

##  1 Introduction

Humans are remarkably capable of inferring the 3D structure of a real world
scene even over short timescales. For example, when navigating along a street,
we are able to locate obstacles and vehicles in motion and avoid them with a
fast response time. Years of substantial interest in geometric computer vision
has not accomplished comparable modeling capabilities to humans for various
real-world scenes where reflections, occlusions, non-rigidity and textureless
areas exist. So what can human ability be attributed to? A central concept is
that humans learn the regularities of the world while interacting with it,
moving around, and observing vast quantities of scenes. Consequently, we
develop a rich, consistent and structural understanding of the world, which is
utilized when we perceive a new scene. Our binocular vision is a supporting
feature, from which the brain can not only build disparity maps, but can also
combine to obtain structural information. These two ideas prompt one of the
fundamental problems in computer vision — depth estimation — whose quality has
a direct influence on various application scenarios, such as autonomous
driving, robotic navigation, augmented reality and 3D reconstruction.

Thanks to advanced deep learning techniques, the performance of depth
estimation methods has improved significantly over the last few years. Most
previous work relies on ground-truth depth data and considers deep
architectures for generating depth maps in a supervised manner [5, 17, 26,
39]. However, collecting vast and varied training datasets with accurate per-
pixel ground truth depth data for supervised learning is a formidable
challenge. To overcome this limitation, some recent works have shown that
self-supervised methods are instead able to effectively tackle the depth
estimation task [10] [33]. We are particularly inspired by the approaches
proposed in [11, 45, 8, 15] where they took view synthesis as supervisory
signals to train the network and exploited differences between the original
input, synthesized view, and left and right disparity results as penalties
(i.e. a photometric image reconstruction cost, a left-right consistency cost
and a disparity smoothness cost) to force the system to generate accurate
disparity maps. However, although some works have tried to emphasize the
complementary information in the stereo image pair and used sharing weights
when extracted features from input images [33] [2], the contextual information
between the multiple views — especially some strong feature matches — lie on
the epipolar line, and this information has not been effectively explored and
exploited.

In this paper, we follow the unsupervised learning setting and introduce the
H-Net, a novel end-to-end trainable network for depth estimation given
rectified stereo image pairs. The proposed H-Net effectively fuses the
information in the stereo pair and combines epipolar geometry with learning-
based depth estimation approaches. In summary, our main contributions in this
paper are:

  * •

We design a Siamese encoder-Siamese decoder network architecture, which fuses
the complementary information in the stereo image pairs while enhancing the
communication between them. To the best of our knowledge, this is the first
time this architecture is used for depth estimation.

  * •

We propose a mutual epipolar attention module to enforce the epipolar
constraint in feature matching and emphasise the strong relationship between
the features located along the same epipolar lines in rectified stereo image
pairs.

  * •

We further enhance the proposed attention module by using the optimal
transport algorithm to incorporate in a novel fashion semantic information and
filter out outlier feature correspondences.

We demonstrate the effectiveness of our approach on the challenging KITTI [9]
and Cityscapes datasets [3]. Compared to previous approaches, the H-Net
achieves state-of-the-art results.

##  2 Related work

Estimating depth maps from stereo images has been explored for decades [1].
Accurate stereo depth estimation plays a critical role in perceiving the 3D
geometric configuration of scenes and facilitating a variety of computer
vision applications in the real world [16]. Recent work has shown that depth
estimation from a stereo image pair can be effectively tackled by learning-
based methods with convolutional neural networks (CNNs) [2].

###  2.1 Supervised Depth Estimation

A pyramid stereo matching network was proposed in [2], where spatial pyramid
pooling and dilated convolution were adopted to enlarge the receptive fields,
while a stacked hourglass CNN was designed to further boost the utilization of
global context information. Duggal _et al_. [4] proposed a differentiable
PatchMatch module to abandon most disparities without requiring full cost
volume evaluation, and thus the specific range to prune for each pixel could
be learned. Kusupati _et al_. [20] improved the depth quality by leveraging
the predicted normal maps and a normal estimation model, and proposed a new
consistency loss to refine the depths from depth/normal pairs.

The above methods are fully supervised and rely on having large amounts of
accurate ground truth depth for training. However, this is challenging to
obtain data in various real-world settings [44]. Synthetic training data is a
potential solution [7] [28], but still requires manual curation for every new
application scenario.

###  2.2 Unsupervised Depth Estimation

Due to the lack of per-pixel ground truth depth data, self-supervised depth
estimation is an alternative, where image reconstruction is the supervisory
signal during training [11]. The input for this type of model is usually a set
of images, either as stereo pairs [33][32] or as monocular sequences [45]
[15].

Gard _et al_. [8] proposed an approach using a calibrated stereo camera pair
setup for unsupervised monocular depth estimation, in which depth was
generated as an intermediate output and the supervision signal came from the
reconstruction combining the counterpart image in a stereo pair. Godard _et
al_. [10] extended this work by using forward and backward reconstructions of
different image views while adding an appearance matching loss and multi-scale
loss to the model. Per-pixel minimum reprojection loss and auto-masking were
explored in [11], which allowed the network to ignore objects moving at the
same velocity as the camera or frames captured when the camera was static,
with further improved results. Johnston _et al_. [15] introduced discrete
disparity prediction and applied self-attention to the depth estimation
framework, providing a more robust and sharper depth estimation map.

It has been shown that training with an added binocular color image could help
single image depth estimation by posing it as an image reconstruction problem
without requiring ground truth [10] [11]. Andrea _et al_. [33] showed that the
depth estimation results could be effectively improved within an adversarial
learning framework, with a deep generative network that learned to predict the
disparity map for a calibrated stereo camera using a wrapping operation.

In the multi-view (stereo) depth estimation task, it is naturally to employ
complementary features from different views to establish the geometric
correspondences. Zhou _et al_. [44] presented a framework that learned stereo
matching costs without human supervision, in which the network parameters were
updated in an iterative manner and a left-right check was applied to guide the
training procedure. Joung _et al_. [16] proposed a framework to compute
matching cost in an unsupervised setting, where the putative positive samples
in every training iteration were selected by exploiting the correspondence
consistency between two stereo images. Although these methods tried to explore
the feature relationship between the stereo images, the concrete matching
matrix have not been effectively exploited and been applied to the learning
procedure, which leads to a cost of details and a waste of geometric
information, especially the strong constraints on the epipolar line.

Figure 1: The H-Net architecture. Figure 2: Optimal Transport based Mutual
Epipolar Attention (OT-MEA) block combines OT retrieving (Eq. 4) into the MEA
module (Eq. 1).

##  3 Method

Here, we describe the details of the process of depth prediction using the
proposed H-Net.

###  3.1 H-Net architecture

In this paper, the encoder-decoder structure Monodepth2 [11] was adopted as
the fundamental backbone, based on the U-Net [35]. As shown in Fig. 1, the
proposed architecture consisted of a double-branch encoder and a double-branch
decoder. To make the network compact, similar to [2] and [33], a Siamese
Encoder - Siamese Decoder (SE-SD) structure was designed with shared weights
between the two branches in both the encoder and the decoder. To our
knowledge, this is the first time a SE-SD is used for stereo depth estimation
enabling the extraction of mutual information from the pair of input images.

The Siamese Encoder (SE) of H-net included two branches of Resnet18 [13] with
shared trainable parameters. The left and right rectified images
$\textit{{I}}^{\rm l},\textit{{I}}^{\rm r}\in\mathbb{R}^{3\times h_{0}\times
w_{0}}$ were fed into each branch of the SE to extract common features from
the input images, where $h_{0},w_{0}$ denotes the image size. The outputs of
the three deeper Residual-down-sampling (Res-down) blocks in the SE were
interconnected with a novel mutual attention block proposed in this work — the
so-called Optimal Transport-based Mutual Epipolar Attention (OT-MEA) block,
shown in Fig. 2 and explained in detail below.

The abstract latent features from the encoder were fused in the middle part by
concatenating the feature maps extracted from each SE block between the two
branches. Each concatenated map is then convolved by two separate convolution
layers with different trainable parameters.

The decoder took the fused latent features as inputs and generated sigmoid
outputs for each input image similar to [10] and [11]. It was composed of the
same number of Residual-up-sampling (Res-up) blocks as Res-down to recover the
full resolution, as well as OT-MEA blocks inserted in the first three Res-up
blocks. Each sigmoid output $\Omega$ of the decoder was transformed to scene
depth as $D=1/(a\Omega+b)$. The parameters a and b were selected to constrain
depth $D$ between 0.1 and 100 units.

###  3.2 Mutual Epipolar Attention

State-of-the-art deep learning methods for stereo depth estimation have not
considered the epipolar constraint when estimating feature correspondences. In
this work, we introduce a mutual attention mechanism to give more emphasis to
features correspondences which lie on the same epipolar line.

Recently, Wang et al. [38] proposed the Non-Local (NL) block which allowed
them to exploit global-range attention in an image sequence. This was then
extended with the introduction of the Mutual NL (MNL) block [43] to explore
the mutual relationships between different inputs in multi-view vision.
However, global-range feature matching in the NL and MNL blocks suffers from
the high number of parameters, memory requirement and training time.
Furthermore, these blocks can be misled by repeated textures in the scenes.

To overcome the above limitations, we designed the Mutual Epipolar Attention
(MEA) module to constrain feature correspondences to the same epipolar line
between a pair of rectified stereo images. Here, MEA was defined as:

$\left\\{\begin{array}[]{cc}\textbf{{Y}}^{\rm l\to r}:=\Psi({\textbf{{X}}^{\rm
l}})\otimes\Phi({\textbf{{X}}^{\rm l}},{\textbf{{X}}^{\rm r}})\\\
\textbf{{Y}}^{\rm r\to l}:=\Psi({\textbf{{X}}^{\rm
r}})\otimes\Phi({\textbf{{X}}^{\rm r}},{\textbf{{X}}^{\rm
l}})\end{array}\right.$ (1)

where $\otimes$ denotes the batch matrix multiplication, $\textbf{{X}}^{\rm
l},\textbf{{X}}^{\rm r}\in\mathbb{R}^{h\times c\times w}$ denote the
transported and reshaped input signals from the two branches,
$\textbf{{Y}}^{\rm l\to r},\textbf{{Y}}^{\rm r\to l}\in\mathbb{R}^{h\times
c\times w}$ are the output signals from the MEA block.
$\Phi:\mathbb{R}^{h\times c\times w}\times\mathbb{R}^{h\times c\times
w}\to\mathbb{R}^{h\times w\times w},(\textbf{{X}}^{\rm 1},\textbf{{X}}^{\rm
2})\mapsto\textbf{{M}}^{1\to 2}$ is a pair-wise matching function, the so
called retrieval function, which evaluates the compatibility between the two
inputs. $\Psi:\mathbb{R}^{h\times c\times w}\to\mathbb{R}^{h\times c\times
w},\textbf{{X}}\mapsto\textbf{{V}}$ is a unary function which maps vectors
from one feature space to another which is essential for fusion.

Following the settings in [38], the Embedded Gaussian (EG) similarity
representation was used to define our matching function:

$\Phi_{\rm EG}(\textbf{{X}}^{1},\textbf{{X}}^{2}):={\rm
softmax}(\mathcal{C}_{1}({{\textbf{{X}}^{1}})^{\top}\otimes\mathcal{C}_{2}(\textbf{{X}}^{2}}))$
(2)

where $\mathcal{C}$ is the $1\times 1$ convolution, and was also used in the
unary function for vector mapping:

$\Psi:=\mathcal{C}$ (3)

In our experimental work, the EG-based MEA and MNL modules were compared and
denoted as EG-MEA and EG-MNL, respectively.

###  3.3 Optimal transport based mutual attention

In stereo vision, the input images have been captured from cameras at
different positions and view angles making the field of view of the two images
sightly different. This can cause outliers in depth estimation due to
incorrect feature correspondences in the areas which are not visible to both
cameras. To eliminate outliers in these areas, we further enhanced our
proposed MEA module to suppress the contribution of correspondences in these
occluded areas during feature matching. The EG similarity representation
defined in Eq.(2) cannot achieve this because all the areas of the input
signals are equally considered.

For this purpose, we formulated the matching task in Eq.(1) as an optimal
transport (OT) problem as it has already been proven that OT improves semantic
correspondence [24]. Thus, a new OT-based retrieval function is further
proposed, tailored to our stereo depth estimation problem:

$\begin{array}[]{l}\Phi_{\rm
OT}(\textbf{{X}}^{1},\textbf{{X}}^{2}):=\mathop{\arg\min}\limits_{\textbf{{M}}}{\|\textbf{{M}}\odot{\rm
e}^{1-\mathcal{C}^{\prime}_{1}({{\textbf{{X}}^{1}})^{\top}\otimes\mathcal{C}^{\prime}_{2}(\textbf{{X}}^{2}})}\|}_{1}\\\
{\rm
s.t.}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}\textbf{u}\otimes\textbf{{M}}=\Theta(\textbf{{X}}^{2}),~{}\textbf{u}\otimes\textbf{{M}}^{\top}=\Theta(\textbf{{X}}^{1})\end{array}$
(4)

where $\odot$ denotes a Hadamard product, $\mathcal{C}^{\prime}$ is a sequence
operation of convolution and channel-wise Euclidean normalization,
$\textbf{u}\in\\{1\\}^{h\times 1\times w}$ is a matrix with all elements equal
to 1. $\Theta:\mathbb{R}^{h\times c\times w}\to\mathbb{R}^{h\times 1\times
w},\textit{{X}}\mapsto\textbf{{U}}$ is the sequence operation of convolution,
ReLU activation and pixel-wise L1-normalization to generate the transported
mass of pixels U. The matrix M is the variable to be optimised and represents
the optimal matching matrix $\textbf{{M}}^{1\to 2}$.

Here, OT-based matching in Eq. (4) assigns to each pixel the sum of each
column of the similarity weights in matching matrix $\textbf{{M}}^{1\to 2}$,
which is constrained by the mass:

$\left\\{\begin{array}[]{l}U_{ij}^{1}=\sum_{k}{M_{ijk}^{1\to 2}}\\\
U_{ik}^{2}=\sum_{j}{M_{ijk}^{1\to 2}}\end{array}\right.,\forall
i,j,k\in\mathbb{Z},i\leq\textit{h},j,k\leq\textit{w}$ (5)

where $U_{ij}^{1}$, $U_{ik}^{2}$ and ${M_{ijk}^{1\to 2}}$ are the elements of
the $\textbf{{U}}^{1}$, $\textbf{{U}}^{2}$ and $\textbf{{M}}^{1\to 2}$
respectively indexed by $i,j,k$. In contrast to the equal consideration by EG-
based matching in Eq. (2), varying weights are assigned to different
correspondences in Eq. (5), determined by the latent semantic messages
forwarded from the input signals. This enables the OT module to suppress the
outliers and focus on correspondences with more mass which lie on the semantic
areas.

In this paper, since Eq. (4) is a convex optimization problem, the Sinkhorn
algorithm is used to obtain the numerical solution of this OT problem [24]. OT
matching based MEA is denoted as OT-MEA and Fig. 2 illustrates the
implementation sketch of the OT-MEA used in H-net. Both MEA and OT modules can
be used separately or in combination and we present their impact with an
ablation study in Section 5.2. OT-MEA was also compared in our experimental
work to the OT matching based MNL, denoted as OT-MNL.

###  3.4 Self-Supervised Training

For the left and right input images $\textit{{I}}^{\rm l},\textit{{I}}^{\rm
r}\in\mathbb{R}^{3\times h_{0}\times w_{0}}$, the sigmoid outputs of the H-Net
were transformed to depth maps $\textit{{D}}^{\rm l},\textit{{D}}^{\rm
r}\in\mathbb{R}^{1\times h_{0}\times w_{0}}$ as explained in Section 3.1. By
combining one of the depth maps (e.g $\textit{{D}}^{\rm l}$) and the count-
part input image ($\textit{{I}}^{\rm r}$), we were able to reconstruct the
initial image ($\textit{{I}}^{\rm{l*}}$) using the re-projection sampler [14].
Here we used the left image $\textit{{I}}^{\rm l}$ as an example to present
the supervisory signal and loss components. The final loss function included
the loss terms for both left and right images. The similarity between the
input image $\textit{{I}}^{\rm l}$ and the reconstructed image
$\textit{{I}}^{\rm{l*}}$ provides our supervisory signal. Our photometric
error function $\mathcal{L}^{l}_{ap}$ was defined as the combination of
$L_{1}$-norm and structural similarity index (SSIM) [11]:

$\mathcal{L}_{\rm ap}^{\rm l}=\frac{1}{N}\sum_{i,j}\frac{\gamma}{2}(1-{\rm
SSIM}(I_{ij}^{\rm l},I_{ij}^{l*}))+(1-\gamma){\|I_{ij}^{\rm
l}-I_{ij}^{l*}\|}_{1}$ (6)

where, $N$ denotes the number of pixels and $\gamma$ is the weighting for
$L_{1}$-norm loss term. To improve the predictions around object boundaries,
an edge-aware smoothness term $\mathcal{L}_{ds}$ was applied [11, 15]:

$\mathcal{L}_{\rm ds}^{\rm
l}=\frac{1}{N}\sum_{i,j}|\partial_{x}(\textit{d}_{ij}^{\rm{l*}})|e^{-|\partial_{x}{\textit{I}}_{ij}^{\rm
l}|}+|\partial_{y}(\textit{d}_{ij}^{\rm{l*}})|e^{-|\partial_{y}{\textit{I}}_{ij}^{\rm
l}|}$ (7)

where ${d^{l*}=d^{l}\sqrt{d^{l}}}$ represents the mean-normalized inverse of
depth ($1/\textbf{{D}}$) which aims at preventing shrinking of the depth
prediction [37].

To overcome the gradient locality of the re-projection sampler, we adopted the
multi-scale estimation method presented in [11], which first upsamples the low
resolution depth maps (from the intermediate layers) to the input image
resolution and then reprojects and resamples them. The errors were computed at
the higher input resolution. Finally, the photometric loss and per-pixel
smoothness loss were balanced by the smoothness term $\lambda$ and the total
loss was averaged over each scale (s), branch (left and right) and batch:

$\begin{split}\mathcal{L}_{\rm
total}&=\frac{1}{2m}\sum_{s=1}^{m}(\mathcal{L}_{s}^{\rm
l}+\mathcal{L}_{s}^{\rm r})\\\
&=\frac{1}{2m}\sum_{s=1}^{m}\big{(}(\mathcal{L}_{\rm ap}^{\rm
l}+\lambda\mathcal{L}_{\rm ds}^{\rm l})+(\mathcal{L}_{\rm ap}^{\rm
r}+\lambda\mathcal{L}_{\rm ds}^{\rm r}))\end{split}$ (8)

##  4 Experiments

Method | Train | Abs Rel | Sq Rel | RMSE | RMSE log | ${\delta<1.25}$ | $\delta<1.25^{2}$ | ${\delta<1.25^{3}}$
---|---|---|---|---|---|---|---|---
Eigen [5] | D | 0.203 | 1.548 | 6.307 | 0.282 | 0.702 | 0.890 | 0.890
Liu [23] | D | 0.201 | 1.584 | 6.471 | 0.273 | 0.680 | 0.898 | 0.967
AdaDepth [19] | D* | 0.167 | 1.257 | 5.578 | 0.237 | 0.771 | 0.922 | 0.971
Kuznietsov [21] | DS | 0.113 | 0.741 | 4.621 | 0.189 | 0.862 | 0.960 | 0.986
DVSO [41] | D*S | 0.097 | 0.734 | 4.442 | 0.187 | 0.888 | 0.958 | 0.980
SVSM FT [27] | DS | 0.094 | 0.626 | 4.252 | 0.177 | 0.891 | 0.965 | 0.984
Guo [12] | DS | 0.096 | 0.641 | 4.095 | 0.168 | 0.892 | 0.967 | 0.986
DORN [6] | D | 0.072 | 0.307 | 2.727 | 0.120 | 0.932 | 0.984 | 0.994
UnDeepVO [22] | MS | 0.183 | 1.730 | 6.57 | 0.268 | - | - | -
Zhan FullNYU [42] | D*MS | 0.135 | 1.132 | 5.585 | 0.229 | 0.820 | 0.933 | 0.971
EPC++ [25] | MS | 0.128 | 0.935 | 5.011 | 0.209 | 0.831 | 0.945 | 0.979
Monodepth2 [11] | MS | 0.106 | 0.818 | 4.750 | 0.196 | 0.874 | 0.957 | 0.979
Monodepth2 (1024 × 320) [11] | MS | 0.106 | 0.806 | 4.630 | 0.193 | 0.876 | 0.958 | 0.980
Yang [40] | MS | 0.099 | 0.763 | 4.485 | 0.185 | 0.885 | 0.958 | 0.979
Garg [8]† | S | 0.152 | 1.226 | 5.849 | 0.246 | 0.784 | 0.921 | 0.967
Monodepth R50 [10]† | S | 0.133 | 1.142 | 5.533 | 0.230 | 0.830 | 0.936 | 0.970
StrAT [29] | S | 0.128 | 1.019 | 5.403 | 0.227 | 0.827 | 0.935 | 0.971
3Net (R50) [34] | S | 0.129 | 0.996 | 5.281 | 0.223 | 0.831 | 0.939 | 0.974
3Net (VGG) [34] | S | 0.119 | 1.201 | 5.888 | 0.208 | 0.844 | 0.941 | 0.978
Pilzer [33] | S | 0.152 | 1.388 | 6.016 | 0.247 | 0.789 | 0.918 | 0.965
SuperDepth + pp [31] (1024 × 382) | S | 0.112 | 0.875 | 4.958 | 0.207 | 0.852 | 0.947 | 0.977
Monodepth2 [11] | S | 0.109 | 0.873 | 4.960 | 0.209 | 0.864 | 0.948 | 0.975
Monodepth2 (1024 × 320) [11] | S | 0.107 | 0.849 | 4.764 | 0.201 | 0.874 | 0.953 | 0.977
PFN [32] | S | 0.102 | 0.802 | 4.657 | 0.196 | 0.882 | 0.953 | 0.977
H-Net (Ours) | S | 0.094 | 0.600 | 4.197 | 0.174 | 0.909 | 0.964 | 0.983
H-Net (Ours) Full Eigen | S | 0.076 | 0.607 | 4.025 | 0.166 | 0.918 | 0.966 | 0.982

Table 1: Quantitative results. Comparison of our proposed H-Net to existing methods on KITTI2015 [9] using the Eigen split unless marked with ‘Full Eigen’, which indicates the full Eigen dataset. The best result in each category are presented in bold while the second best results are underlined. All results here are shown without post-processing [10] unless marked with -+pp. The supervision mode for each method is indicated in the Train: D-Depth supervision, D*-Auxiliary depth supervision, M-Self-supervised mono supervision and S-self-supervised stereo supervision. Symbol † represents the new results from github. Metrics labeled by red mean lower is better while labeled by blue mean higher is better. Left input |  |  |  |
---|---|---|---|---
Right input |  |  |  |
Monodepth[10] |  |  |  |
Monodepth2(S)[11] |  |  |  |
Pilzer[32] |  |  |  |
H-NET(ours) |  |  |  |
Left input |  |  |  |
Right input |  |  |  |
Monodepth[10] |  |  |  |
Monodepth2(S)[11] |  |  |  |
Pilzer[32] |  |  |  |
H-NET(ours) |  |  |  |
Figure 3: Qualitative results on the KITTI Eigen split. The depth prediction
are all for the left input image. Our H-Net in the last row generates the
depth maps with more details and performs better on distinguishing different
parts in one object, i.e. buildings, kerbs bushes and trees, which reflects
the superior quantitative results in Table 1.

Setting | SE-SD | MEA | OT | Abs Rel | Sq Rel | RMSE | RMSE log | ${\delta<1.25}$ | $\delta<1.25^{2}$ | ${\delta<1.25^{3}}$
---|---|---|---|---|---|---|---|---|---|---
Backbone [11] | ✗ | ✗ | ✗ | 0.109 | 0.873 | 4.960 | 0.209 | 0.864 | 0.948 | 0.975
SE-SD | ✓ | ✗ | ✗ | 0.096 | 0.700 | 4.403 | 0.189 | 0.894 | 0.960 | 0.979
SE-SD w/ EG-MNL | ✓ | ✗ | ✗ | 0.086 | 0.701 | 4.289 | 0.178 | 0.912 | 0.964 | 0.980
SE-SD w/ EG-MEA | ✓ | ✓ | ✗ | 0.080 | 0.665 | 4.086 | 0.173 | 0.917 | 0.964 | 0.981
SE-SD w/ OT-MNL | ✓ | ✗ | ✓ | 0.082 | 0.725 | 4.279 | 0.180 | 0.917 | 0.962 | 0.979
H-Net (Ours) | ✓ | ✓ | ✓ | 0.076 | 0.607 | 4.025 | 0.166 | 0.918 | 0.966 | 0.982

Table 2: Ablation Study. Results for different variants of our model (H-Net) on KITTI2015 [9] using full Eigen dataset with comparison to our backbone Monodepth2 [11]. We evaluate the impact of the Siamese encoder- Siamese decoder (SE-SD), mutual epipolar attention (MEA) and optimal transport (OT). Metrics labeled by red mean lower is better while labeled by blue mean higher is better Setting | Num of Parameters
---|---
SE-SD (baseline) | 30.7M
EG-MNL | +0.3M(1%)
EG-MEA | +0.6M(2%)
OT-MNL | +0.3M(1%)
OT-MEA (Ours) | +0.6M(2%)
Table 3: Number of Parameters (M:million) for our models with different settings of the mutual attention module. Left input |  |  |  |
---|---|---|---|---
Right input |  |  |  |
H-Net |  |  |  |
Ground Truth |  |  |  |
Figure 4: Qualitative results on the Cityscapes dataset. Our H-Net generates
very close predictions compared with the ground truth.

We trained and evaluated the proposed H-Net on the KITTI2015 [9] with the full
Eigen and Eigen split dataset [5]. For the full Eigen setting, there were
22600 pairs for training and 888 for validation while for Eigen split, there
were 19905 training pairs and 2212 validation pairs. The same intrinsics were
used for all images. The principal point of the camera was set to the image
center and the focal length was the average of all the focal lengths in KITTI.
All of the images were rectified and the transformation between the two stereo
images was set to be a pure horizontal translation of fixed length. During the
evaluation, only depths up to a fixed range of 80m were evaluated per standard
practice [5, 8, 10, 11]. As our backbone model, we used Monodepth2 [11] and
kept the original ResNet18 [13] as the encoder. Furthermore, we also trained
and tested our H-Net on the Cityscapes dataset [3] to verify its
generalisability.

We compared our results with state-of-the-art supervised and self-supervised
approaches and both qualitative and quantitative results were generated for
comparison. To better understand how each component influenced the overall
performance, we conducted an ablation study by turning various components of
the model off, in turn.

###  4.1 Implementation Details

Our H-Net model was trained using the PyTorch library [30], with an
input/output resolution of $640\times 192$ and a batch size of 8. The
$L_{1}$-norm loss term $\gamma$ was set to 0.85 and the smoothness term
$\lambda$ was 0.001. The number of scales $m$ was set to 4, which meant that
totally we had 4 multi scales and there were 4 output scales as well with
resolutions $\frac{1}{2^{0}}$, $\frac{1}{2^{1}}$, $\frac{1}{2^{2}}$ and
$\frac{1}{2^{3}}$ of the input resolution. The model was trained for 20 epochs
using the Adam optimizer [18] requiring approximately 14 hours on a single
NVIDIA 2080Ti GPU. We set the learning rate to $10^{-4}$ for the first 15
epochs and dropped it to $10^{-5}$ for the remainder. As with previous papers
[11], we also used a Resnet encoder with pre-trained weights on ImageNet [36],
which proved able to improve the overall accuracy of the depth estimation and
to reduce the training time [11, 15].

##  5 Results and Discussion

###  5.1 KITTI Results

The qualitative results and quantitive results on the KITTI Eigen split are
shown in Table 1 and Figure 4. In Table 1, it can be seen that the proposed
H-Net outperforms all existing state-of-the-art self-supervised methods by a
significant margin. Compared with other approaches that applied direct
supervision signals (supervised methods), the model was still competitive. As
our H-Net takes stereo image pairs as the input, in contrast with [11] and
[15], we did not need to remove static frames. However, to make the comparison
fair, we used both full Eigen and Eigen split dataset to make the dataset
consistent with other methods. Among all the evaluation measures, the best and
the second best ones were produced by our H-Net model, which indicates that
our model can learn from the geometry constraints and benefits from the
optimal transport solution, achieving state-of-the-art depth predictions. For
the quantitative results, we can see that the depth maps generated by our
model contained more details, i.e. the structural characteristics of
buildings, protruding kerbs, bushes, and trees. Besides, our model could
effectively distinguish different parts of every object, for example, the
upper part of the tree is no longer uniform but is full of outlines and
details.

###  5.2 KITTI Ablation Study Results

The results of the ablation study on the KITTI dataset are shown in Table 2.
We can see that the backbone Monodepth2 model [11] performed the worst without
any of our contributions but by changing the architecture to a Siamese
encoder- Siamese decoder, the evaluation measures steadily improved. The
reason might be that fusing the complementary information between the stereo
image pair gave the framework higher chance to generate accurate predicted
depth maps. Our MEA and OT modules were all incorporated in the SE-SD
architecture. Row 4 shows that the addition of MEA benefits the depth
estimation performance in all the evaluation measures, especially on metrics
that are sensitive to large depth errors e.g. RMSE. The significantly large
improvement of the SE-SD architecture with MEA, is likely due to the epipolar
constraint, which allowed the network to learn strong correspondences limited
on the same epipolar lines in the rectified stereo images. The impact of the
OT-MNL is presented in Row 5, compared to the SE-SD we still can notice a
dramatic increase in most of the evaluation metrics. The reason might be that
the optimal transport algorithm further improved the MEA by increasing the
correct correspondence weights, merging the semantic features while
suppressing outliers. In the last row, by combining the backbone with all of
our components, the effectiveness of the final framework was significantly
improved, as expected, and state-of-the-art results were observed. Besides,
although our OT-MEA module was inspired by the MNL, our results outperformed
the same SE-SD architecture with MNL. Apart from the performance evaluation
measures, we also estimated the number of parameters for each of the examined
settings. While all of our proposed components contributed to the overall
performance in the self-supervised depth estimation task, the number of
parameters was barely increased. We can see from Table 3 that our OT-MEA
module cost 0.6 million (2.0%) additional parameters compared with the pure
SE-SD architecture.

###  5.3 Cityscapes results

The performance of H-Net has been further evaluated on the Cityscape dataset.
The results in Figure 4 show the accuracy of the depth estimated by H-Net
compared to the ground truth, with detailed reconstructions of objects such as
cars, human, and trees. More experimental results could be found in the
supplementary material.

##  6 Conclusion

In this paper we presented a novel network, the H-Net, for self-supervised
depth estimation, achieving state-of-the-art depth prediction. By designing
the Siamese encoder-Siamese decoder architecture, exploiting the mutual
epipolar attention, and formulating the optimal transport problem, both the
global-range correspondence between stereo image pairs and strongly related
feature correspondences satisfying the epipolar constraint in the rectified
images were effectively explored and fused. We showed how this benefited the
overall performance on public datasets and how together they gave a large
improvement in evaluation measures, indicating that the model effectively
tackled the limits of other self-supervised depth estimation methods and
closed the gap with supervised approaches.

## References

  * [1] Stephen T Barnard and Martin A Fischler.  Computational stereo.  ACM Computing Surveys (CSUR), 14(4):553–572, 1982.
  * [2] Jia-Ren Chang and Yong-Sheng Chen.  Pyramid stereo matching network.  In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, pages 5410–5418, 2018.
  * [3] Marius Cordts, Mohamed Omran, Sebastian Ramos, Timo Rehfeld, Markus Enzweiler, Rodrigo Benenson, Uwe Franke, Stefan Roth, and Bernt Schiele.  The cityscapes dataset for semantic urban scene understanding.  In Proceedings of the IEEE conference on computer vision and pattern recognition, pages 3213–3223, 2016.
  * [4] Shivam Duggal, Shenlong Wang, Wei-Chiu Ma, Rui Hu, and Raquel Urtasun.  Deeppruner: Learning efficient stereo matching via differentiable patchmatch.  In Proceedings of the IEEE/CVF International Conference on Computer Vision, pages 4384–4393, 2019.
  * [5] David Eigen, Christian Puhrsch, and Rob Fergus.  Depth map prediction from a single image using a multi-scale deep network.  arXiv preprint arXiv:1406.2283, 2014.
  * [6] Huan Fu, Mingming Gong, Chaohui Wang, Kayhan Batmanghelich, and Dacheng Tao.  Deep ordinal regression network for monocular depth estimation.  In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, pages 2002–2011, 2018.
  * [7] Adrien Gaidon, Qiao Wang, Yohann Cabon, and Eleonora Vig.  Virtual worlds as proxy for multi-object tracking analysis.  In Proceedings of the IEEE conference on computer vision and pattern recognition, pages 4340–4349, 2016.
  * [8] Ravi Garg, Vijay Kumar Bg, Gustavo Carneiro, and Ian Reid.  Unsupervised cnn for single view depth estimation: Geometry to the rescue.  In European conference on computer vision, pages 740–756. Springer, 2016.
  * [9] Andreas Geiger, Philip Lenz, and Raquel Urtasun.  Are we ready for autonomous driving? the kitti vision benchmark suite.  In 2012 IEEE Conference on Computer Vision and Pattern Recognition, pages 3354–3361. IEEE, 2012.
  * [10] Clement Godard, Oisin Mac Aodha, and Gabriel J. Brostow.  Unsupervised monocular depth estimation with left-right consistency.  In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition (CVPR), July 2017.
  * [11] Clément Godard, Oisin Mac Aodha, Michael Firman, and Gabriel J Brostow.  Digging into self-supervised monocular depth estimation.  In Proceedings of the IEEE/CVF International Conference on Computer Vision, pages 3828–3838, 2019.
  * [12] Xiaoyang Guo, Hongsheng Li, Shuai Yi, Jimmy Ren, and Xiaogang Wang.  Learning monocular depth by distilling cross-domain stereo networks.  In Proceedings of the European Conference on Computer Vision (ECCV), pages 484–500, 2018.
  * [13] Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun.  Deep residual learning for image recognition.  In Proceedings of the IEEE conference on computer vision and pattern recognition, pages 770–778, 2016.
  * [14] Max Jaderberg, Karen Simonyan, Andrew Zisserman, and Koray Kavukcuoglu.  Spatial transformer networks.  arXiv preprint arXiv:1506.02025, 2015.
  * [15] Adrian Johnston and Gustavo Carneiro.  Self-supervised monocular trained depth estimation using self-attention and discrete disparity volume.  In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pages 4756–4765, 2020.
  * [16] Sunghun Joung, Seungryong Kim, Kihong Park, and Kwanghoon Sohn.  Unsupervised stereo matching using confidential correspondence consistency.  IEEE Transactions on Intelligent Transportation Systems, 21(5):2190–2203, 2019.
  * [17] Alex Kendall, Hayk Martirosyan, Saumitro Dasgupta, Peter Henry, Ryan Kennedy, Abraham Bachrach, and Adam Bry.  End-to-end learning of geometry and context for deep stereo regression.  In Proceedings of the IEEE International Conference on Computer Vision, pages 66–75, 2017.
  * [18] Diederik P Kingma and Jimmy Ba.  Adam: A method for stochastic optimization.  arXiv preprint arXiv:1412.6980, 2014.
  * [19] Jogendra Nath Kundu, Phani Krishna Uppala, Anuj Pahuja, and R Venkatesh Babu.  Adadepth: Unsupervised content congruent adaptation for depth estimation.  In Proceedings of the IEEE conference on computer vision and pattern recognition, pages 2656–2665, 2018.
  * [20] Uday Kusupati, Shuo Cheng, Rui Chen, and Hao Su.  Normal assisted stereo depth estimation.  In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pages 2189–2199, 2020.
  * [21] Yevhen Kuznietsov, Jorg Stuckler, and Bastian Leibe.  Semi-supervised deep learning for monocular depth map prediction.  In Proceedings of the IEEE conference on computer vision and pattern recognition, pages 6647–6655, 2017.
  * [22] Ruihao Li, Sen Wang, Zhiqiang Long, and Dongbing Gu.  Undeepvo: Monocular visual odometry through unsupervised deep learning.  In 2018 IEEE international conference on robotics and automation (ICRA), pages 7286–7291. IEEE, 2018.
  * [23] Fayao Liu, Chunhua Shen, Guosheng Lin, and Ian Reid.  Learning depth from single monocular images using deep convolutional neural fields.  IEEE transactions on pattern analysis and machine intelligence, 38(10):2024–2039, 2015.
  * [24] Yanbin Liu, Linchao Zhu, Makoto Yamada, and Yi Yang.  Semantic correspondence as an optimal transport problem.  In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pages 4463–4472, 2020.
  * [25] Chenxu Luo, Zhenheng Yang, Peng Wang, Yang Wang, Wei Xu, Ram Nevatia, and Alan Yuille.  Every pixel counts++: Joint learning of geometry and motion with 3d holistic understanding.  IEEE transactions on pattern analysis and machine intelligence, 42(10):2624–2641, 2019.
  * [26] Wenjie Luo, Alexander G Schwing, and Raquel Urtasun.  Efficient deep learning for stereo matching.  In Proceedings of the IEEE conference on computer vision and pattern recognition, pages 5695–5703, 2016.
  * [27] Yue Luo, Jimmy Ren, Mude Lin, Jiahao Pang, Wenxiu Sun, Hongsheng Li, and Liang Lin.  Single view stereo matching.  In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, pages 155–163, 2018.
  * [28] Nikolaus Mayer, Eddy Ilg, Philipp Fischer, Caner Hazirbas, Daniel Cremers, Alexey Dosovitskiy, and Thomas Brox.  What makes good synthetic training data for learning disparity and optical flow estimation?  International Journal of Computer Vision, 126(9):942–960, 2018\.
  * [29] Ishit Mehta, Parikshit Sakurikar, and PJ Narayanan.  Structured adversarial training for unsupervised monocular depth estimation.  In 2018 International Conference on 3D Vision (3DV), pages 314–323. IEEE, 2018.
  * [30] Adam Paszke, Sam Gross, Soumith Chintala, Gregory Chanan, Edward Yang, Zachary DeVito, Zeming Lin, Alban Desmaison, Luca Antiga, and Adam Lerer.  Automatic differentiation in pytorch.  2017\.
  * [31] Sudeep Pillai, Rareş Ambruş, and Adrien Gaidon.  Superdepth: Self-supervised, super-resolved monocular depth estimation.  In 2019 International Conference on Robotics and Automation (ICRA), pages 9250–9256. IEEE, 2019.
  * [32] Andrea Pilzer, Stéphane Lathuilière, Dan Xu, Mihai Marian Puscas, Elisa Ricci, and Nicu Sebe.  Progressive fusion for unsupervised binocular depth estimation using cycled networks.  IEEE transactions on pattern analysis and machine intelligence, 42(10):2380–2395, 2019.
  * [33] Andrea Pilzer, Dan Xu, Mihai Puscas, Elisa Ricci, and Nicu Sebe.  Unsupervised adversarial depth estimation using cycled generative networks.  In 2018 International Conference on 3D Vision (3DV), pages 587–595. IEEE, 2018.
  * [34] Matteo Poggi, Fabio Tosi, and Stefano Mattoccia.  Learning monocular depth estimation with unsupervised trinocular assumptions.  In 2018 International conference on 3d vision (3DV), pages 324–333. IEEE, 2018.
  * [35] Olaf Ronneberger, Philipp Fischer, and Thomas Brox.  U-net: Convolutional networks for biomedical image segmentation.  In International Conference on Medical image computing and computer-assisted intervention, pages 234–241. Springer, 2015.
  * [36] Olga Russakovsky, Jia Deng, Hao Su, Jonathan Krause, Sanjeev Satheesh, Sean Ma, Zhiheng Huang, Andrej Karpathy, Aditya Khosla, Michael Bernstein, et al.  Imagenet large scale visual recognition challenge.  International journal of computer vision, 115(3):211–252, 2015\.
  * [37] Chaoyang Wang, José Miguel Buenaposada, Rui Zhu, and Simon Lucey.  Learning depth from monocular videos using direct methods.  In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, pages 2022–2030, 2018.
  * [38] Xiaolong Wang, Ross Girshick, Abhinav Gupta, and Kaiming He.  Non-local neural networks.  In Proceedings of the IEEE conference on computer vision and pattern recognition, pages 7794–7803, 2018.
  * [39] Haofei Xu and Juyong Zhang.  Aanet: Adaptive aggregation network for efficient stereo matching.  In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pages 1959–1968, 2020.
  * [40] Nan Yang, Lukas von Stumberg, Rui Wang, and Daniel Cremers.  D3vo: Deep depth, deep pose and deep uncertainty for monocular visual odometry.  In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pages 1281–1292, 2020.
  * [41] Nan Yang, Rui Wang, Jorg Stuckler, and Daniel Cremers.  Deep virtual stereo odometry: Leveraging deep depth prediction for monocular direct sparse odometry.  In Proceedings of the European Conference on Computer Vision (ECCV), pages 817–833, 2018.
  * [42] Huangying Zhan, Ravi Garg, Chamara Saroj Weerasekera, Kejie Li, Harsh Agarwal, and Ian Reid.  Unsupervised learning of monocular depth estimation and visual odometry with deep feature reconstruction.  In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, pages 340–349, 2018.
  * [43] Jian-Qing Zheng, Ngee Han Lim, and Bartłomiej W Papież.  D-net: Siamese based network for arbitrarily oriented volume alignment.  In International Workshop on Shape in Medical Imaging, pages 73–84. Springer, 2020.
  * [44] Chao Zhou, Hong Zhang, Xiaoyong Shen, and Jiaya Jia.  Unsupervised learning of stereo matching.  In Proceedings of the IEEE International Conference on Computer Vision, pages 1567–1575, 2017.
  * [45] Tinghui Zhou, Matthew Brown, Noah Snavely, and David G Lowe.  Unsupervised learning of depth and ego-motion from video.  In Proceedings of the IEEE conference on computer vision and pattern recognition, pages 1851–1858, 2017.


$\mathcal{N}(0,\Sigma)$ and assume that

$n\geq\widetilde{O}\left(\max\left(\frac{d^{2}\log^{5}(1/\beta)}{\eta^{2}},\frac{(k\log(1/\delta)+\log^{2}(1/\delta))\cdot\log(n/\beta\delta)}{\varepsilon^{2.5}},\frac{\log^{3}(n/\delta\beta)}{\varepsilon^{3}}\right)\right).$

Then with probability $1-\beta$, the output of Algorithm 11 on input
$\mathcal{Y}$ and parameters $\eta\in(0,1/2)$, $\varepsilon,\delta\in(0,1]$,
$t=12$, $C=O(1)$ large enough and any positive integer $k$ satisfies:

$\left\lVert\Sigma^{-1/2}\widehat{\Sigma}\Sigma^{-1/2}-I\right\rVert_{F}\leq\widetilde{O}\left(\eta\right)+O\left(\sqrt{\frac{d^{2}+\log(1/\beta)}{k}}\right)$

In particular, if
$k\geq\widetilde{O}\left((d^{2}+\log(1/\beta))/\eta^{2}\right)$ as well, we
have

$\left\lVert\Sigma^{-1/2}\widehat{\Sigma}\Sigma^{-1/2}-I\right\rVert_{F}\leq\widetilde{O}\left(\eta\right).$

###### Proof.

By the guarantees of Lemmas 6.9, A.6, the algorithm fails to reach the noise
injection step with probability at most $2\beta/3$. Assume now that Algorithm
11 does not output halt in the first two steps. Then we have that:

$\displaystyle\left\lVert\Sigma^{-1/2}\widehat{\Sigma}\Sigma^{-1/2}-I\right\rVert_{F}$
$\displaystyle\leq\left\lVert\Sigma^{-1/2}\widetilde{\Sigma}\Sigma^{-1/2}-I\right\rVert_{F}+\left\lVert\Sigma^{-1/2}(\widetilde{\Sigma}-\widehat{\Sigma})\Sigma^{-1/2}\right\rVert_{F}$
$\displaystyle\leq\left\lVert\Sigma^{-1/2}\widetilde{\Sigma}\Sigma^{-1/2}-I\right\rVert_{F}+\left\lVert\Sigma^{-1/2}\widetilde{\Sigma}^{1/2}\right\rVert_{2}^{2}\left\lVert\widetilde{\Sigma}^{-1/2}\widehat{\Sigma}\widetilde{\Sigma}^{-1/2}-I\right\rVert_{F}.$

By Theorem 6.15 and choice of $n$, the first term is at most
$\widetilde{O}\left(\eta\right)$, and
$\left\lVert\Sigma^{-1/2}\widetilde{\Sigma}^{1/2}\right\rVert_{2}^{2}$ is at
most $O(1)$. Finally,
$\left\lVert\widetilde{\Sigma}^{-1/2}\widehat{\Sigma}\widetilde{\Sigma}^{-1/2}-I\right\rVert_{F}$
is bounded by invoking the utility guarantee of Theorem 5.1. ∎

##  7 Pure DP Covariance Estimation Lower Bound

In this section, we detail an information-theoretic lower bound for Gaussian
covariance estimation under differential privacy constraints. Like our upper
bound, our lower bound has a logarithmic dependence on $\kappa$. Our proof
builds on previous packing-style lower bound arguments for pure DP estimation
[HT10, AAAK21, BKSW21, KLSU19].

##### High-level Overview

For any integer $d\geq 2$, given any covariance matrix
$\Sigma\in{\mathbb{R}}^{d\times d}$ that satisfies
$I\preceq\Sigma\preceq\kappa I$, we show that to learn $\mathcal{N}(0,\Sigma)$
within total variation $O(\alpha)$, we must require sample complexity
$\Omega\left(\frac{d^{2}}{\varepsilon}\log\left(\frac{d\kappa}{\alpha}\right)+\frac{d^{2}}{\varepsilon\alpha}\right)$.
We proceed in two steps: first we show a lower bound of
$\Omega\left(\frac{d^{2}}{\varepsilon}\log\left(\frac{d\kappa}{\alpha}\right)\right)$
which does not depend polynomially on $1/\alpha$. Then we combine it with a
previous lower bound of $\Omega\left(\frac{d^{2}}{\varepsilon\alpha}\right)$,
due to [KLSU19]. Taken together, this gives us a lower bound of
$\Omega\left(\frac{d^{2}}{\varepsilon}\log\left(\frac{d\kappa}{\alpha}\right)+\frac{d^{2}}{\varepsilon\alpha}\right)$:

######  Theorem 7.1.

Let $\varepsilon,\alpha\in(0,1)$, $d\geq 2$. Any $\varepsilon$-DP algorithm
that, given $n$ i.i.d. samples $\mathcal{X}=\\{X_{1},X_{2},\ldots,X_{n}\\}$
from $\mathcal{N}(0,\Sigma)$ for an unknown $\Sigma\in\mathbb{R}^{d\times d}$
satisfying $I\preceq\Sigma\preceq\kappa I$, outputs
$\widehat{\Sigma}=\widehat{\Sigma}(\mathcal{X})$ such that, with probability
at least $0.9$,

$\text{TV}\left(\mathcal{N}(0,\Sigma),\mathcal{N}(0,\widehat{\Sigma})\right)<O(\alpha),$

must require

$n=\Omega\left(\frac{d^{2}}{\varepsilon}\log\left(\frac{d\kappa}{\alpha}\right)+\frac{d^{2}}{\varepsilon\alpha}\right).$

###  7.1 Condition Number Lower Bound

We rely on previous work on differentially private hypothesis selection
[BKSW21]: given samples from some unknown distribution $P$ (e.g., defined by
$\mathcal{N}(0,\Sigma)$ for some $\Sigma\in{\mathbb{R}}^{d\times d}$), what is
the closest distribution to $P$ in some set $\mathcal{H}$?

Crucial to the derivation of the lower bound of
$\Omega\left(\frac{d^{2}}{\varepsilon}\log\left(\frac{d\kappa}{\alpha}\right)\right)$
is the notion of covers and packings:

######  Definition 7.1 ($\gamma$-Cover).

A $\gamma$-cover of a set of distributions $\mathcal{H}$ is a set of
distributions $\mathcal{C}_{\gamma}$, such that for every $H\in\mathcal{H}$
there exists $P\in\mathcal{C}_{\gamma}$ with the following property:
$\text{TV}(P,H)\leq\gamma$.

######  Definition 7.2 ($\gamma$-Packing).

A $\gamma$-packing of a set of distributions $\mathcal{H}$ is a set of
distributions $\mathcal{P}_{\gamma}\subseteq\mathcal{H}$, such that for every
pair $P,Q\in\mathcal{P}_{\gamma}$, $\text{TV}(P,Q)>\gamma$.

The following lemma states that, provided we can find an $\alpha$-packing, we
can get a sample complexity lower bound for pure DP:

######  Lemma 7.2 (Lemma 5.1 in [BKSW21]).

Let $\mathcal{P}_{\alpha}$ be an $\alpha$-packing of a set of distributions
$\mathcal{H}$. Then for any $P\in\mathcal{H}$, any
$\varepsilon$-differentially private algorithm that takes sample
$X_{1},\ldots,X_{n}\sim P$ produces, with probability at least 0.99, a
distribution $\widehat{H}$ such that $\text{TV}(P,\widehat{H})\leq\alpha/2$
requires

$n=\Omega\left(\frac{\log|\mathcal{P}_{\alpha}|}{\varepsilon}\right).$

Note that the sample complexity lower bound in Lemma 7.2 is not of the form
$\Omega\left(\frac{\log|\mathcal{P}_{\alpha}|}{\varepsilon\alpha}\right)$
since such a lower bound would contradict already-existing upper bounds.

Lemma 7.3 shows the existence of an $\alpha$-cover of a set of $d$-dimensional
Gaussian distributions:

######  Lemma 7.3 (Lemma 6.8 in [BKSW21]).

Let $\mu\in{\mathbb{R}}^{d},\Sigma\in{\mathbb{R}}^{d\times d}$ such that
$\left\lVert\mu\right\rVert_{2}\leq R$ and $I\preceq\Sigma\preceq\kappa I$.
Then there exists an $\alpha$-cover of the set of Gaussian distributions
$\mathcal{N}(\mu,\Sigma)$ of size

$O\left(\frac{dR}{\alpha}\right)^{d}\cdot
O\left(\frac{d\kappa}{\alpha}\right)^{d(d+1)/2}.$

To use the lower bound from Lemma 7.2, we need an $\alpha$-packing and not an
$\alpha$-cover. The following lemma relates the size of the largest
$\alpha$-packing to the smallest $\alpha$-cover:

######  Lemma 7.4 (Lemma 5.2 in [BKSW21]).

Let $\mathcal{H}$ be a set of distributions. If $p_{\alpha}$ and $c_{\alpha}$
are the size of the largest $\alpha$-packing and smallest $\alpha$-cover of
$\mathcal{H}$, respectively, then

$p_{2\alpha}\leq c_{\alpha}\leq p_{\alpha}.$

We can now obtain the following corollary of a sample complexity lower bound
that depends on $\kappa$:

######  Corollary 7.5.

Fix $\varepsilon,\alpha\in(0,1)$. For any integer $d\geq 2$ and covariance
matrix $\Sigma\in{\mathbb{R}}^{d\times d}$ satisfying
$I\preceq\Sigma\preceq\kappa I$, let $\hat{\Sigma}=\hat{\Sigma}(\mathcal{X})$
be any $\varepsilon$-DP algorithm such that with probability at least 0.99,
given $n$ i.i.d. samples $\mathcal{X}=\\{X_{1},\ldots,X_{n}\\}$ from
$\mathcal{N}(0,\Sigma)$, the algorithm has the following guarantee:

$\text{TV}(\mathcal{N}(0,\Sigma),\mathcal{N}(0,\hat{\Sigma}))<\alpha/2.$

Then

$n=\Omega\left(\frac{d^{2}}{\varepsilon}\log\left(\frac{d\kappa}{\alpha}\right)\right).$

###### Proof.

Set $R=O(\alpha/d)$ since the mean of the Gaussian is a constant. By Lemma 7.4
and Lemma 7.3, there exists an $\alpha$-packing of size
$O((\frac{d\kappa}{\alpha})^{d^{2}})$. And by Lemma 7.2, this gives us a
sample complexity lower bound of
$n=\Omega(\frac{d^{2}}{\varepsilon}\log(\frac{d\kappa}{\alpha}))$.

∎

###  7.2 Precision Matrix Lower Bound

We now proceed to show the lower bound of
$\Omega(\frac{d^{2}}{\varepsilon\alpha})$. The proof of the theorem relies on
the following technical lemma on the TV distance between two mean-zero
Gaussians with different covariance. By Theorem 7.6, it suffices to derive a
lower bound on
$\left\lVert\Sigma_{1}^{1/2}\Sigma_{2}^{-1}\Sigma_{1}^{1/2}-I_{d}\right\rVert_{F}$
where $\Sigma_{1}$ and $\Sigma_{2}$ are the unknown covariance matrix and the
output from the $\varepsilon$-DP algorithm, respectively.

######  Lemma 7.6 (Lemma 3.5 in [DMR20], Theorem 1.1 in [DMR18]).

Let $\mu\in\mathbb{R}^{d}$ and let $\Sigma_{1},\Sigma_{2}$ be positive
definite symmetric $d\times d$ matrices. Use $\lambda_{1},\ldots,\lambda_{d}$
to denote the eigenvalues of $\Sigma_{1}^{-1}\Sigma_{2}-I_{d}$. Then,

$0.01\leq\frac{\text{TV}(\mathcal{N}(\mu,\Sigma_{1}),\mathcal{N}(\mu,\Sigma_{2}))}{\min\left\\{1,\sqrt{\sum_{i=1}^{d}\lambda_{i}^{2}}\right\\}}\leq
1.5.$

Also,

$\text{TV}(\mathcal{N}(0,\Sigma_{1}),\mathcal{N}(0,\Sigma_{2}))\geq\frac{1}{100}\min\left\\{1,\left\lVert\Sigma_{1}^{1/2}\Sigma_{2}^{-1}\Sigma_{1}^{1/2}-I_{d}\right\rVert_{F}\right\\}.$

For two Gaussians with the same mean, [DMR18] gives closed-form lower and
upper bounds in TV distance. The upper and lower bounds are within (small)
constants of each other.

Note that since $\Sigma_{1}^{-1}\Sigma_{2}$ and
$\Sigma_{1}^{-1/2}\Sigma_{2}\Sigma_{1}^{-1/2}$ have the same spectrum, we have

$\sum_{i=1}^{d}\lambda_{i}^{2}=\left\lVert\Sigma_{1}^{-1/2}\Sigma_{2}\Sigma_{1}^{-1/2}-I_{d}\right\rVert_{F}^{2}.$

The following statement, although not explicitly stated in [KLSU19], can be
inferred from [KLSU19]. We combine the statement with cleaner versions of
[DMR20] to derive our lower bound.

######  Proposition 7.7 (see also [KLSU19]).

Let $d\geq 2$. Let $\widehat{\Sigma}$ be an $\varepsilon$-DP algorithm that
outputs an approximation of the covariance matrix $\Sigma$, where
$\frac{1}{2}I\preceq\Sigma\preceq 2I$, such that

$\mathbb{E}_{X\sim\mathcal{N}(0,\Sigma)^{\otimes
n}}\left[\left\lVert\left[\widehat{\Sigma}(X)\right]^{-1}-\Sigma^{-1}\right\rVert_{F}^{2}\right]\leq\frac{\alpha^{2}}{64}.$

Then $n=\Omega\left(\frac{d^{2}}{\varepsilon\alpha}\right)$.

###### Proof.

We can equivalently prove that
$\mathbb{E}_{X\sim\mathcal{N}(0,\Sigma)^{\otimes
n}}\left[\left\lVert\widehat{\Sigma}(X)-\Sigma\right\rVert_{F}^{2}\right]\leq\frac{\alpha^{2}}{64}$.
We assume that $n=O(\frac{d^{2}}{\varepsilon\alpha})$ and will reach a
contradiction.

Let $\mathcal{M}_{d}$ denote the set of $d$-by-$d$ real symmetric matrices.
Consider

$\mathcal{S}_{n}=\left\\{S\in\mathcal{M}_{d}\,:\,S\text{ has diagonal entries
that are }0\text{ and non-diagonals either }-\frac{\alpha}{2d}\text{ or
}+\frac{\alpha}{2d}\right\\}.$

Clearly,

$|\mathcal{S}_{n}|=2^{(d^{2}-d)/2}.$

Let $U\sim\text{Unif}(\mathcal{S}_{n})$ be the uniform distribution over
$\mathcal{S}_{n}$. For any $V\in\mathcal{S}_{n}$, define
$\Sigma=\Sigma(V)=I+V$. The $\varepsilon$-DP algorithm $\widehat{\Sigma}$ aims
to output a matrix as close to $\Sigma$ as possible.

Define $Z$ and $Z^{\prime}$ such that

$Z=\left\langle\widehat{\Sigma}(X),V\right\rangle=2\sum_{i<j}\widehat{\Sigma}(X)_{ij}\cdot
V_{ij},$ (7.1)

and

$Z^{\prime}=\left\langle\widehat{\Sigma}(X^{\prime}),V\right\rangle=2\sum_{i<j}\widehat{\Sigma}(X^{\prime})_{ij}\cdot
V_{ij}.$ (7.2)

Let $V,V^{\prime}$ be independent samples from $\text{Unif}(\mathcal{S}_{n})$.
Then sample $X\sim\mathcal{N}(0,\Sigma(V))^{\otimes n}$ and
$X^{\prime}\sim\mathcal{N}(0,\Sigma(V^{\prime}))^{\otimes n}$. Also, note that
$\left\lVert\widehat{\Sigma}(X)-\Sigma(V)\right\rVert_{F}^{2}=\sum_{i<j}2(\widehat{\Sigma}_{ij}(X)-\Sigma_{ij}(V))^{2}$.

Then, by Lemma 7.8,
$\mathbb{E}[Z]\geq\frac{\alpha^{2}}{16}-\frac{1}{2}\left\lVert\widehat{\Sigma}(X)-\Sigma(V)\right\rVert_{F}^{2}\geq\frac{7\alpha^{2}}{128}$.

Finally, observe that by Lemma 7.9 and Lemma 7.8,
$\mathbb{P}[Z>\alpha^{2}/32]=\Omega(1)$ and
$\mathbb{P}[Z^{\prime}>\alpha^{2}/32]\leq\exp(-\Omega(d^{2}))$ but Lemma 7.9
leads to $\Omega(1)\leq\exp(4\alpha\varepsilon n)-\Omega(d^{2})$ which would
require $n=\Omega(\frac{d^{2}}{\varepsilon\alpha})$. ∎

The following lemma is used to lower bound the expected value of
$Z=\left\langle\widehat{\Sigma}(X),V\right\rangle$ in terms of
$\left\lVert\widehat{\Sigma}(X)-\Sigma(V)\right\rVert_{F}^{2}$:

######  Lemma 7.8 (Claim 6.12 of [KLSU19]).

For any $d\geq 2$,

$\mathbb{E}[Z]\geq\frac{\alpha^{2}}{16}-\frac{1}{2}\left\lVert\widehat{\Sigma}(X)-\Sigma(V)\right\rVert_{F}^{2}\geq\frac{7\alpha^{2}}{128}.$

The following lemma relates $Z$ to $Z^{\prime}$:

######  Lemma 7.9 (Claim 6.13 and 6.14 of [KLSU19]).

For $Z,Z^{\prime}$ as defined in Equations (7.1) and (7.2), we have:

  1. 1.

$\mathbb{P}[Z>\alpha^{2}/32]\leq\exp(4(\alpha\varepsilon
n))\cdot\mathbb{P}[Z^{\prime}>\alpha^{2}/32]$.

  2. 2.

$\mathbb{P}[Z^{\prime}>\alpha^{2}/32]\leq\exp(-\Omega(d^{2}))$.

###  7.3 Putting it Together

We now prove Theorem 7.1:

###### Proof of Theorem 7.1.

By Theorem 7.6, to prove Theorem 1.4, it suffices to show that it is
impossible to have both
$\left\lVert\Sigma^{1/2}\widehat{\Sigma}^{-1}\Sigma^{1/2}-I\right\rVert_{F}\leq\alpha$
and $n=O\left(\frac{d^{2}}{\varepsilon\alpha}\right)$ using an
$\varepsilon$-DP algorithm to compute
$\widehat{\Sigma}=\widehat{\Sigma}(\mathcal{X})$.

First note that

$\displaystyle\left\lVert\Sigma^{1/2}\widehat{\Sigma}^{-1}\Sigma^{1/2}-I\right\rVert_{F}$
$\displaystyle=\left\lVert\Sigma^{1/2}(\widehat{\Sigma}^{-1}-\Sigma^{-1})\Sigma^{1/2}\right\rVert_{F}$
(7.3)
$\displaystyle\geq\sigma_{d}(\Sigma^{1/2})^{2}\left\lVert\widehat{\Sigma}^{-1}-\Sigma^{-1}\right\rVert_{F},$
(7.4)

where $\sigma_{d}(\Sigma^{1/2})$ denotes the smallest singular value of
$\Sigma^{1/2}$. Because $\Sigma^{1/2}$ is symmetric and positive definite, we
know that eigenvalues coincide with its singular values. Also, the eigenvalues
of $\Sigma^{1/2}$ are larger than $1/\sqrt{2}$ so that

$\left\lVert\Sigma^{1/2}\widehat{\Sigma}^{-1}\Sigma^{1/2}-I\right\rVert_{F}\geq\frac{1}{2}\left\lVert\widehat{\Sigma}^{-1}-\Sigma^{-1}\right\rVert_{F}.$

By Lemma 7.7,
$\left\lVert\widehat{\Sigma}^{-1}-\Sigma^{-1}\right\rVert_{F}^{2}\geq\frac{\alpha^{2}}{64}$.
As a result,
$\left\lVert\Sigma^{1/2}\widehat{\Sigma}^{-1}\Sigma^{1/2}-I\right\rVert_{F}\geq\alpha/16$,
contradicting the assumption that

$\text{TV}\left(\mathcal{N}(0,\Sigma),\mathcal{N}(0,\widehat{\Sigma})\right)<\alpha/1600.$

Thus, $n=\Omega\left(\frac{d^{2}}{\varepsilon\alpha}\right)$. By Corollary
7.5, we obtain a lower bound of
$n=\Omega(\frac{d^{2}}{\varepsilon}\log(\frac{d\kappa}{\alpha}))$. As a
result, the lower bound is a max of
$n=\Omega\left(\frac{d^{2}}{\varepsilon\alpha}\right)$ and
$n=\Omega\left(\frac{d^{2}}{\varepsilon}\log(d\kappa/\alpha)\right)$ which
asymptotically is

$n=\Omega\left(\frac{d^{2}}{\varepsilon}\log\left(\frac{d\kappa}{\alpha}\right)+\frac{d^{2}}{\varepsilon\alpha}\right).$

This completes the proof. ∎

##  8 Conclusion

In this work, we have designed differentially private algorithms that achieve
the optimal sample complexity for privately estimating a Gaussian in high
dimensions. For the pure DP setting, via the use of a recursive
preconditioning approach, we present the first polynomial-time algorithm that
needs $\tilde{O}(d^{2}\log\kappa)$ samples. Through a lower bound argument, we
show that the dependence on $\kappa$ is necessary. In the approximate DP
setting, we present an algorithm that needs $\widetilde{O}(d^{2})$ samples (no
condition number dependence). We leave the following open questions for future
work:

  1. 1.

All the algorithms presented in this work only apply to the central model of
DP where the data curator is trusted. However, other trust models, such as
local DP [War65, EGS03, KLN+11], are of practical interest. What sample and
communication complexity bounds for learning a Gaussian are required in such
models?

  2. 2.

In this work, we focus on the fundamental tasks of mean and covariance
estimation. It would be interesting to apply our framework to other
statistical tasks (e.g., sparse mean estimation [GH22] or regression) to see
if it can achieve optimal sample complexities beyond just mean and covariance
estimation.

  3. 3.

For the purpose of learning a Gaussian to within small TV distance, we measure
the quality of our covariance estimate with respect to the Manalanobis
distance, which require $\Omega(d^{2})$ samples. Is there a polynomial-time DP
algorithm for estimating the covariance to within small spectral norm error
with $o(d^{2})$ samples?

## Acknowledgement

Fred Zhang would like to thank Weihao Kong for a helpful discussion about
[LKKO21, LKO22].

## References

  * [AAAK21] Ishaq Aden-Ali, Hassan Ashtiani, and Gautam Kamath.  On the sample complexity of privately learning unbounded high-dimensional gaussians.  In Algorithmic Learning Theory (ALT), 2021.
  * [AL22] Hassan Ashtiani and Christopher Liaw.  Private and polynomial time algorithms for learning gaussians and beyond.  In Conference on Learning Theory (COLT), 2022.
  * [AS66] S. M. Ali and S. D. Silvey.  A general class of coefficients of divergence of one distribution from another.  Journal of the Royal Statistical Society: Series B (Methodological), 28(1):131–142, 1966.
  * [BDKU20] Sourav Biswas, Yihe Dong, Gautam Kamath, and Jonathan Ullman.  Coinpress: Practical private mean and covariance estimation.  In Advances in Neural Information Processing Systems (NeurIPS), 2020\.
  * [BGS+21] Gavin Brown, Marco Gaboardi, Adam Smith, Jonathan Ullman, and Lydia Zakynthinou.  Covariance-aware private mean estimation without private covariance estimation.  In Advances in Neural Information Processing Systems, 2021.
  * [BKN10] Amos Beimel, Shiva Prasad Kasiviswanathan, and Kobbi Nissim.  Bounds on the sample complexity for private learning and private data release.  In Conference on Theory of Cryptography (TCC), Lecture Notes in Computer Science, 2010.
  * [BKSW21] Mark Bun, Gautam Kamath, Thomas Steinke, and Zhiwei Steven Wu.  Private hypothesis selection.  IEEE Transactions on Information Theory, 67(3):1981–2000, 2021\.
  * [BS98] Dan Boneh and James Shaw.  Collusion-secure fingerprinting for digital data.  IEEE Trans. Inf. Theory, 44(5):1897–1905, 1998.
  * [BS16] Mark Bun and Thomas Steinke.  Concentrated differential privacy: Simplifications, extensions, and lower bounds.  In Martin Hirt and Adam D. Smith, editors, Conference on Theory of Cryptography (TCC), 2016.
  * [BUV14] Mark Bun, Jonathan Ullman, and Salil Vadhan.  Fingerprinting codes and the price of approximate differential privacy.  In Proceedings of the 46th Annual ACM Symposium on Theory of Computing (STOC), 2014.
  * [CSI67] I. CSISZAR.  Information-type measures of difference of probability distributions and indirect observation.  Studia Scientiarum Mathematicarum Hungarica, 2:229–318, 1967.
  * [DK19] Ilias Diakonikolas and Daniel M Kane.  Recent advances in algorithmic high-dimensional robust statistics.  arXiv preprint arXiv:1911.05911, 2019.
  * [DKK+18] Ilias Diakonikolas, Gautam Kamath, Daniel M Kane, Jerry Li, Ankur Moitra, and Alistair Stewart.  Robustly learning a gaussian: Getting optimal error, efficiently.  In Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), 2018.
  * [DKK+19] Ilias Diakonikolas, Gautam Kamath, Daniel Kane, Jerry Li, Ankur Moitra, and Alistair Stewart.  Robust estimators in high-dimensions without the computational intractability.  SIAM Journal on Computing, 48(2):742–864, 2019.
  * [DKM+06] Cynthia Dwork, Krishnaram Kenthapadi, Frank McSherry, Ilya Mironov, and Moni Naor.  Our data, ourselves: Privacy via distributed noise generation.  In Annual International Conference on Theory and Application of Cryptographic Techniques (EUROCRYPT), 2006.
  * [DMNS06] Cynthia Dwork, Frank McSherry, Kobbi Nissim, and Adam D. Smith.  Calibrating noise to sensitivity in private data analysis.  In Third Theory of Cryptography Conference on Theory of Cryptography (TCC), 2006.
  * [DMR18] Luc Devroye, Abbas Mehrabian, and Tommy Reddad.  The total variation distance between high-dimensional gaussians.  arXiv preprint arXiv:1810.08693, 2018.
  * [DMR20] Luc Devroye, Abbas Mehrabian, and Tommy Reddad.  The minimax learning rates of normal and ising undirected graphical models.  Electronic Journal of Statistics, 14(1):2338–2361, 2020.
  * [DRV10] Cynthia Dwork, Guy N Rothblum, and Salil Vadhan.  Boosting and differential privacy.  In IEEE 51st Annual Symposium on Foundations of Computer Science (FOCS), 2010.
  * [EGS03] Alexandre V. Evfimievski, Johannes Gehrke, and Ramakrishnan Srikant.  Limiting privacy breaches in privacy preserving data mining.  In Proceedings of the Twenty-Second ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems (PODS), 2003.
  * [FKP+19] Noah Fleming, Pravesh Kothari, Toniann Pitassi, et al.  Semialgebraic proofs and efficient algorithm design.  Foundations and Trends® in Theoretical Computer Science, 14(1-2):1–221, 2019.
  * [GH22] Kristian Georgiev and Samuel B Hopkins.  Privacy induces robustness: Information-computation gaps and sparse mean estimation.  In Advances in Neural Information Processing Systems (NeurIPS), 2022\.
  * [HKM22] Samuel B Hopkins, Gautam Kamath, and Mahbod Majid.  Efficient mean estimation with pure differential privacy via a sum-of-squares exponential mechanism.  In Proceedings of the 54th Annual ACM SIGACT Symposium on Theory of Computing (STOC), 2022.
  * [HKMN22] Samuel B. Hopkins, Gautam Kamath, Mahbod Majid, and Shyam Narayanan.  Robustness implies privacy in statistical estimation, 2022.
  * [HT10] Moritz Hardt and Kunal Talwar.  On the geometry of differential privacy.  In Proceedings of the 2010 ACM International Symposium on Theory of Computing (STOC), 2010.
  * [Hub64] Peter J Huber.  Robust estimation of a location parameter.  The Annals of Mathematical Statistics, 35(1):73–101, 1964.
  * [KLN+11] Shiva Prasad Kasiviswanathan, Homin K. Lee, Kobbi Nissim, Sofya Raskhodnikova, and Adam D. Smith.  What can we learn privately?  SIAM J. Comput., 40(3):793–826, 2011.
  * [KLSU19] Gautam Kamath, Jerry Li, Vikrant Singhal, and Jonathan Ullman.  Privately learning high-dimensional distributions.  In Conference on Learning Theory (COLT), 2019.
  * [KMS22a] Gautam Kamath, Argyris Mouzakis, and Vikrant Singhal.  New lower bounds for private estimation and a generalized fingerprinting lemma.  In Advances in Neural Information Processing Systems (NeurIPS), 2022\.
  * [KMS+22b] Gautam Kamath, Argyris Mouzakis, Vikrant Singhal, Thomas Steinke, and Jonathan Ullman.  A private and computationally-efficient estimator for unbounded gaussians.  In Conference on Learning Theory (COLT), 2022.
  * [KMV22] Pravesh Kothari, Pasin Manurangsi, and Ameya Velingker.  Private robust estimation by stabilizing convex relaxations.  In Conference on Learning Theory (COLT), 2022.
  * [KMZ22] Pravesh K Kothari, Peter Manohar, and Brian Hu Zhang.  Polynomial-time sum-of-squares can robustly estimate mean and covariance of gaussians optimally.  In Algorithmic Learning Theory (ALT), 2022.
  * [KOTZ14] Manuel Kauers, Ryan O’Donnell, Li-Yang Tan, and Yuan Zhou.  Hypercontractive inequalities via sos, and the frankl–rödl graph.  In Proceedings of the Twenty-Fifth Annual ACM-SIAM Symposium on Discrete Algorithms, pages 1644–1658. SIAM, 2014.
  * [KSS18a] Pravesh K Kothari, Jacob Steinhardt, and David Steurer.  Robust moment estimation and improved clustering via sum of squares.  In Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing (STOC), 2018.
  * [KSS18b] Pravesh K Kothari, Jacob Steinhardt, and David Steurer.  Robust moment estimation and improved clustering via sum of squares.  In Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing, pages 1035–1046, 2018.
  * [KSU20] Gautam Kamath, Vikrant Singhal, and Jonathan Ullman.  Private mean estimation of heavy-tailed distributions.  In Conference on Learning Theory (COLT), 2020.
  * [KV18] Vishesh Karwa and Salil P. Vadhan.  Finite sample differentially private confidence intervals.  In Innovations in Theoretical Computer Science Conference (ITCS), 2018.
  * [Las01] Jean B Lasserre.  New positive semidefinite relaxations for nonconvex quadratic programs.  In Advances in Convex Analysis and Global Optimization, pages 319–331. Springer, 2001.
  * [LKKO21] Xiyang Liu, Weihao Kong, Sham M. Kakade, and Sewoong Oh.  Robust and differentially private mean estimation.  In Advances in Neural Information Processing Systems (NeurIPS), 2021\.
  * [LKO22] Xiyang Liu, Weihao Kong, and Sewoong Oh.  Differential privacy and robust statistics in high dimensions.  In Conference on Learning Theory (COLT), 2022.
  * [LRV16] Kevin A Lai, Anup B Rao, and Santosh Vempala.  Agnostic estimation of mean and covariance.  In 2016 IEEE 57th Annual Symposium on Foundations of Computer Science (FOCS), 2016.
  * [McS10] Frank McSherry.  Privacy integrated queries: an extensible platform for privacy-preserving data analysis.  Commun. ACM, 53(9):89–97, 2010.
  * [MT07] Frank McSherry and Kunal Talwar.  Mechanism design via differential privacy.  In 48th Annual IEEE Symposium on Foundations of Computer Science (FOCS), 2007.
  * [Nes00] Yurii Nesterov.  Squared functional systems and optimization problems.  In High performance optimization, pages 405–440. Springer, 2000\.
  * [NTZ13] Aleksandar Nikolov, Kunal Talwar, and Li Zhang.  The geometry of differential privacy: the sparse and approximate cases.  In Annual ACM Symposium on Theory of Computing (STOC), 2013.
  * [Par00] Pablo A Parrilo.  Structured semidefinite programs and semialgebraic geometry methods in robustness and optimization.  California Institute of Technology, 2000.
  * [RV13] Mark Rudelson and Roman Vershynin.  Hanson-wright inequality and sub-gaussian concentration.  Electronic Communications in Probability, 18:1–9, 2013.
  * [SCV18] Jacob Steinhardt, Moses Charikar, and Gregory Valiant.  Resilience: A criterion for learning in the presence of arbitrary outliers.  In 9th Innovations in Theoretical Computer Science Conference (ITCS), 2018.
  * [Sho87] Naum Z Shor.  Quadratic optimization problems.  Soviet Journal of Computer and Systems Sciences, 25:1–11, 1987\.
  * [SS21] Vikrant Singhal and Thomas Steinke.  Privately learning subspaces.  In Advances in Neural Information Processing Systems (NeurIPS), 2021\.
  * [SV16] Igal Sason and Sergio Verdú.  $f$-divergence inequalities.  IEEE Transactions on Information Theory, 62(11):5973–6006, 2016\.
  * [TCK+22] Eliad Tsfadia, Edith Cohen, Haim Kaplan, Yishay Mansour, and Uri Stemmer.  Friendlycore: Practical differentially private aggregation.  In International Conference on Machine Learning (ICML), 2022.
  * [Tuk60] John W. Tukey.  A survey of sampling from contaminated distributions.  Contributions to probability and statistics, 2:448–485, 1960.
  * [Vad17] Salil P. Vadhan.  The complexity of differential privacy.  In Tutorials on the Foundations of Cryptography — Dedicated to Oded Goldreich, pages 347–450. Springer, 2017.
  * [Ver18] Roman Vershynin.  High-dimensional probability: An introduction with applications in data science, volume 47.  Cambridge University Press, 2018.
  * [Wai19] Martin J. Wainwright.  High-Dimensional Statistics: A Non-Asymptotic Viewpoint.  Cambridge University Press, 2019.
  * [War65] Stanley L. Warner.  Randomized response: A survey technique for eliminating evasive answer bias.  Journal of the American Statistical Association, 60(309):63–69, 1965.

##  Appendix A Technical Lemmata from KMV22

Here we re-state and modify some useful theorems and proofs from [KMV22].

###  A.1 Truncated Laplace Mechanism

The Laplace mechanism [DMNS06] is a widely used mechanism for ensuring (pure)
DP. It adds noise drawn from the Laplace distribution to the output of the
algorithm one wants to privatize.

######  Definition A.1 (Laplace Distribution).

The Laplace distribution with mean $\mu$ and parameter $b$ on $\mathbb{R}$,
denoted by $\mathrm{Lap}(\mu,b)$, has the PDF $\frac{1}{2b}e^{-|x-\mu|/b}$.

######  Theorem A.1 (Laplace Mechanism [DMNS06]).

For $\varepsilon>0$. Consider any function
$f:\mathcal{X}^{n}\rightarrow{\mathbb{R}}^{K}$. For any dataset
$x\in\mathcal{X}^{n}$, the Laplace Mechanism outputs

$f(x)+(L_{1},\ldots,L_{k}),$

where $L_{1},\ldots,L_{k}$ are drawn i.i.d. from
$\mathrm{Lap}(0,\Delta/\varepsilon)$ where $\Delta$ is the global sensitivity
of the function $f$. Furthermore, the mechanism satisfies
$(\varepsilon,0)$-DP.

We use a “truncated” version of the Laplace mechanism where the noise
distribution is shifted and truncated to be non-negative.

######  Definition A.2 (Truncated Laplace distribution).

The (negatively) truncated Laplace distribution with mean $\mu$ and parameter
$b$, denoted by $\mathrm{tLap}(\mu,b)$ is defined as $\mathrm{Lap}(\mu,b)$
conditioned on the value being negative.

The truncated Laplace mechanism adds noise drawn from the truncated Laplace
distribution and it is known that the mechanism yields
$(\varepsilon,\delta)$-DP.

######  Lemma A.2 (Truncated Laplace Mechanism, Lemma 3.27 of [KMV22]).

Let $f:\mathcal{Y}\to\mathbb{R}$ be any function with sensitivity at most
$\Delta$. Then the algorithm that adds
$\mathrm{tLap}\left(-\Delta\left(1+\frac{\ln\left(1/\delta\right)}{\varepsilon}\right),\Delta/\varepsilon\right)$
to $f$ satisfies $(\varepsilon,\delta)$-DP.

Finally, we also state a bound on the tail probability of the truncated
Laplace distribution which will be useful in our subsequent analysis.

######  Lemma A.3.

Suppose $\mu<0$ and $b>0$. Let $X\sim\mathrm{tLap}(\mu,b)$. Then, for $y<\mu$,
we have that

$\Pr[X<y]=\frac{e^{(y-\mu)/b}}{2-e^{\mu/b}}.$

###  A.2 Approximate DP Selection via Exponential Mechanism

We describe DP-Selection of Theorem 6.1. It relies on the truncated Laplace
mechanism from the prior subsection. Specifically, DP-Selection works as
follows.

  1. 1.

First, run the exponential mechanism to select $c_{1}\in\mathcal{C}$ using
budget of $\varepsilon/2$ using the score function.

  2. 2.

Using the truncated Laplace mechanism (Lemma A.2), sample
$N\sim\mathrm{tLap}\left(-\Delta(1+\frac{2\log(1/\delta)}{\varepsilon}),\frac{2\Delta}{\varepsilon}\right)$
and check if $\textsf{score}(c_{1},Y)+N\geq\kappa$. If so, output $c_{1}$. If
not, output $\perp$.

Because $N$ is sampled from a truncated Laplace, we are guaranteed that $N\leq
0$ so that for any $c\neq\perp$ obtained from DP-Selection,
$\textsf{score}(c,Y)\geq\kappa$.

###  A.3 Witness Checking

Crucial to our DP outlier-robust algorithms is that they are witness-
producing: the algorithms find a sequence of weights on the input that induces
a distribution with relevant properties (e.g., certifiable subgaussianity).
Essentially, the algorithms search over witnesses that have certifiable
subgaussian moments or satisfy certifiable hypercontractivity. However, with a
small probability, the algorithm might not find a good witness and then
reject. We can make the whole procedure DP by observing that if on the dataset
$Y$, we can return a good witness, then on a neighboring dataset $Y^{\prime}$,
the same witness should also be good for $Y^{\prime}$.

In the next section, we describe a DP mechanism for implementing the Witness
checking steps of Algorithms 9 and 11. This mechanism and its analysis already
appear in [KMV22]; we include it in this section for the sake of completeness.
As discussed below, we implement a minor modification to Lemma 4.18 of [KMV22]
(that is already implicit in that work) that improves the final utility
guarantee of the procedure. For simplicity, we only describe below the
mechanism and its analysis for the case of $\mathcal{A}^{\textsf{mean}}$ and
certifiable subgaussianity. The same final privacy and utility guarantees hold
for the case of $\mathcal{A}^{\textsf{cov}}$ and certifiable
hypercontractivity.

####  A.3.1 Certifiable Subgaussianity

We begin by recalling the following results from [KMV22].

######  Lemma A.4 (Lemma 4.6 of [KMV22]).

Let $\zeta$ be a pseudo-distribution of degree $O(k)$ consistent with
$\mathcal{A}$ on input $Y$ with outlier rate $\eta\ll 1/k$. Suppose there
exists a $2k$-certifiably $C$-subgaussian distribution
$X\subseteq\mathbb{R}^{d}$ with mean $\mu_{*}$ of size $n$ such that $|Y\cap
X|\geq(1-\eta)n$. Then, for $\eta\leq\eta_{0}$ for some absolute constant
$\eta_{0}$ and for
$\hat{\mu}=\frac{1}{W}\sum_{i=1}^{n}\widetilde{\mathbb{E}}_{\zeta}[w_{i}]y_{i}$
where $W=\sum_{i=1}^{n}\widetilde{\mathbb{E}}[w_{i}]$, we have:

$\frac{1}{W}\sum_{i=1}^{n}\widetilde{\mathbb{E}}_{\zeta}[w_{i}]\left\langle
y_{i}-\hat{\mu},u\right\rangle^{2k}\leq(C^{\prime}k)^{k}\left(\frac{1}{W}\sum_{i=1}^{n}\widetilde{\mathbb{E}}_{\zeta}[w_{i}]\left\langle
y_{i}-\hat{\mu},u\right\rangle^{2}\right)^{k},$

for $C^{\prime}\leq C(1+O(\eta^{1-1/2k})k)$ for small enough $\eta$.

######  Lemma A.5 (Lemma 4.18 of [KMV22]).

Let $0\leq p_{i}(Y)\leq\frac{1}{(1-2\eta^{\prime})}$ be a sequence of non-
negative weights adding up to $n$ that induce a $2k$-certifiable
$C^{\prime}$-subgaussian distribution on $Y$. Let $p_{i}(Y^{\prime})$ be a
sequence of non-negative weights adding up to $n$ on $Y^{\prime}$ adjacent to
$Y$ such that $\left\lVert p(Y)-p(Y^{\prime})\right\rVert_{1}\leq\beta$ for
$\beta\leq\eta_{0}$. Then, for small enough absolute constant
$\eta^{\prime}>0$, $p_{i}(Y^{\prime})$ induces a $2k$-certifiable
$C^{\prime}(1+O(\beta^{1-1/2k})k)$-subgaussian distribution on $Y$.

Lemma A.5 follows directly from the proof of Lemma 4.18 in [KMV22] combined
with Lemma A.4. As done in [KMV22], after privately selecting a stable outlier
rate, we compute a pseudo-distribution $\zeta$ minimizing the potential for
subgaussian certificate parameter $C$. Witness-checking involves the following
private procedure $\mathcal{M}_{2}$:

  1. 1.

On input $(\mathcal{Y},\eta,C,\zeta,\beta,\varepsilon,\delta)$, let
$\gamma\sim\mathrm{tLap}(-\Delta(1+\log(1/\delta)),\Delta/\varepsilon)$ for
$\Delta=O(Ck\sqrt{L/n})$ large enough and compute $C^{\prime}=C+\gamma$. In
the next lemma, we show this procedure satisfies $(\varepsilon,\delta)$-DP by
using Lemma A.2 and a bound on the sensitivity of the subgaussianity
parameter.

  2. 2.

Check that
$p=\widetilde{\mathbb{E}}_{\zeta}[w]/\left\lVert\widetilde{\mathbb{E}}_{\zeta}[w]\right\rVert_{1}$
induces a $2k$-certifiably $C^{\prime}$-subgaussian distribution on
$\mathcal{Y}$. This check is just DP post-processing on the parameter
$C^{\prime}$. If the check does not pass, reject (i.e., return
$C^{\prime}=\bot$). Otherwise, return $C^{\prime}$.

We now show that computing $C^{\prime}$ can be done while satisfying
$(\varepsilon,\delta)$-DP:

######  Lemma A.6.

The mechanism $\mathcal{M}_{2}$ satisfies $(\varepsilon,\delta)$-DP when
invoked on input dataset $\mathcal{Y}\subset\mathbb{R}^{d}$ of size $n\geq
O\left(\frac{Lk^{2}\log^{2}(1/\delta\beta)}{\varepsilon^{2}}\right)$, outlier
rate $\eta\in[0,1/2]$ and pseudo-distribution $\zeta$ satisfying
$\mathcal{A}^{\textsf{mean}}_{C,\eta,n}(\mathcal{Y})$ that has passed the
Stable outlier rate selection step of Algorithm 9 without halting. It outputs
$C^{\prime}\in\mathbb{R}_{>0}\cup\\{\bot\\}$ with the following guarantees:

  1. 1.

If the mechanism does not output $\perp$, then
$\widetilde{\mathbb{E}}_{\zeta}[w]$ induces a $2k$-certifiably
$C^{\prime}$-subgaussian distribution on $\mathcal{Y}$.

  2. 2.

With probability at least $1-\beta$, the mechanism satisfies
$C^{\prime}\in[C/2,C]$.

###### Proof.

We begin by giving a privacy proof for $\mathcal{M}_{2}$, again following
[KMV22]. Let $C^{*}(\mathcal{Y})$ be the smallest $C^{*}$ for which a
$2k$-certifiably $C^{*}$-subgaussian distribution on $\mathcal{Y}$ can be
induced. Then by Lemma A.5 for any neighboring $\mathcal{Y}^{\prime}$,
$C^{*}(\mathcal{Y})-C^{*}(\mathcal{Y}^{\prime})\leq C^{*}(\mathcal{Y})\cdot
O(k\beta^{1-1/2k})$, where $\beta$ is the sensitivity $\beta=\left\lVert
p(\mathcal{Y})-p(\mathcal{Y}^{\prime})\right\rVert_{1}$. However, we know that
Algorithm 9 has completed the Stable outlier rate selection without halting.
Hence, it holds that that $C^{*}(\mathcal{Y})\leq C$ and $\beta\leq O(L/n)$ by
Lemma 6.9. Combining this information with the fact that $k\geq 1$, we have
$C^{*}(\mathcal{Y})-C^{*}(\mathcal{Y}^{\prime})\leq\Delta$ for some
$\Delta=O(Ck\sqrt{L/n})$. Invoking the guarantee of the Truncated Laplace
Mechanism (Lemma A.2) for this choice of $\Delta$, we conclude that the
sampling step of the the procedure $\mathcal{M}_{2}$ satisfies
$(\varepsilon,\delta)$-DP. The rest of the procedure is post-processing.

As per utility, by the tail bounds of the truncated Laplace distribution
(Lemma A.3), with probability at least $1-\beta$, it holds that
$\gamma\geq-O(\frac{\Delta}{\varepsilon}\log(\frac{1}{\delta\beta}))$. Thus,
we have that
$C^{\prime}=C+\gamma=\left(1-O\left(\frac{\sqrt{L}k\log(1/\delta\beta)}{\varepsilon\sqrt{n}}\right)\right)C\geq
C/2$ by assumption on $n$. Finally, by definition of the truncated Laplace
distribution, $\gamma\leq 0$, so $C^{\prime}\leq C$. ∎