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

The implementation details

We tune the step-size $\eta$ of SVOGS from $\\{0.01,0.1,1\\}$. The probability $p$ is tuned from $\\{p_0,5p_0,10p_0\\}$, where $p_0=1/\min\\{\sqrt{n}+\delta/\mu\\}$. The batch size $b$ is determined from $\\{\lfloor b_0/10\rfloor,\lfloor b_0/5\rfloor,\lfloor b_0\rfloor\\}$, with $b_0=1/p_0$.

We set the other parameters by following our theoretical analysis. We set the average weight as $\gamma=1-p$. For the momentum parameter, we set $\alpha=1$ for convex-concave case and $\alpha=\max\\{1-\eta\mu/6,1-p\eta\mu/(2\gamma+\eta\mu)\\}$ for strongly-convex-strongly-concave case, where we estimate $\mu$ by $\max\\{\lambda,\beta\\}$ for problem (13). For the sub-problem solver, we set its step-size according to the smoothness parameter of sub-problem (2), i.e., $1/(L+1/\eta)$.

In addition, we estimate the smooth parameter $L$ and the similarity parameter $\delta$ by following the strategy in Appendix C of Ref. [5].

Based on above appropriate setting, our SVOGS achieves better performance than baselines. We are happy to provide the detailed parameters setting in our revision.

It should be tested on more datasets

We have provided additional experimental results on datasets w8a ($N=49,749$, $d'=300$) and covtype ($N=581,012$, $d'=54$). Please refer to the PDF file in Author Rebuttal. We can obverse the proposed SVOGS performs better than baselines on these datasets. We are happy to involve the additional experimental results into our revision.

Why is the communication complexity different from the number of communication rounds?

Recall that the communication complexity in our paper refers to the overall volume of information exchanged among the nodes. We take the convex and concave case as an example (Theorem 1) to explain why the communication complexity is different from the number of communication rounds.

1. The results of Theorem 1 (discussion in Line 147-177) shows we require the communication rounds of $K={\mathcal O}(\delta D^2/\varepsilon)$ to achieve the desired accuracy $\varepsilon$.

2. We requires the communication complexity of ${\mathcal O}(n)$ to achieve $F(z^0)=\frac{1}{n}\sum_{i=1}^n F_i(z^0)$ in initialization.

3. The index set ${\mathcal S}^k$ with $|{\mathcal S}^k|=b$ means the term of sums in Line 6 of Algorithm 1 takes the communication complexity of ${\mathcal O}(b)={\mathcal O}(\sqrt{n})$ at each iteration.

4. The communication for the full gradient term $F(w^{k-1})$ in Line 6 of Algorithm 1 does not need to be performed at every iteration. Notice that Line 10 performs $w^{k+1}=z^{k+1}$ with probability $p=\Theta(1/\sqrt{n})$ and performs $w^{k+1}=w^{k}$ (no communication) with probability $1-p=1-\Theta(1/\sqrt{n})$, which means only the case of $w^{k+1}=z^{k+1}$ needs to communicate to achieve the full gradient with the communication complexity of ${\mathcal O}(n)$. Therefore, the overall the expected communication complexity related to the full gradient term is ${\mathcal O}(pn)={\mathcal O}(\sqrt{n})$ at each iteration.

Based on above analysis, we can conclude the overall communication complexity is $n + {\mathcal O}(b+pn)K = {\mathcal O}(n+\sqrt{n}\delta D^2/\varepsilon),$ which is different from the communication rounds $K={\mathcal O}(\delta D^2/\varepsilon).$

In addition, the full participation methods (e.g., EG [24], SMMDS [5] and EGS [25]) requires the communication for the full gradient at every iteration, which leads to the more expensive communication complexity of ${\mathcal O}(n\delta D^2/\varepsilon)$.

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

The comparisons in Table 1-2 show the local gradient calls complexities in our results match the lower bounds up to logarithmic factors. We thank the reviewer for pointing out that the gap of logarithmic factors could possibly be overcome with the usage of the gradient sliding technique. We believe this is an interesting future direction.

Dear Authors,

Thank you for the response.

Results for minimization in Ref. [25]

Ref. [25] studies both minimization and minimax problems. We only compare their results for the minimax problem (Table 1-3).

The minimax problem is indeed more difficult than the minimization problem. For example, Section 3 of Ref. [25] considers the strongly convex minimization problem by archiving the complexities depend on $\sqrt{\delta/\mu}$ and $\sqrt{L/\mu}$, and Section 4 of Ref. [25] considers the strongly-convex-strongly-concave minimax (strongly monotone variational inequality) problem by archiving the complexities depend on $\delta/\mu$ and $L/\mu$. Noticing that the lower bounds in Section 6.2 of our paper show such dependence on $\delta/\mu$ and $L/\mu$ cannot be improved for this minimax problem, which means it is more difficult.

Combine EG [25] with node sampling

Compared with our result, applying the node sampling (variance reduction) [1] to EG method [25] will lead to the additional term $\sqrt{n}$ in the complexity of communication rounds, because EG framework cannot benefit to the mini-batch sampling.

For ease of understanding, we follow the notations and settings of the Algorithm 1 for single machine in Ref. [1] to illustrate this issue (the problem in distributed case is similar). The essential step in the analysis for Algorithm 1 of Ref. [1] is their equation (9) in Lemma 2.9, that is

where $\tau=\sqrt{1-\alpha}\gamma/L$ and Assumption 1(iv) is the mean-squared Lipschitz continuous condition on $F_j(\cdot)$ such that $\mathbb{E}\big[\\|F_j(u)-F_j(w)\\|^2\big]\leq L^2\\|u-w\\|^2$ for all $u,w\in\mathcal{Z}$.
Directly adapting above analysis to our distributed problem will leads to an extra term of $\sqrt{n}$ in the complexity of communication rounds (compared with the methods without node sampling), since the third line in the loop of Algorithm 1 of Ref. [1] only draws one sample $\xi_k$. To match the results of our paper, we desire to introduce the mini-batch sampling like our Algorithm 1 (Line 6) into the framework of EG, which is replacing the term $F_{\xi_k}(w_k)-F_{\xi_k}(z_{k+1/2})$ with $\frac{1}{|\mathcal S^k|}\sum_{j\in\mathcal S^k} (F_{j}(w_k)-F_{j}(z_{k+1/2})),$ where $\mathcal S$ follows the notation in our Algorithm 1. Then the above derivation becomes

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