Pairwise Learning with Adaptive Online Gradient Descent
Authors: Tao Sun
Qingsong Wang
Yunwen Lei
Dongsheng Li
Bao Wang
Venue: Accepted by TMLR ()

Abstract: In this paper, we propose an adaptive online gradient descent method with momentum for pairwise learning, in which the stepsize is determined by historical information. Due to the structure of pairwise learning, the sample pairs are dependent on the parameters, causing difficulties in the convergence analysis. To this end, we develop novel techniques for the convergence analysis of the proposed algorithm. We show that the proposed algorithm can output the desired solution in strongly convex, convex, and nonconvex cases. Furthermore, we present theoretical explanations for why our proposed algorithm can accelerate previous workhorses for online pairwise learning. All assumptions used in the theoretical analysis are mild and common, making our results applicable to various pairwise learning problems. To demonstrate the efficiency of our algorithm, we compare the proposed adaptive method with the non-adaptive counterpart on the benchmark online AUC maximization problem.

Published in Transactions on Machine Learning Research (10/2023)
Pairwise Learning with Adaptive Online Gradient Descent
Tao Sun
amttoosallfssh@@oullokkccc
College of Computer
National University of Defense Technology
Changsha, Hunan, China
Qingsong Wang Department of Mathematics Scientific Computing and Imaging (SCI) Institute University of Utah Salt Lake City, Utah, USA
8973 &osu.
Yunwen Lei
leigw
Department of Mathematics The University of Hong Kong Pokfulam, Hong Kong
Dongsheng Li
dsli edu.co
College of Computer National University of Defense Technology Changsha, Hunan, China
Bao Wang
wxnngaonnj@gmail.cm com
Department Mathematics Scientific Compuling and Imoging (SCI) Institude Universily of Ulah
Salt Lake City, Utah, USA
Reviewed on OpenReview: https: // openreview. net/ forum? id- rg1SaH092k
Abstract
In this paper, we propose an adaptive online gradient descent method with momentum for pairwise learning, in which the step size is determined by historical information. Due the structure of pairwise learning, the sample pairs are dependent difficulties in the convergence analysis. To this end, we develop novel techniques for the convergence analysis of the proposed algorithm. We show that the proposed algorithm can output the desired solution in strongly convex, convex, and nonconvex cases. Furthermore, we present theoretical explanations for why our proposed algorithm can accelerate previous workhorses for online pairwise learning. All assumptions used the theoretical analysis are mild and common, making our results applicable to various pairwise lcarning problems. To demonstrate the efficiency of our algorithm, we compare the proposed adaptive method with the non-adaptive counterpart the benchmark online AUC maximization problem.
the parameters, causing
1 Introduction
Let IC C d be closed convex set (can be the full space Rd) representing the parameter space. Given statistical sample space with probability distribution P; let F(:E,E') Ed + R be closed function
"The first and second authors contributed equally this paper. Dongsheng Li is the corresponding author. Dongsheng Li and Tho Sun supported in part by the National Science Foundation of China (62025208), Hunan Provincial Natural Science Foundation of China (2022JJ10065), Young Elite Scientists Sponsorship Program CAST (2022QNRC001, and Contimoous Support PDI. (WDZC20233250001),

---

Published in Transactions on Machine Learning Research (10/2023)
associated with two samples g,5' E E. This paper considers the following pairwise learning problem
{f(=) : == PP REKCRd
min
(1)
where the function F.): can be either convex or nonconvex in æ. The pairwise learning model
[
describes various classical machine learning tasks, including the metric learning [Weinberger & Saul 2009
Kulis et al. 2013 Xing et al. 2002 Ying & Li, 2012] ranking (Rejchel 2012 Agarwal & Niyogi 2009
two-stage multiple kernel learning (Kumar et al. 2012); neural link prediction (Wang et. al. 2021) the
minimum error entropy principle (Hu et al. 2013),
and can be adapted to the area under ROC curve (AUC)
maximization (Zhao et al.] 2011 Gao et al. 2013 Ying et al. 2016
Liu et al., 2018 (scc Remark 2 in
Section for more details).
There are two major kinds of workhorses for the model (1) i.e., offline and online. The offline one similar to the empirical risk minimization (ERM): given an i.idd sample set (". we solve
min EE
e():
nn 1) i.JE(m),
where [n] == 1,2....., The major difference between the offline pairwise learning model and the ERM lies in the elficiency of the samples and whether the objective functions are independent of each other. A n-samples training set outputs finite-sum minimization with O(n) sub-functions in ERM, while the same training set results in O(n²) in the offline pairwise learning. Furthermore, the objective functions in the ERM are independent of each other, which is broken for the offiine pairwise learning" One possible modification to cireumvent the dependent objective functions is to form the objective function with two new independent samples in each iteration. This method is suggested in (Peel et al., 2010 Scction 4.2) and can be regarded as the algorithm proposed by Zhao et al.] (2011) ) with buffer size one. However, as shown in (Zhao el al., 2011), this two-dependent-poine version of online learning does not fully utilize the sampling sequence and results in inferior performance compared with algorithms that utilize some historical samples.
The ouline pairwise learning assumes the i.i.d. samples (s*)<E[n) are continuously received by the model. In the kth iteration, the online style algorithm proceods to sample new data &k from P and reuses the previous samples (gh)isiss with {jeh C lk 1] to get the mini-batch stochastic gradient gº = = E (F(="; (hh) (Wang et al. 2012 Zhao et al. 2011 Ying & Zhou, 2016 Thus, the on- line method needs to employ an Oss) memory to store the previously sampled data and (s) computations to calculate the gradient. Nevertheless, the mini-batel version suffers two drawbacks: 1) It has been proved
that its excess generalization bound can be as large as 0 (tt2 (++++/) ++) (Wang et al. 2012), and we need to use
large s to improve generalization of the online method. 2) A large s causes tremendous computational and memory costs that are unacceptable for online settings. To this end, a simple yet efficient online gradient descent, (OGD) is proposed (presented as Algorithm 1 in which the stochastic gradient g* is set to be g (Yang et al. 2021b). An interesting finding is that the OGD can achieve O (R) excess generalization bound. The tavorable memory and computation costs make the OGD applicable to broader online settings.
In this paper, we focus on developing provably convergent online algorithms with adaptive stepsizes for pairwise learning. Considering the efficiency of the sampling method of OGD (Yang et al. 2021b), our algorithm inherits such kind of sampling. Moreover, our algorithm employs momentum.
1.1
The Adaptive Online Gradient Descent for Pairwise Learning
The OGD performs an SGD-style (stochastic gradient descent) itcration but with biasod stochastic gradients since gk is related to = Motivated by the remarkable success of the adaptive variants of SGD for machine
learning (Duchi et al.] 2011 McMahan & Streeter] 2010 Tieleman & Hinton 2012 Kingma & Ba 2015
Reddi et al. 2018 Ward et al. 2019), we propose the adaptive variant of OGD (AOGD) for pairwise learning.
For example, F(a:: (2. and F(an .9) are not independent because they have a shared data g!.
2

---

Published in Transactions on Machine Learning Research (10/2023)
Algorithm Online Gradient Descent (OGD) for Pairwise Learning (Yang et al. 2021b
Paramcters: >> 0.
Initialization: x" 0, P for k 1, 3....
step 1: receive ę and calculate g² V 5*,
step 2: x++ (rojx ng"
End for
Algorithm Adaptive Online Gradient Descent (AOGD) for Pairwise Learning
Parameters: 1j 0, 0 < 1. Initialization: x² m for k = 1,2.3....
0, 5¹ p
step 1: receive g and calculate ge = VF(attck, ck-1) step 2: m fm (1 0)g²
step 3: r y + 1|
step 4: m=+11 Projx 1mm* (1+))
End for
presented as Algorithm 2 AOGD directly uses the historical sum of the moment rather than the weighted average form used in Adam (Kngmma & Ba 2015), and AOGD can be rewritten the weighted average form: let 0* = Et ///k/ b* /k, then steps 3 and 4 of AOGD can be reformulated as follows:
8h (1-
1 aK
+ 11g8
(2)
n m
*+1 ++1 = Projic x x===
V (ob)1/2
In reformulation (2 weights of the moment are (1/k)<2) and slepsizes {n/Vk) / satisfying the sufficient conditions for the convergence of Adam-type algorithms (Zou et al. 2019: Chen et al. 2019).
Compared with OGD, AOGD employs the momentum and adaptive stepsize generated by the historical information. Thus unlike OGD, AOGD needs a memory of history, but without much computational overhead since AOGD only computes gradient once in each iteration. Another difference between OGD and AOGD lies in the hyper- tpper-parameter np in OGD, 7 shall be set small the desired error while in AOGD, n be set as a constant that is independent of c.
1.2 Comparison with A Closely Related Work
In (Din al. 2015), by adopting the AdaGrad-style adaptive gradient update, Duchi et al. (2011) have proposed an adaptive method for online AUC maximization, which is kind of pairwise learning. Although both (Ding et al. 2015) and our paper consider the adaptive online method for pairwise learning, there are four major differences between (Ding et al. 2015) and our paper, summarized below.
1) We follow the sampling method used by the OGD algorithm in (Yang et al. 2021b 2) We consider more general cases and provide the corresponding theoretical guarantees, including the more general model (pairwise learning rather than only AUC maximization), and convergence for more general scttings, including the nonconvex case, and more general schemes c.g., the use of momentun.
3) We get rid of using the regret bound because it does not directly tell us whether the algorithm converges to the desired minimizer. Another important reason for not using the regret bound for the analysis that the regret. bound has difficulties covering the nonconvex cases. Based on the above rcasons, non-regret analysis is necessary.
4) We develop new analysis techniques to get the non-regret convergence analysis. Notice that the regret bound is not affected by the stochasticity of the data, and thus the analysis in (Ding et al. 2015) does not need to consider how deal with the biased stochastic gradients.
3

---

Published in Transactions on Machine Learning Research (10/2023)
properties and novel techniques
Convergence Results
properties and techniques
bounding [x)()++1) [a*
Analysis
Analysis
properties of intermediate variables
Convergence Results
intermediate variables
Adaptive SGD or OGD AOGD
Contrasting the analysis of AOGD against adaptive SGD/OGD. Our analysis of AOGD studies the properties of some intermediate variables. To this end, we develop novel techniques. In the last step, we use the properties of the intermediate variables to derive the convergence guarantee for AOGD.
Figure 1:
1.3 Challenges in the Analysis and Difference from Existing Analysis
The primary source of challenges theoretical analysis comes from the fact that a. is dependent on g ck-1 which immediately breaks the unbiased expectation of the stochastic gradient ; <* i.e., E (a* gk
ck-1]] + f==*). As such, we cannot directly follow the techniques from adaptive SGD
Duchi et al.
2011 Reddi et al. 2018 Chen et al., 2019 Ward et al. 2019 Zou et al. 2019
Li & Orabona
2019h. In paper (Yang et al. 2021bb. the authors consider the following decomposition
+ VVF((" g"
s", g*-1" - F/ :e" E"-))
Notice that --1 is independent of ck-1, 5h, and 2e = 1/ v The Lipschitz property of the gradient then gives
:VF(a" 5h (atth"h))--00 - "i - O0il - x0111))
and the proof is similar to the "delayed" SGD.
However, our proof cannot directly follow the technique above because AOGD involves two extra recipes, i.e, momentum and adaptive stepsize. When momentum exists, we need to deal with both g and m rather than only g², and we have to modify the techniques from (Yang et al. 2021b to analyze the effects of momentum Another difficulty the use of the adaptive stepsize variable n/(r=) ) Furthermore, w is dependent of the pair (5* ((*),, making the analysis more challenging.
In contrast the existing analysis, our approach is not directly establishing the Lyapunov descent starting from bounding [[ f(**)]. Instead, recruit some intermediate variables. Taking the nonconvex case as an example, we first establish a Lyapunou-like descent property as follows
Bi- B(-VS((*)) m (1 S PR(-V/(("" ") (((b-)/)/) + "p(x". xx 10-1,,h 5k 1
where f( A-1 _ (k_ ck-)) is a function of variables at xt-1 çk gk-1, and gk-2, We stress that the descent is not Lyapunov because # and c(æ* x e* eh ck-2) 2) is not always negative. Then, we build the correspondence between the mathematical convergence mcasurement and [(<-V((*)) m² ((u))) A big picture of the difference in analyzing adaplive SGD/OGD and AOGD is presented in Figure
1.4 Contributions
Our major contributions are threefold, which are summarized below.
Indeed, the conclusion part of Yang al. 2021b), the authors have listed the momentum variant. as future work.
4

---

Published in Transactions on Machine Learning Research (10/2023)
We propose adaptive online gradient descent algorithm for pairwise learning with simple sam- pling strategy. The proposed algorithm uses adaptive stepsize and momentum, requiring only a small overhead in memory and computational costs.
We present the convergence results for the proposed algorithm under different settings, inchuding strongly convex, general convex, and nonconvex cases. The use of adaptive stepsize and momentum requires non-trivial techniques for the convergence analysis. We also provide theoretical explanations for why our proposed algorithm can accelerate OGD.
We verify the efficiency of the proposed AOGD the benchmark online AUC maximization task, showing that AOGD outperforms OGD.
1.5 Notation
Throughout this paper, we use boldface letters to denote vectors, e-g., Tc y E The jth coordinate of the vector is denoted by zj. The Le norm of the vector is denoted by ||œ||. We denote E[-] as the expectation with respect to the underlying probability space. We denote the minimum value of the function f over IC as minx f, and denote (r) as the projection of æ onto the set K. For two positive sequences (ax, by bx)x20, ag = O(bg) means that there exists > such that a₃ < Cb₃. The notation a₃ = O(bx) indicates that ag = (bb) and by = O(a)). We use aş = ((xx) and aş = (bb) to hide the logarithmic factor but still with the same order. We use aj 2 ((bb) to present the relation a 2 Cbg with C O.
1.6 Organization
We organize this paper as follows: In Section 2 we present assumptions and theoretical convergence results for AOGD under general convex, strongly convex, and nonconvex settings. We mumerically verify the efficiency of AOGD and compare to the benchmark OGD Section 3 More related works are discussed Section followed by concluding remarks. The detailed proofs are provided in the supplementary materials.
2
Convergence Analysis
2.1
Assumptions
We first collect several necessary assumptions for the convergence analysis of AOGD:
Assumption
The function F() differentiable, and its gradient T.- T.-Töpschitz, i.e.,
IVF( (F(y: s L| - yll. Va,y y E K, E..
(3)
Assumption 2: The gradient of E, is uniformly bounded, i.e., [VF(2; S B for some constant B > 0, Va E K, and E. E.
The Lipschitz smooth gradient assumption is widely used in the (non)convex optimization and pairwise
learning communities. While Assumption 2 is frequently used in the adaptive SGD community, see, e.g.,
Duchi et al.) 2011 Reddi et al. 2018 Chen et al. 2019 Ward et al. 2019 Zou et al. 2019 Li & Orabona 2019 K Note that when K. is bounded
Duchi et al. (201 Reddi et al. (2018) have assumed the boundedness of the constrained set Assumption directly holds for the continuity of the gradient but not vice versa.
Moreover, Assumption indicates the following estimate of Vf(x))
f=)]l| = [IE..' - E < Eg (VFx: B.
Using mathematical induction, we can see that the momentum m also enjoys the uniform bound according to Assumption 2. Furthermore, stress that we do not need to assume the variance is bounded, which is indicated by Assumption 2 since have
E VF((: S V
B².
Thhe uniform assumption presented in (Li & Orabona 2019 enjoys another presentation, L.e., (Assumption (H2)) presented as 1f(x)-((v) Gl| -yl. Note that when differentiable, it is equivalent to sup,, [=)(( S G. With bounded assumption for F(w;() f()) (Li & Orabonal 2011)) which is indeed the uniform bound assumption.
Any continuous function is uniformly bounded over closed bounded subset. of Rd.
5

---

Published in Transactions on Machine Learning Research (10/2023)
Assumptions 1 and 2 will be used in the analysis of AOGD for all different scenarios in the subsequent analysis.
2.2 General Convex Cases
In this subsection, we present the convergence result of AOGD for the general convex case, i.e., F(x; 5, is convex with respect to and any fixed e. Note that the convexity of g, indicates the convexity of f(x) in [p but not vice versa.
Thcorem (General Converity) Let Assumption 1 hold, and l1g 2 8 > for some constant o, and F. be conver. Assume (a")221 is generated by AOGD for pairwise learning, x arg mingek f(x), and K. is additionally bounded, k..,, maxx,yeK || -ll S D. Then we have
Σ
C1 + (2)
E
f
-=
min f K x
(4)
K
K
where 01 := Eve [1="""="-""" =111 3B² and 02 c2(K)
2(1-0)m V8
=
n+2D² 2(1-0)
+ (n1 + 1)
EVOK+T +
4L +
212 vB
In EVeR
v8
Assumption 2 is implicitly used in Theorem because we have assumed the boundedness of the constrained set IC, The bounded constrained set is indeed stronger than the uniform bounded gradient assumption. We leave how to relax the bounded set assumption as future work. From Theorem [ we can see that the convergence rate dependent on [[VvK). The boundedness of the stochastic gradients indicates that E[vE*] OVKK), which means the worst convergence rate of AOGD is Ö 1
We notice that the
VK
convergence rate Ō VK coincides with the rate OGD for pairwise learning in the general convex case 2021bb. However, in some cases [[[vk] can decay faster than O(VK), based which can
Yang el al. establish an accelerated rate of AOGD.
Proposition Assume the conditions of Theorem hold, and assume ElVuk] = O(K)) with 0 < a S 1 Then we have
K k==
-min
min f ④
K Ki-a
If 1 the convergence rate of AOGD is thus better than Ö( theoretical interpretation of why AOGD is possible to be faster than OGD
1 then provides a Yang et al. 2021b
Proposition
VK
Remark 1 Note that the condition 1/2 directly holds due to the boundedness of the stochastic gradients. The fast decoying condition a < 1/2 has been commonly used as a slandard explanation for why adaplive stochastic optimization algorithms often outperform non-adaptive schemes, as shown in several studies [Reddt et al. 2018: Chen al. 2018: 2019 Liu al. 2019). As far as our current knowledge goes, the superiority of adaptive SGD over non-adaptive approaches not well-explained, apart from the assumption that a < 1/2. This assumplion is commondy used in previous works because many braining lasks involve sporse slochastic gradients. However, it is important to note that this assumption is not logical consequence of sparse gradients resulting in a < 1/2. Instead, the assumption is more of a hypothetieal analysis. In summary, while the assumption a < 1/2 is widely employed in the lileralure, we do not have a definilive explanation for the effectiveness of adaptive SGD beyond this assumption. Further research is required to goin a comprehensive understanding of the benefits of adaptive SGD compared to non-adaptive methods.
2.3 Strongly Convex Cases
In this subsoction, we consider the case that the function F(x; E.5') is u-strongly convex for some constant > 0, i.., ((x;,.5) F(y: (VF(y; 8) 2 x yl2.. In particular, if 0, F(x: then reduces to general convex.

---

Published in Transactions on Machine Learning Research (10/2023)
Stepsize rule for the strongly convex case. Before developing convergence guarantee of AOGD for strongly convex cases, we need to select the appropriate stepsize rule for AOGD. We first need to explain the stepsize rule of AOGD for the general convex case, Le., v/v for some constant > 0, is inappropriate for 1 solving strongly convex problems. The boundedness of gradient directly gives us Ve 2 0 VR However,
such & stepsize rule causes the accumulation of stochastic noise; it will not improve the convergence rate of AOGD under strong convexity compared to the rate of AOGD under general convexity. A proper stepsize
choice for the strongly convex case is θ ((t) (Bach & Moulines, 2013)- Indeed, in papers (Duchi et al. 2011
Sun et al. 2020). the authors use the VAVEE stepsize rule for AdaGrad when the problem is strongly convex,
and we follow this stepsize rule for the strongly convex online pairwise learning, Note that VIVEE e
which coincides with the stepsize used for SGD when the undorlying problem is strongly convex, In summary, 2 with step 4', which given below
in the strongly convex case, we replace step of Algorithm
step 4': x+1 = Projjx xx
1 vk
m
(6)
Next, present the convergence rate of AOGD for pairwise learning with the strong convexity assumption.
Theorem 2 Let Assumption 1 hold, and || 2 >
0, and E,g;) be strongly convex. Assume (a*)221 generated by the AOGD for pairwise learning with = 0 using stepsize rule step 4', and x² = mig fxx). By setting nl = 2 then we have
In K K
E[1K" x²11? =
In the strongly convex case, Assumption 2 is equivalent to the boundedness assumption of the constrained set
This is because the function f()) is also v-strongly convex 3 yielding [[V]())] [[][())
V [
y|| I'll with of being the global minimizer of f. When Assumption 2 holds, in Subsection 2.1 we have
shown that [a=]] B over K. Thus, we get |||||| I || æt|| that xt is fixed, and the set I. is then uniformly bounded.
| s + ||-||| when K. Notice
Theorem above shows that AOGD can achieve faster convergence rate under the strong convexity assumption than that for general convex cases. Theorem 2 also shows that in the strongly convex case, AOGD achieves an almost optimal convergence rate of SGD under strong convexity, specifically δ k (the
optimal convergence rale is O according to (Rakhlin al. 2012)). The result in Theorem 2 does not 2 which is infinity when == == 0. For technical reasons,
generalize to the general convex case since we set 1/ = / we set = 0 in Theorem 2, i.e. we only consider the momentum free case. We will consider how to build the convergence rate ① K for AOGD with momentum in our future work.
2.4 Nonconvex Cases
In this part, consider the case when F(a; is nonconvex. The assumptions for the nonconvex case are much milder than the convex and strongly convex cases. We can even get rid of using the projection operator Proje(-) for AOGD. The convergence result of AOGD for the nonconvex case is presented as follows.
Theorem Let Assumptions 1, hold, and let {x* Jx21 be generated by AOGD, and || 2 for some constant 8 > 0. Suppose Vor < C ka for two constants C > 0 and 0 < a S 2, and K. is the full space. Then, we have
G3 + (a(
min
(8)
Kl-a
Taaking expectation of both sides of the inequality F(x:;.e') F(v:E.')) (VF(V:C.')) -0) f1l uvl? gives us the strong convexity
7

---

Published in Transactions on Machine Learning Research (10/2023)
2 where 03 : (1-0)v8 + 4Cf(m²) and ca(K)= = (1+-0m 1- + + 12/0++ In
see that the convergence rate of AOGD is Ō ki-a): and is the worst case due to the boundedness of the stochastic gradient. When 1. we get faster convergence of AOGD compared with OGD SGD in the general nonconvex case.
From Theorem
The conditions of Theorem can also be satisfied by the general convex case without projection. Therefore,
8 also holds when F( ) is convex. However, (8) is weaker than 14 since the convergence rate in ( is not established with respect to the function values.
3 Numerical Results
Table 1: Statistics of the dataset used for contrasting the performance of AOGD and OGD, where n is the number of samples in each dataset, and d is the number of features of each instance in given dataset. All datasets come from the LIBSVM website (Chang & Lin 2011 and they are used in (Yang et al. 2021b).
diabtes
german
ijcnn1
letter
mnist
usps
11
768
1,000
49,90 10,990
15,000
60,000
7,291
d
8
24
22
161
780
256
In this section, mumerically validate theoretical findings for both convex and nonconvex cases. To this end, we compare our proposed AOGD against the baseline OGD proposed in (Yang et al. 2021b)
0
for pairwise lcarning in terms of generalization and rate of convergence with respect to the number of
iteration. We also include the results of AdaOAM in (Ding et al. 2015 : an adaplive online algorithm for AUC maximization. However, we note that the algorithm in (Ding et al.) 2015) is not designed for general pairwise lcarning. Following (Yang al.) 2021b), we consider six benchmark datasets, summarizod in Table D Also, following the data split strategy used in (Yang al. 2021b), for the dataset with multiple classes, we convert the first half of classes to the positive class and the second half of classes the negative class.
For each dataset, we use 80% of the data for training and the remaining 20% for testing. All the reported results are based on 25 runs with random shuffling. The generalization performance reported using the average AUC score and standard deviation on the test data. To determine proper hyperparameters for OGD, AOGD, and AdaOAM, we conduct 5-fold vrossvaalidttin on the training sets: 1) for OGD, we select stepsizes 7/ 17 10: -5:-5:57 and the parameter space K. is to be the 2 centered at the origin with radius R E 10|- ; 2) for AOGD, we let f 0.9 and select stepsizes ne 7) E 10(-6:5; and the parameter space K. is also the I22lball centered at the origin with radius R E 10 10/-3,31; 3) for AdaOAM, we select stepsizes = E 10[-5:5) 5555 and the parameter space K. is set to be the -all centered at the origin with radius R E 10(-3,3)
Convex case:
We run experiments on AUC maximization using the following convex loss function f(w; (x, v), (x',v) l(w (x x' [0)))===1====11 + E(w (TTT(a (æ' x)) 11))==)=1
where
y and y =11,
I==1A==-1)
otherwise.
and similarly for Iyy=- Also, l is a surrogate loss function, e.g., the hinge loss
0 - otherwise.
il i
((t) -1 (1- - 1)+
IIn Yang
2021b1 the authors have shown that OGD remarkably outperform existing algorithms, including OLP
Kar
20133. OAM
(Zhao al. 2011
SGDpair
(Lei et al. 2020). and SPAUC (Lel Ying 2021
stands integers
5, 5).
8

---

Published in Transactions on Machine Learning Research (10/2023)
Remark 2
The loss function above follows the setup in (Yang et al. 2021b) which is designed for the AUC marimization problem with data stream (x. v) sumpled from a distribulion that contains both posilive and negative somples by utilizing the indicator function -iz=1Ag==-1 and M1 We want to mention that the second term is not presented in the main text of (Yang et al. 2021b) but implicitly utilized their code 8 on which our implementation is bused. In parlicular, in both OGD and AOGD, the loss activaled or non-zero whenever the consecutive sample pairs () and (x',y') are of opposite labels, i.e,, y = and y' or y - and s/ 1.
We now provide further clarification on the pairwise model and AUC mozimization: In model the distribution for and ç' is assumed to be the same. This is in contrast to the early AUC marimization formulation, as seen in (Zhao et al., 2001)), which does not have this property. In the early formulation, the positive and negative classes are treated differently, with potentially different distributions. However, we can introduce indicator functions and show that the AUC marimization can be represented as a special form of as above.
A natural question that arises is why we would choose to reformulate the AUC marimization problem into the model [ At first glance, there does not seem to be any apparent advantage to such a reformulation, as the algorithm only works when a negative sample is encountered along with positive sample. In the worsl-case scenario, if all the negative labels are encountered before the positive labels, the algorithm would almost output no predictions.
We provide a necessory explanation here:
a) The worst-case scenario mentioned above is highly unlikely to occur because we assume that the data is independently and identically distributed from the underbying distribution.
b) In the online setting, the labels are unknown in advance. While the work of Zhaa et al. (2011) discusses the online scenario, they employ an "update buffer" data pre-processing step to divide the data and subsequently run the algorithu offline. Therefore, we cannot directly apply the formulation described in [Zhao et al. 2011). To address this, it is more flexible to utilize the formalation presented in (Yang el ul.) 20.160. This formulation is beller suited for online learning, as it does not require an offtine processing step like the one used in [Zhao et al., 2011))
c) Existing results from (Yang al. 2021b] demonstrate that the formulation 1 outperforms pre- vious methods, even when a negotive sample encountered along with a positive sample. This is because previous methods often have high gradient complerity at each iteration, while the online complerity is very small in the proposed formalation.
In summary, the reformulation 4 allows for more flexibility in the optimization process and has the potential to yield better results in practical scenarios.
Figure plots the AUC scores of AOGD, OGD, and AdaOAM against the number of iterations (in log scale)
Table 2: Average AUC scores + standard deviation with convex loss function across the six benchmark
datasets listed in Table ! The best results are highlighted in boldface.
Algorithm diabetes
german
1jenn1
letter
mnist
usps
ADGD
.831 + .027
.795 + .026
.934 + .002
.814 + .006
.931 + .002
.925 + .004
OGD
.831 = 000
.933 + .021
.934 + .002
.810 + .007
.932 + .001
.926 + .006
AdaDAM
.829- = .027
.792 + .028
.934 = .003
.814 + .009
.932 - .002
.924 - .005
Table 2 summarizes the generalization performance between AOGD and OGD. The results for AOGD and AdaOAM are obtained from our above experiment and the results for OGD are adapted from YYang et al.
NNumber of iterations N is given by 22n//2+4 where Noog is the log-scaled number of iterations. on the six benchmark datasets listed in Table The numerical results on the six benchmark datasets show that AOGD converges faster than OGD and AdaOAM general, confirming our theoretical results.
9

---

Published in Transactions on Machine Learning Research (10/2023)
diabetes
german
0.80
0.80
0.75
AUC score
0.70
0.75
AUC
0.65
AOGD
ADGD
0.70
DGD
OCD
0.60
AdaDAK
AdaOAM
5
10
15
20
0
5
10
15
20
Iterations (log scale)
Iterations (log scale)
ijennl
letter
0.80
0.9
0.75
AUC score
0.8
0.70
AUC
0.7
0.65
ADGD
ADCD
0.6
DGD
OGD
0.60
AdaOAM
AdaDAM
0.5
10
15
20
25
10
20
30
Iterations (log scale)
Iterations (log scale)
mnist
uepe
0.9
0.9
AUC score
AUC score
0.8
0.8
0.7
ADGD
0.7
ADGD
0GD
OGD
0.6
AdaDAM
0.6
AdaDAM
10 15
25
Iterations (log scale)
Iterations (log scale)
Figure 2: The AUC score of AOGD and OGD against the number of iterations (in log scale) for AUC maximization with convex loss (hinge loss). It evident that AOGD converges faster than OGD and AdaOAM in general, confirming our established thcoretical results for AOGD.
2021b). Overall, AOGD generalizes well OGD and AdaOAM as the peak performance of these three methods are comparable. Establishing the generalization of OAGD is an interesting future direction.
Non-convex case: We follow the setting in Appendix G of (Yang et al. 2021b on AUC maximization using the logistic link function logit(t) = (1 + exp(-t))- and then the square loss function E(t) (1 t) Hence, the loss function for the AUC maximization problem is given by the non-convex function
f(w; y), (x))))) = Il-logitt (wT(x--)) (x-xx') " 41=-nn==-1) + (1- logit (w (x' [x)) -y==-1g/=1))
We plot in Figure 3 the AUC scores of AOGD, OGD, and AdaOAM against the number of iterations on the six benchmark datasets listed in Table ! The numerical results on the six benchmark datasets show that AOGD converges faster than OGD and AdaOAM in general, confirming our theoretical results.
10

---

Published in Transactions on Machine Learning Research (10/2023)
Table 3: Average AUC scores standard deviation with nonconvex loss function across the six benchmark
datasets listed in Table The bost results highlighted in boldface.
Algorithm
diabetes
german
ijenn1
letter
mnist
usps
ADGD
.834 - .022
.797 + .023
.935 1 .002
.815 + .005
.932 _ .002
.928 1 .004
OGD
.829 = .033
.994 + .022
.934 + .002
.815 + .003
.931
+ .002
.926 + .005
AdaOAM
.831 .025
.789 + .021
.931 + .002
.815 + .006
.932 + .003
.926 + .007
diabetes
german
0.80
0.80
0.75
AUC score
0.70
AUC
0.75
0.65
DGD
OGD
AdaDAK
AdaDAM
20
10
20
Iterations (log scale)
Iterations (log scale)
ijenni
letter
0.50
0.9
0.75
AUC score
0.8
0.70
AUC
0.7
0.65
ADGD
ADGD
0.60
OGD
0.6
OGD
AdaDAN
AdaDAM
0.55
0.5
20
30
Tterations (log scale)
Iterations (log scale) usps
mnist
0.9
0.9
AUC score
0.8
0.8
AUC
0.7
ADGD
0.7
ADGD
OGD
0.6
AdaDAM
AdaDAM
0.6
0
0
20
25
Iterations (log scale)
Iterations (log scale)
Figure 3: The AUC score of AOGD, OGD, and AdaOAM against the number of iterations (in log scale) with non-convex loss function. In this case, AOGD converges faster than OGD and AdaOAM in general, confirming our established theoretical results for AOGD. In particular, the slower convergence of AdaOAM is more prominent in the non-convex case.
4 More Related Works
Because offiine methods employ the ERM-like policy, the core problem of most offline methods establishing the generalization bound of the finite-sum model with statistical learning theory algorithmic stability
11

---

Published in Transactions on Machine Learning Research (10/2023)
AAgarall & Niyogi 2009 Jin et al. 2009 Wang et al. 2019
Gao & Zhou 2013 Lei et al. 2020 It is worth
mentioning that the difficulty in the generalizat ceneralization analysis for pairwise learning lies in that the objective functions fail to be i.d. with each other, which breaks the fundamental assumption in statistical learning thoory and the algorithmic stability communities.
The online methods for pairwise learning assume the model accesses a data stream of i.i.d. samples, including online AUC maximization algorithms (Zhao et al.] [001]] Yiin et al.] 2016 Liu al 2018; Natole et al.
2018
Lei & Ying
2021 Guo et al.
2020), online metric learning algorithms (ShleevShwwart
al.) 2004
Davis et al., 2007;
Jain et al., 2008
Jin et al.
2009), online learning to rank (Rejchel 2012 Schuth et al.
2013 Zoghi et al.
2017 Li et al. 2019). neural link prediction (Wang et al.] 2021), etc. The online AUC
maximization is proposed by Zhao et al.
2011) with theoretical guaranlees. In the paper (Ying et al. 2016
a stochastic online AUC maximization algorithm is proposed from the perspective of a saddle representation.
The main advantage of the algorithm in (Ying et al.) 2016) is to avoid storing all previous examples and sccond-order covariance matricos. Loveraging saddle representation, Liu et al., (2018) propose a faster online AUC maximization algorithm with provably improved statistical convergence rates. The stochastic proximal algorithms for AUC maximization with non-differentiabbe regularization are proposed and studied in (Natole ct al. 2018). To make the algorithm scalable to large-scale streaming data, Lei & Ying) (2021) propose a new stochastic proximal algorithm. In the paper (Guo et al. 2020), the authors consider the distributed setting and propose a communication-effcien stochastic AUC maximization with deep neural networks. Shalev-Shwartz et al. (2004) propose an online algorithm for supervised learning of pseudo-metrics. In DDviis al.] 2007), the authors present an information-theorett approach for online metric learning. In Jainn et al. 2008), leveraging the LogDet regularization, the authors propose fast online metric learning for the similarity scarch. The generalization bound of regularized distance metric learning is established in (Jin) et al. 2009). Rejchel (2012) consider ranking estimators that minimize the convex empirical risks and prove their generalization bounds. A framework of online learning to rank is proposed by [Schuhh et al. (2013). In the paper (Zoghi et al. 2017), the authors investigate online learning to rank in stochastic click models. Paper (Li et al. 2019) introduces a new model for online ranking with features. The differentially private
pairwise learning has been recently studied, and representative ive works include (Huai et al. 2020 Yang el al. 2021a; Xue et al. 2021 Yang al. 2021b).
5 Conclusions
In this paper, we propose adaptive online gradicnt descent algorithms solve pairwise lcarning problems and establish their theoretical performance bounds in strongly convex, convex, and nonconvex seltings. Our theoretical results explain why the convergence speed of adaptive online gradient descent can outperform the one without adaptive stepsize for pairwise lcarning. We also provide numerical experiments to demonstrate the efficiency of the proposed algorithm.
Limitation and future work. There are two major limitations in our analysis: 1) we assume the set IC is bounded in establishing Theorem [ and 2) the convergence rate in Theorem 2 is analyzed for the adaptive online gradient descent without momentum. We leave how to overcome the above two limitations as future work. There are numerous other avenues for future work, including 1) Can we establish the lower bound of the convergence rates for the adaptive online gradient descent applied to pairwise learning? 2) Can we extend the online adaptive gradient descent to the proximal settings to solve nonsmooth pairwise learning problems?
12

---

Published in Transactions on Machine Learning Research (10/2023)
Broader Impact Statement
N/A
References
Shivani Agarwal and Partha Niyogi. Gencralization bounds for ranking algorithms via algorithmic stability. Journal of Machine Learning Research, 10(2), 2009.
Francis Bach and Eric Moulines. Non-strongly-coovex smooth stochastic approximation with convergence rate O(1/n). Advonces in neural information processing systems, 26, 2013.
Chih-Chung Chang and Chih-Jen Lin. LIBSVM: A library for support vector machines. ACM Transactions on Intelligent Systems and Technology, -2::1227:27, 2011. Software available at http://wwx csie ntu. edu. cchuttr/-cjjim/libbee
Xiangyi Chen, Sijia Liu, Ruoyu Sun, and Mingyi Hong. On the convergence of a class of Adam-type algorithms for non-convex optimization. Tn International Conference Learning Representations, 2019.
URL
Zaiyi Chen, Zhuoning Yuan, Jinfeng Yi, Bowen Zhou, Enhong Chen, and Tianbao Yang. Universal stagewise learning for non-convex problems with convergence averaged solutions. In International Conference Learning Representations, 2018.
Jason V Davis, Brian Kulis, Prateek Jain, Suvrit Sra, and Inderjit S Dhillon. cntrmattion-hhorette metric learning. In Proceedings of the 24th international conference on Machine learning, pp. 209-216, 2007.
Yi Ding, Peilin Zhao, Steven Hoi, and Yew-Soon Ong. An adaptive gradient method for online maxi- mization. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 29, 2015.
John Duchi, Elad Hazan, and Yoram Singer. Adaptive subgradient methods for online learning and stochastic optimization. Journal of Machine Learning Research, 12(Jul):211-2113) 2011.
Wei Gao and Zui-Hua Zhou. Uniform convergence, stability and learnability for ranking problems. In Suunty-Thire International Joint Conference on Artificial Intelligence. Citeseer, 2013.
Wei Gao, Rong Jin, Shenghuo Zhu, and Zhi-Hua Zhou. One-pass AUC optimization. In International conference on machine learning, pp. 906-914. PMLR, 2013.
Zhishuai Guo, Mingrui Liu, Zhuoning Yuan, Li Shen, Wei Liu, and Tianbao Yang. Commmication-efficienn distributed stochastic AUC maximization with deep neural networks. In International Conference on Machine Learning, pp. 3864-3874. PMLR, 2020.
Ting Hu, Jun Fan, Qiang Wu, and Ding- Xuan Zhou. Learning theory approach to minimum error entropy criterion. Journal of Machine Learning Research, 14(2), 2013.
Mengdi Huai, Di Wang, Chenglin Miao, Jinhui Xu, and Aidong Zhang. Pairwise learning with differential privacy guarantees. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 34, pp. 694-701, 2020.
Prateek Jain, Brian Kulis, Inderjit Dhillon, and Kristen Grauman. Online metric learning and fast similarity search. Advances in neural information processing systems, 21, 2008
Rong Jin, Shijun Wang, and Yang Zhou. Regularized distance metric learning: Theory and algorithm. Advances in neurol information processing systems, 22, 2009.
Purushottam Kar, Bharath Sriperunbudur, Prateek Jain, and Harish Karnick. On the generalization ability ouline learning algorithms for pairwise loss functions. In Sanjoy Dasgupta and David McAllester (ods.), Proceedings of the 30th International Conference on Machine Learning, volume 28 of Proceedings of Machine Learning Research, pp. 441-449, Atlanta, Georgia, USA, 17-19 Jun 2013. PMLR. URL www.iiinnnmmm......mm mlr. wwt.eerrrssev/aaaeeeeee html
13

---

Published in Transactions on Machine Learning Research (10/2023)
Diederik P. Kingma and Jimmy Ba. Adam: A method for stochastic optimization. In International Confer- ence on Learning Representations, 2015.
Brian Kulis al. Metric learning: survey. Foundalions and Trends0 in Machine Learning, 5(4):287 364, 2013.
Abhishek Kumar, Alexandru Niculescu-Mizii, Koray Kavukcoghu, and Hal Daumé. A binary classification framework for two-stage multiple kernel learning. In Proceedings of the 29th International Coference on International Conference on Machine Learning, pp. 1331-1338, 2012.
Yunwen Lei and Yiming Ying. Stochastic proximal AUC maximization. Journal of Machine Learning Research, 22(61):1 45, 2021.
Yunwen Lei, Antoine Ledent, and Marius Kloft. Sharper generalization bounds for pairwise learning. Ad- vances in Nearul Information Processing Systems, 33:21236 21246, 2020.
Shuai Li, Tor Lattimore, and Csaba Szepesvári. Online learning to rank with features. In International Conference on Machine Learning, pp. 3856-3865. PMLR, 2019.
Xiaoyu Li and Francesco Orabona. On the convergence of stochastic gradient descent with adaptive stepsizes. The 22nd International Conference on Arlificial Intelligence and Slalistics, pp. 983 992, 2019.
Mingrui Liu, Xiaoxuan Zhang, Zaiyi Chen, Xiaoyu Wang, and Tianbao Yang. Fast stochastic AUC maxi- mization with -(o/)))-oneeeeeencee rale. In International Conference on Machine Learning, pp. 3189-3199
PMLR, 2018.
Mingrui Liu, Youssef Mroueh, Jerret Ross, Wei Zhang, Xiaodong Cui, Payel Das, and Tianbao Yang. Towards better understanding of adaptive gradient algorithms in generative adversarial nets. In International Conference on Learning Representations, 2019.
H. Brendan McMahan and Matthew Streeter. Adaptíve bound optimization for online convex optimization. COLT 2010, pp. 244, 2010.
Michael Natole, Yiming Ying, and Siwei Lyu. Stochastic proximal algorithms for AUC maximization. In International Conference on Machine Learning, pp. 3710-3719. PMLR, 2018.
Thomas Peel, Sandrine Authoine, and Liva Ralaivola. Empirical bernstein inequalities for u-statistios.
Advances in Neural Information Processing Systems, 23, 2010.
Alexander Rakhlin, Ohad Shamir, and Karthik Sridharan. Making gradient descent optimal for strongly convex stochastic optimization. In Proceedings of the 29th International Coference on International Con- ference on Machine Learning, pp. 1571 1571-1578, 2012.
Sashank J. Reddi, Satyen Kale, and Sanjiv Kumar. On the convergence of Adam and beyond. In International Conference on Learning Representations, 2018. URL
Wojciech Rejchel. On ranking and generalization bounds. Journal of Machine Learning Research, 13(5). 2012.
Anne Schuth, Katja Hofmann, Shimon Whiteson, and Maarten De Rijke. Lerot: An online learning to rank framework. In Proceedings of the 2013 workshop on Living labs for information retrieval evaluation, pp. 23 26, 2013.
Shai Shalev-Shwartz, Yoram Singer, and Andrew Y Ng. Ouline and batch learning of pseudo-metrics. In Proceedings of the twenty-first international conference on Machine learning, pp. 94, 2004.
Tao Sun, Linbo Qiao, Qing Liao, and Dongsheng Li. Novel convergence results of adaptive stochastic gradient descents. IEEE Transactions Image Processing, 30:1044-100 1056, 2020.
Tijmen Tieleman and Geoffrey Hinton. Lecture 6.5- B.S-RMPrrop, coursera: Neural networks for machine learning. Universily of Toronto, Technical Report, 2012.
14

---

Published in Transactions on Machine Learning Research (10/2023)
Boyu Wang, Hejia Zhang, Peng Liu, Zebang Shen, and Joelle Pincau. Multitask metric learning: Theory and algorithm. In The 22nd Intervational Conference on Artāficial Intelligence and Statislics, pp. 2362-3371 PMLR, 2019.
Yuyang Wang, Roni Khardon, Dmitry Pechyony, and Rosie Jones. Generalization bounds for online learning algorithms with pairwise loss functions. In Conference on Learning Theory, pp. 13-1. JMLR Workshop and Conference Proceedings, 2012.
Zhitao Wang, Yong Zhou, Litao Hong. Yuanhang Zou, and Hanjing Su. Pairwise learning for neural link prediction. arXiv preprint arXiv:211 012-2112.02200 02.929 2021.
Rachel Ward, Xiaoxia Wu, and Leon Bottou. Adagrad stepsizes: Sharp convergence over nonconvex land- scapes. In International Conference on Machine Learning, pp. 6677-6686. PMLR, 2019.
Kilian Q Weinberger and Lawrence K Saul. Distance metric learning for large margin nearest neighbor classification. Journal of machine learning research, 10(2), 2009.
Eric Xing, Michael Jordan, Stuart J Russell, and Andrew Ng. Distance metric learning with application
clustering with side-information. Advances in neural information processing systems, 15, 2002.
Zhiyu Xue, Shaoyang Yang, Mengdi Huai, and Di Wang. Differentially private pairwise learning revisited. IJCAI, 2021.
Zhenhuan Yang, Yunwen Lei, Siwei Lyu, and Yiming Ying. Stability and differential privacy of stochastic gradient descent for pairwise learning with non-smooth loss. In International Conference on Artificial Intelligence and Statistics, pp. 2026 2034. PMLR, 2021a.
Zhenhuan Yang, Yunwen Lei, Puyu Wang, Tianbao Yang, and Yiming Ying. Simple stochastic and online gradient descent algorithms for pairwise learning. Advances in Neural Information Processing Systems, 34, 2021b.
Yiming Ying and Peng Li. Distance metric lcarning with eigenvalue optimization. The Journal of Machine Learning Research, 13(1):1-26, 2012.
Yiming Ying and Ding- Xuan Zhou. Online pairwise learning algorithms. Neural computation, 28(4):743 777, 2016.
Yiming Ying, Longyin Wen, and Siwei Lyu. Stochastic online AUC maximization. Advances in neural information processing systems, 29, 2016.
Peilin Zhao, Steven CH Hoi, Rong Jin, and Tianbo Yang. Online AUC maximization. In Proceedings of the 28th International Conference on Machine Learning TCML, pp. 233-240 2011.
Masrour Zoghi, Tomas Tunys, Mohammad Ghavamzadeh, Branislav Kveton, Csaba Szepesvari, and Zheng Wen. Online learning to rank in stochastic click models. In International Conference on Machine Learning, pp. 4298. PMLR, 2017.
Fangyu Zou, Li Shen, Zequn Jie, Weizhong Zhang, and Wei Liu. A sufficient condition for convergences of Adam and RMSProp. In Proceedings of the IEEE Conference on Computer Vision and Potlern Recognition, pp. 11127 11135, 2019.
15

---

Published in Transactions on Machine Learning Research (10/2023)
A Proofs of Results in the Convex Scenario
A.1 Technical Lemmas
Given any x² argk min f, in the (strongly) convex setting, we introduce the following notation
Øk =
+ E
L
11
B
Vi
Vok-2
Vok-i
V8.
Vik-2
VoL
AІ == |[[|m (1²//((()))))
(9)
Bg = E ((xx xx m
Cg = (n0 + 1-
2 A + (1 0)
We have the following lemmas.
Lemma [Lemma 9 in the appendir, [LA Orabona 2019 non-increasing function. Then have
Let 01 02,...,, OK be non-negatine, and h be
Ex au
aghian +
>aa)
a.) S
h(t)dt.
Lemma 2 Assume h221 is generated by Algorithm
then we have
K
K
Σ
Ax
S
B
k=1
Lemma 3 Assume h221 is generated by Algorithm
and ||gs|
v O, then have
K
K E
E Enn w
112 E 1h x. k
<
Bllgg k 1/
Lemma 4 Assume t 1221 is generated by Algorithm then we have
FIVF((* - 111 2z kh 112
Lemma 5 Assume ( J221 is generated by Algorithm and Assumptions and hold, then the following result holds
By < 0B Cn + (1- 1)8( -(x²))
A.2 Proof of Theorem 1
Given & E Zt, with Lemina and mathematical induction, we have the following inequality
By S 0² Bi
Σ
gh
+
Σ (1 11 0)0 10 f(xx))
i=1
1=1
Notice that ml = 0 and Bi = 0, we get
B& <
--i +
Σ (1
-)0-=---B(((0')) -(aa)))))
(10)
1=1
16

---

Published in Transactions on Machine Learning Research (10/2023)
Summing the inequality
100
from k = 1 to K gives us
k
K
K k-1
BB
<
C +
ΣΣ (1 1- - f(x')
k=1
k= i=1
k= t=1
Σ
CF
k=
+ (1- 0) Σ
B B(f(x') - f(x")))
0
Therefore, we have
K
K
Bg ΣK Cj
-
(11)
0)
(1 0)2
The scheme of the algorichm indicates that
x A+1 = Projx (x* - 1/m=m//ff )))
We then get
| k+l x²11 ==||2=||Pooxxdddf 1mmmm )1=+)())) x²11
|Projx = |Proix - nmm* (1² - (x:)x(
I || nmn* (1 x x=2
Multiplying both sides with (u are then led to
(u 112 s (u*)å - 2=111 2m/mm* xx - x²) + m/2 112/(1=)3
which is equivalent to Taking the total expectation of both sides of the above equation gives us
(1* ( x 112 S ( - x²1 + (m x - x²h)
+ 1 I & (2/( + ((o (o*) ||[ x ==1
B2nBr S B(u*)) $ x01 B(u*+1) || x0
x
(12)
+ Ax + (B(v - E(or)b)D²
Summing 12 from to K gives us
B+)((1 0) S
EVel x -x
"
A
D
EV v++
21y(1 - 0)
2(1 0)
(1-
Together with
we then have
EVol x x 1=112
E(s(**)- - -s(x)) 5
2n1(1
1=1
(13)
K
D2
ΣK Ck
+
7
A + (1- 0)
Bvok+T
2(1
0)
(1- 0)2
We turn to bound the right-hand side of 13 and get the following bound
K
17
17 Elo K4t
Au 5
(14)
2(1
2(1 0)
17

---

Published in Transactions on Machine Learning Research (10/2023)
On the other hand, we can get
Σ レ Ck
v
1/0
E(v
E(u
+
2L
Eh
x++
K
Eeb
0)2
(1
0)
(1
0)2
5
(1
0)2
k=1
(15)
3B2
gx+1
< (1 0)2
n78
B(u
+
2L
E In
v8
v6
E In
(1 0)
8
(1 (1- 0)
Substituting the bounds
14 and
15 into
13
we are then led to
((((z") - -(xx))
1=1
IE 0d | - x²11
77 7 2D2
n7 +
EVvK+I
(16)
+
211(1 8)
2(1 8)
(1 11-60 0)2
4L
2L
Vuk+
3B²
+
En
(1 0)2
(1 0)2
v8
(1- 0)=
Notice that - In(.) and - are both convex when is positive, using Jensen's inequality gives us
hn IE & -Enn
B(V S -
Votk
Eln SIEVVRRt E
V
EV ok
Therefore, 16 can be presented as
K k== K
ci + (
min f
S
where
EVe'l 1 x11
3B²
C1 =
+ (1- 0)2v8'
2(1- - 0)m
and
(2(K) := 17221* 110 + 1 2(1 0)
4L
2L
E EVok+I
+
BVU++ + +1
+
In
(1 0)2
(1 0)2
(1 - 0026
v8
B Proofs of Results in the Strongly Convex Scenario
B.1 Proof of Proposition 2
The boundedness of the gradient and the strong convexity indicate IC is bounded, whose radius is assumed to be >>0 0. Notice that the operator (.)j.c()) contractive, as = 0, we get
Blaakt1 x²1 E Projic
m / vk) x=1|
Vi"
E Projx
1
m² /V (x))x
Vk
< x*
m // x='1
V/
Fa ek ek
x x²)
n E
El
x
112
2 17
E
+
m & 11//02
Vk
Vuk
k
112
lm 1/2
E (1 2mp / kon
E *
xz 112]
12
k
yx
+ Vk
"
B([F(x";E*
: ek)] ///
18

---

Published in Transactions on Machine Learning Research (10/2023)
where we used the strong convexity of F(x; , (*-1). Now, we turn to bound
B([((a"i" ( : ()/Voo))
With direct computations, we have the decomposition
B([F(="; - F( 1//V
= =B([F(=' 15 - - F(x ,e _ -
1)/ V 2)
+ B([F(s k - - F [1x (
5 _ 1)] V 2
+ 2 e [F(x") , : 1111)1 x (1/V - 1/
Vk
consequently,
B( ; 5 ch-11 - ; ck- ( (1-1)]//v>))
I B (m* k 11 VF k 11 ck eh (k-1))
DB B(1 B(1/V// x - 1/Vo*)
vk Iv 2
1 11 |m-
VF
1. ck 112 1|
2/k- -1
2vK -1
DB
B
B(1/
/ - 11/Vo*
B(1/ v - 1/V-1111
Vh
Tvo
1
E(
m
112
DB
/ -1/obh
v6
Vk
VT:
B
EE
uk-2 1/ 1
VK- IV8
where we used (([F(x=: ch ; sk-1)
Fi
ck 5h
ok 2 = [fxx)) - s(a f(** Vo-2 S 0. Let-
ting
B
and Bx == -ivk-T
E |im 2-1
VV 55* 11
+ 2D
- -1/Vo)) +
2v
Vkvk-
VI E(1/VE+-1 1/ V / +
28g
1 Im
1
a&+1 S (1 ))xx + Bz.
With direct computations, we have
1
03 < 02
+ 122
2
2
1
2
04
03 A3
02
3
B2 + 83,
3
3
3
1
3
0s
+
31
<
02
+
B2 + 33 + 84.
4
4
4
:
aK+1 <
02
Σ
K
k3
K
K
k=
Notice that
kB = (E | -1 ||
FF ck 5 1112
+ =E
+ E(11VV p 1 1/Vo*)
-
2
m 113
+ +E(I/V - 1/ // +
E
bk
19

---

Published in Transactions on Machine Learning Research (10/2023)
LVF("" 1 111
we just need to compute Ex=1
By using Lemma we have
E V
F
ch 5h- || h22 s 21 x=
113/ 2E 1
With the fact
11g *
112
11
S
+ B² -B1101
2
we then get
VF Ro
1, 1, ck- 111
E
O vl
2k-2
km
With Lemma
we can get
k
In K
kBp = 0(nv*) = O(I () = 0K+1
K
k=
C Proofs of Results in Nonconvex Scenario
C.1 Additional Technical Lemmas
In the nonconvex case, denote the following items to simplify the presentations of the technical lemmas
Aς = E 1|/////
Bx = E (- V ((=*), m (1xx//()))))))))))))))){)))
(17)
Ok = AnAr + 2(1 - F) |1g / + +611 - 0) B2 (1 (2) 1
(1--) /V8 + - 20 1/2) x k-1 1|2.
Lemma Assume {a* J221 generated by Algorithm
then we have
K
K E 1
Σ
A
< En 5
A==
Lemma 7 Assume (x" Ju21 is generaled by Algoritlo and the functions are nonconeer. Let K. be the full space and Assumptions and
hold, then the following result holds
BB +
0)
(IV/(<>>1P//(""> S S0 Cz.
2
C.2 Proof of Theorem 3
According Lemma we have
0
K-1
(1
+ -Bx
1)
B₁ Σ
k=1
k=1
K-1
K
B²
$ < 10-1) B +
C +
(18)
v8
1=1
1=1
The Lipschitz property of the gradients gives
Lil - xx
LTÿ
- -B <
EVVS((
x A+1
B +
An.
(19)
2
20

---

Published in Transactions on Machine Learning Research (10/2023)
Combining with 19 we get the following estimate
K
K-1 Av + 2f(x*)
Σ
B&
S Ln
(20)
k=1
k=1
On the other hand, with Lemma 3
have the following bound
2
K
20m
K
6
1k 12/8 5/2)) 7)
Cx
A
+ (2r.
(21)
v8
k=1
Using [Lemma 2,
Li & Orabona
2019
and Lemma
6
we have
K
A S El K
(22)
Substituting
22
21 K
and
20
into
18
then we get
E [IV
((({)))
k=1
(1+ 0)m
vk
(7 (7- 60) 2f(x*)
21 1V 12/0+ E In (0(0))))
(23)
1
(1 - 0)58
7
Notice that
1. Cka
then we have
(u))z
K
K
E ((IIF("")P/")"))
min E Vf Iskc k
k
k=
We then complete the proof by using the fact that 0 < I-a following estimate
1
< when 0 < a & 1/2. Thus, we can get the
C3 cc)
min 1sk5k
<
KI-0
where
C3 = 2( (17-68)BB B2 4Cf(x')
(1-0)V8
7
and
(k(K) = ( (1 (1+00) O)m
1 + 2T. / + 1.2/5 + 5/2) In( CK
Proofs of the Technical Lemmas
D.1 Proof of Lemma 2
With the fact that m = (1 -1 "" when & 2 1, have
d
d
k
m /// /2/(0/)>/1
Σ
m (1 3 Σ
0)2
Σ
g g
5=1
Σ (1 0)2(
g (g))2/(11)))
1=1
d
(
< Σ (1 0)2.
Σ
gk ( (3)))
1-0
1=1
1=1
k
*
=
(1 - 0)
Σ
gh ||
2) 2/ (1 11-))-
8)
Σ
gh '1''' 112 12/("))
]=1
j=1
21

---

Published in Transactions on Machine Learning Research (10/2023)
where a) uses the Cauchy's inequality وو S ag)
EEj=1 03) with og (ot)) and
by 0 - o./ (v b) is due to v S oh when j S k. Thus, we are led to
K
K K
1
(v)))))
j=1
j=1km
K
K
K
8 -
-
1
1 0
Thus, we can get
Σ An S E Ellg 1| (2/((/))))))))))))))))
Using Lemma 1 with ax= = 12 and h(.)) = 1
v
we get
K
( VVCK -o Vok,
where we used the fact that o0 2 0. The proof is then completed.
D.2 Proof of Lemma 3
Similar to the proof of Lemmn we have
| - =0112- = Projx - - 20*1|2= = ||Projj (2 (=== mmm* - Projx
|| ((0 Σ m (10)) 5 Σ (1 0)
gh- / (
i=1
j=l
a) d
k Σ (1 - 8)²
k
(g (o*)
d
k-1
gk
- Σ (1 - 0)2
Σ gh (g)))
1 1- 0
1=1
j=l
i=1
k = (1 0) Σ
k
gh a و|ا 12 (b²
1) (1 Σ
pk-j j |وا 12//00
j=l
j=1
where a) uses the fact that (Ej=1 ,zbb)² v Σラ= ag Σイ D2 with aj -²²² and bj -0=²²² / and b)
is due to S 6t when j S k. Thus, we can get
K
K 11//00
| - x² x112 <
l1g
R=
k=
Using Lemma 1 with as = |12 and h(-) 1 we are then led to
lg |1 / In ant
wo - In wo
8
k=
The proof is then completed.
22

---

Published in Transactions on Machine Learning Research (10/2023)
D.3 Proof of Lemma 4
Direct compulations give us
Blgg~11 = "
V/ , 11
+ - - : 11=
2E/
VF
-- ; ; (*-1))
EI/F
)|( - E VF 5 5 V F k- -, _-
2
eh 1| - L 2 * - k 11?
where a) uses the inequality V F (xth; 5K gk
VF -b 1 c* c 2
(g 1)1 2E F ch 1k-1) V ( - 111 Thus we can get
E F 5 5h 1| < 21 | 112 2 g
D.4 Proof of Lemma 5
The convexity of Sig (xr) with respect to a and g² VF :0, gives us
B(x" - x",g" = B[F((" :0, (h--)) Fa="; (
1 1 Flat; et, gh-1) F(x";
(24)
The Lipchitz gradient continuily of F( 2k-1) with respect to indicates
E {[F(<*~1; ck ck 1) - F(x*: , sh-1
2 Blla* - -=1111 112 + BBx k-1 x² V VF(*" , (k-1))
BllØ* x² 11 + Exx (20k-1 - x², V F - -h, c*-1)
(25)
2
+ #(x
x V F hi 5
(0,gk*1 ck-1) - (F 5 ch -k-1))
3L
E11 - 111 + B(x k- kh VF(x 5k
2
where we used the Cauchy's inequality B(x xt, VF(=" ck -h- VF k ek c* s L|| 111. Because ę* gk-1 are independent of k
:(F((=: ch g
ge = f(x²) f(x*-11)
(26)
Turning back to
24 we get
E E(x" th ge) < E[F k- (0 1gh,, Fla": 5 + f(x²))
) -f(x*-1
(27)
Notice that k 1 is independent of (5* ck-1))
B(x - k VF k- 11, sk
E(x * t,, V ff(x*~11)
+ E(a k- * V [
k- ck - c (11))
1 |m 111
(28)
< B(xx t vS })}
+
=
2
v V
1 B |V c² ck-1) EV F(x BV <
+
2
V
23

---

Published in Transactions on Machine Learning Research (10/2023)
where we used EVF(x* 55 5x - |]/ V Now, we turn to the upper bound of _ 1VF Ligh st )) F(
E| with X Vek-1 - x²), and Y [VF
1k-1)
16 112
V VF 1 k ch- 1 EVF , 1|
E
2
VF(x k- Vek-1
1 B
EVF k- , 5 112
15
2
V
1
+
(IIFF(( (a--1 ,
(h-1)-
EVF(x* x -x, 111 (
Vot-i
Vot-z
2
(29)
1 E V
: E , <*- 1|1
+ E
2
Vek=
Vok-1
1A3) T.
x 11 E11
+ BB
V
Vink-2
V
S Ok:
where de = E | v
+ 2B2 E
Vek-2 Vol-r) + L² -0-0 -0--111
+ B²B Vot=z voz): and a) depends on
v8
Lemma 4 Thus, we have
B(xh-1 - x², V k- c :5 ()
1
|lm * 111
(30)
S 1<x0 xt (f(x*-11
+ ck.
2
Once with the Lipchitz property,
fv ) x 1-----0" S f(x*~11 f(x²) + L
2 1 - x 112
(31)
Combing 31 and
30
we then get
E(x k- x², VF VF( : ) S f(xz 1) - f(z²))
L 11 - ----1112
1 E
m 112
(32)
v + db.
2
2
Substituting 32
into
25
E (x k- : eh ck-1) F
[ < 22 x - 1112
l|m 112
(33)
+ f(xx-1)- f(x*) E
V v + Øz.
2
Substituting 333
into 27 we then get
1 | 112
112
E(x=" x= gh) & 2 - x² * 112 + f(x²) )- - f(xx )
2 Vok-1 + dx.
(34)
According to our algorithm and we denote A = B((x² x², )) then we have
IE ((æ - at m²)) = EE ((0" - =²,0m" k-1 + - -1-0)g
= (1 -) A + 0E(x* - x² m --1
(1 0)- A OE(x k-1 .m= k- x11 + 0x( x-1 m k-1
6)
< (1 - 0) A + 0B(x" - k- mm k -1) 1 + n0BB m +1 1 / (2 11)
where b) depends on that (a k --1 m 11) < |/ _
x - 111-11m = |Projx - -Proj
m k
I| < 1mm--112/(00) 11/2/1/ 1)).. Then, we get
B& < (1 - 0)E(x* x²' x² + + A
(35)
Substituting 34
into
35
we then proved the desired result.
24

---

Published in Transactions on Machine Learning Research (10/2023)
D.5 Proof of Lemma 6
This proof is identical to the proof of Lemma B and will not be reproduced.
D.6 Proof of Lemma 7
Notice that EV Fa* 1; ) then gel
B( ((-V((")((ot)11>> g
B -B- )/(()) VFF/ 1²
= -=IVV((=))\//(())) (( (((()) vf(x*11))
Vf(x*)
+ (XV -) VF : 5 1 (x-1))
(36)
v(((a)
+ E
, V ; +*
(w²)²
The Cauchy's inequality together with the smooth assumption gives
EXV -ffr)
S (1))) (((a))/(({})t)
(37)
/// Vf(=*)) -
((IV + xz - (0)))(
Similarly, the Lipschitz property of the stochastic gradient yields
EVV (x ) VF 1, 5 _ ck-l) - V ; , cx-1)) F 1. ck 2)-1)- - V (xx ck ck 2k-11]]
(((*))
< E
(1+)
(wb)
(38)
< B
V
+ - /1//(10t)
Substituting 338
and
37
into
36
we are then led
E
VE-V((>>)/)
g
(VV("(()))))))///( + (t)
(39)
1
- (
Now, we turn to bound (f):
(f) E<V
v V 1k ck-1))
+ E -
+ Vf(x 1/( Vi(a / [ - -VF(x-- gk-))
< (<(V)((')) V5(0 ))/(0 ) vf(x=11) vF(ot=1; (+1)))
+ 2B² 2/ 1/2 - 1/(0a)
El El x 112 22²2|11 B[1 2- 1/(ot)}b
ElIV 111 - vF
gh, 1///)12/00
2
25

---

Published in Transactions on Machine Learning Research (10/2023)
Furthermore, we have
E1|
- )|
E
VF
5* 5h ||3 /
2
+
E1
V
VF
(1/e0 - 1/
Lemma
L
L
x
x²x --
2E و 12 k- + 2B² - 1//0-2)
1
E
x
11
2g | 122/0/ + AB - 1/10-2).
8
Thus, 39
can also be bounded as
E(- ((-V
- (12 (1²/((²)*))
+ - 2g 12/0"
(40)
12/ 112
We also use a shorthand notation A = R (o= gh1) and then
E - V ((x'' m /
= E (- V
k-1 (1-
= (1 - 0) AE (E / m m
a) < (1 0) A /E (
m m OnlElIm 1 112////111
(41)
where a) uses the Cauchy-Schward inequality and the Lipschitz property of and ot S ot. Substituting into we then proved the result.
E
Ablation study of the parameter 0
In this section, we investigate the influence of the parameter 0 on the convergence rate of AOGD. The experimental setup adheres to the detailed in Section focusing on the hinge loss applied to the ijenni dataset.
We fix the parameters and R at values 1.0 and 10.0, respectively, while varying 0 over the set {0.1, 0.3, 0.5, 0.7,0.7.... 0.9). The rationale behind these chosen values for and R stems from optimization results observed at 0 = 0.9, aligning with the configurations presented Table 2 and Fig. 2
As depicted in Figure the convergence rate of AOGD across different values is displayed. Notably, the convergence rate appears robust to the specific selection of with slightly better performance observed intermediate 0 value, specifically 0 = 0.7.
26

---

Published in Transactions on Machine Learning Research (10/2023)
ij
0.9
AUC score
0.8
0 0.1
0.7
0 = 0.3
0 = 0.5
0.6
0 = 0.7
0 = 0.9
0.5
0
20 Iterations (log scale)
10
30
Figure 4: The effect of 0 on the convergence rate of AOGD with hinge loss on ijcnn1 dataset. The result suggests AOGD achieves robust performance across different 0 values.
27


Reviews:
[{"review_id": "7gIqgOAQZM", "reviewer": "Reviewer_DVMN", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths\n\n-\tThe paper provides comprehensive theoretical results under both convex and nonconvex cases.\n\n-\tThe proposed algorithm is easy to use.\n\nWeaknesses\n\n-\tThe theoretical benefit of using momentum theta is unclear. Theorem 2 assumes no momentum (i.e. theta=0) and the bounds in Theorem 1&3 seem to be optimal when theta = 0. Can the authors explain how using momentum improves the convergence bounds?\n\n-\tHow do the bounds in the paper compare with previous online GD bounds? \n\n-\tThe projection operator Proj(·) is not defined in the paper.\n\n-\tThe authors claim that one of the differences compared with Ding et al. (2015) is that they consider general pairwise learning rather than only AUC maximization, yet the experiments only AUC maximization task. It will be better to show empirical results on other pairwise learning tasks to support the claim that the results in the paper apply to general pairwise learning.\n\n-\tSince the experiment only includes one AUC maximization task, it is unclear what case (strongly convex/convex/nonconvex) it falls in. I would suggest the authors conduct experiments for each case and empirically verify their three theorems. The current empirical results do not give many insights. It basically shows that AOGD sometime gives a bit of improvement compared to OGD.\n\n-\tThe baseline in the experiment should include Ding et al. (2015), which is also an adaptive GD algorithm.  \n\n-\tThe authors mention when alpha is less than 0.5, AOGD converges faster than OGD. It is unclear if the experiment belongs to this case and whether we should expect AOGD to converge faster. \n", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "No", "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": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This paper proposes a new adaptive online gradient descent algorithm for pairwise learning. Specifically, the algorithm leverages momentum and adaptive stepsizes in a similar way as ADAM. The authors provide convergence bounds under strongly convex, convex, and nonconvex cases and test the algorithm on an  AUC maximization task.", "claims_and_evidence_yn": "No", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "-\tClearly compare the convergence bounds with previous bounds. Explain how the added components (momentum and adaptive stepsizes) improve the bounds.\n\n-\tAdd empirical results to verify theorems.\n\n-\tAdd empirical results on other pairwise learning tasks beyond AUC maximization.\n\n-\tAdd the related baseline Ding et al. (2015).\n", "broader_impact_concerns": "NA", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "L32IaWZXps", "reviewer": "Reviewer_aBKL", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "The paper is mostly clear and well written. The authors overcome the challenges in the analysis and provide convergence rate in strongly convex, convex and nonconvex cases. However, I have following concerns:\n\n1. My first concern is that the convergence analysis does not reflect the advantage of using momentum. In theorem 1 and theorem 3, choosing $\\theta=0$ leads to the best convergence rate (c1, c2, c3, c4 all achieve minimum when $\\theta=0$). Also, theorem 2 only considers the momentum-free case.\n\n2. The description of assumption 1 is not accurate. It should be assumed that the gradient of F is Lipschitz continuous, not that the function F is Lipschitz continuous.\n\n3. In section 2.3, the paper claims that AOGD achieves the optimal convergence rate of SGD in the strongly convex case. However, the optimal convergence rate of SGD is O(1/K) (Rakhlin et al., 2012) rather than O(log(K)/K). Thus the convergence rate of AOGD is suboptimal.\n\n4. In the empirical comparison, the performance of AOGD and OGD are very close. Also, I think the method proposed by Ding te al.(2015) should be considered as a baseline for the experiments.\n", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "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": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This paper proposes an adaptive online gradient descent method for pairwise learning. The authors also provide convergence analysis for the proposed method in strongly convex, convex and nonconvex cases. The proposed method outperforms the non-adaptive counterpart on the online AUC maximization experiments.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "I suggest authors study how parameter $\\theta$ affects the convergence property. For example, the authors may empirically compare the performance of different choices of $\\theta$. In addition, the experiments should compare the proposed methods with Ding te al.(2015) since their method is also suitable for AUC maximization.", "broader_impact_concerns": "no broad impact concerns", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "ILPHExUYKz", "reviewer": "Reviewer_s7Zb", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n\nThe authors prove convergence rates and explain regimes when the new method AOGD improves the previous method OGD. I didn't check the proofs, but the theoretical bounds sound to me.\n\nWeaknesses:\n\nMy main concern (or question) is why we can't modify Algorithms 1 and 2 and add the following step between the step 1 and 2:\n\nstep 1.5: drop $g^k$ from step 1. Receive $\\widehat{\\xi}^k$ and calculate $g^k = \\nabla F(x^k; \\widehat{\\xi}^k, \\xi^{k}).$\n\nNow $g^k$ is unbiased. The idea is to drop 1st, 3rd, 5th, and so on gradients. This way, we can reduce this problem to the classical stochastic gradient problem. Why does this strategy is overlooked in the pairwise learning community? \nYes, the computation complexity will increase by two. However, the theory will be simpler and nicer. Due to the fact that $g^k$ are biased in Algorithms 1 and 2, the theory requires much stronger assumptions than in the classical unbiased case.\n", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "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": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "The paper considers the pairwise learning problem and develops a new Adam-like method based on Online Gradient Descent (Yang et al. (2021b)). The authors support the new method with the theoretical convergence rates in the convex and non-convex settings.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "-", "broader_impact_concerns": "-", "additional_comments": "", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: Some concerns were raised by the reviewers but these were appropriately addressed by the revision and the author discussion (in particular, improving the experimental section). Two reviewers were leaning accept while one reviewer was leaning reject due to their concerns about the momentum analysis (see next paragraph) and the experiment section (see my comments about it in the "claims and evidence section above").

One remaining concern from the reviewers after the revision is that the theoretical analysis does not highlight an improvement thanks to momentum (the bound is best with zero momentum in Theorem 1 and 3, and Theorem 2 did not consider the momentum). Given that this type of analysis is quite challenging and this phenomenon is typical in the convergence analysis of momentum methods literature, I don't think that this is too problematic.

There was also a detailed discussion with reviewer s7Zb about the alternative sampling scheme which considers two independent samples at every iteration rather than re-using an old sample as in the current paper and in the OGD algorithm. The advantage of this alternative sampling scheme is that the theoretical analysis is simpler (as the gradient is unbiased). But
1) As mentioned by the authors in their rebuttal and in the revision, the "re-using" sampling approach allows to have T iterations with T samples rather than T/2 iterations with the "2 independent samples" approach, which could suggest more progress. This is not a theoretical necessity though, as perhaps T/2 "cleaner samples" could converge faster than T "biased samples". But empirically, the 2 independent samples approach was observed to perform worse in [Zhao et al. 2011], as mentioned in the author revision
2) Moreover, this "re-using" sample approach was already deemed better in the literature (such as in [1] on which the submission heavily builds on).
This reviewer recommended acceptance at the end.

I thus recommend acceptance subject to a minor revision. I detailed the required changes below.

### Required changes:

1) Proposition 1 provides an argument why their adaptive step-size could improve over OGD theoretically. This hinges on the assumption that $E[\sqrt{v_k}] = O(K^\alpha)$ with $\alpha < \frac{1}{2}$. While the authors provide a theoretical justification that this holds for 
$\alpha = \frac{1}{2}$, they do not provide any explanation (or empirical evidence) which could indicate that it holds for $\alpha < \frac{1}{2}$. To clarify the claim of Proposition 1, the authors should either provide in their revision more evidence that this can hold; or at least clarify in their text that this is a purely hypothetical analysis, which, while being mentioned being also assumed in the previous literature in Remark 1, still would require additional inquiry / evidence to conclude something.

2) The discussion about the different sampling schemes made me realize a crucial point that is not explicitly mentioned in the paper, but I think it should be discussed in the revision. The formulation for pairwise learning as defined in Eq. (1) seems to implicitly assume that $F(x; \xi, \xi')$ has some kind of "symmetry" in $\xi$ and $\xi'$ in the sense that they play similar role (as you use the same distribution $P$ on $\xi$ and $\xi'$). Yet, the standard AUC formulation (such as appearing e.g. in [Zhao et al. 2011] does not have this property (it treats the positive and the negative classes differently, and these also can have different distributions). [1] provides a formulation where $\xi$ and $\xi'$ can have the same distribution (see the 'AUC maximization paragraph in their Section 2.1 e.g.). But this is using indicator functions and then the F they define will be always zero unless $\xi$ has a positive label and $\xi'$ has a negative label. Supposing I was sampling the points independently, this means that only 1/4 of my iterations would yield a non-zero signal. And in the online learning regime where someone could give me a fixed stream of data-points; suppose that they had sorted the labels beforehand, and had put all the negative labels first and then the positive labels. Then by always considering two consecutive data-points as my (\xi, \xi') pairs, only when I have a (+ve label, -ve label) pair would I have a non-zero signal. In the worst-case setting I just mentioned, this would actually never happen as the only transition is from -ve to +ve (the wrong direction), and thus nothing would be learned with ODG or the proposed algorithm by the author!

In their revision, the authors should discuss this last aspect in more details and how this affects (or not) their algorithm. For better motivation and clarity, they should also explicitly provide the F formulation for the AUC application that they consider (this could be in the introduction e.g. when introducing the pairwise learning framework). Given that they assume iid samples for $\xi_k$, my worst-case example is unlikely; but it would be useful to clarify all this. In particular, it is an interesting feature of their approach for AUC (assuming the same formulation as in [1]) that they can never have two non-zero updates in a row (but can have many zero updates in a row). This point is somewhat puzzling, and it also brings some nuance to their claim that the "re-using" sampling approach yield T iterations out of T samples vs. the "2 samples approach" which yield T/2 iterations. As at least one out of two iterations is zero, the re-using approach here actually has less than T/2 iterations! In contrast, if we allow to use two independent samples per iteration, one could use one sample from the positive class and one independent sample from the negative class to always have a non-zero update at each iteration for the other approach. The gain of one approach vs. the other becomes less clear from this perspective, and all this should be clarified in the revision.

Please explain in OpenReview he high level changes you have made in the revision to help the verification.
Decision: Accept (poster)