# RDMNet: Reliable Dense Matching Based
Point Cloud Registration for Autonomous Driving

Chenghao Shi, Xieyuanli Chen, Huimin Lu∗, Wenbang Deng, Junhao Xiao∗, Bin Dai
Chenghao Shi, Xieyuanli Chen, Huimin Lu, Wenbang Deng and Junhao Xiao are with
the College of Intelligence Science and Technology, National University of
Defense Technology, Changsha, China.Bin Dai is with the Unmanned Systems
Research Center, National Innovation Institution of Defense Technology,
Beijing, China. Corresponding author: Junhao Xiao, Huimin Lu, e-mail:
<EMAIL_ADDRESS><EMAIL_ADDRESS>This work was supported in part by
the National Science Foundation of China under Grant U1913202, U22A2059 and
U1813205, as well as Major Project of Natural Science Foundation of Hunan
Province under Grant 2021JC0004.

###### Abstract

Point cloud registration is an important task in robotics and autonomous
driving to estimate the ego-motion of the vehicle. Recent advances following
the coarse-to-fine manner show promising potential in point cloud
registration. However, existing methods rely on good superpoint
correspondences, which are hard to be obtained reliably and efficiently, thus
resulting in less robust and accurate point cloud registration. In this paper,
we propose a novel network, named RDMNet, to find dense point correspondences
coarse-to-fine and improve final pose estimation based on such reliable
correspondences. Our RDMNet uses a devised 3D-RoFormer mechanism to first
extract distinctive superpoints and generates reliable superpoints matches
between two point clouds. The proposed 3D-RoFormer fuses 3D position
information into the transformer network, efficiently exploiting point clouds’
contextual and geometric information to generate robust superpoint
correspondences. RDMNet then propagates the sparse superpoints matches to
dense point matches using the neighborhood information for accurate point
cloud registration. We extensively evaluate our method on multiple datasets
from different environments. The experimental results demonstrate that our
method outperforms existing state-of-the-art approaches in all tested datasets
with a strong generalization ability.

###### Index Terms:

Autonomous Driving, 3D Registration, Deep Learning, Point Cloud Data
Processing

##  I Introduction

Point cloud registration is a fundamental problem in computer vision,
robotics, and autonomous driving. It aims to estimate the transformation
between pairs of partially overlapped point clouds. The correspondence-based
methods [1, 2, 3] are the current domination. They first find the data
association, such as point matches between two LiDAR point clouds. Based on
that, they then compute the relative transformation straightforwardly with a
singular value decomposition (SVD) or a robust estimator, e.g., RANSAC [4]. To
balance the computation consumption and correspondence quality, most existing
methods find the association on the downsampled sparse points or keypoints [3,
5, 1]. However, downsampling will inevitably make part of the points lose
their corresponding points, which degrades the registration performance.

Figure 1: Point cloud registration under a challenging situation. We compare
our method (right column) against GeoTransformer [6] (left column). Given two
point clouds (first row), we first extract the sampled points uniformly
distributed in the point cloud. Geotransformer uses them directly as
superpoints in (second left), while our RDMNet adds the learned offsets to the
sampled points and generates better superpoints near the geometrically
significant regions (second right). The orange lines show the learned offsets,
which make superpoints from both point clouds fall closer in the geometrically
significant regions. Using our proposed 3D-RoFormer to generate high-quality
superpoint correspondences, our RDMNet subsequently finds better dense-point
correspondences (third right) compared to the baseline method (third left). In
the end, our method successfully registers the two scans (bottom right) while
the baseline method fails (bottom left).

Inspired by works in image matching, recent advances [2, 7] utilize the
coarse-to-fine mechanism show remarkable performance on point cloud
registration. The coarse-to-fine mechanism [2, 7] downsamples the point cloud
into sparse superpoints and uses these superpoints to split the point cloud
into point patches. On the coarse level, it finds the superpoint (patch)
correspondences depending on the overlapped area of two patches. On the fine
level, the superpoint correspondences are then propagated to dense point
matches based on neighborhood consensus, i.e., finding the point matches only
from the matched patches. This limits the search space to a reasonable range,
which not only reduces the computational complexity, but also makes the
established matches more reliable. However, the performance of the final
matches heavily relies on the quality of the superpoint correspondences.

In this paper, we dig into the properties of the superpoint that affect the
final performance. As a powerful contextual information encoder, transformer
[8] has been adapted to multiple point cloud learning tasks [9]. Existing
methods [2, 6, 7] exploit transformers to increase the robustness of
superpoint matches. However, the vanilla transformer used in CoFiNet [2] lacks
geometric information, which hinders the performance of the position-sensitive
point cloud registration. GeoTransformer [6] infuses the pair-wise distance
and triplet-wise angular information into the transformer, while NegNet [7]
constructs point pair features based on the geometric information [10].
Although yielding promising results, they are computationally expensive and
neglect the distribution of the superpoints, thus leading to suboptimal point-
matching results.

To tackle the above-mentioned problems, we propose the RDMNet to exploit both
the contextual and geometric information of the point cloud and generate
reliable dense-point correspondence for point cloud registration. The core
technique in RDMNet is our devised novel transformation-invariant attention
mechanism, named 3D-RoFormer. It encodes the 3D position into a deep rotation
matrix and naturally incorporates explicit relative position dependency into
the self-attention calculation, thus becoming transformation-invariant while
keeping lightweight and fast. For the superpoint distribution, RDMNet uses a
superpoint detection module to first uniformly sample points over the whole
point cloud and then learn the offset for each point, making the superpoint
pairs more compact and falling in significant regions. Fig. 1 demonstrates
that our RDMNet extracts more compact superpoint pairs and finds more reliable
dense-point correspondences compared to the baseline methods.

To thoroughly evaluate our method, we conduct experiments on multiple outdoor
datasets, including KITTI [11], KITTI-360 [12], Apollo [13], Mulran [14], and
a self-recorded dataset with our own mobile robot in a campus environment.
Note that we only train our method on the training data of the KITTI dataset
and directly apply it to other datasets collected by different LiDAR sensors
in different environments. The experimental results show that our method
outperforms the state-of-the-art methods in terms of both superpoint matching
and pose estimation with strong generalization ability.

To sum up, our main contributions are:

  * •

A novel transformer, 3D-RoFormer, that efficiently learns the contextual and
geometric features for superpoint matching with limited computation and
storage cost.

  * •

A novel network RDMNet that generates reliable superpoints and dense-point
correspondences to achieve state-of-the-art point cloud registration
performance.

  * •

Extensive evaluations on multiple outdoor datasets while only trained on the
KITTI dataset show that our RDMNet achieves superior performance with strong
generalization ability compared to other state-of-the-art methods.

We will make the implementation of our method open-source.

##  II Related Work

Point cloud registration refers to finding the relative spatial transformation
that aligns two point clouds. The existing methods can be broadly classified
into two categories: correspondence-free and correspondence-based.

The correspondence-free methods transform the registration problem into a
regression problem. Early work like PointNetLK proposed by Aoki _et al._ [15]
first extracts the feature of the point cloud using PointNet [16] and then
regresses the transformation from the features. Zheng _et al._ [17] utilize a
similar idea with PointNetLK and further refine the result in an iterative
computation architecture. Other works such as the one by Huang _et al._ [18]
solve the registration problem by minimizing the feature-metric projection
error. Such methods struggle to construct reliable regression models, and
registration accuracy is not guaranteed.

The correspondence-based methods first extract correspondences between two
point clouds and then compute the transformation using a direct solver or a
robust estimator. Extracting correct correspondences is the most challenging
part of such methods. The standard correspondence-based approach is the
iterative closest point (ICP) algorithm [19] and its numerous variants [20,
21]. They find correspondences using the nearest neighbor search or other
heuristics iteratively, thus heavily relying on good initial estimation for
transformation. Recent work [9] follows the idea of ICP and establishes the
soft correspondences in the learned feature space, which relaxes the
requirement of good initial guesses. However, the computational complexity and
global searching limit the application of these methods to large-scale point
clouds.

Different from the above ICP-like methods, keypoint-based methods find
correspondences on sparse points generated by either uniformly sampling [22,
23, 24] or keypoint detection [25, 5, 3]. PPFNet and PPF-FoldNet proposed by
Deng _et al._ [22, 23] introduce point pair feature (PPF) combined with
PointNet to produce local patch representation for matching. Different from
PPFNet and PPF-FoldNet establishing correspondences on uniform sampling
points, keypoint-based methods sample points according to pre-defined [26] or
learned saliency [25, 5, 3] for higher repeatability. In order to handle the
low overlap situation, PREDATOR proposed by Huang _et al._ [1] extracts the
points that are not only salient but also lie in the overlap region. Based on
that, Zhu _et al._ [6] recently proposed NgeNet to augment the features with
point pair information and use a multi-level consistency voting to improve
discrimination.

Figure 2: Pipeline overview. Given two point clouds, our RDMNet first extracts
superpoints from them using a superpoint detection module. Then, it applies a
coarse patch matching to find the correspondences between sparse superpoints
from two point clouds. Finally, a finer point matching module is then used to
propagate superpoint correspondences into dense-point matches, which are used
to estimate the final transformations between these two point clouds.

Inspired by recent advances in image matching, CoFiNet proposed by Yu _et al._
[2] and GeoTransformer proposed by Qin _et al._ [7] utilize a coarse-to-fine
mechanism that first finds reliable sparse point patch correspondences and
then propagates the sparse correspondences to dense point matches. Benefiting
from the highly efficient backbone, they are able to obtain dense descriptors
for large point clouds. The coarse-to-fine mechanism also greatly reduces the
search space and increases the matching reliability. HRegNet proposed by Lu
_et al._ [27] also utilizes the coarse-to-fine scheme, but different from the
above methods, it extracts multi-level features and refines the transformation
hierarchically. The quality of the sparse patch correspondences is important
for such coarse-to-fine methods. To improve the correspondence accuracy, the
existing methods mostly exploit the transformer network [8]. For example,
CoFiNet [2] adopts the original transformer [8] as a powerful contextual
information encoder to generate more accurate point correspondences. However,
the vanilla transformer lacks geometric information, which hinders the
performance of the position-sensitive point cloud registration. GeoTransformer
[6] tackles this problem by infusing the pair-wise distance and triplet-wise
angular into the transformer, while NegNet [7] constructs the geometric
features with point pair features [10]. Although yielding promising results,
GeoTransformer results in extra-large $\mathcal{O}(n^{2})$ storage complexity
from the pair-wise distance and triplet-wise angular. NegNet is
computationally expensive due to the normal estimation. Besides, existing
works neglect the distribution of the superpoints. They use simple uniform
sampling points that may separate a single object into several patches, which
usually retain a low overlap ratio with patches in the other point cloud. This
may lead to bad superpoint matching and dense point propagation results.
Unlike the existing methods, our RDMNet uses the proposed 3D-RoFormer
exploiting both the contextual and geometric information of the point cloud,
which generates better correspondences for point registration.

##  III Our Approach

Given two point clouds ${\mathcal{P}^{{\mbox{{{\scriptsize
A\/}}}}}}=\\{\mbox{\boldmath$p$}_{i}^{{\mbox{{{\scriptsize
A\/}}}}}\in\mathbb{R}^{3}\\}^{M}_{i=1}$ and
${\mathcal{P}^{{\mbox{{{\scriptsize
B\/}}}}}}=\\{\mbox{\boldmath$p$}_{j}^{{\mbox{{{\scriptsize
B\/}}}}}\in\mathbb{R}^{3}\\}^{N}_{j=1}$, we aim to establish point
correspondences between the two point clouds. To this end, we propose the
RDMNet that finds correspondences in a coarse-to-fine manner. The overview of
our approach is illustrated in Fig. 2. It is built upon our devised novel
3D-RoFormer network (see Sec. III-A) and consists of three main steps:
superpoint detection (see Sec. III-B), coarse patch matching (see Sec. III-C),
and finer point matching (see Sec. III-D).

###  III-A 3D-RoFormer

We first introduce our devised novel 3D-RoFormer, which is a translation-
invariant transformer and the core technique of our RDMNet. We build
3D-RoFormer upon the vanilla transformer [8]. For a point
$\mbox{\boldmath$p$}_{i}^{{\mbox{{{\scriptsize Q\/}}}}}$ with its feature
$\mbox{\boldmath$h$}_{i}^{{\mbox{{{\scriptsize Q\/}}}}}$ in the query point
cloud Q and all the points in the source point cloud S, the network computes
the query $\mbox{\boldmath$q$}_{i}$, key $\mbox{\boldmath$k$}_{j}$, and value
$\mbox{\boldmath$v$}_{j}$ transformer feature maps with a linear projection:

$\displaystyle\mbox{\boldmath$q$}_{i}$
$\displaystyle={\mbox{{{W\/}}}}_{1}\,\mbox{\boldmath$h$}_{i}^{{\mbox{{{\scriptsize
Q\/}}}}}+\mbox{\boldmath$b$}_{1},$ $\displaystyle\mbox{\boldmath$k$}_{j}$
$\displaystyle={\mbox{{{W\/}}}}_{2}\,\mbox{\boldmath$h$}_{j}^{{\mbox{{{\scriptsize
S\/}}}}}+\mbox{\boldmath$b$}_{2},$ (1) $\displaystyle\mbox{\boldmath$v$}_{j}$
$\displaystyle={\mbox{{{W\/}}}}_{3}\,\mbox{\boldmath$h$}_{j}^{{\mbox{{{\scriptsize
S\/}}}}}+\mbox{\boldmath$b$}_{3}.$

