summaries: This paper adopts semi-hard negative mining, a sampling strategy widely used for metric learning, for contrastive self-supervised learning. Specifically, the paper chooses the negative samples in the range of $[w_l, w_u]$ percentiles (close, but not too close) in terms of the normalized feature distance. As the initial representation is not informative, the paper anneals down the percentile range. This sampling strategy improves the contrastive learning methods (IR, CMC, MoCO).

summaries: This is an interesting paper that discusses the negative sample mining in visual representation learning. The authors discuss the theory and method to conditionally select the negative samples based on the dot product of representations in noise constructive estimation (NCE). Their theory shows that the NCE with negative examples sampling from a conditional distribution q is lower bounded with mutual information, and the object has higher bias and lower variance. The authors also provide the method to construct the conditional distribution by picking a ring surface where the dot product of representations is bounded within percentiles of data.

summaries: Inspired by the effectiveness of hard negative mining in deep metric learning, this papers focuses on the problem of negative mining in unsupervised learning under the contrastive setting. One of the problems in this scenario is that naively selecting difficult negatives may yield an objective that no longer bounds mutual information, which is the basis for many contrastive objectives such as the Noise Contrastive Estimator. To address this problem, this paper formally defines a family of conditional distributions where negatives can be drawn from (negatives are chosen conditional on the current instance), while maintaining a lower bound on the NCE and on mutual information, resulting in a new estimator dubbed Conditional NCE. It also shows that, even though it’s a looser bound than NCE, it also has lower variance, which may lead to better local optima. Finally, within this family of conditional distributions, the paper proposes the Ring model, which takes inspiration from semi-hard negative mining approaches, and that can be applied to state-of-the-art contrastive algorithms in order to sample harder negatives, resulting in better representations.

abstractText: Recent methods for learning unsupervised visual representations, dubbed contrastive learning, optimize the noise-contrastive estimation (NCE) bound on mutual information between two transformations of an image. NCE typically uses randomly sampled negative examples to normalize the objective, but this may often include many uninformative examples either because they are too easy or too hard to discriminate. Taking inspiration from metric learning, we show that choosing semi-hard negatives can yield stronger contrastive representations. To do this, we introduce a family of mutual information estimators that sample negatives conditionally – in a “ring” around each positive. We prove that these estimators remain lower-bounds of mutual information, with higher bias but lower variance than NCE. Experimentally, we find our approach, applied on top of existing models (IR, CMC, and MoCo) improves accuracy by 2-5% absolute points in each case, measured by linear evaluation on four standard image benchmarks. Moreover, we find continued benefits when transferring features to a variety of new image distributions from the Meta-Dataset collection and to a variety of downstream tasks such as object detection, instance segmentation, and key-point detection.

authors:
Yuki Markus Asano
Christian Rupprecht
Andrea Vedaldi

title: Self-labelling via simultaneous clustering and representation learning

venue: arXiv preprint arXiv:1911.05371,

authors:
Philip Bachman
R Devon Hjelm
William Buchwalter

title: Learning representations by maximizing mutual information across views

venue: In Advances in Neural Information Processing Systems,

authors:
Sören Becker
Marcel Ackermann
Sebastian Lapuschkin
Klaus-Robert Müller
Wojciech Samek

title: Interpreting and explaining deep neural networks for classification of audio signals

venue: arXiv preprint arXiv:1807.03418,

authors:
Suzanna Becker
Geoffrey E Hinton

title: Self-organizing neural network that discovers surfaces in random-dot stereograms

authors:
Mathilde Caron
Ishan Misra
Julien Mairal
Priya Goyal
Piotr Bojanowski
Armand Joulin

title: Unsupervised learning of visual features by contrasting cluster assignments

venue: arXiv preprint arXiv:2006.09882,

authors:
Ting Chen
Xiaohua Zhai
Marvin Ritter
Mario Lucic
Neil Houlsby

title: Self-supervised gans via auxiliary rotation loss

venue: In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition,

authors:
Ting Chen
Simon Kornblith
Mohammad Norouzi
Geoffrey Hinton

title: A simple framework for contrastive learning of visual representations

venue: arXiv preprint arXiv:2002.05709,

authors:
Xinlei Chen
Haoqi Fan
Ross Girshick
Kaiming He

title: Improved baselines with momentum contrastive learning

venue: arXiv preprint arXiv:2003.04297,

authors:
Carl Doersch
Andrew Zisserman

title: Multi-task self-supervised visual learning

authors:
Carl Doersch
Abhinav Gupta
Alexei A Efros

title: Unsupervised visual representation learning by context prediction

venue: In Proceedings of the IEEE International Conference on Computer Vision, pp

authors:
Jeff Donahue
Karen Simonyan

title: Large scale adversarial representation learning

authors:
Alexey Dosovitskiy
Jost Tobias Springenberg
Martin Riedmiller
Thomas Brox

title: Discriminative unsupervised feature learning with convolutional neural networks. In Advances in neural information processing

authors:
Mark Everingham
Luc Van Gool
Christopher KI Williams
John Winn
Andrew Zisserman

title: The pascal visual object classes (voc) challenge

venue: International journal of computer vision,

title: Pytorch lightning

venue: GitHub. Note: https://github. com/williamFalcon/pytorchlightning Cited by,

authors:
Spyros Gidaris
Praveer Singh
Nikos Komodakis

title: Unsupervised representation learning by predicting image rotations

venue: arXiv preprint arXiv:1803.07728,

authors:
Jean-Bastien Grill
Florian Strub
Florent Altché
Corentin Tallec
Pierre H Richemond
Elena Buchatskaya
Carl Doersch
Bernardo Avila Pires
Zhaohan Daniel Guo
Mohammad Gheshlaghi Azar

title: Bootstrap your own latent: A new approach to self-supervised learning

venue: arXiv preprint arXiv:2006.07733,

authors:
Raia Hadsell
Sumit Chopra
Yann LeCun

title: Dimensionality reduction by learning an invariant mapping

venue: IEEE Computer Society Conference on Computer Vision and Pattern Recognition (CVPR’06),

authors:
Kaiming He
Georgia Gkioxari
Piotr Dollár
Ross Girshick

title: Mask r-cnn

venue: In Proceedings of the IEEE international conference on computer vision,

authors:
Kaiming He
Haoqi Fan
Yuxin Wu
Saining Xie
Ross Girshick

title: Momentum contrast for unsupervised visual representation learning

authors:
Olivier J Hénaff
Aravind Srinivas
Jeffrey De Fauw
Ali Razavi
Carl Doersch
SM Eslami
Aaron van den Oord

title: Data-efficient image recognition with contrastive predictive coding

authors:
R Devon Hjelm
Alex Fedorov
Samuel Lavoie-Marchildon
Karan Grewal
Phil Bachman
Adam Trischler
Yoshua Bengio

title: Learning deep representations by mutual information estimation and maximization

venue: arXiv preprint arXiv:1808.06670,

authors:
Sergey Ioffe
Christian Szegedy

title: Batch normalization: Accelerating deep network training by reducing internal covariate shift

venue: arXiv preprint arXiv:1502.03167,

authors:
Xu Ji
João F Henriques
Andrea Vedaldi

title: Invariant information clustering for unsupervised image classification and segmentation

authors:
Alexander Kolesnikov
Xiaohua Zhai
Lucas Beyer

title: Revisiting self-supervised visual representation learning

venue: In Proceedings of the IEEE conference on Computer Vision and Pattern Recognition,

authors:
Junnan Li
Pan Zhou
Caiming Xiong
Richard Socher
Steven CH Hoi

title: Prototypical contrastive learning of unsupervised representations

venue: arXiv preprint arXiv:2005.04966,

authors:
Tsung-Yi Lin
Michael Maire
Serge Belongie
James Hays
Pietro Perona
Deva Ramanan
Piotr Dollár
C Lawrence Zitnick

title: Microsoft coco: Common objects in context

venue: In European conference on computer vision,

authors:
Loren Lugosch
Mirco Ravanelli
Patrick Ignoto
Vikrant Singh Tomar
Yoshua Bengio

title: Speech model pre-training for end-to-end spoken language understanding

authors:
Ishan Misra
Laurens van der Maaten

title: Self-supervised learning of pretext-invariant representations

venue: In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition,

authors:
Hyun Oh Song
Yu Xiang
Stefanie Jegelka
Silvio Savarese

title: Deep metric learning via lifted structured feature embedding

