Originality: The authors' solve a problem left open in a previous paper and made strictly improve on previous work for approximation algorithms. They do so by giving new insights into structural properties of extreme points of semi-definite programs and more general convex programs. As far as I understand, the algorithms presented in the paper are not substantially new, but the analysis of these algorithms is novel. Quality: The paper seems complete and the proofs appear correct. The paper tackles interesting problems and reaches satisfying conclusions. They essentially close the book on the k 2 case, make significant improvements for k 2 and leave open some questions for structured data.

Recent work of Samadi et al. introduced the fair PCA problem where the goal is to find a projection that minimizes the error and furthermore the error is balanced across two groups in the population. The takeaway message from their paper was that adding one extra dimension is enough. Firstly, this paper resolves the main open question from the work of Samadi et al. by giving an algorithm that does not need to increase the dimension by one. Second, they push the framework fo fair PCA in some interesting new directions that allow for alternative notions of fairness and multiple groups. They improve the fairness penalty to be \sqrt{k} from k-1.

The other reviewers also convinced me that despite not having the right assumptions for the mention applications, the work might still be useful in other applications. I request the authors to remove the applications mentioned in the introduction or to explicitly write that their assumptions are not satisfied for them. Based on this points, I increase my score from 4 to 6. Let me also clarify on why I believe having the right assumption is important and what I dislike about the theory. SARAH is an interesting method as it does not require bounded gradients and, at the same time, there are settings where the its known complexity is better than that of SGD.

This paper has been deeply discussed between the reviewers and myself. After a lengthy discussion and thanks to the authors' rebuttal, the reviewers were convinced that the proposed algorithm and its analysis and novel, interesting, and worth to be published in NeurIPS. However, the reviewers also noted the mismatch between the motivating examples in the introduction and the assumptions in the analysis. Note that it is not enough to state that the assumptions hold in the "domain of optimization" because there is no guarantee that such domain is bounded. So, please carefully take into account the reviewers' comments in preparing the camera-ready version.

Additional Feedback: [After rebuttal] I appreciate the additional explanations in the rebuttal. I think the example (a more complete version) will go a long way in improving the paper, but as is presented I think not enough details is given for a proper evaluation, thus I look forward to reading a revised version of this work. Note that my tautology comment is not saying that the proof is trivial, but saying the way it is written masks the potential insights the proof may give, in particular, there should be a result that shows that such a limit in Cons 1 exists under some general conditions characterising the data and the model architecture. I believe the example provided in the rebuttal may potentially be useful for formalising this. On first reading, these conditions appear not well-motivated.

Before the author response, all the reviewers seem agree that the results were quite interesting (and I agree), but had a concern about the connection to ML. The author response included examples which mostly addressed this concern, so two reviewers recommended acceptance, while another (reviewer 1) recommended rejection, but was borderline. However, I feel the remaining concerns by reviewer 1 are rather minor.

Weaknesses: While the paper is written very clearly, there are several questions I'd like to raise. Firstly, in discussing the applicability of the results the paper mentions'some basic vision or sound recognition tasks' (line 33) - I'd like to ask about some examples of such tasks. Looking at the statement of the Theorem 1, seems that it should be applicable in finite-dimensional spaces with invertible covariance matrices. If it is so, then I do not understand the results. In particular, for X distributed with a finite support and has identity covariance matrix, the conditions (a) and (b) hold for arbitrarily large positive \alpha, however the theorem statement implies that the estimates will go to zero at an arbitrarily large polynomial rate, which is not true.

The submission considers noiseless (/low noise) linear regression with non-linear transformation of the input data, and show that under this setting, SGD achieves faster convergence rates. This is a very nice contribution with applicability to important problems as mentioned by the authors in their feedback. We urge the authors to incorporate the points they made in response to the reviews.

The paper concerns robust linear regression in the online setting, where the data follows a Gaussian linear model with corruptions. It is shown that the stochastic gradient descent on the absolute loss converges to the true parameter at a rate of order O(1/n). The paper received a universally positive evaluation from the reviewers, who acknowledged the novelty of the results, the theoretical justification of the proposed approach and the scalability of the algorithm. The main issue raised in the reviews is about quite restrictive assumptions on the data distribution (Gaussian linear model, and the centered data assumption).

Softmax policy gradient is a popular algorithm for policy optimization in single-agent reinforcement learning, particularly since projection is not needed for each gradient update. However, in multi-agent systems, the lack of central coordination introduces significant additional difficulties in the convergence analysis. Even for a stochastic game with identical interest, there can be multiple Nash Equilibria (NEs), which disables proof techniques that rely on the existence of a unique global optimum. Moreover, the softmax parameterization introduces non-NE policies with zero gradient, making it difficult for gradient-based algorithms in seeking NEs. In this paper, we study the finite time convergence of decentralized softmax gradient play in a special form of game, Markov Potential Games (MPGs), which includes the identical interest game as a special case. We investigate both gradient play and natural gradient play, with and without \log -barrier regularization.