${\mbox{{{Q\/}}}},{\mbox{{{S\/}}}}$ could be downsampled input point clouds or
sparse superpoints. If ${\mbox{{{Q\/}}}},{\mbox{{{S\/}}}}$ are the same point
cloud, Eq. (III-A) generates the feature maps for self-attention operation,
otherwise cross-attention. After that, the transformer computes an attentional
weight for the query point with each source point:
$\alpha_{ij}=\textrm{softmax}_{j}(\mbox{\boldmath$q$}_{i}^{\sf
T}\mbox{\boldmath$k$}_{j})$, and obtains the final attention-enhanced feature
for the query point as:

$\displaystyle(\tilde{\mbox{\boldmath$h$}}_{\text{vanilla}})_{i}=\sum_{j=1}^{|{\mbox{{{\scriptsize
S\/}}}}|}\textrm{softmax}_{j}(\mbox{\boldmath$q$}_{i}^{\sf
T}\mbox{\boldmath$k$}_{j})\mbox{\boldmath$v$}_{j}=\sum_{j=1}^{|{\mbox{{{\scriptsize
S\/}}}}|}\alpha_{ij}\mbox{\boldmath$v$}_{j},$ (2)

where $|{\mbox{{{S\/}}}}|$ represents the number of the points in S.

Transformer has shown to be superior for point cloud registration [28, 7, 2].
However, the vanilla transformer contains no geometric information, thus
leading to suboptimal registration results. Different works are proposed to
enhance the transformer with geometric information [7, 6]. However, they are
either memory-consuming [7] or time-consuming [6].

Inspired by the recent Roformer [29] using rotational information for natural
language processing, we propose a novel 3D-Roformer that encodes the absolute
position information with a rotation matrix for 3D point cloud registration.
Based on 3D-Roformer, our RDMNet can better exploit both contextual and
geometric information of the point clouds to generate more reliable keypoints.
We first adapt the rotary position embedding into 3D data by leveraging a MLP
and mapping the position $\hat{\mbox{\boldmath$s$}}_{i}\in\mathbb{R}^{3}$ into
the rotary embedding
$\mbox{\boldmath$\Theta$}_{i}=[\theta_{1},\theta_{2},\cdots,\theta_{d/2}]\in\mathbb{R}^{\frac{\hat{d}}{2}}$:

$\displaystyle\mbox{\boldmath$\Theta$}_{i}=\text{MLP}_{\text{rot}}(\hat{\mbox{\boldmath$s$}}_{i}).$
(3)

Each element in $\mbox{\boldmath$\Theta$}_{i}$ can be treated as a rotation in
a 2D plane and represented by a rotation matrix. The final formulation of the
rotary 3D position embeddings
${\mbox{{{R\/}}}}_{\mbox{\boldmath$\scriptsize$}\Theta_{i}}\in\mathbb{R}^{\tilde{d}\times\tilde{d}}$
is:

$\displaystyle{\mbox{{{R\/}}}}_{\mbox{\boldmath$\scriptsize$}\Theta_{i}}$
$\displaystyle=\begin{bmatrix}&\cos\theta_{1}\\!&-\sin\theta_{1}\\!&\cdots\\!&0\\!&0\\\
&\sin\theta_{1}\\!&\cos\theta_{1}\\!&\cdots\\!&0\\!&0\\\
&\vdots\\!&\vdots\\!&\ddots\\!&\vdots\\!&\vdots\\\
&0\\!&0\\!&\cdots\\!&\cos\theta_{\frac{d}{2}}\\!&-\sin\theta_{\frac{d}{2}}\\\
&0\\!&0\\!&\cdots\\!&\sin\theta_{\frac{d}{2}}\\!&\cos\theta_{\frac{d}{2}}\end{bmatrix}.$
(4)

Figure 3: The rotary 3D position embedding.

Applying ${\mbox{{{R\/}}}}_{\mbox{\boldmath$\scriptsize$}\Theta_{i}}$ to a
$\tilde{d}$ dimensional vector is equivalent to divide the vector into
$\tilde{d}/2$ 2D vectors and rotate each of them by
$\\{\theta_{i}|i=1,\cdots,\tilde{d}/2\\}$ accordingly (see Fig. 3). We apply
${\mbox{{{R\/}}}}_{\mbox{\boldmath$\scriptsize$}\Theta_{i}}$ and
${\mbox{{{R\/}}}}_{\mbox{\boldmath$\scriptsize$}\Theta_{j}}$ to query
$\mbox{\boldmath$q$}_{i}$ and key $\mbox{\boldmath$k$}_{j}$ respectively in
self-attention operation and obtain the rotary self-attention as:

$\displaystyle\alpha_{ij}^{\prime\prime}$
$\displaystyle=\textrm{softmax}_{j}(({\mbox{{{R\/}}}}_{\mbox{\boldmath$\scriptsize$}\Theta_{i}}\mbox{\boldmath$q$}_{i})^{\sf
T}{\mbox{{{R\/}}}}_{\mbox{\boldmath$\scriptsize$}\Theta_{j}}\mbox{\boldmath$k$}_{j}),$
(5) $\displaystyle\tilde{\mbox{\boldmath$h$}}_{i}$
$\displaystyle=\sum_{j=1}^{|\tilde{\mathcal{P}}|}\alpha_{ij}^{\prime\prime}\mbox{\boldmath$v$}_{j}.$
(6)

The benefits of using the proposed rotary self-attention are as follows.
First, by encoding the position information as a rotation matrix, the rotary
self-attention explicitly encodes the relative position information neatly.
Using the properties of the rotation matrix, we can further derive Eq. (5) as:

$\displaystyle\alpha_{ij}^{\prime\prime}$
$\displaystyle=\textrm{softmax}_{j}(\mbox{\boldmath$q$}_{i}^{\sf
T}{\mbox{{{R\/}}}}_{\mbox{\boldmath$\scriptsize$}\Theta_{i}}^{\sf
T}{\mbox{{{R\/}}}}_{\mbox{\boldmath$\scriptsize$}\Theta_{j}}\mbox{\boldmath$k$}_{j}),$
$\displaystyle=\textrm{softmax}_{j}(\mbox{\boldmath$q$}_{i}^{\sf
T}{\mbox{{{R\/}}}}_{\mbox{\boldmath$\scriptsize$}\Theta_{j}-\mbox{\boldmath$\scriptsize$}\Theta_{i}}\mbox{\boldmath$k$}_{j}),$
(7)

where $\mbox{\boldmath$\Theta$}_{j}-\mbox{\boldmath$\Theta$}_{i}$ is naturally
incorporated into the calculation of the attention scores
$\alpha_{ij}^{\prime\prime}$ and then fused with the output feature
$\tilde{\mbox{\boldmath$h$}}_{i}$ in Eq. (6). Therefore, our method is
lightweight without requiring extra-large storage memory for relative position
embeddings, which will be further verified in Sec. IV-G.

Secondly, the proposed 3D-Roformer is easy to deploy and operates very fast.
Due to the sparsity of
${\mbox{{{R\/}}}}_{\mbox{\boldmath$\scriptsize$}\Theta}$, the calculation of
${\mbox{{{R\/}}}}_{\mbox{\boldmath$\scriptsize$}\Theta_{i}}\cdot\mbox{\boldmath$q$}_{i}$
and
${\mbox{{{R\/}}}}_{\mbox{\boldmath$\scriptsize$}\Theta_{j}}\cdot\mbox{\boldmath$k$}_{j}$
can be done in a computationally efficient way using vector addition and
multiplication operations, for example:

$\small{{\mbox{{{R\/}}}}_{\mbox{\boldmath$\scriptsize$}\Theta_{i}}\cdot\mbox{\boldmath$q$}_{i}=\begin{bmatrix}q_{1}\\\
q_{2}\\\ \vdots\\\ q_{d-1}\\\
q_{d}\end{bmatrix}\otimes\begin{bmatrix}\cos\theta_{1}\\\ \cos\theta_{1}\\\
\vdots\\\ \cos\theta_{d/2}\\\
\cos\theta_{d/2}\end{bmatrix}+\begin{bmatrix}-q_{2}\\\ q_{1}\\\ \vdots\\\
-q_{d}\\\ q_{d-1}\end{bmatrix}\otimes\begin{bmatrix}\sin\theta_{1}\\\
\sin\theta_{1}\\\ \vdots\\\ \sin\theta_{d/2}\\\
\sin\theta_{d/2}\end{bmatrix}.}$ (8)

Thirdly, our proposed 3D-RoFormer is translation-invariant inherited from the
linearity of MLP:

$\displaystyle\mbox{\boldmath$\Theta$}_{j}-\mbox{\boldmath$\Theta$}_{i}=\text{MLP}_{\text{rot}}(\hat{\mbox{\boldmath$s$}_{j}}-\hat{\mbox{\boldmath$s$}}_{i}).$
(9)

Therefore, our 3D-RoFormer will not be influenced by the changes in
observation positions when used for finding correspondences. We enhance the
final output features of the 3D-RoFormer
$\tilde{\mathbf{H}}^{{\mbox{{{\scriptsize A\/}}}}}$ and
$\tilde{\mathbf{H}}^{{\mbox{{{\scriptsize B\/}}}}}$ for point matching by
interleaving the rotary self-attention and cross-attention for $l$ times.

Benefiting from the above-mentioned advantages, our proposed RDMNet uses the
devised 3D-RoFormer in both the superpoint detection and sparse patch matching
modules to better find superpoint correspondences.

###  III-B Superpoint Detection

Our approach aims first to find reliable sparse patch matches and then
propagate them to dense point matches based on neighborhood consensus. Such a
coarse-to-fine scheme avoids the time-consuming and unreliable global search
of dense feature correspondences.

Considering a point patch as the vicinity of a keypoint, the task can be
treated as the keypoint detection and vicinity grouping. We assign a keypoint
for each point patch and regard them all together as one superpoint. A simple
way to extract keypoints is to directly use the uniform sampling center point
of each voxel [7, 2]. However, the uniformly sampled center points may
separate a single object into several patches and share low overlap vicinities
with center points in the other point cloud (see Fig. 1), which leads to poor
patch matching and dense point match propagation in the following steps.

To address this issue, we propose the superpoint detection module to extract
more reliable superpoints for the point patch partition. We use the KPEncoder
[30] as the backbone of the proposed superpoint detection module that
hierarchically downsamples and encodes the point cloud into the uniformly
distributed nodes $\hat{\mathcal{P}}$ with associated features
$\hat{\mathbf{F}}\in\mathbb{R}^{|\hat{\mathcal{P}}|\times\hat{d}}$. The node
feature from KPEncoder contains only the contextual and geometric information
of the single point cloud but lacks information between two point clouds, thus
not being able to reason the inter-clues to make the associated superpoints
compact. Therefore, we use the proposed 3D-RoFormer to fuse inter-point-cloud
information and explicitly encode intra-point-cloud information at the same
time. We denote the enhanced feature by 3D-RoFormer as
$\tilde{\mathbf{F}}\in\mathbb{R}^{|\hat{\mathcal{P}}|\times\tilde{d}}$. A
Voting module is then used to estimate the geometric offset and feature offset
from the node to the proposal superpoint ${{{\mathcal{S}}}}$, i.e.,
$[\Delta{\mathbf{P}},\Delta{\mathbf{F}}]=\text{Vote}(\tilde{\mathbf{F}})$,
${{{\mathcal{S}}}}=\hat{\mathcal{P}}+\Delta\mathbf{P}$, and
${{\mathbf{H}}}=\tilde{\mathbf{F}}+\Delta\mathbf{F}$. We use a group of Multi-
Layer Perceptron (MLP) to form the Voting module. Though very simple, it
generates meaningful offsets based on the feature learned by our 3D-RoFormer
(see Fig. 7) and boosts the registration performance by a large margin (see
Tab. V). In this paper, we supervise the superpoints to fall in the locally
significant region, which may also lead to redundant proposals located in the
same significant region. Thus, we use a simple radius search-based filtering
strategy to force only one proposal in the same region. We iteratively perform
a radius search for each proposal and filter out the ones close to the search
center. After that, we obtain the final superpoints $\hat{\mathcal{S}}$ with
associated features $\hat{\mathbf{H}}$. Note that we limit the offsets
$\Delta\mathbf{P}$ to a certain range, which maintains the superpoints to be
evenly distributed throughout the point cloud instead of only concentrated in
so-called significant areas. It also avoids possible degeneracy [5].

For each superpoint $\hat{\mbox{\boldmath$s$}}_{i}$, we construct a local
patch ${\mathcal{G}_{i}}$ using a point-to-node strategy [5]. Specifically,
each point is assigned to its nearest superpoint by:

$\displaystyle{\mathcal{G}}_{i}=\\{\mbox{\boldmath$p$}\in\mathcal{P}|i=\mathop{\rm
argmin}_{j}(\|{\mbox{\boldmath$p$}}-\hat{\mbox{\boldmath$s$}_{j}}\|_{2}),\hat{\mbox{\boldmath$s$}_{j}}\in\hat{\mathcal{S}}\\}.$
(10)

There are two advantages of this strategy. First, it assigns every point to a
specific superpoint without duplication or loss. Second, it adapts to
different densities, which is particularly suitable for our case since our
superpoints break the uniformity of the original sampling after adding
offsets.

###  III-C Sparse Patch Matching

Based on the detected superpoints, we then conduct patch matching on the
coarse level and find superpoints/patch correspondences between point clouds A
and B.