venue: In Proceedings of the IEEE conference on computer vision and pattern recognition,

authors:
Aaron van den Oord
Yazhe Li
Oriol Vinyals

title: Representation learning with contrastive predictive coding

venue: arXiv preprint arXiv:1807.03748,

authors:
Vassil Panayotov
Guoguo Chen
Daniel Povey
Sanjeev Khudanpur

title: Librispeech: an asr corpus based on public domain audio books

venue: In 2015 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP),

authors:
Deepak Pathak
Ross Girshick
Piotr Dollár
Trevor Darrell
Bharath Hariharan

title: Learning features by watching objects move

authors:
Ben Poole
Sherjil Ozair
Aaron van den Oord
Alexander A Alemi
George Tucker

title: On variational bounds of mutual information

authors:
Olga Russakovsky
Jia Deng
Hao Su
Jonathan Krause
Sanjeev Satheesh
Sean Ma
Zhiheng Huang
Andrej Karpathy
Aditya Khosla
Michael Bernstein

title: Imagenet large scale visual recognition challenge

authors:
Florian Schroff
Dmitry Kalenichenko
James Philbin

title: Facenet: A unified embedding for face recognition and clustering

authors:
Alex Tamkin
Mike Wu
Noah Goodman

title: Viewmaker networks: Learning views for unsupervised representation learning

venue: arXiv preprint arXiv:2010.07432,

authors:
Yonglong Tian
Dilip Krishnan
Phillip Isola

title: Contrastive multiview coding

venue: arXiv preprint arXiv:1906.05849,

authors:
Yonglong Tian
Chen Sun
Ben Poole
Dilip Krishnan
Cordelia Schmid
Phillip Isola

title: What makes for good views for contrastive learning

venue: arXiv preprint arXiv:2005.10243,

authors:
Eleni Triantafillou
Tyler Zhu
Vincent Dumoulin
Pascal Lamblin
Utku Evci
Kelvin Xu
Ross Goroshin
Carles Gelada
Kevin Swersky
Pierre-Antoine Manzagol

title: Meta-dataset: A dataset of datasets for learning to learn from few examples

venue: arXiv preprint arXiv:1903.03096,

authors:
Michael Tschannen
Josip Djolonga
Paul K Rubenstein
Sylvain Gelly
Mario Lucic

title: On mutual information maximization for representation learning

authors:
Xiaolong Wang
Abhinav Gupta

title: Unsupervised learning of visual representations using videos

title: Speech commands: A dataset for limited-vocabulary speech recognition

venue: arXiv preprint arXiv:1804.03209,

authors:
Chao-Yuan Wu
R Manmatha
Alexander J Smola
Philipp Krahenbuhl

title: Sampling matters in deep embedding learning

authors:
Mike Wu
Chengxu Zhuang
Milan Mosse
Daniel Yamins
Noah Goodman

title: On mutual information in contrastive learning for visual representations

venue: arXiv preprint arXiv:2005.13149,

authors:
Zhirong Wu
Yuanjun Xiong
Stella X Yu
Dahua Lin

title: Unsupervised feature learning via nonparametric instance discrimination

authors:
Jiahao Xie
Xiaohang Zhan
Ziwei Liu
Yew Soon Ong
Chen Change Loy

title: Delving into interimage invariance for unsupervised visual representations

venue: arXiv preprint arXiv:2008.11702,

authors:
Mang Ye
Xu Zhang
Pong C Yuen
Shih-Fu Chang

title: Unsupervised embedding learning via invariant and spreading instance feature

venue: In Proceedings of the IEEE Conference on computer vision and pattern recognition,

authors:
Yuhui Yuan
Kuiyuan Yang
Chao Zhang

title: Hard-aware deeply cascaded embedding

authors:
Richard Zhang
Phillip Isola
Alexei A Efros

title: Colorful image colorization

authors:
Chengxu Zhuang
Alex Lin Zhai
Daniel Yamins

title: Local aggregation for unsupervised learning of visual embeddings

heading: 1 INTRODUCTION

text:
Supervised learning has given rise to human-level performance in several visual tasks (Russakovsky et al., 2015; He et al., 2017), relying heavily on large image datasets paired with semantic annotations. These annotations vary in difficulty and cost, spanning from simple class labels to more granular descriptions like bounding boxes and key-points. As it is impractical to scale high quality annotations, this reliance on supervision poses a barrier to widespread adoption. While supervised pretraining is still the dominant approach in computer vision, recent studies using unsupervised “contrastive” objectives, have achieved remarkable results in the last two years, closing the gap to supervised baselines (Wu et al., 2018; Oord et al., 2018; Hjelm et al., 2018; Zhuang et al., 2019; Hénaff et al., 2019; Misra & Maaten, 2020; He et al., 2019; Chen et al., 2020a;b; Grill et al., 2020).
Many contrastive algorithms are estimators of mutual information (Oord et al., 2018; Hjelm et al., 2018; Bachman et al., 2019), capturing the intuition that a good low-dimensional “representation” is one that linearizes the useful information embedded within a high-dimensional data point. In vision, these estimators maximize the similarity of encodings for two augmentations of the same image. This is trivial (e.g. assign all image pairs maximum similarity) unless the similarity function is normalized. This is typically done by comparing an image to “negative examples”, which a model must assign low similarity to. We hypothesize that how we choose these negatives greatly impacts the representation quality. With harder negatives, the encoder is encouraged to capture more granular information that may improve performance on downstream tasks. While research in contrastive learning has explored architectures, augmentations, and pretext tasks, there has been little attention given to the negative sampling procedure. Meanwhile, there is a rich body of work in deep metric learning showing semi-hard negative mining to improve the efficacy of triplet losses. Inspired by this, we hope to bring harder negative sampling to modern contrastive learning.
Naively choosing difficult negatives may yield an objective that no longer bounds mutual information, removing a theoretical connection that is core to contrastive learning and has been shown to
be important for downstream performance (Tian et al., 2020). In this paper, we present a new estimator of mutual information based on the popular noise-contrastive estimator (NCE) that supports sampling negatives from conditional distributions. We summarize our contributions below:
1. We prove our Conditional-NCE (CNCE) objective to lower bound mutual information. Further, we show that although CNCE is a looser bound than NCE, it has lower variance. This motivates its value for representation learning.
2. We use CNCE to generalize contrastive algorithms that utilize a memory structure like IR, CMC, and MoCo to sample semi-hard negatives in just a few lines of code and minimal compute overhead.
3. We find that the naive strategy of sampling hard negatives throughout training can be detrimental. We then show that slowly introducing harder negatives yields good performance.
4. On four image classification benchmarks, we find improvements of 2-5% absolute points. We also find consistent improvements (1) when transferring features to new image datasets and (2) in object detection, instance segmentation, and key-point detection.

heading: 2 BACKGROUND

