Near-Optimal Distributed Minimax Optimization under the Second-Order Similarity

This paper considers the distributed convex-concave minimax optimization under the second-order similarity. We propose stochastic variance-reduced optimistic gradient sliding (SVOGS) method, which takes the advantage of the finite-sum structure in the objective by involving the mini-batch client sampling and variance reduction. We prove SVOGS can achieve the $\varepsilon$-duality gap within communication rounds of ${\mathcal O}(\delta D^2/\varepsilon)$, communication complexity of ${\mathcal O}(n+\sqrt{n}\delta D^2/\varepsilon)$, and local gradient calls of $\tilde{\mathcal O}(n+(\sqrt{n}\delta+L)D^2/\varepsilon\log(1/\varepsilon))$, where $n$ is the number of nodes, $\delta$ is the degree of the second-order similarity, $L$ is the smoothness parameter and $D$ is the diameter of the constraint set. We can verify that all of above complexity (nearly) matches the corresponding lower bounds. For the specific $\mu$-strongly-convex-$\mu$-strongly-convex case, our algorithm has the upper bounds on communication rounds, communication complexity, and local gradient calls of $\mathcal O(\delta/\mu\log(1/\varepsilon))$, ${\mathcal O}((n+\sqrt{n}\delta/\mu)\log(1/\varepsilon))$, and $\tilde{\mathcal O}(n+(\sqrt{n}\delta+L)/\mu)\log(1/\varepsilon))$ respectively, which are also nearly tight. Furthermore, we conduct the numerical experiments to show the empirical advantages of proposed method.

Paper

Similar papers

Peer review

Reviewer DkHm5/10 · confidence 4/52024-07-08

Summary

The paper proposes SVOGS, and improved algorithm for distributed minimax optimization by client mini-batch sampling and gradient variane reduction. Theoretical rates on communication complexity and gradient computations are provided, along with their lower bounds. The analysis shows that SVOGS achieves the corresponding lower bounds. A numerical example is provided to justify the efficacy.

Strengths

1. The presentation is clear and the notations are clean. 2. The paper is theoretically solid, with comprehensive thereotical results. The lower bounds, although based on some tricks and results from prior works, provide novel contribution to the field of minimax optimization.

Weaknesses

The main drawback is the experiment section. The proposed method is only tested on one small dataset, and the paper lacks the basic information on how SVOGS is implemented and tuned (e.g., parameter $b, p, \alpha, \gamma$ in Algorithm 1). It seems to me that the proposed method requires much heavier fint-tuning than prior methods thus less practically convenient. The implementation details should be provided to justify the true practical value of this method. Also, it should be tested on more datasets.

Questions

See above

Rating

5

Confidence

4

Soundness

2

Presentation

3

Contribution

3

Limitations

NA

Reviewer qmRX7/10 · confidence 3/52024-07-13

Summary

The paper studies distributed min-max optimization under the assumption of second-order data similarity, i.e. the hessians of the objectives at different nodes are close enough. For the classes of (strongly)-convex-(strongly)-concave functions with Lipschitz gradient, lower complexity bounds are proposed. Moreover, an algorithm SVOGS is proposed that strictly reaches the lower bounds in communications and up to a logarithmic factor in local gradient calls. Therefore, the paper almost closes the gap in distributed centralized min-max optimization with data similarity.

Strengths

1. The problem, assumptions and results are clearly stated. 2. An algorithm optimal in communications and near-optimal in gradient calls is proposed. That closes the complexity gap for the class of distributed min-max optimization problems with second-order similarity. 3. Overall, the paper has a readable structure.

Weaknesses

There still remains a gap in the local gradient calls complexity. Maybe it can be overcome with the usage of gradient sliding technique.

Questions

I did not find the difference between the number of communication rounds and communication complexity. It seems that Algorithm 1 sends the same amount of information at each communication round. So why is communication complexity different from the number of communication rounds?

Rating

7

Confidence

3

Soundness

4

Presentation

3

Contribution

4

Limitations

The work is theoretical and does not have negative societal impact.

Reviewer qmRX2024-08-09

Answer to Rebuttal

Dear Authors, Thank you for the response.

Reviewer Vpvu6/10 · confidence 4/52024-07-13

Summary

This manuscript considers solving (strongly) convex (strongly) concave distributed minimax optimization problem. The authors proposed a stochastic variance-reduced optimistic gradient sliding method with node sampling, named SVOGS, which achieves complexity nearly matches the obtained lower bound.

Strengths

- The paper improves the complexity of existing algorithms through the adoption of node sampling, especially when dealing with a large number of nodes. The theoretical results are well-supported by simulation experiments. - The complexity results are thoroughly compared with existing results. - The paper is well-organized and easy to read.

Weaknesses

- The algorithm design is straightforward. The novelty of the algorithm is limited to the node sampling aspect, which is a simple and obvious adaptation from the existing methods, e.g. Ref. [5]. The authors should further clarify the unique characterisics of the algorithm. - It seems to the reviewer that incorporating uniform and independent node sampling (c.f., Line 5 in Algorithm 1) does not present any new challenge to the convergence analysis as compared to existing methods. The authors should further clarify the technical contribution of their approach. - The experiments utilize toy datasets, e.g., a9a, which may limit the generalizability of the results. - The rationality of Assumption 2 should be discussed in more detail to ensure its validity and relevance to the study. - Theorems 1 and 2 requires many hyperparameters to be set to exact values that depend on the parameters of the problem. In practice, these parameters are often very difficult to obtain, which may weaken the theoretical results in this work.

Questions

- The authors bring the results for minimization in Ref. [25] directly to compare with the results for the minimax problem in this paper. Does this mean that the minimax problem in this paper does not have additional difficulties compared with the minimization problem? - The distinction between the optimistic gradient and extra-gradient methods for minimax problem should be clarified. The reviewer is curious about the possibility that the EG method in Ref. [25], combined with node sampling, could also achieve similar results. - Refer to Weaknesses for more concerns to be addressed properly.

Rating

6

Confidence

4

Soundness

3

Presentation

3

Contribution

2

Limitations

The (strongly) convex (strongly) concave distributed minimax optimization problem considered in this work is not applicable to most machine learning tasks and is thus of limited significance in this area.

Reviewer Vpvu2024-08-12

Thank you for the detailed response. Since most of my concerns have been well addressed, I raise my overall rating to weak accept.

Program Chairsdecision2024-09-25

Decision

Accept (poster)

© 2026 NYSGPT2525 LLC