Since the superpoints have just been shifted and filtered by the superpoint
detection module, the associated feature $\hat{\mathbf{H}}$ could be
inconsistent with the surroundings. Therefore, we first feed the superpoints
with the associated features to another 3D-RoFormer to update the features
with the newest contextual and geometric information from the updated
superpoints. Then we conduct the superpoint matching. We follow Qin  _et al._
[7] and compute a Gaussian correlation matrix
${\mathbf{C}}\in\mathbb{R}^{|\hat{\mathcal{S}}^{{\mbox{{{\scriptsize
A\/}}}}}|\times|\hat{\mathcal{S}}^{{\mbox{{{\scriptsize B\/}}}}}|}$ between
normalized $\hat{\mathbf{H}}^{{\mbox{{{\scriptsize A\/}}}}}$ and
$\hat{\mathbf{H}}^{{\mbox{{{\scriptsize B\/}}}}}$ with
$c_{i,j}=\exp(-\|{{{\hat{\mathbf{h}}}}_{i}^{{\mbox{{{\scriptsize
A\/}}}}}}-{{{\hat{\mathbf{h}}}}_{j}^{{\mbox{{{\scriptsize B\/}}}}}}\|^{2})$. A
dual-normalization is then performed to suppress ambiguous matches:

$\displaystyle\hat{c}_{i,j}=\frac{c_{i,j}}{\sum_{k=1}^{|{\hat{\mathcal{S}}^{{\mbox{{{\scriptsize
A\/}}}}}}|}c_{i,k}}\cdot\frac{c_{i,j}}{\sum_{k=1}^{|{\hat{\mathcal{S}}^{{\mbox{{{\scriptsize
B\/}}}}}}|}c_{k,j}}.$ (11)

We choose the largest $N_{c}$ entries as the superpoint correspondences:

$\displaystyle{\mathcal{M}}=\\{({\hat{\mbox{\boldmath$s$}}_{x_{i}}^{{\mbox{{{\scriptsize
A\/}}}}}},{\hat{\mbox{\boldmath$s$}}_{y_{i}}^{{\mbox{{{\scriptsize
B\/}}}}}})|(x_{i},y_{i})\in\text{topk}_{x,y}(\hat{c}_{x,y})\\}.$ (12)

Based on the fast superpoint matching, we determine the corresponding matched
patches and use them as the basis for the subsequent fine-level dense-point
matching.

###  III-D Dense Point Matching

On the Fine level, we aim to generate dense point matches from the coarse
patch correspondences.

We leverage the KPDecoder [30] to recover point-level descriptors
${{\mathbf{F}}}$. Instead of using the updated superpoint feature, we recover
the point-level feature from the raw anchor point feature
$\tilde{{{\mathbf{F}}}}$ since there might be information loss after
offsetting and filtering. For each superpoint correspondence
$({\hat{\mbox{\boldmath$s$}}_{x_{i}}^{{\mbox{{{\scriptsize
A\/}}}}}},{\hat{\mbox{\boldmath$s$}}_{y_{i}}^{{\mbox{{{\scriptsize
B\/}}}}}})$, we have its corresponding patch match
$({{{{\mathcal{G}}}}_{x_{i}}^{{\mbox{{{\scriptsize
A\/}}}}}},{{{{\mathcal{G}}}}_{y_{i}}^{{\mbox{{{\scriptsize B\/}}}}}})$ and
then compute a match score matrix ${\mathbf{O}_{i}}\in\mathbb{R}^{M_{i}\times
N_{i}}$ :

$\displaystyle\mathbf{O}_{i}={{{\mathbf{F}}}_{x_{i}}^{{\mbox{{{\scriptsize
A\/}}}}}}({{{\mathbf{F}}}_{y_{i}}^{{\mbox{{{\scriptsize B\/}}}}}})^{\sf
T}/\sqrt{\tilde{d}},$ (13)

where $M_{i}=|{\mathcal{G}}_{x_{i}}^{{\mbox{{{\scriptsize A\/}}}}}|$ and
$N_{i}=|{\mathcal{G}}_{y_{i}}^{{\mbox{{{\scriptsize B\/}}}}}|$ represent the
number of points in ${\mathcal{G}}_{x_{i}}^{{\mbox{{{\scriptsize A\/}}}}}$ and
${\mathcal{G}}_{y_{i}}^{{\mbox{{{\scriptsize B\/}}}}}$ respectively.

To handle non-matched points, we append a “dustbin” row and column for
$\mathbf{O}_{i}$ filled with a learnable parameter $\alpha\in\mathbb{R}$. The
Sinkhorn algorithm is then used to solve the soft assignment matrix
${{\mathbf{Z}}}^{i}\in\mathbb{R}^{(M_{i}+1)\times(N_{i}+1)}$. Different from
[7, 2] that drops the dustbin and recovers the assignment by comparing the
soft assignment score with a hand-tuned threshold, we directly find max entry
both row-wise and column-wise on ${{\mathbf{Z}}}^{i}$ which is then recovered
to assignment ${{{\mathcal{C}}}}^{i}$:

$\displaystyle{{{\mathcal{C}}}}^{i}=$
$\displaystyle\\{({{{{\mathcal{G}}}}_{x_{i}}^{{\mbox{{{\scriptsize
A\/}}}}}}(m),{{{{\mathcal{G}}}}_{y_{i}}^{{\mbox{{{\scriptsize
B\/}}}}}}(n)|(m,n)\in\text{toprow}_{m,n}({{\mathbf{Z}}}_{1:M_{i},1:(N_{i}+1)}^{i})\\}\cup$
$\displaystyle\\{({{{{\mathcal{G}}}}_{x_{i}}^{{\mbox{{{\scriptsize
A\/}}}}}}(m),{{{{\mathcal{G}}}}_{y_{i}}^{{\mbox{{{\scriptsize
B\/}}}}}}(n)|(m,n)\in\text{topcolumn}_{m,n}({{\mathbf{Z}}}_{1:(M_{i}+1),1:N_{i}}^{i})\\},$
(14)

where $m$ and $n$ represent the indexes of the max entry of
${{\mathbf{Z}}}^{i}$.

A point is either assigned to points in the matched patch or to the dustbin.
By this, we do not need manual tuning but require a discriminative assignment
matrix, which can be obtained by using our proposed loss function as detailed
in Sec. III-E. Note that a point is not strictly assigned to a single point in
our approach, as the strict one-to-one point correspondences do not hold in
practice due to the sparsity nature of the point cloud. Instead, we trust and
keep the assignment results from both sides, i.e., matches from query to
source and vice versa. This results in extensively more point matches while
maintaining a high inlier ratio, which benefits the transformation estimation.
The final correspondences are the combination of points matches from all
patches:

$\displaystyle{{{\mathcal{C}}}}=\bigcup_{i=1}^{N_{c}}{{{\mathcal{C}}}}^{i}.$
(15)

###  III-E Loss function and training

The final loss is the weighted sum of these three components:
$L=L_{\text{s}}+L_{\text{c}}+L_{\text{f}}$, where $L_{\text{s}}$ is the
superpoint detection loss, $L_{\text{c}}$ is the coarse match loss,
$L_{\text{f}}$ is the fine match loss.

Superpoint detection loss. The superpoint detection loss is composed of two
parts $L_{s}=L_{s1}+L_{s2}$. The first part $L_{s1}$ is designed to guide our
superpoints lying in the significant region, and the second part $L_{s2}$ is
designed to make the superpoints close to the real measurement points.
Specifically, for the first part, we do not explicitly define the significance
of a point, but use a chamfer loss to minimize the distance between matched
superpoints:

$\small{L_{\text{s}1}=\sum_{i=1}^{|{{{\mathcal{S}}}}^{{\mbox{{{\scriptsize
A\/}}}}}|}\min_{\mbox{\boldmath\scriptsize$s$}^{{\mbox{{{\scriptsize
B\/}}}}}_{j}\in{{{\mathcal{S}}}}^{{\mbox{{{\scriptsize
B\/}}}}}}\|\mbox{\boldmath$s$}^{{\mbox{{{\scriptsize
A\/}}}}}_{i}-\mbox{\boldmath$s$}_{j}^{{\mbox{{{\scriptsize
B\/}}}}}\|^{2}_{2}+\sum_{i=1}^{|{{{\mathcal{S}}}}^{{\mbox{{{\scriptsize
B\/}}}}}|}\min_{\mbox{\boldmath\scriptsize$s$}_{j}^{{\mbox{{{\scriptsize
A\/}}}}}\in{{{\mathcal{S}}}}^{{\mbox{{{\scriptsize
A\/}}}}}}\|\mbox{\boldmath$s$}_{i}^{{\mbox{{{\scriptsize
B\/}}}}}-\mbox{\boldmath$s$}_{j}^{{\mbox{{{\scriptsize A\/}}}}}\|^{2}_{2}.}$
(16)

Supervised by $L_{\text{s}1}$, we find that the superpoints tend to move to
their nearest “significant” regions to minimize the distance between
superpoint pairs. For the second part, we use another chamfer loss that
minimizes the distance between the superpoint to its closest point:

$\small{L_{s2}=\sum_{i=1}^{|{{{\mathcal{S}}}}^{{\mbox{{{\scriptsize
A\/}}}}}|}\min_{\mbox{\boldmath\scriptsize$p$}^{{\mbox{{{\scriptsize
A\/}}}}}_{j}\in{{{\mathcal{P}}}}^{{\mbox{{{\scriptsize
A\/}}}}}}\|\mbox{\boldmath$s$}^{{\mbox{{{\scriptsize
A\/}}}}}_{i}-\mbox{\boldmath$p$}_{j}^{{\mbox{{{\scriptsize
A\/}}}}}\|^{2}_{2}+\sum_{i=1}^{|{{{\mathcal{S}}}}^{{\mbox{{{\scriptsize
B\/}}}}}|}\min_{\mbox{\boldmath\scriptsize$p$}_{j}^{{\mbox{{{\scriptsize
B\/}}}}}\in{{{\mathcal{P}}}}^{{\mbox{{{\scriptsize
B\/}}}}}}\|\mbox{\boldmath$s$}_{i}^{{\mbox{{{\scriptsize
B\/}}}}}-\mbox{\boldmath$p$}_{j}^{{\mbox{{{\scriptsize B\/}}}}}\|^{2}_{2}.}$
(17)

Coarse match loss. We follow [7] and use overlap-aware circle loss to guide
the network to extract reliable superpoint correspondence with relatively high
overlap. We set the patch in A with at least one positive patch in B as the
anchor patches ${{{{\mathcal{G}}}}^{{\mbox{{{\scriptsize A\/}}}}}}$. For an
anchor patch ${{{{\mathcal{G}}}}_{i}^{{\mbox{{{\scriptsize A\/}}}}}}$, its
positive patch set $\varepsilon_{i}^{+}$ is defined as those sharing at least
10% overlap with ${{{{\mathcal{G}}}}_{i}^{{\mbox{{{\scriptsize A\/}}}}}}$, and
its negative patch set $\varepsilon_{i}^{-}$ is those that do not overlap with
${{{{\mathcal{G}}}}_{i}^{{\mbox{{{\scriptsize A\/}}}}}}$. Then the overlap-
aware circle loss on A is calculated as:

$\footnotesize{{{L}_{\text{c}}^{{\mbox{{{\scriptsize
A\/}}}}}}=\frac{1}{|{{{\mathcal{A}}}}|}\sum_{{{{{\mathcal{G}}}}_{i}^{{\mbox{{{\scriptsize
A\/}}}}}}\in{{{\mathcal{A}}}}}\log[1+\sum_{{{{{\mathcal{G}}}}_{j}^{{\mbox{{{\scriptsize
B\/}}}}}}\in\varepsilon^{+}_{i}}e^{\lambda_{i}^{j}\beta_{i,j}^{+}(d_{i}^{j}-\Delta^{+})}\cdot\sum_{{{{{\mathcal{G}}}}_{k}^{{\mbox{{{\scriptsize
B\/}}}}}}\in\varepsilon^{-}_{i}}e^{\beta_{i,k}^{-}(\Delta^{-}-d_{i}^{k})}],}$
(18)

where $d_{i}^{j}=\|{{{\hat{\mathbf{h}}}}_{i}^{{\mbox{{{\scriptsize
A\/}}}}}}-{{{\hat{\mathbf{h}}}}_{j}^{{\mbox{{{\scriptsize B\/}}}}}}\|_{2}$,
$\lambda_{i}^{j}$ refers to the overlap ratio between
${{{{\mathcal{G}}}}_{i}^{{\mbox{{{\scriptsize A\/}}}}}}$ and
${{{{\mathcal{G}}}}_{j}^{{\mbox{{{\scriptsize B\/}}}}}}$, and
$\beta_{i,j}^{+}=\gamma(d_{i}^{j}-\Delta^{+})$ and
$\beta_{i,k}^{-}=\gamma(d_{i}^{k}-\Delta^{-})$ represent the positive and
negative weights. The hyper-parameters setting is followed by convention:
$\Delta^{+}=0.1$ and $\Delta^{-}=1.4$. The overall coarse match loss is the
average of overlap-aware circle loss on A and B, i.e.,
$L_{\text{c}}=({{L}_{\text{c}}^{{\mbox{{{\scriptsize
A\/}}}}}}+{{L}_{\text{c}}^{{\mbox{{{\scriptsize B\/}}}}}})/2$

Fine match loss. To learn a discriminative soft assignment matrix and support
our dense point match module, we use a gap loss on the soft assignment matrix
${{\mathbf{Z}}}^{i}$ of each patch correspondence
$\\{{{{{\mathcal{G}}}}_{x_{i}}^{{\mbox{{{\scriptsize
A\/}}}}}},{{{{\mathcal{G}}}}_{y_{i}}^{{\mbox{{{\scriptsize B\/}}}}}}\\}$. For
each matched patch pair, we generate its ground truth correspondences
${{\mathbf{M}}}^{i}\in\\{0,1\\}^{(M_{i}{+}1)\times(N_{i}{+}1)}$ with a match
threshold $\tau$, where
$M_{i}=|{{{{\mathcal{G}}}}_{x_{i}}^{{\mbox{{{\scriptsize A\/}}}}}}|$,
$N_{i}=|{{{{\mathcal{G}}}}_{x_{i}}^{{\mbox{{{\scriptsize B\/}}}}}}|$. The gap
loss is then calculated as:

$\displaystyle L_{\text{f}}^{i}=$
$\displaystyle\frac{1}{M_{i}}\sum_{m=1}^{M_{i}}\log(\sum_{n=1}^{N_{i}+1}[(-r_{m}^{i}+{{\mathbf{Z}}}_{m,n}^{i}+\eta)_{+}+1])$
$\displaystyle+\frac{1}{N_{i}}\sum_{n=1}^{N_{i}}\log(\sum_{m=1}^{M_{i}+1}[(-c_{n}^{i}+{{\mathbf{Z}}}_{m,n}^{i}+\eta)_{+}+1]),$
(19)

where $(\bullet)_{+}=max(\bullet,0)$,
$r_{m}^{i}=\sum_{n=1}^{N_{i}{+}1}{{\mathbf{Z}}}_{m,n}^{i}{{\mathbf{M}}}_{m,n}^{i}$
refers to the soft assignment value for the true match of $m$-th point in
${{{{\mathcal{G}}}}_{x_{i}}^{{\mbox{{{\scriptsize A\/}}}}}}$, and
$c_{n}^{i}=\sum_{m=1}^{M_{i}{+}1}{{\mathbf{Z}}}_{m,n}^{i}{{\mathbf{M}}}_{m,n}^{i}$
refers to the soft assignment value for the true match of $n$-th point in
${{{{\mathcal{G}}}}_{x_{i}}^{{\mbox{{{\scriptsize B\/}}}}}}$. The final fine
match loss is the average over all the matched patch pairs:
$L_{\text{f}}=\frac{1}{2|{{{\mathcal{M}}}}|}\sum_{i=1}^{|{{{\mathcal{M}}}}|}L_{\text{f}}^{i}$.

We implement and evaluate our RDMNet on 4 NVIDIA RTX 3090 GPUs. The network is
trained with Adam optimizer [31]. We use 5 layers of KPEncoder (4 layers of
downsampling) and 3 layers of KPDecoder, which result in coarse-level points
with a resolution of $4.8$ m and fine-level points with a resolution of $0.6$
m. The batch size is 1, and the learning rate is $10^{-4}$ and decay
exponentially by 0.05 every 4 epochs. We also adapt the same data augmentation
as in [1].

##  IV Experimental Evaluation

TABLE I: Matching results on multiple datasets under different numbers of samples. The best results are highlighted in bold, and the second bests are marked with an underline. | KITTI | KITTI-360 | Apollo | Mulran | Campus
---|---|---|---|---|---
# Samples | 5000 | 1000 | 250 | 5000 | 1000 | 250 | 5000 | 1000 | 250 | 5000 | 1000 | 250 | 2000 | 1000 | 250
Feature Match Recall (%)
Predator [1] | 99.64 | 99.64 | 99.64 | 99.87 | 99.78 | 99.44 | 99.98 | 99.98 | 97.86 | 85.96 | 82.01 | 58.76 | 49.12 | 49.12 | 39.18
CofiNet [2] | 99.64 | 99.64 | 99.82 | 99.89 | 99.89 | 99.86 | 100 | 100 | 100 | 91.79 | 93.10 | 93.20 | 62.57 | 66.07 | 67.84
NgeNet [6] | 99.64 | 99.64 | 99.64 | 99.94 | 99.94 | 99.94 | 100 | 100 | 100 | 95.18 | 94.90 | 87.70 | 91.81 | 88.89 | 70.76
Geotransformer [7] | 99.82 | 99.82 | 99.82 | 99.89 | 99.92 | 99.94 | 100 | 100 | 100 | 88.28 | 91.05 | 91.67 | 98.25 | 98.25 | 97.66
RDMNet (ours) | 99.82 | 99.82 | 99.82 | 99.92 | 99.94 | 99.94 | 100 | 100 | 100 | 98.31 | 98.72 | 98.81 | 100 | 100 | 100
Inlier Ratio (%)
Predator [1] | 62.9 | 50.2 | 29.5 | 60.2 | 48.8 | 29.3 | 44.3 | 31.8 | 16.8 | 14.2 | 11.1 | 6.6 | 5.5 | 5.4 | 4.7
CofiNet [2] | 34.2 | 36.1 | 36.2 | 32.4 | 34.4 | 34.8 | 40.4 | 41.9 | 42.2 | 17.6 | 19.1 | 19.4 | 6.5 | 6.7 | 6.8
NgeNet [6] | 66.5 | 51.5 | 28.6 | 63.2 | 49.6 | 28.5 | 68.6 | 49.2 | 24.8 | 29.1 | 20.7 | 11.1 | 12.4 | 11.4 | 8.1
Geotransformer [7] | 75.7 | 86.0 | 87.5 | 73.2 | 83.7 | 85.5 | 83.8 | 91.0 | 92.4 | 33.6 | 43.7 | 46.3 | 19.0 | 21.7 | 24.9
RDMNet (ours) | 86.7 | 93.0 | 95.3 | 84.0 | 91.0 | 93.7 | 92.1 | 96.4 | 97.6 | 31.4 | 42.6 | 51.1 | 34.9 | 36.8 | 41.5

###  IV-A Dataset Overview

Figure 4: Our campus data collection platform and some LiDAR data
visualization of the campus dataset.

We evaluate RDMNet and compare it with the state-of-the-art methods on both
publicly available datasets, including KITTI odometry [11], KITTI-360 [12],
Apollo-SouthBay [13] and Mulran [14] datasets, and a self-recorded dataset.
These datasets provide LiDAR scans collected in different environments with
the corresponding ground-truth poses. The KITTI odometry and KITTI-360 contain
LiDAR data collected by a Velodyne HDL64 LiDAR in Germany. These two datasets
use a similar sensor setup but collect data from different times and
environments. The Apollo-SouthBay dataset also uses a Velodyne HDL64 LiDAR but
with a different sensor setup collecting data in the U.S. cities. The Mulran
dataset contains data collected by an OS1-64 LiDAR from Korea. Fig. 4 shows
our own platform equipped with a Velodyne VLP16 LiDAR, an inertial measurement
unit (Xsens MTi-300), and a GNSS (INS CGI-410). We build our own dataset in a
campus environment with ground-truth poses calculated by combining the GNSS
and IMU with the state-of-the-art LiDAR SLAM method [32].

We follow [1, 7] and split the KITTI odometry into three sets: sequences 00-05
for training, 06-07 for validation, and 08-10 for testing. To evaluate the
generalization ability, we directly apply the models trained on the KITTI
odometry dataset to other datasets. Also in line with [1, 7, 6], we use the
LiDAR pairs that are at most 10 m away as samples and get 1358 pairs for
training, 180 pairs for validation, and 14577 pairs for testing. Note that the
sensors, environments, and platform setups are different between the KITTI
odometry datasets to others, which thoroughly tests the generalization ability
of the approaches.

TABLE II: Registration results on multiple datasets using RANSAC- 50k. The results in brackets on the KITTI dataset are those reported in the original paper evaluated under bad ground truth poses. We fix it and also report the new results. The best results are highlighted in bold, and the second bests are marked with underlines. All the models are only trained on the KITTI dataset. | KITTI | KITTI-360 | Apollo | Mulran | Campus
---|---|---|---|---|---
Registration Recall (%)
Predator [1] | 99.82 | 99.50 | 99.27 | 53.02 | 9.94
CofiNet [2] | 99.82 | 99.62 | 100 | 80.79 | 36.84
NgeNet [6] | 99.82 | 99.94 | 100 | 82.96 | 81.29
Geotransformer [7] | 99.82 | 99.86 | 100 | 75.68 | 71.93
RDMNet (ours) | 99.82 | 99.89 | 100 | 87.09 | 96.49
Relative Rotation Error (∘)
Predator [1] | 0.25 (0.27) | 0.29 | 0.21 | 1.03 | 1.94
CofiNet [2] | 0.37 (0.41) | 0.44 | 0.18 | 0.52 | 1.81
NgeNet [6] | 0.26 (0.30) | 0.30 | 0.18 | 0.35 | 1.01
Geotransformer [7] |  0.22 (0.24) | 0.28 | 0.12 | 0.30 | 0.97
RDMNet (ours) | 0.18 | 0.25 | 0.10 | 0.45 | 0.69
Relative Translation Error (cm)
Predator [1] |  5.8 (6.8) | 7.2 | 7.8 | 30.4 | 53.9
CofiNet [2] | 8.2 (8.5) | 10.1 | 6.7 | 17.3 | 38.6
NgeNet [6] | 6.1 (7.4) | 7.5 | 5.9 | 9.2 | 13.6
Geotransformer [7] | 6.7 (7.4) | 8.1 | 6.1 | 12.0 | 18.4
RDMNet (ours) | 5.3 | 7.0 | 4.6 | 14.4 | 12.7

###  IV-B Correspondence Matching Performance

We first evaluate the correspondence matching performance. Following [7], we
use two metrics to evaluate the matching performance: i) Inlier Ratio (IR),
the ratio of correct correspondences with residuals below a certain threshold,
e.g., 0.6 m, after applying the ground truth transformation, and ii) Feature
Match Recall (FMR), the fraction of point cloud pairs with inlier ratio above
a threshold, e.g., 5$\%$.

We compare the results of our method with the recent state-of-the-art methods:
Predator [1], CofiNet [2], NgeNet [6], and Geotransformer [7]. We report the
results in Tab. I with different numbers of samples. The sampling strategy is
slightly different for different methods. For Predator and NgeNet, we use the
default setting that samples points with probability proportional to the
estimated scores. As for our approach, CofiNet, and Geotransformer, because
they directly output point correspondences without interest point sampling, we
pick the top-$k$ correspondences according to fine level soft assignment
scores. Note that, the result of our approach reported on Mulran dataset is
the result after removing the superpoint detection module, as we find that
superpoint detection module is hard to generalize to partially occluded point
clouds. For a fair comparison, we do not retrain the modified model. To our
surprise, RDMNet still achieves the best FMR and the second-best IR on Mulran,
as shown in Tab. I. RDMNet performs even better on other benchmarks, achieving
the best FMR and IR. Notably, RDMNet exceeds the baseline by a large margin of
about 10%-15% in IR. Interestingly, the performance of the keypoint-based
methods and the methods that follow a coarse-to-fine manner present different
trends when the number of samples becomes smaller. Keypoint-based methods,
i.e., Predator and NgeNet, show a downward trend, while coarse-to-fine
methods, i.e., CofiNet, Geotransformer, and ours, show an upward trend. The
reason is that when the number of samples becomes smaller, the keypoint-based
method becomes more difficult to sample the points in the overlap region,
which is underwritten by the reliable patch correspondences for coarse-to-fine
methods.

Figure 5: The registration recall under different thresholds. When changing one of the thresholds, we fix the other one to its default number, i.e., 5∘ for the rotation threshold and 2 m for the translation threshold. TABLE III: Registration results on multiple datasets without RANSAC. All the models are only trained on the KITTI dataset. | KITTI | KITTI-360 | Apollo | Mulran | Campus
---|---|---|---|---|---
Registration Recall (%)
HRegNet [27] | 96.76 | 20.39 | 9.39 | - | 8.19
Geotransformer (LGR) | 99.82 | 99.86 | 100 | 72.91 | 60.23
RDMNet (ours, LGR) | 99.82 | 99.90 | 100 | 83.68 | 86.55
Relative Rotation Error (∘)
HRegNet [27] | 1.04 | 2.18 | 2.14 | - | 2.72
Geotransformer (LGR) | 0.31 (0.31) | 0.36 | 0.29 | 0.49 | 0.97
RDMNet (ours, LGR) | 0.27 | 0.35 | 0.29 | 0.48 | 0.83
Relative Translation Error (cm)
HRegNet [27] | 6.7 | 112.8 | 116.7 | - | 98.3
Geotransformer (LGR) | 5.5 (6.0) | 6.9 | 5.1 | 9.7 | 18.0
RDMNet (ours, LGR) | 3.9 | 5.9 | 3.5 | 9.3 | 16.1
Figure 6: Trajectory estimation results on KITTI dataset using the LiDAR pairs
10 m away.

###  IV-C Point Cloud Registration Performance

The second experiment evaluates the point cloud registration results and
supports our claim that our method outperforms the state-of-the-art method in
point cloud registration.

We also follow [7] using three other metrics to evaluate the registration
performance: i) Relative Translation Error (RTE), the Euclidean distance
between estimated and ground truth translation vectors, ii) Relative Rotation
Error (RRE), the geodesic distance between estimated and ground truth rotation
matrices, and iii) Registration Recall (RR), the fraction of scan pairs whose
RRE and RTE are below certain thresholds, e.g., 5∘ and 2 m.

