Summary and Contributions: The paper studies a variant of online ranking problem. In the offline settings preferred items belong to different groups, and one need to generate a sequence of items so that qualitatively speaking for each group R_t of items at least k_t elements appear high in the list. More formally they formulate the problem as an online version of the known "Generalized Min-Sum Set Cover" (GMSSC) task: In this problem, given a set U {1,...,n} of n items, in each step 1. The learner selects a permutation \pi_t items in U 2. The adversary selects a request R_t \subset U with demand k_t . The goal is to minimize the multiplicative regret, that is the ratio of the total cost to the cost of selecting a fixed optimal permutation \pi* in all steps.

The reviewers have some concerns that the rebuttal didn't fully address but they all like the paper and agree that it should be accepted at NeurIPS.

Summary: This paper presents an approach for solving machine learning tasks that require the prediction to be presented in the form of a set. The authors propose to use the set encoder (which is composed of permutation-invariant operations) at the prediction phase by finding an output set with an optimization procedure. As the model output is a vector of continuous features for each set element, it can be done by means of nested gradient descent optimization. In order to solve the task of set prediction for external feature vector, the work suggests a combined loss function that encourages the representation of ground truth to be close to obtained features. Results are shown on MNIST and CLEVR datasets and outperform those of an MLP baseline.

Relation to Prior Work: It is clear how this work differs from the prior literature, since it is the first one to study implicit regularization in the setting of stochastic convex optimization. However, the related literature section could be improved. First, implicit regularization dates back to much earlier works than the ones concerning neural networks (the first theoretical work on implicit regularization is due to Buhlmann and Yu 2003 "Boosting with the l2 loss"). Given that the work the authors present has little or nothing to do with neural networks, the related work section should be expanded to include other authors who developed the theory of implicit regularization for gradient descent over the past 20 years. Also, it is worth noting that one of the central reasons motivating the sutudy of early stopping and implicit regularization is the computational efficiency of the method in comparison to the explicit regularization schemes.

I appreciate the author's taking time to respond to comments from my review. In particular I look forward to see similar techniques applied to multi-agent hidden network zero-sum games as per their response. The action space is given by finite vector spaces, and these map to a lower dimensional space via a smooth function. Payoffs are then zero-sum in this space. Although it is already known that gradient descent is difficult for games (even zero-sum games as those used), the authors show that even in this general dynamic the situation is just as dire.

Following the author response, consensus on acceptance was easily reached, on the grounds that the paper makes important contributions to gradient dynamics in certain zero-sum games which capture a restricted class of GANs. We encourage the authors to clarify the introduction/motivation to accurately reflect the results.

The title used for the paper is misleading since the rate O(epsilon {-2}) can only be achieved for a special class of non-convex concave min-max problems. More specifically, this rate is attained when using the algorithm to minimize the pointwise maximum of finite collection of non-convex functions. For general non-convex concave the rate is O(epsilon {-4}). This is clarified in the body of the paper, but the title is clearly misleading. It is not clear in the paper when this assumption (or even its relaxed replacement in the appendix) holds in practice.

Originally, the paper got three positive scores: 7,7,6, all with very high confidences. Basically, there was no critical issues raised by the reviewers, except suggesting the enhancement on experiments and clarifying some points. During discussion, all the reviewers agreed that the paper should be accepted and Reviewer #3 raised his/her score to 7. So all the reviewers reached a consensus. Thus the AC decided to accept the paper. However, the AC also have the following comments after a quick reading.

Additional Feedback: - The authors note (with references) that the pure behavioral cloning approach performs poorly as it doesn't use information about the dynamics and state distributions of the problem. It would be useful if the authors could present a short concrete example of exactly what type of information is lost when ignoring the MDP structure. At a first read it feels like it implies the off-line setting means we have all the information we *need* from the start, which I think is the opposite of what the authors are trying to say. - Line 112 - This sentence immediately brings to mind a decision between parametric vs. non-parametric methods. I don't think that's what the authors are trying to say so maybe the terminology of "parameterizing a policy" should be changed throughout the paper. If it is what the authors are trying to say, then it is not made clear why a parametric approach is the correct choice.

This paper proposes two novel approaches for the uncoupled regression problem, in which the correspondance between the input data and the targets is not known. Instead these methods use unlabeled data and pairwise comparisons of the targets. The first approach is the risk approximation approach (RA) and it minimizes an approximation of the risk defined based on the expected Bregman divergence. The second approach, called the target transformation (TT) approach, consists in mapping the target variable to a uniformly distributed random variable using the cumulative distribution function. Estimation error bounds are derived for each method.