Variance Reduced Distributed Non-Convex Optimization Using Matrix Stepsizes

Authors: Hanmin Li, Avetik Karagulyan, Peter Richtárik
Primary area: optimization
Keywords: Federated Learning, Non-Convex Optimization, Optimization

Abstract:
Matrix-stepsized gradient descent algorithms have been shown to have superior performance in non-convex optimization problems compared to their scalar counterparts. The det-CGD algorithm, as introduced by Li et al. (2023), leverages matrix stepsizes to perform compressed gradient descent for non-convex objectives and matrix smooth problems in a federated manner. The authors establish the algorithm’s convergence to a neighborhood of a weighted stationarity point under a convex condition for the symmetric and positive-definite matrix stepsize. In this paper, we propose two variance-reduced versions of the det-CGD algorithm, incorporating MARINA and DASHA methods. Notably, we establish theoretically and empirically, that det-MARINA and det-DASHA outperform MARINA, DASHA and the distributed det-CGD algorithms in terms of iteration and communication complexities.

Decision: reject
Reviewer scores: 5, 3, 5, 5

Reviews and discussion:
<thread>
creation date:
1729490190963

thread_type:
official_review

<thread_object>
creator: reviewer_3m4m

<content>
summary:
the paper considers matrix step size for federated learning, combined with some variance reduction methods to achieve exact convergence

strengths:
variance reduced method together with matrix step size shows convergence

weaknesses:
only considered nonconvex case

questions:
1. What is the challenge in analysis of combining variance reduction with matrix step size?
2. How does the rate compare with existing literature?
3. Why one should take the trouble of using matrix step size?
</content>
</thread_object>

</thread>
<thread>
creation date:
1730060224185

thread_type:
official_review

<thread_object>
creator: reviewer_iscf

<content>
summary:
The paper proposes matrix-stepsize versions, namely det-MARINA and det-DASHA, of distributed variance-reduction algorithms MARINA and DASHA. The main idea was that the scalar stepsize can be replaced by a matrix stepsize similar to second-order (Newton) methods. The authors derive convergence guarantees to stationarity in the sense that the gradient squared norm vanishes with rate $O(1/k)$ where $k$ is the algorithms' iterate. Numerical experiments show some improvement of the proposed methods compared to MARINA and DASHA.

strengths:
The paper is generally well-written with sufficient background. The motivation is also clear and natural: matrix stepsize is better than scalar stepsize. Convergence analysis is provided.

weaknesses:
Since the proposed methods are matrix-stepsize adaptations of MARINA and DASHA, we can expect them to retain the general properties observed in the original MARINA and DASHA schemes. To my understanding, both MARINA and DASHA also converge to stationarity and, unlike det-CGD, do not exhibit a restrictive convergence neighborhood. Thus, these new algorithms would naturally inherit this characteristic, which makes this advantage less novel in my view. From a theoretical standpoint, it would be helpful to directly compare Theorems 1 and 2 with the convergence properties of MARINA and DASHA (see specific questions below). Additionally, the Lipschitz matrix seems impractical in most cases, whereas the Lipschitz constant is typically more accessible; therefore, including the Lipschitz matrix may not be essential. While the experiments do show improvements, the gains appear relatively modest.

questions:
(1) Regarding the optimal matrix stepsize in the optimization problem in line 304, the authors minimize the RHS of (5) with respect to D that aims to makes the bound as small as possible. However, the LHS of (5) also contains D. How could you tell that minimizing the RHS yields the optimal improvement?

(2) When comparing det-MARINA and and MARINA, in Corollary 3 for example, they say this iteration complexity of det-MARINA is better than MARINA. Please elaborate this claim more. For example, their gradient norm are not the same, how can we compare them?
</content>
</thread_object>

</thread>
<thread>
creation date:
1730501674188

thread_type:
official_review

<thread_object>
creator: reviewer_h5fa

<content>
summary:
The work "Variance reduced distributed nonconvex optimization using matrix stepsizes" proposes decentralized variance reduced schemes with matrix step-sizes. The incorporation of variance reductions allows for convergence to arbitrary precision as opposed to the original work Li et. al (2024b). The authors provide theoretical guarantees for their algorithms and demonstrate their performance empirically.

strengths:
1) The proposed schemes address an issue that makes the distributed version of det-CGD less desirable. This is achieved via the incorporation of a variance reduction mechanisms that aids in controlling the variance introduced by the compression.
2) The work is well written and the contribution is clear.

weaknesses:
1) The novelty of this work is limited, as it seems combine a known algorithm (detCGD) with a given problem with two known solutions to the problem (proposed in MARINA and DASHA). It is unclear to this reviewer what is the main challenge when combining these. I suggest the authors highlight which technical challenges need to be addressed to incorporate variance reduction into detCGD, and why these significantly differ from the case in which the step-size is a scalar.

questions:
See weaknesses.
</content>
</thread_object>

</thread>
<thread>
creation date:
1730785269674

thread_type:
official_review

<thread_object>
creator: reviewer_gjqi

<content>
summary:
This paper provided two novel federated learning optimization methods based on variance-reduced matrix stepsizes. The theoretical analysis shows the communication complexity of proposed methods are better than existing methods, which is also validated by numerical experiments.

strengths:
The idea of using matrix stepsize and variance-reduction to improve the communication complexity in federated learning is interesting. The thermotical guarantees have been established.

weaknesses:
Please see the part of questions.

questions:
I have several questions about Section 4.2.

a) Line 310 says we can relax the problem to certain linear subspace and achieve Corollary 1. Is there any theoretical result to bound the approximation error of such relax?  

b) In the expression of equation (6), we require achieving matrices ${\bf W}^{1/2}$, ${\bf L}^{-1}$, and several eigenvalues. Is the computation of these quantity expensive in practice? 

c) Line 394 says we can estimate ${\bf L}_i$ by gradient method (Wang et al., 2022). I have not detailed checked the paper of Want et al. (2022). Can you summarize their main results and ideas (e.g., the complexity and the algorithm design)?

I have also some questions about the comparisons with related work.

d) I think more detailed introduction for MARINA and DASHA is necessary, which is useful to help the readers understand why the authors focus on the comparisons with these two methods.

e) The iteration with matrix stepsize looks more expensive than classical first-order methods. I think the comparison with classical first-order methods (e.g., distributed GD, SGD, SARAH...) should be involved, including the discussion on the computational cost.
</content>
</thread_object>

</thread>
<thread>
creation date:
1731850758939

thread_type:
official_comment

<thread_object>
creator: authors

<content>
title:
Response to all reviewers

comment:
We sincerely thank all the reviewers for taking the time to review our paper.

The reviewers raised several concerns, for which we have prepared a comprehensive, case-by-case response to each reviewer. We hope this detailed clarification addresses their questions and provides additional insight into our work.
</content>
</thread_object>

</thread>


Metareview:
metareview:
This paper extends the det-CGD algorithm, which uses matrix stepsizes for non-convex optimization, by introducing two variance-reduced versions: det-MARINA and det-DASHA. These methods improve iteration and communication complexities over the existing methods, with both theoretical and empirical validation of their superior performance.

While the paper's theoretical approach is interesting, the main criticism raised by the reviewers was the lack of novelty in the proposed method. Specifically, the following weaknesses were highlighted:

1. One reviewer noted that the novelty of this work is limited, as it combines a known algorithm (det-CGD) with a given problem and two existing solutions (MARINA and DASHA). The reviewer found it unclear what specific challenges were addressed in combining these components.
2. Another reviewer expressed a similar concern, stating that the results of this paper are unsurprising when compared to MARINA and DASHA.