We compare the results of our method with the recent RANSAC-based state-of-
the-art methods: Predator [1], CofiNet [2], NgeNet [6], and Geotransformer [7]
in Tab. II. There is an error in the evaluation codes of these methods using
KITTI ground-truth except NgeNet. We fix the error and report the results
before the fix as reported in the original papers and new results after the
fix. As can be seen, Our RDMNet achieves the best RR on Mulran and outperforms
all the baselines on all other datasets. Especially on the campus dataset,
RDMNet outperforms baseline methods with a large margin on all metrics. We
further evaluate RR for all the methods at different RRE and RTE thresholds on
the KITTI and Campus datasets (see Fig. 5). Our RMDNet exhibits higher
registration recall at all thresholds. Especially, RMDNet exceeds baseline
methods by a large margin when generalizing to the campus dataset.

TABLE IV: Absolute pose error on sequences 08-10 of KITTI dataset. Best performance is highlighted in bold while the second best is marked with an underline. | Rot. | Rot. | Rot. | Trans. | Trans. | Trans.
---|---|---|---|---|---|---
|  RMSE (∘) |  MAE (∘) |  STD (∘) | RMSE(cm) | MAE(cm) | STD(cm)
KITTI Sequence 08
Predator [1] | 104.7 | 39.77 | 8.13 | 10469.6 | 4228.3 | 4319.7
CofiNet [2] | 8.80 | 4.11 | 1.77 | 879.8 | 335.1 | 381.8
NgeNet [6] | 6.48 | 3.17 | 0.91 | 647.8 | 273.4 | 255.2
Geotransformer [7] | 4.18 | 2.01 | 0.60 | 418.3 | 171.2 | 170.3
RDMNet (ours) | 3.23 | 1.58 | 0.68 | 323.0 | 139.3 | 124.0
KITTI Sequence 09
Predator [1] | 4.14 | 1.99 | 1.12 | 413.5 | 174.9 | 162.5
CofiNet [2] | 3.10 | 2.35 | 1.61 | 309.8 | 121.5 | 131.3
NgeNet [6] | 4.67 | 2.54 | 0.76 | 466.7 | 173.0 | 206.6
Geotransformer [7] | 2.84 | 1.37 | 0.76 | 283.6 | 103.6 | 126.8
RDMNet (ours) | 1.91 | 1.43 | 0.67 | 190.9 | 76.9 | 79.0
KITTI Sequence 10
Predator [1] | 3.5 | 2.55 | 1.37 | 349.7 | 136.6 | 148.7
CofiNet [2] | 3.2 | 2.9 | 1.6 | 319.9 | 134.6 | 126.5
NgeNet [6] | 2.97 | 2.2 | 1.08 | 296.8 | 106.7 | 134.1
Geotransformer [7] | 1.32 | 1.1 | 0.35 | 132.5 | 64.5 | 41.2
RDMNet (ours) | 1.26 | 1.09 | 0.39 | 126.3 | 60.9 | 40.0
Figure 7: Visualizations of our superpoint detection and point patch grouping.
(a) shows the corresponding images of the environment only for reference. (b)
shows the uniformly sampled superpoints (red dots) with their point patches
grouped by point-to-node strategy. We assign each point patch a random color
for visualization. (c) shows the uniformly sampled superpoints with learned
offsets (orange lines). (d) shows the final superpoints after offsetting and
filtering. (e) shows the point patches grouped by the final superpoints. Each
point patch is assigned a random color. Uniformly sampled superpoints can
easily separate a single object into several parts, as seen in (b). This poses
challenges for matching. Our superpoint detection module learns a pattern that
brings the superpoints close to a geometrically significant region together
without using any semantic information. This leads to a more reasonable point
patch grouping which benefits point matching.

We also compare our method to state-of-the-art RANSAC-free methods using
Local-to-Global Registration (LGR) [7]: HRegNet [27] and Geotransformer [7] in
Tab. III. LGR is specifically proposed for superpoint-based approaches [7]. It
calculates poses by performing weighted SVD on dense point correspondences of
each patch and chooses one that admits the most inlier matches, which greatly
reduces the computation time by limiting the iterations to $|\mathcal{M}|$.
When using LGR, our method attains remarkable results for translation
estimation and surpasses the best RANSAC-based results by about 1 cm on KITTI,
KITTI-360, and Apollo datasets. In most cases, our method is the best among
other RANSAC-free methods.

The above experiments evaluate the performance of all the methods in relative
pose estimation. We further evaluate the absolute pose error of all the
methods. We still use the LiDAR pairs 10 m away for transformation estimation
and chain these transformations to obtain the trajectory. Fig. 6 shows the
trajectories estimated by different methods on the three test sequences of the
KITTI dataset. We calculate the root mean squared error (RMSE) and mean
absolute error (MAE) of each estimated trajectory against the ground truth
trajectory listed in Tab. IV. As can be seen, our RMDNet achieves overall the
best performance.

So far, we have demonstrated the superior capability of our RMDNet for point
cloud registration in terms of both relative and absolute pose errors. The
superiorities of our method lay both in its high accuracy on the datasets
similar to the training set (KITTI-360 and Apollo) and in its robustness while
generalizing to the datasets under totally different sensor configurations
(Mulran and Campus). The key to the robustness and accuracy are the two main
modules of the method, i.e., 3D-RoFormer and superpoint detection module. The
3D-RoFormer injects powerful feature representation capability into the
network by encoding relative position information in a lightweight manner,
while the superpoint detection module generates reliable superpoints that
boost the matching and registering significantly.

Figure 8:  Matching and registration results of our RDMNet compared to recent
advances CoFiNet [2] and GeoTransformer[7]. In (a), (c), and (e), we visualize
the matching on three datasets. Our RMDNet finds more inlier matches on
salient regions (e.g., the curbs and the shrubs) and reject the outlier
matches between similar flat patches. (b), (d), and (f) show our RMDNet
achieves more accurate and robust registration compared to baseline methods.

###  IV-D Qualitative Results

To provide more insights into the proposed RDMNet, we visualize the
superpoints and the corresponding point patches learned by our method in Fig.
7. As can be seen, compared to the vanilla uniformly distributed superpoints
(second row), our method can extract the superpoints close to their nearest
geometrically significant region, such as the curbs and objects, as shown from
the third row to the fourth row. Based on that, our method groups the dense
point patches more meaningfully, where points on a single object are gathered
in the same patch (fifth row), which is important for finding accurate
correspondence and obtaining good registration results.

Fig. 8 provides the matching and registration results of our method compared
to Geotransformer [7] and CoFiNet [2]. It shows that our RDMNet finds more
inlier matches on salient regions, rejects outlier matches between similar
flat areas, and performs robust and accurate registration.

###  IV-E Robustness Tests

Figure 9: Registration robustness tests in terms of (a) pair-wise distance and
(b) noise level on the KITTI datasets.

We conduct registration robustness tests regarding different overlap ratios
and noise levels on the KITTI datasets. We generate the testing datasets with
varying overlap ratios using the LiDAR pairs at different distances. See Fig.
9a, in terms of RR, RRE, and RTE, RDMNet achieves the best registration
performance for paired point clouds with varying overlap ratios. For
evaluation under different noise levels, we add zero-mean Gaussian noise with
$\sigma$ standard deviation to the point coordinates. See Fig. 9b, RDMNet
obtains the more accurate and robust registration than competitor algorithms
at all noise levels. Note that RDMNet shows the superior robustness that
maintains an extremely high registration recall of $96.58\%$ compared to other
baselines at a high noise level of $0.9$ m.

###  IV-F Ablation Study

We conduct ablation studies on KITTI and Apollo datasets to better understand
the effectiveness of each module in the proposed RDMNet, and show that the
full RDMNet is the best setup. We use the model trained with negative log-
likelihood loss [7, 2] using the vanilla transformer and without the
superpoint detection module as the base model. Tab. V summarizes the point
registration results of the ablation study. SDM refers to the superpoint
detection module, and RoPE refers to the rotary position embedding. As can be
seen, all modules of our method bring improvement in the point cloud
registration individually. Combining all proposed modules, our RDMNet performs
the best.

We also provide a study on the effectiveness of our proposed 3D-RoFormer. We
compare it with other existing transformers, including vanilla transformer
[2], absolute position embedding (APE) [28], and geometric embedding (GEO)
[7]. We only change the transformer parts in our RDMNet while keeping the rest
parts the same and comparing the point cloud registration results. As shown in
Tab. VI, using our proposed 3D-RoFormer, our RDMNet achieves the best
performance in all metrics on both the KITTI and Campus datasets.

TABLE V: Ablation study of individual modules. SDM | RoPE | gap loss | KITTI | Apollo
---|---|---|---|---
RR | RRE | RTE | RR | RRE | RTE
| ✓ | ✓ | 99.46 | 0.20 | 5.8 | 99.34 | 0.16 | 6.9
✓ |  | ✓ | 99.82 | 0.20 | 5.5 | 98.49 | 0.20 | 6.7
✓ | ✓ |  | 99.82 | 0.18 | 5.7 | 100 | 0.11 | 5.0
✓ | ✓ | ✓ | 99.82 | 0.18 | 5.3 | 100 | 0.10 | 4.6
TABLE VI: Ablation of 3D-RoFormer. Model | KITTI | Campus
---|---|---
RR | RRE | RTE | RR | RRE | RTE
vanilla transformer | 99.82 | 0.32 | 7.3 | 86.55 | 1.70 | 26.6
APE transformer | 99.82 | 0.20 | 5.3 | 91.23 | 0.97 | 15.6
GEO transformer | 99.82 | 0.24 | 6.5 | 88.89 | 1.01 | 20.2
3D-RoFormer (Ours) | 99.82 | 0.18 | 5.3 | 96.49 | 0.69 | 12.7

###  IV-G Study on Runtime and Storage

We measure the runtime and storage of the major module 3D-RoFormer for
different numbers of input nodes per scan. The experiments are performed on an
NVIDIA GeForce GTX 3090 GPU. As shown in Tab. VII, the runtime and storage of
3D-RoFormer increase linearly as the number of input nodes increases, similar
to the vanilla transformer and APE transformer, while less than the quadratic
GEO transformer.

TABLE VII: Runtime and storage of different transformer networks with different numbers of input nodes. Model | Run time (ms) | Storage (MB)
---|---|---
Num. of input nodes | 1000 | 500 | 100 | 1000 | 500 | 100
vanilla transformer | 31 | 24 | 22 | 40 | 23 | 6
APE transformer | 33 | 29 | 24 | 46 | 24 | 6
GEO transformer | 58 | 40 | 26 | 9784 | 2318 | 6
3D-RoFormer (Ours) | 38 | 30 | 28 | 57 | 40 | 6

##  V Conclusion

In this paper, we present RDMNet that leverages a coarse-to-fine strategy to
extract dense point correspondences for point cloud registration. We exploit
insights from natural language processing and keypoint detection and design a
novel transformation-invariant transformer named 3D-RoFormer. It learns to
aggregate contextual and geometric information of the point clouds in a fast
and lightweight way and extracts salient and compact superpoint pairs for
point cloud registration. We evaluate and compare our approach on multiple
datasets, including publicly available ones and our self-recorded dataset
collected from different environments. Extensive experiments suggest that our
approach outperforms the baseline methods in terms of both correspondence
matching and point cloud registration with a strong generalization ability. In
the future, we want to figure out why the voting module does not work well in
the Mulran dataset and improve the voting module’s generalization ability. We
also want to explore the potential of RDMNet to tackle the global localization
problem.

