Informative Sample-Aware Proxy for Deep Metric Learning
Aoyu Li

Ikuro Sato

Kohta Ishikawa

aoyuli@rio.gsic.titech.ac.jp
Tokyo Institute of Technology
Tokyo, Japanisato@c.titech.ac.jp
Tokyo Institute of Technology
Denso IT Laboratory
Tokyo, Japan

ishikawa.kohta@core.d-itlab.co.jp
Denso IT Laboratory
Tokyo, Japan

Rei Kawakami

Rio Yokota

reikawa@sc.e.titech.ac.jp
Tokyo Institute of Technology
Tokyo, Japanrioyokota@gsic.titech.ac.jp
Tokyo Institute of Technology
Tokyo, Japan

ABSTRACT
Among various supervised deep metric learning methods proxybased approaches have achieved high retrieval accuracies. Proxies, which are class-representative points in an embedding space,receive updates based on proxy-sample similarities in a similarmanner to sample representations. In existing methods, a relatively
small number of samples can produce large gradient magnitudes(i.e., hard samples), and a relatively large number of samples can produce small gradient magnitudes (i.e., easy samples); these can play amajor part in updates. Assuming that acquiring too much sensitivity
to such extreme sets of samples would deteriorate the generalizability of a method, we propose a novel proxy-based method called
Informative Sample-Aware Proxy (Proxy-ISA), which directly modifies a gradient weighting factor for each sample using a scheduled
threshold function, so that the model is more sensitive to the informative samples. Extensive experiments on the CUB-200-2011,
Cars-196, Stanford Online Products and In-shop Clothes Retrieval
datasets demonstrate the superiority of Proxy-ISA compared withthe state-of-the-art methods.

CCS CONCEPTS• Computing methodologies → Image representations.

KEYWORDS
metric learning, adaptive sampling, robust estimation
ACM Reference Format:
Aoyu Li, Ikuro Sato, Kohta Ishikawa, Rei Kawakami, and Rio Yokota. 2022.
Informative Sample-Aware Proxy for Deep Metric Learning. In ACM Multimedia Asia (MMAsia ’22), December 13–16, 2022, Tokyo, Japan. ACM, New
York, NY, USA, 11 pages. https://doi.org/10.1145/3551626.3564942

Permission to make digital or hard copies of all or part of this work for personal orclassroom use is granted without fee provided that copies are not made or distributedfor profit or commercial advantage and that copies bear this notice and the full citationon the first page. Copyrights for components of this work owned by others than ACM
must be honored. Abstracting with credit is permitted. To copy otherwise, or republish,
to post on servers or to redistribute to lists, requires prior specific permission and/or afee. Request permissions from permissions@acm.org.
MMAsia ’22, December 13–16, 2022, Tokyo, Japan© 2022 Association for Computing Machinery.
ACM ISBN 978-1-4503-9478-9/22/12. . . $15.00
https://doi.org/10.1145/3551626.3564942

Proxies
Data embeddings

Traditional methods
Outliers havelarge impact

Typical clusters

After learning, overlap remains
Ours
Other clusters

Informative region

Too easy(down-weighted)
Well separated

Embedding space

Too hard (down-weighted)

Figure 1: Overview of typical proxy-based DML and the proposed approach in this paper. Traditional methods can resultin a few hard samples pulling the proxy, exacerbating theoverlapping problem. The Proxy-ISA proposed in this paper
aims to address this limitation by identifying such samples
and reducing their contribution to the proxy.

1

INTRODUCTION

Learning semantic similarities between a pair of visual data is an
important objective in computer vision tasks. Metric learning aims
to learn an embedding space such that samples from the same
category are close to each other and otherwise far apart. In deep
metric learning (DML), learnable encoders are utilized to produce
representations in an embedding space in which semantic distances
between samples can be measured. DML has broad computer-visionapplications such as image retrieval [30, 32], face recognition [40],person re-identification [42] and few-shot learning [4, 16, 43].
Throughout the past studies, DML methods can be categorized
into two families: pair-based and proxy-based. Pair-based methods
consider the distance between a pair of data embeddings, while
proxy-based methods consider the distance between a data embedding and a class-representative point in the embedding space.
A typical example of pair-based losses is contrastive loss [6],which aims to pull close or push apart a pair of data embeddings
according to the identicality of the class labels. Other pair-based
losses, such as triplet loss [13] and N-pair loss [32], extend this idea
to more than two samples. Due to its combinatorial nature, a naive
implementation of a pair-based method suffers from polynomial
growth of complexity with respect to the number of training samples. Additionally, training with pairs from a subset (mini-batch)lacks global information of the embedding space. In contrast, proxybased methods [8, 26, 29, 36] assign one or more trainable referenceMMAsia ’22, December 13–16, 2022, Tokyo, Japan

points called proxies to each class, and reduce the training complexity by considering only the distance from the data embeddings
to proxies. During training, proxies attract data embeddings of thesame class (i.e., positives) and push away those of different classes(i.e., negatives). Meanwhile, proxies are kept in memory and thus
serve as a source of global information.
In existing methods, a small number of hard samples, such as
positives that are far apart and negatives that are close, produce
large gradients, and thus will have more impact on learning. A large
number of easy samples can also dominate the gradient because of
their large population size. An intuitive strategy is to select only
the hard samples [12], but this has been observed to produce noisy
gradients and converge to bad local optima [41], and its impact on
proxies remains to be discussed. In pair-based methods, mining
strategies, such as semi-hard negative mining [31], have been proposed to select and learn more important negatives that are closer tothe anchor but still farther away than the corresponding positives.
However, the hardness is usually manually defined by a numericalthreshold, is fixed during learning, and is shared among different
classes. As illustrated in Fig. 1, increasing the gradient weights ofhard proxy-data pairs may also disrupt the ideal distribution of theclusters.
To address the limitations of existing proxy-based methods andto effectively incorporate the idea of sample importance into proxybased DML, we propose the Informative Sample-Aware Proxy (ProxyISA) that directly controls gradient weights non-uniformly according to the temporal learning states, which are defined by how thesamples with different hardness distribute in the embedding space.
Our idea is motivated by empirical findings in active learning [5],where informative samples dynamically change along learning. In
Proxy-ISA, as outlined in Fig. 1, each proxy is assigned a temporal similarity range, determined by the space already learned (tooeasy), informative region, and the space contains outliers (too hard);
weights for positive and negative pairs are assigned separately. We
apply a memory queue to estimate each class hardness. Unlike
memory-based DML [20, 39], where past information is directly
used to update weights, our use of memory allows us to estimate
the space occupied by easy samples around the proxies and to judge
whether the sample of interest is informative.
Our main contributions are summarized as follows:• We propose a novel method for proxy-based DML, which performs class-dependent dynamic weighting for each sample
based on the learned intra- and inter-class relations.
• We apply the concept of a “volume" of the class-related region[7] to DML and demonstrate empirically that focusing on
informative samples based on the estimation of the classhardness improves generalization.
• Proxy-ISA achieves state-of-the-art performance on four
public benchmarks of DML in both standard and Metric
Learning Reality Check (MLRC) [27] evaluation settings.

2

RELATED WORK

Pair Mining / Pair Weighting in DML Non-uniform sampling[1, 2, 15, 17] and weighting [5, 22, 23] methods have been shown to
improve the performance of deep neural networks and have been
widely applied to various tasks. In pair-based DML, many samplingLi, et al.

