{'fraction_non_alphanumeric': 0.039270019266988504, 'fraction_numerical': 0.020219513779144025, 'mean_word_length': 4.488830798479087, 'pattern_counts': {'":': 0, '<': 9, '<?xml version=': 0, '>': 15, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 11, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Proxy Synthesis: Learning with Synthetic Classes for Deep Metric Learning

One of the main purposes of deep metric learning is to construct an embedding space that has well-generalized embeddings on both seen (training) classes and unseen (test) classes. Most existing works have tried to achieve this using different types of metric objectives and hard sample mining strategies with given training data. However, learning with only the training data can be overfitted to the seen classes, leading to the lack of generalization capability on unseen classes. To address this problem, we propose a simple regularizer called Proxy Synthesis that exploits synthetic classes for stronger generalization in deep metric learning. The proposed method generates synthetic embeddings and proxies that work as synthetic classes, and they mimic unseen classes when computing proxy-based losses. Proxy Synthesis derives an embedding space considering class relations and smooth decision boundaries for robustness on unseen classes. Our method is applicable to any proxy-based losses, including softmax and its variants. Extensive experiments on four famous benchmarks in image retrieval tasks demonstrate that Proxy Synthesis significantly boosts the performance of proxy-based losses and achieves state-of-the-art performance.


Introduction
Deep metric learning aims to learn a similarity metric among arbitrary data points so that it defines an embedding space where semantically similar images are close together, and dissimilar images are far apart. Owing to its practical significance, it has been used for a variety of tasks such as image retrieval (Gordo et al. 2016;Sohn 2016), person reidentification (Yu et al. 2018;Hermans, Beyer, and Leibe 2017), zero-shot learning (Zhang and Saligrama 2016), and face recognition (Wen et al. 2016;Deng et al. 2019). The well-structured embedding is requested to distinguish the unseen classes properly, where the model is required to learn image representation from seen classes. This has been achieved by loss functions, which can be categorized into two types: pair-based and proxy-based loss.
The pair-based losses are designed based on the pairwise similarity between data points in the embedding space, such as contrastive (Chopra, Hadsell, and LeCun 2005), triplet (Weinberger and Saul 2009), N-pair loss (Sohn 2016), etc. However, they require high training complexity and empirically suffer from sampling issues (Movshovitz-Attias et al. 2017). To address these issues, the concept of proxy has been introduced. A proxy is a representative of each class, which can be trained as a part of the network parameters. Given a selected data point as an anchor, proxy-based losses consider its relations with proxies. This alleviates the training complexity and sampling issues because only data-toproxy relations are considered with a relatively small number of proxies compared to that of data points.
Although the performance of metric learning losses has been improved, a network trained only with training (seen) data can be overfitted to the seen classes and suffer from low generalization on unseen classes. To resolve this problem, previous works (Zheng et al. 2019;Gu and Ko 2020;Ko and Gu 2020) have generated synthetic samples to exploit additional training signals and more informative representations. However, these methods can only be used for pairbased losses; thus, they still suffer from the training complexity and sampling issues.
In this paper, we propose Proxy Synthesis (PS), which is a simple regularizer for proxy-based losses that encourages networks to construct better generalized embedding space for unseen classes. As illustrated in Figure 1, our method generates synthetic embeddings and proxies as synthetic classes for computing a proxy-based loss. Proxy Synthesis exploits synthetic classes generated by semantic interpolations to mimic unseen classes, obtaining smooth decision boundaries and an embedding space considering class relations. Moreover, the proposed method can be used with any proxy-based loss, including softmax loss and its variants. We demonstrate that our proposed method yields better robustness on unseen classes and deformation on the input and embedding feature. We achieve a significant performance boost on every proxy-based loss with Proxy Synthesis and obtain state-of-the-art performance with respect to four famous benchmarks in image retrieval tasks.

Related Work
Sample Generation: To achieve better generalization, previous works (Zhao et al. 2018;Duan et al. 2018;Zheng et al. 2019) have leveraged a generative network to create synthetic samples, which can lead to a bigger model and slower training speed. To solve these problems, recent works Ko and Gu 2020) have proposed to generate samples by algebraic computation in the embedding space. However, the above works can only be used for pair-based losses, which causes the same drawbacks of high training complexity and careful pair mining. In addition, the above works exploit synthetic embeddings only for existing (seen) classes, when Proxy Synthesis uses synthetic embeddings and proxies as virtual classes for generalization on unseen classes explicitly.
Mixup: Mixup techniques Verma et al. 2018;Guo, Mao, and Zhang 2019) have been proposed for generalization in the classification task. These techniques linearly interpolate a random pair of training samples and the corresponding one-hot labels. Proxy Synthesis and Mixup techniques share the common concept in terms of interpolating features for augmentation but have three major differences. First, Mixup techniques are proposed for generalization, which aims for robustness on seen classes, such as classification, whereas Proxy Synthesis is proposed for generalization in metric learning tasks, aiming for robustness on unseen classes. Second, Mixup techniques interpolate the input vectors and hidden representations, whereas the proposed method interpolates the embedding features in the output space. Third, Mixup techniques interpolate onehot labels, while Proxy Synthesis interpolates proxies, which allow us to learn the positional relations of class representatives in the embedding space explicitly.
Virtual Class: Virtual softmax (Chen, Deng, and Shen 2018) generates a single weight as a virtual negative class for softmax function to enhance the discriminative property of learned features in the classification task. Even though the work proves that the constrained region for each class becomes more compact by the number of classes increase, Virtual softmax considers a single synthetic weight without any corresponding embedding as a virtual negative class. Moreover, generating virtual weight by W virt = Wy i xi / xi is not applicable for softmax variants with weight normalization (i.e. Norm-Softmax, ArcFace, Proxy-anchor, etc), where x i is i-th embedding, and W yi is its positive class weight. This is because W virt of the synthetic negative class will be equivalent to x i after normalization. In contrast, Proxy Synthesis generates multiple proxies (weights) and corresponding embeddings as multiple virtual classes, which can be used as negative and also positive classes. Moreover, the proposed method is applicable for any proxybased loss and softmax variants.

