Frequency-aware SGD for Efficient Embedding Learning with Provable Benefits
Authors: Yan Li
Dhruv Choudhary
Xiaohan Wei
Baichuan Yuan
Bhargav Bhushanam
Tuo Zhao
Guanghui Lan
Venue: ICLR 2022 Poster (2022)

Abstract: Embedding learning has found widespread applications in recommendation systems and natural language modeling, among other domains. To learn quality embeddings efficiently, adaptive learning rate algorithms have demonstrated superior empirical performance over SGD, largely accredited to their token-dependent learning rate. However, the underlying mechanism for the efficiency of token-dependent learning rate remains underexplored. We show that incorporating frequency information of tokens in the embedding learning problems leads to provably efficient algorithms, and demonstrate that common adaptive algorithms implicitly exploit the frequency information to a large extent. Specifically, we propose (Counter-based) Frequency-aware Stochastic Gradient Descent, which applies a frequency-dependent learning rate for each token, and exhibits provable speed-up compared to SGD when the token distribution is imbalanced. Empirically, we show the proposed algorithms are able to improve or match the performance of adaptive algorithms on benchmark recommendation tasks and a large-scale industrial recommendation system,  closing the performance gap between SGD and adaptive algorithms. Our results are the first to show token-dependent learning rate provably improves convergence for non-convex embedding learning problems.

Published conference paper at ICLR 2022
FREQUENCY-AWARE SGD FOR EFFICIENT EMBED- DING LEARNING WITH PROVABLE BENEFITS
Yan Li
Dhruv Choudhary
Xiaohan Wei
ISyF, Georgia Tech y11939@gatech.edu
Meta
Meta ub Poimeteerrf com
cy
Baichuan Yuan Meta beyuan fb. com
Bhargav Bhushanam
Tuo Zhao
Meta
ISyE, Georgia Tech
bbhushaname fb. com
tourzhao@gatech. edu
Guanghui Lan
ISyE, Georgia Tech
george lan@isye. gateyy...attch.....
ABSTRACT
Embedding learning has found widespread applications in recommendation sys- tems and natural language modeling, among other domains. To learn quality em- beddings efficiently, adaptive learning rate algorithms have demonstrated supe- rior empirical performance over SGD, largely accredited to their learning rate. However, the underlying mechanism for the efficiency of token- dependent learning rate remains underexplored. We show that incorporating fre- queney information of tokens in the embedding learning problems leads to prov- ably efficient algorithms, and demonstrate that common adaptive algorithms im- plicitly exploit the frequency information to a large extent. Specifically, we pro- pose (Counter-basee) Frequency-awe plies a trequency-dependen learning rate for each token, and exhibits provable speed-up compared to SGD when the token distribution is imbalanced. Empir- ically, we show the proposed algorithms are able to improve or match adaptive algorithms benchmark recommendation tasks and large-scale industrial rec- ommendation system, closing the performance gap between SGD and adaptive al- gorithms, while using significantly lower memory. Our results are the first to show token-dependent learning rate provably improves convergence for non-convex em- bedding learning problems.
Stochastic Gradient Descent, which ap-
INTRODUCTION
Embedding learning describes a problem of learning dense real-valued vector representation for cat- egorical data, often referred token (Pennington al., 2014; Mikolov al., 201 2013a;b). Good quality embeddings can capture rich semantic information of tokens, and thus serve as the corner- stone for downstream applications (Santos et al., 2020). Due to their significant impact on model performance and large memory footprint (21.8% of total parameters for BERT (Devlin et al., 2018), 95% for industrial recommenders in Section 4), how to learn quality embedding vectors efficiently forms an important problem in applications, including recommendation systems and natural lan- guage processing.
Empirically, adaptive algorithms (Duchi et al., 2011; Kingma & Ba, 2014; Reddi et al., 2019) have witnessed significant successes, yielding state of the art performance both industrial-scale recom- mendation systems and natural language model (Guo et al., 2017; Zhou et al., 2018b; Devlin et al., 2018; Liu et al., 2019). Stochastic gradient descent (SGD), on the other hand, has struggled to keep up, often yielding much slower convergence and low quality models (Liu et al., 2020; Zhang al., 2019) (see also Figure 2). The sharp contrast on the efficiency of adaptive algorithms and SGD is particularly distinctive, SGD is the typical choice of optimization algorithms in the other domains of machine learning, such as vision/image related tasks (He et al., 2016; Goyal et al., 2017).
Work done during internship Meta.

---

Published conference paper at ICLR 2022
The common belief behind the empirical edge of adaptive learning rate algorithms over SGD is that the former ones exploit sparsity of high dimensional feature. Specifically, feature in a typical embedding learning problem comes in the form of one/multi-hot encoding of tokens (e.g. wordpiece in NLP and user/item in recommendation systems), which leads to sparse stochastic gradient that has only non-zero values for tokens within the mini-batch. In addition, token distributions of real world data often highly imbalanced and satisfy the power-law property (Piantadosi, 2014; Celma, 2010; Clauset et al., 2009), and infrequent tokens are widely believed to be more informative to model learning. Thus adaptive algorithms can pick up information from the infrequent tokens more efficiently, as they can schedule a higher learning rate for the infrequent tokens (Duchi et al., 201 I).
Despite the appealing intuition, there is a significant theory-practice gap on the empirical superiority of adaptive learning rate algorithms over SGD, and no developed theories can explicitly justify the previous intuition. Better dimensional dependence of adaptive algorithms has only been shown in the convex setting (Duchi et al., 2011), 1), which hardly generalizes to even the simplest practical models in embedding learning problems (e.g.. Factorization Machine, Rendle (2010)), whose loss landscape is non non-convex. For non-convex settings, most theoretical efforts have been devoted to analyzing adaptive learning rate algorithms for general non-convex objectives, which yield subpar convergence rate compared to standard SGD (Ward et al., 2018; Défossez et al., 2020; Chen et al., 2018; Zhou et al., 2018a). In fact, the standard SGD has been recently shown to be minimax optimal for non-convex problems (Drori & Shamir, 2020; Arjevani et al., 2019), and thus not improvable in general. Moreover, since adaptive algorithms are only implicitly exploiting frequency information, and if the intuition indeed holds true, one might naturally wonder whether we can instead develop an adaptive learning rate schedule that explicitly depends on frequency information. Motivated by our previous discussions, we raise and aim address the following questions
Questions
Can we design a frequency-dependent adaptive learning rate schedule? Can we show prov- able benefits over SGD?
We answer the previous question by showing that token frequency information can be leveraged to design provably efficient algorithms for embedding learning. Specifically,
Our contributions.
We propose Frequency-aware Stochastic Gradient Descent (FA-SGD), simple modification to standard SGD, which applies a loken-dependent learning rate that inversely proportional to the frequency of the token. We also propose a variant, named Counter-based Frequency-aware
Stochastic Gradient Descent (CF-SGD), which is able to estimate frequency in an online fashion,
much similar to Adagrad (Duchi et al., 2011) and Adam (Kingma & Ba, 2014).
Theoretically, we show that both FA-SGD and CF-SGD outperform standard SGD for embedding learning problems. Specifically, they are able to significantly improve convergence for learning infrequent tokens, while maintaining convergence speed for frequent tokens. To the best of our knowledge, our proposed algorithms are the first to show provable speed-up over standard SGD for non-convex embedding learning problems. This is in sharp contrast with other popular adaptive learning rate algorithms, whose empirical performance can not be explained by existing theories. Empirically, we conduct extensive experiments on benchmark datasets and large- scale industrial recommendation system. We show that FA/CF-SGD is able to significantly improve over SGD, and improves/matches popular adaptive learning rate algorithms. We also observe the second- order moment maintained by Adagrad and Adam highly correlates with the frequency information, demonstrating intimate connections between adaptive algorithms and the proposed FA/CF-SGD.
1.1 RELATED LITERATURE
Adaptive algorithms for non-convex problems. There has been fruitful line of research on an- alyzing the convergence of adaptive learning rate algorithms in non-convex setting. These results aim to match the convergence rate of standard SGD given by (1/VT)) (Ghadimi & Lan, 2013), however often with additional factor of log T' (Ward et al., 2018; Défossez et al., 2020; Chen et al., 2018; Reddi et al., 2018), or with worse dimension dependence (Zhou et al., 2018a) for smooth problem (assumed by almost all prior works). Moreover, all existing works aim to analyze the vergence for general non-convex problems, ignoring unique data features in embedding learning problems, where adaptive algorithms are most successful. We explicitly take account into the spar-
2

---

