# Neural Volumetric Memory for Visual Locomotion Control

Ruihan Yang1 Ge Yang2,3 Xiaolong Wang1
1UC San Diego 2Institute of AI and Fundamental Interactions 3MIT CSAIL

###### Abstract

Legged robots have the potential to expand the reach of autonomy beyond paved
roads. In this work, we consider the difficult problem of locomotion on
challenging terrains using a single forward-facing depth camera. Due to the
partial observability of the problem, the robot has to rely on past
observations to infer the terrain currently beneath it. To solve this problem,
we follow the paradigm in computer vision that explicitly models the 3D
geometry of the scene and propose Neural Volumetric Memory (NVM), a geometric
memory architecture that explicitly accounts for the SE(3) equivariance of the
3D world. NVM aggregates feature volumes from multiple camera views by first
bringing them back to the ego-centric frame of the robot. We test the learned
visual-locomotion policy on a physical robot and show that our approach, which
explicitly introduces geometric priors during training, offers superior
performance than more naïve methods. We also include ablation studies and show
that the representations stored in the neural volumetric memory capture
sufficient geometric information to reconstruct the scene. Our project page
with videos is https://rchalyang.github.io/NVM

Figure 1: Real-World Deployment: We deploy our policy in real-world
environments with Stones, Stairs, Stages, Obstacles, and Unstructured Terrain.
Our robot utilizes the volumetric memory of the surrounding 3D structure to
successfully traverse complex environments.

##  1 Introduction

Figure 2: Overview of Simulated Environment & Real World Environment: Our
simulated environments are shown on the left and real-world environments are
shown on the right. For the real-world environment, the corresponding visual
observations for each real-world environment are shown in the bottom row. All
policies are trained in the simulation and transferred into the real world
without fine-tuning.

Consider difficult locomotion tasks such as walking up and down a flight of
stairs and stepping over gaps (Figure 1). The control of such behaviors
requires tight coupling with perception because vision is needed to provide
details of the terrain right beneath the robot and the 3D scene immediately
around it. This problem is also partially-observable. Immediately relevant
terrain information is often occluded from the robot’s current frame of
observation, forcing it to rely on past observations for control decisions.
For this reason, while blind controllers that are learned in simulation using
reinforcement learning have achieved impressive results in agility and
robustness [36, 33, 38], there are clear limitations on how much they can do.
How to incorporate perception into the pipeline to produce an integrated
visuomotor controller thus remains an open problem.

A recent line of work combines perception with locomotion using ego-centric
cameras mounted on the robot. The predominant approach for addressing partial
observability is to do frame-stacking, where the robot maintains a visual
buffer of recent images. This naïve heuristic suffers from two major problems:
first, frame-stacking on a moving robot ignores the equivariance structure of
the 3D environment, making learning a lot more difficult as policy success now
relies on being able to learn to account for spurious changes in camera poses.
A second but subtler issue is that biological systems do not have the ability
to save detailed visual observations pixel-by-pixel. These concerns motivate
the creation of an intermediary, short-term memory mechanism to functionally
aggregate streams of observation into a single, coherent representation of the
world.

Motivated by these observations, we introduce a novel volumetric memory
architecture for legged locomotion control. Our architecture consists of a 2D
to 3D feature volume encoder, and a pose estimator that can estimate the
relative camera poses given two input images. When combined, the two networks
constitute a Neural Volumetric Memory (NVM) that takes as input a sequence of
depth images taken by a forward-looking, ego-centric camera and fuses them
together into a coherent latent representation for locomotion control. We
encourage the memory space to be $SE(3)$ equivariant to changes in the camera
pose of the robot by incorporating translation and rotation operations based
on estimated relative poses from the pose network. This inverse transformation
allows NVM to align feature volumes from the past to the present ego-centric
frame, making both integrating over multiple timesteps into a coherent scene
representation and learning a policy, less difficult.

Our training pipeline follows a two-step teacher-student process where the
primary goal of the first stage is to produce behaviors in the form of a
policy. After training completes, this policy can traverse these difficult
terrains robustly, but it relies on privileged sensory information such as an
elevation map and ground-truth velocity. Elevation maps obtained in the real
world are often biased, incomplete, and full of errors [40], whereas ground-
truth velocity information is typically only available in instrumented
environments. Hence in the visuomotor distillation stage of the pipeline,
which still runs in the simulator, we feed the stream of ego-centric views
from the forward depth camera into the neural volumetric memory. We feed the
content of this memory into a small policy network and train everything end-
to-end including the two network components of the NVM using a behavior
cloning loss where the state-only policy acts as the teacher. For
completeness, we offer an additional self-supervised learning objective
(Figure 4) that relies on novel-view consistency for learning. The end product
of this visuomotor distillation pipeline is a memory-equipped visuomotor
policy that can operate directly on the UniTree A1 robot hardware (see Figure
1). A single policy is used to handle all environments covered by this paper.
We provide comprehensive experiment and ablation studies in both simulation
and the real world, and show that our method outperforms all baselines by a
large margin. It is thus essential to model the 3D structure of the
environment.

##  2 Related Work

Figure 3: Neural Volumetric Memory (_NVM_): Our NVM module extracts 3D feature
volumes from every visual observation in the near past, transform them with
corresponding estimated transformation into present robot frame, and fuse the
transformed feature volumes into a neural volumetric memory for decision-
making.

#### Blind Locomotion Controllers:

Legged locomotion using the proprioception of the robot has been studied for
decades [16, 68, 61, 42, 3, 51]. Traditionally, controllers are developed with
model-based methods [5, 15, 9, 10, 2, 17, 59, 4]. However, most model-based
methods fail to generalize to unseen environments in the real world. In order
to attain better generalization and robustness, recent works [32, 60, 22, 36,
24, 25, 65, 33, 48] utilize model-free reinforcement learning to train neural
network controllers in simulation and directly transfer the learned policies
to the real robot. These methods are able to achieve high levels of agility
and adapt over diverse terrains using just the proprioceptive state of the
robot. The real-world utility of these robots, however, is also limited, since
these blind controllers are unable to perceive the surrounding. In this paper,
we propose to integrate perception to facilitate control, with a focus on a
better 3D understanding of the environments.

#### Locomotion with Exteroceptive Perception:

The elevation map [13, 34, 46, 12] around the robot has been used to perform
optimization and planning for foot placement [11, 71, 63, 8, 66, 47]. Recent
RL controller [40, 53] also uses elevation maps in an end-to-end manner. Using
the elevation map to represent the surrounding is straightforward for foot
placement optimization, but the elevation map obtained in the real world is
either noisy or requires a complicated hardware pipeline. Another option is
using depth or RGB images to provide visual observation for the controller.
Hierarchical control systems [26, 39, 55, 58, 69] are proposed to utilize
depth reading while the low-level controllers still rely on only the
proprioceptive state of the robot. To get the most out of the depth image,
Yang et al. [67] and Imai et al. [23] propose to learn visual RL policy to
output the raw joint angles and enable the robot to maneuver in the wild
avoiding different kinds of obstacles. Agarwal et al. [1] and Loquercioo et
al. [37] train a policy using RL to traverse a large variety of terrains.
Though these works show encouraging results in specific tasks, they have not
fully exploited the 3D structure of the environment. On the other hand, we
propose to train a novel neural volumetric memory together with policy
learning, which allows our robot to walk through more challenging terrains.

#### Volumetric Cognitive Map:

How to represent and understand the 3D scene has been studied by the computer
vision community for a long time. Hartley et al. [20] and Wiles et al. [64]
provide representation built on geometry principles and camera motions.
Learning-based approaches are proposed [28, 70, 62, 29, 64, 21, 52, 35] to
learn 3D representation from 2D inputs. Neural 3D representations [14, 19, 56,
45, 44, 41, 57] has also shown great result in multiple computer vision tasks
[14, 18, 19]. Our work is closely related to Lai et al. [35] where the deep
voxel feature representing the entire scene and the camera trajectory are
learned from video clips without odometry in a self-supervised manner. Instead
of focusing on view synthesis, we aggregate the 3D feature volume to form a
short-term memory representation for decision-making.

#### Teacher-Student Training:

To accelerate training and utilize the privileged information in simulation,
Miki et al. [40] follow a teacher-student training framework, where the
teacher policy is trained with privileged information and then distilled into
student policy where the privileged information is not available. Multiple
works in different research domains [6, 27, 30, 31, 7, 43, 50] follow this
framework as well. We share a similar pipeline as [1, 39] where elevation-map-
based policies are trained first and the elevation-map-based policies are
distilled visual policies afterward.

##  3 Volumetric Memory for Legged Locomotion

Legged locomotion using ego-centric camera views is intrinsically a partially-
observed problem. To make the control problem tangible, our robot needs to
aggregate information from previous frames and correctly infer the occluded
terrain underneath it. During locomotion, the camera mounted directly on the
robot chassis undergo large and spurious changes in pose, making integrating
individual frames to a coherent representation non-trivial.

To account for these camera pose changes, we propose neural volumetric memory
(NVM) — a 3D representation format for scene features. It takes as input a
sequence of visual observations and outputs a single 3D feature volume
representing the surrounding 3D structure.

###  3.1 Baking-in $\boldsymbol{SE(3)}$ Equivariance in NVM

Our training procedure encourages the learned memory space to be $SE(3)$
equivariant by applying translation and rotation transformations on the
feature volume before aggregating additional information from new
observations.

As the first step (Figure 3), an encoder network receives a sequence of
consecutive observations $O_{t}..O_{t-n+1}$. Instead of generating a compact
feature embedding in the shape of a tuple, the 3D encoder $Enc_{3D}$ extracts
feature volumes ${V}_{t}..{V}_{t-n+1}$. A second network $Enc_{\textrm{pose}}$
estimates the relative changes in camera pose between the present frame
${O}^{v}_{t}$ and frames ${O}^{v}_{t}..{O}^{v}_{t-n+1}$ from the past. This
sequence of estimate allows NVM to transform the feature volume
${V}_{t}..{V}_{t-n+1}$ from the past to the present frame using the
transformations ${T}^{t}_{t}..{T}^{t}_{t-n+1}$. We annotate the transformed
feature volume as $\hat{V}_{t}..\hat{V}_{t-n+1}$. These canonicalized volumes
can now be aggregated together by element-wise sum to produce a fused feature
volume $\hat{V}^{m}_{t}$ for the surrounding 3D structure. This scheme allows
NVM to disentangle the symmetry structure of the ambient 3D space from the
“content” specific to the scene. By doing so, we encourage $SE(3)$
equivariance in the memory space.

We provide a detailed description of all components in our NVM module in the
remaining section.

3D Encoder: Our 3D encoder $Enc_{3D}$ takes a 2D depth image as input and
outputs a 3D feature volume. We parameterize this encoder with a set of 2D
convolution layers followed by 3D convolution layers. Specifically, we
generate a 2D feature map with the shape $(C,H,W)$ using 2D convolution, then
reshape the feature map channel-wise into a volume tensor with the shape
$(C/D,D,H,W)$. We chose a voxel-grid size of $D=12,H=6,W=6$. The 3D
convolution layers are added, to further refine the 3D features.

$V_{i}=Enc_{3D}(O^{v}_{i})\ \ \ \ \ i=t..t-n+1$

Pose Encoder: Our pose encoder $Enc_{\textrm{pose}}$ takes two depth images
and estimates the transformation in the latent space between two frames.
Specifically, our pose encoder outputs 6D vectors representing the camera pose
(rotation and translation) and we parameterize the pose encoder with a set of
2D convs. When constructing the _NVM_ , the pose encoder is used to estimate
the transformation $T^{t}_{t}..T^{t}_{t-n+1}$ between previous frames and the
present frame by comparing previous visual observation
$O^{v}_{t}..O^{v}_{t-n+1}$ and present $O^{v}_{t}$.

$T_{i}^{j}=Enc_{\textrm{pose}}(O^{v}_{i},O^{v}_{j})\in SE(3)$

Fusing 3D feature: Given feature volumes from different frames and the
estimated transformation from different frames to the present frame. We
transform the feature volume $V_{t}..V_{t-n+1}$ with the corresponding
transformation $T^{t}_{t}..T^{t}_{t-n+1}$. Particularly, for each position
$p=(i,j,k)^{T}$ in 3D deep voxel, we transform it to
$\hat{p}=(\hat{i},\hat{j},\hat{k})^{T}$ with:

$\hat{p}=Rp+t$

where $R$ is a 3x3 rotation matrix from $T^{t}_{t}..T^{t}_{t-n+1}$ and $t$ is
the translation vector from $T^{t}_{t}..T^{t}_{t-n+1}$, and we note the
transformation function as $f$.

$\hat{V}_{i}=f(V_{i},T^{t}_{i})\ \ \ \ i=t..t-n+1$