text:
We focus on exemplar-based contrastive objectives, where examples are compared to one another to learn a representation. Many of these objectives (Hjelm et al., 2018; Wu et al., 2018; Bachman et al., 2019; Tian et al., 2019; Chen et al., 2020a) are equivalent to NCE (Oord et al., 2018; Poole et al., 2019), a popular lower bound on the mutual information, denoted by I, between two random variables. This connection is well-known and stated in several works (Chen et al., 2020a; Tschannen et al., 2019; Tian et al., 2020; Wu et al., 2020). To review, recall:
I(X;Y ) INCE(X;Y ) = Exi,yi⇠p(x,y)Ey1:k⇠p(y)
" log
ef✓(xi,yi)
1 k+1 P j2{i,1:k} e f✓(xi,yj)
# (1)
where x, y are realizations of two random variables, X and Y , and f✓ : X ⇥ Y ! R is a similarity function. We call y1:k = {y1, . . . yk} negative examples, being other realizations of Y . Suppose the two random variables in Eq. 1 are both transformations of a common random variable X . Let T be a family of transformations where each member t is a composition of cropping, color jittering, gaussian blurring, among others (Wu et al., 2018; Bachman et al., 2019; Chen et al., 2020a). We call a transformed input t(x) a “view” of x. Let p(t) denote a distribution over T , a common choice being uniform. Next, introduce an encoder g✓ : X ! Sn 1 that maps an example to a L2-normalized representation. Suppose we have a dataset D = {xi}ni=1 of n values for X sampled from a distribution p(x). Then, the contrastive objective for the i-th example is:
L(xi) = Et,t0,t1:k⇠p(t)Ex1:k⇠p(x)
" log
eg✓(t(xi)) T g✓(t 0(xi))/⌧
1 k+1 P j2{i,1:k} e g✓(t(xi))T g✓(tj(xj))/⌧
# (2)
where ⌧ is a temperature. The equivalence of Eq. 2 to NCE is immediate given f✓(x, y) = g✓(x)T g✓(y)/⌧ . Maximizing Eq. 2 chooses an embedding that pulls two views of the same example together while pushing two views of distinct examples apart. A drawback to this framework is that the number of negatives k must be large to faithfully approximate the true partition. In practice, k is limited by memory. Recent innovations have focused on tackling this challenge:
Instance Discrimination (Wu et al., 2018), or IR, introduces a memory bank of n entries to cache embeddings of each example throughout training. Since every epoch we observe each example once, the memory bank will save the embedding of the view of the i-th example observed last epoch in its ith entry. Representations stored in the memory bank are removed from the automatic differentiation tape, but in return, we can choose a large k by querying M . A follow up work, Contrastive Multiview Coding (Tian et al., 2019), or CMC, decomposes an image into two color modalities. Then, CMC sums two IR losses where the memory banks for each modality are swapped.
Momentum Contrast (He et al., 2019), or MoCo, observed that the representations stored in the memory bank grow stale, since possibly thousands of optimization steps pass before updating an entry again. So, MoCo makes two important changes. First, it replaces the memory bank with a
first-in first-out (FIFO) queue of size k. During each minibatch, representations are cached into the queue while the most stale ones are removed. Second, MoCo introduces a second (momentum) encoder g0✓0 as a copy of g✓. The primary encoder g✓ is used to embed one view of xi whereas the momentum encoder is used to embed the other. Again, gradients are not propagated to g0✓0 .
In this work, we focus on contrastive algorithms that utilize a memory structure that we repurpose in Sec. 4 to efficiently sample hard negatives from. In Sec. 7, we briefly discuss generalizations to contrastive algorithms that do not use a memory structure.

heading: 3 CONDITIONAL NOISE CONTRASTIVE ESTIMATION

