Response to Reviewer Nhkx
Thank you for your prompt response and valuable comments. We have carefully considered your remaining concerns and have responded in detail as follows:
>__Q6:__ My main consideration is the applicability of the lower bound provided by Li et al. [6]. Noticing that their Definition 1 does not include second-order Lipschitz continuity. The lower bound of $\varOmega \left( \epsilon ^{-4} \right)$ in their Theorem 2 is based on the function $f^{\text{sc-nc-sg}}$. The proof of this theorem only verifies its gradient is Lipschitz continuous. However, the Lipschitz continuity of its Hessian is unclear. Therefore, we should check if the construction of Li et al. [6] holds the second-order Lipschitz continuity shown in Assumption 2. If the author can address this issue, I will increase my overall rating. Otherwise, the statement on the optimality should be avoided in revision (I will still keep borderline accept).
__Response__ We have carefully checked the construction of the hard examples for obtaining the complexity lower bound in [6] and verified that they satisfy second-order Lipschitz continuity on $y$ as assumed in Assumption 2. Specifically, we recall the hard instance in the stochastic setting in [6] (c.f., Eqs. (10) and (11)) as follows:
$$
\bar{f}^{\text{nc-sc-sg}}\left( \boldsymbol{x},\boldsymbol{z};\bar{\boldsymbol{y}} \right) =-\Psi \left( 1 \right) \Phi \left( x_1 \right) +\sum_{i=2}^T{\left[ \Psi \left( -z_i \right) \Phi \left( -x_i \right) -\Psi \left( z_i \right) \varPhi \left( x_i \right) \right]}+\sum_{i=1}^{T-1}{\left[ c_1x_{i}^{2}+c_2z_{i+1}^{2} \right]}+\sum_{i=1}^{T-1}{h^{\text{sg}}\left( x_i,z_{i+1};\bar{\boldsymbol{y}}^{\left( i \right)} \right)},
$$
with
$$
h^{\text{sg}}\left( x,z;\boldsymbol{y} \right) =\frac{C}{n}\left[ -\frac{1}{2}\boldsymbol{y}^{\text{T}}\left( \frac{1}{n^2}I_n+A \right) \boldsymbol{y}+\boldsymbol{b}_{x,z}^{\text{T}}\boldsymbol{y} \right]
$$
and $\boldsymbol{b}_{x,z}=x\boldsymbol{e}_1-\frac{1}{2}z\boldsymbol{e}_n$, where $\boldsymbol{x}$ and $\boldsymbol{z}$ are variables to minimize, $\boldsymbol{y}$ is the variable to maximize, $\Psi \left( \cdot \right)$ and $\Phi \left( \cdot \right)$ are component functions, $c_1$, $c_2$ and $C$ are constants, $A$ is a positive semi-definite matrix (refer to Section 4 in [6] for detailed definitions).
It should be noted that the assumption of second-order Lipschitz continuity of this work is only required to hold for $y$ (c.f., Eq. (11) in Assumption 2), and the terms related to $y$ in the objective function $\bar{f}^{\text{nc-sc-sg}}$ are only in $h^{\text{sg}}$, which is twice differentiable. It is not difficult to verify that $\nabla _{x,z;\boldsymbol{y}}^{2}h^{\mathrm{sg}}=-\left( \frac{1}{n^2}I_n+A \right)$ and $\nabla _{\boldsymbol{yy}}^{2}h^{\mathrm{sg}}=\mathrm{diag}\left\\{ 1,0,\cdots,0,-1/2 \right\\}$ are constant matrices and thus both are Lipschitz continuous. This indicates that $\bar{f}^{\text{nc-sc-sg}}$ is second-order Lipschitz continuous for $y$, satisfying Eq. (11) in Assumption 2. Therefore, we believe that the lower bound given by Li et al. [6] is applicable to the function class considered in our work. Combined with the previous discussion, we will carefully revise our statement about "near-optimal" to avoid any possible confusion.
>__Q7:__ For Q4, I recommend to unify the presentation of constrained/unconstrained setting on the variable.
__Response__ Thank you for your suggestion. We will do a proper revision of the presentation of the decision variable domains.
>__Q8:__ For Q5, I think reduce the communication complexity is possible even if there is no average smoothness assumption. At least, this can be address in nonconvex minimization, e.g.,
> * [18] Yucheng Lu and Christopher De Sa. Optimal Complexity in Decentralized Training. ICML 2021.
__Response__ We agree with the reviewer that reducing the communication complexity is possible even without relying on the average smoothness assumption. As mentioned by the reviewer, without this assumption, Lu et al. [18] combined local updates with the Factorized Consensus method (c.f., Lemma 1 in [18]) and Accelerated Gossip protocol (c.f., Algorithm 3), yielding reduced communication complexity. However, in order to obtain a computational complexity of $\varOmega \left( \epsilon ^{-3} \right)$ as in [12], this assumption is required in most of the literature based on the variance reduction methods. Otherwise, without this assumption, the sampling complexity obtained by Lu et al. [18] matches another lower bound $\varOmega \left( \epsilon ^{-4} \right)$. Having noted the characteristics and limitations of these methods, we believe they are all worthy of further investigation to improve the communication efficiency of distributed algorithms, with or without this average smoothness assumption.