strategies [9, 41] and a general pair weighting (GPW) framework[37] have been developed.
Hard sample mining is the most widely discussed sampling strategy for pair-based DML. For example, Wu et al.[41] showed thatpair-wise distance distribution in the embedding space is biased,
and proposed distance weighted sampling to sample negative pairs
uniformly according to the pair-wise distance within the mini-batch.
Additionally, the deep sampler network (DSN) [9] was proposed
to learn an adaptive sampling distribution based on the prior relations between training samples in the feature embedding network.
However, the architecture of DSN relies on the design of the loss
function, and online sampling increases the training cost. Wanget al.[37] proposed the general pair weighting (GPW) framework,
which casts the sampling problem of deep metric learning into a
unified view of pair weighting through gradient analysis. They
proposed the Multi-Similarity (MS) loss to generate non-uniform
pair weights based on various pair relations.
Since hard mining is easily influenced by outliers that lead thelearned model to a bad local optima [31], methods such as Density
Aware DML [10] and Class-Aware Attention [38] were proposed to
identify outliers and reduce their impact on learning. In HardnessAware DML [44], the hardness threshold was scheduled by a global
loss to perform adaptive mining. Although hardness threshold andweighting score have been applied in existing methods, the proposed thresholds and weights were not adaptive to class hardness,
which can vary during training. Additionally, these methods provide
pair-wise information by exploiting data-to-data relations within
mini-batches, which results in the deficiency of global information;
thus, the corresponding learning signal is sub-optimal.
Proxy-Based Deep Metric Learning The use of proxy is raisedby Proxy-NCA [26], which combines the NCA loss [11] with aproxy. In its standard setting, one proxy is assigned to each class,and the raw data point is encouraged to be close to a positive
proxy and far from all negative proxies. Alternatively, Proxy-Anchor[18] regards each proxy as an anchor, and intra-class relations aretreated similarly to the MS loss [37]. More recent studies [29, 45]also consider assigning more proxies to each class to capture intraclass variance. For example, Qian et al.[29] extended the SoftMax
loss to DML with multiple class centers, and proposed SoftTriple
loss, which reflects the local geometry for each class. ProxyGML[45] applies the proxy in a graph structure manner, and multiple
proxies are selected to construct a subgraph to help raw data points
learn the neighbor structure. Although memory-based learning [20]
was introduced to proxy-based methods for better generalization,
existing methods do not consider the learning stability of the proxyitself, and still do not simultaneously address both intra- and interclass relations in the loss function.
Rather than regarding the proxies as class representatives orgraph nodes, the proposed Proxy-ISA treats each proxy as thecenter of a class-related region (subspace), and the definition of all
the regions are estimated separately according to the proxies. As thelearning difficulty varies from class to class, the definition of regions
also varies even within the same iteration. In the proposed method,
the proxy-data pairs are treated non-uniformly and adaptively basedon the learned intra- and inter-class relations, resulting in better
handling of global information.

Informative Sample-Aware Proxy for Deep Metric Learning

3

MMAsia ’22, December 13–16, 2022, Tokyo, JapanPROPOSED APPROACH

In this section, we first revisit the GPW framework [37] to provide
a unified view of DML loss functions, and qualitatively discuss theimpact and problems of hard samples on the learning of the proxies.
We then propose our gradient weighting method for proxy-based
loss by introducing an estimation logic for hardness that adaptively
changes along learning to ameliorate the problems.

3.1(a) Proxy-Anchor@epoch30

The Gradient Weighting Mechanism

Let 𝒙 𝑖 ∈ R𝐷 be a real-value sample vector, and 𝑦𝑖 ∈ {1, 2, . . . , 𝐶} be
the corresponding label. Then the input matrix and the label vector
for 𝑚 training samples can be denoted as 𝑿 ∈ R𝑚×𝐷 and 𝒚 ∈ R𝑚 ,respectively. Let 𝒑𝑐 ∈ R𝑑 be the proxy for class 𝑐 (𝑐 = 1, 2, . . . , 𝐶).
We denote a deep neural network by 𝑓 (·; 𝜽 ) : R𝐷 → R𝑑 , where𝜽 denotes the corresponding parameters and 𝑑 is the embedding
dimension. Then the cosine similarity between a data embedding
vector and a proxy can be defined as S𝑖,𝑐 := ⟨𝑓 (𝒙 𝑖 ; 𝜽 ), 𝒑𝑐 ⟩, where⟨·, ·⟩ denotes the dot product. Similarly, the similarity matrix canbe denoted as 𝑺 ∈ R𝑚×𝐶 .
Given a proxy-based loss L (𝑺, 𝒚), the derivative w.r.t. 𝜽 at the𝑡-th iteration can be written as
𝑚 ∑︁
𝐶
∑︁
𝜕L (𝑺, 𝒚)
𝜕L (𝑺, 𝒚) 𝜕S𝑖,𝑐=
𝜕𝜽
𝜕S𝑖,𝑐 𝑡 𝜕𝜽 𝑡𝑡
𝑖=1 𝑐=1𝑚 ∑︁∑︁∑︁ 𝜕L 𝜕S𝑖,𝑐 ª
𝜕L 𝜕S𝑖,𝑐©
+=­®.
𝜕S𝑖,𝑐 𝑡 𝜕𝜽 𝑡 𝑐=𝑦 𝜕S𝑖,𝑐 𝑡 𝜕𝜽 𝑡
𝑖=1 «𝑐≠𝑦𝑖
𝑖
¬

(1)

𝜕L
𝜕S𝑖,𝑐 𝑡 in Eq. (1) is regarded as a constant scalar in the gradient w.r.t.

𝜽 . Since positive pairs are encouraged to be close and negative pairs
𝜕Lneed to be pushed away from each other, we assume 𝜕S
𝑡 ≥ 0
𝑖,𝑐

𝜕L
≤ 0 for positive pairs. Thus, Eq. (1)for negative pairs, and 𝜕S𝑖,𝑐 𝑡
can be transformed into a form of weighted sum:
𝑚 ∑︁
∑︁
∑︁
𝜕S𝑖,𝑐
𝜕S𝑖,𝑐 ª
𝜕L (𝑺, 𝒚)
©
𝑤𝑖,𝑐
=
−
𝑤𝑖,𝑐
­
®,
𝜕𝜽
𝜕𝜽
𝜕𝜽 𝑡
𝑡
𝑡
𝑐=𝑦𝑖
𝑖=1 «𝑐≠𝑦𝑖¬(2)

𝜕 L (𝑺,𝒚)where 𝑤𝑖,𝑐 = 𝜕S
. Eq. (2) suggests that the gradient signal
𝑖,𝑐𝑡
is actually controlled by 𝑤𝑖,𝑐 , namely, how the similarity metric isdefined in the DML loss function.

3.2

Impact of Gradient Weights on Proxies

Let 𝑷 ∈ R𝐶×𝑑 be the proxy set. The gradient w.r.t. 𝑷 can be obtainedby replacing 𝜽 in Eq. (2):
𝑚 ∑︁
∑︁
∑︁
𝜕S𝑖,𝑐
𝜕S𝑖,𝑐 ª
𝜕L (𝑺, 𝒚)
©
=
𝑤𝑖,𝑐
−
𝑤𝑖,𝑐
­
®.
𝜕𝑷
𝜕𝒑
𝜕𝒑𝑐 𝑡
𝑐 𝑡 𝑐=𝑦𝑖𝑡
𝑖=1 «𝑐≠𝑦𝑖¬(3)

Eq. (3) suggests that the learning of a proxy is also affected by 𝑤𝑖,𝑐 .
In pair-based methods, the effect of 𝑤𝑖,𝑐 is symmetrical since we
can treat either side of the pair as an anchor. However, in proxybased methods, larger gradient weights may result in an undesirable
proxy distribution, which is detrimental to the representation of
global information.

(b) Norm.SoftMax@epoch30