Preliminary
Consider a deep neural network f : D f − → X , which maps from an input data space D to an embedding space X . We define a set of embedding feature X = [x 1 , x 2 , . . . , x N ], where each feature x i has label of y i ∈ {1, . . . , C} and N is the number of embedding features. We denote a set of proxy P = [p 1 , p 2 , . . . , p C ] and formulate generalized proxy-based loss as: where (x, p) denotes random pair of embedding and matching proxy from the pair distribution R. Softmax loss is not only the most widely used classification loss but also has been re-valued as competitive loss in metric learning (Zhai and Wu 2018;Boudiaf et al. 2020). Let W j ∈ R d denote the j-th column of the weight W ∈ R d×C , where d is the size of embedding features. Then, Softmax loss is presented as follows: where we set the bias b = 0 because it does not affect the performance (Liu et al. 2017;Deng et al. 2019). Because the proxy P is learned as model parameter, the weight W of softmax loss can be interpreted as proxy, which is the center of each class (Deng et al. 2019;Wang et al. 2018b).
Normalizing the weights and feature vector is proposed to lay them on a hypersphere of a fixed radius for better interpretation and performance (Wang et al. 2017(Wang et al. , 2018aLiu et al. 2017). When we transform the logit (Pereyra et al. 2017) as W T j x i = W j x i cos θ j and fix the individual proxy (weight) W j = 1 and feature x i = 1 by l 2 -normalization, the normalized softmax (Norm-softmax) loss can be written with proxy-wise form as: where p + is a positive proxy, P − is a set of negative proxies, γ is a scale factor, and s(a, b) denotes the cosine similarity between a and b. More details of proxy-based (Proxy-NCA (Movshovitz-Attias et al. 2017), SoftTriple (Qian et al. 2019), and Proxy-anchor (Kim et al. 2020)) and softmax variants (SphereFace (Liu et al. 2017), ArcFace (Deng et al. 2019), and CosFace (Wang et al. 2018b)) losses are presented in the supplementary Section A.

Proxy Synthesis
One of the key purposes of metric learning is to construct a robust embedding space for unseen classes. For this purpose, the proposed method allows proxy-based losses to exploit synthetic classes. Training a proxy-based loss using Proxy Synthesis is performed in three steps. First, we process a mini-batch of input data with a network f to obtain a set of embeddings X. Second, given two random pairs of an embedding and corresponding proxy from different classes, (x, p) and (x , p ), we generate a pair of synthetic embedding and proxy (x,p) as follows: where I λ (a, b) = λa+(1−λ)b is a linear interpolation function with the coefficient of λ ∼ Beta(α, α) for α ∈ (0, ∞), and λ ∈ [0, 1]. We perform µ × batch size generations of Eq. 4, where hyper-parameter µ = # of synthetics batch size is a generation ratio by batch size. Thereafter, we define X as a set of original and synthetic embeddings, and P as a set of original and synthetic proxies. Synthetic proxyp will work as a representative of the synthetic class, which has a mixed representation of class p and p , whereas the synthetic embeddingx will be a synthetic data point of the synthetic class. Third, we compute the loss, including synthetic embeddings and proxies, as if they are new classes. The generalized loss with Proxy Synthesis is formulated as: where R λ is a distribution of the embedding and proxy pairs including originals and synthetics generated with λ. Implementing Proxy Synthesis is extremely simple with few lines of codes. Moreover, it does not require to modify any code of proxy-based loss and can be used in a plug-and-play manner with negligible computation cost. Code-level description and experiment of training time and memory are presented in the supplementary Section B.1 and D.1, respectively.

Discussion
Learning with Class Relations: Unlike tasks that only test with seen classes such as classification, metric learning is desired to construct a structural embedding space for robustness on unseen classes. A well-structured embedding space should contain meaningful relations among embeddings; an example from the previous work (Mikolov et al. 2013) is as follows: king − man + woman ≈ queen in a word embedding space. To achieve this, Proxy Synthesis explicitly inserts in-between class relations with synthetic classes (i.e., I λ (wolf, dog) ≈ wolf dog) and they mimic unseen classes for training with a diverse range of data characteristics. Proxy Synthesis considers class relations with Equation 4 and 5 in forward propagation. This characteristic is reflected in backward propagation as well.
For convenience in gradient analysis, we write the loss of softmax function on (x, p i ), where x is an anchor embedding of input, and p i is corresponding positive proxy, as follows, where E(p) = e S(x,p) and S(x, p) = s(x, p) x p = x T p. Then, gradient over positive similarity S(x, p i ) is, It shows that the gradient over S(x, p i ) only considers the similarity of the anchor embedding and its proxy by E(p i ).
When Proxy Synthesis is applied, the gradient changes. In this gradient induction, we assume that the positive proxy p i of input is used for generating synthesized proxyp with p j asp = λp i + λ p j , where λ = 1 − λ. Then, the gradients over S(x, p i ) and S(x, p j ) are inducted as follows, In contrast to the softmax loss, Proxy Synthesis enables the gradient over S(x, p i ) and S(x, p j ) to consider class relation between p i and p j via E(p) = E(λp i + λ p j ) in the backward propagation. The detailed induction is presented in supplementary Section B.2.
Obtaining a Smooth Decision Boundary: Synthetic classes work as hard competitors of original classes because of positional proximity, which leads to lower prediction confidence and, thus, smoother decision boundaries. The smoothness of the decision boundary is a main factor of generalization (Bartlett and Shawe-Taylor 1999; Verma et al. 2018), and it is more desirable in metric learning to provide a relaxed estimate of uncertainty for unseen classes. For better intuitions, we conduct an experiment to visualize the generalization effect of Proxy Synthesis, as depicted in Figure 2.

Input space visualization
Embedding space visualization Figure 2: Experiment with 2D isotropic Gaussian dataset including red, blue, and gray classes. Simple feed-forward network with two-dimensional embedding is used, while we train network with red and blue classes and let gray class remain unseen. The darker the intensity of the blue or red in the background, the higher the prediction confidence to blue or red class, respectively.
For both the input and embedding spaces, Norm-softmax has a strict decision boundary, whereas PS + Norm-softmax has a smooth decision boundary that transitions linearly from the red to the blue class. Further theoretical analysis of such phenomenon is provided below. A network with ordinary softmax outputs the probability of an embedding x belonging to a specific class i as follows, Considering the linearity of similarity function S(x, p) = x T p, the strict decision boundary is constructed when the network always outputs embedding vector close to one proxy, even though the input has shared visual semantics among different classes. Such phenomenon occurs because the softmax function forces all embedding vectors to become as close to the corresponding proxies as possible during training. Considering the softmax loss of an embedding vector and its positive proxy (x, p i ) as Equation 6, the gradient of such loss over x can be inducted as follows: It is obvious that τ i < 0 and τ k > 0. Considering the parameter update is performed by x = x − η ∂Li ∂x , where η is a learning rate, the gradient descent forces x to be closer to p i and to be distant from other proxies p k .
Proxy Synthesis overcomes such problem of embedding space to overfit to the proxies by providing a gradient of opposite direction compared to ordinary softmax. To describe major difference of Proxy Synthesis and ordinary softmax, we consider softmax loss for synthesized pairx = λx + λ x ,p = λp i + λ p j , where (x, p i ) and (x , p j ) are pairs of an embedding and a corresponding proxy: where E(p) = e S(x,p) and P − = P \ {p i , p j }. It should be noted thatp / ∈ P . Since we suggest to sample λ from Beta(α, α) with small α in Section 4.3,p has high chance to be generated either close to p i with λ >> 0.5 or close to p j with λ << 0.5. As the proofs for both cases are equivalent, we assume the first case:x is much closer to x than x . We consider gradient over x because the loss will affect the closer embedding vector more than the other one. The inducted gradient over x is as follows: Asx is closer to p i andp compared to other proxies, Equation 14 can be re-written as follows, It is obvious that τ i > 0, implying that by adopting Proxy Synthesis, softmax loss for synthesized pair provides gradient which leads embedding vector not too close to the corresponding proxy p i ; it is also obvious that τ j < 0, implying that softmax loss for synthesized pair provides gradient which makes embedding vector not too distant from the competing proxy p j . In such a manner, Proxy Synthesis prevents embedding vectors lying too close to proxies, which finally leads to the smooth decision boundary. The detailed induction is provided in the supplementary Section B.3.

Experimental Setting
We evaluate the proposed method with respect to four benchmarks in metric learning: CUB-200-2011 (CUB200) (Wah et al. 2011    We set elements of X and P to be checked( ) embeddings and proxies to compute L N orm ( X, P ).
hyper-parameters of Proxy Synthesis, α and µ are set to 0.4 and 1.0, respectively. Considering recent works (Musgrave, Belongie, and Lim 2020; Fehervari, Ravichandran, and Appalaraju 2019) that have presented enhanced evaluation procedure with regard to fairness, we include an evaluation procedure designed from work "A metric learning reality check" (Musgrave, Belongie, and Lim 2020) and call it MLRC evaluation, which contains 4-fold cross-validation, ensemble evaluation, and usage of fair metrics (P@1, RP, and MAP@R). Please refer to supplementary Section C for further details on the benchmarks and implementation.

Impact of Synthetic Class
Embedding Space Visualization: Exploiting synthetic classes is preferable in metric learning because the main goal is to develop robustness on unseen classes. This is depicted visually in Figure 3. In Figure 3a, unseen test embeddings are located in-between the clusters of train embeddings by forming clusters. Similarly, synthetic classes are also generated in-between train embeddings, as depicted in Figure 3b, and play an important role in mimicking unseen classes during the training phase. Thus, these additional training signals enable a network to capture extra discriminative features for  better robustness on unseen classes. Extended visualization is in supplementary Section D.5.

Impact of Synthetic Embedding and Proxy:
To investigate the quantitative impact of synthetic embedding and proxy, we conduct an experiment by differentiating the elements of X and P in Norm-softmax loss. Table 1 illustrates that using only synthetic embeddings and proxies (M2) leads to a slightly lower performance than the baseline (M1). Adding synthetic proxies (M3) and using synthetic embedding instead of the original embedding (M4) leads to improved performance when compared with the baseline (M1). This indicates that the generated synthetic embeddings and proxies build meaningful virtual classes for training. Finally, using all embeddings and proxies (Proxy Synthesis) achieves the best performance among all cases by considering the fundamental and additional training signals.

Synthetic Class as Hard Competitor
Impact of Hardness: Generating synthetic classes is required to be hard enough so that the model can learn more discriminative representations. The hardness of synthetic classes can be controlled by α, which decides probability distribution for the sampling of the interpolation coefficient λ. In Table 2, static λ = 0.1 shows low performance because synthetic classes are too close to original classes, and static λ = 0.5 also shows low performance because it generates synthetic classes in the middle of two original classes, which is relatively easy to distinguish. The optimal static λ value is around 0.2, which establishes the proper difficulty of distinguishment. Moreover, the result shows that the stochastic generation is better than the static generation. This is because stochastic generation can generate more number of different synthetic classes with wide variation. In the stochastic generation, α = 1.0 is the same with uniform distribution, and α = 1.5 has a high chance of generating synthetics in the middle of two classes; thus, their performance is relatively low. Similar to the experiment of static generation, α around 0.4 shows the best performance, which has a high chance of generating synthetic classes close enough to an original class. We provide additional experiments on the effect of hyper-parameter in supplementary Section D.2.
Logits Visualization: We compare the cosine similarity (logits) between embeddings and proxies during the training procedure. In Figure 4a, the logit values of ground truth (GT), which are represented by the main diagonal D 0 , are clearly red owing to high prediction confidence. This leads to a strict decision boundary, as depicted in Figure 2a and Figure 2c, and may cause an overfitting problem. On the other hand, the GT logit values of PS + Norm-softmax (D 1 and D 4 ) have lower confidence, represented with yellow to orange color. This is because synthetic classes generated near the original classes work as hard competitors (D 2 and D 3 ), which prevents excessively high confidence, while the   confidence of main diagonals (D 1 and D 4 ) is still higher than that of competitors' diagonals (D 2 and D 3 ) with redder color for the same embedding. This smoothens the decision boundary, as depicted in Figure 2b and Figure 2d, and leads to stronger generalization.

Robustness to Deformation
Input Deformation: To further evaluate the quality of representations learned with Proxy Synthesis, we perform a deformation test on the input data with trained networks. In Table 3, we evaluate the test data with several input deformations that are not used in training. A better-generalized model should be more robust to a large variety of input deformations. The result indicates that the network trained using Proxy Synthesis demonstrates significantly improved performance to input deformations.
Embedding Deformation: To see the robustness on embedding deformation of trained networks, we evaluate performance with synthetic embeddings. Figure 5 depicts a network trained with Norm-softmax loss struggling with low performance on both the train and test set. In contrast, a network trained with Proxy Synthesis performs almost twice as well when compared with Norm-softmax loss on both the train and test set. This demonstrates that Proxy Synthesis provides more robust embedding features, which also leads to robustness on unseen classes. Besides, the patterns of performance are similar to those discussed in Section 4.3. When λ is close to 0 and 1, the performance is low because of hard   synthetics, and when λ is close to 0.5, the performance is high because of relatively easy synthetics. Additional experiments are in the supplementary Section D.3.

Comparison with Other Regularizers
Further, we compare the proposed method with other regularizers, including Virtual Softmax, Input Mixup, and Manifold Mixup in the image retrieval task. Note that Virtual Softmax is not applicable to Norm-softmax loss because W virt will always be constant 1. As presented in Table 5, Virtual Softmax degrades the performance of all cases with a margin of average -2.15%. Input Mixup degrades the performance on CARS196 with an average margin -0.75% and improves the performance on SOP with an average margin +0.45%. Manifold Mixup increases the performance of all cases with an average margin +0.5%. This illustrates that although these techniques are powerful for generalizing seen classes, such as classification tasks, they lack discriminative ability on unseen classes. On the other hand, Proxy Synthesis improves performance for all cases with a large margin of average +1.9% and achieves the best performance among all. Further analysis, including hyper-parameter search for Mixup and experiments in the classification task, is presented in the supplementary material Section D.4.

Comparison with State-of-the-Art
Finally, we compare the performance of our proposed method with state-of-the-art losses in two ways: conventional and MLRC evaluation. In conventional evaluation, the combinations of Proxy Synthesis with proxy-based losses improve performance by a large margin in every benchmark as presented in Table 6. For fine-grained datasets with  few categories such as CUB200 and CARS196, the performance gain ranges between a minimum of +0.7% and a maximum of +2.8%, and the average improvement is +1.1%. For large-scale datasets with numerous categories such as SOP and In-Shop, the performance gain ranges between a minimum of +0.4% and a maximum of +1.4%, and the average improvement is +0.9%. Even in the specifically designed MLRC evaluation, Table 4 shows that Proxy Synthesis enhances performance for every metric and benchmark. Extended comparisons with Recall@k for conventional evaluation and performance of seperated 128-dim for MLRC evaluation are presented in the supplementary Section D.6.

Conclusion
In this paper, we have proposed a novel regularizer called Proxy Synthesis for proxy-based losses that exploits synthetic classes for stronger generalization. Such effect is achieved by deriving class relations and smoothened decision boundaries. The proposed method provides a significant performance boost for all proxy-based losses and achieves state-of-the-art performance in image retrieval tasks.

A Proxy-based Losses
In this section, we describe each proxy-based loss, including softmax and its variants used in our study. We follow the same notation from Section 3 in the main paper.
Proxy-NCA: Proxy-NCA loss (Movshovitz-Attias et al. 2017) is the first proxy-based loss in metric learning to resolve sampling issues of pair-based losses. It proposes the concept of proxy, which approximates the original data points so that we do not need to sample informative pairs but can explicitly compute the loss with proxies. Proxy-NCA loss is defined as: where d(a, b) = a − b 2 is the Euclidean distance, p + is positive proxy and P − denotes the set of negative proxies.
SoftTriple: SoftTriple loss (Qian et al. 2019) extends softmax loss with multiple proxies (centers) for each class. It assigns each image to one of the sub-proxies within the class, which has the maximum similarity. We define the relaxed similarity between the sample x and the proxy p as: where s(a, b) = a T b denotes the cosine similarity between feature a and b, p k is a k-th sub-proxy of the class, and γ > 0 is a scaling factor. Then, SoftTriple loss is presented as: where > 0 is a scaling factor and δ > 0 is a margin.
Proxy-anchor: Proxy-anchor loss (Kim et al. 2020) is one of the most recent proxy-based losses in the metric learning task. Unlike the existing proxy-based losses, it exploits each proxy as an anchor and considers its relations of all data in a batch. For each proxy p, let X + p and X − p as the set of positive and negative embedding vectors of p, respectively, where X is divided into two sets of X + p and X − p . Proxy-anchor loss can be formulated as: where γ > 0 is a scaling factor, and δ > 0 is a margin.
Softmax: As formulated in Equation 2 in the main paper Section 3.1, Softmax loss is presented as follows: When we transform the logit (Pereyra et al. 2017) as W T j x i = W j x i cos θ j , where θ j is an angle between the weight W j and the feature x i , the softmax loss can be rewritten with proxy-wise form as: (vi) Normalized Softmax: As defined in Equation 3 in Section 3.1, the normalized softmax (Norm-softmax) loss, which normalizes the weights and feature vectors, is presented as follows: L N orm (X, P ) = − 1 | X | x∈X log e γs(x,p + ) e γs(x,p + ) + q∈P − e γs(x,q) .

B Details of Proxy Synthesis B.1 Proxy Synthesis Algorithm
We present a code-level description of Proxy Synthesis in Algorithm 1. In the method arguments, embeddings and proxies are list of original embeddings and proxies. α is a shape parameter for beta distribution, and µ is a generation ratio by batch size as defined in Section 3.2 from the main paper. First, Proxy Synthesis samples pairs of embeddings and proxies from different classes, respectively. And we generate synthetic embeddings and proxies by linear interpolation. Then, we merge synthetic and original embeddings and proxies to use in loss computation. Note that Proxy Synthesis is extremely easy and simple to implement with only several lines of code. Furthermore, it does not need to revise any code of proxy-based loss and can be used in a plug-and-play manner.

B.2 Induction for Gradient Analysis
We provide a detailed induction of gradient analysis, which is discussed in Learning with Class Relations from Section 3.3. We first show the induction of gradient analysis for the loss of softmax function, and then present the induction of gradient analysis when Proxy Synthesis is applied.
Softmax: The loss of softmax function on (x, p i ), where x is an anchor embedding of input, and p i is the corresponding positive proxy, can be written as follows, where E(p) = e S(x,p) , S(x, p) = s(x, p) x p = x T p and P − = P \ {p i }. Then, the gradient over S(x, p i ) is Besides the gradient mentioned in the original paper, we have also inducted the gradient over S(x, p k ) where p k = p i additionally. The inducted gradient is as follows, .

(xi)
Proxy Synthesis: In order to show the major difference between ordinary sofmax and Proxy Synthesis, we assume that the positive proxy p i of input x is used for generating synthesized proxyp with p j asp = λp i + λ p j , where λ = 1 − λ. Then the loss function in Equation ix should be re-written as follows, In this induction, the gradients over three parameters are interested, which are S(x, p i ), S(x, p j ) and S(x, p k ), where p k = p i , p j . The induction of each gradient is written as follows.
Case 1. the gradient over S(x, p i ): Case 2. the gradient over S(x, p j ): Case 3. the gradient over S(x, p k ): . (xiv)

B.3 Proof of Smooth Decision Boundary
We present a detailed induction for proof of smooth decision boundary, which is discussed in Section 3.3. We show the proof by comparing gradient descent of softmax and Proxy Synthesis.
Gradient Descent of Softmax: The induction of the gradient of loss function L i over embedding vector x in Equation ix is as follows: where, It is obvious that τ i < 0 and τ k > 0. Considering the parameter update is performed by x = x − η ∂Li ∂x , where η is a learning rate, the gradient descent always forces x to be closer to p i and to be distant from other proxies p k .
Gradient Descent of Proxy Synthesis: In order to describe major difference of Proxy Synthesis and ordinary softmax, we consider softmax loss for synthesized pairx = λx + λ x ,p = λp i + λ p j , where (x, p i ) and (x , p j ) are pairs of an embedding and a corresponding proxy,L where E(p) = e S(x,p) and P − = P \ {p i , p j }. It should be noted thatp / ∈ P . Since we suggest to sample λ from Beta(α, α) with small α,p has high chance to be generated either close to p i with λ >> 0.5 or close to p j with λ << 0.5. As the proofs for both cases are equivalent, we assume the first case:x is much closer to x than x . We consider gradient over x because the loss will affect the closer embedding vector more than the other one. The desired gradient is inducted as follows, . (xviii) As mentioned above,x andp are much closer to x and p i respectively, compared to other class. Therefore, E(p), E(p i ) >> E(q) (∀q =p, p i ). Although |p − p i | < |p − q| (∀q =p, p i ), as the difference of exponential function is much larger than the difference of linear function, . With such conclusion, the above gradient may be approximated as follows, where, It is obvious that τ i > 0, implying that by adopting Proxy Synthesis, softmax loss for synthesized pair provides gradient which leads embedding vector not too close to the corresponding proxy p i ; it is also obvious that τ j < 0, implying that softmax loss for synthesized pair provides gradient which makes embedding vector not too distant from the competing proxy p j . In such a manner, Proxy Synthesis prevents embedding vectors lying too close to proxies, which finally leads to the smooth decision boundary.
• For CUB200, we use 5,864 images of the first 100 classes for training and the remaining 5,924 images of the 100 other classes for testing.
• For CARS196, we use the first 8,054 images of 98 classes for training and the remaining 8,131 images of the 98 other classes for testing.
• For SOP, we follow the train and test splits described in (Oh Song et al. 2016), where the first 59,551 images of 11,318 classes are used for training, and the remaining 60,502 images of 11,316 classes are used for testing.
• For In-Shop, we follow the setting described in (Liu et al. 2016) using 25,882 images of the first 3,997 classes for training and 28,760 images of the remaining classes for testing; the test set is further partitioned into a query set with 14,218 images of 3,985 classes and a gallery set with 12,612 images of 3,985 classes.
Note that we do not use the bounding box information for CUB200 and CARS196.

C.2 Implementation
Throughout the experiments, we use the PyTorch (Paszke et al. 2019) framework on a Tesla P40 GPU with 24GB memory. In the "conventional evaluation", we follow the widely used training and evaluation procedure from (Oh Song et al. 2016;Sohn 2016;Kim et al. 2020;Wang et al. 2019a). In the "metric learning reality check (MLRC) evaluation", we follow the specifically designed procedure in terms of fairness from (Musgrave, Belongie, and Lim 2020).
Conventional Evaluation: The input images are augmented by random cropping and horizontal flipping in the training phase, whereas they are center-cropped in the test phase. The size of the cropped images is 224 × 224. For the backbone network, we use ImageNet (Deng et al. 2009) pre-trained Inception network with batch normalization (Ioffe and Szegedy 2015) (BN-Inception). We freeze batch normalization for CUB200 and CARS196 because the images obtained from them are similar to those obtained from ImageNet (Deng et al. 2009), whereas we keep BN training on SOP and In-Shop by following (Qian et al. 2019;Wang et al. 2019a;Kim et al. 2020). With a global average pooling followed by a fully connected layer for dimensional reduction, we set the embedding feature's output dimension to 512. We set the learning rate of 10 −4 for CUB200 and CARS196, and 10 −3 for SOP and In-Shop using the Adam optimizer (Kingma and Ba 2014) and a batch size of 128. The learning rate is decayed by a factor of 0.1 at the 50th epoch for CARS196, 60th epoch for In-Shop, and 20th epoch for CUB200 and SOP. We use α = 0.4 and µ = 1.0 for Proxy Synthesis in every experiment, except that we search for the best values in the experiment of comparison with state-of-the-art. For Proxy-anchor loss, we follow the experimental setting of (Kim et al. 2020), which includes batch size of 180, AdamW optimizer (Loshchilov and Hutter 2017), parameter warm-up, and combination of average and max pooling layers. Considering that papers of softmax variants (Liu et al. 2017;Wang et al. 2018;Deng et al. 2019) do not include hyper-parameters for the aforementioned benchmarks, we search for the best hyper-parameters. In Eq 6, γ = 30.0, m 1 = 1.05, m 2 = 0.0, and m 3 = 0.0 is used for SphereFace (Liu et al. 2017), γ = 23.0, m 1 = 1.0, m 2 = 0.0, and m 3 = 0.1 is used for CosFace (Wang et al. 2018), and γ = 23.0, m 1 = 1.0, m 2 = 0.1, and m 3 = 0.0 is used for ArcFace (Deng et al. 2019). For the rest of the losses, we follow the same hyper-parameters as specified in each paper.

MLRC Evaluation:
In the training phase, we first resize each image to make its shorter side has length 256, then perform a random crop to have a size between 40 and 256, and aspect ratio between 3/4 and 4/3. This image is then resized to 227 × 227 and flipped horizontally with a 50% probability. During the test phase, images are resized 256 and then center cropped to 227. For the backbone network, we use an ImageNet pre-trained BN-Inception network with an output embedding size of 128. All networks are trained with a batch size of 32, RMSprop optimizer, and learning rate of 10 −6 . In order to find the best hyperparameters for loss functions, we conduct 50 experiments of hyper-parameter search where each experiment consists of 4-fold cross-validation. We perform 10 training using the best hyper-parameters and report the average and confidence intervals across these experiments. We report separated (128-dim) and concatenated (512-dim) accuracy, which is concatenated and l 2 -normalized of 128-dim embeddings of the 4 models.

C.3 Input Deformation
For the input deformation experiment described in Section 4.4, we use the imgaug (Jung et al. 2020) python library for image deformation.
• In the cutout experiment, each input image is randomly filled by two grayish pixels that are 20% of the image size.
• For the dropout experiment, a value p from the range of 0 ≤ p ≤ 0.2 is sampled; thereafter, p × 100% of all pixels is dropped from each image. • For the zoom-in and zoom-out experiments, each input image is transformed by zoom-in and zoom-out at scale of 50% and 150%, respectively. • In the rotation and shearing experiments, each image is rotated and sheared at a randomly sampled degree between -30°and 30°. • For the Gaussian noise experiment, noise is sampled once per pixel from a normal distribution N (0, s), where s is sampled between 0 and 0.2 × 255; subsequently, Gaussian noise is added to each image. • For the Gaussian blur experiment, we blur each image with a Gaussian kernel with a sigma of 3.0.

D.1 Training Time and Memory
The additional training time and memory required when using Proxy Synthesis is negligible. Table A indicates that the computation times required for generating synthetics and computing loss are 0.232ms ∼ 0.467ms and 0.872ms ∼ 1.530ms, respectively, which is trivial. This is because synthetics can be generated and the losses can be computed using simple linear algebra. In terms of memory, Norm-softmax loss creates N features for both embeddings and proxies and a N × N similarity matrix for the computation of loss. On the other hand, PS + Norm-softmax loss creates (N + µ × N ) features for both embeddings and proxies and a (N + µ × N ) × (N + µ × N ) similarity matrix for the computation of loss. Considering that the proposed method does not need additional forward propagation for generating synthetics unlike previous methods (Zhao et al. 2018;Duan et al. 2018;Zheng et al. 2019), the additional memory required for the generation of synthetics is negligible.

D.2 Effect of Hyper-parameters
In Figure A, we investigate the effect of the two hyper-parameters α and µ used in Proxy Synthesis by varying the values of α ∈ {0.2, 0.4, 0.8, 1.0, 1.5, 2.0} and µ ∈ {0.2, 0.5, 1.0, 1.5, 2.0}. For α in the interpolation function, smaller values (0.2 ∼ 0.8) show relatively good performance because they lead to a higher chance of generating hard synthetic classes near the original classes, as discussed in Section 4.3 from the main paper. Moreover, the results suggest that when the generation ratio µ is around 1.0, the performance is high. We speculate that this is because too few synthetics by a small value of µ generate an insufficient effect of Proxy Synthesis, whereas too many synthetics by a large value of µ can be a distraction to learn with information of originals. Thus, a value of µ close to 1.0, where the number of synthetics is similar to that of the originals, leads to high and stable performance.

D.3 Robustness to Embedding Deformation
In addition to the embedding deformation experiment in Section 4.4, we include additional experimental results on Normsoftmax and Proxy-NCA losses. Table Ba shows performances of Norm-softmax experiment, which is the base values for Figure 5. We conduct the same experiments with Proxy-NCA loss, as shown in Table Bb. For both loss functions, Proxy Synthesis shows significant performance gain with a similar performance pattern. It demonstrates that the models can obtain more robust embedding features by Proxy Synthesis.

D.4 Comparison with Other Regularizers
Recent works have studied the different requirements of generalization between classification and metric learning tasks Milbich et al. 2020). In the classification task, training and test data share the same class information with i.i.d. training and test distributions; thus, strong focus on the most discriminative directions of significant variance is shown to be advantageous (Verma et al. 2018;Roth et al. 2020). However, for transfer learning, such as metric learning, training data does not share class information with test data. Because of this shift in training and test distribution, recent works Milbich et al. 2020) argue that preserving a substantial amount of directions of significant variance is required for generalization in metric learning. The following experiments include the quantitative comparison with Mixup Verma et al. 2018;Guo, Mao, and Zhang 2019) and Virtual softmax (Chen, Deng, and Shen 2018) in classification and retrieval tasks. They demonstrate that both techniques work well for the classification task, while Proxy Synthesis works the best for the retrieval task, which verifies the different requirements of generalization between classification and metric learning as studied in Milbich et al. 2020).