Since directly performing transformation in latent space might cause
misalignment due to the coarse of voxel representation, we use two additional
3D conv layers to refine the transformed feature volume. We then aggregate
transformed feature volumes to get Neural Volumetric Memory $\hat{V}^{m}_{t}$
representing the surrounding 3D structure in the present frame by computing
the mean over feature volumes:

$\hat{V}^{m}_{t}=\frac{1}{n}\sum_{i=t-n+1}^{t}\hat{V}_{i}$

###  3.2 Learning NVM via Self-Supervision

Figure 4: Self-Supervised Learning: we train a separate decoder to predict the
visual observation in the different frames given one visual observation and
the estimated transformation between two frames, similar to Lai et al.[35].

Although the behavior cloning objective is sufficient in producing a good
policy, being equivariant to translation and rotation automatically offers a
standalone, self-supervised learning objective just for the neural volumetric
memory. Shown in Figure 4, one can assume that the surrounding 3D scene
remains static between frames. Because the camera is forward-looking, we can
canonicalized feature volume from earlier frames, and use it to predict a
camera image taken at later steps. This self-consistency loss, computed as the
pixel reconstruction error, encourages the memory to be $SE(3)$ equivariant.

For given visual observation history over a short span of time
$O^{v}_{t}..O^{v}_{t-n+1}$, we use the most dated visual observation
$O^{v}_{t-n+1}$ in the visual history and predict all frames. We extract a 3D
feature volume from $O^{v}_{t-n+1}$: $V_{t-n+1}=Enc_{3D}(O^{v}_{t-n+1})$,
estimate the relative camera pose $T^{t-n+1}_{t}..T^{t-n+1}_{t-n+1}$ between
$O^{v}_{t}..O^{v}_{t-n+1}$ and the most dated $O^{v}_{t-n+1}$. We transform
the extracted 3D feature volume $V_{t-n+1}$ into different frames with the
corresponding transformations and then use a decoder $Dec$ to predict the
visual observation $\hat{O}^{v}_{t..t-n+1}$ rendered in different frames. The
Decoder $Dec$ takes a deep 3D feature volume as input and outputs a 2D image.
The decoder first reshapes the deep 3D feature volume with shape $(C,D,H,W)$
into shape $(C*D,H,W)$ and applies a set of 2D conv layers to map the reshaped
features to images. Given the predicted visual observation
$\hat{O}^{v}_{t..t-n+1}$ and the original visual observation
$O^{v}_{t}..O^{v}_{t-n+1}$ in different frames, we compute the prediction loss
with pixel-wise L1 loss. The 3D feature encoder and the pose encoder are both
trained in this predictive self-supervised training task. Specifically, we can
formulate this 3D representation learning task as follows:

$\displaystyle V_{t-n+1}$ $\displaystyle=Enc_{3D}(O^{v}_{t-n+1})$
$\displaystyle\hat{O}^{v}_{i}$ $\displaystyle=Dec(f(V_{t-n+1},T_{i}^{t-n+1}))\
\ i=t..t-n+1$ $\displaystyle L_{rec}$
$\displaystyle=\frac{1}{n}\sum_{i=t}^{t-n+1}|O^{v}_{i}-\hat{O}^{v}_{i}|$

where $L_{rec}$ represents the L1 loss. Since the information contained in
different visual observations is naturally different, perfect prediction in
our task is not feasible. However, such a predictive learning task could still
improve the 3D structural understanding of the surrounding and encourages the
SE(3) equivariance over the learned 3D latent space, for this reconstruction
loss encourages the disentanglement between the surrounding 3D structure and
the camera pose.

###  3.3 Teacher Policy and Visuomotor Distillation

Image observations introduce additional overhead and slow training down as
much as $40$ times111We are able to achieve 40k fps using just elevation map.
Using $64\times 64$ images, it slows down to 1k fps.. For this reason, we
bootstrap learning the visuomotor policy by first training a state-space
policy that depends on the elevation map.

#### Learning a state-only policy

We use proximal policy optimization (PPO [54]) to train a single teacher
policy $\hat{\pi}$ in all four environments. We parameterize the teacher
policy as a 4-layer ReLU network with $[256,128,128,64]$ latent neurons. To
provide terrain information, we include two elevation maps, one larger and
coarser than the other. Overall, the observation space for the teacher policy
include:

  * •

proprioceptive state - $\mathbb{R}^{63}$ A $63$-dimension vector consists of
the gravity vector in the body frame $\textbf{g}_{t}$, joint rotations
$\textbf{q}_{t}$, joint velocity $\dot{\textbf{q}}_{t}$, and previous actions
$\textbf{a}_{t-1}$.

  * •

privileged information - $\mathbb{R}^{14}$ A $14$-dimension vector including
linear velocity $\textbf{v}_{t}$ and angular velocity
$\boldsymbol{\omega}_{t}$ of the robot, and environment parameters
$\textbf{e}_{t}$.

  * •

a dense elevation map $m_{dense}$ \- $\mathbb{R}^{21\times 26}$ with $5$
spacing between the grid points, which is only slightly bigger than the robot.

  * •

a sparse elevation map $m_{sparse}$ \- $\mathbb{R}^{10\times 19}$ with $10$
spacing. This covers a much larger area.

We provide a more detailed description of the observation in the appendix.

#### Reward function

: We use the same reward function for teacher’s training in all environments.
The reward contains the following terms: 1) Reward for moving forward at a
target velocity (in our experiment: 0.4m/s). 2) an energy penalty to encourage
the robot to use as little torque as possible. 3) Height tracking reward
encouraging the robot to walk while maintaining a specific relative height to
the ground (in our experiment: 0.265m). 4) AMP reward [49] encouraging the
agent to produce natural gaits.

$\displaystyle R=$
$\displaystyle\;\alpha_{\text{forward}}*R_{\text{forward}}+\alpha_{\text{energy}}*R_{\text{energy}}$
$\displaystyle+\;\alpha_{\text{height}}*R_{\text{height}}+\alpha_{\text{amp}}*R_{\text{amp}}$

We include the details of each reward term and the corresponding weights in
the appendix.

#### Visuomotor distillation:

Given the privileged teacher policy from stage one, we then distill the
privileged teacher policy $\hat{\pi}$ into the visual policy $\pi$ without
privileged information. Our visual policy utilizes proprioceptive state and
visual observation for decision-making. The proprioceptive state $O_{prop}$ is
the same as we used to train privileged elevation-based policy in stage one
while the visual observation contains a sequence of depth images
($O^{v}_{t}..O^{v}_{t-n+1}$, n=5 in our experiment) with a shape 64 × 64 from
a depth camera mounted on the head of the robot. The observation space
comparison between the privileged teacher policy and the visual policy is
provided in Table 1, and the specific position of the camera is provided in
Figure 2.

Table 1: Comparison between observation spaces. State-only policy (w/ elevation-map) vs. vision policy |  Joint states |  Velocity |  Elevation map |  Depth map
---|---|---|---|---
Teacher policy | ✓ | ✓ | ✓ | ✗
Visual policy | ✓ | ✗ | ✗ | ✓

As shown in Figure 3, our visual policy first processes the sequential visual
observation with our proposed NVM module. After obtaining NVM with shape
$(C,D,H,W)$, our visual policy flattens the NVM into a 2D feature map with
shape $(C\times D,H,W)$ and utilizes a set of 2D conv layers and a single
linear layer to get a 1D visual feature. Our visual policy encodes the
proprioceptive state with a neural network and gets the proprioceptive
feature. The proprioceptive feature and visual feature are then concatenated
and fed into a final network to get the actual action for the robot.

The visual policy is trained with behavior cloning by minimizing the L1
distance between actions from teacher policy $\hat{\pi}$ and visual policy
$\pi$,

$L_{BC}=|\hat{\pi}(p)-\pi(o)|$

where $\mathbf{p}$ is the privileged observation (including elevation maps),
and $\mathbf{o}$ is the observation (including visual observations). Combined
with our proposed self-supervised task, the overall training loss for our NVM
is given by:

$L=\lambda_{BC}L_{BC}+\lambda_{rec}L_{rec}$

In our experiment, we use $\lambda_{BC}=1$ and $\lambda_{rec}=0.01$.

##  4 Experiments

Table 2: Evaluation of All Policies: We evaluate all methods in all four
environments and show their Traversing Rate and Success Rate. The privileged
elevation-map-based policy is noted as Teacher, and its performance is
regarded as the upper bound for the rest methods.

| Traversing Rate (%) $\uparrow$ | Success Rate (%) $\uparrow$
---|---|---
Scenarios | Stages | Stairs | Stones | Obstacles | Stages | Stairs | Stones | Obstacles
Teacher | $\mathbf{97.9\scriptstyle{\pm 2.0}}$ | $\mathbf{94.5\scriptstyle{\pm 1.8}}$ | $\mathbf{89.6\scriptstyle{\pm 3.1}}$ | $\mathbf{92.8\scriptstyle{\pm 1.8}}$ | $\mathbf{95.6\scriptstyle{\pm 2.3}}$ | $\mathbf{86.6\scriptstyle{\pm 2.7}}$ | $\mathbf{70.6\scriptstyle{\pm 5.2}}$ | $\mathbf{87.8\scriptstyle{\pm 2.7}}$
NaiveCNN | $76.4\scriptstyle{\pm 26.9}$ | $81.5\scriptstyle{\pm 28.6}$ | $29.4\scriptstyle{\pm 10.6}$ | $63.3\scriptstyle{\pm 22.5}$ | $53.9\scriptstyle{\pm 19.7}$ | $71.3\scriptstyle{\pm 25.4}$ | $0.5\scriptstyle{\pm 0.8}$ | $45.2\scriptstyle{\pm 16.4}$
NaiveCNN-MS | $72.1\scriptstyle{\pm 25.4}$ | $84.5\scriptstyle{\pm 29.7}$ | $26.4\scriptstyle{\pm 9.3}$ | $63.7\scriptstyle{\pm 22.7}$ | $48.9\scriptstyle{\pm 18.9}$ | $73.1\scriptstyle{\pm 26.2}$ | $0.0\scriptstyle{\pm 0.0}$ | $48.1\scriptstyle{\pm 18.3}$
NaiveCNN-RNN | $68.3\scriptstyle{\pm 24.1}$ | $82.4\scriptstyle{\pm 29.7}$ | $26.3\scriptstyle{\pm 9.3}$ | $67.9\scriptstyle{\pm 23.9}$ | $48.9\scriptstyle{\pm 18.0}$ | $79.1\scriptstyle{\pm 28.9}$ | $2.2\scriptstyle{\pm 1.5}$ | $49.8\scriptstyle{\pm 17.9}$
LocoTransformer | $74.0\scriptstyle{\pm 26.5}$ | $85.5\scriptstyle{\pm 29.9}$ | $25.2\scriptstyle{\pm 8.9}$ | $65.2\scriptstyle{\pm 22.9}$ | $53.3\scriptstyle{\pm 19.3}$ | $75.8\scriptstyle{\pm 26.8}$ | $0.9\scriptstyle{\pm 1.1}$ | $46.7\scriptstyle{\pm 16.9}$
NVM | $\mathbf{79.9\scriptstyle{\pm 28.1}}$ | $\mathbf{85.5\scriptstyle{\pm 30.0}}$ | $\mathbf{47.4\scriptstyle{\pm 16.7}}$ | $\mathbf{74.1\scriptstyle{\pm 26.0}}$ | $\mathbf{65.0\scriptstyle{\pm 23.2}}$ | $\mathbf{79.8\scriptstyle{\pm 28.2}}$ | $\mathbf{14.4\scriptstyle{\pm 6.0}}$ | $\mathbf{61.6\scriptstyle{\pm 21.9}}$

###  4.1 Simulation Environments

We evaluate NVM on four challenging terrains shown in Figure 2. Our intention
is to evaluate the global and local perception ability of agents, as well as
the robustness of the learned locomotion skills. Our environments consist of
Stages including multiple separate stages with gaps of different sizes between
stages; Obstacles including multiple tall cuboids for the agent to avoid;
Stairs including stairs with different heights and widths; Stones including
numerous small stones of different shapes for the agent to step over. Stages,
Stairs, and Stones environments evaluate the agent’s ability to reason about
the nearby surrounding and perform precise foot placement. Obstacle
environment requires the agent to be able to perform long-term planning and
avoid obstacles beforehand.

###  4.2 Baselines

We compare our method against baselines that do not contain SE(3) equivariance
priors:

  * •

NaiveCNN which learns visual features with a 2D CNN encoder followed by a
linear projection. Visual features and proprioceptive features are
concatenated. The action is then computed from the concatenated feature.

  * •