Figure 2: t-SNE [34] visualization of 512-dimensional embedding space for the Cars-196 dataset. (a) and (b) present theembedding space learned by Proxy-Anchor and normalized
SoftMax, respectively. The proxies of Proxy-Anchor, plottedwith navy blue stars, form a cluster at an early stage due tothe strong repulsive forces.
The first proxy-based loss combined with gradient weighting
was the Proxy-Anchor loss [18], which is formulated as follows:
∑︁
1 ∑︁
©
ª
log ­1 +𝑒 𝛼 (𝛿−S𝑖,𝑐 ) ®
+|𝑪 |𝑐 ∈𝑪 +« 𝑖:𝑦𝑖 =𝑐
¬
(4)
𝐶
∑︁
∑︁
1
©
𝛼 (𝛿+S𝑖,𝑐 ) ª𝑒log ­1 +
+
®,
𝐶 𝑐=1
𝑖:𝑦
≠𝑐
𝑖
«
¬
where 𝑪 + = {𝑐 |𝑐 ∈ 𝒚} denotes a set of class labels in a mini-batch,and 𝛼, 𝛿 are fixed hyper-parameters. By taking the derivative of
L𝑃𝐴 w.r.t. S𝑖,𝑐 , the gradient weights are given by
L𝑃𝐴 :=

1𝛼𝑒 𝛼 (𝛿−S𝑖,𝑐 ), 𝑦𝑖 = 𝑐,|𝑪 + | 1+ Í 𝑒 𝛼 (𝛿−S 𝑗,𝑐 )
𝑗 :𝑦 =𝑐𝑗(5)𝛼𝑒 𝛼 (𝛿+S𝑖,𝑐 )1𝑦𝑖 ≠ 𝑐.
Í𝛼 (𝛿+S 𝑗,𝑐 ) ,

𝐶 1+
𝑒


𝑗 :𝑦 𝑗 ≠𝑐From Eq. (5), it is clear that for a positive pair, 𝑤𝑖,𝑐 will be large
if the data embedding is far from its proxy (i.e. S𝑖,𝑐 is small), andwill be larger if it is farther than other positive pairs related to thesame proxy (i.e. S𝑖,𝑐 < ∀S 𝑗,𝑐 ). A similar approach is adopted forthe negative pairs, as illustrated in Fig. 1, where the thickness of
the arrows indicates the magnitude of the gradient weights. If a
positive pair contains an outlier, the proxy will be pulled heavily inthat direction.
We now analyze the optimization problem according to eachterm in the Proxy-Anchor loss.

𝑤𝑖,𝑐 =

Proposition 1
∑︁
∑︁
©
ª
log ­1 +𝑒 𝛼 (𝛿−S𝑖,𝑐 ) ® = max
𝛼P𝑐+ (𝑖)(𝛿 − S𝑖,𝑐 ) + 𝐻 (P𝑐+ ),+P
𝑐𝑖:𝑦𝑖 =𝑐« 𝑖:𝑦𝑖 =𝑐
¬
∑︁
∑︁
©
ª
log ­1 +𝑒 𝛼 (𝛿+S𝑖,𝑐 ) ® = max
𝛼P𝑐− (𝑖)(S𝑖,𝑐 + 𝛿) + 𝐻 (P𝑐− ),
P𝑐−
𝑖:𝑦
≠𝑐
𝑖:𝑦
≠𝑐
𝑖
𝑖
«
¬
(6)
where 𝐻 (·) denotes entropy for regularization, P𝑐+ and P𝑐− are theprobability distributions over the positives and negatives related to aÍproxy 𝒑𝑐 , respectively, and P𝑐+ (𝑖) ∈ {P𝑐+ |P𝑐+ (𝛿) + 𝑖:𝑦𝑖 =𝑐 P𝑐+ (𝑖) =MMAsia ’22, December 13–16, 2022, Tokyo, Japan
Volume oflearned subspace𝜂𝑐Li, et al.

(𝑐)𝑆𝑜𝑢𝑡𝑙𝑖𝑒𝑟
(𝑐)

(𝑐)
𝐸𝑛 𝛾𝑐

𝐸𝑛+𝑚 𝛾𝑐

Proxy

Proxy
(𝑐)

Learned volume
grows along training

𝑆𝑙𝑒𝑎𝑟𝑛𝑒𝑑

Figure 3: Two thresholds related to a proxy. S𝒐𝒖𝒕 𝒍 𝒊𝒆𝒓 : similarity threshold to detect outliers, i.e. data embeddings with(𝑐)
S𝑖,𝑐 < S𝑜𝑢𝑡𝑙𝑖𝑒𝑟 ; S𝒍𝒆𝒂𝒓 𝒏𝒆𝒅 : similarity threshold to detect overlapping between the learned subspace and the newly sampled(𝑐)data. Samples that satisfy S𝑖,𝑐 > S𝑙𝑒𝑎𝑟𝑛𝑒𝑑 are considered too(𝑐)easy for the model. When 𝐸𝑛 increases, 𝜂𝑐 should decrease.

sample from a harder class contains more information than thatfrom an easier class. This is consistent with the fact that most data
embeddings of easier classes are closer to each other than that ofharder classes. According to the original definition in [7], the total
volume of the feature space for each class has an upper bound,and random sampling can be considered as randomly covering
this volume. This means that overlapping between the samples
randomly happens. Let 𝑉𝛾𝑐 be the upper bound of the total volume
and 𝛽 = 𝑉𝑉−1 . Then the effective number (denoted as 𝐸𝑛 ) is definedas
1 − 𝛽𝑛(𝑐)
𝐸𝑛 𝛾𝑐 =
𝛾𝑐 ,
(8)
1−𝛽
where

1
(𝑐)
Í
lim 𝐸 =
=𝑉
(9)
1, ∀𝑖, P𝑐+ (𝑖) ≥ 0}, P𝑐− (𝑖) ∈ {P𝑐− |P𝑐− (−𝛿)+ 𝑖:𝑦𝑖 ≠𝑐 P𝑐− (𝑖) = 1, ∀𝑖, P𝑐− (𝑖) ≥
𝑛→∞ 𝑛
1−𝛽
0}, where we defineholds. Eqs. (8) and (9) suggest that 𝐸𝑛 is independent from the1
1−class hardness. Therefore, in the proposed approach, we regard
P𝑐+ (𝛿) =Í 𝛼 (𝛿−S𝑗,𝑐 ) , P𝑐 (−𝛿) =Í 𝛼 ( S𝑗,𝑐 −(−𝛿))
𝑒
𝑒
1+
1+
the effective number as training progress bar and introduce an
𝑗:𝑦 𝑗 =𝑐
𝑗:𝑦 𝑗 ≠𝑐effective number for each class. The upper bound 𝑉 is set as a hyper(7)parameter. Furthermore, we treat the boundary of the feature space(see appendix for proof).
(𝑐)as the outlier boundary, and define S𝑜𝑢𝑡𝑙𝑖𝑒𝑟 + 𝜂𝑐 as the threshold of
Proposition 1 suggests that Proxy-Anchor loss actually optimizes two data distributions related to each proxy, and that these
distributions are independent to each other. Thus, the global proxy
distribution is not relevant during training. This is in contrast to
the normalized SoftMax loss, which considers an optimal global
proxy distribution related to each data embedding [29], resulting in
updates of proxies that are completely dominated by data embeddings. Since more samples are regarded as hard in the early stagesof learning, the repulsive force generated by negatives cause theproxies to be far from the ideal distribution, as illustrated in Fig. 2.
Additionally, solutions for the positive terms are sub-optimal when
the positives contain outliers.

3.3

Class Hardness