Experiment on Classification:
Because softmax loss and its variants are included in proxy-based loss, Proxy Synthesis can be used for classification tasks as well. We conduct experiments for comparing the proposed method with Virtual Softmax and Mixup techniques in classification task on four datasets: Cifar10 (Krizhevsky, Hinton et al. 2009), Cifar100 (Krizhevsky, Hinton et al. 2009), SVHN (Netzer et al. 2011), andTinyImagenet (CS231N 2017). We add an implementation of Proxy Synthesis in the official implementation 1 of Manifold Mixup, and use the same scripts for every experiment. For a fair comparison, we use the best hyper-parameters reported in Verma et al. 2018) and search for the best hyper-parameters α and µ of Proxy Synthesis as shown in Table C.
The results are presented in Table D. Intriguingly, Proxy Synthesis improves the performance of every dataset in the classification task. We speculate that it is because the effect of the smoothing decision boundary gives a positive effect on generalization.    (He et al. 2016b).
The gains of Proxy Synthesis are always higher than that of Virtual Softmax because Virtual Softmax is limited by generating one synthetic negative class, while Proxy Synthesis generates multiple synthetic classes, including synthetic embeddings. However, the performance gain of Proxy Synthesis is lower than that of Input and Manifold Mixup except for TinyImagenet. Because Proxy Synthesis considers synthetic classes as different classes from the original classes, this can be a distraction for the network training positional confidence of each original class. On the other hand, Input and Manifold Mixup improve performance by considering linear behavior in-between classes, which is more suitable for the classification task.