NaiveCNN-RNN which shares a similar structure with _NaiveCNN_ , but before
computing action from the concatenated feature, _NaiveCNN-RNN_ baseline
utilizes a 2-layer GRU to provide memory mechanism for the agent

  * •

LocoTransformer which utilizes a shared transformer model to perform cross-
modal reasoning between visual tokens from 2D visual feature map and
proprioceptive features, instead of directly concatenating visual feature and
proprioceptive feature.

  * •

Multi-Step NaiveCNN (NaiveCNN-MS) which use a 2D CNN to extract visual feature
from each depth image and fuse them together to get the overall visual
feature, instead of stacking multiple depth images and processing the stacked
visual observation with a 2D CNN.

For _NaiveCNN_ and _LocoTransformer_ , the visual observations in the near
past are stacked in the channel dimension and serve as input for 2D encoder.
All these baselines and our method share the same 2D CNN encoder structure for
a fair comparison.

###  4.3 Simulated Results

Table 3: Ablation study. We scale the grid resolution of the neural volumetric
memory and the horizon of the past kept in memory. By default, our NVM uses
use $D=12,H=W=6,n=5$.

| Traversing Rate (%) $\uparrow$ | Success Rate (%) $\uparrow$
---|---|---
Scenarios | Stages | Stairs | Stones | Obstacles | Stages | Stairs | Stones | Obstacles
NVM | $\mathbf{79.9\scriptstyle{\pm 28.1}}$ | $85.5\scriptstyle{\pm 30.0}$ | $47.4\scriptstyle{\pm 16.7}$ | $\mathbf{74.1\scriptstyle{\pm 26.0}}$ | $\mathbf{65.0\scriptstyle{\pm 23.2}}$ | $79.8\scriptstyle{\pm 28.2}$ | $14.4\scriptstyle{\pm 6.0}$ | $\mathbf{61.6\scriptstyle{\pm 21.9}}$
NVM(D=3) | $65.4\scriptstyle{\pm 23.7}$ | $68.0\scriptstyle{\pm 25.3}$ | $38.6\scriptstyle{\pm 14.5}$ | $46.5\scriptstyle{\pm 17.0}$ | $52.8\scriptstyle{\pm 19.4}$ | $52.2\scriptstyle{\pm 19.7}$ | $5.9\scriptstyle{\pm 4.1}$ | $36.1\scriptstyle{\pm 13.5}$
NVM(D=6) | $79.3\scriptstyle{\pm 27.8}$ | $83.1\scriptstyle{\pm 29.2}$ | $\mathbf{49.8\scriptstyle{\pm 17.6}}$ | $66.2\scriptstyle{\pm 23.6}$ | $64.2\scriptstyle{\pm 23.0}$ | $74.7\scriptstyle{\pm 26.4}$ | $\mathbf{14.7\scriptstyle{\pm 6.2}}$ | $50.2\scriptstyle{\pm 19.3}$
NVM(D=4x4) | $72.8\scriptstyle{\pm 26.5}$ | $70.1\scriptstyle{\pm 25.9}$ | $39.1\scriptstyle{\pm 14.4}$ | $66.4\scriptstyle{\pm 24.0}$ | $54.8\scriptstyle{\pm 21.4}$ | $62.8\scriptstyle{\pm 23.7}$ | $11.3\scriptstyle{\pm 6.0}$ | $48.6\scriptstyle{\pm 18.4}$
NVM(D=8x8) | $78.9\scriptstyle{\pm 27.8}$ | $73.4\scriptstyle{\pm 26.3}$ | $41.8\scriptstyle{\pm 15.0}$ | $64.5\scriptstyle{\pm 22.9}$ | $61.4\scriptstyle{\pm 22.3}$ | $64.8\scriptstyle{\pm 23.9}$ | $12.2\scriptstyle{\pm 4.8}$ | $50.0\scriptstyle{\pm 18.3}$
NVM(n=3) | $70.1\scriptstyle{\pm 24.8}$ | $76.6\scriptstyle{\pm 26.9}$ | $37.6\scriptstyle{\pm 13.3}$ | $64.3\scriptstyle{\pm 23.0}$ | $43.9\scriptstyle{\pm 16.8}$ | $67.0\scriptstyle{\pm 23.9}$ | $0.6\scriptstyle{\pm 0.8}$ | $48.9\scriptstyle{\pm 18.1}$
NVM(n=9) | $78.4\scriptstyle{\pm 27.6}$ | $\mathbf{85.9\scriptstyle{\pm 30.1}}$ | $39.8\scriptstyle{\pm 14.1}$ | $69.8\scriptstyle{\pm 24.6}$ | $61.6\scriptstyle{\pm 22.0}$ | $\mathbf{80.0\scriptstyle{\pm 28.5}}$ | $5.8\scriptstyle{\pm 3.2}$ | $56.1\scriptstyle{\pm 19.9}$

Evaluation metrics: We evaluate the final policies of all methods for 640
episodes in each simulated environment and compare the performance. We
evaluate different methods by two metrics: traversing rate(%) and success
rate(%). The traversing rate is defined by the distance the robot moves
dividing the reachable distance (the distance between the end of the
environment and starting position), and the Success Rate is defined by the
ratio of the robot reaching the end of the environment.

We evaluated all methods including the privileged teacher policy (noted as
Teacher) across all environments and the results are provided in Table 2.
Since in stage two of our pipeline, visual policies are trained by imitation
learning (our method with self-supervised learning as well), the performance
of the privileged teacher policy can be regarded as the upper bound for the
performance of visual policies. We can see that our NVM outperforms all the
baselines in all the environments, especially the Stones environment which
requires the agent to estimate the 3D structure of the surroundings from
visual observations and provide accurate foot placement. Surprisingly, it
turns out our method traversed a longer distance in the obstacle environment,
where the understanding of 3D structure is not required since it’s possible to
avoid the obstacles with only the latest visual observation. In this case, we
conjecture that the 3D understanding of the environment helps the agent to
keep closer to the trajectory of the teacher policy would take since the
teacher could exploit the 3D structure of the surroundings to find the optimal
path.

We find that though _NaiveCNN-MS_ introduces the mechanism of processing each
frame of visual observation separately, there is no improvement compared with
_NaiveCNN_. This comparison indicates that the improvement brought by our NVM
is actually from explicitly modeling the 3D transformation instead of
introducing more computation. Compared with _NaiveCNN_ , the memory-enabled
_NaiveCNN-RNN_ also shows no improvement, which indicates that the memory
mechanism provided by RNN is not better than, if not worse, naively stacking
the visual observations in the near past.

###  4.4 Real World Results

To validate the performance of our method beyond simulation, we constructed
multiple real-world experiment scenes as shown on the right of Figure 2. We
evaluated our method in three scenes: Stages: we build $4$ discrete stages
with $15~{}$ / $20~{}$ / $30~{}$ between stages. Stairs: We build a stair
consisting of $3$ ladders with heights of $3~{}$ / $6~{}$ / $10~{}$.
Obstacles: We place multiple cuboid obstacles in the narrow hallway for the
robot to avoid. We deploy the policies in real-world scenes and record the
distance robot moved for each episode. We terminate the episode after a
certain amount of time or until the robot reaches the end of the environment
or the robot falls. We repeat the experiment for each method and environment
five times. Real-world trajectories are also provided in Figure 1. Since
_NaiveCNN_ , _NaiveCNN-RNN_ , _LocoTransformer_ show similar performance in
simulation and _LocoTransformer_ is known to be more robust in unseen
scenarios and objects in the real world, we compared our NVM with
_LocoTransformer_ in these three scenarios. The quantitative results are shown
in Table 4. We find that our NVM moved significantly further in _Stages_ and
_Stairs_ while slightly further in _Obstacles_. This is because _Stages_ and
_Stairs_ environment require the robot to understand the surrounding 3D
structure to place the foot while _Obstacles_ only requires the ability to
perform high-level planning with visual observation. We observe that in
_Stages_ and _Stairs_ environment, agents trained with _LocoTransformer_ can
place the front leg across the stage or over the ladder, but not the rear legs
when the gap between stages is large or the ladder is tall, which demonstrates
that lack of understanding of the surrounding 3D structure. We also found that
even though _LocoTransformer_ agent could move a reasonable distance in
simulation in _Stairs_ and _Stages_ environment, it fails in the real world.
The real-world results indicate that the understanding of the surrounding 3D
structures is essential for legged robots to traverse complex terrains in the
real world and our NVM module provides a high-quality volumetric memory of the
surrounding 3D structure.

Table 4: Evaluating the visual policy in the real world Distance Moved ()
$\uparrow$
---
Scenarios | Stages | Stairs | Obstacles
NVM | $\mathbf{5.4\scriptstyle{\pm 0.3}}$ | $\mathbf{4.0\scriptstyle{\pm 0.0}}$ | $\mathbf{7.3\scriptstyle{\pm 0.1}}$
LocoTransformer | $3.4\scriptstyle{\pm 0.1}$ | $2.1\scriptstyle{\pm 0.8}$ | $6.7\scriptstyle{\pm 0.4}$

(a) Stages

(b) Obstacles

(c) Stairs

(d) Stones

Figure 5:  Visual reconstruction from learned decoder. We visualize the
synthesized visual observation in our self-supervised task. For every tuple,
the first image shows the robot moving in the environment, the second image is
the input visual observation $O^{v}_{t-n+1}$, the third image is the
synthesized visual observation using 3D feature volume $V_{t-n+1}$ extracted
from $O^{v}_{t-n+1}$ and the estimated relative camera between $O^{v}_{t-n+1}$
and robot’s ego-centric frame, and the fourth image is the actual visual
observation captured by the robot (the ground-truth in our self-supervised
task). For the input visual observation, we apply extensive data augmentation
to the image to improve the robustness of our model.

###  4.5 Visualization of SSL task

Aiming to gather insight into our learned 3D features volume, we visualized
the synthesized visual observation $\hat{O^{v}_{t}}$ in our self-supervised
learning task along with the present visual observation $O^{v}_{t}$ (the
ground truth in our SSL task), and most dated visual observation
$O^{v}_{t-n+1}$ (the input in our SSL task) in Figure 5. Even though we apply
extensive data augmentation over the raw visual observation (the second image
for every case), the synthesized visual observations are clearly indicating
the robustness of our model. In the synthesized visual observation for _Stair_
and _Obstacle_ environment, we can see the overall structure of the
environment is well-preserved. In Figure 5(b), The obstacles in the previous
frame are transformed to the position in the current frame without much
distortion. In Figure 5(c), the boundary of the nearest ladder is clear, and
the second nearest ladder is also observable in the present frame. We have to
note that the reason the decoder can not recover the details away from the
robot is in the input for SSL the large values are clipped. For more complex
_Stages_ and _Stones_ environments, we found that even though the terrain
details are not perfectly reconstructed, the essential regions for decision-
making are reconstructed which means the learned 3D voxel features capture the
most important parts in the visual observations. In Figure 5(a), we can see
the gaps between stages nearby are well reconstructed and in Figure 5(d), we
can see the reconstructed stone in front of the robot.

###  4.6 Ablation Study

we perform multiple sets of ablation studies, and the results are shown in
Table 3, with the purpose of studying the influence of different components in
our method.

The Resolution of NVM: We provide our NVM module voxel features with different
resolutions by slightly changing the structure of the 2D encoder, which
resulting 2D feature maps in different shapes and use different depth
parameter $D$. From Table 3, we find that the larger depth value $D$ generally
provides better performance, since larger $D$ converts the 2D feature map into
more fine-grained voxel feature which results in fine-grained neural
volumetric memory, and it’s supposed to be easier for the agent to reason
about the foot placement over complex terrain with more fine-grained neural
volumetric memory. For $H$ and $W$, we found that $6x6$ which provides enough
detail horizontally without introducing much noise vertically works best.

The Length of Visual History of NVM: We provide our NVM model with different
lengths of visual history by changing the number of stored visual observation
frames. As shown in Table 3, the performance of _NVM_ improves when the length
of visual history increases to 5 from 3, we think this is because the longer
visual history provides longer 3D memory of the surrounding for the agent to
safely placing the rear feet. But when the length of visual history increases
to 9 from 5, the performance drops, we hypothesize that it is because when the
visual history becomes too long, it’s hard for the pose encoder to estimate
the accurate transformation between the oldest frame and the current frame,
and the surplus visual information might be redundant for decision-making over
terrains.

##  5 Conclusion