text:
In NCE, the negative examples are sampled i.i.d. from the marginal distribution, p(y). Indeed, the existing proof that NCE lower bounds mutual information (Poole et al., 2019) assumes this to be true. However, choosing negatives in this manner may not be the best choice for learning a good representation. For instance, prior work in metric learning has shown the effectiveness of semihard negative mining in optimizing triplet losses (Wu et al., 2017; Yuan et al., 2017; Schroff et al., 2015). We similarly wish to exploit choosing semi-hard negatives in NCE conditional on the current example but to do so in a manner that preserves the lower bound on mutual information.
In presenting the theory, we assume two random variables X and Y , deriving a general bound; we will return to the contrastive learning setting in Sec. 4. To begin, in Eq. 1, suppose we sample negatives from a distribution q(y|x) conditional on a value x ⇠ p(x) rather than the marginal p(y), which is independent of X . Ideally, we would like to freely choose q(y|x) to be any distribution but not all choices preserve a bound on mutual information1. This does not, however, imply that we can only sample negatives from p(y) (Poole et al., 2019; Oord et al., 2018). One of our contributions is to formally define a family of conditional distributions Q such that for any q(y|x) 2 Q, drawing negative examples from q defines an estimator that lower bounds I(X;Y ). We call this new bound the Conditional Noise Contrastive Estimator, or CNCE. We first prove CNCE to be a bound: Theorem 3.1. (The Conditional NCE bound) Define d-dimensional random variables X and Y by a joint distribution p(x, y) and let Y1, ..., Yk be i.i.d. copies of Y with the marginal distribution p(y). Fix any function f : (X,Y ) ! R, any realization x of X , and let c = Ey⇠p(y)[ef(x,y)], the expected exponentiated similarity. Pick a set B ⇢ R strictly lower-bounded by c. Assume the pulled back set SB = {y|ef(x,y) 2 B} has non-zero probability (i.e. p(SB) > 0). For A1, . . . , Ak in the Borel -algebra over Rd, define A = A1 ⇥ . . .⇥Ak and let
q((Y1, . . . , Yk) 2 A|X = x) = kY
j=1
p(Aj |SB).
Let ICNCE(X;Y ) = Ex,y⇠p(x,y)Ey1,...,yk⇠q(y1,...,yk|x)  log e f(x,y)
1 k Pk j=1 e f(x,yj)
. Then ICNCE  INCE.
Proof. To show ICNCE  INCE, we show Ep[log Pk j=1 e f(x,yj)] < Eq[log Pk j=1 e
f(x,yj)]. To see this, apply Jensen’s to the left-hand side of logEp[ Pk j=1 e f(x,yj)] < log Pk j=1 e f(x,yj), which holds if yj 2 SB for j = 1, . . . , k, and then take the expectation Eq of both sides. The last inequality holds by monoticity of log, linearity of expectation, and the fact that Ep[ef(x,yj)]  ef(x,yj).
Theorem Intuition. For intuition, although using arbitrary negative distributions in NCE does not bound mutual information, we have found a restricted class of distributions Q where every member q(y|x) “subsets the support” of the distribution p(y). That is, given some fixed value x, we have defined q(y|x) to constrain the support of p(y) to a set SB whose members are “close” to x as measured by the similarity function f . For every element y 2 SB , the distribution q(y|x) wants to assign to it the same probability as p(y). However, as q(y|x) is not defined outside of SB , we must renormalize it to sum to one (hence p(Aj |SB) = p(Aj\SB)p(SB) ). Intuitively, q(y|x) cannot change p(y) too much: it must redistribute mass proportionally. The primary distinction then, is the smaller
1We provide a counterexample in Sec. A.1.
support of q(y|x), which forces samples from it to be harder for f to distinguish from x. Thm. 3.1 shows that substituting q(y|x) for p(y) in NCE still bounds mutual information. Theorem Example 3.1. We give a concrete example for the choice B that will be used in Sec. 4. For any realization x, suppose we define two similarity thresholds !`,!u 2 R where c < !` < !u. Then, choose B = [w`, wu]. In this case, the set SB , which defines the support of the distribution q(y|x), contains values of y that are not “too-close” to x but not “too-far”. In contrastive learning, we might pick these similarity thresholds to vary the difficulty of negative samples.
Interestingly, Thm. 3.1 states that CNCE is looser than NCE, which raises the question: when is a looser bound useful? In reply, we show that while CNCE is a more biased estimator than NCE, in return it has lower variance. Intuitively, because q(y|x) is the result of restricting p(y) to a smaller support, samples from q(y|x) have less opportunity to deviate, hence lower variance. Formally: Theorem 3.2. (Bias and Variance Tradeoff) Pick any x, y ⇠ p(x, y). Fix the distribution q(y1:k|x)
as stated in Theorem 3.1. Define a new random variable Z(y1:k) = log
✓ ef(x,y)
1 k Pk j=1 e f(x,yj)
◆ repre-
senting the normalized similarity. By Theorem 3.1, the expressions Ep(y1:k)[Z] and Eq(y1:k|x)[Z] are estimators for I(X;Y ). Suppose that the set SB is chosen to ensure Varq(y1:k|x)[Z]  Varq̃(y1:k|x)[Z], where q̃(A) = p(A| complement of SB). That is, we assume the variance of the normalized similarity when using y1:k 2 SB is smaller than when using y1:k /2 SB . Then Biasp(y1:k)(Z)  Biasq(y1:k|x)(Z) and Varp(y1:k)(Z) Varq(y1:k|x)(Z).
The proof can be found in Sec. A.2. Thm. 3.2 provides one answer to our question of looseness. In stochastic optimization, a lower variance objective may lead to better local optima. For representation learning, using CNCE to sample more difficult negatives may (1) encourage the representation to distinguish fine-grained features useful in transfer tasks, and (2) provide less noisy gradients.

heading: 4 RING DISCRIMINATION

text:
We have shown CNCE to be a new bound on the mutual information that uses hard negative samples. Now we wish to apply CNCE to contrastive learning where the two random variables are again transformations of a single variable X . In this setting, for a fixed xi ⇠ p(x), the CNCE distribution is written as q(x|t(xi)) for some transform t 2 T . Samples from x ⇠ q(x|t(xi)) will be such that the exponentiated distance, exp{g✓(t(xi))T g✓(t0(x))}, is at least a minimum value c. As in Example 3.1, we will choose B = [!`,!u], a closed interval in R defined by two thresholds.
Picking thresholds. We pick the thresholds conditioned on the i-th example in the dataset, hence each example has a different set B. We first describe how to pick the upper threshold !u. Given the i-example xi, we pick a number u 2 [0, 100] representing an upper “percentile”. We consider each example x in the dataset to be in the support SB if and only if the (exponentiated) distance between the embedding of xi and x, or exp{g✓(t(xi))T g✓(t0(x))}, is below the u-th percentile for all x 2 D. Call this maximum distance !u. In other words, we construct q(x|t(xi)) such that we ignore examples from the dataset whose embedding dot producted with the embedding of xi is above !u. (Note that u = 100 recovers NCE.) For a small enough choice of u, the upper similarity threshold !u will be greater than c (defined in Thm. 3.1 as the expected distance with respect to p(x)), and the samples from q(x|t(xi)) will be harder negatives to discriminate from xi.
In picking the lower threshold !`, one could choose it to be 0, so B = [0,!u). However, picking the closest examples to t(xi) as its negative examples may be inappropriate, as these examples might be better suited as positive views rather than negatives (Zhuang et al., 2019; Xie et al., 2020). As an extreme case, if the same image is included in the dataset twice, we would not like to select it as a negative example for itself. Furthermore, choosing negatives “too close” to the current instance may result in representations that pick up on fine-grain details only, ignoring larger semantic concepts. This suggests removing examples from q(x|t(xi)) we consider “too close” to xi. To do this, we pick a lower percentile 0  ` < u. For each example x 2 D, we say it is in SB if exp{g✓(t(xi))T g✓(t0(x))} is below !u and also if it is above the `-th percentile of all distances with respect to D. Call this minimum distance !`. Fig. 2 visualizes this whole procedure.
dist(x ,x )=i 1
=dist(x ,x )i 1
q(x|t(x ))i
T
Step 3: Sort distances. Step 4: Compute threhsolds. Step 5: Define distribution q.
l-th u-th
SB lw
wu R5 4 1 3 4 x x x x x
Step 1: Pick two percentiles. Step 2: Compute distances.
dist(x,y)= e g(t(x)) g(t’(y))T
0 l u 100 1 2 3 4 5x x x x x
x
p(x)
i
SB
xi i
5 dist(x ,x ) i 1 dis t(x
,x )
old, !u, to be very small early in training. At the start of training, the encoder g✓ is randomly initialized and cannot guarantee that elements in the `-th to u-th percentile are properly calibrated: if the representations are near random, choosing negatives that are close in embedding distance may detrimentally exclude those examples that are “actually” close. This could lock in poor local minima. To avoid this, we propose to use an annealing policy that reduces !u (and thus the size of the support SB) throughout training. Early in training we choose !u to be large. Over many epochs, we slowly decrease !u closer to !l, thereby selecting more difficult negatives. We explored several annealing policies and found a linear schedule to be well-performing and simple (see Sec. G). In our experiments, annealing is shown to be crucial: being too aggressive with negatives early in training produced representations that performed poorly on downstream tasks.

heading: 5 EXPERIMENTS

text:
We explore our method applied to IR, CMC, and MoCo in four commonly used visual datasets. As in prior work (Wu et al., 2018; Zhuang et al., 2019; He et al., 2019; Misra & Maaten, 2020; Hénaff
et al., 2019; Kolesnikov et al., 2019; Donahue & Simonyan, 2019; Bachman et al., 2019; Tian et al., 2019; Chen et al., 2020a), we evaluate each method by linear classification on frozen embeddings. That is, we optimize a contrastive objective on a pretraining dataset to learn a representation; then, using a transfer dataset, we fit logistic regression on representations only. A better representation would contain more “object-centric” information, thereby achieving a higher classification score.
Training Details. We pick the upper percentile u = 10 and the lower percentile ` = 1 although we anneal u starting from 100. We resize input images to be 256 by 256 pixels, and normalize them using dataset mean and standard deviation. The temperature ⌧ is set to 0.07. We use a composition of a 224 by 224-pixel random crop, random color jittering, random horizontal flip, and random grayscale conversion as our augmentation family T . We use a ResNet-18 encoder with a output dimension of 128. For CMC, we use two ResNet-18 encoders, doubling the number of parameters. For linear classification, we treat the pre-pool output (size 512 ⇥ 7 ⇥ 7) after the last convolutional layer as the input to the logistic regression. Note that this setup is equivalent to using a linear projection head (Chen et al., 2020a;b). In pretraining, we use SGD with learning rate 0.03, momentum 0.9 and weight decay 1e-4 for 300 epochs and batch size 256 (128 for CMC). We drop the learning rate twice by a factor of 10 on epochs 200 and 250. In transfer, we use SGD with learning rate 0.01, momentum 0.9, and no weight decay for 100 epochs without dropping learning rate. These hyperparameters were taken from Wu et al. (2018) and used in all of Table 1 for a consistent comparison. We found normalizing hyperparameters to be important for a fair comparison as many competing algorithms use different hyperparameters. For a state-of-the-art comparison, see Table 5.
The results for CIFAR10, CIFAR100, STL10, and ImageNet are in Table 1. Overall, IR, CMC, and MoCo all benefit from using more difficult negatives as shown by 2-5% absolute points of improvement across the four datasets. While we find different contrastive objectives to perform best in each dataset, the improvements from Ring are consistent: the Ring variant outperforms the base for every model and every dataset. We also include as a baseline Local Aggregation, or LA (Zhuang et al., 2019), a popular contrastive algorithm (see Sec. H) that implicitly uses hard negatives without annealing. We find our methods to outperform LA by up to 4% absolute.
Model Linear Eval.
IR 81.2 IRing 83.9 IRing (No Anneal) 81.4 IRing (` = 0) 82.1
(a) CIFAR10 Model Linear Eval.
IR 43.2 IRing 48.4 IRing (No Anneal) 41.3 IRing (` = 0) 47.3
(b) ImageNet
Transferring Features. Thus far we have only evaluated the learned representations on unseen examples from the training distribution. As the goal of unsu-
pervised learning is to capture general representations, we are also interested in their performance on new, unseen distributions. To gauge this, we use the same linear classification paradigm on a suite of image datasets from the “Meta Dataset” collection (Triantafillou et al., 2019) that have been used before in contrastive literature (Chen et al., 2020a). All representations were trained on CIFAR10. For each transfer dataset, we compute mean and variance from a training split to normalize input images, which we found important for generalization to new visual domains.
We find in Table 3 that the Ring models are competitive with the non-Ring analogues, with increases in transfer accuracies of 0.5 to 2% absolute. Most notable are the TrafficSign and VGGFlower datasets in which Ring models surpass others by a larger margin. We also observe that IRing largely outperforms LA. This suggests the features learned with more difficult negatives are not only useful for the training distribution but may also be transferrable to many visual datasets.
More Downstream Tasks. Object classification is a popular transfer task, but we want our learned representations to capture holistic knowledge about the contents of an image. We must thus evaluate performance on transfer tasks such as detection and segmentation that require different kinds of visual information. We study four additional downstream tasks: object detection on COCO (Lin et al., 2014) and Pascal VOC’07 (Everingham et al., 2010), instance segmentation on COCO, and keypoint detection on COCO. In all cases, we employ embeddings trained on ImageNet with a ResNet-18 encoder. We base these experiments after those found in He et al. (2019) with the same hyperparameters. However, we use a smaller backbone (ResNet-18 versus ResNet-50) and we freeze its parameters instead of finetuning them. We adapt code from Detectron2 (Wu et al., 2019).
We find IRing outperforms IR by around 2.3 points in COCO object detection, 2.5 points in COCO Instance Segmentation, 2.6 points in COCO keypoint detection, and 2.1 points in VOC object detection. Similarly, MoCoRing finds consistent improvements of 1-3 points over MoCo on the four tasks. Future work can investigate orthogonal directions of using larger encoders (e.g. ResNet-50) and finetuning ResNet parameters for these individual tasks.

heading: 6 RELATED WORK

