Variance Reduced Distributed Non-Convex Optimization Using Matrix Stepsizes
Federated Learning;Non-Convex Optimization;Optimization
Yes
No ethics review needed.
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.
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.
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.
Please see the part of questions.
Yes
No ethics review needed.
See weaknesses.
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.
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.
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.
Yes
No ethics review needed.
(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?
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.
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.
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.
Yes
No ethics review needed.
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?
variance reduced method together with matrix step size shows convergence
the paper considers matrix step size for federated learning, combined with some variance reduction methods to achieve exact convergence
only considered nonconvex case
This paper proposes two variance reduced matrix step-sized federated learning algorithms for non-convex objectives.
@inproceedings{
anonymous2024variance,
title={Variance Reduced Distributed Non-Convex Optimization Using Matrix Stepsizes},
author={Anonymous},
booktitle={Submitted to The Thirteenth International Conference on Learning Representations},
year={2024},
url={https://openreview.net/forum?id=M5u38Os65F},
note={under review}
}
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.
I certify that there is no URL (e.g., github page) that could be used to find authors’ identity.
I acknowledge that I and all co-authors of this work have read and commit to adhering to the ICLR Code of Ethics.
Federated Learning Non-Convex Optimization Optimization
I certify that there is no acknowledgement section in this submission for double blind review.
/pdf/bda0a7b154b1e866a74e1f88f3bef8f627013dd5.pdf
optimization
I understand the reciprocal reviewing requirement as described on https://iclr.cc/Conferences/2025/CallForPapers. If none of the authors are registered as a reviewer, it may result in a desk rejection at the discretion of the program chairs. To request an exception, please complete this form at https://forms.gle/Huojr6VjkFxiQsUp6.
I certify that this submission complies with the submission instructions as described on https://iclr.cc/Conferences/2025/AuthorGuide.
Variance Reduced Distributed Non-Convex Optimization Using Matrix Stepsizes
ICLR 2025 Conference Submission
ICLR.cc/2025/Conference/Submission