- Rating
- 1
- Confidence
- 3
- Informativeness
- 1
- Presentation
- 2
- Soundness
- 1
Read review
Paper summary
This paper investigates variance reduction with compressed communication for distributed nonconvex optimization. The authors identify a potential bias caused by majority voting over local gradient signs and introduce two algorithms, DVR-Sign and DVR-Q, that maintain a global gradient estimate through compressed gradient increments. The methods are further extended to finite-sum optimization with periodic gradient refreshes. The paper provides convergence analyses for both settings and evaluates the methods using LIBSVM datasets and ImageNet classification tasks.
Critical strengths
-
The paper presents a counterexample demonstrating that majority voting over local gradient signs may lead to a nonzero gradient floor, even when the local gradients are exact. This observation provides a useful explanation of why conventional sign-based aggregation can be problematic in distributed optimization.
-
The authors establish convergence guarantees for stochastic and finite-sum optimization and show improvements over the theoretical bounds of SSVR-MV. The experimental results also indicate some performance gains over the selected baselines.
Critical weaknesses
-
The novelty of the proposed methods is not sufficiently established. Several important components of the proposed algorithms, including stochastic sign compression, recursive gradient estimation, and the communication of compressed gradient differences, have already been explored in previous studies. In particular, DIANA (Mishchenko et al., 2019) and MARINA (Gorbunov et al., 2021) employ closely related ideas for distributed optimization. The periodic full-gradient refreshes combined with compressed gradient differences in Algorithm 2 also resemble the mechanism used in MARINA. However, the paper provides little discussion of these closely related approaches. The Related Work section mainly summarizes previous results without clearly establishing how the proposed algorithms differ from existing methods. As a result, it is difficult to determine whether the contribution lies in a fundamentally new algorithmic design or primarily in extending the convergence analysis of existing techniques.
-
The practical value of the theoretical results is not convincingly demonstrated. A substantial part of the paper is devoted to convergence analysis, but the connection between these theoretical improvements and practical communication efficiency remains unclear. The paper does not sufficiently examine how compression noise affects convergence or whether the improved theoretical rates lead to meaningful communication savings in practice.
-
The experimental evaluation is also limited. Although data heterogeneity is a central motivation, the paper does not clearly describe the Non-IID data partitioning or investigate how different levels of heterogeneity influence performance. This is an important omission since sign-based gradient updates can be sensitive to disagreement among local gradients. Furthermore, the experiments do not include closely related compressed variance-reduction methods or provide direct validation of the finite-sum variants. Consequently, the current results are insufficient to establish the practical advantages of the proposed approach.
Questions for authors
-
What distinguishes the proposed algorithms from existing compressed variance-reduction approaches, particularly DIANA and MARINA? Can the authors clarify the main algorithmic novelty and provide comparisons with these methods?
-
How are the training datasets distributed among workers? Can the authors evaluate the methods under different Non-IID settings to demonstrate their robustness to data heterogeneity?
-
How does compression variance affect the performance of the proposed methods, especially for high-dimensional models? Can the authors provide a more comprehensive evaluation of communication efficiency, including the cost of periodic full-gradient refreshes and convergence to comparable accuracy levels?