Summary
This paper considers application of variance reduction to sign-based optimization, i.e., a setting where the algorithm can only access to $\mathrm{sign}(\nabla f(x^t; \xi^t))$ at step $t$, in the smooth and nonconvex setting.
Because $\\{\pm 1\\}$-valued vectors can be transmitted more efficiently than real-valued vectors, the sign-based optimization is considered to be useful especially in distributed optimization.
While a naive SGD-type algorithm previously achieved the convergence rate of $O(d^\frac12 T^{-\frac14})$, the proposed variance-reduced algorithm yields the rate of $O(d^\frac12 T^{-\frac13})$ (measured by the $L_1$-norm of the gradient.)
Next, they applied the algorithm to finite-sum optimization (with $m$ components) and obtained the convergence rate of $O(m^\frac14 d^\frac12 T^{-\frac14})$.
Finally, they applied these results to distributed optimization (the server received $\\{\pm 1\\}$-valued gradient estimators from clients), with an additional technique called \textit{majority vote} to obtain unbiased gradient estimators, and obtained improved communication complexities.
Strengths
### **The problem is well-motivated**
Sign-based optimization is an important technique to reduce computational / communication complexities in large-scale optimization. I think it is a natural attempt to apply variance reduction, which is a common technique to accelerate optimization, to achieve more efficient sign-based optimization.
### **Improved convergence rate**
Overall, the proposed approach improved the convergence rates of sign-based optimization, which I think solid contributions to the theory of optimization.
- For stochastic non-convex optimization, the proposed algorithm achieves $\min{1\leq t \leq T}\mathbb{E}[\\|\nabla f(x^t)\\|]\lesssim d^\frac12 T^{-\frac13}$, which is an improvement from the $d^\frac12 T^{-\frac14}$ rate of SignSGD ([Bernstein et al., 2018](https://arxiv.org/abs/1802.04434)).
- For finite-sum optimization, the proposed algorithm achieves $\min{1\leq t \leq T}\mathbb{E}\[\|\nabla f(x^t)\\|]\lesssim m^\frac14 d^\frac12 T^{-\frac12}$, whereas the previous SignSVRG algorithm achieves the rate of $O(m^\frac12 d^\frac12 T^{-\frac12})$ ([Chzhen and Schechtman, 2023](https://arxiv.org/abs/2305.13187). (I am a bit confused because Ii looks like there is no benefit of variance reduction for SignSVRG in terms of the dependency on $m$.)
- For distributed optimization, the proposed algorithm achieves $\min{1\leq t \leq T}\mathbb{E}[\\|\nabla f(x^t)\\|]\lesssim d^\frac12 T^{-\frac12} + d n^{-\frac12}$ or $\lesssim d^\frac14 T^{-\frac14}$. The previous bound was $d T^{-\frac14} + d n^{-\frac12}$ ([Sun et al., 2023](https://proceedings.mlr.press/v202/sun23l.html)) or $d^\frac38 T^{-\frac18}$ ([Jin et al., 2023](https://arxiv.org/abs/2002.10940), in $L^2$-norm). This is achieved by a trick called majority vote, which stochastically maps the real-valued gradient vector (or $\nabla f_i(x)$) into $\\{\pm 1\\}$-valued vectors transmitted to the server.
### **Experimental results**
The authors showed sufficient amount of experiments to verify the validity of the proposed methods (as a theory paper).
Weaknesses
### **Technical novelty**
Variance reduction itself is quite common in the optimization field so I am afraid that this paper might be a bit incremental. Section 3.3 (Results under weaker assumptions) looks redundant given Theorem 2, as there are no technical difficulty about weakening the assumption described.
### **Hyperparameter choice**
Although this is a common criticism, most variance reduction algorithm require a very careful hyperparameter tuning. It looks like the theoretical guarantees of the proposed algorithms also require a specific set of hyperparameters, and I am not confident in the robustness of the proposed algorithms to the hyperparameters.
Questions
### **On additional terms**
- Why is the term of $md/T$ required in Theorem 4?
- Why is the term of $d n^{-\frac12}$ required in Theorem 5?
### **On the difficulties to further improve the convergence rates**
- In theorem 6, why cannot you improve the convergence rate into $\mathrm{poly}(d) T^{-\frac13}$?
### **Assumptions**
- Is it possible to weaken Assumption 3 to averaged smoothness, i.e., $\frac1m \sum_{i=1}^m \\|\nabla f_i(x)-\nabla f_i(y)\\|^2 \leq L^2 \\|x-y\\|^2$