Venue: NeurIPS 2021 Conference

Reviews:

final_score: rating: 7: Good paper, accept
review_content: summary: The paper is about a variant of online learning for pairwise learning. The authors select the last sample as the sample to pair the current sample with. This is different from previous algorithms that select random subsets or a random single sample. The algorithm per se is nothing really new as it can be viewed as a special case of previous algorithms. The focus of the paper is to analyze generalization capabilities of this algorithm. The authors show that it generalizes well despite being so limited which is surprising. The key obstacle is in the fact that the gradient estimators are no longer unbiased. 

The main contributions of the work are in the analyses of the generalization property in the online and offline setting, and there are similar results in a differential privacy setting. 
main_review: I appreciate and value the contributions due to the fact that 1) the result is surprising due to the algorithms being very restrictive, and 2) the gradient is a biased estimator which makes any analysis tricky. 

The paper is well written.

The computational experiments are somewhat superfluous. The paper is theoretical and the experiments seem to be artificial. The algorithm proposed could (should) be compared but such a comparison needs to be much more comprehensive. The current results are very limited. 

Some specific remarks:
1) ERM is never defined
2) only when s becomes to infinity as n ???
3) "It was mentioned in [20]" should be "It is mentioned in [20]"
4) "when a FIFO buffering set with a very small size" ???
5) 128: to the size
6) 151: does not work; Why not? I assume it select the current sample and a random previous sample. 
7) 158: analyses
8) F is never defined. I get it that it is the population loss but this is never defined. 
10) A1: I assume G is a constant and not a function of z, z^\prime
11) 187: to convexity
12) A4: unclear; Does it have to hold for any subset S? What is w_S? I assume it is w_S^*
limitations_and_societal_impact: yes
review_title: null

final_score: rating: 5: Marginally below the acceptance threshold
review_content: summary: Pairwise learning seeks to minimize objective functions that are sums (or expectations) over pairs of observations from a dataset. Online learning strategies are difficult to mix with this structure as the number of terms grows quadratically in the number of observations. This paper proposes to take as a stochastic gradient only the gradient of the term corresponding to the last pair of observations; it presents rigorous analysis of the performance of this strategy. This paper studies the generalization error of both a multi-pass SGD (Algorithm 1) and a single-pass SGD (Algorithm 2). 
main_review: This paper presents convergence results in a wide number of settings (smooth, non-smooth, under a Polyak-Lojasiewicz condition). It is thus dense but well presented. 

I would like to understand better the benefit of the approach of the authors. In the online framework, it is clear that using the loss over the last pair (and not over the $n-1$ new losses that involve the $n$-th observation), the computational cost per iteration is much smaller. However, this seems to come at the loss of a lot of statistical information. What does your theoretical analysis conclude on this tradeoff? Are your algorithms better than the classical "pointwise learning" approach?

A related question is the following. Say that I set myself in the non-smooth setting, and I have $n$ observation. I can apply Algorithm 1, and by Theorem 1, after $n^2$ iterations, I get a performance of $O(1/\sqrt{n})$. But I can also apply Algorithm 2. In that case, I use Remark 6 and the claim of l.257-261, after $n$ iterations, I get a performance of $O(1/\sqrt{n})$. Should I be surprised that Algorithm 2 is so much faster?

Your paper raises several time that the difficulty in your proof is the correlation between $w_{t-1}$ and the randomness $\xi_t = (z_{i_t}, z_{i_{t-1}})$ that is used to build the stochastic gradient. Alternatively, the problem is that $\xi_t = (z_{i_t}, z_{i_{t-1}})$, $\xi_{t-1} = (z_{i_t={t-1}}, z_{i_{t-2}})$, $\dots$ are not independent. But they form a Markov chain, that is quickly mixing ($\xi_t$ and $\xi_{t-2}$ are independent). I know there are papers that study SGD when the source of randomness is a Markov chain, see, e.g., https://arxiv.org/pdf/1809.04216.pdf . Have you considered this approach? Do you think you could plug-in your problem into their results (or similar results by other authors) in order to obtain the convergence of the optimization error? 

Minor remarks:
- L. 272: why does the convergence rate increase with $s$? Shouldn't larger batch sizes help? 
-  L. 67: what is $d$? 
- L.190-192: do you have examples where the PL condition holds for a pairwise learning problem? 

=============
After the rebuttal: 

After the conversation with the authors, my main concern would be whether this work is novel enough to be published at the NeurIPS conference. The algorithms, results and proofs are closed variants of the "pointwise" framework; the main new difficulty is the correlation between stochastic gradients, but we know from Markov chain SGD (see above) that it can be handled (some of the results of the paper can even be derived rigorously from https://arxiv.org/pdf/1809.04216.pdf). Note that I'm not an expert in pairwise learning, but rather of SGD, so I may have a biased perspective. 
limitations_and_societal_impact: I am not sure whether the proposed algorithms are significantly faster than the more naive approaches, see my question above. It could be beneficial to make this more clear in the paper.
review_title: null

final_score: rating: 9: Top 15% of accepted NeurIPS papers, strong accept
review_content: summary: 
The paper focuses on pairwise learning, where the loss function depends on pairs of data samples. In particular, the paper provides novel algorithms for both offline and online settings. In each iteration of these algorithms, the number of used samples is 1. This is precisely the main importance of the work, as the previous works used either all the previously used samples or a buffer with size S; the former results in high computation complexity (O(T) gradients at the T-th iteration), while the latter obtains a bound that is only useful when the buffer size (S) is large. On the contrary, the work uses a buffer size of 1, while obtaining the same generalization bound with the algorithm using all samples. Moreover, the authors provide thorough theoretical analysis of their algorithms including, generalization bounds, optimization bounds, stability results for both convex and non-convex as well as smooth and non-smooth functions. They finally provide some preliminary numerical results on AUC maximization. 

main_review: The paper is very well-written, where all the assumptions, results, and distinction with the previous work are clearly stated. Moreover, they deliver important results on pairwise learning that is interesting in the machine learning community. The theoretical studies are thorough and include different settings, e.g., online and offline, convex and non-convex, smooth and non-smooth as well as different analysis, e.g., generalization bounds, stability, and optimization bounds. They further provide a differentially private SGD algorithm, which is interesting on its own. In overall, I find the contributions of the paper solid and quite strong. 
limitations_and_societal_impact: The followings are only minor issues and typos.

(a) In Line 176, it seems to me that the "excess generalization error" was supposed to be "optimization error".

(b) I am personally familiar with pairwise learning and its importance, however, it might be good to discuss its applications in more details, regardless of the algorithms used for solving them.  

(c) Typos:
(c1) Line 45, "becomes to" --> "goes to"
(c2) Line 70, "can also apply to" --> "can also be applied to"
(c3) Line 133, "It is worth of pointing out" --> "It is worth pointing out"
(c4) Line 153, I believe the authors meant to say that the gradient is NOT an unbiased estimator. 
(c5) Line 213, "rends" --> "renders"
review_title: null

Meta-review: The main topic of this submission is an online and stochastic gradient method for pairwise learning (fix title of submission). There was a very constructive discussion between the reviewers and the authors, leading to clarification about the various points of the analysis.

Based on my own evaluation, I recommend to accept.
Decision: Accept (Poster)