Experiment on Retrieval:
To further compare the proposed method with other regularizers, we train networks for image retrieval tasks on Norm-softmax loss with different regularizers. For a fair comparison, we search for the best performing value of α in the Input and Manifold Mixup as shown in Table E, and use α = 0.4 and µ = 1.0 for Proxy Synthesis. In Virtual Softmax, we observe that W T virt X i is much bigger than that of positive class W T yi X i because of the same direction of vectors W virt and X i and it fails to train the network. To handle these issues, we clip the similarity with a virtual negative class to be under 10 for softmax. Moreover, Virtual Softmax is not applicable to Norm-softmax loss because W virt will always be constant 1. The detailed analysis of comparison with other regularizers in the retrieval tasks is provided in Section 4.5 from the main paper.

D.5 Visualization of Embedding Space
We present t-SNE visualizations (Maaten and Hinton 2008) of models, which are trained with PS + Norm-softmax loss on CUB200 and SOP in Figure B and C, respectively. They show a similar pattern with Figure 3 by placing unseen test embeddings in-between the clusters of train embeddings. With such a pattern, synthetic classes, generated in-between train embeddings, would mimic unseen classes during the training phase. For further analysis, we provide t-SNE visualizations by each epoch of a model, which is trained with PS + Norm-softmax loss on CARS196 in Figure

D.6 Comparison with State-of-the-Art
This section contains the extended comparison with state-of-the-art per dataset in both conventional and MLRC evaluation protocols. The conventional evaluation includes more Recall@k evaluation and existing methods for Table 6 in the main paper. The MLRC evaluation includes the performance of separated models with a 128-dimensional embedding feature for Table 4 in the main paper. The corresponding tables for each dataset are Table F and G for CUB-200-2011(Wah et al. 2011, Table H and I for CARS196 (Krause et al. 2013), Table J and K for Standford Online Products (Oh Song et al. 2016), and Table L for In-Shop Clothes (Liu et al. 2016). In conventional evaluation, Proxy Synthesis improves the performance of proxy-based losses for most Recall@k except for a minority of cases. Compared to the ensemble, sample generation, and pair-based methods, the proposed method outperforms all cases in every dataset with a large margin. In MLRC evaluation, performances of both concatenated 512-dim and separated 128-dim are increased in every metric and dataset. Considering MLRC evaluation is designed with respect to fairness, the result demonstrates that the proposed method enhances generalization ability for pair-based loss in general.           , V16 for VGG16 (Simonyan and Zisserman 2014) and BN for Inception with batch normalization (Ioffe and Szegedy 2015).