text:
Several of the ideas in Ring Discrimination relate to existing work. Below, we explore these connections, and at the same time, place our work in a fast-paced and growing field.
Hard negative mining. While it has not been deeply explored in modern contrastive learning, negative mining has a rich line of research in the metric learning community. Deep metric learning utilizes triplet objectives of the form Ltriplet = d(g✓(xi), g✓(x+)) d(g✓(xi), g✓(x )+↵) where d is a distance function (e.g. L2 distance), x+ and x are a positive and negative example, respectively, relative to xi, the current instance, and ↵ 2 R+ is a margin. In this context, several approaches pick
semi-hard negatives: Schroff et al. (2015) treats the furthest (in L2 distance) example in the same minibatch as xi as its negative, whereas Oh Song et al. (2016) weight each example in the minibatch by its distance to g✓(xi), thereby being a continuous version of Schroff et al. (2015). More sophisticated negative sampling strategies developed over time. In Wu et al. (2017), the authors pick negatives from a fixed normal distribution that is shown to approximate L2 normalized embeddings in high dimensions. The authors show that weighting by this distribution samples more diverse negatives. Similarly, HDC (Yuan et al., 2017) simulataneously optimizes a triplet loss using many levels of “hardness” in negatives, again improving the diversity. Although triplet objectives paved the way for modern NCE-based objectives, the focus on negative mining has largely been overlooked. Ring Discrimination, being inspired by the deep metric learning literature, reminds that negative sampling is still an effective way of learning stronger representations in the new NCE framework. As such, an important contribution was to do so while retaining the theoretical properties of NCE, namely in relation to mutual information. This, to the best of our knowledge, is novel as negative mining in metric learning literature was not characterized in terms of information theory.
That being said, there are some cases of negative mining in contrastive literature. In CPC (Oord et al., 2018), the authors explore using negatives from the same speaker versus from mixed speakers in audio applications, the former of which can be interpreted as being more difficult. A recent paper, InterCLR (Xie et al., 2020), also finds that using “semi-hard negatives” is beneficial to contrastive learning whereas negatives that are too difficult or too easy produce worse representations. Where InterCLR uses a margin-based approach to sample negatives, we explore a wider family of negative distributions and show analysis that annealing offers a simple and easy solution to choosing between easy and hard negatives. Further, as InterCLR’s negative sampling procedure is a special case of CNCE, we provide theory grounding these approaches in information theory. Finally, a separate line of work in contrastive learning explores using neighboring examples (in embedding space) as “positive” views of the instance (Zhuang et al., 2019; Xie et al., 2020; Asano et al., 2019; Caron et al., 2020; Li et al., 2020). That is, finding a set {xj} such that we consider xj = t(xi) for the current instance xi. While this does not deal with negatives explicitly, it shares similarities to our approach by employing other examples in the contrastive objective to learn better representations. In the Appendix, we discuss how one of these algorithms, LA (Zhuang et al., 2019), implicitly uses hard negatives and expand the Ring family with ideas inspired by it.
Contrastive learning. We focused primarily on comparing Ring Discrimination to three recent and highly performing contrastive algorithms, but the field contains much more. The basic idea of learning representations to be invariant under a family of transformations is an old one, having been explored with self-organizing maps (Becker & Hinton, 1992) and dimensionality reduction (Hadsell et al., 2006). Before IR, the idea of instance discrimination was studied (Dosovitskiy et al., 2014; Wang & Gupta, 2015) among many pretext objectives such as position prediction (Doersch et al., 2015), color prediction (Zhang et al., 2016), multi-task objectives (Doersch & Zisserman, 2017), rotation prediction (Gidaris et al., 2018; Chen et al., 2019), and many other “pretext” objectives (Pathak et al., 2017). As we have mentioned, one of the primary challenges to instance discrimination is making such a large softmax objective tractable. Moving from a parametric (Dosovitskiy et al., 2014) to a nonparametric softmax reduced issues with vanishing gradients, shifting the challenge to efficient negative sampling. The memory bank approach (Wu et al., 2018) is a simple and memory-efficient solution, quickly being adopted by the research community (Zhuang et al., 2019; Tian et al., 2019; He et al., 2019; Chen et al., 2020b; Misra & Maaten, 2020). With enough computational resources, it is now also possible to reuse examples in a large minibatch and negatives of one another (Ye et al., 2019; Ji et al., 2019; Chen et al., 2020a). In our work, we focus on hard negative mining in the context of a memory bank or queue due to its computational efficiency. However, the same principles should be applicable to batch-based methods (e.g. SimCLR): assuming a large enough batch size, for each example, we only use a subset of the minibatch as negatives as in Ring. Finally, more recent work (Grill et al., 2020) removes negatives altogether, which is speculated to implicitly use negative samples via batch normalization (Ioffe & Szegedy, 2015); we leave a more thorough understanding of negatives in this setting to future work.

heading: 7 DISCUSSION