We propose a short-term memory mechanism, the Neural Volumetric Memory (NVM),
to enable legged robots to traverse complex terrains with ease. NVM aggregates
knowledge from sequential visual observation in the near past by explicitly
modeling the translation and rotation between previous frames and the present
frame. The explicit modeling of the transformation and self-supervised task
also encourage the $SE(3)$ equivariance in the memory space. Our neural
volumetric memory module enables the legged robot to traverse complex terrain
in simulation and the real world and achieve better sim-to-real generalization
results. This shows our neural volumetric memory provides reliable surrounding
3D structure information for the robot to perform decision-making and new
possibility of utilizing visual observation for legged-robot.

Acknowledgements. This project was supported, in part, by NSF CCF-2112665
(TILOS), NSF CAREER Award IIS-2240014, NSF 1730158 CI-New: Cognitive Hardware
and Software Ecosystem Community Infrastructure (CHASE-CI), NSF ACI-1541349
CC*DNI Pacific Research Platform, Amazon Research Award and gifts from
Qualcomm. Ge Yang is supported by the National Science Foundation Institute
for Artificial Intelligence and Fundamental Interactions (IAIFI,
https://iaifi.org/) under the Cooperative Agreement PHY-2019786. We thank
Yuxiang Yang for providing help regarding hardware setup.

## References

  * [1] Ananye Agarwal, Ashish Kumar, Jitendra Malik, and Deepak Pathak.  Legged locomotion in challenging terrains using egocentric vision.  In 6th Annual Conference on Robot Learning, 2022.
  * [2] Gerardo Bledt and Sangbae Kim.  Extracting legged locomotion heuristics with regularized predictive control.  In 2020 IEEE International Conference on Robotics and Automation (ICRA), pages 406–412. IEEE, 2020.
  * [3] Gerardo Bledt, Matthew J Powell, Benjamin Katz, Jared Di Carlo, Patrick M Wensing, and Sangbae Kim.  Mit cheetah 3: Design and control of a robust, dynamic quadruped robot.  In 2018 IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS), pages 2245–2252. IEEE, 2018.
  * [4] Jan Carius, René Ranftl, Vladlen Koltun, and Marco Hutter.  Trajectory optimization for legged robots with slipping motions.  IEEE Robotics and Automation Letters, 4(3):3013–3020, 2019.
  * [5] Jared Di Carlo, Patrick M. Wensing, Benjamin Katz, Gerardo Bledt, and Sangbae Kim.  Dynamic locomotion in the MIT cheetah 3 through convex model-predictive control.  In 2018 IEEE/RSJ International Conference on Intelligent Robots and Systems, IROS 2018, Madrid, Spain, October 1-5, 2018, pages 1–9. IEEE, 2018.
  * [6] Dian Chen, Brady Zhou, Vladlen Koltun, and Philipp Krähenbühl.  Learning by cheating.  In Conference on Robot Learning, pages 66–75. PMLR, 2020.
  * [7] Tao Chen, Jie Xu, and Pulkit Agrawal.  A system for general in-hand object re-orientation.  In Conference on Robot Learning, pages 297–307. PMLR, 2022.
  * [8] Annett Chilian and Heiko Hirschmüller.  Stereo camera based navigation of mobile robots on rough terrain.  In 2009 IEEE/RSJ International Conference on Intelligent Robots and Systems, pages 4571–4576. IEEE, 2009.
  * [9] Jared Di Carlo, Patrick M Wensing, Benjamin Katz, Gerardo Bledt, and Sangbae Kim.  Dynamic locomotion in the mit cheetah 3 through convex model-predictive control.  In 2018 IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS), pages 1–9. IEEE, 2018.
  * [10] Yanran Ding, Abhishek Pandala, and Hae-Won Park.  Real-time model predictive control for versatile dynamic motions in quadrupedal robots.  In 2019 International Conference on Robotics and Automation (ICRA), pages 8484–8490. IEEE, 2019.
  * [11] Peter Fankhauser, Marko Bjelonic, C. Dario Bellicoso, Takahiro Miki, and Marco Hutter.  Robust rough-terrain locomotion with a quadrupedal robot.  In 2018 IEEE International Conference on Robotics and Automation (ICRA), pages 5761–5768, 2018.
  * [12] Péter Fankhauser, Michael Bloesch, Christian Gehring, Marco Hutter, and Roland Siegwart.  Robot-centric elevation mapping with uncertainty estimates.  In International Conference on Climbing and Walking Robots (CLAWAR), 2014.
  * [13] Péter Fankhauser, Michael Bloesch, and Marco Hutter.  Probabilistic terrain mapping for mobile robots with uncertain localization.  IEEE Robotics and Automation Letters, 3(4):3019–3026, 2018.
  * [14] Hsiao-Yu Fish Tung, Ricson Cheng, and Katerina Fragkiadaki.  Learning spatial common sense with geometry-aware recurrent networks.  In cvpr.
  * [15] Christian Gehring, Stelian Coros, Marco Hutter, Michael Blösch, Mark A. Hoepflinger, and Roland Siegwart.  Control of dynamic gaits for a quadrupedal robot.  In 2013 IEEE International Conference on Robotics and Automation, Karlsruhe, Germany, May 6-10, 2013, pages 3287–3292. IEEE, 2013\.
  * [16] Hartmut Geyer, Andre Seyfarth, and Reinhard Blickhan.  Positive force feedback in bouncing gaits?  Proceedings of the Royal Society of London. Series B: Biological Sciences, 270(1529):2173–2183, 2003.
  * [17] Ruben Grandia, Farbod Farshidian, Alexey Dosovitskiy, René Ranftl, and Marco Hutter.  Frequency-aware model predictive control.  IEEE Robotics and Automation Letters, 4(2):1517–1524, 2019.
  * [18] Adam W Harley, Shrinidhi Kowshika Lakshmikanth, Paul Schydlo, and Katerina Fragkiadaki.  Tracking emerges by looking around static scenes, with neural 3d mapping.  In eccv, 2020.
  * [19] Adam W. Harley, Fangyu Li, Shrinidhi K. Lakshmikanth, Xian Zhou, Hsiao-Yu Fish Tung, and Katerina Fragkiadaki.  Learning from unlabelled videos using contrastive predictive neural 3d mapping.  In ICLR, 2019.
  * [20] Richard Hartley and Andrew Zisserman.  Multiple view geometry in computer vision.  Cambridge university press, 2003.
  * [21] Ronghang Hu, Nikhila Ravi, Alexander C. Berg, and Deepak Pathak.  Worldsheet: Wrapping the world in a 3d sheet for view synthesis from a single image.  In Proceedings of the IEEE International Conference on Computer Vision (ICCV), 2021.
  * [22] Jemin Hwangbo, J. Lee, A. Dosovitskiy, Dario Bellicoso, Vassilios Tsounis, V. Koltun, and M. Hutter.  Learning agile and dynamic motor skills for legged robots.  Science Robotics, 4, 2019.
  * [23] Chieko Imai, Minghao Zhang, Yuchen Zhang, Marcin Kierebinski, Ruihan Yang, Yuzhe Qin, and Xiaolong Wang.  Vision-guided quadrupedal locomotion in the wild with multi-modal delay randomization.  In 2022 IEEE/RSJ international conference on intelligent robots and systems (IROS).
  * [24] Atil Iscen, Ken Caluwaerts, Jie Tan, Tingnan Zhang, Erwin Coumans, Vikas Sindhwani, and Vincent Vanhoucke.  Policies modulating trajectory generators.  In 2nd Annual Conference on Robot Learning, CoRL 2018, Zürich, Switzerland, 29-31 October 2018, Proceedings, volume 87 of Proceedings of Machine Learning Research, pages 916–926. PMLR, 2018.
  * [25] Deepali Jain, Atil Iscen, and Ken Caluwaerts.  Hierarchical reinforcement learning for quadruped locomotion.  In 2019 IEEE/RSJ International Conference on Intelligent Robots and Systems, IROS 2019, Macau, SAR, China, November 3-8, 2019, pages 7551–7557. IEEE, 2019.
  * [26] Deepali Jain, Atil Iscen, and Ken Caluwaerts.  From pixels to legs: Hierarchical learning of quadruped locomotion.  arXiv preprint arXiv:2011.11722, 2020.
  * [27] Joel Janai, Fatma Güney, Aseem Behl, Andreas Geiger, et al.  Computer vision for autonomous vehicles: Problems, datasets and state of the art.  Foundations and Trends® in Computer Graphics and Vision, 12(1–3):1–308, 2020.
  * [28] Danilo Jimenez Rezende, SM Eslami, Shakir Mohamed, Peter Battaglia, Max Jaderberg, and Nicolas Heess.  Unsupervised learning of 3d structure from images.  Advances in neural information processing systems, 29:4996–5004, 2016.
  * [29] Angjoo Kanazawa, Shubham Tulsiani, Alexei A Efros, and Jitendra Malik.  Learning category-specific mesh reconstruction from image collections.  In ECCV, 2018.
  * [30] Elia Kaufmann, Antonio Loquercio, Rene Ranftl, Alexey Dosovitskiy, Vladlen Koltun, and Davide Scaramuzza.  Deep drone racing: Learning agile flight in dynamic environments.  In Conference on Robot Learning, pages 133–145. PMLR, 2018.
  * [31] Elia Kaufmann, Antonio Loquercio, René Ranftl, Matthias Müller, Vladlen Koltun, and Davide Scaramuzza.  Deep drone acrobatics.  arXiv preprint arXiv:2006.05768, 2020.
  * [32] Nate Kohl and Peter Stone.  Policy gradient reinforcement learning for fast quadrupedal locomotion.  In Proceedings of the 2004 IEEE International Conference on Robotics and Automation, ICRA 2004, April 26 - May 1, 2004, New Orleans, LA, USA, pages 2619–2624. IEEE, 2004.
  * [33] Ashish Kumar, Zipeng Fu, Deepak Pathak, and Jitendra Malik.  Rma: Rapid motor adaptation for legged robot.  Robotics: Science and Systems, 2021.
  * [34] In-So Kweon and Takeo Kanade.  High-resolution terrain map from multiple sensor data.  IEEE Transactions on Pattern Analysis and Machine Intelligence, 14(2):278–292, 1992.
  * [35] Zihang Lai, Sifei Liu, Alexei A Efros, and Xiaolong Wang.  Video autoencoder: self-supervised disentanglement of 3d structure and motion.  In ICCV, 2021.
  * [36] Joonho Lee, Jemin Hwangbo, Lorenz Wellhausen, Vladlen Koltun, and Marco Hutter.  Learning quadrupedal locomotion over challenging terrain.  Science robotics, 5(47), 2020.
  * [37] Antonio Loquercio, Ashish Kumar, and Jitendra Malik.  Learning visual locomotion with cross-modal supervision, 2022.
  * [38] G. Margolis, Ge Yang, Kartik Paigwar, Tao Chen, and Pulkit Agrawal.  Rapid locomotion via reinforcement learning.  ArXiv, abs/2205.02824, 2022.
  * [39] Gabriel B Margolis, Tao Chen, Kartik Paigwar, Xiang Fu, Donghyun Kim, Sang bae Kim, and Pulkit Agrawal.  Learning to jump from pixels.  In 5th Annual Conference on Robot Learning, 2021.
  * [40] Takahiro Miki, Joonho Lee, Jemin Hwangbo, Lorenz Wellhausen, Vladlen Koltun, and Marco Hutter.  Learning robust perceptive locomotion for quadrupedal robots in the wild.  Sci Robot, 7(62):eabk2822, Jan. 2022.
  * [41] Ben Mildenhall, Pratul P Srinivasan, Matthew Tancik, Jonathan T Barron, Ravi Ramamoorthi, and Ren Ng.  Nerf: Representing scenes as neural radiance fields for view synthesis.  In ECCV, 2020.
  * [42] Hirofumi Miura and Isao Shimoyama.  Dynamic walk of a biped.  The International Journal of Robotics Research, 3(2):60–74, 1984\.
  * [43] Tongzhou Mu, Zhan Ling, Fanbo Xiang, Derek Yang, Xuanlin Li, Stone Tao, Zhiao Huang, Zhiwei Jia, and Hao Su.  Maniskill: Generalizable manipulation skill benchmark with large-scale demonstrations.  arXiv preprint arXiv:2107.14483, 2021.
  * [44] Siva Karthik Mustikovela, Varun Jampani, Shalini De Mello, Sifei Liu, Umar Iqbal, Carsten Rother, and Jan Kautz.  Self-supervised viewpoint learning from image collections.  In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pages 3971–3981, 2020.
  * [45] Thu Nguyen-Phuoc, Chuan Li, Lucas Theis, Christian Richardt, and Yong-Liang Yang.  Hologan: Unsupervised learning of 3d representations from natural images.  In Proceedings of the IEEE International Conference on Computer Vision, pages 7588–7597, 2019.
  * [46] Yiyuan Pan, Xuecheng Xu, Yue Wang, Xiaqing Ding, and Rong Xiong.  Gpu accelerated real-time traversability mapping.  In 2019 IEEE International Conference on Robotics and Biomimetics (ROBIO), pages 734–740. IEEE, 2019.
  * [47] Xue Bin Peng, Glen Berseth, KangKang Yin, and Michiel Van De Panne.  Deeploco: Dynamic locomotion skills using hierarchical deep reinforcement learning.  ACM Transactions on Graphics (TOG), 36(4):1–13, 2017.
  * [48] Xue Bin Peng, Erwin Coumans, Tingnan Zhang, Tsang-Wei Edward Lee, Jie Tan, and Sergey Levine.  Learning agile robotic locomotion skills by imitating animals.  In Robotics: Science and Systems, 07 2020.
  * [49] Xue Bin Peng, Ze Ma, Pieter Abbeel, Sergey Levine, and Angjoo Kanazawa.  Amp: Adversarial motion priors for stylized physics-based character control.  ACM Trans. Graph., 40(4), July 2021.
  * [50] Lerrel Pinto, Marcin Andrychowicz, Peter Welinder, Wojciech Zaremba, and Pieter Abbeel.  Asymmetric actor critic for image-based robot learning.  arXiv preprint arXiv:1710.06542, 2017.
  * [51] Marc H Raibert.  Hopping in legged systems—modeling and simulation for the two-dimensional one-legged case.  IEEE Transactions on Systems, Man, and Cybernetics, SMC-14(3):451–463, 1984.
  * [52] Chris Rockwell, David F. Fouhey, and Justin Johnson.  Pixelsynth: Generating a 3d-consistent experience from a single image.  In ICCV, 2021.
  * [53] Nikita Rudin, David Hoeller, Philipp Reist, and Marco Hutter.  Learning to walk in minutes using massively parallel deep reinforcement learning.  In Conference on Robot Learning, pages 91–100. PMLR, 2022.
  * [54] John Schulman, Filip Wolski, Prafulla Dhariwal, Alec Radford, and Oleg Klimov.  Proximal policy optimization algorithms.  arXiv preprint arXiv:1707.06347, 2017.
  * [55] Mingyo Seo, Ryan Gupta, Yifeng Zhu, Alexy Skoutnev, Luis Sentis, and Yuke Zhu.  Learning to walk by steering: Perceptive quadrupedal locomotion in dynamic environments.  In arXiv preprint arXiv:2209.09233, 2022.
  * [56] Vincent Sitzmann, Justus Thies, Felix Heide, Matthias Nießner, Gordon Wetzstein, and Michael Zollhofer.  Deepvoxels: Learning persistent 3d feature embeddings.  In CVPR, 2019.
  * [57] Vincent Sitzmann, Michael Zollhöfer, and Gordon Wetzstein.  Scene representation networks: Continuous 3d-structure-aware neural scene representations.  In NeurIPS, 2019.
  * [58] Maks Sorokin, Jie Tan, C. Karen Liu, and Sehoon Ha.  Learning to navigate sidewalks in outdoor environments.  IEEE Robotics and Automation Letters, 7(2):3906–3913, 2022.
  * [59] Yu Sun, Wyatt L. Ubellacker, Wen-Loong Ma, Xiang Zhang, Changhao Wang, Noel V. Csomay-Shanklin, Masayoshi Tomizuka, Koushil Sreenath, and Aaron D. Ames.  Online learning of unknown dynamics for model-based controllers in legged locomotion.  IEEE Robotics and Automation Letters (RA-L), 2021.
  * [60] Jie Tan, Tingnan Zhang, Erwin Coumans, Atil Iscen, Yunfei Bai, Danijar Hafner, Steven Bohez, and Vincent Vanhoucke.  Sim-to-real: Learning agile locomotion for quadruped robots.  In Hadas Kress-Gazit, Siddhartha S. Srinivasa, Tom Howard, and Nikolay Atanasov, editors, Robotics: Science and Systems XIV, Carnegie Mellon University, Pittsburgh, Pennsylvania, USA, June 26-30, 2018, 2018.
  * [61] Nick Torkos and Michiel van de Panne.  Footprint–based quadruped motion synthesis.  In Proceedings of the Graphics Interface 1998 Conference, June 18-20, 1998, Vancouver, BC, Canada, pages 151–160, June 1998.
  * [62] Shubham Tulsiani, Tinghui Zhou, Alexei A Efros, and Jitendra Malik.  Multi-view supervision for single-view reconstruction via differentiable ray consistency.  In CVPR, 2017.
  * [63] Martin Wermelinger, Péter Fankhauser, Remo Diethelm, Philipp Krüsi, Roland Siegwart, and Marco Hutter.  Navigation planning for legged robots in challenging terrain.  In 2016 IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS), pages 1184–1189. IEEE, 2016.
  * [64] Olivia Wiles, Georgia Gkioxari, Richard Szeliski, and Justin Johnson.  Synsin: End-to-end view synthesis from a single image.  In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pages 7467–7477, 2020.
  * [65] Zhaoming Xie, Xingye Da, Buck Babich, Animesh Garg, and Michiel van de Panne.  Glide: Generalizable quadrupedal locomotion in diverse environments with a centroidal model.  CoRR, abs/2104.09771, 2021.
  * [66] Zhaoming Xie, Hung Yu Ling, Nam Hee Kim, and Michiel van de Panne.  Allsteps: curriculum-driven learning of stepping stone skills.  In Computer Graphics Forum, volume 39, pages 213–224. Wiley Online Library, 2020.
  * [67] Ruihan Yang, Minghao Zhang, Nicklas Hansen, Huazhe Xu, and Xiaolong Wang.  Learning vision-guided quadrupedal locomotion end-to-end with cross-modal transformers.  In International Conference on Learning Representations, 2022.
  * [68] KangKang Yin, Kevin Loken, and Michiel Van de Panne.  Simbicon: Simple biped locomotion control.  ACM Transactions on Graphics (TOG), 26(3):105–es, 2007.
  * [69] Wenhao Yu, Deepali Jain, Alejandro Escontrela, Atil Iscen, Peng Xu, Erwin Coumans, Sehoon Ha, Jie Tan, and Tingnan Zhang.  Visual-locomotion: Learning to walk on complex terrains with vision.  In Aleksandra Faust, David Hsu, and Gerhard Neumann, editors, Proceedings of the 5th Conference on Robot Learning, volume 164 of Proceedings of Machine Learning Research, pages 1291–1302. PMLR, 08–11 Nov 2022\.
  * [70] Tinghui Zhou, Matthew Brown, Noah Snavely, and David G Lowe.  Unsupervised learning of depth and ego-motion from video.  In CVPR, 2017.
  * [71] Matt Zucker, Nathan Ratliff, Martin Stolle, Joel Chestnutt, J Andrew Bagnell, Christopher G Atkeson, and James Kuffner.  Optimization and learning for rough terrain legged locomotion.  The International Journal of Robotics Research, 30(2):175–191, 2011\.