Published conference paper at ICLR 2022
Algorithm 1 Frequency-aware Stochastic Gradient Descent
Total iteration number T, token frequency {pE and learning rate schedule (EX,eEX) specified by (7).
Input:
Initialize: @ E Nxd, sample Unif([T)), fort -.... (1) Sample (i) ~ D, calculate st. -V,, e(O;,: : O2. Viesi) Sj. Vos, ElOie 025 Wh
(2) Update parameters
0 =0, 0% - The 0ct1 = 0f Vi U
-h
0, 00 I'e 85+1= = =0 Vj E V.J #
end for Output: O
sity of stochastic gradient, and token distribution imbalancedness into the design and analysis of our proposed algorithms, which are the keys better convergence properties.
Adaptive algorithms and SGD. To the best of our knowledge, the study on understanding why adaptive learning rate algorithms outperform SGD very limited. Zhang al. (2019) argue that BERT pretraining (Devlin et al., 2018) has heavy-tailed noise, implying unbounded variance and possible non-convergence
SGD. Normalized gradient clipping method proposed therein and converges for family of heavy-tailed noise distributions. Our results focus by showing that imbalanced token distribution is an important factor that can be leveraged to design more efficient algorithms for embedding learning problems. Our result also does not rely the noise to be heavy-tailed for the convergence benefits of the proposed FA/CF-SGD to take effect.
different direction
Notations: For vector/matrix, use ||-|| to denotes its Ey-norm/Frobenuus norm. We use ||-112 to denote the spectral norm of a matrix.
2 PROBLEM SETUP
We consider an embedding learning problem which aims to learn user and item embeddings through their interactions. We denote U as the set of users, and as the set of items, and let X = U V denote the union, referred to tokens throughout the rest of the paper. We assume |X| N, i.e. the total number of user and item is N. For the case of presentation, we always use letter to index user set U, letter j index item set V. and letter i to index the union set X. The embedding learning problem can be abstracted into the following stochastic optimization problem:
f()) = E(j))D (e (;;05); G xa
min
Σ iEUJEV
((.,))(00,00::..)
(1)
Here (i,j) denotes the user-item pair sampled from the unknown interaction distribution D, O,, 8, E Idd (the i, j-th row θ) denotes their embedding vectors respectively, and the loss ((6,, 8y: Miy) denotes the prediction loss for their interaction Vig E {-1,+11 (e.g., logistic loss). We further let
Ps = Σ D(i.)) ViEU; Pj = D(,,), VjeV,
(2)
JEV
IEU
denote the marginal distribution over U and V.
Remark 2.1. Our analysis also allows treatment of additional network structure (with parame- ters denoted by W) that takes nonlinear transformation of embedding vectors, e.g., f(O, W) ((,,))-((O; 0,; W; W;ys)) We omit their explicit treatment for presentation simplicity. In addition, although we mainly discuss in the context of recommendation, our analysis and results only relies on sparsity of stochastic gradient and the imbalancedness of token distributions, which allow one to extend our results to other embedding learning problems (c.g., language model pretraining).
The full algorithmic descriptions of our proposed Frequency-awart Stochastic Gradient Descent (FA-SGD) algorithm are presented Algorithm 1. Note that randomly outputting historical iter- ate is commonly adopted in literature for showing convergence of stochastic gradient descent type algorithms for non-convex problems (Ghadimi & Lan, 2013). In practice, we can simply use the last iterate @ as the output solution. In addition, Section 3.3 presents CF-SGD (Algorithm 2), which does not need the token distribution as the input and can estimate it in an online fashion.
3

---

Published conference paper at ICLR 2022
At iteration t, FA-SGD samples (it. D, and ob- tain the sparse stochastic gradient g¹ defined in (3). Note that only the ig-th and je-th row of ge are non-zero. One can readily verify that jt) [9t] Vef(@'). Going forward, we will denote V the k-th row of gradient f(("), and of as the k-th row stochastic gradient 9r- Note that we have
0 Ve. E00,, S3 Veeese)
9t
(3)
Va,, elos Dirsee
0
E5 [of, lée = 1] V///ps, E, [9]] 1ie = VfJppj
(4)
We further denote 6%
1 f gf for all & X. Then by definition E [6 1 10=01 =] and
pt E
E 1 ]] 0 for all i U. EEV. V. We pose the following assumptions the its variance.
Assumption (Bounded conditional variance). We assume that the variance of 8% is bounded. That is, there exists {o Mex, such that
16 11 ii = S sof E [16,,, = soj ViEU,jeV.
(5)
Assumption I allows us to provide finer characterization on the variance of stochastic gradient compared typical variance assumption literature. To illustrate, recall that standard assumption in the stochastic optimization literature assumes Var(g") = Ve g²1]2 I o² for some uni- versal constant O. Consider an extreme setting, where have exact gradient for the sampled user-item pair, i.c., gi, 1 Vf, and oj. - Vf then we have σ = for all E X. In Pic
contrast, the variance of g" is still non-zero. In general setting, can bound the variance as shown in the following proposition. Note that the variance lower bound arises naturally form the extreme sparsity of the stochastic gradient.
Proposition 2.1. Given Assumption I, we have
E(1/r - 1) 1| Var(g') S
Σ REX
PKo +
- 11)
(6)
REX
kEX
Assumption (Smoothness of prediction loss), We assume E(U, v; yy is symmetric w.r.t. u and v for any y {1,,++), and there exists I >> 0 such that ViV
I, (
L.
The assumption the symmetry of é is readily satisfied by almost all neural network architecture. In essence, this assumption only requires that the parameterization of embedding vector is token agnostic. On the other hand, the spectral upper bound the Hessian matrix standard assumption in optimization literature.
THEORETICAL RESULTS
We first present the convergence results of FA-SGD and standard SGD for embedding learning problem formulated in (1), and discuss the advantage that FA-SGD offers when the token distribution {ps] is highly imbalanced. We further propose variant, named CF-SGD, which estimate frequency information in an online fashion and still provably enjoys the benefits of FA-SGD.
3.1 CONVERGENCE OF FA-SGD AND STANDARD SGD
Theorem 3.1 (FA-SGD). With Assumption 1 and 2, take learning rate policy to be
t min min (1/(4L).a//TPp)
(7)
where denotes the total mumber of iterations, and a = - pio?), we have
E V = -11(1199)-) + vPEy Enex mot (((")))) Vk X.
(8)
VT
4

---

Published conference paper at ICLR 2022
Remark 3.1 (Connection with Stochastic Block Coordinate Descent). Our FA-SGD shares some similarities with Stochastic Block Coordinate Descent (SBCD) (Nesterov, 2012; Dang & Lan, 2015; Richtárik Takáč, 2014) applied to problem (1), in the sense that each iteration we sample certain blocks of variables (0.,, l) in our case), and only update the sampled blocks by following its stochas- tic gradient. Different from SBCD, the stochastic gradient of the block variable gi, in the FA-SGD is biased, shown in (4). Note that with unbiased stochastic gradient, SBCD method typically con- verges slower than standard SGD by a factor that can be as large as number of blocks. As a concrete example, when the token distribution is uniform, SBCD converges slower than standard SGD by factor of X J. hence slower than FA-SGD by factor of |X] from Corollary 3.1 developed later.
Recall that from Proposition 2.1, the variance of stochastic gradient is heavily influenced by the population gradient Vef(@), and can be huge whenever the population gradient is, presumably in the early phase of training. This relationship is also supported by empirical findings in Zhang et al. (2019) (Figure 2a), where the authors show that for BERT pretraining, the noise distribution in stochastic gradient g" is highly non-stationary, which has large variance in the beginning of the training and smaller variance at the end of training. Since existing analysis of SGD in literature assumes a constant variance bound for the stochastic gradient, our observation in Proposition 2.1 requires an alternative analysis of SGD for problem (1).
To obtain the convergence rate of standard SGD in the presence of iterate-dependen variance (6), our key insight is to tailor the convergence analysis to the sparsity of the stochastic gradient for problem (I). We show the convergence of standard SGD the following.
Theorem 3.2 (Standard SGD). With Assumption and 2, take learning rate policy be n/
)(0))- we have where T denotes the total number of iterations, and a
min+
4T. vT
L Liex Ploy'
E V 0 (1(1119)) + 1f
E
(9)
Note that both FA-SGD and standard SGD attain a rate of OL/vVT). Compared to existing rates of standard SGD (Ghadimi & Lan, 2013), we do not require constant variance bound on stochastic gra- dient, as we have discussed above. Compared to existing rates of adaptive learning rate algorithms (Zhou et al., 201 8a; Chen et al., 201 8), both rates obtained here exhibits dimension-free property. We emphasize here that due to the dimension free nature of the bounds for both SGD and FA-SGD, dimension, which is the main moti-
we do not claim the proposed FA-SCE AGD has better dependence vation of adaptive algoritims (Duchi et al., 2011: Kingma & Ba, 2014; Reddi et al., 2019). Instead, the major difference the convergence of FA-SGD (8) and that of standard SGD (9) is that the for- mer one is token-dependent.. Specifically, for FA-SGD, each token & E X has its own convergence characterization, while all the tokens have the same convergence characterization in the standard SGD. We first make a simple observation stating the equivalence of FA-SGI and standard SGD, when the token distribution {pw]kex is uniform.
Corollary 3.1 (Uniform Distribution). Suppose the user distribution {ps Yieu and item distribution {pshev is the uniform distribution. Then FA-SGD and standard SGD is equivalent to each other, in terms of both algorithmic execution and convergence rate.
3.2 WHEN DOES FA-SGD OUTPERFORM STANDARD SGD?
We show FA-SGD shines when the token distribution (px heex defined in (2), is highly imbalanced. Before we present detailed discussions, we make an important remark that highly imbalanced token distributions are ubiquitous in social systems, presented in the form power-law. Examples of such distributions include the degree of individuals in the social network (Muchnik et al., 2013); the frequency of words in natural language (Zipf, 2016); citations for academic papers (Brzezinski, 2015); number of links on the internet (Albert et al., 1999). For more discussions on plwer-law distributions in social and natural systems, we refer readers to Kumamoto & Kamihigashi (2018).
In Figure 1c. 1d we plot the user and item counting distribution of Movielens -MM dataset. One could clearly see that the user and item distributions are highly imbalanced, with small percentages of users/items taking up the majority of rating records. We defer details on the skewness of token distributions for Criteo dataset to Appendix C.
5

---

Published conference paper at ICLR 2022
top User
0.3
tup User
2002
3030-
0.2
prequency
1502
Cousts
2220
1920
8,0
12 15
16
0.0
3
9
12
2000
4002
2000
2003
2002
5005
Prequency Rank
Proquency
USer Pack
Ibm flakk
(a) Exponential Tail
(b) Polynomial Tail
(c) User counts
(d) Item counts
Figure 1: Token distribution with an exponential and polynomial tail, and the user/item counting distributions for Movielens-IN IM dataset.
To illustrate the comparative advantage of FA-SGD when the token distribution {ps hee is highly skewed. We consider two classes of distribution families with different tail properties, one with exponential tail, and one with polynomial tail.
Corollary 3.2 (Exponential Tail). Let U
(in V - (imm where in denote the user with n-th largest frequency, and jm denote the item with the m-th largest frequency. Suppose
(10) for some > Define UT as the set users whose frequencies are within e-factor the highest
pi,, x exp(-Tn), Pim x exp(-Tm), Vn [[U]], m E [[V]]
frequency: UT = {in : S }}, and VT similarly as VT {im m S }}. We refer to UT as the top users, and VT as the top items.
Then given [V] 2 } the proposed FA-SGD, compared to standard SGD:
(1) Obtains the same rate of convergence, for the top users Ur and top items Vr:
(2)
EE
V fT,
ll can converge faster by a factor of Q {exp (r(n -UTTl)) for in E U UT:
(3) E fm can converge faster by a factor of S2 {exp (T(m - [Vrl))) for in E V Vrr
We remark that [v] > 1 is very mild condition, as it only requires that the most infrequent user/item should have its frequency smaller than the most frequent user/item by at least factor of e. i.e., the non-top user/item set U Ur, V Vir is nonempty. This is readily satisfied by the token distributions recommendation systems and natural language modeling (Celma, 2010: Zipf, 2016), where the lowest frequency is at least orders of magnitude smaller than the highest frequency. The factor of e in defining Ur, VT can also be readily replaced by any constant larger than 1.
From Corollary 3.2, we can see that FA-SGD improves significantly over standard SGD for user/item distribution with exponential tail. Specifically, FA-SGD achieves the same convergence rate of top users/items compared to SGD, meanwhile it significantly improves the convergence of the non-top users/items. Moreover, the strength of such an improvement increases exponentially as we move towards the tail users/items.
( Corollary 3.3 (Polynomial Tail). Let U [ta) I- V= [-mm) 1 where in denote the user with n-th largest frequency, and jm denote the item with the m-th largest frequency. Suppose
Pi, n Pim m,, Vn [[U]], E [[V]]
(11)
for some v 2 2. Define UT as the set of users whose frequencies are within 2-factor from the highest frequency: UT fin nn 2 1/16], and VT similarly as VT = {im : m m- 2 1/16]. We refer to UT as the top users, and VT as the top items.
Then given [U], 161/v, the FA-SGD, compared to standard SGD:
(1) Obtains the same rate of convergence, for the top users UT and top items Vr;
(2)
E V fT, 1| can converge faster by a factor of f { converge faster by a factor of { [[V]]
for each in E U Ur:
[orl
(3) E VJ
for each jm V Vr.
We remark that polynomial tail (37) is also the prototypical example of the power law distribution class for modeling social behaviors (Kumamoto & Kamihigashi, 2018). The constant 2 in the condi- tion v 2 2 can be replaced by any constant strictly larger than 1, with slight changes to the constant factor in the statements of the corollary.
From Corollary 3.3, we can see that FA-SGD improves significantly over standard SGD for user/item distribution with polynomial tail. Specifically, FA-SGD achieves the same convergence rate of top

---

Published conference paper at ICLR 2022
Algorithm 2 Counter-based Frequency-aware Stochastic Gradient Descent
Input: Total iteration number T. Initialize: @ E IK N xd, counter sample T Uni((((/2,...,T)) for /. .. do
(1) Sample (t) ~ D, calculate of, Ve., E(0),: :e.:::,..... Vee.se)) gj. = Ve,, E(O,,, Bse
(2) Compute counter- counter-based learning rate fi (ct,), , 7/. (c),) specified by (12)
(3) Update parameters
0 0 4
1 R. 0+ 0r. WEU,i #
0 = 0f. T3 @t = 0j. Vj V.J j d
(4) Update counters
2+1 = c, + 1, c 141 = d, Vi ViEUS U4
4.
4+1 c + 1, d = e, NjEV,
end for
Output: O
users/items compared SGD, meanwhile it significantly improves the convergence of the non-top users/items. Moreover, the strength of such an improvement increases in polynomial order as we move towards the tail users/items.
3.3 ONLINE ESTIMATION OF FREQUENCY INFORMATION
In certain application scenarios, the token distribution {pE] can be unknown in advance of learning. To apply FA-SGD, one needs to employ preprocessing step in order to estimate the token distribution to a high accuracy, and then run the algorithm with estimated token distribution. Such a preprocessing step often requires additional human efforts and data. To remove such undesirable preprocessing step, below we present an online variant of FA-SGD, which uses the counter of tokens collected during training to estimate the token distribution dynamically. We show that the proposed Counter-basee Frequency-awe -wwae Stochastic Gradient Descent (CF-SGD) is able to retain the benefits of FA-SGD despite unknown token distribution.
Theorem 3.3 Mounter-based FA- FA-SGD). In addition to Assumption I and 2, suppose IV < G.
Take counter-based learning rate policy in Algorithm to be
Th (c)) min 1/(4T), 1/ TP
Fh = tkE X
(12)
where T denotes the total number of iterations, a = /all (LE/ pio?) and My = f(00) f + Σtex p L, we have
V = - LM,, +
VPL Eiex piot ((f(00))))
VP (iex Eioi)
vPcl
(13)
/T
/T
for T max minuex 1.
2log G log( (1(1/ Vpx)
Pk
We believe the assumption on gradient bound ff S G is not strictly necessary and can re- moved with more refined analysis. Nevertheless, the requirement on T only logarithmically depends on the gradient bound G. addition, we highlight that the convergence characterization in Theorem 3.3 is still -okenddependent. Specifically, we can show that despite not knowing token distribution beforehand, CF-SGD can gain the same advantages that FA-SGD enjoys over SGD.
Corollary 3.4 (Exponential Tail). Suppose we have the same set of conditions given in Corollary 3.2, and a // (f(eo) f*) S 1. Define UT as the set of users whose frequencies are within e- factor from the highest frequency: Ux = (in : S }}, and Vy similarly as Vi = {im : m S 4 We refer to UT as the top users, and Vr as the top items.
Then given |U).IVI }, the proposed CF-SGD, compared to standard SGD:
(1) Obtains the same rate of convergence, for the top users UT and top items Vr:
(2) EE S[, can converge faster by a factor of {exp (7(n (U+())) for in E U Ur:
7

---

Published conference paper at ICLR 2022
(3) EE V 1| can converge faster by a factor of St {exp (r(m [Vrl))) for in E V VT. Corollary 3.5 (Polynomial Tail). Suppose we have the same set of conditions given in Corollary 3.3, and a / (-( S 1. Define Ur as the set of users whose frequencies are within 2-factor from the highest frequency: UT = {in - 2 1/16], and Vr similarly as Vr = {im m 2 1/16]. We refer to UT as the top users, and VT as the top items.
Then given |U|, 2 161/", the FA-SGD, compared to standard SGD:
(1) Obtains the same rate of convergence, for the top users Uy and top items Vr:
(2) E V sT. can converge faster by a factor of
for each in E U \ UT:
[rrl
for each jm E V V\ Vr. The proofs of Corollary 3.4 and 3.5 follow similar lines as in the proofs of Corollary 3.2 and 3.3, which we defer to Appendix D
(3) E V l can converge faster by a factor of
m [r
4 EXPERIMENTS
We conduct extensive experiments to verify the effectiveness of our proposed algorithms and our developed theories, on both publicly available benchmark recommendation datasets, and a large- scale industrial recommendation system. Additional experiments learning Word2 embed- dings (Mikolov et al., 2013a) are presented in Appendix B, demonstrating the general applicability of the FA/CF-SGD. We list key elements of our experiment setup for benchmark datasets below.
Datasets: MovieL M (Grouplenss 2003) and Criteo ITB Click Logs dataset (Criteo, 2014).
Models: Factorization Machine (FM) (Rendle, 2010), and DeepFM (Guo et al., 2017).
Metric: Training loss (cross-entropy loss), and test AUC (Area Under the ROC Curve).
Baseline algorithms: SGD, Adam (Kingma & Ba, 2014), Adagrad (Duchi et al., 201 1). Note that Adam and Adagrad are widely popular in training recommendation systems and language models.
We also empirically verify that the token distributions for both Movielens- 1M (Figure 1) and Criteo (Appendix C) dataset are highly imbalanced, with most of the token distributions having clear polynomially or exponentially decaying tail.
Since CF-SGD does not require frequency information, which is huge practical benefit compared to FA-SGD, in our experiments we mainly evaluate our proposed CF-SGD against the baseline algorithms. To ensure fair comparison, for each dataset and model type, we carefully tune the learning rate of each algorithm for best performance. We apply early stopping and stop training whenever the validation AUC do not increase for 2 consecutive epochs, which is widely adopted in practice (Takács et al., 2009; Dacrema et al., 2021).
FM
FM
Desp!M
DeeptrM
0.2
Adam
Adart
0.03
Acagmad SOD
Magnd
0.75
0.73
3
3077
0.03
0.5
0.5
5.6
Arbummd
Ct 500
Adum
0.6
0.90
Adas S0D
Adagrad
0.4
15000
20000
3002
12000
20100
5050 7530
2500
5000
20200
Dovalien
Recutia
Dusaliu
(a) Training loss
(b) Validation AUC
(c) Training loss
(d) Validation AUC
Figure 2: Movielens- 1M dataset with FM and DeepFM model. CF-SGD significantly outperforms
standard SGD, and is highly competitive against Adam, Adagrad.
Movielens-IN IMM: We can observe from Figure 2 that for FM and DeepFM model: (1) SGD yields the slowest convergence in training loss and AUC. (2) The proposed CF-SGD yields significantly faster convergence than SGD for training loss. In addition, CF-SGD converges even faster than the adap- tive learning algorithms in the carly stage of training: (3) All the algorithms eventually reaches peak AUC around 81.0%, while CF-SGD attains the peak AUC much faster than baseline algorithms. These empirical observations help us confirm the effectiveness of the proposed CF-SGD algorithm. We further make an empirical observation that draws a close connection between adaptive algorithms and CF-SGD. We plot the second-order gradient moment maintained by Adagrad and Adam against the estimated frequency maintained by CF-SGD. Surprisingly, the second-order gradient moment quickly develops a close-to linear relationship with the frequency information accumulated by CF- SGD (Figure 3a,3b). This observation suggests that Adagrad and Adam are exploiting frequency information implicitly to large extent.
8

---

Published conference paper at ICLR 2022
Criteo: We observe qualitative behavior of CF-SGD similar Movielens- 1M dataset, as can be seen in Figure 3c,3d, 4a,4b.
IM
DuepFM
FM
FM
0.91
Adas
0.6
0.8
CP SCD
0.0
0.7
2.5
Alagrod
0.7
0.6
Alun
0.6
Alan
Adagrod
0.
Adas
Adagind
1.0
9.5
90D
Alagmd
CP SCD
2300
5900 7000
10000
12500
2000
6000
7500
10000
(a) Correlation
(b) Correlation
(c) Training loss
(d) Validation AUC
Figure 3: (a-b) Second-order gradient moment correlates linearly with frequency maintained by
CF-SGD; (c-d) Comparisons on Criteo dataset with FM model.
DM
DeepFM
Industrial Recommender Sys.
NEICP-SDD (D1C)-SDD NE/Naagnnd/
dndustrial Recommender Sys.
Maraa
0+
0.800-
Adagrad
0.00
SGD
5GD
Thaining
-0.02
0.5
0.700
50D
-0.03
0.2
0
50D
105
0.0
2.0
Eeevttios
3.5
1e10
21-
1.0
Iheratoon
2.0
1n10
(a) Training loss (b) Validation AUC
(c) Train NE Curve
(d)
Train NE Diff %
Figure 4: (a-b) Comparisons Criteo dataset with DeepFM model; (c-d) Comparisons on
industrial-scale recommendation dataset with an ultra-large recommender model.
Industrial Recommendation System: We train an ultra-large industrial recommendation model with the proposed CF-SGD. The training data contains 10 days of user-item interaction
Alg
NE
Difi %
Adagrad
0.78643
0.0
CF-SGD
0.78628
-0.02
records, with 2.5 billion examples per day (25 billion exam-
Table 1: Eval NE Diff %
ples in total). We use around 800 features, with ~ 100 million
average number of tokens per feature. We compare CF-SGD with Adagrad, which has been carefully tuned in production usage. For both algorithms, we use batch size of 64k and do one-pass training. Different from benchmark academic datasets, we use Normalized Entropy (NE) as the evaluating metric (He et al., 2014) (smaller is better), which is the cross- cross-entropy loss normalized by the entropy of background click through rate. Note that due to numerous iterations of the production model, any relative improvement
0.02% is considered to be significant. In Figure 4c, 4d we compare the training NE curve CF-SGD and Adagrad, we can see that CF-SGD shows faster convergence than Adagrad (see NE difference % in Figure 4d). From Table 1 we can observe that CF-SGD also improves over Adagrad during the serving phase.
Memory Efficiency: On top of the above empirical evidences showing that CF-SGD learns fast faster than standard SGD, and comparable (if not better) to adaptive algorithms, we further highlight that CF-SGD learns cheap. Specifically, adaptive algorithms require additional memory to store history information for each parameter. For an embedding table of size N x d (N tokens, d being embedding dimension), the memory needed is least 3NV x d for Adam (fist/second-order gradient moment), and 2N x d for Adagrad (second-order gradient moment). In sharp contrast, CF-SGD only requires N additional memory, for storing the estimated frequency. Since the choice of typical embedding dimension d exceeds 64 (Yin & Shen, 2018), adaptive algorithms require memory at least twice the size of the embedding table, while CF-SGD requires negligible memory overhead. Note the industrial recommendation model in our experiments has size over multiple terabytes, with above 95% of consumed by embedding tables. Doubling the memory footprint by using standard Adam/Adagras is infeasible in terms of both engineering and environmental concern.
CONCLUSION
We propose (Counter-based) Frequency-awan SGD for embedding learning problems, which adopts frequency-depente learning rate schedule for each token. We demonstrate provable benefits that FA/CF-SGD enjoy over standard SGD for imbalanced token distributions, with extensive exper- iments supporting our theoretical findings. Our empirical findings also suggest that adaptive al- gorithms can implicitly exploit frequency information and hence share close connections with the proposed algorithms, this connection might be helpful in the direct analysis of adaptive algorithms for embedding learning problems, which we leave as a future direction.

---

Published conference paper at ICLR 2022
ACKNOWLEDGEMENTS
We deeply appreciate Aaron Defazio and Michael Rabbat for their valuable feedbacks and insightful discussions. We are also grateful to Yuxi Hu for his help on production model experiments.
REFERENCES
Réka Albert, Hawoong Jeong, and Albert-László Barabási. Diameter the world-wide web. nature, 401(6749):130-131 1999.
Yossi Arjevani, Yair Carmon, John C Duchi, Dylan Foster, Nathan Srebro, and Blake Woodworth. Lower bounds for non-convex stochastic optimization. arXiv preprint arXiv:1912.02365, 2019.
Michal Brzezinski. Power laws in citation distributions: evidence from scopus. Scientometrics, 103 (1):213-228, 2015.
Öscar Celma. The long tail in recommender systems. In Music Recommendation and Discovery, pp. 87-107. Springer, 2010.
Xiangyi Chen, Sijia Liu, Ruoyu Sun, and Mingyi Hong. On the convergence of a class of adam-type algorithms for non-convex optimization. arXiv preprint arXiv:1808.02941, 2018.
Aaron Clauset, Cosma Rohilla Shalizi, and Mark EJ Newman. Power-law distributions in empirical data. SIAM review, 51(4):661770, 2009.
Criteo. Criteo 1TB Click Logs dataset. https::////. ailab. www.eoriie........ httpt///...co/essssseeeeeeeee
2014. 2014.
Maurizio Ferrari Dacrema, Simone Boglio, Paolo Cremonesi, and Dietmar Jannach. A troubling analysis of reproducibility and progress in recommender systems research. ACM Transactions Information Systems (TOIS), 39(2):1-49, 2021.
Cong D Dang and Guanghui Lan. Stochastic block mirror descent methods for nonsmooth and stochastic optimization. SIAM Journal on Optimization, 8588),856-88, 2015.
Alexandre Défossez, Léon Bottou, Francis Bach, and Nicolas Usunier. A simple convergence proof of adam and adagrad. arXiv preprint arXiv:2003.02395, 2020.
Jacob Devlin, Ming- Mii Chang, Kenton Lee, and Kristina Toutanova. Bert: Pre-training of deep bidirectional transformers for language understanding. arXiv preprint arXiv:1810.04800 2018.
Yoel Drori and Ohad Shamir. The complexity of finding stationary points with stochastic gradient descent. In International Conference on Machine Learning, pp. 2658-26611 PMLR, 2020.
John Duchi, Elad Hazan, and Yoram Singer. Adaptive subgradient methods for online learning and stochastic optimization. Journal of machine learning research, 12(7), 2011.
Saced Ghadimi and Guanghui Lan. Stochastic first-and zeroth-order methods for nonconvex stochas- tic programming. SIAM Journal on Optimization, 23(4):2341-2365 2013.
Priya Goyal, Piotr Dollár, Ross Girshick, Pieter Noordhuis, Lukasz Wesolowski, Aapo Kyrola, An- drew Tulloch, Yangqing Jia, and Kaiming He. Accurate, large minibatch sgd: Training imagenet in I hour. arXiv preprint (ttp:1106.0267,.200
GroupLens. Movielens-IM. htttass//groppeees..rrr//ttseee 2003.
Huifeng Guo, Ruiming Tang, Yunming Ye, Zhenguo Li, and Xiuqiang He. Deepfm: factorization- machine based neural network for ctr prediction. arXiv preprint
2017.
Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Deep residual learning for image recog- nition. In Proceedings of the IEEE conference on computer vision and pattern recognition, pp- 770-778, 2016.
10

---

Published conference paper at ICLR 2022
Xinran He, Junfeng Pan, Ou Jin, Tianbing Xu, Bo Liu, Tao Xu. Yanxin Shi, Antoine Atallah, Ralf Herbrich, Stuart Bowers, et al. Practical lessons from predicting clicks on ads at facebook. In Proceedings of the Eighth International Workshop on Data Mining for Online Advertising, pp- 1-9, 2014.
Diederik Kingma and Jimmy Ba. Adam: method for stochastic optimization. arXiv preprint 11Xi::142.6698, 2014.
Shin-Ichiro Kumamoto and Takashi Kamihigashi. Power laws in stochastic processes for social phenomena: An introductory review. Frontiers in Physics, 6:20, 2018.
Liyuan Liu, Xiaodong Liu, Jianfeng Gao, Weizhu Chen, and Jiawei Han. Understanding the diffi- culty of training transformers. arXiv preprint arXiv:2004. (tt::2004008249, 2020.
Yinhan Liu, Myle Out, Naman Goyal, Jingfei Du, Mandar Joshi, Danqi Chen, Omer Levy, Mike Lewis, Luke Zettlemoyer, and Veselin Stoyanov. Roberta: A robustly optimized bert pretraining approach. arXiv preprint arXiv:1907.11692 2019.
Stephen Merity, Caiming Xiong, James Bradbury, and Richard Socher. Pointer sentinel mixture models. arXiv preprint 1609.07660077555 2016.
Tomas Mikolov, Kai Chen, Greg Corrado, and Jeffrey Dean. Efficient estimation of word represen- tations vector space. arXiv preprint arXiv: TtV::/301.788. 2013a.
Tomas Mikolov, llya Sutskever, Kai Chen, Greg S Corrado, and Jeff Dean. Distributed representa- tions of words and phrases and their compositionality. In Advances in neural information pro- cessing systems, pp. 3111-3119 2013b.
Lev Muchnik, Sen Pei, Lucas Parra, Saulo DS Reis, José S Andrade Jr, Shlomo Havlin, and Hernán A Makse. Origins of power-law degree distribution in the heterogeneity of human activity in social networks. Scientific reports, 3(1):1-8, 2013.
Yu Nesterov. Efficiency of coordinate descent methods on huge-scale optimization problems. SIAM Journal on Optimization, 22(2):341-362, 2012.
Jeffrey Pennington, Richard Socher, and Christopher Manning. GloVe: Global vectors for word representation. In Proceedings of the 2014 Conference on Empirical Methods in Natural Lan- guage Processing (EMNLP), pp. 1532-1543, Doha, Qatar, October 2014. Association for Com- putational Linguistics. doi: 10.3115/v1/D14-111 URL https: https////cccatthoooooooo org/
D14-1162.
Steven T Piantadosi. Zipl's word frequency law in natural language: critical review and future directions. Psychonomic bulletin & review, 21(5):1112 1130, 2014.
Reddi, Manzil Zaheer, Devendra Sachan, Satyen Kale, and Sanjiv Kumar. Adaptive methods for nonconvex optimization. In Proceeding of 32nd Conference Neural Information Processing Systems (NIPS 2018), 2018.
Sashank J Reddi, Satyen Kale, and Sanjiv Kumar. On the convergence of adam and beyond. arXiv preprint arXiv: 09999040..99...... 2019.
Steffen Rendle. Factorization machines. In 2010 IEEE International conference on data mining, pp-
1000. IEEE, 2010.
Peter Richtárik and Martin Takáč. Iteration complexity of randomized block-coordinate descent methods for minimizing a composite function. Mathematical Programming, 144(1):1-38, 2014.
Joaquim Santos, Bernardo Consoli, and Renata Vieira. Word embedding evaluation in downstream tasks and semantic analogies. In Proceedings of the 12th Language Resources and Evaluation Conference, pp. 4828 4834, Marseille, France, May 2020. European Language Resources Asso- ciation. ISBN 909-99-99990 10-95554-334 URL https: ttttt:s://acaaatt.oiio /aclantooooggyyyc.oooooo wwtpoooooyyyo.g/g22/0e org/2020 1rec-1. 594.
11

---

Published conference paper at ICLR 2022
Gábor Takács, István Pilászy, Bottyán Németh, and Domonkos Tikk. Scalable collaborative filtering approaches for large recommender systems. The Journal of Machine Learning Research, 10:623- 656, 2009.
Rachel Ward, Xiaoxia Wu, and Leon Bottou. Adagrad stepsizes: Sharp convergence over nonconvex landscapes, from any initialization. arXiv preprint arXiv:/806.0066 2, 2018.
Zi Yin and Yuanyuan Shen. On the dimensionality of word embedding. arXiv preprint urXiv:/8/2.0443 2018.
Jingzhao Zhang, Sai Praneeth Karimireddy, Andreas Veit, Seungyeon Kim, Sashank Reddi, Sanjiv Kumar, and Suvrit Sra. Why are adaptive methods good for attention models? arXiv preprint arXiv: arXiv:/912.00 19/1099/..3111 194, 2019.
Dongruo Zhou, Jinghui Chen, Yuan Cao, Yiqi Tang, Ziyan Yang, and Quanquan Gu. On the convergence of adaptive gradient methods for nonconvex optimization. arXiv preprint arXiv:/800s 808.05671, 8a.
Guorui Zhou, Xiaoqiang Zhu, Chenru Song, Ying Fan, Han Zhu, Xiao Ma, Yanghui Yan, Junqi Jin, Han Li, and Kun Gai. Deep interest network for click-through rate prediction. In Proceedings of the 24th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining, pD- 1059-1068, 2018b.
George Kingsley Zipf. Human behavior and the principle of least effort: An introduction to human ecology. Ravenio Books, 2016.
12

---

Published conference paper at ICLR 2022
A EXPERIMENT DETAILS
A.1 DATASETS AND PREPROCESSING
Movielens- Movielens-Iee IM contains 1,000,209 anonymous ratings of approximately 3,900
movies made by 6,040 MovieLens users. Each ratings is integer ranging from 1 to 5. We use only user and movie to make prediction. We treat samples with rating less or equal to 3 as negative examples, and samples with rating greater than 3 as positive examples.
Criteo: The dataset consists a portion of Criteo's 's traffic over period of 7 days. Each sample corresponds an ad served by Criteo. The label is either (indicating ad being clicked) (indicating ad being ignored). The dataset consists of 13 features (integer values) and 26 categor- ical features. There is 45840617 total examples. For the integer valued features, we apply the log transformation (log(x: whenever r >> 2), and convert into categorical features, as suggested by the winner of Criteo Competition !
For both Moviclens- and Criteo dataset, we random split into training set, validation set and test set, taking up 80%, 10%, and 10% of the total samples respectively.
Implementation: We build upon torchfm², which contains implementation of various popular rec- ommendation models.
A.2 MODEL ARCHITECTURE
For all FM models, we use 64 as the embedding size. For all DeepFM models, we use 16 as the embedding size, and use (16, 16) as the widths of the hidden layers.
A.3
HYPERPARAMETERS
For Movielens- 1M dataset, the learning rate of different algorithms are list in Table 2. Model Type
SGD
CF-SGD
Adagrad
Adam
FM
lel
lc0
2c-2
le-3
DeepFM
le-2
2e0
4e-2
2e-3
Table 2: Learning rates for Moviclens- IM dataset.
For Criteo dataset, the learning rate of different algorithms are list Table
Model Type
SGD
CF-SGD
Adagrad
Adam
FM
le-2
le-1
le-2
le-3
DeepFM
le-2
lc-2
lc-2
lc-3
Table 3: Learning rates for Criteo dataset.
All the algorithms use 1024 as the batch size during training.
B ADDITIONAL EXPERIMENTS ON WORD2VEC EMBEDDING LEARNING
We demonstrate the effectiveness of the proposed FA/CF-SGI for embedding learning problems in natural language modeling. Specifically, we conduct experiments for learning Word2 embed- dings proposed in Mikolov al. (2013a). Two learning models considered:
(1) Continuous Bag-of-Word the center word), given its neighboring words. The training task is defined by taking each word in the corpus as the center word, and minimize the total prediction loss.
(CBOW): CBOW aims to predict each word (which we refer to as
(2) Skip-Gram: Skip-Gram aims predict each context word, given a center word. The training task is defined by taking each word in the corpus as the center word, and minimize the total prediction loss.
Dataset and Preprocessing. We use WikiText-2 dataset (Merity et al., 2016), which contains 36k text lines and 2M tokens in the training dataset. We remove extremely rare tokens with less than
13

---

Published conference paper at ICLR 2022
50 occurrences in the training dataset. Note that removing extremely rare tokens was also proposed in the original Word2 paper Mikolov et al. (2013a) where only the top million most frequent tokens are selected.
Experiment details and results. We choose the embedding dimension to be 300 as suggested value Mikolov al. (2013a). Note that for each word w, Word2 represents by pair of embedding vectors (Uwr, Vw)) which we refer to as the center embedding and context embedding, respectively. Specifically, tw is used when w serves as the center word, and ew is used when w serves as the context word. This makes the proposed FA/CF-SGD perfectly applicable for learning Word2 Vec embeddings, by simply setting as the set of center embedding vectors, and V as the set of context embedding vectors.
We compare CF-SGD with standard SGD, and Adam. Following the suggestion from Mikolov et al. (2013a), we decrease the learning rate linearly epoch increases. We initial stepsize of 1.0 for both CF-SGD and SGD, and the stepsize of 0.025 for Adam. We iterate over the training dataset for 20 epochs, with batch size of 96. Note the original Word2Vec was trained with only 3 epochs, albeit on a much larger corpus. The results are reported in Figure 5. CROW
Skip Gram
Skip Gram
CBOW
SG0
Adam
7.5
CF 6OD
Scb
Treinig
7.0
6.69
6.0
5.6
55
2002
6003
15
(a) Training loss
(b) Testing loss
(c) Training loss
(d) Testing loss
Figure 5: Comparison between CF-SGD, SGD, and Adam for learning Word2 embeddings on WikiText-2 dataset.
One can clearly see that for both CBOW and Skip-Gramm models, CF-SGD able to significantly improve standard SGD. For Skip-Gram model, observe that CF-SGD even yields compa- rable performance to Adam. For CBOW model, CF-SGD is able fill in the huge performance gap between Adam and SGD, and yields similar testing performance compared Adam. Note that do not extensively tune the initial stepsize of CF-SGD, and the linearly-decaying stepsize annealing rule was proposed in Mikolov et al. (2013a) for speeding-up up SGD, which we believe might the optimal choice for CF-SGD. We believe further improvements can be made by searching for the best initial learning rate and proper stepsize annealing rule for CF-SGD.
14

---

Published conference paper at ICLR 2022
C REAL WORLD TOKEN DISTRIBUTIONS
We plot token distributions for the first 28 features (after preprocessing) of the benchmark recom- mendation dataset Criteo. Note that the semantic information of features for the Criteo dataset is
0.4
0.35
0.3
0.25
0.15
0.10
0.2
0.10
0.0
0.00
0.00
Teken Bank
Token Bank
Tokce Back
Tolan Bank
(a) Feature
(b) Feature
Feature 2
Feature 3
0.20
0.10
0.030
0:15
0.00
2000
0,030
0.30
Taloo
0.5
0.06
0.000
20
100
122
200
0.00
25
:00
0.00
20
60
50
0.00
20
60
(e) Feature
(f) Feature 5
(g) Feature 6
(b) Feature 7
5.8-
Nike Brawerr
0.59
0.4
0.3
Toam Freqpancc
2.5
8.3
0.3
0.02
8.21
9.2
0.00
30
(i Feature
ii Feature
(k) Feature 10
(l) Feature
0.12
10 7102
5.4
0.10
Tolon trmqueecy
0.:0
0.04
0.29
6.3
0.52
Tales Rank
Taler Bank
Thzen Back
Tihos Raik
(m) Feature 12
(n) Feature 13
(0) Feature 14
(p) Feature 17
0.50
0..3
Preeuerac
3.8
0.555
0.8
02
0.3
0.000
0.1
Cosss
0.0
0.0
9.0
2303
7530 10000 12303
(q) Feature 18
(r) Feature 19
(s) Feature 20
(l) Feature
0.3
011300
0.320
5.000
0,1100
0.015
8.016
0.230
5.010
0.2
20
Titen Rack
Tekes Bank
Thben Bank
Tceet Roni
(u) Feature 23
(v) Feature 25
(w) Feature 26
(x) Feature 27
15

---

Published conference paper at ICLR 2022
D ANALYSIS
Throughout our analysis, we use & (ft, to denote the random user/item ids sampled from the unknown distribution D. We use Sit] (C. (==) to denote the random samples collected up to the beginning of the t-th iteration, and use & and Eiyj interchangeably when the context is clear. Finally, we use Fi ((p) to denote the o-algebra generated by the random variables Eir]-
Proof of Proposition 2.1. Let V E RR denote the submatrix that contains gradient of users embeddings, and fiv E R/vxd for the gradient of item embeddings. Similarly, let o E Rlulxd oi E <RIV denote the stochastic gradient of user and item embeddings, respectively.
Eis 190 V E,
Ejils
Vf.. - s1.11²+
Σ
|
= Ri,
(1
)² | 2 Ej,li 1 11
Σ
|
Pie
Σ
ji ||0% 11 Ep((1
pi(
|
Σ
P:
iEU
IEU
i
Σ piEji ||0
+ Σ pi(1
Σ
p:)
|
Similarly, we can show
Ei -1s - -VR1I Σ
E 11,,,11/
p5(1 - + Ea-
|
Pj
JEV
jEV
JEV
Note that ||ge
4 = 1lg6 - VS8 -
+ +
- V from which we conclude the proof. 17
Proposition D.1. Given Assumption 2, let d; 8y RRd, and ex satisfy 0f 0, + 8 0', 0, + 85.
we have
L ||.
_ |1,
+ (Ve,
where L2 = 2Lpx for all E X.
Proof.
Apply second-order Taylor expansion, we have
E F) (6..0,)
f(0') (
+ (67 .o))
FT
where
ÿ (0)) Σ D(i.j)) 1(0,
jEV
E f2,0,((0) D(i.j) and (8,
8y; Viy), Σ V ((, (. NEU
F f(,)
D(i.)) ((,, 0z; ve))
iEU
for some Ô as convex combination of and O¹, and the last equality uses the fact that f(u; v) is
symmetric w.r.t u and Now given the assumption that V2 (3)11 S T,, ((s:5 : )|2 5 T.
16

---

Published conference paper at ICLR 2022
we have
S(0') f(6) + (Vo.f.)) (Vo.f..))+ (Vo,f.6)) 6 Hō; + +5 Fō, + 20, E6,
$ f(0) + (Vo....)) + (V,,f,6) + L
Σ (1, Σ
D(C
JEE
w'eU
+ D(ij)) | + P(i,))
= =(()) + (Vo.f..)) + (Vo)f,6)) + Σ
Σ
Lo(
j'EV
N'EU
L
+ Lj
= f()) + (Vo. f. 6,) + (o,f.6,) +
||o: 2|
||ā
2
2
where the first inequality we use 6.1 Fd, v |6: |6
1/4 (116:]] + |18,11),, and the last
equality we use the definition that La = 2Lpb for all k E X.
Before we specify the concrete learning rate, we have the following generic convergence character- ization.
Proposition D.2. Given learning rate keettr we have the following holds for Algorithm 1.
T
Ix(n))2)
T
E
nk
| < ((09)
+
Ph
(nk))
Pk
1= KEX
t=0 KEX
Proof. From Proposition D.1, we have
Lie
Li
)(0+t) s(()) + (V 01,) (V.z, - 00,)) +
10:t1 01,11
10
02 11
2
=s(6') - nh. (Vi,, k(.) - nnj (VS, ,/.,) + Li,
Isj
mh |1 11
10 11?
+
(14)
2
2
Conditioned on past history Ft, we have
f
Et.d. [vl, (Vfi, 91)1 B,i. [n), (V .f
Σ ped
Σ
n
|
(15)
pi
Similarly, we have
Bicsi [n). (VIJ of)1
|
(16)
NEV
On the other hand, we have
Ei.ii Lt. (nt, |1,t [12] = E (n
V.f.
5%
Pte
|[ 1
|| 11 )
< 21,, Ejilie
15.
2E,, Li. (n,
+ 1
Př,
|IV
-2 Σ (2
+ o
(17)
IEU
17

---

Published conference paper at ICLR 2022
where the first inqquality uses ||a + bll2 1 2 2||all + [|b|] the second inequality uses (5), and the final equality uses the definition of L; in Proposition D.I. Following similar arguments, we also have
| D3
Ei (L (ng.)) [19 2 11
2 Σ OTf)
+ o3
(18)
jEV
Plug in (15) (16) (17) (18) back into (14), we obtain
Ta(nh)2
I,(r1)2
Big. [ - f((0)
Σ
mh
|
11}
||
1?
Pi
Pj
İEU
JEV
+
Σ
P.. +
EPII,
IEU
JEU
Ialobt))
= f(())
Σ
The
|Vsill +2 Σ
Ph Pa
KEX
kEX
Equivalently, we have
| & f(0') - Ei... [ +2 Σ
Pnhn (19)
PE:
kEX
REX
Sum up (19) from t T and take total expectation, we have
T
I2(
T
E
Th
| - f(00) fr +
Σ
Ph Inh
Ph
t=0 REX
Proof of Theorem 3.1. Given Proposition D.2, suppose constant stepsize, i.e. voé 7h for all t E [T). and sample Unif((T]), then for any E X,
Lu(nk)²)
E
MA
| $1((0) l
PaLa(ma)20f
Pk
which implies that for any & E X,
f(00) - f
Eiex PIL
E
V
S
+
La (1x))
T 11k
1/1
Ps
For a given a > 0, we choose
{ as the following
n min 1
4L TTPel
Combined with Proposition D.I, we have mh In( = T/s - 22(1))²²
7i
and hence
2
J < 2
4 41 (II
+
Tyk
We can bound the first term by
(f(09)-1) f()
(f(0))- -()
VTpx
T max
4L,
Tmk
a
{ L (f(00) - f*)
VP (f(00) -ft)
o
T
avT
18

---

Published conference paper at ICLR 2022
In addition, since
Loi a²
L E piofa?
E
Σ lEx
Pi
Tpt
IeX
thus we can bound the second term by
ElexPi PTTa(1)oof
I. Lix Piofa
4L, VPET
max
176
a L/Drk Eiex Dioja VT
{ L2
EiEx piot
o
T
Thus we have
BIVSE1 O - -M)
vPh -1')
L²a Eiex piod
LV/D EIEx PioPa
+
+
T
avT
T
VT
(20)
By choosing
T.2iex pl07 we have
[100)-1"
V
/PIc (f((") -*)
LVPP% EiEx Piofa -0}
_of
o
VPRY Eiex (1) S
(21)
aVT
VT
VT
12a2 ΣiEx
T. (.( 1*)
(22)
T
T
Thus combining (20) (21) (22), we have
L [f((9)) fz)
VPk Eiex
ST) -
E V 2 0
Vk E X.
VT
L
Proof of Theorem 3.2. Given Proposition D.2, suppose we use token-agnostic constant stepsize, i.e.,
Th = for all E [T], X, and sample 7 ~ UnT)( then for any & E X,
In(1)²
E
S(())) 1 + 2
Σ
Pk
0=o
1= REX
which implies that for any k X.
E V < f(00) l
ΣlEx P (2())
+2
T (n- (n)2
Ie(n)² pt
11
Pk
For given a > 0, we choose (n*) as the following
r = min
a
4L VT
Combined with Proposition D.1, we have
Iz(n)² = 17 - (0_(n) 2 "/, and hence
Pk
2(S(0)) r*) 4 S1
V 2 <
+
Tn
19

---

Published conference paper at ICLR 2022
We can bound the first term by
(f(6") -f)
-f*)
4h, VT
T max
Tn
a
of
L (f(0")))) -r)
(5(09) -f9
= =0
avT
In addition, since
Pi Lot a²
L
Eiexxhofa'
Σ
T
IEX
thus we can bound the second term by
EiEx pi PII((m)
LiExpiooa
L LiEx
VT
max
4L,
11
T
1.a²
EIEx
EiE Piofa
0
T
Thus we have
V {
L. ( - (1(09)- -^)
lex 12a 12a2Etex Eiex oř
IiEee
T
avT
VT
(23)
)(00)-f-
By choosing a = V >>EexPoaf
we have
E =of VEEEXPPORU11000
(f(0))
(24)
aVT
VT
VT
([((0)-) 1*) L2a² DI XEX pio
(25)
Thus combining (23) (24) (25), have
L (1(09) -²)
(( - I*)
V flll =
+
4k E X.
T
VT
Proof of Theorem 3.3. We define p = Et 1 (is = 1t/ E' {je = }} /t. and m7
for all [T],i U,j E V,K E X. In addition, define the frequency- dependent learning rates ni = min
min
2L pTpx
Note that (19) still holds. Sum up (19) from = 0 to T and take total expectation, we have
(
T
E
at f
f((0) f + 2E
Σ Σ
(26)
Pk
1=
REX
In contrast to FA-SGD and standard SGD, here the stepsize Th E F, is also a random variable. We first proceed upper bound the right hand side of (26).
20

---

Published conference paper at ICLR 2022
For each le X, denote Tx= -. t 2
where e > 0 is any absolute constant. Note that we have for any
pk
Tk.
PP% - pkl
Pk
S
1 - pkl
2
Pk
S exp
Pk (Tpa(1 ph))
S exp (-tpe).
(27)
2
2
Moreover, we have
P
Phl -
Pk
n I aork:
(28)
2
where og max {1 (1- 22/3, v2 - 11 < 1. Note that for any T >
Tk.
T BB
[TA) = Te
T
Σ
Be (Th) +
Σ
ps B [
t=0
1=
1=++1
To bound the first term, note that from definition of i% we have Th S I. hence
Tk
Tu
(t)
2 = TrppI (t)² 2
= cIaoR (t)²
Σ 1=
PIIRORRLE (M)) S
1=0
To bound the second term, note that from (27), for any t > Tp with probability at least 1 - 8% (here
6% = exp((tpx)). we have that \T - 7% I o07 Denote Hi = {w: : in - 7% I aooh J. we have
Be (T = Eg (Th 2 HE
BT(TTT (HE))
(
s (1 + ao) (Th
EE mt
Be (agg)
$ (1+ 5% ( 2
Hence for any t 2 Tu.
T Σ
T
(7)2 2
[712 <
Σ
(1 + an) pp +
Σ
1=
t=
Thus we obtain
1 2
1 (1) I.
Σ pa T [( s c
(1+ Po +
Σ
1=0
t=
2 2
1 [
T
exp( exp(-c)pp
(1) 2
< cT+ 2
Σ
T (1 + oo) 2 Te + 1 exp(-pa)
+
[.]
==
(1)
11' 2
S cT
Σ
(1 + 0n) 2p Tx + an exp(-c)pppecppppp T
i.
where the last inequality uses the fact that Σt Ei 8 < Eie 8%
expl Tapp) I-expl -exp((-pt) pp) I -exp(-ppp
exp(-0)
and 0 SUPPe(0.1) I-exp(-p)
P
Hence by denoting To = maxXEx TR, we have that for any i E X, and t 2 To.
E 1=0
7
La (72))
1 S f(0")
8r +2
Σ
CLEO
1
I
Pk
AEX
(A)
T
1
(1 + an) P' I + an exp( exp(-c)IAo0
L
1= SOX
(C)
(B)
(29)
21

---

Published conference paper at ICLR 2022
Note that term (B) in (29) can be bounded following exactly the same step as in the proof of Theorem 3.1, for which we have
pf Loi a²
T
Σ
IT) Σ
L E
piota?
Tpi
JE
1EX
LEX
Hence for any constant
(we can readily choose
1), we have
V | f(0") f +2{ Σ
1
Eg
L
D
Pk
t=
REX
(A))
1
+ (1 + 2o)²L Σ
Proraa" +
a1 exp(-e) exp(-c)]koff
REX
kEX
(B')
(0))
By the definition of f%. we also have Th-
2
then
2
I& (T6))
T
E
T
Ee
Pk
2
Hence we obtain
E
2 $((0") - fr +
L
(1)
2
L
t=0
keX
(A')
+ (1+ 2 Σ
profa
ai exp(epp)ccceco Expo
1
2
(30)
kEX
KEX
(BV)
(C')
or equivalently,
T
2 2 5*)
4(A')
4(B))
4(C')
E
| S ΣL ok
+
+
(31)
D
Th
Σ
El th
Σl= nk
1=
Let To denote a positive integer to be determined later, recall that from (27), for any 1> To, with probability at least og (here & = exp(-tpx)) we have Inf Tl I con hold. Denote Bi = (w Inf 1 S oo7/) ) then we have that for any l E X.
TH
Th
E
|
2
R
/
1=0
t= W
t=
E
T/
V V
1s
1= 1
T
T
2 (1 00)
1//
Eg
V f 2
1s;
1=0 ml
T
2 (1 - 00)
Bg V - -
2t= T
7
(1- an (T' To)
Σ
Eg V 2
To To
t=
(1 OT) - -To)
E,Ex V
02)
(32)
T
22

---

Published conference paper at ICLR 2022
where the fourth inequality uses the assumption that || Σ G², and the last equality follows from the definition that 7 ~ Un.f Finally, choose To = T/2, combine (31) and (32), obtain
E. I O { [ -ft)
A(A')
4(B)
4(C")
Σr n/ Eizonh th
Σi
Σi= 1/
Combine with the definition of (A'), (B'), (C") in (30), and the definition of of we obtain
Eg |V of f(09) f + ExEx I (t)
(1 a0) Exex + 8
Ex 1. KEX pEo
Σ m/
+ texp(-Tpx/2j0²
El= Ti
Et m/
Mj
1.E kex profa?
E
Σt 1%
where the last inequality holds whenever T 2 To and To large enough so that exp( Pepp--Ppp//2CC S M, and the second equality follows from the definition of My S(00) ft +
M,
- r
EXEX L (+) = f(0") f + Ekex pro L. Finally, following similar lines as in the proof
of Theorem 3.1, by choosing v EEEe Pio?
M,
we obtain that for T 2 max { (oo Jo.
LM, VPW Eiex LM
Eg
| 0
VT
(f(00) - f*) VPWV Exex L
(EiEx
LM,
0
T
VT
LM, VPk Σiex pio (f(00)- (f f²) --) +
Ph SiexpIoo VT
Wk E X,
VT
where the last inequality uses simple fact w I va + vb whenever a, > 0. remains to estimate the order of To. we need /opo/TTp//2/0) 2) 5
My
this can be readily satisfied by
taking To 2 log G log (M,(1/2L+a/ /Pa))
Improvement of CF-SC CF-SGD over SGD. Now under the the assumption that of o² for all / e X, compared with the rate convergence of standard SGD in (9), the improvement Counter-based Frequency-aware SGD is governed by the ratio % defined by
(1 (1+
VPk
VL(f(00) ( )r))
"e ==
V Eie ri
which is only constant factor away from the the improvement ratio "y of vanilla frequency-aware SGD over standard SGD, given by
/Pk
=
E
oi
Hence both Corollary 3.2 and 3.3 hold for Counter- based Frequency-aware SGD after properly adjusting the constant factor in the statement.
23

---

Published conference paper at ICLR 2022
Proof of Corollary 3.1. By trivial verification.
Corollary D.1 (Corollary 3.2, restated), Let U user with n-th largest frequency, and jm denote the item with the m-th largest frequency, Suppose
(tr I V
= {im Kimimt where in denote the
Pin X exp(-Tn), Pim x exp(-rm), Vn E [1 [|][]]
(33)
for some > O. Then there exists Bu, Br > 0 such that for any user in E U, we have
Pi ΣIEx pro = (T) exp (-Tn) - 1 1-exp(-7 exp(-r) exp (-Tn).
+ exp(-r)
(34)
ΣiEx of
Similarly, for any item Im E V, we have
Pjm. ΣiEx piot = By exp -
1 + exp(-r)
1 - exp(-r) exp {Tmm..
(35)
ΣIEX oी
In addition, there exists an absolute constant C 0, such that for whenver UU) IV 2 7, we have Br ( S C, and thus
Pin ΣiEx &Cexp(-Tn)
Pym Eiex
S Cxep (-rm}, Vi, E U, Vjm E V. (36)
Diexpiot
Proof. Define Mu 1-exp(-7) and My 1-exp(-r) 1-exp(-r|V[]> from (33) we have Pi..
1-exp(-r(U1)"
My exp(-rn), Psm Pjm = My (xp(-rr)) In addition, we denote
M 1 - --2(0))
+ M2 1 - exp(-22TU1) (U))
MU.v
Σ Pi
ps + Σ pj
1 ex-exp(222
1 expep- 2T)
TEX
iEU
jEV
(1 exp( (pp(((-((i)) (1 -exp(())))))( + (1
(1- cxp -T))
(1 exp( (1)p==
(1 (1- (1=exp(-T|VV) (1 exp(-r))
Thus we obtain,
Pia Elex pio?
2pt..
2Mu exp(-7n) -Bu exp(-Tn), Vin E U
Σiex
Σlex Vi
May
Pin Σiex piot
2pi
2My
exp(-rm) = 3v exp(-rm)) Vin E V,
ΣIEX přoo
ΣlEx Pi
Mu.y
From the definition of Bu Me.v
2M By
Me.v combined with the fact that My,y 2 21-exp(-7 -T)
2Mv,
(1exp(-r)
and Mr, My < 1, we obtain the inequality in (34) and (35). Finally, whenever [U], 2 7, we 1-exp(-r) 1+exp(-T)
2 have Bu S (exxp(-T(0)) I 1-exp(-T) I 1-e-1 and similarly 3y S - Let C = 1-e-1, we obtain (36).
Corollary D.2 (Corollary 3.3, restated), Let U user with n-th largest frequency, and jm denote the item with the m-th largest frequency. Suppose
(1 V
- I where i, denote the
Pi,, X n. Pin & mm Vn [[]]], m |
E [[V]]
(37)
for some 2 2. Define UT as the set of users whose frequencies are within 2-factor from the highest frequency: UT = (in nn = 2 1/2), and VT similarly as Vr = {im : m " 2 1/2]. We refer to UT as the top users, and Vr as the top items. Then there exists absolute constant C > 0. such that
Pi., Piot Σiex ofo?
< C'n""; Pin Eiexpiof
S Om-", Vi, E Vjm E V.
Σiex ofot
24

---

Published conference paper at ICLR 2022
Proof. We have Pin Mon where My
Similarly, we have Pim Mym
Σn
where Mv
Hence
Σm m"
Pín Eiex piot ΣiEx
2pt..
2Mun
ΣiexPi
Mi
Σ
10
2v
M3 ΣM
m= m m- 2V
m=
We have
10
1U
1U1+1
n
V
1
+
n 1
1+
n
1 + V-
[2 - (10) + +1)--J]
n=1
2
|0]
|U|+1
1
1+
[] (10) + 1)
V 1
[0]
> 1 +
[21-2 2u
(10) + 1)1-2y
2y
R=1
which implies
1 1
V- 1 MU (1U) + (11++)22-// -1)2- + V V-1
MU 21-v - (1U) + 1) + +
1 1
Mv < 21-v - ([V) 1) - 1
Mr >
(IV) + 1) +
Thus
Pin Σiex pio Σiexpiof
2/2v-1) 1)(v-1)
n1 (2--v_ ((]+v((
2 (21-20 -(1U) + 1 20 + 2v 1)+ + ([V]=)}) -+x) (1U++)) -4D)
(21-2v - -(VV + 1)1-22 2v + 2v 1)
Note that
21-2v - -(U1 1))1 + 2v - 1 1> 2v - 1, 21-2" - (1V) + 1) + +2 - 1> 1 1
(IU) + 1)1 +v > 1+v' (V + 1) +
1 1+v
1
2ー-V (10) + 1)
+ -
V w-1 21-v (V + 1)
+
+
=-1
Then we conclude with
Pin, Σiex P
(2v (2v-1) 1) (1 + v)2
つリ < 16n
ΣIEx oi
1) (v - 12 -1)
where the last inequality follows from the fact that v 2 2. Similarly we can show that
Pim ΣIEx Pio?
< 16m "M
Eiex
Take C = 16, we obtain the desired result.
25


Reviews:
[{"review_id": "b6pLMPjTGcX", "reviewer": "Reviewer_8cB1", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "The paper investigates the idea of incorporating frequency into SGD for embedding learning, which makes a lof of sense and hasn't been explored before to my knowledge. The theoretical results is interesting in that the proposed method outperforms SGD *WHEN* skewed distribution appeared. And the good thing is that for frequent users/items, the convergence rate remains the same, but much improved for infrequent ones. The empirical results are also very interesting: (i) reveals that Adam/Adagrad mostly implicitly capture the frequency information in momentum; (ii) show great performance improvement over SGD, and very competitive performance against adaptive methods.\n\nI just have a few comments/questions:\n\n(i) it'd be great to have a slice performance analysis, which may reveal that the improvement in infrequent items is even larger.\n(ii) for infrequent items, whether a high convergence rate will contribute to overfitting? though the generalization property is beyond the scope of the paper.\n(iii) it seems the hidden width of DeepFM is `(16, 16) `, which seems too small to me? Will the analysis/results change for large NNs?\n\n\n", "summary_of_the_paper": "The paper proposes a frequency-based SGD method, where the learning rate is inversely proportional to the token frequency. Theoretical results show the proposed methods outperform SGD in skewed distributions, and empirically verify the effectiveness of the proposed method, and reveal the similarity between Adam/AdaGrad's momentum and frequency.\n\n", "summary_of_the_review": "The paper nicely introduces frequency information into SGD, with various interesting theoretical analysis and empirical results.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "OAlstV1JvhP", "reviewer": "Reviewer_Xi3e", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Strengths\n1. The proposed algorithms are easy to implement.\n2. Both the online and offline situations are considered.\n\nWeaknesses\nThe experiments are insufficient. Offline training is also regularly (daily or hourly) required and conducted in industrial recommender systems for capturing long-term interests. It is unknown if FA-SGD outperforms the baselines in offline evaluation. Besides, matching and ranking are two stages in recommender systems. FM and DeepFM are commonly used models in the stage of ranking. It is unknown if CF-SGD shows advantages in the stage of matching. I suggest the authors employ the algorithm to some common matching models such as DSSM for a comprehensive evaluation. In addition, only the cross-entropy (point-wise) loss is tested in the experiments. It is unknown if the proposed algorithms can generalize to adapt to other losses such as the pair-wise loss.\n", "summary_of_the_paper": "This paper proposes two optimization algorithms for recommendation where the token distributions are highly imbalanced. The frequency information is integrated into the optimization algorithms for fast convergence and better performance. The proposed algorithms are easy to understand and implement, and the theoretical analysis for the bounds are provided.", "summary_of_the_review": "This paper proposes to integrate the frequency information of tokens into the optimization algorithms for a fast convergence. The idea is novel and the proposed algorithms are easy-to-implement. I recommend to accept it. However, the experiments are not comprehensive and I want to see a thorough evaluation which considers the offline training and the matching stage. Besides, more loss functions should also be investigated. ", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "EKLBUFU7GrE", "reviewer": "Reviewer_xBEu", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Strengths:\n- The paper addresses a very interesting problem about incorporating frequency information into the optimizer for embedding learning in recommender systems. \n- The paper is well-written and the proposed method is well-motivated. \n- The paper demonstrates that the proposed method has provable benefits over SGD.\n\nWeakness: In my opinion, the paper can be improved a lot by re-framing the pitch and enriching the experiments. \n- The title/abs/intro of this paper covers the various areas of embedding learning while the experiments are only on recommendation. I would rather suggest the authors frame the pitch in the area of recommender systems instead of in general embedding learning. \n- To echo with the above points, it will be very interesting if the authors also show some empirical evidence of the proposed method on other embedding learning tasks, like word2vec of knowledge graph embeddings. \n- In Figure 2 (b), it looks like there is a big jump in the red line at the iteration around 1500. Could you explain what was happening there?\n- I wonder if you tune the momentum in SGD. \n- Do you have figures of correlation on Movielens-1M? like Figure 3(a) and 3(b)?\n- In Figure 4 (d) what's the Y-axis? \n- I don't quite get why \"In Figure 4c, 4d we compare the training NE curve CF-SGD and Adagrad, we can see that CF-SGD shows faster convergence than Adagrad during training\". Looking at Figure 4c, I only see the same convergence rate of CF-SGD and Adagrad. \n- It would be interesting to see a curve plot of the learning rate for each token v.s. the frequency of the token.\n\nMinor issues (typos, formats): \n- workpiece -> wordpiece?", "summary_of_the_paper": "This paper proposes a frequency-aware learning algorithm for embedding learning in recommender systems. The idea of incoporating frequency information into the learning algorithm is very interesting to me. The proposed method is very simple and easy to implement with provable benefits.\n", "summary_of_the_review": "The paper addresses the problem of adaptive learning rates in recommender systems. The authors propose a novel and simple method to incorporate token frequency information into the learning rate schedule. The authors also show provable benefits over SGD. I think the paper can be further improved by changing the pitch to focus more on recommender systems and enriching the experiments as said in the main reviews.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "4daxVoMN5Me", "reviewer": "Reviewer_42Qf", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Minor concerns: \n\n1. Why are the lines in Figure 4c identical? \n2. It might be better to zoom in on the y-axis for training loss and AUCs in a smaller region. It is hard to distinguish each method in the current y-axis scale. \n3. How robust is each method towards random seeds and hyper-parameters? Having a variance and confidence interval might help. \n4. Any results for languages? \n", "summary_of_the_paper": "This paper proposes a counter-based learning-rate scheduler for SGD. This algorithm is designed based on the long tail distribution in recommendations and languages. The proposed algorithm enjoys a theoretic guarantee unlike other adaptive learning rate methods, e.g., Adams. Simultaneously, the authors demonstrated that the proposed algorithm achieved comparable empirical performance in two recommendation datasets. Overview, the paper is well-written, which has presented the contributions clearly. \n", "summary_of_the_review": "This paper is well-written and made solid contributions for adaptive learning-rate in long-tail distribution. ", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}]

Author rebuttal:

Meta-review: The paper provides a new learning technique for problems that require learning embeddings. In particular, the authors analyze a technique that takes into account the frequency of items in an embedding layer to modify the learning rate for each embedding. The paper provides a theoretical analysis of this approached and contrasts it to that of SGD. It also provides experiments validating this approach empirically.

The reviewers agree that the paper provides a simple yet effective method, based on realistic assumptions (non-uniform frequencies). In addition, the paper seems to be well written and easy to follow.
One issue raised in the reviews was about the focus of the paper, and the fact that the experiments are limited to recommendation systems even though the method is claimed to be generic for any model requiring embeddings. During the rebuttal the authors provided experiments for an NLP task that show favorable results to the new technique in another regime. Given the overall positive feedback and this new evidence validating the proposed method, I recommend accepting the paper.
Decision: Accept (Poster)