Venue: NeurIPS 2021 Conference

Reviews:

final_score: rating: 7: Good paper, accept
review_content: summary: The paper analyzes the generalization ability of SGD for pairwise learning problems. The authors prove better generalization error bounds incorporating some variance term or the optimal error. They also provide a new SGD with O(n) computation per trial whose generalization bound is state-of-the-art. Furthermore, they show results for strongly convex losses and non-convex losses. 

main_review: The writing of the paper is excellent in general. In particular, every theorem comes with a remark, which is helpful to understand the technical improvement to related work.
The paper is technically solid. 

My concern is about concrete examples of loss functions and motivating problems. For example, AUC maximization is closely related to the paper. However, generalization error of AUC would involve conditional distributions on positive and negative instances and the generalization error defined in this paper seems not appropriate to the AUC problem. Then I wonder what concrete problems are subjects of the formulation of the paper.  

Corollary 5 (b) assumes that F(w^*) is O(1/n), but this assumption seems not natural since F(w^*) is independent of the sample size and does not decrease when sample size n increases. So I feel that statement (b) is not meaningful. Furthermore, in Remark 3, the authors insist on the advantage of Theorem 4 to previous work [37][53] based on the corollary. I feel the statement is not fair as it is based on a weird assumption and should be removed.

The technical results of Theorem 8 (improving n^2 to n in computation time per trial) and Corollary 13 (extension of the previous approach to pairwise non-convex learning) are non-trivial and impressive. In particular, Coro. 13 needs to overcome the difficulty caused by dependent pairs in the analysis. 

Overall, my impression of the paper is rather positive and the paper is better evaluated if my concerns raised above are resolved.

Minor Comments:
Line 145: Does the expectation is also taken w.r.t. the randomized algorithm A?


After reading other reviews and author responses, I raised my score a bit since the raised issues are resolved.

limitations_and_societal_impact: N/A
review_title: null

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: The paper seeks to develop new generalization and excess risk bounds for pairwise learning using SGD. The goal is to achieve error rates with near-optimal dependence in the number of gradient evaluations. To this end, stability properties of SGD are analysed and used to obtain the generalization/excess risk bounds. 
main_review: When it comes to deriving generalization and excess-risk bounds, the authors argue that pairwise learning is more difficult than point-wise learning due to the non-i.i.d. nature of the training examples of the former. This then motivates the approach taken by the authors, which involves studying the stability properties of SGD and applying some decoupling tricks (to overcome issues that come with the non-i.i.d. nature of the problem).

It seems to me that the authors have missed some highly relevant work in point-wise learning that should lead to optimal excess-risk rates (both in expectation and high probability) when applied to pair-wise learning. In fact, modern online-to-batch-conversion techniques---see e.g. Theorem 1 in http://proceedings.mlr.press/v97/cutkosky19a.html---reduce the problem of deriving excess risk bounds to that of getting regret bounds in an online learning setting. The data need not be i.i.d., and so this is applicable to pair-wise learning. Furthermore, SGD is essentially just OGD in the online learning setting, for which regret bounds are well studied for non-smooth/smooth and convex/strongly convex cases. Therefore, applying Theorem 1 in http://proceedings.mlr.press/v97/cutkosky19a.htm to the setting of pair-wise learning, and plugging in the regret bound of OGD, should recover, or even improve the excess-risk result of the current paper. 

The current paper might still have some novel contributions when it comes to generalization bound (not excess-risk bounds) since I do not really know how these can be obtained using the online learning framework.

The paper is a little dense and still contains many inconsistencies and typos. I now mention some of them:
- It seems that the authors talk about generalization bounds when they mean excess-risk bound (see e.g. Theorem 7). Please fix this.
- The use of 'linear time' is not correct. A linear time rate in n is something line exp(-O(n)).
- Lines 102-104, you mention a randomized algorithm A, but you are not taking the expectation when you write F(A(S))
- In thm1, it should be F(A(S)) and not F(S)
- In thm3, mention that A is given a training dataset of size n
- The statement of Thm 4 is a little strange. How do you define a w that is independent of the algorithm A yet dependent on S? Furthermore, to call the result of Thm 4 a generalization bound, you technically need w = A(S). But the current theorem statement does not allow this.
- Another instance of confusing the concepts of generalization and excess-risk is in Remark 3: you start talking about generalization, then switch to talking about F(w_\star)
- In lines 246-247: the claim that a log n^2/\sqrt{n} bound has not been derived before for point-wise learning needs more explanation. Can you point to the best-known rate for this case?
- In Thm 9, what is w_s^*? Define it explicitly.
- Missing bracket in F_S(A(S) in thm 10.

limitations_and_societal_impact: No negative social impact
review_title: null

final_score: rating: 5: Marginally below the acceptance threshold
review_content: summary: The paper proposes generalization for pairwise learning, based on assumptions of algorithmic stability.
It shows different bounds that depend on assumptions on the smoothness of the pairwise function.
main_review: I did not delve into the math in detail.
I think the most interesting part of the publication is how they can propose stronger assumptions to derive bounds in $O(n^{-1})$ for the SGD algorithm, without any noise assumption on the data distribution (as do generalization results in $O(n^{-1})$ for U-statistics do, see [13]), but only using assumptions on the pairwise function $f$. You say you incorporate the variance in the analysis to derive faster bounds, which is exactly the purpose of the Mammen-Tsybakov (sometimes known as Bernstein) conditions for instance based (not pairwise) learning use in generalization bounds. [13] shows that we can bound the variance at a lower cost when dealing with U-statistics, as the analysis relies on the second Hoeffding decomposition (writing a U-statistic as an standard empirical process and a degenerate U-statistic) and the Hajek projection used to obtain the standard empirical process is a variance-reducing transformation of the original U-statistic. Your results propose fast bounds that are derived from the shape of the function $f$ rather than by an assumption the data, which is novel in my opinion (I looked at [37] and they seem to only propose $O(n^{-1/2})$ and in my opinion is a good result to extend with your SGD analysis.
I think the paper seeks to cover too much ground for the format of the conference, which obscures the message, and should recenter the paper on one meaningful message.

Also, ref [a1] below is proposing guarantees for SGD for the minimization of U-statistics (pairwise functions), which is exactly what you are doing. Their analysis assumes only convexity (l. 41-42) and a VC-assumption. I believe that your contributions should be compared to theirs.

[a1] SGD Algorithms based on Incomplete U -statistics: Large-Scale Minimization of Empirical Risk, Papa et al, NeurIPS 2015

----- AFTER READING THE REVIEWS AND REBUTTAL

I thank the authors for a serious response to the concerns of the reviewers.
I am very familiar with uniform convergence generalization bounds but not that familiar with algorithmic stability.
While my reject rating was motivated by the fact that the paper overlaps with existing work, the authors have successfully underlined the differences between their work and [a1]. For these reasons, I raised my rating to weak reject, as I would accept the paper if its results were put in perspective with already existing pairwise generalization bounds. I did not raise it further as integrating them is a significant undertaking.
limitations_and_societal_impact: Nothing to declare
review_title: null

Meta-review: The paper makes a good contribution to pairwise learning problems by providing better generalization error bounds for stochastic gradient descent (SGD) applied to these problems, and providing analysis for both convex and non-convex problems.
Decision: Accept (Poster)