text:
Computational cost of Ring. To measure the cost of CNCE, we compare the cost an epoch of training MoCo/IR versus MoCoRing/IRing on four image datasets. Table 5a reports the average
cost over 200 epochs. We observe that Ring models cost no more than 1.5 times the cost of standard contrastive algorithms, amounting to a difference of 3 to 7 minutes in ImageNet and 10 to 60 seconds in three other datasets per epoch. In the context of deep learning, we do not find the cost increases to be substantial. In particular, since (1) the memory structure in IR and MoCo allow us to store and reuse embeddings and (2) gradients are not propagated through the memory structure, the additional compute of Ring amounts to one matrix multiplication, which is cheap on modern hardware. We used a single Titan X GPU with 8 CPU workers, and PyTorch Lightning (Falcon et al., 2019).
Comparison with the state-of-the-art. Unlike the experiments in Sec. 5, we now choose the optimal hyperparameters for MoCo-v2 (Chen et al., 2020b) separately for CIFAR10, CIFAR100, and STL10. Table 5b compares MoCo-v2 and its CNCE equivalent, MoCoRing-v2 using linear evaluation. We observe comparable improvements as found in Table 1 even with optimal hyperparameters. Notably, the gains generalize to ResNet-50 encoders. Refer to Sec. F for hyperparameter choices.
Generalization to other modalities. Thus far, we have focused on visual representation learning, although the same ideas apply to other domains. To exemplify the generality of CNCE, we apply MoCoRing to learning speech representations. Table 5c reports linear evaluation on six transfer datasets, ranging from predicting speaker identity to speech recognition to intent prediction. We find significant gains of 1 to 4 percent over 4 datasets and 6 transfer tasks with an average of 2.2 absolute percentage points. See Sec. E for experimental details.
Batch-based negative sampling. In Ring, we assumed to have a memory structure that stores embeddings, which led to an efficient procedure of mining semi-hard negatives. However, another flavor of contrastive algorithms removes the memory structure entirely, using the examples in the minibatch as negatives of one another. Here, we motivate a possible extension of Ring to SimCLR, and leave more careful study to future work. In SimCLR, we are given a minibatch M of examples. To sample hard negatives, as before, pick ` and u as lower and upper percentiles. For every example xi in the minibatch, only consider the subset of the minibatch {x : x ✓ M, exp{g✓(t(xi))T g✓(t0(x))} in the `-th and u-th percentiles in M} as negative examples for xi. This can be efficiently implemented as a matrix operation using an element-wise mask. Thus, we ignore gradient signal for examples too far or too close to xi in representation. As before, we anneal u from 100 to 10 and set ` = 1. Table 5d report consistent but moderate gains over SimCLR, showing promise but room for improvement in future research.

heading: 8 CONCLUDING REMARKS

text: To conclude, we presented a family of mutual information estimators that approximate the partition function using samples from a class of conditional distributions. We proved several theoretical statements about this family, showing a bound on mutual information and a tradeoff between bias and variance. Then, we applied these estimators as objectives in contrastive representation learning. In doing so, we found that our representations outperform existing approaches consistently across a spectrum of contrastive objectives, data distributions, and transfer tasks. Overall, we hope our work to encourage more exploration of negative sampling in the recent growth of contrastive learning.

heading: ACKNOWLEDGMENTS

text: This research was supported by the Office of Naval Research grant ONR MURI N00014-16-1-2007. MW is supported by the Stanford Interdisciplinary Graduate Fellowship as the Karr Family Fellow.


summaries: This work introduces CAFE, a novel training algorithm to leak training data in a federated learning setup. Extending from "deep leakage from gradient" fake images are optimised with respect to the difference observed from the client gradients (i.e. with the real images) and the one observed with the current version of the fake image. However, DLG does not work when the mini-batch size increases due to a messy gradient representation. In this work, the authors propose to keep track of the batch index. Indeed, it may happen that the server decides of the batch index corresponding to the training data that will be used by the client during the local training. Within such conditions, a malicious server can easily store fake images corresponding to specific indices and therefore optimise correctly each fake images w.r.t the corresponding real image.

summaries: This paper studies the data leakage issue in the federated learning. More precisely, when the servers have access to model parameters and gradients. It can recover the input data via gradient matching, and the authors claim that their method performs well even with large training batch sizes, e.g. over 40. Finally, the author also studies the possibility of attacking during learning, where they suggest that multiple updates of fake data helps. However, their contribution seems incremental, gradient matching is used in previous literature [zhu et al 2019], and their main modification is extra two regularization terms: total variation and internal representation regularization, and a data index alignment technique (whose exact meaning is unclear in the paper).

summaries: The submission considers the problem of reconstructing private data from gradients in a Federated Learning system, which has been recently shown to a threat in distributed learning systems. Two types of federated learning systems are considered. Vertical federated learning (VFL) refers to the case where different agents hold different features of the same data points while  Horizontal federated learning (HFL) refers to the case where different agents how all the features of different subsets of the data.

abstractText: Private training data can be leaked through the gradient sharing mechanism deployed in machine learning systems, such as federated learning (FL). Increasing batch size is often viewed as a promising defense strategy against data leakage. In this paper, we revisit this defense premise and propose an advanced data leakage attack to efficiently recover batch data from the shared aggregated gradients. We name our proposed method as catastrophic data leakage in federated learning (CAFE). Comparing to existing data leakage attacks, CAFE demonstrates the ability to perform large-batch data leakage attack with high data recovery quality. Experimental results on vertical and horizontal FL settings have validated the effectiveness of CAFE in recovering private data from the shared aggregated gradients. Our results suggest that data participated in FL, especially the vertical case, have a high risk of being leaked from the training gradients. Our analysis implies unprecedented and practical data leakage risks in those learning settings.

authors:
Arjun Nitin Bhagoji
Supriyo Chakraborty
Prateek Mittal
Seraphin Calo

title: Analyzing federated learning through an adversarial lens

venue: In International Conference on Machine Learning,

authors:
Tianyi Chen
Xiao Jin
Yuejiao Sun
Wotao Yin

title: VAFL: a method of vertical asynchronous federated learning

venue: arXiv preprint:2007.06081,

authors:
K. Cheng
T. Fan
Yilun Jin
Yang Liu
Tianjian Chen
Qiang Yang

title: Secureboost: A lossless federated learning

venue: framework. arXiv,

authors:
Trishul Chilimbi
Yutaka Suzue
Johnson Apacible
Karthik Kalyanaraman

title: Project adam: Building an efficient and scalable deep learning training system

venue: In 11th USENIX Symposium on Operating Systems Design and Implementation (OSDI

authors:
Matt Fredrikson
Somesh Jha
Thomas Ristenpart

title: Model inversion attacks that exploit confidence information and basic countermeasures

venue: In Proceedings of the 22nd ACM SIGSAC Conference on Computer and Communications Security,

authors:
Jonas Geiping
Hartmut Bauermeister
Hannah Dröge
Michael Moeller

title: Inverting gradients – how easy is it to break privacy in federated learning

authors:
Briland Hitaj
Giuseppe Ateniese
Fernando Pérez-Cruz

title: Deep models under the GAN: information leakage from collaborative deep

venue: learning. arXiv,

authors:
Forrest N. Iandola
Khalid Ashraf
Matthew W. Moskewicz
Kurt Keutzer

title: Firecaffe: near-linear acceleration of deep neural network training on compute

venue: clusters. arXiv,

authors:
Peter Kairouz
H Brendan McMahan
Brendan Avent
Aurélien Bellet
Mehdi Bennis
Arjun Nitin Bhagoji
Keith Bonawitz
Zachary Charles
Graham Cormode
Rachel Cummings

title: Advances and open problems in federated learning

venue: arXiv preprint:1912.04977,

authors:
Jakub Konečnỳ
H Brendan McMahan
Daniel Ramage
Peter Richtárik

title: Federated optimization: Distributed machine learning for on-device intelligence

venue: arXiv preprint:1610.02527,

title: Scaling distributed machine learning with the parameter server

venue: In Proceedings of the 11th USENIX Conference on Operating Systems Design and Implementation,

authors:
H. McMahan
Eider Moore
D. Ramage
S. Hampson
Blaise Agüera y Arcas

title: Communicationefficient learning of deep networks from decentralized data

authors:
Luca Melis
Congzheng Song
Emiliano De Cristofaro
Vitaly Shmatikov

title: Inference attacks against collaborative learning

venue: In Proceedings of the 35th Annual Computer Security Applications Conference,

authors:
Reza Shokri
Vitaly Shmatikov

title: Privacy-preserving deep learning

authors:
Yijue Wang
Jieren Deng
Dan Guo
Chenghong Wang
Xianrui Meng
Hang Liu
Caiwen Ding
Sanguthevar Rajasekaran

title: Sapag: A self-adaptive privacy attack from gradients

authors:
Chulin Xie
Keli Huang
Pin-Yu Chen
Bo Li

title: DBA: Distributed backdoor attacks against federated learning

venue: In International Conference on Learning Representations,

authors:
Qiang Yang
Yang Liu
Tianjian Chen
Yongxin Tong

title: Federated machine learning: Concept and applications

venue: ACM Trans. Intell. Syst. Technol.,

authors:
Bo Zhao
Konda Reddy Mopuri
Hakan Bilen

title: idlg: Improved deep leakage from gradients

authors:
Ligeng Zhu
Zhijian Liu
Song Han

title: Deep leakage from gradients

venue: In Advances in Neural Information Processing Systems

heading: 1 INTRODUCTION

text:
Federated learning (FL) (Chilimbi et al., 2014; Shokri & Shmatikov, 2015) is an emerging machine learning framework where a central server and multiple workers collaboratively train a machine learning model. Most of existing FL methods consider the setting where each worker has data of a different set of subjects but their data share many common features. This setting is also referred to data partitioned or horizontal FL (HFL). Unlike the HFL setting, in many learning scenarios, multiple workers handle data about the same set of subjects, but each has a different set of features. This case arises in financial and healthcare applications (Chen et al., 2020). In these examples, data owners (e.g., financial institutions and hospitals) have different records of those users in their joint user base, so, by combining their features, they can establish a more accurate model. We refer to this setting as feature-partitioned or vertical FL (VFL).
Compared with existing distributed learning paradigms, FL raises new challenges including the heterogeneity of data and the privacy of data (McMahan et al., 2017). To protect data privacy, only model parameters and the change of parameters (e.g., gradients) are exchanged between server and workers (Li, 2014; Iandola et al., 2015). Recent works have studied how a malicious worker can embed backdoors or replace the global model in FL (Bagdasaryan et al., 2018; Bhagoji et al., 2019; Xie et al., 2020). As exchanging gradients is often viewed as privacy-preserving protocols, little attention has been paid to information leakage from public shared gradients and batch identities.
In this context, inferring private user data from the gradients has received growing interests (Fredrikson et al., 2015; Hitaj et al., 2017; Melis et al., 2018). A popular method that was termed deep leakage from gradients (DLG) has been developed in (Zhu et al., 2019) that infers training data in an efficient way without using any generative models or prior information. However, DLG lacks generalizability on model architecture and weight distribution initialization (Geiping et al., 2020). In Zhao et al. (2020), an analytical approach has been developed to extract accurate labels from the gradients. Wang et al. (2020) proposed a novel gradient difference as a distance measure to improve recovery accuracy. However, all of them cannot scale up to the large-batch data leakage setting.
The contributions of this paper are summarized in the following.
1) We develop an advanced data leakage attack that we term CAFE to overcome the limitation of current data leakage attacks on FL. CAFE is able to recover large-scale data both in VFL and HFL.
2) Our large-batch data recovery is based on the novel use of data index alignment and internal representation alignment in FL, which can significantly improve the recovery performance.
3) The effectiveness and practical risk induced from our data leakage algorithm is justified in the dynamic FL training setting when all parameters in the model are updated every iteration.

heading: 2 PRELIMINARY

text:
FL can be categorized into horizontal and vertical FL settings (Kairouz et al., 2019). In this section, we provide necessary background of FL in this section.
Horizontal FL. In HFL, data are distributed among local workers holding the same feature space. Suppose that there are M workers participating in the FL process and the number of samples in the dataset X is N . The dataset is denoted as X := [X1, . . . ,Xm, . . . ,XM ]T , where Xm ∈ RNm×p is the local data partitioned to worker m, and p is the dimension of data feature space, Nm is the number of data samples partitioned to local worker m, and ∑M m=1Nm = N . Since all local data share the same feature space, each local worker computes the gradients independently and uploads them to the server. The server receives all gradients from each local worker and uses gradient aggregation methods such as FedAvg (Konečnỳ et al., 2016). Let the parameters of the model as θ and the loss function as L. Then the objective function of HFL can be defined as:
min θ
1
N M∑ m=1 L(θ;Xm) with L(θ;Xm) := ∑ n∈Nm L(θ;xn) (1)
Vertical FL. Different from HFL, in VFL, each local worker m is associated with a unique set of features. Each data sample xn in dataset X can be written as
xn = [x T n1, . . . ,x T nm, . . . ,x T nM ] T (2) where xnm ∈ Rpm is the data partitioned to worker m and pm is the data dimension in local worker m. The label space {yn}Nn=1 can be regarded as a special feature and is partitioned to the server or a certain local worker. Similar to (1), the objective function of VFL can be written as:
min θ
1
N N∑ n=1 L(θ;xn1; . . . ;xnM ) (3)

heading: 3 CATASTROPHIC DATA LEAKAGE FROM BATCH GRADIENTS

text: To realize large-scale data recovery from aggregated gradients, we propose our algorithm named as CAFE: Catastrophic dAta leakage in Federated lEarning. While CAFE can be applied to any type of data, without loss of generality, we use image datasets throughout the paper.

heading: 3.1 WHY LARGE-BATCH DATA LEAKAGE ATTACK IS DIFFICULT?

text:
We start by providing some intuition on the difficulty of performing large-batch data leakage from aggregated gradients based on the formulation of DLG (Zhu et al., 2019). Assume thatN images are selected as the input for a certain learning iteration. We define the data batch as X = {xn, yn|xn ∈ RH×W×C , n = 1, 2, . . . , N}, where H,W,C represents the height, the width and the channel number of each image. Likewise, the batched ‘recovered data’ is denoted by X̂ = {x̂n, ŷn|x̂n ∈ RH×W×C , n = 1, 2, . . . , N}, which have the same dimension as X . Then the objective function is
X̂ ∗ = argmin X̂ ∥∥∥∥∥ 1N N∑
n=1
∇θL(θ,xn, yn)− 1
N N∑ n=1 ∇θL(θ, x̂n, ŷn) ∥∥∥∥∥ 2
(4)
Note that in (4), the dimensions of the aggregated gradients is fixed. However, as the N increases, the dimension of X̂ and X rise. When N is sufficiently large, it will be more challenging to find the “right” solution X̂ of (4) corresponding to the ground-truth dataset X . On the other hand, CAFE addresses this large-batch issue by data index alignment for batch data recovery, which can effectively exclude undesired solutions. We discuss a specific example in Appendix A.
As a motivating example, Figure 1 compares our proposed attack with DLG on a batch of 40 images. The recovery quality of DLG is far from satisfactory, while CAFE can successfully recover all images in the batch. It is worth noting that because DLG is not effective on large-batch recovery, it is suggested in Zhu et al. (2019) that increasing batch size could be a promising defense. However, the successful recovery of CAFE shows that such defense premise gives a false sense of security in data leakage and the current FL is at risk, as large-batch data recovery can be accomplished.

heading: 3.2 CAFE IN VFL

text:
In VFL, the server sends public key to local workers and decides the data index in each iteration of training and evaluation (Yang et al., 2019; Cheng et al., 2019). During the training process, local workers exchange their intermediate results with others to compute gradients and upload them. Therefore, the server has the access to both the model parameters and their gradients. Notably, CAFE can be readily applied to existing VFL protocols where the batch data index is assigned.
Figure 2 gives an overview of CAFE in the VFL setting. The blue part represents a normal VFL paradigm and the red part represents the CAFE attack. Since data are vertically partitioned among different workers, data index alignment turns out to be an inevitable step in the vertical training process, which provides the server (the attacker) an opportunity to control the selected batch data index. Suppose that there are M workers participating FL and the batch size is N . The aggregated gradients can be denoted by
∇θL(θ,X t) = 1
Nb Nb∑ n=1 ∇θL(θ,X tn) with X tn = [xtn1,xtn2, . . . ,xtnM ]. (5)
Algorithm 1 CAFE in VFL ( regular VFL protocol and CAFE protocol )
1: Initialize model parameters θ and generate fake data X̂ 2: for t = 1, 2, . . . , T do 3: Server broadcasts the global model to all local workers (a total of M workers)
4: for m = 1, 2, . . . ,M do 5: Worker m takes real batch data 6: Worker m computes the intermediate results and exchanges them with other workers 7: Worker m uses the exchanged intermediate results to compute local aggregated gradients 8: Worker m uploads real local aggregated gradients to the server. 9: end for
10: Server computes real global aggregated gradients∇θL(θ,X t)
11: Server computes the fake global aggregated gradients∇θL(θ, X̂ t) 12: Server computes CAFE loss: D(X t; X̂ t) and∇X̂ tD(X
t; X̂ t) 13: Server updates the batch data X̂ t with∇X̂ tD(X t; X̂ t)
14: Server updates the model parameters θ with∇θL(θ,X t) 15: end for
A benign server will perform legitimate computations designed by FL protocol. However, as shown in Figure 2, a curious server can provide the same legitimate computation as a benign server while simultaneously perform data recovery in a stealthy manner. The server symmetrically generates fake images corresponding to the real ones. Once a batch of original data is selected, the server takes the corresponding fake batch and obtains the fake gradients as
∇θL(θ, X̂ t) = 1
Nb Nb∑ n=1 ∇θL(θ, X̂ tn) with X̂ tn = [x̂tn1, x̂tn2, . . . , x̂tnM ]. (6)
Algorithm 1 gives a pseudo code that implements our CAFE attack in VFL cases. The key part in our algorithm is aligning the real data batch indices with the fake ones. We define the squared `2-norm of the difference between the real and fake aggregated gradients in (7). Since the server has the access to the model parameters, the attacker is able to compute the gradient of fake data from the loss in (7) and optimize the fake data for the purpose of recovering real data.
D(X t; X̂ t) = ∥∥∇θL(θ,X t)−∇θL(θ, X̂ t)∥∥2. (7)