Following the idea of active learning, we can reduce the weightsof outliers to stabilize the learning of the proxy if most of the data
embeddings are close enough to the proxies (i.e. easy classes). The
problem is then how to obtain a boundary to detect outliers for eachclass. We define such an outlier boundary as a class-(proxy-) de(𝑐)pendent similarity threshold S𝑜𝑢𝑡𝑙𝑖𝑒𝑟 , and define 𝜂𝑐 to be the range
for informative samples. In other words, we increase the gradient(𝑐)(𝑐)weights for positive pairs such that S𝑖,𝑐 ∈ [S𝑜𝑢𝑡𝑙𝑖𝑒𝑟 , S𝑜𝑢𝑡𝑙𝑖𝑒𝑟 + 𝜂𝑐 ](𝑐)and decrease them otherwise, where S𝑜𝑢𝑡𝑙𝑖𝑒𝑟 +𝜂𝑐 should be anotherthreshold related to the current learned subspace for class 𝑐.
Since we do not have any a priori knowledge about the difficultyof each class, all samples should be treated equally in the earlystages of training. Such distinctions should be made independently
after the subspace of the class has reached a certain learning stage.
Volume of the learned subspace To simulate the learning of
the subspace, we assume each data embedding owns one volumetricunit of the subspace belonging to its class, and apply the theory ofeffective number (discussed in [7]).
Let 𝛾𝑐 be the volumetric unit for class 𝑐, we assume it is affectedby the class hardness and should be larger for a difficult class. A(𝑐)the learned subspace related to class 𝑐, denoted as S𝑙𝑒𝑎𝑟𝑛𝑒𝑑 . Hence,
𝜂𝑐 decreases as the learning progresses, as shown in Fig. 3.
Estimating the Class Hardness Based on the above definition,
for a proxy-based method, the average cosine similarity of thelearned positive proxy-data pairs (excluding the outliers) reflects
how well the model learned about a class, and can be used toestimate the class hardness after a certain stage.
Estimating the class hardness using only the current mini-batch
may not be enough, since there are usually only a few samples fromthe same class in the mini-batch, and the number of samples forsome classes may be zero. Therefore, we apply a memory queue tostore the clean data embeddings which were sampled during thepast few iterations. Formally, let 𝑀 be the memory queue with max
size 𝑇 , and 𝑇𝑐 be the total number of embeddings from class 𝑐 in 𝑀.
(𝑐)
Then S𝑙𝑒𝑎𝑟𝑛𝑒𝑑 is calculated by
(𝑐)

(𝑐)

S𝑙𝑒𝑎𝑟𝑛𝑒𝑑 = ℎ · S𝑎𝑣𝑔 =

ℎ
𝑇𝑐

∑︁

S𝑖,𝑐 ,(10)𝑖:(𝒙 𝑖 ,𝑦𝑖 ) ∈𝑀,𝑦𝑖 =𝑐where ℎ is the hyper-parameter used to scale the hardness. After
processing a mini-batch, we filter out outliers and enqueue therest to 𝑀, as illustrated in Fig. 4. The memory queue starts after acertain number of steps is reached, because the embeddings in theinitial stages are typically scattered and the resulting similarities
are not representative.

3.4

Informative Sample-Aware Proxy

Our proposed Proxy-ISA utilizes the aforementioned properties togenerate dynamic pair-weights. Let 𝜔𝑖,𝑐 be the weighting score forthe pair which consists of a data embedding 𝑓 (𝒙 𝑖 ; 𝜽 ) and a proxy𝒑𝑐 . This weighting score depends on the semantic state of 𝒙 𝑖 and(𝑐)+ and 𝜔 − denote the weighting scorelearning progress 𝐸𝑛 . Let 𝜔𝑖,𝑐𝑖,𝑐for positive pairs and negative pairs, respectively.

Informative Sample-Aware Proxy for Deep Metric Learning

MMAsia ’22, December 13–16, 2022, Tokyo, Japan

Figure 5: Curve of the decay functions.
Figure 4: Training flow of Proxy-ISA. Shapes denote embeddings from different classes, whose thresholds are denoted
in different colors. When the size of 𝑀 reaches 𝑇 , it dequeues
the old embeddings to keep the memory up-to-date. Embeddings from the past few iterations are available for reference
due to the slow drift phenomenon discussed in [39]. The algorithm is described in appendix.

for all positive pairs, defined as
(𝑐)

𝜈𝑛

=

1
(𝑐)

,

Based on the analysis in Sec. 3.3, we define 𝜂𝑐 as follows:
(𝑐)

(𝑐)

𝜂𝑐 = (1 + 𝑘 (1 − ℎ · S𝑎𝑣𝑔 ))𝜈𝑛 + 𝜆,To reduce the harmful factors from extremely hard samples, wefirst reform the optimization problems as
∑︁
+ +
max
𝛼
𝜔𝑖,𝑐
Q𝑐 (𝑖)(𝛿 − S𝑖,𝑐 ) + 𝐻 (Q𝑐+ )+Q𝑐𝑖:𝑦𝑖 =𝑐

𝛼
max
−
Q𝑐

∑︁

− −
Q𝑐 (𝑖)(S𝑖,𝑐 + 𝛿) + 𝐻 (Q𝑐− )
𝜔𝑖,𝑐

(11)

𝑖:𝑦𝑖 ≠𝑐where Q𝑐+ and Q𝑐− have the same form as P𝑐+ and P𝑐− , respectively.
According to Proposition 1, the optimal of the formulas in Eq. (11)
are
∑︁
+
©
ª
log ­1 +𝑒 𝜔𝑖,𝑐 ·𝛼 (𝛿−S𝑖,𝑐 ) ® ,¬« 𝑖:𝑦𝑖 =𝑐∑︁−©
ªlog ­1 +𝑒 𝜔𝑖,𝑐 ·𝛼 (𝛿+S𝑖,𝑐 ) ® ,« 𝑖:𝑦𝑖 ≠𝑐¬(12)respectively. Thus, the objective function of Proxy-ISA can be formulated as
∑︁
∑︁
+
1
©
ª
L𝐼𝑆𝐴 := Í +𝑒 𝜔𝑖,𝑐 ·𝛼 (𝛿−S𝑖,𝑐 ) ®
log ­1 +
𝜔¯ 𝑐
+
𝑖:𝑦
=𝑐
𝑐 ∈𝑪
𝑖
«
¬
𝑐 ∈𝑪 +

(13)

𝐶
∑︁
−
1 ∑︁
©
ª
𝑒 𝜔𝑖,𝑐 ·𝛼 (𝛿+S𝑖,𝑐 ) ® ,log ­1 ++Í −𝜔¯ 𝑐 𝑐=1𝑐« 𝑖:𝑦𝑖 ≠𝑐¬+ and 𝜔 − , respectively,
where 𝜔¯ 𝑐+ and 𝜔¯ 𝑐− are the average of all 𝜔𝑖,𝑐𝑖,𝑐for all samples 𝑖 that belong to class 𝑐. The summation reflects theaverage scores of all classes (the global learning status) that relate
to the positive or negative term.
Adaptive Pair Weighting Scores Since the model has higher
confidence in the intra-class hardness when the learning progresses(𝑐)to a later stage, the penalty from 𝜔𝑖,𝑐 is greater for a larger 𝐸𝑛 .
1
A naive implementation is to set 𝜔𝑖,𝑐 = (𝑐 ) for both positive𝐸𝑛

and negative pairs when penalty is needed. However, this causes
the learning signal to be too weak for positive pairs and thus an(𝑐)imbalance between the positive and negative terms when 𝐸𝑛 islarge, since the penalties for outliers are only made for positive+ , we set a lower bound 𝜈 (𝑐)pairs. To prevent the diminishing of 𝜔𝑖,𝑐𝑛

(14)

1 + log(1 + 𝐸𝑛 )(15)