Appendix

##  1 Detailed Observation Space

In this section, we provide more details about different components of
observation space for both the privileged teacher policy and visual policies.
The Unitree A1 robot we used has 12 joints, corresponding to 12 Degrees of
Freedom (DoF), and we use positional control for the 12 DOF. Specifically, the
proprioceptive input contains:

  * •

Joint Rotations - $\mathbb{R}^{12\times 2}$ contains joint rotations for all
joints ($12$D) for the past two control step.

  * •

Joint Velocity - $\mathbb{R}^{12}$ contains joint velocities for all joints
($12$D).

  * •

Previous Action - $\mathbb{R}^{12\times 2}$ contains positional command for
all joints ($12$D) for the past two control step.

  * •

Projected Gravity - $\mathbb{R}^{3}$ contains the projected gravity in the
robot frame, representing the orientation of the robot.

The privileged information for privileged teacher policy training contains:

  * •

Linear Velocity - $\mathbb{R}^{3}$ contains the linear velocity of the robot
in the world frame.

  * •

Angular Velocity - $\mathbb{R}^{3}$ contains the linear velocity of the robot
in the world frame.

  * •

Environment Parameters - $\mathbb{R}^{8}$ contains randomized environment
parameters.

For visual observation, we provide $N=5$ frames of the depth image ($64\times
64$) to construct the perception history. To simulate the noisy visual
observation in the real world, for each time step, we randomly sample $1\%$
pixels in $(64,64)$ depth image and set the reading for these pixels to be the
maximum reading.

##  2 Reward for Privileged Teacher Training

For the training of privileged teacher policy in all environments we use the
same reward function as follows:

$\displaystyle R=$
$\displaystyle\;\alpha_{\text{forward}}*R_{\text{forward}}+\alpha_{\text{energy}}*R_{\text{energy}}$
$\displaystyle+\;\alpha_{\text{height}}*R_{\text{height}}+\alpha_{\text{amp}}*R_{\text{amp}}$

In our experiment, we use
$\alpha_{\text{forward}}=1,\alpha_{\text{energe}}=-0.005,\alpha_{\text{height}}=-2.0,\alpha_{\text{amp}}=1.0$

we provide specific formulations of different reward terms in our reward
function

$\displaystyle
R_{\text{forward}}=1+|v_{\text{robot}}-v_{\text{target}}|/v_{\text{target}}$

where $v_{\text{robot}}$ is the current robot speed along the forward
direction, and the $v_{\text{target}}=0.4$ is the target moving forward speed.

$\displaystyle R_{\text{energy}}=\sum_{i}|\tau_{i}\times\dot{q}_{i}|$

where $\tau_{i}$ is the the motor torques applied to the $i$th joint, and the
$\dot{q}_{i}$ is the joint velocity for the $i$th joint.

$\displaystyle R_{\text{height}}=||h_{\text{robot}}-h_{\text{target}}||$

where $h_{\text{robot}}$ is the current relative height of the robot with
respect to the terrain, and the $h_{\text{target}}=0.265$ is the target height
to track.

For AMP reward, we follow the setting in Peng et al [49], where a gait
discriminator is trained to distinguish the gait in the reference motions and
the gait produced by the RL policy. The score (between $0$ and $1$) from the
discriminator is used as the AMP reward. The gait closer to the reference
motions is assigned a higher reward.


Copyright for this paper by its authors. Use permitted under Creative Commons
License Attribution 4.0 International (CC BY 4.0).

The IJCAI-2024 AISafety Workshop

[orcid=0009-0002-5376-7881<EMAIL_ADDRESS>]

[orcid=0000-0003-0060-4771<EMAIL_ADDRESS>]

[orcid=0000-0001-6171-3811<EMAIL_ADDRESS>] [1]

[1]Corresponding author.

# Low-Latency Privacy-Preserving Deep Learning Design via Secure MPC

Ke Lin  Tsinghua University, 30 Shuangqing Rd., Haidian District, Beijing,
100084, China  Yasir Glani  Ping Luo

(2024)

###### Abstract

Secure multi-party computation (MPC) facilitates privacy-preserving
computation between multiple parties without leaking private information.
While most secure deep learning techniques utilize MPC operations to achieve
feasible privacy-preserving machine learning on downstream tasks, the overhead
of the computation and communication still hampers their practical
application. This work proposes a low-latency secret-sharing-based MPC design
that reduces unnecessary communication rounds during the execution of MPC
protocols. We also present a method for improving the computation of commonly
used nonlinear functions in deep learning by integrating multivariate
multiplication and coalescing different packets into one to maximize network
utilization. Our experimental results indicate that our method is effective in
a variety of settings, with a speedup in communication latency of $10\sim
20\%$.

###### keywords:

Multi-party computation deep learning privacy-preserving

##  1 Introduction

Secure multi-party computation (MPC) [1, 2] enables parties to compute
securely over their private data without revealing the data to each other.
Secure MPC offers privacy-preserving property, which makes it suitable for
most privacy-sensitive domains, such as medical research and finance. Upon the
development of deep learning techniques, the ability to capture important
information from large datasets of neural models raises concerns regarding the
surveillance of individuals [3]. In this case, the prospects of secure MPC
demonstrate its application to secure machine learning and deep learning.
While MPC-based deep learning frameworks have achieved significant performance
in general scenarios, most works suffer from the limitations caused by  1.
_network communication_ due to the nature of exchanging intermediate
information during MPC execution,  2. _excessive computation_ introduced by
complex MPC protocols.  Since the computation of MPC protocols is largely
determined by their sophisticated design, optimizing the protocol itself would
seem to be difficult and infeasible. Thus, some studies [4] are concerned with
improving the communication stage of MPC protocols to make them more
practical. In this paper, we present an approach to reduce the communication
latency of the MPC protocol through optimized multivariate multiplication.