heading: 3.3 AUXILIARY REGULARIZERS

text:
In addition to the gradient matching loss in (7), we further introduce two regularization terms – internal representation regularization and total variance (TV) norm. Motivated by (Geiping et al., 2020), the input vectors of the first fully connected layer can be directly derived from the gradients, we define the real/fake inputs of the first fully connected layer at the tth iteration as Zt/Ẑt ∈ RN×P and we use `2 norm of their difference as what we call internal representation regularization.
To promote the smoothness of the fake images, we assume the TV norm of the real images as a constant, ξ, and compare it with the TV norm of the fake ones, TV(X̂ ). For each image x ∈ RH×W×C in data batch X t, its TV norm is denoted by TV(x) = ∑ c ∑ h,w [ |xh+1,w,c − xh,w,c|+
|xh,w+1,c − xh,w,c| ] . As the result, the loss at the tth iteration D(X t, X̂ t) can be rewritten as:
D(X t; X̂ t) = ∥∥∇θL(θ,X t)−∇θL(θ, X̂ t)∥∥2 + βTV (X̂ ) · 1{TV (X̂ )−ξ≥0} + γ∥∥Zt − Ẑt∥∥2F , (8)
where β and γ are coefficients and 1{TV (X̂ )−ξ≥0} is the indicator function. We will provide an ablation study in Section 4.5 to demonstrate the utility of these regularizers.
(Epoch: 50, 100, 200, 300, 450, 600, Original data)

heading: 3.4 CAFE IN HFL

text:
Similarly, we can apply our CAFE algorithm to HFL as well. Let X tm denote the original batch data taken by local worker m at the tth iteration. The gradients of the parameters at the tth iteration is
∇θL(θ,X t) = 1
M M∑ m=1 ∇θL(θ,X tm) , X t = {X t1 ,X t2 , . . . ,X tm, . . . ,X tM}. (9)
Symmetrically, we define the batch fake data and fake aggregated gradients as
∇θL(θ, X̂ t) = 1
M M∑ m=1 ∇θL(θ, X̂ tm) , X̂ t = {X̂ t1 , X̂ t2 , . . . , X̂ tm, . . . , X̂ tM}. (10)
Due to space limitation, we will provide the CAFE algorithm for HFL in Appendix B.

heading: 4 PERFORMANCE EVALUATION

heading: 4.1 EXPERIMENT SETUPS AND DATASETS

text:
We conduct experiments on CIFAR-10, CIFAR-100 and Linnaeus 5 datasets in both HFL and VFL settings. All the fake data are initialized uniformly and optimized by the normalized gradient descent method. Our algorithm can recover all the data participating in FL with a relative large batch size (more than 40). Scaling up to our hardware limits, CAFE can leak as many as 2000 images in the VFL setting including 4 workers.
Evaluation metrics. To measure the data leakage performance, we introduce peak signal-to-noise ratio (PSNR) value with mean squared error (MSE) defined in (11) and (12). Higher PSNR value of leaked data represents better performance of data recovery.
MSEc(x, x̂) = 1
HW H∑ i=1 W∑ j=1 [xijc − x̂ijc]2 (11)
PSNR(x, x̂) = 1
C C∑ c=1 [ 20 log10(max i,j xijc)− 10 log10(MSEc(x, x̂)) ] . (12)
Baseline methods for comparison. We compare CAFE with three other baselines, (i) DLG (Zhu et al., 2019), (ii) DLG given labels (iDLG) (Zhao et al., 2020), and (iii) using cosine similarity to compare the real and fake gradients (Geiping et al., 2020). We implement the original DLG and our CAFE under the same model and optimization methods. We run the DLG on 50 single images respectively and compute the average iterations required to make the PSNR value of a single leaked image above 30. We also compute the expected iteration number per image leakage for our CAFE algorithm. Furthermore, we fix the batch size, and compare the PSNR value obtained by CAFE with that of DLG. We also test the impact of given labels on CAFE by using the techniques in (Zhao et al., 2020). Moreover, we compare the performance of CAFE under different loss functions: i) replacing the squared `2 norm term with the cosine similarity of two gradients (CAFE with cosine similarity) ii) loss proposed in (Geiping et al., 2020), which only contains the TV norm regularizer.

