The reviewers were positive about this paper based upon their initial read. The authors response addressed their concerns, so they were even more comfortable with a positive outcome after the author response. I encourage the authors to incorporate their responses to the reviewer concerns into any final version of the paper.

Weaknesses: Though there are some merits of the paper, here are a bunch of major problems of the submission: 1. PL condition is a very strong assumption. Although it does not require convexity-concavity, it is a global condition, which roughly requires similar properties of strong convexity-concavity. I agree there are some applications of min-max problems under PL condition, as mentioned in the paper, but the applications are extremely limited, and I am not sure they are important applications to ML community. In general, nonconvex-nonconcave min-max problems won't satisfy PL condition. To this extend, the title of the paper is a bit misleading, and it should mention PL condition explicitly.

This paper studies AGDA/Stoc-AGDA for minimax problems that may not be nonconvex-nonconcave but obey the two-sides Polyak-Łojasiewicz (PL), Moreover, this paper proposes a variance reduction version of AGDA and achieves better complexity results. The reviewers thought the problem setting was interesting and relevant to Neurips but also had a variety of concerns. These concerns were partially mitigated based on the response but other concerns remained. The reviewers had a spirited and comprehensive technical discussion about the merits of this paper. Two reviewers raised their score R4 - 4-5 and R2 4- 7 while one reviewer slightly lowered their score 8- 7. Based on the reviews, response, discussion and my own reading the main pros and cons of this paper are as follows.

This paper aims at solving the saddle point problem \min_{x} \max_{y} g(x, y) where g(x, \cdot) is concave for each x and g(\cdot, y) is either strongly convex or nonconvex for every y . The authors introduce a new algorithm called DIAG which combines Mirror-prox and Nesterov's AGD to solve the minimax problem. For the case that g is strongly-convex with respect to x, the authors show that DIAG has a convergence rate of \mathcal{O}(1/k 2) when the suboptimality for a pair of point (\hat{x},\hat{y}) is defined as the primal-dual optimality gap \max_{y} g(\hat{x},y) - \min_{x} g(x, \hat{y}) . For the case that g is nonconvex with respect to x, the authors show that DIAG finds an \epsilon -first-order stationary point (FOSP) after at most \mathcal{O}(1/\epsilon 3) gradient evaluations. The convergence criteria considered in this paper for solving a strongly convex-concave problem is interesting.

All reviewers agreed that this paper makes an interesting contribution to NeurIPS. Please make sure to take the reviewers' comments in consideration for the camera-ready version, in particular improving the clarity of the presentation and making the overall statements more precise.

Summary and Contributions: Contribution: The paper gives a new deterministic algorithm for maximizing a non-monotone submodular function subject to a matroid constraint. The algorithm achieves a 1/4 approximation and it has a running time of O(n r), where n is the size of the ground set and r is the rank of the matroid. Using known techniques, one can speed up the algorithm to nearly-linear at a small loss in the approximation. Comparison to previous work: Previously, there were two main approaches for obtaining deterministic algorithms for the problem. The first approach, due to Lee et al., uses local search and it obtains a 1/4 - eps approximation but the running time is a much larger polynomial (at least n 4).

Supervised classification techniques use training samples to find classification rules with small expected 0-1 loss. Conventional methods achieve efficient learning and out-of-sample generalization by minimizing surrogate losses over specific families of rules. This paper presents minimax risk classifiers (MRCs) that do not rely on a choice of surrogate loss and family of rules. MRCs achieve efficient learning and out-of-sample generalization by minimizing worst-case expected 0-1 loss w.r.t. In addition, MRCs' learning stage provides performance guarantees as lower and upper tight bounds for expected 0-1 loss.

The proliferation of web agents necessitates advanced navigation and interaction strategies within complex web environments. Current models often struggle with efficient navigation and action execution due to limited visibility and understanding of web structures. Our proposed R2D2 framework addresses these challenges by integrating two paradigms: Remember and Reflect. The Remember paradigm utilizes a replay buffer that aids agents in reconstructing the web environment dynamically, thus enabling the formulation of a detailed ``map'' of previously visited pages. This helps in reducing navigational errors and optimizing the decision-making process during web interactions. Conversely, the Reflect paradigm allows agents to learn from past mistakes by providing a mechanism for error analysis and strategy refinement, enhancing overall task performance. We evaluate R2D2 using the WEBARENA benchmark, demonstrating significant improvements over existing methods, including a 50% reduction in navigation errors and a threefold increase in task completion rates. Our findings suggest that a combination of memory-enhanced navigation and reflective learning promisingly advances the capabilities of web agents, potentially benefiting various applications such as automated customer service and personal digital assistants.

Testing and evaluation is an important step before the large-scale application of the autonomous driving systems (ADSs). Based on the three level of scenario abstraction theory, a testing can be performed within a logical scenario, followed by an evaluation stage which is inputted with the testing results of each concrete scenario generated from the logical parameter space. During the above process, abundant testing information is produced which is beneficial for comprehensive and accurate evaluations. To make full use of testing information, this paper proposes an Integrated accelerated Testing and Evaluation Method (ITEM). Based on a Monte Carlo Tree Search (MCTS) paradigm and a dual surrogates testing framework proposed in our previous work, this paper applies the intermediate information (i.e., the tree structure, including the affiliation of each historical sampled point with the subspaces and the parent-child relationship between subspaces) generated during the testing stage into the evaluation stage to achieve accurate hazardous domain identification. Moreover, to better serve this purpose, the UCB calculation method is improved to allow the search algorithm to focus more on the hazardous domain boundaries. Further, a stopping condition is constructed based on the convergence of the search algorithm. Ablation and comparative experiments are then conducted to verify the effectiveness of the improvements and the superiority of the proposed method. The experimental results show that ITEM could well identify the hazardous domains in both low- and high-dimensional cases, regardless of the shape of the hazardous domains, indicating its generality and potential for the safety evaluation of ADSs.

Graph-structured combinatorial challenges are inherently difficult due to their nonlinear and intricate nature, often rendering traditional computational methods ineffective or expensive. However, these challenges can be more naturally tackled by humans through visual representations that harness our innate ability for spatial reasoning. In this study, we propose transforming graphs into images to preserve their higher-order structural features accurately, revolutionizing the representation used in solving graph-structured combinatorial tasks. This approach allows machines to emulate human-like processing in addressing complex combinatorial challenges. By combining the innovative paradigm powered by multimodal large language models (MLLMs) with simple search techniques, we aim to develop a novel and effective framework for tackling such problems. Our investigation into MLLMs spanned a variety of graph-based tasks, from combinatorial problems like influence maximization to sequential decision-making in network dismantling, as well as addressing six fundamental graph-related issues. Our findings demonstrate that MLLMs exhibit exceptional spatial intelligence and a distinctive capability for handling these problems, significantly advancing the potential for machines to comprehend and analyze graph-structured data with a depth and intuition akin to human cognition. These results also imply that integrating MLLMs with simple optimization strategies could form a novel and efficient approach for navigating graph-structured combinatorial challenges without complex derivations, computationally demanding training and fine-tuning.