In general, privacy-preserving deep learning frameworks usually adopt secret-
sharing-based techniques to avoid extensive computational overheads [5, 6, 7,
8]. Consequently, secret-sharing-based methods require multiple exchanges of
intermediate results to achieve collaborative MPC operations. As these MPC
techniques are based on linear computations, such as addition and
multiplication, modern deep learning techniques that inherently rely on linear
algebra benefit significantly from them. Considering the heavy dependency on
linear operations, our research aims to reduce unnecessary communication
rounds following [9] during the execution of MPC protocols.

Our main contributions are as follows:

  * •

We propose a low-latency secret-sharing-based method for computing
multivariate multiplications and univariate polynomials using network
communication that is efficient and reduces unnecessary communication rounds
on the fly.

  * •

We improve the computation of nonlinear functions by integrating the proposed
multivariate multiplication and coalescing different packets into one single
packet to maximize network utilization.

  * •

We conducted experiments to evaluate the effectiveness of our method in the
context of models with varying sizes, networks with different latency and
bandwidth, the accuracy of downstream classification tasks, and the number of
participants involved. The results indicate an overall improvement of $10\sim
20\%$ in communication latency.

##  2 Background

###  2.1 Arithmetic Secret Sharing Based Scheme

Our setup is primarily focused on arithmetic operations, so we represent all
inputs and intermediate results in terms of linear secret sharing between $n$
parties, especially in the context of additive secret-sharing schemes.

Apart from the general $(n,t)$-Shamir secret sharing scheme [10], which relies
on the degree-$t$ polynomials over $n$ parties, we adopt the simple arithmetic
secret sharing scheme based on $(n,0)$-Shamir secret sharing. In other words,
we share a scalar value $x\in\mathbb{Z}/Q\mathbb{Z}$ across $n$ parties
$\mathcal{P}$, where $\mathbb{Z}/Q\mathbb{Z}$ denotes a ring with $Q$
elements, following the notations of [5]. The sharing of $x$ is defined as
$[x]=\\{[x]_{p}\\}_{p\in\mathcal{P}}$, where $[x]_{p}$ is the party $p$’s
share of $x$. The ground-truth value $x$ could be reconstructed from the sum
of the shares of each party, i.e. $x=\sum_{p\in\mathcal{P}}[x]_{p}$.

When parties wish to share a value $x$, they generate a pseudorandom zero-
share that sums to 0. The party that possesses the value adds $x$ to their
share in secret. To represent floating-point numbers, we adopt a fixed-point
encoding to encode any floating-point number $x_{F}$ into a fixed-point
representation, $x$. Alternatively, we consider that each $x$ is the result of
multiplying a floating-point number $x_{F}$ by a scaling factor $B=2^{L}$ and
rounding to the nearest integer, i.e. $x=\lfloor Bx_{F}\rceil$. Here $L$ is
the precision of the fixed-point encoding. To decode a ground-truth floating-
point value $x_{F}$ from $x$, we compute as follows: $x_{F}\approx x/B$.

###  2.2 Arithmetic Secret Sharing Based MPC

It is noteworthy that arithmetic secret shares are homomorphic and can be used
to implement secure MPC, especially in the context of linear computation in
most cases.

#### Addition.

The sum of two secret shared values $[x]$ and $[y]$ could be directly computed
as $[z]=[x]+[y]$, where each party $p\in\mathcal{P}$ computes
$[z]_{p}=[x]_{p}+[y]_{p}$ without multi-party communications.

#### Multiplication.

Two secret shared values $[x]$ and $[y]$ are multiplied using a random Beaver
triple [11] generated by the Trusted Third Party (TTP): a triplet
$([a],[b],[ab])$. It should be noted that the Beaver triple could be shared in
advance by each party. The parties first calculate $[\epsilon]=[x]-[a]$ and
$[\delta]=[y]-[b]$. In this way, the $[\epsilon]$ and $[\delta]$ are then
revealed to all parties (denoted as $\operatorname{\mathbf{Reveal}}(\cdot)$)
without compromising information since the ground-truth values $a,b$ remain
unknown to each party except for the TTP. The final results could be computed
as $[xy]=[c]+\epsilon[b]+[a]\delta+\epsilon\delta$. Algorithm 1 illustrates
the multiplication using Beaver triples.

#### Linear functions.

It is possible to implement functions that consist of linear operations by
combining additions and multiplications. Common operations in deep learning,
such as element-wise product and convolution, are allowed in a linear
paradigm.

#### Nonlinear functions.

Due to the inherent infeasibility of nonlinear functions in the standard
arithmetic secret-sharing scheme, most works use approximation methods to
simulate the outcome of nonlinear functions. In particular, Taylor Expansion,
Newton-Rhapson, and Householder methods are commonly used to approximate
nonlinear functions using only linear operations. All reciprocal functions,
exponential functions, loss functions, kernel functions, and other useful
functions in deep learning are calculated this way, for example.

Algorithm 1 Beaver Multiplication $\mathbf{Mul}([x],[y])$

1:Secret-shared inputs $[x],[y]$, Beaver triple ($[a],[b],[ab]$).

2:$[xy]$.

3:$\triangleright$ Compute masked values

4:$[\epsilon]\leftarrow[x-a]=[x]-[a]$

5:$[\delta]\leftarrow[y-b]=[y]-[b]$

6:$\triangleright$ Reveal $\epsilon$ and $\delta$ through one-round
communications

7:$\epsilon\leftarrow\operatorname{\mathbf{Reveal}}([\epsilon])$

8:$\delta\leftarrow\operatorname{\mathbf{Reveal}}([\delta])$

9:return $\epsilon\delta+\epsilon[b]+[a]\delta+[ab]$

###  2.3 Notations

This section summarizes the notations used throughout this work. We denote
$[x]$ as a secret sharing of $x$. $\operatorname{\mathbf{Reveal}}([x])$ means
that the ground-truth value $x$ is revealed to every party involved in the
computation through one-round communications. Since most linear operations are
also applicable to element-wise operations and matrix operations, $x$ can also
represent a vector, matrix, or even a tensor if there is no confusion and
ambiguity.

##  3 Related Work

To achieve communication-efficient MPC, various approaches have been developed
to optimize the communication rounds and the throughput of communication.
Ishai and Kushilevitz [12] proposes a new representation of polynomials for
round-efficient secure computation, dividing high-degree polynomials into
multiple low-degree polynomials that are easy to solve. Mohassel and Franklin
[13] performs operations directly on polynomials, such as polynomial
multiplication and division. Dachman-Soled et al. [14] improves the evaluation
of multivariate polynomials with different variables being held as private
inputs by each party. Then, Lu et al. [4] proposes an efficient method for
evaluating high-degree polynomials with arbitrary numbers of variables. While
the current research has focused on improving the calculation of polynomials,
our study aims to develop a communication-efficient and effective MPC system
for use in modern deep learning frameworks by leveraging arithmetic tuples
computation from Krips et al. [9]. This system is not confined to only
computing polynomials within finite rings, as seen in previous studies.

In recent years, several deep learning frameworks that preserve privacy have
emerged to enable the secure inference of neural network models. Wagh et al.
[8] implements a maliciously secure 3-party MPC protocol from SecureNN [15]
and ABY3 [16]. Knott et al. [5] provides flexible machine-learning APIs with a
rich set of functions for secure deep learning. Li et al. [7] presents a fast
and performant MPC Transformer inference framework designed to be privacy-
preserving. Our low-latency linear MPC implementation is built on top of Knott
et al.’s CrypTen framework and provides a significant improvement in
communication latency.

##  4 Methodology

###  4.1 Multivariate Multiplication

Since Beaver triples illustrate how to multiply two variables with pre-shared
triplets, a classic multiplication between multiple variables, such as
$[xyz]$, requires several rounds of binary multiplication, i.e.
$\mathbf{Mul}(\mathbf{Mul}([x],[y]),[z])$. This naive implementation, however,
introduces additional communication rounds during the on-the-fly
$\operatorname{\mathbf{Reveal}}$ process. In general, a $n$-ary multiplication
requires $n-1$ rounds of communication.

To reduce the communication rounds involved in the multivariate
multiplications, the basic binary Beaver triple is extended into a general
$n$-ary Beaver triple. This results in only _one round_ of communication
required throughout the entire process.

Assume the $n$ inputs could be represented as $\\{[x_{i}]\\}_{i=1}^{n}$. The
precomputation and preshared information required by the extended protocol is
$\\{\mathcal{A}_{i}\\}_{i=1}^{n}$. Here
$\mathcal{A}_{1}:=\\{[a_{j}]\\}_{j=1}^{n}$ is defined as the set of $n$
auxiliary shared values used to blind the the inputs
$\\{[x_{i}]\\}_{i=1}^{n}$, which is also similar to the Beaver’s idea. Then
$\mathcal{A}_{i}(i\geq 2)$ is defined as the set of shared degree-$i$ cross-
terms consisting of the variables in $\mathcal{A}_{1}$. For example,
$\mathcal{A}_{2}$ could be defined as $\mathcal{A}_{2}:=\\{[a_{i}a_{j}]\mid\
i\neq j\wedge 1\leq i,j\leq n\\}$, and
$\mathcal{A}_{3}:=\\{[a_{i}a_{j}a_{k}]\mid\ i\neq j\neq k\wedge 1\leq
i,j,k\leq n\\}$, and so on. Similar to the construction of $[\epsilon]$ and
$[\delta]$ in Section 2.2, we define the difference between the inputs and the
masks as $[\delta_{i}]:=[x_{i}]-[a_{i}]$. The secret-shared $[\delta_{i}]$ is
then made public across all parties without leakage to the ground-truth value
of both $[x_{i}]$ and $[a_{i}]$. The improvement of our method originates from
the following equation:

$\displaystyle\prod_{i=1}^{n}x_{i}$
$\displaystyle=\prod_{i=1}^{n}(\delta_{i}+a_{i})$ (1)
$\displaystyle=\prod\delta_{i}+\sum_{i}\delta_{i}\frac{\prod
a_{m}}{a_{i}}+\sum_{i,j,i\neq j}\delta_{i}\delta_{j}\frac{\prod
a_{m}}{a_{i}a_{j}}$ $\displaystyle\quad+\dots+\prod a_{i}.$

Here we informally use the fractional representation, such as $\frac{\prod
a_{m}}{a_{i}}$, to denote the products of all the terms _except for_ certain
ones. Note that this fractional form does not involve any actual division.
Also, each secret-shared term of $[\frac{\prod a_{m}}{a_{i}\dots a_{j}}]$
could be found in the auxiliary sets $\\{\mathcal{A}_{i}\\}_{i=1}^{n}$, which
is preshared across all parties.

Adaptation of Equation 1 in secret-sharing scheme is as follows:

$\displaystyle[\prod_{i=1}^{n}x_{i}]$
$\displaystyle=\prod\delta_{i}+\sum_{i}\delta_{i}[\frac{\prod
a_{m}}{a_{i}}]+\sum_{i,j,i\neq j}\delta_{i}\delta_{j}[\frac{\prod
a_{m}}{a_{i}a_{j}}]$ (2) $\displaystyle\quad+\dots+[\prod a_{i}].$

Since Equation 2 is linear to the secret-sharing terms, all communications
could be conducted in parallel, i.e. in a single round of communications. In
this case, we could simply reveal all the secret-sharing terms in
$\\{\mathcal{A}_{i}\\}_{i=1}^{n}$ and compute the sharing of final results in
constant complexity. The protocol is formally described in Algorithm 2.

Algorithm 2 Multivariate Beaver Multiplication of $n$ inputs
$\mathbf{Mul}([x_{1}],[x_{2}],\dots,[x_{n}])$

1:Secret-shared inputs $\\{[x_{i}]\\}_{i=1}^{n}$, auxiliary sets
$\\{\mathcal{A}_{i}\\}_{i=1}^{n}$.

2:$[\prod x_{i}]$.

3:$\triangleright$ Compute masked values

4:for $i\in[1,n]$ do

5: $[\delta_{i}]\leftarrow[x_{i}-a_{i}]=[x_{i}]-[a_{i}]$

6:end for

7:$\triangleright$ Reveal $\delta_{i}$ through one-round communications

8:parallel for $i\in[1,n]$ do

9: $\delta_{i}\leftarrow\operatorname{\mathbf{Reveal}}([\delta_{i}])$

10:end parallel for

11:$\triangleright$ Compute results using preshared
$\\{\mathcal{A}_{i}\\}_{i=1}^{n}$

12:return $\prod\delta_{i}+\sum_{i}\delta_{i}[\frac{\prod
a_{m}}{a_{i}}]+\sum_{i,j,i\neq j}\delta_{i}\delta_{j}[\frac{\prod
a_{m}}{a_{i}a_{j}}]+\dots+[\prod a_{i}]$