## References

  * [1] S. Huang, Z. Gojcic, M. Usvyatsov, A. Wieser, and K. Schindler.  Predator: Registration of 3d point clouds with low overlap.  In Proc. of the IEEE Conf. on Computer Vision and Pattern Recognition (CVPR), 2021.
  * [2] H. Yu, F. Li, M. Saleh, B. Busam, and S. Ilic.  Cofinet: Reliable coarse-to-fine correspondences for robust pointcloud registration.  Proc. of the Advances in Neural Information Processing Systems (NIPS), 2021.
  * [3] X. Bai, Z. Luo, L. Zhou, H. Fu, L. Quan, and C. Tai.  D3feat: Joint learning of dense detection and description of 3d local features.  In Proc. of the IEEE Conf. on Computer Vision and Pattern Recognition (CVPR), 2020.
  * [4] M. Fischler and R. Bolles.  Random sample consensus: a paradigm for model fitting with applications to image analysis and automated cartography.  Communications of the ACM, 1981.
  * [5] J. Li and G. Lee.  Usip: Unsupervised stable interest point detection from 3d point clouds.  In Proc. of the IEEE Intl. Conf. on Computer Vision (ICCV), 2019\.
  * [6] L. Zhu, H Guan, C. Lin, and R. Han.  Neighborhood-aware geometric encoding network for point cloud registration.  arXiv preprint, 2022.
  * [7] Z. Qin, H. Yu, C. Wang, Y. Guo, Y. Peng, and K. Xu.  Geometric transformer for fast and robust point cloud registration.  In Proc. of the IEEE Conf. on Computer Vision and Pattern Recognition (CVPR), 2022.
  * [8] A. Vaswani, N. Shazeer, N. Parmar, J. Uszkoreit, L. Jones, Aidan A. Gomez, Ł. Kaiser, and I. Polosukhin.  Attention is all you need.  Proc. of the Advances in Neural Information Processing Systems (NIPS), 2017.
  * [9] Z. Yew and G. Lee.  Rpm-net: Robust point matching using learned features.  In Proc. of the IEEE Conf. on Computer Vision and Pattern Recognition (CVPR), 2020.
  * [10] B. Drost, M. Ulrich, N. Navab, and S. Ilic.  Model globally, match locally: Efficient and robust 3d object recognition.  In Proc. of the IEEE Conf. on Computer Vision and Pattern Recognition (CVPR), 2010.
  * [11] A. Geiger, P. Lenz, and R. Urtasun.  Are we ready for Autonomous Driving? The KITTI Vision Benchmark Suite.  In Proc. of the IEEE Conf. on Computer Vision and Pattern Recognition, 2012.
  * [12] Y. Liao, J. Xie, and A. Geiger.  KITTI-360: A novel dataset and benchmarks for urban scene understanding in 2d and 3d.  arXiv preprint, 2021.
  * [13] W. Lu, Y. Zhou, G. Wan, S. Hou, and S. Song.  L3-Net: Towards Learning Based LiDAR Localization for Autonomous Driving.  In Proc. of the IEEE/CVF Conf. on Computer Vision and Pattern Recognition, 2019.
  * [14] X. Zhang, L. Wang, and Y. Su.  Visual place recognition: A survey from deep learning perspective.  Pattern Recognition, 2021.
  * [15] Y. Aoki, H. Goforth, R. Srivatsan, and S. Lucey.  Pointnetlk: Robust & efficient point cloud registration using pointnet.  In Proc. of the IEEE Conf. on Computer Vision and Pattern Recognition (CVPR), 2019.
  * [16] C.R. Qi, H. Su, K. Mo, and L.J. Guibas.  PointNet: Deep Learning on Point Sets for 3D Classification and Segmentation.  In Proc. of the IEEE Conf. on Computer Vision and Pattern Recognition, 2017.
  * [17] Y. Zheng, Y. Li, S. Yang, and H. Lu.  Global-pbnet: A novel point cloud registration for autonomous driving.  IEEE Trans. on Intelligent Transportation Systems (ITS), 2022.
  * [18] X. Huang, G. Mei, and J. Zhang.  Feature-metric registration: A fast semi-supervised approach for robust point cloud registration without correspondences.  In Proc. of the IEEE Conf. on Computer Vision and Pattern Recognition (CVPR), 2020.
  * [19] P. J. Besl and N. D. McKay.  A Method for Registration of 3D Shapes.  IEEE Trans. on Pattern Analalysis and Machine Intelligence, 14(2):239–256, 1992.
  * [20] Z. Zhang.  Iterative point matching for registration of free-form curves and surfaces.  Intl. Journal of Computer Vision, 13(2):119–152, 1994.
  * [21] A. Segal, D. Haehnel, and S. Thrun.  Generalized-ICP.  In Proc. of Robotics: Science and Systems, 2009.
  * [22] H. Deng, T. Birdal, and S. Ilic.  Ppfnet: Global context aware local features for robust 3d point matching.  In Proc. of the IEEE Conf. on Computer Vision and Pattern Recognition (CVPR), 2018.
  * [23] H. Deng, T. Birdal, and S. Ilic.  Ppf-foldnet: Unsupervised learning of rotation invariant 3d local descriptors.  In Proc. of the Europ. Conf. on Computer Vision (ECCV), 2018.
  * [24] L. Li and M. Yang.  Point cloud registration based on direct deep features with applications in intelligent vehicles.  IEEE Trans. on Intelligent Transportation Systems (ITS), 2021.
  * [25] Z. Yew and G. Lee.  3dfeat-net: Weakly supervised local 3d features for point cloud registration.  In Proc. of the Europ. Conf. on Computer Vision (ECCV), 2018.
  * [26] Y. Zhong.  Intrinsic shape signatures: A shape descriptor for 3d object recognition.  In Proc. of the Int. Conf. on Computer Vision (ICCV) Workshops, 2009\.
  * [27] F. Lu, G. Chen, Y. Liu, L. Zhang, S. Qu, S. Liu, and R. Gu.  Hregnet: A hierarchical network for large-scale outdoor lidar point cloud registration.  In Proc. of the IEEE Intl. Conf. on Computer Vision (ICCV), 2021\.
  * [28] C. Shi, X. Chen, K. Huang, J. Xiao, H. Lu, and C. Stachniss.  Keypoint matching for point cloud registration using multiplex dynamic graph attention networks.  IEEE Robotics and Automation Letters (RA-L), 2021.
  * [29] J. Su, Y. Lu, S. Pan, B. Wen, and Y. Liu.  Roformer: Enhanced transformer with rotary position embedding.  arXiv preprint, 2021.
  * [30] H. Thomas, C.R. Qi, J. Deschaud, B. Marcotegui, F. Goulette, and L.J. Guibas.  KPConv: Flexible and Deformable Convolution for Point Clouds.  In Proc. of the IEEE/CVF Intl. Conf. on Computer Vision, 2019.
  * [31] D.P. Kingma and J.Ba.  Adam: A method for stochastic optimization.  arXiv preprint, abs/1412.6980, 2014.
  * [32] T. Shan, B. Englot, D. Meyers, W. Wang, C. Ratti, and D. Rus.  Lio-sam: Tightly-coupled lidar inertial odometry via smoothing and mapping.  In Proc. of the IEEE/RSJ Intl. Conf. on Intelligent Robots and Systems (IROS), 2020.


# Efficient Byzantine-Resilient Stochastic Gradient Descent