heading: 4.2 CAFE IN HFL SETTINGS

text:
In the HFL setting, we use a neural network consisting of 2 convolutional layers and 3 fully connected layers. The number of output channels of the convolutional layers are 64 and 128 respectively. The number of nodes of the first two fully connected layers are 512 and 256. The last layer is the softmax classification layer. We assume that 4 workers are involved in HFL and each of them holds a dataset including 100 images. The batch size of each worker in the training is 10, so there are 40 (10 × 4) images in total participating per iteration. For each experiment, we initialize the fake data using uniform distribution and optimize them for 800 epochs.
Figures 4a and 4b show the CAFE loss curves and the PSNR curves on the three datasets in HFL cases. In the loss ratio curve, we set the ratio of current CAFE loss and the initial CAFE loss L(θ,X t) L(θ,X 0) as label y. The PSNR values are always above 35 at the end of each CAFE attacking process, suggesting high data recovery quality (see Figure 1 as an example). Figure 3 shows the attacking process of CAFE on Linnaeus. Under CAFE, PSNR reaches 35 at the 450th epoch where the private training data are completely leaked visually.
Comparison with DLG baseline. In Table 1a, we set the batch ratio in CAFE as 0.1 and compare it with DLG under different batch sizes. Clearly, CAFE outperforms DLG thanks to our novel design of large-batch data leakage attack. As shown in Table 1b, DLG cannot obtain satisfactory results when the batch size increases to 40, while CAFE successfully recovers all the images. Due to similarity between iDLG and DLG, the results are in Appendix C.
Comparison with cosine similarity. Table 2a shows that the PSNR values are still above 30 if we use cosine similarity instead of `2 norm. The slight drop in PSNR value may result from scaling ambiguity in cosine similarity. There is a performance gap between the loss of CAFE and the loss in Geiping et al. (2020), which validates the importance of our proposed auxiliary regularizers.
Table 3: PSNR via Batch size
Batch size
PSNR Datasets CIFAR-10CIFAR-100Linnaeus
10 per worker 35.03 36.90 36.37 20 per worker 33.14 33.99 36.32 30 per worker 32.31 33.21 35.96 40 per worker 30.59 30.70 35.49
(a) HFL (4 workers, batch ratio = 0.1)
Batch size
PSNR Datasets CIFAR-10CIFAR-100Linnaeus
8 41.80 44.42 39.96 40 59.51 65.00 41.37 80 57.20 63.10 43.66 160 54.74 64.75 38.72 (b) VFL (4 workers, batch ratio = 0.2)
Table 4: PSNR via Batch ratio
Batch ratio
PSNR Datasets CIFAR-10
(HFL) Linnaeus CIFAR-10 (VFL)
0.1 34.10 35.38 48.78 0.05 34.49 32.92 55.46 0.02 37.96 35.66 48.45 0.01 35.39 36.56 46.46
10 1
10 2
10 3
10 4
Iteration
10
15
20
25
30
PS NR
10 −3
10 −2
10 −1
Tr ain
ing lo
ss
PSNR Training loss
Figure 5: PSNR and training loss curves

heading: 4.3 CAFE IN VFL SETTINGS

text:
Since DLG cannot be applied in VFL protocol, we test the performance of CAFE on various factors. We slice one image into 4 small pieces. Each worker holds one piece and the feature space dimension of each piece is 16 × 16 × 3. The model is composed of 2 parts. The first part consists of 2 convolutional layers and 3 fully connected layers for each worker. The second part only consists of the softmax layer. In the training process, the pieces are sent into the first part respectively and turn to vectors as intermediate results. Local workers then exchange their intermediate results, concatenate them and put them into the second part. We set the batch size as 40 in VFL. Figure 4c and 4d show the CAFE loss curves and the PSNR curves on the three datasets in VFL cases. The data recovery is even better than the results in HFL. The PSNR values of CIFAR-10 and CIFAR-100 rise higher than 40. Same as the part in HFL, we put comparison with iDLG in Appendix C.
Comparison with cosine similarity. From Table 2b, we can conclude that the PSNR values still keep close to the ones by using CAFE. Scaling ambiguity in cosine similarity may also cause the drop in PSNR value. The performance gap between the loss of CAFE and the loss in Geiping et al. (2020) is much larger than the one in VFL, which indicates the utility of our auxiliary regularizers.

heading: 4.4 ATTACKING WHILE FL

text: Previous works have shown that DLG performs better on an untrained model than a trained one (Geiping et al., 2020). We also implement CAFE in the ‘attacking while learning’ mode, in which the FL process is ongoing. When the network is training, the selected batch data and the parameters of the model change every iteration, which may cause the attack loss to diverge. To address this issue, for each real data batch, we compute the real gradients and optimize the corresponding fake data k times. We demonstrate on Linnaeus dataset, set k = 10 and stop CAFE after 1000 iterations (100 epochs). Figure 5 gives the curves of the training loss and the corresponding PSNR value. The PSNR value still can be raised to a relatively high value. It indicates that CAFE can be a practical data leakage attack in a dynamic training environment of FL.

heading: 4.5 ABLATION STUDY

text:
We test CAFE under different batch size, batch ratio, and with (without) auxiliary regularizers.
PSNR via Batch size. Table 3 shows that the PSNR values still keep above 30 when the batch size increases with fixed number of workers and batch ratio. The result implies that the increasing batch size has little influence on data leakage performance of CAFE.
PSNR via Batch ratio. In HFL, 4 workers participate in the learning setting and we fix the amount of data held by each worker as 500. In the VFL case, we implement CAFE on a total of 800 images. In Table 4, we change the batch ratio from 0.1 to 0.01 while keeping the trained epochs as 800. For both settings, the data leakage performance keeps at the same level.
Impact of auxiliary regularizers Table 6 in Appendix D demonstrates the impact of auxiliary regularizers. From Figure 6, adjusting the threshold ξ prevents images from being over blurred during the reconstruction process. TV norm can eliminate the noisy patterns on the recovered images and increase the PSNR. Images leaked without regularizing the Frobenius norm of the difference between the internal representations Z and Ẑ may lose some details and causes the drop of PSNR.

heading: 5 CONCLUSIONS

text: In this paper, we uncover the risk of catastrophic data leakage in federated learning (CAFE) through an algorithm that can perform large-batch data leakage with high data recovery quality. Extensive experimental results demonstrate that CAFE can recover large-scale private data from the shared aggregated gradients on both vertical and horizontal FL settings, overcoming the batch limitation problem in current data leakage attacks. Our advanced data leakage attack and its stealthy nature suggests practical data privacy concerns in FL and poses new challenges on future defenses.