The total rounds of communications are indeed reduced from $n-1$ to constant
$1$ when a regular $n$-ary multiplication is performed, but the overall size
of communication data increases from linear to exponential. In a naïve
implementation, the data size of $n$-ary multiplication is only $3(n-1)$ for a
total transmission of $n-1$ Beaver triples. As opposed to a multivariate
implementation, it is $2^{n}-1$ to transmit the auxiliary sets
$\\{\mathcal{A}_{i}\\}_{i=1}^{n}$. Therefore, in practice, there is a trade-
off between communication latency and throughput.

###  4.2 Univariate Polynomials

The formal form of univariate polynomials is defined as
$P(x)=\sum_{i=0}^{n}b_{i}x^{i}$, where $b_{i}$ refers to the coefficients of
the degree-$i$ term. The use of univariate polynomials enables efficient
evaluation and manipulation of polynomial expressions. According to Damgård et
al. [17], we can compute all required $[x^{i}]$ in parallel using multivariate
multiplications, then multiply them with corresponding plaintext coefficients.
Despite its benefits, this trick has the disadvantage of exponentially
increasing the size of transmitted data, which becomes unbearable when the
exponent exceeds 5.

This method can be implemented in practice by computing a tuple of base terms
and then multiplying the tuple by a certain term iteratively, as in the
exponentiating by squaring method or the fast modulo algorithm. In other
words, a tuple $\bm{g}=(1,x,\dots,x^{m-1})$ of size $\lVert\bm{g}\rVert=m$
could be multiplied by $x^{\lVert\bm{g}\rVert}$ repeatedly to iterate all the
$x^{i}$ terms. The overview of the implementation of univariate polynomials is
described in Algorithm 3. Note that $\bm{b}_{s:e}$ is the subvector of
$\bm{b}$ from position $s$ to $e$.

Algorithm 3 Univariate Polynomial $\mathbf{Poly}([x],\bm{b})$

1:Secret-shared input $[x]$, coefficients $\bm{b}=(b_{0},b_{1},\dots,b_{n})$,
base terms size $\lVert\bm{g}\rVert$.

2:$\sum_{i=0}^{n}b_{i}[x^{i}]$.

3:$\triangleright$ Construct base terms

4:parallel for $i\in[1,\lVert\bm{g}\rVert]$ do

5: $[x^{i}]\leftarrow\mathbf{Mul}([x],\dots,[x])$ $\triangleright$ multiplied
by $[x]$ of $i$ times

6:end parallel for

7:$\bm{g}\leftarrow(1,[x],\dots,[x^{\lVert\bm{g}\rVert-1}])$

8:$\triangleright$ Iteratively exponentiating

9:$t\leftarrow 0$

10:for $i\in[0,\lfloor\frac{n}{\lVert g\rVert}\rfloor-1]$ do

11: $\text{s}\leftarrow i\cdot\lVert\bm{g}\rVert$

12: $\text{e}\leftarrow(i+1)\cdot\lVert\bm{g}\rVert$

13: $t\leftarrow t+\bm{b}_{s:e}\cdot\bm{g}$

14: $\triangleright$ Vectorized Beaver Multiplication

15: $\bm{g}\leftarrow[x^{\lVert\bm{g}\rVert}]\cdot\bm{g}$

16:end for

17:return $t$

###  4.3 Nonlinear Approximations

In this section, we take one step further to optimize the commonly used
nonlinear functions by leveraging the property of parallelization of our
proposed multivariate multiplication.

#### Exponentiation.

Since exponential functions grow in geometrical speed, approximations based on
series expansion generally suffer from a significant reduction in accuracy
since we do not know the exact value of the input. Consequently, we resort to
the naive iterative approximation, which is capable of utilizing multivariate
multiplication effectively:

$e^{[x]}=\lim_{n\rightarrow\infty}\left(1+\frac{[x]}{d^{n}}\right)^{d^{n}}.$

During each iteration, the $d$-th power of the previous result is calculated.
With increasing iteration rounds $n$, the answer would become closer to the
actual results.

#### Logarithm.

The calculation of logarithms relies on the higher-order iterative methods for
a better convergence, i.e. Householder methods on $y=\ln x$:

$\displaystyle[h_{n}]$ $\displaystyle=1-[x]e^{-[y_{n}]}$
$\displaystyle[y_{n+1}]$
$\displaystyle=[y_{n}]-\sum_{k=1}^{\infty}\frac{1}{k}[h_{n}^{k}]$

Note that the implementation of logarithm is the combination of exponentiation
and univariate polynomials. The degree of the polynomials determines the
precision of the output.

#### Reciprocal.

The reciprocal function $y=\frac{1}{x}$ is calculated using the Newton-Raphson
method with an initial guess $y_{0}$:

$\displaystyle[y_{n+1}]$ $\displaystyle=[y_{n}](2-[x][y_{n}])$
$\displaystyle=2[y_{n}]-[x][y_{n}][y_{n}]$

#### Trigonometry.

Trigonometric functions could be treated as the special case of exponentiation
with $d=2$. The sine and cosine functions are calculated in the field of
complex numbers:

$\displaystyle[\sin{x}]$ $\displaystyle=\mathrm{Im}([e^{ix}])$
$\displaystyle[\cos{x}]$ $\displaystyle=\mathrm{Re}([e^{ix}])$

Using the above-mentioned nonlinear functions, we can calculate most of the
existing loss functions in deep learning, such as the sigmoid, tanh, and
cross-entropy functions. Various other common nonlinear functions, such as the
softmax function and kernel function, can also be calculated using exponential
and reciprocal functions.

###  4.4 Communication Coalescing

The key to achieving low-latency secret-sharing computation is to reduce the
total number of rounds of communications among different parties. While we
introduce a latency-friendly implementation of basic math operations, other
kinds of communications, such as precision checking, still require an
additional but _independent_ communication round.

In general, the communication involved in multiple math operations could be
abstracted as a communication graph, or strictly, as a communication tree.
Accordingly, we observe some independent communications that do not affect
downstream results can be deferred and combined into one single round of
communication. This process is referred to as _communication coalescing_ , and
it eliminates unnecessary rounds of communication and improves the utilization
of network bandwidth.

##  5 Security Analysis

The correctness of the multivariate multiplication is trivial based on the
observation in Equation 1 and 2. As univariate polynomials are implemented
using the same method as the extended fast modulo algorithm, their
effectiveness could also be demonstrated by the correctness and security of
multivariate multiplication. Coalescing mechanisms only alter the order of
communication rounds without modifying the payload, which is also reliable and
secure.

Multivariate computations are similarly secure as traditional Beaver
multiplications under semi-honest conditions. It is intuitively obvious that
since $a_{i}$ is chosen at random by TTP, the $\delta_{i}=x_{i}-a_{i}$ value
is indistinguishable from a random number. Consequently, the disclosure of
$[\delta_{i}]$ does not reveal any critical information regarding $x_{i}$.
This assumption holds even if multiple parties, except for the TTP, collude.

Table 1: Communication Latency and Data with Different Network Settings.
Latency and data are measured in milliseconds and MiBs.

Model | Dataset | $t_{\text{comp}}$ | Data Size |  $t_{\text{comm}}$ ($N_{\text{low}}$) |  $t_{\text{comm}}$ ($N_{\text{med}}$) |  $t_{\text{comm}}$ ($N_{\text{high}}$)
---|---|---|---|---|---|---
Naïve | Ours | Naïve | Ours | Naïve | Ours | Naïve | Ours
LinearSVC | MNIST | 0.032 | 0.022 | 0.024 | 0.082 | 0.059 | 0.604 | 0.568 | 4.339 | 4.026
LeNet | CIFAR-10 | 0.900 | 38.562 | 41.647 | 1.373 | 1.182 | 7.673 | 6.983 | 53.010 | 47.868
ResNet-18 | ImageNet | 110.447 | 11571.294 | 12612.711 | 219.541 | 185.293 | 1681.685 | 1407.570 | ~11 760 | ~9 870
Transformer | Sentiment140 | 7.824 | 771.787 | 893.421 | 12.190 | 9.715 | 78.624 | 61.877 | 559.645 | 421.413

To clarify the security of multivariate multiplication formally, we denote
$[x]_{p}$ as the secret share of $x$ for party $p\in\mathcal{P}$. The global
equations of the multivariate system are as follows:

$\displaystyle\sum_{p\in\mathcal{P}}[x_{i}]_{p}$ $\displaystyle=x_{i}$ (3)
$\displaystyle\sum_{p\in\mathcal{P}}[a_{i}]_{p}$ $\displaystyle=a_{i}$
$\displaystyle\sum_{p\in\mathcal{P}}[a_{i}a_{j}]_{p}$
$\displaystyle=a_{i}a_{j}$ $\displaystyle\dots&\dots{\\\
}\sum_{p\in\mathcal{P}}[a_{1}\dots a_{n}]$ $\displaystyle=a_{1}\dots a_{n}$
$\displaystyle[x_{i}]_{p}-[a_{i}]_{p}$ $\displaystyle=[\delta_{i}]_{p}$

with known $[\delta_{i}]_{p}$ for every $p\in\mathcal{P}$ to each party. From
each party’s view, these $2^{n}+2n-1$ equations have
$\Theta(2^{n}\lVert\mathcal{P}\rVert)$ unknown variables. This indicates the
difficulty in determining the exact value of $x_{i}$, as shown in [18].

A party’s view represents all the values it can obtain during its execution.
Then the following theorem holds:

###### Theorem 1

Let $\\{x_{i}^{\prime}\\}$ and $\\{x_{i}^{\prime\prime}\\}$ be random values.
The distribution of the view of each party is identical when
$x_{i}=x_{i}^{\prime}$ or $x_{i}=x_{i}^{\prime\prime}$.

This guarantees the security of multivariate multiplication by ensuring the
indistinguishability between the random distribution and the view’s
distribution.

##  6 Experiments

###  6.1 Experimental Setup

As part of our proposed methodology, we use CrypTen [5] as the basic MPC deep
learning framework, which has already provided naïve implementations of
secret-sharing-based computations. In most of our experiments, we use 3-party
MPC on CPUs. Additionally, we allow a maximum of $4$-ary multiplication as
stated in Section 4.1, and we set $d=3$ for exponentiation and $k=8$ for
logarithm as described in Section 4.3.

To measure the performance, we perform several experiments with deep learning
models with different sizes:  (a) Linear Support Vector Classification
(LinearSVC) with L2 penalty;  (b) LeNet [19] with shallow convolutional and
linear layers along with ReLU activation functions;  (c) ResNet-18 model [20]
with multiple convolutional, linear, pooling, and activation layers;  (d)
Transformer Encoder model [21] with a single multi-head attention layer and
BatchNorm [22] in place of LayerNorm [23].  We employ several datasets for
classification tasks with appropriate adaption to specific models, including
MNIST [19], CIFAR-10 [24], ImageNet[25], and Sentiment140 [26] datasets.

Each of our experiments is conducted in a simulated multi-node environment
using Docker. TTP is conducted in an independent environment separate from the
normal parties. To manually simulate different network environments concerning
bandwidth and latency, we utilize the docker-tc tool to adjust the docker
network settings accordingly.

###  6.2 Metrics

To provide a comprehensive evaluation of our proposed method, we adopt metrics
from a variety of perspectives.

  * •

$t_{\text{comp}}$: The computational time cost for evaluating a single data
sample in one round.

  * •

$t_{\text{comm}}$: The time cost of communication associated with evaluating a
single data sample in one round.

  * •

Size of Transmission Data: The size of transmitted network packets when
evaluating a single data sample in one round.

  * •

Accuracy: The classification accuracy when evaluated on a particular dataset.

###  6.3 Latency & Throughput

To assess the efficiency of our proposed method, we simulate networks with
different network latencies:  (a) network $N_{\text{low}}$ with 0.1ms latency,
(b) network $N_{\text{med}}$ with 5ms latency,  (c) and network
$N_{\text{high}}$ with 40ms latency.  All of these networks have a bandwidth
of 1Gbps. Our simulated multi-node settings include 3 nodes with an additional
TTP by default.

As shown in Table 1, the computation cost of each model is negligible in
medium and high latency network settings in comparison to the communication
cost. Therefore, we will focus only on the communication costs associated with
our proposed method.

Compared to the naïve method implemented by CrypTen, our method illustrated in
Section 4.1 remains close since it does not introduce a substantial amount of
additional communication payload if the maximum number of input variables is
set appropriately. For instance, a 3-ary or 4-ary multiplication would not
produce a significant increase in the total size of communications.

It is noteworthy that our proposed method reduces the communication cost in
every network setting as compared to the naïve implementation of MPC. Overall,
we achieve an improvement of $10\sim 20\%$, which shows significant
enhancement in the performance of high-latency environments for practical
purposes.