Kaiyun Li1,2 Xiaojun Chen1,🖂 Ye Dong1,2 Peng Zhang3 Dakui Wang1 Shuai Zeng1
1Institute of Information Engineering, Chinese Academy of Sciencess, Beijing,
China.
2 School of Cyber Security, University of Chinese Academy of Sciencess,
Beijing, China.
3 Guangzhou University, Guangzhou, China. {likaiyun,
<EMAIL_ADDRESS>
<EMAIL_ADDRESS>
###### Abstract

Distributed Learning often suffers from Byzantine failures, and there have
been a number of works studying the problem of distributed stochastic
optimization under Byzantine failures, where only a portion of workers,
instead of all the workers in a distributed learning system, compute
stochastic gradients at each iteration. These methods, albeit workable under
Byzantine failures, have the shortcomings of either a sub-optimal convergence
rate or high computation cost. To this end, we propose a new Byzantine-
resilient stochastic gradient descent algorithm (BrSGD for short) which is
provably robust against Byzantine failures. BrSGD obtains the optimal
statistical performance and efficient computation simultaneously. In
particular, BrSGD can achieve an order-optimal statistical error rate for
strongly convex loss functions. The computation complexity of BrSGD is
$O(md)$, where $d$ is the model dimension and $m$ is the number of machines.
Experimental results show that BrSGD can obtain competitive results compared
with non-Byzantine machines in terms of effectiveness and convergence.

##  1 Introduction

In the fields of recommendation systems, natural language processing, and
computer vision, it is often the case that we need to build complex models
from large-scale datasets. As the available data for training models
continuously grow, it is urgent to use distributed learning to digest these
large-scale data. In a distributed learning system, robustness and security
issues have become a major concern. In particular, individual computing units,
i.e., worker machines, may exhibit abnormal behavior due to data corruption,
hardware/software malfunction, communication delay, etc. This abnormal (even
worse adversarial) behavior is typically modeled as Byzantine failure Lamport
et al. (1982). It is well-known that a single Byzantine-faulty machine can
arbitrarily skew standard distributed learning algorithms based on naive
gradients aggregation, e.g., an average of the gradients collected from all
the workers Blanchard et al. (2017). Moreover, Byzantine failure is
exacerbated in Federated Learning (FL), where training data resides at
autonomous worker machines, and a central server facilitates the learning
process Konečnỳ et al. (2015); McMahan et al. (2017); Kairouz and McMahan
(2021). The behavior of a worker machine under Byzantine failure is often
unpredictable, and even becomes susceptible to malicious and coordinated
attacks Aono et al. (2017); Zhao et al. (2020). Therefore, it is increasingly
important to develop robust distributed algorithms in the adversarial setting.

Existing works on Blanchard et al. (2017); Feng et al. (2014); Chen et al.
(2017); Xie et al. (2018); Yin et al. (2018) suffer from the shortcomings of
either a sub-optimal statistical guarantees or high computation cost. They are
inapplicable to distributed settings where. As a result, we wish to develop
distributed learning algorithms that can achieve two objectives
simultaneously. The first objective is  Byzantine-resilience which refers to
achieving the best performance even though a relatively large fraction of the
workers are Byzantine. The second objective is high computation efficiency
which refers to preserving as much as possible the run-time speedup by using
distributing computation across multiple workers.

To deal with Byzantine failures, an intuitive solution is to use coordinate-
wise median Yin et al. (2018) and its variants Chen et al. (2017); Xie et al.
(2018). However, these methods independently consider each single exception
dimension, which requires heavy computation cost when there are a large number
of dimensions. For example, to compute the median value of a single exception
dimension, the easiest way is to apply a sorting algorithm to the dimension,
which yields a time complexity of $O(dm\log m)$. This time complexity is
unaffordable when $d$ is very large.

In this paper, we define a new metric for the gradient vector to evaluate
whether it is a Byzantine worker. Our key insight is to directly use the
$\ell_{1}$-norm constraint to eliminate abnormal gradients, which can greatly
simplify the calculation. Specifically, let $\boldsymbol{g}^{i}$ be a
stochastic gradient computed by a worker $i\in[m]$, then $\boldsymbol{g}^{i}$
shall concentrate around $\boldsymbol{g}^{med}$, where $\boldsymbol{g}^{med}$
is the median value of $\boldsymbol{g}^{i},i\in[m]$. In other words, if
$\|\boldsymbol{g}^{i}-\boldsymbol{g}^{med}\|_{1}>2\mathfrak{T}$, where
$\mathfrak{T}>0$ is a hyper-parameter, then we can declare worker $i$ as
Byzantine.

Figure 1: The gradients are collected and combined into a matrix. Taking a
column of the matrix, the values uploaded by the normal workers in this column
has little difference.

A challenge to the $\ell_{1}$-norm method is that some Byzantine workers may
hide without violating the constraint. Then, we further define a score for
each gradient. As shown in Fig.1, the master machine needs to collect the
gradients that are flattened into a $d$-dimensional vector from all the
workers, and then align these vectors into a new matrix by columns. As shown
in Fig.2, when taking one column of the matrix, we can observe that a subset
with a smaller number of elements must deviate heavier from the global mean
value than a larger number of elements. Based on the observations that the
honest majority and the values uploaded by the normal workers are with little
difference, a subset with a smaller number of elements is more likely to
contain Byzantine workers. Therefore, we can judge the outliers according to
each dimension of the gradient and count the number of outliers as a score. We
keep the $\beta$-fraction gradients with the highest scores.

Noted that Byzantine workers may be falsely labeled as good ones. Fortunately,
the convergence rates of our method are not impacted significantly.
Especially, the subroutine for calculating the score has only one round of
comparison and one round of averaging. Thus, it is computationally efficient,
almost the same as a naive method implemented through averaging Polyak and
Juditsky (1992). The contributions of the paper can be summarized as follows:

  * •

We present a new robust aggregation rule for distributed synchronous
Stochastic Gradient Descent algorithm BrSGD in an adversarial setting. The new
algorithm can handle Byzantine resilience. Moreover, the computation
complexity of the proposed algorithm is $O(md)$.

  * •

We theoretically analyze the statistical error rates of our method on strongly
convex loss functions. In particular, our algorithm can achieve an order-
optimal statistical error rate for strongly convex losses.

  * •

We also demonstrate the convergence of the proposed algorithm by conducting
empirical studies. The experimental results on four types of Byzantine attacks
match the results of none-Byzantine machines in terms of effectiveness and
convergence.

The rest of this paper is organized as follows. Related work is summarized in
Section 2. In Section 3, we formulate the problem of this work. Section 4
presents our method and analyzes the statistical error rates. In Section 5, we
present the empirical evaluations, and we conclude this work in Section 6.

Figure 2: The goal of Byzantine workers ($\mathrm{subset}_{2}$) is to make the
mean value of the set $\\{x_{1},\dots,x_{8}\\}$ deviating from the real mean
of the $\mathrm{subset}_{1}$ as much as possible. However, based on the honest
majority assumption, the number of elements in $\mathrm{subset}_{1}$ is
greater than $\mathrm{subset}_{2}$, i.e., $d_{1}<d_{2}$. Thus, we can infer
whether the Byzantine worker is included according to the number of elements
in the two subsets divided by the mean value.

##  2 Related Work

Recently there have been a large number of works stuyding the problem of
Byzantine stochastic optimization Blanchard et al. (2017); Feng et al. (2014);
Su and Vaidya (2016); Chen et al. (2017); Alistarh et al. (2018); Su and
Vaidya (2019); Xie et al. (2018); Yin et al. (2018); Su and Xu (2019); Chen et
al. (2018). Here, we compare existing Byzantine-robust distributed learning
algorithms that are most relevant to our work and summarize the comparison in
this section.

According to different ideas, existing algorithms can be roughly divided into
the following three categories, i.e., Median-based method, Anomaly-detection-
based method, and Redundant-gradients-based method.

The median-based method is used in the context of Byzantine-tolerant
distributed learning in papers Blanchard et al. (2017); Feng et al. (2014).
The median-based method can be further sub-divided into Geometric Median Chen
et al. (2017) and Marginal Median Xie et al. (2018); Yin et al. (2018). For
geometric median, the $(1+\epsilon)$-approximate geometric median can be
computed in $O(dm\log^{3}\frac{1}{\epsilon})$ Cohen et al. (2016). An
algorithm called the selection algorithm Blum et al. (1973) with average time
complexity $O(m)$ ($O(m^{2})$ is the worst case) to obtain median values.
Anomaly detection is performed by running the $T$ iterations Alistarh et al.
(2018); Allen-Zhu et al. (2021). Although computation complexity is
considerable for anomaly detection methods, each gradient needs to be checked,
and inner product operations are also involved. These operations are very
time-consuming in practical. In these algorithms, the most time-consuming is
via redundant gradients methods (ideas from coding theory) Chen et al. (2018).

The closest literature is the work of Yin et al. Yin et al. (2018). They
consider a similar Byzantine model, but for gradient descent (GD). Reference
Blanchard et al. (2017) proposes a general Byzantine-resilient gradient
aggregation rule called Krum. This rule has expensive complexity
$O(m^{2}(d+\log m))$ and does not provide a characterization of the
statistical errors. Recent work Chen et al. (2017) only applies in the
strongly convex setting and is sub-optimal convergence rate. In contrast, our
algorithm is efficient ($O(md)$) in computational complexity and achieves
order-optimal statistical error rates for strongly convex losses.

##  3 Preliminaries

First of all, we introduce the used notations. A vector is denoted as
$\boldsymbol{w}$, and $\boldsymbol{w}_{i}$ denotes the $i$-th element of
$\boldsymbol{w}$. Matrices are denoted as $\boldsymbol{M}$. We let
$\boldsymbol{M}_{i,j}$ denote its entry at location $(i,j)$,
$\boldsymbol{M}_{i,\cdot}$ denote its $i$-th row, and
$\boldsymbol{M}_{\cdot,j}$ denote its $j$-th column. $[N]$ denotes
$\\{1,2,\dots,N\\}$. For any differentiable function $f$, we denote its
partial derivative for the $i$-th argument by $\partial_{i}f$. We index the
set of worker machines by $[m]$, and denote the set of Byzantine machines by
$\mathcal{B}\in[m]$ (thus $|\mathcal{B}|=\alpha m$).

We consider a distributed computation model with one master machine and $m$
worker machines and that an $\alpha$-fraction of the workers may be Byzantine
(where $\alpha<1/2$). Each worker machine stores $n$ samples, each of which is
sampled independently from an unknown distribution $\mathcal{D}$.
$\ell_{i}(\boldsymbol{w};\boldsymbol{x})$ be a loss function of $i$-th worker
machine associated with parameter vector
$\boldsymbol{w}\in\mathcal{W}\in\mathbb{R}^{d}$ and the sample
$\boldsymbol{x}$, where $\mathcal{W}$ is the parameter space. Denoted the
$j$-th data on the $i$-th worker machine by $\boldsymbol{x}^{i,j}$, and
$F_{i}(\boldsymbol{w}):=\frac{1}{n}\sum_{j=1}^{n}\ell_{i}(\boldsymbol{w},\boldsymbol{x}^{i,j})$
denote the empirical risk function for the $i$-th worker. Our goal is to learn
a model defined by the parameter that minimizes the population loss:

$\boldsymbol{w}^{*}=\arg\min_{\boldsymbol{w}\in\mathbb{R}^{d}}F(\boldsymbol{w}),$
(1)

where

$F(\boldsymbol{w}):=\mathbb{E}[F_{i}(\boldsymbol{w})].$ (2)

The parameter space $\mathcal{W}$ is compact with diameter $D$, i.e.,
$\|\boldsymbol{w}-\boldsymbol{w}^{{}^{\prime}}\|_{2}\leq
D,\forall\boldsymbol{w},\boldsymbol{w}^{{}^{\prime}}\in\mathcal{W}$.

Input:initialize parameters $\boldsymbol{w}^{0}\in\mathcal{W}$, step-size
$\eta$, hyperparameters $0<\beta<\frac{1}{2}$, thresholds $\mathfrak{T}>0$,
and iterations $T$;

Master machine: send $\boldsymbol{w}^{0}$ to all the worker machines;

for  _$t=0,1,\dots,T-1$_ do

for  _all $i\in[m]$_ do

Worker machine $i$: compute local gradient;

$\boldsymbol{g}^{i}(\boldsymbol{w}^{t})=\begin{cases}\nabla\ell_{i}(\boldsymbol{w}^{t}),\quad&i\in[m]\backslash\mathcal{B},\\\
\ast,&i\in\mathcal{B}.\end{cases}$ upload
$\boldsymbol{g}^{i}(\boldsymbol{w}^{t})$ to master machine;

end for

Master machine: compute aggregate gradient
$\boldsymbol{g}(\boldsymbol{w}^{t})\leftarrow\mathcal{A}_{\beta,\mathfrak{T}}(\\{\boldsymbol{g}^{i}(\boldsymbol{w}^{t}):i\in[m]\\}),$
and then send $\boldsymbol{g}(\boldsymbol{w}^{t})$ to all worker machines;

Worker machine: update model parameter
$\boldsymbol{w}^{t+1}\leftarrow\boldsymbol{w}^{t}-\eta\boldsymbol{g}(\boldsymbol{w}^{t})$

end for

Algorithm 1 Byzantine-resilient SGD (BrSGD)

##  4 Our Method

This section presents our Byzantine-Resilient stochastic gradient descent
algorithm (named BrSGD) and briefly summarizes our convergence results on its
performance.

###  4.1 BrSGD Algorithm

The master machine broadcasts the initialized model, and all the workers
receive and accept it as the local initialized model. Then, the master and the
workers update the model iteratively. At each iteration, the normal workers
compute the gradients of their local loss functions and then upload to the
master. The Byzantine workers may send any messages. Next, the master performs
a robust aggregator to compute gradients for model updating and send the
gradient to all workers. After receiving the gradient from the master, the
workers update its parameters in the way of gradient descent and moves into
the next iteration until the whole algorithm is completed. The formulation is
illustrated in Algorithm 1.

In the following context, we focus on the aggregation method construction.
Intuitively, the aggregation rule should return a vector $\boldsymbol{g}$ that
is not too far from the real gradient $\nabla F(\boldsymbol{w})$. More
precisely, $\boldsymbol{g}$ should approximate the steepest direction of the
loss function being optimized. This is expressed as upper bound
$\|\boldsymbol{g}^{i}-\boldsymbol{g}^{med}\|_{1}\leq 2\mathfrak{T}$ on
worker’s gradient vector $\boldsymbol{g}^{i}$ (Constraint 1). If the gradient
satisfies Constraint 1, we add it to the candidates $\mathcal{C}_{1}$. To
further eliminate the impacts of potential anomaly values in candidates, we
set a score to each $\boldsymbol{g}^{i}$ and keep the $\beta$-fraction
gradients with larger scores (Constraint 2). Concretely, the master collect
the gradients that are flattened into a $d$-dimensional vector from all
workers and then align them into a new matrix $\boldsymbol{G}$ by column.
Then, we utilize the observation (cf. Section 1) to mark the anomaly values of
$\boldsymbol{G}$ column-wise. We divide one column of data into two subsets
using their mean and set the subset with a large number of elements to 1,
otherwise 0. Finally, a scoring matrix $\boldsymbol{M}$ composed of 0 and 1
will be generated, and the result of adding the rows will be used as a score
for the corresponding gradient. For each worker $i$, we define the score
$\boldsymbol{s}_{i}=\sum_{j\in[d]}\boldsymbol{M}_{i,j},i\in[m]$. For the
details, please see Algorithm 2.

###  4.2 Convergence Analysis

Inputs: gradient set $\\{\boldsymbol{g}^{i}(\boldsymbol{w}^{t}),i\in[m]\\}$,
hyperparameters $0<\alpha<\beta\leq\frac{1}{2}$, and thresholds
$\mathfrak{T}>0$;

Return: aggregation gradient $\boldsymbol{g}(\boldsymbol{w}^{t})$;

$\boldsymbol{a}=0,\boldsymbol{s}=0,\boldsymbol{n}=0,\boldsymbol{M}=\boldsymbol{0};$
# Initialize the mean vector $\boldsymbol{a}$, score vector $\boldsymbol{s}$,
$\ell_{1}$-norm vector $\boldsymbol{n}$, and score matrix $\boldsymbol{M}$;

for  _$c=0,1,\dots,d$_ do

for  _$r=0,1,\dots,m$_ do

$\boldsymbol{a}_{c}=\boldsymbol{a}_{c}+\boldsymbol{a}_{r}$;

end for

$\boldsymbol{a}_{c}=\boldsymbol{a}_{c}/m;$ # calculate the average value of
the arranged gradient matrix by column;

end for

for  _$c=0,1,\dots,d$_ do

$counter=0$;

for  _$r=0,1,\dots,m$_ do

if  _$\boldsymbol{g}_{c}^{r}(\boldsymbol{w}^{t})\geq\boldsymbol{a}_{c}$_ then

$\boldsymbol{M}_{r,c}=1$;

$counter=counter+1$;

end if

else

$\boldsymbol{M}_{r,c}=0$;

end if

end for

if  _$counter <m/2$_ then

$\boldsymbol{M}_{\cdot,d}=\lnot\boldsymbol{M}_{\cdot,d};$ # obtain the score
matrix based on observation 1;

end if

$\boldsymbol{s}=\boldsymbol{s}+\boldsymbol{M}_{\cdot,d}^{T};$ # calculate the
score for each gradient;

end for

$\boldsymbol{g}_{med}=\mathrm{median}\\{\boldsymbol{g}^{i}(\boldsymbol{w}^{t}):i\in[m]\\}$;

$\mathcal{C}_{1}=\\{i:\|\boldsymbol{g}^{i}(\boldsymbol{w}^{t})-\boldsymbol{g}_{med}\|_{1}\leq
2\mathfrak{T}\\};$ # Constraint 1;

$\mathcal{C}_{2}=\\{i:\mathrm{Top}_{max}^{\beta}(\boldsymbol{s}_{i}),i\in[m]\\};$
# Constraint 2;

$\boldsymbol{g}(\boldsymbol{w}^{t})=\textrm{mean}(\boldsymbol{g}^{i}(\boldsymbol{w}^{t}):i\in\mathcal{C}_{1}\cap\mathcal{C}_{2})$;

Algorithm 2 Aggregator
$\mathcal{A}_{\beta,\mathfrak{T}}(\\{\boldsymbol{g}^{i}(\boldsymbol{w}^{t}):i\in[m]\\})$

In this part, we provide statistical guarantees on the error rates (defined as
the distance between $\boldsymbol{w}^{T}$ and the optimal solution
$\boldsymbol{w}^{*}$) of the algorithms. Throughout we assume that the loss
function $F(\boldsymbol{w})$ is smooth.

######  Assumption 1.

In each iteration $t$, each normal worker machine $i\in[m]$ gives back a
vector $\nabla\ell_{i}(\boldsymbol{w}^{t})\in\mathbb{R}^{d}$ satisfying
$\|\nabla\ell_{i}(\boldsymbol{w}^{t})-\nabla
F(\boldsymbol{w}^{t})\|_{1}\leq\mathcal{V}$.

One can instead assume $Pr[\|\nabla\ell_{i}(\boldsymbol{w}^{t})-\nabla
F(\boldsymbol{w}^{t})\|_{1}\geq t]\leq 2\exp(-t^{2}/2\mathcal{V}^{2})$ and the
results of this paper continue to hold up to logarithmic factors. But we
assumes $F(\boldsymbol{w}_{t})$ is Lipschtz continuous, which implies
$\|\nabla\ell_{i}(\boldsymbol{w}^{t})-\nabla F(\boldsymbol{w}^{t})\|_{1}$ is
bounded. To present the simplest theory, we assumed it is bound with
probability 1.

Firstly, we introduces Lemma 1, which is used to bound the output of algorithm
2.

######  Lemma 1.

In our algorithm, suppose that the one dimensional samples on all the normal
worker machines are independent and identically distributed (i.i.d). Satisfy
$v$-sub-exponential with mean $\mu$. For any $t\geq 0$ and $s\geq 0$, let
$|\frac{1}{|\mathcal{C}_{1}\cap\mathcal{C}_{2}|}\sum_{i\in[m]\backslash\mathcal{B}}g^{i}-\mu|\leq
t$ and $\max_{i\in[m]\backslash\mathcal{B}}|g^{i}-\mu|\leq s$. If we set
$\mathfrak{T}=s\leq\mathcal{V}$, then we have

$|\mathcal{A}_{\beta,\mathfrak{T}}(\\{g^{i}:i\in[m]\\})-\mu|\leq t+3\beta s$
(3)

###### Proof.

To simplify notation, we define $\mathcal{M}=[m]\backslash\mathcal{B}$ as the
set of all normal worker machines,
$\mathcal{C}=\\{\mathcal{C}_{1}\cap\mathcal{C}_{2}\\}\subseteq[m]$ as the set
of candidates, and $\mathcal{R}\subseteq[m]$ as the set of all removed
machines. The estimator simply computes

$\mathcal{A}_{\beta,\mathfrak{T}}(\\{g^{i}:i\in[m]\\})=\frac{1}{|\mathcal{C}|}\sum_{i\in\mathcal{C}}g^{i}$
(4)

Condition 1 and Assumption 1 ensures that the boundary of each dimension of
the gradient in the candidate set does not exceed $2s$. Then, We have

$\displaystyle|\mathcal{A}_{\beta,\mathfrak{T}}(\\{g^{i}:i\in[m]\\})-\mu|=\left|\frac{1}{|\mathcal{C}|}\sum_{i\in\mathcal{C}}g^{i}-\mu\right|$
(5)
$\displaystyle=\frac{1}{|\mathcal{C}|}\left|\sum_{i\in\mathcal{M}}(g^{i}-\mu)-\sum_{i\in\mathcal{M}\cap\mathcal{R}}(g^{i}-\mu)+\sum_{i\in\mathcal{B}\cup\mathcal{C}}(g^{i}-\mu)\right|$
$\displaystyle\leq\frac{1}{|\mathcal{C}|}\left((1-\alpha)mt+\beta ms+2\alpha
ms\right)$ $\displaystyle\leq t+3\beta s$

where the last inequality is by $\beta\geq\alpha$. We directly obtain the
desired result. ∎

######  Assumption 2 (Smoothness of $\ell$ and $F$).

For any $\boldsymbol{x}\in\mathcal{X}$, the partial derivative of
$\ell(\cdot;\boldsymbol{x})$ with respect to the $k$-th coordinate of its
first argument, denoted by $\partial_{k}\ell(\cdot;\boldsymbol{x})$, is
$L_{k}$-Lipschitz continuity for each $k\in[d]$, and the function
$\ell(\cdot;\boldsymbol{x})$ is $G$-Lipschitz smoothness. Let
$L:=\sqrt{\sum_{k=1}^{d}L_{k}^{2}}$. Also assume that the population loss
function $F(\cdot)$ is $G_{F}$-Lipschitz smoothness. It is easy to see that
$G_{F}\leq G\leq L$.

####  4.2.1 Strongly Convex Losses

We consider the case where the population loss function $F(\cdot)$ is strongly
convex.

######  Theorem 1.

suppose that Assumption 2 hold, $F(\cdot)$ is $\lambda_{F}$-strongly convex,
and $\alpha\leq\frac{1}{2}-\epsilon$ for some $\epsilon>0$. In addition, we
assume that $\partial_{k}\ell(\boldsymbol{w};\boldsymbol{x})$ is $v$-sub-
exponential for any $k\in[d]$ and $\boldsymbol{w}\in\mathcal{W}$. Choose step-
size $\eta=1/G_{F}$. Then, with probability at least
$1-\frac{4d}{(1+nmLD)^{d}}$, after $T$ parallel iterations, we have

$\|\boldsymbol{w}^{T}-\boldsymbol{w}^{*}\|_{2}\leq\left(1-\frac{\lambda_{F}}{G_{F}+\lambda_{F}}\right)^{T}\|\boldsymbol{w}^{0}-\boldsymbol{w}^{*}\|_{2}+\frac{2}{\lambda_{F}}\triangle$

where

$\triangle=\widetilde{O}\left(\frac{1}{\sqrt{n}}+\frac{1}{\sqrt{nm}}\right)$

Note that this paper Yin et al. (2018) provide a lower bound showing that the
error rate of any algorithm is
$\widetilde{\Omega}(\frac{\alpha}{\sqrt{n}}+\frac{1}{\sqrt{nm}})$. Therefore,
our algorithm achieved order-optimal statistical error rate.

###### Proof.

The proof is essentially the same as Yin et al. (2018). Therefore, we omit the
details of the analysis here. Choosing

$t=v\max\left\\{\frac{8d}{nm}\log(1+nmLD),\sqrt{\frac{8d}{nm}\log(1+nmLD)}\right\\},$

and

$\displaystyle s$ $\displaystyle=v\max\left\\{\frac{4}{n}(d\log(1+nmLD)+\log
m)\right.$
$\displaystyle\qquad\qquad\qquad\left.,\sqrt{\frac{4}{n}(d\log(1+nmLD)\log
m)}\right\\}.$

By using the simple algebra, we have

$\triangle=\widetilde{O}\left(\frac{1}{\sqrt{n}}+\frac{1}{\sqrt{nm}}\right)$

∎

##  5 Experiments

Algorithms | Ours | Median | Mean | Krum
---|---|---|---|---
$\alpha$ | 0 | $10\%$ | $25\%$ | $50\%$ | $10\%$ | $25\%$ | $50\%$ | $10\%$ | $25\%$ | $50\%$ | $10\%$ | $25\%$ | $50\%$
Gaussian | 84.16 | 83.42 | 84.56 | 83.29 | 83.73 | 85.40 | 86.78 | 9.93 | 9.93 | 9.93 | 82.04 | 79.56 | 79.62
Model Negation | 85.87 | 83.89 | 84.07 | 82.13 | 83.29 | 84.47 | 82.84 | 10.84 | 10.84 | 10.84 | 80.44 | 81.18 | 79.36
Gradient Scale | 85.29 | 84.33 | 83.67 | 82.87 | 81.00 | 61.13 | 9.80 | 85.87 | 82.47 | 60.67 | 77.20 | 81.33 | 70.76
Label Inverse | 85.11 | 82.93 | 82.49 | 83.93 | 84.91 | 86.00 | 82.09 | 72.71 | 74.93 | 80.11 | 81.82 | 78.56 | 68.76
Table 1: Test results of LeNet on FashionMNIST in terms of accuracy using
stochastic gradient descent.

We implemented BrSGD in Python3. Our experiments are executed on
Intel$\circledR$ Xeon$\circledR$ CPU E5-2650 v3@ 2.30GHz servers with 64GB
RAM. We simulate $m=20$ clients. The model is learned atop Pytorch v1.6.0
equipped with CUDA v10.2 and one 12G memory TITAN Xp GPU. the C-S connection
is over WAN with 50Mbps bandwidth and 50ms RTT.

###  5.1 Experimental settings

We conduct experiments to show the Byzantine resilience in the following four
classic adversarial settings:

  * •

We consider the attackers that replace some of the gradient vectors with
Gaussian random vectors with zero mean and isotropic covariance matrix with
standard deviation 200. We refer to this kind of attack as Gaussian Attack.

  * •

For each Byzantine gradient vector, the gradient is replaced by the negative
sum of all the correct gradients, scaled by a large constant (1e10 in the
experiments). We call this attack Model Negation Attack.

  * •

We generate the Byzantine machines in the following way: we replace every
training label $y$ on these machines with $9-y$, e.g., 1 is replaced with 8, 7
is replaced with 2, etc., and the Byzantine machines compute gradients on
these data. Denote this kind of attack by Label Shift.

  * •

Named after Gradient Scale Attack, an attacker replaces some of the gradient
vectors with scaled by a constant (1e10 in the experiments).

We instantiate $m=20$ workers and one master node in experiments, and train a
convolutional neural network model (LeNet LeCun et al. (1998)) on the
FashionMNIST dataset Xiao et al. (2017) using mini-batch stochastic gradient
descent to compare the test accuracies in those above four adversarial
settings. We compare accuracy and convergence with Mean (find the average of
all gradients), KrumBlanchard et al. (2017), and coordinate-wise medianYin et
al. (2018).

###  5.2 Experimental results

Figure 3: The results w.r.t. accuracy vary with the epochs under Byzantine
attacks, where we set step-size $\eta=0.03$ for the LeNet on FashionMNIST.
Curves correspond to losses, and columns correspond to different aggregation
methods. Byzantine workers perform four attacks with 10%, 25%, and 50%
attackers, respectively. We set $\beta=1/2$ for our algorithm.

As is shown in Figure 3, we observe that even with a single attacker
performing a Gaussian Attack or Model Negation Attack, using the Mean method
directly is devastating (a0,a1). Although the median-based method has high
accuracy, the convergence is very slow (b1,b3). Krum and our method have good
accuracy, but the effect of Krum will drop precipitously when the number of
Byzantine worker machines is large ($\alpha=50\%$,c3). In contrast, we can see
that our algorithm has the same convergence as the average method without an
attack ($\alpha=0$). When the $\alpha=50\%$, the model still achieves high
accuracy. We also include the full test accuracy comparison table in Table 1.

In conclusion, the distributed gradient descent algorithm suffers from severe
performance loss in adversarial settings. Moreover, show our algorithm can
indeed defend against Byzantine failures. Compared with the median-based and
Krum methods, our algorithm has excellent accuracy and faster convergence for
the four attacks.

##  6 Conclusion

In this paper, we study a new distributed stochastic optimization algorithm in
an adversarial setting with the purpose of obtaining the optimal statistical
results and computation efficiency simultaneously. Based on the honest-
majority assumption, we propose a new stochastic gradient descent algorithm
BrSGD. We show that the method can achieve an order-optimal
$\widetilde{O}\left(\frac{1}{\sqrt{n}}+\frac{1}{\sqrt{nm}}\right)$ for
strongly convex losses, and the computation complexity of our algorithm is
$O(md)$. Moreover, we conduct extensive experiments to show that our method
outperforms the state-of-the-art methods in terms of effectiveness and
convergence.

## References

  * Alistarh et al. [2018] Dan Alistarh, Zeyuan Allen-Zhu, and Jerry Li.  Byzantine stochastic gradient descent.  In S. Bengio, H. Wallach, H. Larochelle, K. Grauman, N. Cesa-Bianchi, and R. Garnett, editors, Advances in Neural Information Processing Systems, volume 31. Curran Associates, Inc., 2018.
  * Allen-Zhu et al. [2021] Zeyuan Allen-Zhu, Faeze Ebrahimianghazani, Jerry Li, and Dan Alistarh.  Byzantine-resilient non-convex stochastic gradient descent.  In International Conference on Learning Representations, 2021.
  * Aono et al. [2017] Yoshinori Aono, Takuya Hayashi, Lihua Wang, Shiho Moriai, et al.  Privacy-preserving deep learning via additively homomorphic encryption.  IEEE Transactions on Information Forensics and Security, 13(5):1333–1345, 2017.
  * Blanchard et al. [2017] Peva Blanchard, El Mahdi El Mhamdi, Rachid Guerraoui, and Julien Stainer.  Machine learning with adversaries: Byzantine tolerant gradient descent.  In Proceedings of the 31st International Conference on Neural Information Processing Systems, pages 118–128, 2017.
  * Blum et al. [1973] Manuel Blum, Robert W. Floyd, Vaughan R. Pratt, Ronald L. Rivest, and Robert Endre Tarjan.  Time bounds for selection.  J. Comput. Syst. Sci., 7(4):448–461, 1973.
  * Chen et al. [2017] Yudong Chen, Lili Su, and Jiaming Xu.  Distributed statistical machine learning in adversarial settings: Byzantine gradient descent.  Proceedings of the ACM on Measurement and Analysis of Computing Systems, 1(2):1–25, 2017.
  * Chen et al. [2018] Lingjiao Chen, Hongyi Wang, Zachary Charles, and Dimitris Papailiopoulos.  Draco: Byzantine-resilient distributed training via redundant gradients.  In International Conference on Machine Learning, pages 903–912. PMLR, 2018.
  * Cohen et al. [2016] Michael B Cohen, Yin Tat Lee, Gary Miller, Jakub Pachocki, and Aaron Sidford.  Geometric median in nearly linear time.  In Proceedings of the forty-eighth annual ACM symposium on Theory of Computing, pages 9–21, 2016.
  * Feng et al. [2014] Jiashi Feng, Huan Xu, and Shie Mannor.  Distributed Robust Learning.  arXiv e-prints, page arXiv:1409.5937, September 2014.
  * Kairouz and McMahan [2021] Peter Kairouz and H. Brendan McMahan.  Advances and open problems in federated learning.  Foundations and Trends® in Machine Learning, 14(1):–, 2021.
  * Konečnỳ et al. [2015] Jakub Konečnỳ, Brendan McMahan, and Daniel Ramage.  Federated optimization: Distributed optimization beyond the datacenter.  arXiv preprint arXiv:1511.03575, 2015.
  * Lamport et al. [1982] Leslie Lamport, Robert Shostak, and Marshall Pease.  The byzantine generals problem.  ACM Trans. Program. Lang. Syst., 4(3):382–401, July 1982.
  * LeCun et al. [1998] Yann LeCun, Léon Bottou, Yoshua Bengio, and Patrick Haffner.  Gradient-based learning applied to document recognition.  Proceedings of the IEEE, 86(11):2278–2324, 1998.
  * McMahan et al. [2017] Brendan McMahan, Eider Moore, Daniel Ramage, Seth Hampson, and Blaise Aguera y Arcas.  Communication-efficient learning of deep networks from decentralized data.  In Artificial Intelligence and Statistics, pages 1273–1282. PMLR, 2017.
  * Polyak and Juditsky [1992] Boris T Polyak and Anatoli B Juditsky.  Acceleration of stochastic approximation by averaging.  SIAM journal on control and optimization, 30(4):838–855, 1992.
  * Su and Vaidya [2016] Lili Su and Nitin H Vaidya.  Fault-tolerant multi-agent optimization: optimal iterative distributed algorithms.  In Proceedings of the 2016 ACM symposium on principles of distributed computing, pages 425–434, 2016.
  * Su and Vaidya [2019] Lili Su and Nitin H Vaidya.  Defending non-bayesian learning against adversarial attacks.  Distributed Computing, 32(4):277–289, 2019.
  * Su and Xu [2019] Lili Su and Jiaming Xu.  Securing distributed gradient descent in high dimensional statistical learning.  Proc. ACM Meas. Anal. Comput. Syst., 3(1), March 2019.
  * Xiao et al. [2017] Han Xiao, Kashif Rasul, and Roland Vollgraf.  Fashion-MNIST: a Novel Image Dataset for Benchmarking Machine Learning Algorithms.  arXiv e-prints, page arXiv:1708.07747, August 2017.
  * Xie et al. [2018] Cong Xie, Oluwasanmi Koyejo, and Indranil Gupta.  Generalized Byzantine-tolerant SGD.  arXiv e-prints, page arXiv:1802.10116, February 2018.
  * Yin et al. [2018] Dong Yin, Yudong Chen, Ramchandran Kannan, and Peter Bartlett.  Byzantine-robust distributed learning: Towards optimal statistical rates.  In International Conference on Machine Learning, pages 5650–5659. PMLR, 2018.
  * Zhao et al. [2020] B. Zhao, Konda Reddy Mopuri, and Hakan Bilen.  Idlg: Improved deep leakage from gradients.  ArXiv, abs/2001.02610, 2020.