where 𝑘 (> 0) is the sensitivity factor and 𝜆 ∈ [0, 1] is the margin.
Thus, the searching length 𝜂𝑐 is controlled by class hardness, wherea harder class has a wider searching space, and an easier class is
restricted to help stabilize the learning.
Finally, the proposed dynamic weights are defined as follows:
(
(𝑐)
(𝑐)
(𝑐)
1 + 𝜎𝑛 , ℎ · S𝑎𝑣𝑔 − 𝜂𝑐 ≤ S𝑖,𝑐 ≤ ℎ · S𝑎𝑣𝑔 ,
+
𝜔𝑖,𝑐
=
(𝑐)
𝜎𝑛 ,
otherwise,
(16)

(𝑐)
1



S𝑖,𝑐 < ℎ · S𝑎𝑣𝑔 − 𝜂𝑐 ,(𝑐 ) ,−
max(1,𝐸)𝑛𝜔𝑖,𝑐 = 1,otherwise,(𝑐)where 𝜎𝑛+ , defined as
is a decay function for 𝜔𝑖,𝑐
(𝑐)

(𝑐)

=1+

(1 + 𝑒 −𝜏 )(𝜈𝑛 − 1)

,
(17)
(𝑐 )
1 + 𝑒𝑉 −𝐸𝑛 −𝜏
and 𝜏 (> 0) is a hyper-parameter that controls the timing of decay. Since the embeddings are more likely to change in the earlystages and gradually stabilize later, the dynamic weights need
to be controlled such that they change less in the early stages(𝑐)(see appendix for derivation of 𝜎𝑛 ). Using Eq. (9) and Eq. (14),
(𝑐)
(𝑐)
1
+
lim𝑛→∞ 𝜎𝑛 = lim𝑛→∞ 𝜈𝑛 = 1+log(1+𝑉) . This ensures that 𝜔𝑖,𝑐𝜎𝑛(𝑐)does not fall below 𝜈𝑛 , as shown in Fig. 5.

4

EXPERIMENTS

We conduct experiments on four widely used benchmarks to evaluate and analyze the effectiveness of Proxy-ISA.

4.1

Experimental Setting

Datasets Experiments were conducted on the CUB-200-2011 [35],Cars-196 [21], Stanford Online Products (SOP) [33], and In-Shop
Clothes Retrieval (In-Shop) [24] datasets. We follow the standard
protocol applied in [33] to split them into training and testing parts.
CUB-200-2011 contains 200 species of birds with 11,788 images;
we used the first 100 classes (5,864 images) for training and therest for testing. Cars-196 consists of 196 model categories of cars
with 16,185 images; the first 98 classes (8,054 images) were used

MMAsia ’22, December 13–16, 2022, Tokyo, JapanLi, et al.

Table 1: Comparison of Recall@1 of proxy-based methods
on four famous datasets for the task of image retrieval. †denotes evaluation in a fair setting
Method(a) P-ISA@epoch30

CUB Cars SOP In-Shop

Proxy-NCA [26]65.0 83.2 75.9
SoftTriplet [29]65.4 84.5 78.3
Proxy-Anchor† [18] 66.6 84.0 78.3
ProxyGML [45]66.6 85.5 78.0
Proxy-ISA (ours)
68.1 86.4 78.9(b) P-ISA@epoch80

86.9
–
91.3
–
92.3

Table 2: Evaluation in MLRC setting. † denotes evaluation ina fair setting

Method(c) Test set, PA(d) Test set, P-ISA

Figure 6: t-SNE visualization of the 512-dimensional embedding space for the Cars-196 dataset. (a) and (b) present thechanges of the embedding space learned by Proxy-ISA during
training at epoch 30 and 80, respectively, and (c) and (d) show
the results of PA and P-ISA on the test set, respectively.

for training and the rest are used for testing. SOP contains 22,634
classes with 120,053 product images; we used the first 11,318 classes(59,551 images) for training and the rest for testing. The first 3,997
classes (25,882 images) of In-Shop were used for training, while
the remaining 3,985 classes were used for the test set, which waspartitioned into a query set and a gallery set containing 14,218 and
12,612 images, respectively.
Evaluation Metrics The evaluation procedure included two
types of metrics. We first performed a standard evaluation following[33], calculating the Recall@𝐾 for image retrieval tasks. We also
adopted MAP@R, known as Mean Average Precision, from the MLRC
[27] evaluation settings. MAP@R considers the correctness of eachresult associated with a single query, and is considered to be moresuitable for evaluating the entire embedding space.
Implementation Details Our method was implemented in PyTorch [28].We used the Inception network with batch normalization[14] as the embedding network, the embedding dimension was set
to 512. All input images were cropped to 224×224, and random
cropping and horizontal flipping were applied for augmentation
during training; only center-cropping was used during testing. The
memory queue was turned on at the second epoch and the filter
was enabled one epoch after that. The hyper-parameters induced
by Proxy-Anchor were set to 𝛼 = 32, 𝛿 = 10−1 following [18] for all
experiments. Unless otherwise mentioned, we adopted a batch sizeof 128, and used the Adam optimizer [19] with a learning rate of
10−4 and hyper-parameters 𝑉 = 100, ℎ = 1.5 × 10−1 , 𝑘 = 9 × 10−1 ,𝜆 = 10−1 , 𝜏 = 1.5 as our default setting.

CUB-200-2011
R@1
MAP@R

Cars-196
R@1
MAP@R

Margin [41]63.6 ± 0.5 23.1 ± 0.3 81.2 ± 0.5 24.2 ± 0.3
Proxy-NCA [26]65.0 ± 0.4 23.9 ± 0.3 83.6 ± 0.3 25.4 ± 0.3
67.3 ± 0.3 26.7 ± 0.2 85.5 ± 0.2 27.6 ± 0.3
CosFace [36]
ArcFace [8]67.5 ± 0.3 26.5 ± 0.2 85.4 ± 0.3 27.2 ± 0.3
MS [37]65.0 ± 0.3 24.7 ± 0.1 85.1 ± 0.3 28.1 ± 0.2
67.7 ± 0.2 25.2 ± 0.2 83.7 ± 0.3 27.0 ± 0.4
MS+Miner [37]
SoftTriplet [29]66.2 ± 0.4 25.6 ± 0.2 84.5 ± 0.3 27.1 ± 0.2
Proxy-Anchor† [18] 66.3 ± 0.3 25.7 ± 0.3 83.6 ± 0.4 27.1 ± 0.3
Proxy-ISA (ours)
68.1 ± 0.3 26.8 ± 0.2 86.3 ± 0.2 29.3 ± 0.2

4.2

Embedding Space Visualization

To outline how Proxy-ISA controls the learning of proxies, we
visualize the embedding space via t-SNE [34]. As illustrated inFig. 6a, Proxy-ISA gradually widens the distance between proxies sothat each proxy is distributed in its own subspace, and easier classes
form clusters earlier than harder classes. This demonstrates that theclass hardness differs, and the definition of informative samples foreach class also differs. The relationships of class hardness learned
by Proxy-ISA reserves a wider range for a harder class even if it
is an unseen category, as illustrated in Fig. 6d. This demonstrates
that Proxy-ISA can better utilize the embedding space by learning
dynamic margins according to the class hardness. As a result, themodel trained with Proxy-ISA acquires a more detailed subspace
discriminative capability and thus a better generalization.

4.3

Comparison with State-of-the-Art

We now compare Proxy-ISA with state-of-the-art DML methods
by performing image retrieval tasks. The learning rates were set
to 6 × 10−4 for SOP and In-Shop. We only adopted the warm-up
epoch and the AdamW optimizer [25] in the exceptional settings1
introduced by [18] for these two datasets. For a fair comparison,
all such settings were also removed for Proxy-Anchor in experiments on CUB-200-2011 and Cars-196. As shown in Table 1, theproposed Proxy-ISA achieves the best performance compared withthe existing proxy-based methods.
1 See appendix for details.

Informative Sample-Aware Proxy for Deep Metric Learning

The evaluation results in the MLRC setting are presented in Table 2. As the MAP@R metric evaluates the whole embedding space,
the results on the two widely used datasets demonstrate the effectiveness of Proxy-ISA in improving the quality of the embedding
space.

5

CONCLUSION

Treating the proxy-data pairs equally to data pairs can cause undesirable proxy distribution in the embedding space. To address thisproblem, we proposed the Informative Sample-Aware Proxy (ProxyISA), which controls gradient weights non-uniformly according
to different semantic states. Based on the adaptive semantic states
for different classes, Proxy-ISA helps each proxy discover the mostinformative data by exploiting learned information. Furthermore,
we showed that the definition of “informative" is class hardness
dependent by applying the concept of “volume” of the learned subspace to DML. The empirical results demonstrate the superiority ofProxy-ISA over state-of-the-arts.

ACKNOWLEDGMENTS
This work is supported by DENSO IT LAB Recognition and Learning Algorithm Collaborative Research Chair (Tokyo Tech.).

REFERENCES[1] Guillaume Alain, Alex Lamb, Chinnadhurai Sankar, Aaron C. Courville, andYoshua Bengio. 2015. Variance Reduction in SGD by Distributed ImportanceSampling. CoRR (2015). arXiv:1511.06481[2] Yoshua Bengio, Jérôme Louradour, Ronan Collobert, and Jason Weston. 2009.
Curriculum learning. In ICML.
[3] Stephen Boyd and Lieven Vandenberghe. 2004. Convex optimization. Cambridge
university press.
[4] Chris Careaga, Brian Hutchinson, Nathan Oken Hodas, and Lawrence Phillips.
2019. Metric-Based Few-Shot Learning for Video Action Recognition. CoRR
(2019). arXiv:1909.09602[5] Haw-Shiuan Chang, Erik G. Learned-Miller, and Andrew McCallum. 2017. Active
Bias: Training More Accurate Neural Networks by Emphasizing High VarianceSamples. In NeurIPS.
[6] Sumit Chopra, Raia Hadsell, and Yann LeCun. 2005. Learning a similarity metricdiscriminatively, with application to face verification. In CVPR.
[7] Yin Cui, Menglin Jia, Tsung-Yi Lin, Yang Song, and Serge Belongie. 2019. ClassBalanced Loss Based on Effective Number of Samples. In CVPR.
[8] Jiankang Deng, Jia Guo, Niannan Xue, and Stefanos Zafeiriou. 2019. ArcFace:
Additive Angular Margin Loss for Deep Face Recognition. In CVPR.
[9] Yueqi Duan, Lei Chen, Jiwen Lu, and Jie Zhou. 2019. Deep Embedding Learning
With Discriminative Sampling Policy. In CVPR.
[10] Soumyadeep Ghosh, Richa Singh, and Mayank Vatsa. 2019. On Learning Density
Aware Embeddings. In CVPR.
[11] Jacob Goldberger, Geoffrey E Hinton, Sam Roweis, and Russ R Salakhutdinov.
2005. Neighbourhood Components Analysis. In NeurIPS.
[12] Alexander Hermans, Lucas Beyer, and Bastian Leibe. 2017. In Defense of the
Triplet Loss for Person Re-Identification. CoRR (2017). arXiv:1703.07737[13] Elad Hoffer and Nir Ailon. 2015. Deep Metric Learning Using Triplet Network.
In Similarity-Based Pattern Recognition.
[14] Sergey Ioffe and Christian Szegedy. 2015. Batch Normalization: Accelerating
Deep Network Training by Reducing Internal Covariate Shift. In ICML.
[15] Lu Jiang, Zhengyuan Zhou, Thomas Leung, Li-Jia Li, and Li Fei-Fei. 2018. MentorNet: Learning Data-Driven Curriculum for Very Deep Neural Networks on
Corrupted Labels. In ICML.
[16] Leonid Karlinsky, Joseph Shtok, Sivan Harary, Eli Schwartz, Amit Aides,
Rogério Schmidt Feris, Raja Giryes, and Alexander M. Bronstein. 2019. RepMet:
Representative-Based Metric Learning for Classification and Few-Shot Object
Detection. In CVPR.
[17] Angelos Katharopoulos and Francois Fleuret. 2018. Not All Samples Are CreatedEqual: Deep Learning with Importance Sampling. In ICML.
[18] Sungyeon Kim, Dongwon Kim, Minsu Cho, and Suha Kwak. 2020. Proxy Anchor
Loss for Deep Metric Learning. In CVPR.
[19] Diederik P. Kingma and Jimmy Ba. 2015. Adam: A Method for Stochastic Optimization. In ICLR.

MMAsia ’22, December 13–16, 2022, Tokyo, Japan[20] Byungsoo Ko, Geonmo Gu, and Han-Gyu Kim. 2021. Learning with Memorybased Virtual Classes for Deep Metric Learning. In ICCV.
[21] Jonathan Krause, Michael Stark, Jia Deng, and Li Fei-Fei. 2013. 3D Object Representations for Fine-Grained Categorization. In ICCV.
[22] M. Kumar, Benjamin Packer, and Daphne Koller. 2010. Self-Paced Learning for
Latent Variable Models. In NeurIPS.
[23] Tsung-Yi Lin, Priya Goyal, Ross Girshick, Kaiming He, and Piotr Dollár. 2017.
Focal Loss for Dense Object Detection. In ICCV.
[24] Ziwei Liu, Ping Luo, Shi Qiu, Xiaogang Wang, and Xiaoou Tang. 2016. DeepFashion: Powering Robust Clothes Recognition and Retrieval With Rich Annotations.
In CVPR.
[25] Ilya Loshchilov and Frank Hutter. 2019. Decoupled Weight Decay Regularization.
In ICLR.
[26] Yair Movshovitz-Attias, Alexander Toshev, Thomas K. Leung, Sergey Ioffe, andSaurabh Singh. 2017. No Fuss Distance Metric Learning Using Proxies. In ICCV.
[27] Kevin Musgrave, Serge J. Belongie, and Ser-Nam Lim. 2020. A Metric Learning
Reality Check. CoRR (2020). arXiv:2003.08505[28] Adam Paszke, Sam Gross, Francisco Massa, Adam Lerer, James Bradbury, Gregory
Chanan, Trevor Killeen, Zeming Lin, Natalia Gimelshein, Luca Antiga, Alban Desmaison, Andreas Kopf, Edward Yang, Zachary DeVito, Martin Raison, Alykhan
Tejani, Sasank Chilamkurthy, Benoit Steiner, Lu Fang, Junjie Bai, and Soumith
Chintala. 2019. PyTorch: An Imperative Style, High-Performance Deep Learning
Library. In NeurIPS.
[29] Qi Qian, Lei Shang, Baigui Sun, Juhua Hu, Hao Li, and Rong Jin. 2019. SoftTriple
Loss: Deep Metric Learning Without Triplet Sampling. In ICCV.
[30] Jérôme Revaud, John Almazán, Rafael S. Rezende, and César Roberto de Souza.
2019. Learning with Average Precision: Training Image Retrieval with a Listwise
Loss. In ICCV.
[31] Florian Schroff, Dmitry Kalenichenko, and James Philbin. 2015. FaceNet: A
Unified Embedding for Face Recognition and Clustering. In CVPR.
[32] Kihyuk Sohn. 2016. Improved Deep Metric Learning with Multi-class N-pair Loss
Objective. In NeurIPS.
[33] Hyun Oh Song, Yu Xiang, Stefanie Jegelka, and Silvio Savarese. 2016. Deep Metric
Learning via Lifted Structured Feature Embedding. In CVPR.
[34] Laurens van der Maaten and Geoffrey Hinton. 2008. Visualizing Data using
t-SNE. Journal of Machine Learning Research (2008).
[35] Catherine Wah, Steve Branson, Peter Welinder, Pietro Perona, and Serge J Belongie. 2011. The Caltech-UCSD Birds-200-2011 Dataset. Technical Report CNSTR-2011-001. California Institute of Technology.
[36] Hao Wang, Yitong Wang, Zheng Zhou, Xing Ji, Dihong Gong, Jingchao Zhou,
Zhifeng Li, and Wei Liu. 2018. CosFace: Large Margin Cosine Loss for Deep Face
Recognition. In CVPR.
[37] Xun Wang, Xintong Han, Weilin Huang, Dengke Dong, and Matthew R Scott. 2019.
Multi-Similarity Loss with General Pair Weighting for Deep Metric Learning. In
CVPR.
[38] Xinshao Wang, Yang Hua, Elyor Kodirov, Guosheng Hu, and Neil M. Robertson.
2019. Deep Metric Learning by Online Soft Mining and Class-Aware Attention.
In AAAI. Article 657.
[39] Xun Wang, Haozhi Zhang, Weilin Huang, and Matthew R Scott. 2020. Cross-Batch
Memory for Embedding Learning. In CVPR.
[40] Yandong Wen, Kaipeng Zhang, Zhifeng Li, and Yu Qiao. 2016. A Discriminative
Feature Learning Approach for Deep Face Recognition. In ECCV.
[41] Chao-Yuan Wu, R. Manmatha, Alexander J. Smola, and Philipp Krähenbühl. 2017.
Sampling Matters in Deep Embedding Learning. In ICCV.
[42] Wanyin Wu, Dapeng Tao, Hao Li, Zhao Yang, and Jun Cheng. 2021. Deep features
for person re-identification on metric learning. Pattern Recognition (2021).
[43] Yang Zhao, Chunyuan Li, Ping Yu, and Changyou Chen. 2021. ReMP: Rectified
Metric Propagation for Few-Shot Learning. In CVPR.
[44] Wenzhao Zheng, Zhaodong Chen, Jiwen Lu, and Jie Zhou. 2019. Hardness-Aware
Deep Metric Learning. In CVPR.
[45] Yuehua Zhu, Muli Yang, Cheng Deng, and Wei Liu. 2020. Fewer is More: A Deep
Graph Metric Learning Perspective Using Fewer Proxies. In NeurIPS.

A

ALGORITHM AND TRAININGCOMPLEXITY

We describe the training flow of our proposed method in Algorithm 1.
Training Complexity Although our proposed Proxy-ISA takes
complexity of 𝑂 (𝑁𝐶), it will increase the training time to someextent on large datasets that contain a larger number of categories(i.e., 𝐶 ≫ 𝑁 ), since each dynamic weight is treated independently
and calculation of each 𝜂𝑐 takes extra complexity.

MMAsia ’22, December 13–16, 2022, Tokyo, JapanLi, et al.

Algorithm 1 A training iteration of Proxy-ISA
Input: data embeddings 𝑿 , class label 𝒚, proxy set 𝑷 , memory
queue 𝑀.
𝑺 ← cosine similarity between 𝑷 and 𝑿
𝑪 + ← class labels appeared in 𝒚𝑓 𝑖𝑙𝑡𝑒𝑟 ← ∅𝜂 1, 𝜂 2, . . . , 𝜂𝐶 ← calculate search length for each classfor 𝑐 ∈ 𝑪 + dofor 𝑖 : 𝑦𝑖 = 𝑐 do
if 𝑓 𝑖𝑙𝑡𝑒𝑟 is turned on then+ according to S
Calculate 𝜔𝑖,𝑐𝑖,𝑐(𝑐)

Add 𝒙 𝑖 to 𝑓 𝑖𝑙𝑡𝑒𝑟 if S𝑖,𝑐 < S𝑙𝑒𝑎𝑟𝑛𝑒𝑑 − 𝜂𝑐
else
+ ←1
𝜔𝑖,𝑐
end ifend forend forfor 𝑐 = 1, 2, . . . , 𝐶 do
for 𝑖 : 𝑦𝑖 ≠ 𝑐 do
− according to S
Calculate 𝜔𝑖𝑐
𝑖,𝑐
end forend forCalculate loss
if 𝑀 is turned on then
Enqueue 𝒙 𝑖 ∈ {𝑿 − 𝑓 𝑖𝑙𝑡𝑒𝑟 } to 𝑀
Dequeue old embeddings if 𝑀 out of sizefor 𝑐 ∈ 𝑪 + do(𝑐)Update S𝑙𝑒𝑎𝑟𝑛𝑒𝑑 through 𝑀
end forend if(a) A loose space

Figure 7: Impact of compactness of the embedding space on
the repulsive force. A compact space (or clusters of the harderclasses) generates greater joint repulsive force, even if thecosine similarity to the proxy (i.e. the gradient weight of theproxy-data pairs) is kept unchanged.
(𝑐)we then adjust it to our desired curve. Firstly, to satisfy lim𝑛→0+ 𝜎𝑛 ≈1, we transform the function to
1
1−
,
(21)
(𝑐 )
−(𝐸
1 + 𝑒 𝑛 −𝑉 )−𝜏where we introduce 𝜏 to control the timing of decay. Secondly,(𝑐)(𝑐)
to satisfy lim𝑛→∞ 𝜎𝑛 = 𝜈𝑛 , we formulate an equation withunknown variable 𝜉 as follows:
𝜉
(𝑐)
(𝑐)
lim 𝜎 = 1 −= 𝜈𝑛 .
𝑛→∞ 𝑛
1 + 𝑒 −𝜏(𝑐)

𝜉 = (1 + 𝑒 −𝜏 )(1 − 𝜈𝑛 ),PROOF OF PROPOSITION 1(18)

𝑗:𝑦 𝑗 =𝑐

Therefore, we have
𝛼

∑︁

∑︁
©
ª
P𝑐+ (𝑖) (𝛿 −S𝑖,𝑐 ) +𝐻 (P𝑐+ ) = log ­1 +𝑒 𝛼 (𝛿−S𝑖,𝑐 ) ® . (19)𝑖:𝑦𝑖 =𝑐« 𝑖:𝑦𝑖 =𝑐¬

The same analysis is applicable to P𝑐− .

C

DETAILS OF THE DECAY FUNCTION+ is decided by the estimated class hardSince the penalty from 𝜔𝑖,𝑐
ness, it should not be too large when the model cannot determine+ should be close to 1, withthe class hardness. In other words, all 𝜔𝑖,𝑐less variation in the early learning phase. Given an original sigmoid(𝑐)function that varies with 𝐸𝑛 :1(𝑐 )1 + 𝑒 −𝐸𝑛

,

(𝑐)

=1+

(1 + 𝑒 −𝜏 )(𝜈𝑛 − 1)

(20)

.

(𝑐 )

1 + 𝑒𝑉 −𝐸𝑛 −𝜏(𝑐)

Proof. According to the K.K.T. conditions [3], P𝑐+ in Eq. (6) has theclosed-form solution𝑒 𝛼 (𝛿−S𝑖,𝑐 )Í 𝛼 (𝛿−S𝑗,𝑐 ) .
1+
𝑒

(23)

thus, the decay function is formulated as:(𝑐)P𝑐+ (𝑖) =(22)

The solution is𝜎𝑛B(b) A compact space

(24)

(𝑐)

− is set to 1/𝐸
The penalty from 𝜔𝑖,𝑐𝑛 (< 𝜈𝑛 ) for preventing therepulsive force on the proxy from being too large under the impactof a large population of easy negatives.

D

IMPACT OF PROXY-ISA ON THE
EMBEDDING SPACE

To quantitatively describe the learned embedding space, we show
its compactness via heat map of pair-wise cosine similarity. As illustrated in Fig. 8, the distribution of the data embeddings is relatively
compact at the initial stage (results of the pre-trained backbone anda randomly initialized embedding layer), and is dispersed to varying
degrees after applying different objective functions. Fig. 8e, Fig. 8h
and Fig. 8k show that the embedding space learned by Proxy-Anchor
loss [18] stops dispersing after it reaches a certain stage, comparedto the case of normalized SoftMax loss in Fig. 8d, Fig. 8g and Fig. 8j.
This is resulted from the key difference between Proxy-Anchor andnormalized SoftMax, the consideration of the optimization problem(i.e., Proxy-Anchor only considers the optimal distribution of data
embeddings related to each proxy, while normalized SoftMax only
considers the optimal distribution of proxies related to each data
embedding), since Proxy-Anchor generates stronger attractive andrepulsive force between a proxy and a relatively hard sample, theproxy distribution is easily disrupted.

Informative Sample-Aware Proxy for Deep Metric Learning

MMAsia ’22, December 13–16, 2022, Tokyo, Japan(a) N.SoftMax@Initial(b) Proxy-Anchor@Initial(c) Proxy-ISA@Initial(d) N.SoftMax@eph10(e) Proxy-Anchor@eph10(f) Proxy-ISA@eph10(g) N.SoftMax@eph30(h) Proxy-Anchor@eph30(i) Proxy-ISA@eph30(j) N.SoftMax@eph60(k) Proxy-Anchor@eph60(l) Proxy-ISA@eph60

Figure 8: Heat map of cosine similarity between data embeddings of training set of the Cars-196 dataset and proxies. Three
data samples are randomly selected for each class.

MMAsia ’22, December 13–16, 2022, Tokyo, JapanLi, et al.

(a) Recall@1 results vs. 𝑉(b) Recall@1 results vs. 𝑇

Figure 10: Impact of the hyper-parameters 𝑉 (upper boundof 𝐸𝑛 ) and 𝑇 (maximum size of the memory queue) on the
Recall@1 metric.
Figure 9: Impact of the hyper-parameters 𝑘 and 𝜆 on the
MAP@R metric.

Since most of the data embeddings are scattered in a relatively
compact space at the initial stage, a larger fraction of this is regarded
as hard samples (mostly negative) by Proxy-Anchor, which means
the proxies are more likely to move in undesired directions, thus
forming a cluster far from the data embeddings, as shown in thepaper. After the proxies reach a balance (i.e., learned a shortcut by
discriminating the data embeddings while getting far from them),
they still keep the ability to force the positives to be close to eachother and to be far from the negatives, but failed to disperse thewhole embedding space further. In the meanwhile, a too compact
embedding space generates stronger repulsive force, which blocks
the proxy from getting closer to its ideal cluster, as described inFig. 7.
Unlike Proxy-Anchor, our proposed Proxy-ISA captures informative samples that correspond to different learning stages, thus
continues to disperse the embedding space, even in the late learning
phase, as shown in Fig. 8i and Fig. 8l. Although the dispersion is not
as great as normalized SoftMax, Proxy-ISA allows the model to consider relative sample hardness for each class, which is ignored bynormalized SoftMax (also ignored by other SoftMax based methods[8, 36] and Proxy-NCA [26]). In other words, Proxy-ISA considers
both sample-wise hardness and class-wise hardness, this helps theproxy discover its own informative samples adaptively according
to different classes, and thus generates better learning signals forthe model.

Table 3: Comparison of different combination of penalty
from 𝜔𝑖,𝑐 on Cars-196 dataset
(𝑐)

+ :
𝜔𝑖,𝑐

1 (no penalty) 1 (no penalty) 1/𝐸𝑛

− :
𝜔𝑖,𝑐

Recall@1
MAP@𝑅

The most important hyper-parameters are 𝑘 and 𝜆, which control
the search length (𝜂𝑐 ) of the informative samples, and 𝑘 also controls
the sensitivity to class hardness. As illustrated in Fig. 9, for Cars-196[21] dataset, when 𝑘 reaches an appropriate range, the adaptive
search length helps each proxy focus on its informative samples,
and thus improves the model performance for a wider range of themargin 𝜆. In the meanwhile, a search length with too large a 𝑘, i.e.,
too sensitive to the class hardness, will be more likely to introduce
outliers for harder classes, thus can degrade the generalization.
This is consistent with that hard samples do not always mean
informative. For different datasets, the appropriate 𝑘 should be
different because the inter-class relation differs.

(𝑐)

𝜎𝑛

1 (no penalty)

(𝑐)
1/𝐸𝑛

(𝑐)
1/𝐸𝑛

1/𝐸𝑛

83.6
27.1

85.1
28.3

71.4
16.3

85.8
28.7

86.3
29.3

(𝑐)

We show the impact of 𝑉 and 𝑇 on the test set of CUB-200-2011[35] (100 classes). As illustrated in Fig. 10a, too large 𝑉 will degrade
the model performance, since total volume of the finite samples
in the feature space of one class has an appropriate limit, whichshould not be set too large. In the meanwhile, 𝑉 controls the decayof the dynamic weights, which needs to be at an appropriate timing
to help the model focus on the informative samples.
(𝑐)
The memory size 𝑇 affects the estimation quality of S𝑙𝑒𝑎𝑟𝑛𝑒𝑑 ,which is the threshold of a learned subspace. Too small 𝑇 will resultin an insufficient number of samples used for estimation, while toolarge 𝑇 will result in some of the samples in 𝑀 being outdated, thus
the memory size has a best range, as shown in Fig. 10b.

E.2

Effect of the Decay Function(𝑐)

To show the effect of the decay function 𝜎𝑛 , we compare the+ . As shown inperformance by setting different penalties of 𝜔𝑖,𝑐(𝑐)

E ABLATION STUDY
E.1 Impact of Hyper-parameters

(𝑐)

𝜈𝑛

(𝑐)
1/𝐸𝑛

+ = 1/𝐸 , which is the same to 𝜔 − , will degrade
Table 3, setting 𝜔𝑖,𝑐𝑛𝑖,𝑐the performance since the imbalanced weighting between positives(𝑐)and negatives, as discussed in the paper, bounding it with 𝜈𝑛(𝑐)alleviates this problem. After applied the decay function 𝜎𝑛 for+ , our method provides weighting factors dynamically along
𝜔𝑖,𝑐learning, and the penalty increases significantly only when thelearning of the class reached an appropriate phase, this also helps
the model treat informative samples non-uniformly along learning.
In the meanwhile, it prevents the gradient from being dominatedby a relatively large number of easy proxy-data pairs by directlyreducing their gradient weights, which also keeps the class-related
regions from being over-compressed, thus prevents over-fitting,as shown in Fig. 11a. A similar effect can be observed when weapply the adaptive weighting scores directly on Proxy-NCA [26](Fig. 11b).

Informative Sample-Aware Proxy for Deep Metric Learning

MMAsia ’22, December 13–16, 2022, Tokyo, Japan

Table 4: Recall@1 compared to Proxy-Anchor with exceptional settings applied
MethodCUB Cars SOP In-Shop

Proxy-Anchor [18] 68.4 86.1 79.1
Proxy-ISA
69.4 86.8 79.3
(a)

91.5
92.5

(b)

E.3
Figure 11: Performance on unseen classes of Cars-196. Although the baselines converge faster, over-fitting happens as
learning progresses.

Extra Settings for Fair Comparison

As mentioned in other work [20, 45], Proxy-Anchor loss is actually implemented with three additional tricks: 1) the AdamW [25]optimizer instead of Adam [19], 2) a parameter warm-up strategy
for the last FC layer, 3) a combination of average and max poolingfollowing the backbone network. Comparison to Proxy-Anchor
with all the exceptional settings enabled is shown in Table 4.