Furthermore, we observe that our proposed method behaves differently with
neural models with different architectures. Figure 1 illustrates the
communication occupation percentage of ResNet basic blocks and Attention
blocks. As can be seen, the attention mechanism is constrained by its
communication bottleneck in Softmax operation, while CNN is constrained by its
communication via convolutional operations. Considering that our method makes
an improved optimization for nonlinear functions, attention-based models show
a significant improvement in latency, with almost a 25% improvement.
Additionally, this explains the limited improvement of only $8\sim 15\%$ in
traditional machine-learning models and CNN-based models.

Table 2: Classification Accuracy using Different Methods.

Model | Dataset | Accuracy (%)
---|---|---
Origin | Naïve | Ours
LinearSVC | MNIST | 100.00 | 100.00 | 100.00
LeNet | CIFAR-10 | 100.00 | 100.00 | 100.00
ResNet-18 | ImageNet | 69.30 | 61.58 | 60.10
Transformer | Sentiment140 | 59.87 | 58.55 | 57.74

(a) ResNet Basic Block

(b) Attention Block

Figure 1: Communication percentage of different models.

###  6.4 Evaluation

In this section, we examine the side effects and factors associated with the
basic settings, such as the downstream tasks’ accuracy, the number of parties
involved, and the trade-off between network latency and bandwidth.

To evaluate the drop in accuracy, we compare our method with both the original
baseline and the naïve implementation without a low-latency design. Figure 2
shows that, in relatively small scenarios, both the naïve implementation and
our methods are capable of achieving perfect performance as the baselines.
Nevertheless, both MPC-based implementations obtain lower accuracy in complex
scenarios than the baseline, while our methods perform slightly worse than the
naïve implementation. We hypothesize that the multivariate multiplication
introduces additional precision requirements, which in turn reduces accuracy.

The throughput and latency of MPC-based methods are also affected by the
number of parties involved in the computation. From Figure 2, it can be seen
that the communication data size of both methods increases linearly as the
number of parties involved increases. There is, however, a tendency for the
latency to be worse when there are more parties involved.

(a) Size of Trans. Data w.r.t # Parties

(b) Latency w.r.t # Parties

Figure 2: Transimission data and latency of naïve and our proposed methods
when a different number of parties are involved. The experiment is conducted
using the LeNet model on CIFAR-10 using a medium latency network. Figure 3:
Latency of naïve and our proposed methods concerning different network
bandwidth. The experiment is conducted using the LeNet model on CIFAR-10 using
a medium latency network.

Moreover, Figure 3 illustrates how network bandwidth affects communication
costs. When sufficient bandwidth is available, our method can still optimize
the network latency. It is important to note, however, that when the bandwidth
becomes the bottleneck, our method would not be any more effective in reducing
the overall costs of communication. This indicates that bandwidth remains an
important factor in a multi-node MPC setting, especially as the number of
nodes in use grows.

##  7 Discussion

Since the proposed multivariate multiplication is based on a finite ring, it
is likely to have precision issues that lead to incorrect results.
Fortunately, a loss in precision would not significantly affect the overall
performance of deep learning, since the loss could be interpreted as random
noise and distortion in the input data.

Moreover, our proposed method is only applicable to functions that are based
on linear MPC operation. To avoid heavy communications, a modern MPC-based
deep learning framework would also involve other protocols, such as
Homomorphic Encryption [27], Garbled Circuit [28], and Function Secret
Sharing[29]. Though these works may have less communication, our approach
could still be seamlessly integrated with the current secret-sharing framework
and achieve a latency improvement of ~20% without adding excessive
computational workload.

##  8 Conclusion

This study proposes a secret-sharing-based MPC method for enhancing the linear
computation required in deep learning through increased communication
utilization. By utilizing the multivariate multiplication and communication
coalescing mechanisms, we can reduce the number of unnecessary communication
rounds during the execution of both linear and nonlinear deep learning
functions. In our experiments, we demonstrate that our proposed methods
achieve an overall improvement in latency of $10\sim 20\%$ when compared to
the naïve MPC implementation. Additionally, it indicates that throughput and
downstream task performance are comparable to naïve implementations, which
demonstrate the method’s validity and efficiency. We hope that this work will
inspire future improvements in privacy-preserving deep learning techniques and
lead to more practical MPC applications.

###### Acknowledgements.

This work is supported by the National Key R&D Program of China under grant
(No. 2022YFB2703001).

## References

  * Damgård et al. [2012] I. Damgård, V. Pastro, N. Smart, S. Zakarias,  Multiparty computation from somewhat homomorphic encryption,  in: R. Safavi-Naini, R. Canetti (Eds.), CRYPTO 2012, Springer Berlin Heidelberg, Berlin, Heidelberg, 2012, pp. 643–662. doi:10.1007/978-3-642-32009-5_38.
  * Keller [2020] M. Keller,  Mp-spdz: A versatile framework for multi-party computation,  in: Proceedings of the 2020 ACM SIGSAC Conference on Computer and Communications Security, CCS ’20, Association for Computing Machinery, New York, NY, USA, 2020, p. 1575–1590. doi:10.1145/3372297.3417872.
  * Liu et al. [2021] X. Liu, L. Xie, Y. Wang, J. Zou, J. Xiong, Z. Ying, A. V. Vasilakos,  Privacy and security issues in deep learning: A survey,  IEEE Access 9 (2021) 4566–4593. doi:10.1109/ACCESS.2020.3045078.
  * Lu et al. [2021] D. Lu, A. Yu, A. Kate, H. Maji,  Polymath: Low-latency mpc via secure polynomial evaluations and its applications,  Proceedings on Privacy Enhancing Technologies 2022 (2021). doi:10.2478/popets-2022-0020.
  * Knott et al. [2021] B. Knott, S. Venkataraman, A. Hannun, S. Sengupta, M. Ibrahim, L. van der Maaten,  Crypten: Secure multi-party computation meets machine learning,  NIPS 34 (2021) 4961–4973. doi:10.48550/arXiv.2109.00984.
  * Tan et al. [2021] S. Tan, B. Knott, Y. Tian, D. J. Wu,  CryptGPU: Fast privacy-preserving machine learning on the gpu,  in: IEEE S&P, 2021. doi:10.1109/SP40001.2021.00098.
  * Li et al. [2023] D. Li, H. Wang, R. Shao, H. Guo, E. Xing, H. Zhang,  Mpcformer: fast, performant and private transformer inference with mpc,  in: The 11th International Conference on Learning Representations, 2023. doi:10.48550/arXiv.2211.01452.
  * Wagh et al. [2020] S. Wagh, S. Tople, F. Benhamouda, E. Kushilevitz, P. Mittal, T. Rabin,  Falcon: Honest-majority maliciously secure framework for private deep learning,  Proceedings on Privacy Enhancing Technologies 2021 (2020) 188 – 208. doi:10.2478/popets-2021-0011.
  * Krips et al. [2022] T. Krips, R. Küsters, P. Reisert, M. Rivinius,  Arithmetic tuples for mpc,  Cryptology ePrint Archive (2022). URL: https://eprint.iacr.org/2022/667.
  * Shamir [1979] A. Shamir,  How to share a secret,  Commun. ACM 22 (1979) 612–613. doi:10.1145/359168.359176.
  * Beaver [1992] D. Beaver,  Efficient multiparty protocols using circuit randomization,  in: J. Feigenbaum (Ed.), CRYPTO 1991, Springer Berlin Heidelberg, Berlin, Heidelberg, 1992, pp. 420–432. doi:10.1007/3-540-46766-1_34.
  * Ishai and Kushilevitz [2000] Y. Ishai, E. Kushilevitz,  Randomizing polynomials: A new representation with applications to round-efficient secure computation,  in: Proceedings 41st Annual Symposium on Foundations of Computer Science, 2000, pp. 294–304. doi:10.1109/SFCS.2000.892118.
  * Mohassel and Franklin [2006] P. Mohassel, M. Franklin,  Efficient polynomial operations in the shared-coefficients setting,  in: M. Yung, Y. Dodis, A. Kiayias, T. Malkin (Eds.), PKC 2006, Springer Berlin Heidelberg, Berlin, Heidelberg, 2006, pp. 44–57. doi:10.1007/11745853_4.
  * Dachman-Soled et al. [2011] D. Dachman-Soled, T. Malkin, M. Raykova, M. Yung,  Secure efficient multiparty computing of multivariate polynomials and applications,  in: J. Lopez, G. Tsudik (Eds.), Applied Cryptography and Network Security, Springer Berlin Heidelberg, Berlin, Heidelberg, 2011, pp. 130–146. doi:10.1007/978-3-642-21554-4_8.
  * Wagh et al. [2018] S. Wagh, D. Gupta, N. Chandran,  Securenn: Efficient and private neural network training,  Cryptology ePrint Archive (2018). URL: https://eprint.iacr.org/2018/442.
  * Mohassel and Rindal [2018] P. Mohassel, P. Rindal,  Aby3: A mixed protocol framework for machine learning,  in: Proceedings of the 2018 ACM SIGSAC Conference on Computer and Communications Security, CCS ’18, Association for Computing Machinery, New York, NY, USA, 2018, p. 35–52. doi:10.1145/3243734.3243760.
  * Damgård et al. [2006] I. Damgård, M. Fitzi, E. Kiltz, J. B. Nielsen, T. Toft,  Unconditionally secure constant-rounds multi-party computation for equality, comparison, bits and exponentiation,  in: S. Halevi, T. Rabin (Eds.), Theory of Cryptography, Springer Berlin Heidelberg, Berlin, Heidelberg, 2006, pp. 285–304. doi:10.1007/11681878_15.
  * Couteau [2019] G. Couteau,  A note on the communication complexity of multiparty computation in the correlated randomness model,  in: EUROCRYPT 2019, Springer-Verlag, Berlin, Heidelberg, 2019, p. 473–503. doi:10.1007/978-3-030-17656-3_17.
  * Lecun et al. [1998] Y. Lecun, L. Bottou, Y. Bengio, P. Haffner,  Gradient-based learning applied to document recognition,  Proceedings of the IEEE 86 (1998) 2278–2324. doi:10.1109/5.726791.
  * He et al. [2016] K. He, X. Zhang, S. Ren, J. Sun,  Deep residual learning for image recognition,  in: CVPR, 2016, pp. 770–778. doi:10.1109/CVPR.2016.90.
  * Vaswani et al. [2017] A. Vaswani, N. Shazeer, N. Parmar, J. Uszkoreit, L. Jones, A. N. Gomez, L. u. Kaiser, I. Polosukhin,  Attention is all you need,  in: I. Guyon, U. V. Luxburg, S. Bengio, H. Wallach, R. Fergus, S. Vishwanathan, R. Garnett (Eds.), NIPS, volume 30, Curran Associates, Inc., 2017. doi:10.5555/3295222.3295349.
  * Ioffe and Szegedy [2015] S. Ioffe, C. Szegedy,  Batch normalization: accelerating deep network training by reducing internal covariate shift,  in: Proc. 32nd Int. Conf. Machine Learning - Volume 37, ICML’15, JMLR.org, 2015, p. 448–456. doi:10.5555/3045118.3045167.
  * Ba et al. [2016] J. L. Ba, J. R. Kiros, G. E. Hinton, Layer normalization, 2016. arXiv:1607.06450.
  * Krizhevsky et al. [2009] A. Krizhevsky, G. Hinton, et al.,  Learning multiple layers of features from tiny images (2009).
  * Deng et al. [2009] J. Deng, W. Dong, R. Socher, L.-J. Li, K. Li, L. Fei-Fei,  Imagenet: A large-scale hierarchical image database,  in: CVPR, 2009, pp. 248–255. doi:10.1109/CVPR.2009.5206848.
  * Go et al. [2009] A. Go, R. Bhayani, L. Huang,  Twitter sentiment classification using distant supervision,  CS224N project report, Stanford 1 (2009) 2009.
  * Gentry [2009] C. Gentry,  Fully homomorphic encryption using ideal lattices,  in: Proceedings of the Forty-First Annual ACM Symposium on Theory of Computing, STOC ’09, Association for Computing Machinery, New York, NY, USA, 2009, p. 169–178. doi:10.1145/1536414.1536440.
  * Yao [1982] A. C. Yao,  Protocols for secure computations,  in: 23rd Annual Symposium on Foundations of Computer Science (sfcs 1982), 1982, pp. 160–164. doi:10.1109/SFCS.1982.38.
  * Boyle et al. [2015] E. Boyle, N. Gilboa, Y. Ishai,  Function secret sharing,  in: E. Oswald, M. Fischlin (Eds.), EUROCRYPT 2015, Springer Berlin Heidelberg, Berlin, Heidelberg, 2015, pp. 337–367. doi:10.1007/978-3-662-46803-6_12.