Towards a Better Theoretical Understanding of Independent Subnetwork Training

Dear Reviewer 2HE3,

Thanks for the time and effort devoted to our paper.

Comments on Weaknesses

The provided experimental results are not conclusive enough and placed in the end of the Appendix.

We comment on this in our general comment (link) on experiments to all reviewers.

We would like to highlight that the title of our work is “Towards a Better Theoretical Understanding of IST”. That is why, in the main part of the paper, we focus on contributions from theoretical analysis. Another reason is the limited space allowed by the conference submission format. If the reviewer believes that moving the experimental results to the main part will strengthen the points we are making, we can do this in the camera-ready version.

The work is mainly focused on the quadratic model.

We address this in our general response (link) to all reviewers regarding assumptions.

This model is chosen for its commonality in supervised machine learning, including its use in neural networks and its demonstrated efficacy in providing theoretical insights for complex optimization algorithms. In our paper, we emphasize that, despite its apparent simplicity, the quadratic model poses significant analytical challenges, particularly due to the biased gradient estimator used in IST. This makes it a compelling choice for analyzing complex phenomena within optimization algorithms. We further demonstrated that even in seemingly straightforward scenarios, such as the homogeneous interpolation case, the algorithm might not converge.

Responses to questions

Can this work be extended to neural networks such as [1]?

As far as we know, convergence of ResNets training is not adequately understood even for much simpler optimization algorithms such as gradient descent. This lack of understanding is compounded in the case of IST due to the biased nature of the gradient estimator and the complexities inherent in distributed training. Given these challenges, a straightforward extension of our current work to ResNets or similar architectures is not feasible at this stage.

Best regards, Authors

Dear Reviewer cu8b,

Thanks for the time and effort devoted to our paper. We greatly value careful reading of the material and the positive evaluation of our work.

Comments on Weaknesses

Section 2.2 lists 3 assumptions for the theoretical analysis. The authors also discuss the necessity of each assumption. Could the authors try to remove one of them? Specifically, is it possible to discuss other problems other than the specific quadratic one?

We address this weakness in our general response (link) to all reviewers regarding assumptions.

We note that the assumption of exact submodel gradient computation can be easily generalized to stochastic estimators with bounded variance. Regarding the choice of a quadratic model. We chose this approach due to the clear theoretical insights it provides, as detailed in our study. Analyses of similar methods with non-quadratic loss functions have often led to restrictive and impractical assumptions, resulting in unsatisfactory convergence bounds, as discussed in Section 4.3 and Appendix C. The complexity and lack of a suitable theoretical framework for a general class of $L$-smooth functions, particularly with challenges like biased gradient estimators, further motivated our decision.

While we acknowledge the value of extending our analysis to non-quadratic settings, the current theoretical landscape and the intricacies of such an extension necessitated our initial focus on the quadratic model. This foundational work sets the stage for future exploration in more complex loss functions as the field advances.

The paper focuses on the theoretical aspects of IST. It would be insightful to discuss the practical implications of the findings for real-world applications and provide guidance on effectively utilizing IST in various distributed training scenarios.

Thank you for your note on the practical implications of our findings. We discussed it in our general comment (link) on experiments to all reviewers.

Briefly, our study indicates that IST can be highly efficient in both homogeneous and heterogeneous settings, given interpolation conditions typical for large neural networks. However, in the more general case, we found that the convergence of naïve IST is influenced by the level of heterogeneity among the distributed nodes. Specifically, decreasing the learning rate can be especially helpful in heterogeneous scenarios for reducing error.

Figures 1a and 1b have different vertical axis, relative error and absolute error. Could the authors provide both relative and absolute error for these two cases.

We would like to note that it was done on purpose. The first (1a) plot illustrates that the method (functional gap) converges to the neighborhood of the solution in the first case. While the second (1b) one shows that the method’s iterates converge to a fixed point different from the optimum. We can provide additional results in the camera-ready version of the paper.

At the bottom of Page 2, $\mathbf{R}^d \to \mathbf{R}$

Thank you for pointing this out. We already fixed it in our revision.

Best regards, Authors

Dear Reviewer GaQK,

Thanks for the time and effort devoted to our paper. We greatly value careful reading of the material and Appendix.

Responses to questions

Can the author further discuss why the assumption that performing only one gradient computation is reasonable, as it is not a common choice for efficient IST? It would be better if the author could show the theoretic analysis still holds with a more relaxed assumption, like performing twice or more.

We address this comment in our general response (link) to all reviewers regarding assumptions.

We understand that this assumption might seem restrictive and potentially impractical due to the increased communication costs it could entail. However, it is required to isolate and analyze specific properties of IST more effectively. We would like to highlight that our theory could potentially be extended to scenarios involving multiple local steps, as suggested in the approach of Khaled et al. (2019). However, the current state of research indicates that no conclusive analysis demonstrates the advantages of multiple local steps in the worst-case scenarios. We believe that the insights gained from our approach are crucial for guiding future research that might explore more complex scenarios, including those involving multiple local steps.

Can the authors provide a clear discussion on the reason for introducing the gradient sparsification operator compared to the original formula? Why is this operator necessary when analyzing the convergence of IST if those two techniques are orthogonal?

Thank you for bringing this up! Let us clarify the point.

Gradient sketching is introduced to better represent submodel computations. Note that when the gradient is taken with respect to the submodel $\nabla f(\mathbf{C} x)$ it can result in a non-sparse update, which contradicts the idea of IST. To illustrate this, imagine a logistic regression problem, for which computing a gradient for compressed weights vector (even for zero) may result in a non-sparse gradient (potentially without any zeros at all). That is why we believe that sparsification of the gradient is an essential component of correclty representing IST. Thus, our work improves upon the analysis of the original paper.

Best regards, Authors

---

Khaled, Ahmed, et al. "First analysis of local GD on heterogeneous data." arXiv preprint:1909.04715 (2019).

Dear Reviewer VkZR,

Thanks for your time and effort.

Comments on Weaknesses

Theoretical understanding seems to be constrained by the assumptions, which might separate the current analysis from the real use cases

We address this comment in our general response (link) to all reviewers regarding assumptions.

We want to emphasize that in our study, the algorithm and problem setting are intentionally simplified to precisely isolate and understand the unique effects of combining data with model parallelism, especially in the context of distributed submodel gradient computations. We are aware that assumptions we make may deviate from practical settings. However, our goal was not to replicate real-world scenarios closely but to develop a fundamental understanding of certain theoretical aspects of IST.

Although the suggested analysis of the convergence and bias sounds interesting and useful, the limited experimental validation would limit the application of the proposed observation in real distributed training scenarios.

We comment on this Weakness in our general comment (link) on experiments to all reviewers.

In addition, let us stress that the main contribution of our work is from the theory side, and that is why, in our experiments, we focus on well-controlled settings that satisfy the assumptions in our paper to provide evidence that our theory translates into observable predictions. These are well-designed experiments that do support our theory and core claims. Since our results guarantee that the methods work, we do not need to test them extensively on large or complicated datasets and models to show that they do (which is necessary for heuristics unsupported by any theory).

Responses to questions

Can we see a more realistic distributed training scenario (e.g., training ImageNet deep neural networks) to validate the key observations of this work?

We consider extending our experimental results with neural network training for the camera-ready version of the paper. Due to time constraints, it is not possible to provide them during the rebuttal period.

Best regards, Authors

Next, we comment on the necessity and reasons for each simplification, expanding on the paper's subsection 2.2.

1) Exact submodel gradient computation

Our results can be easily generalized to unbiased stochastic gradient estimators $g(x)$ with a bounded variance (one of the most used in the stochastic optimization literature) $\mathbb{E} \||g(x) - \mathbb{E} g(x) \||^2 \leq \delta^2.$ Namely, such local gradient estimators will introduce an additional neighborhood term $\gamma \delta^2$ in our convergence upper bounds. This can be obtained using the bias-variance decomposition:

$$\mathbb{E} \||g(x)\||^2 = \mathbb{E} \||g(x) - \mathbb{E} g(x) \||^2 + \|| \mathbb{E} g(x) \||^2.$$

2) Single local step / gradient computation

Our theory can be extended to methods taking multiple local steps using the approach of, e.g., [2]. However, we deliberately avoided this as it would lead to worse theoretical results, as simple local methods (like local SGD) were shown to be dominated by simpler non-local counterparts in the heterogeneous setting [3]. So, even after several years of studying local update algorithms (at least since 2019), no satisfactory analysis shows its benefits in the worst case.

3) Quadratic model

To start, quadratic loss function is one of the most common (along with cross-entropy) choices of loss functions in supervised machine learning. Neural networks are not an exception.

We want to bring your attention to the fact that even for such a “simple” problem, the analysis is very non-trivial because the gradient estimator of the studied method is biased. We show that even for an interpolation homogeneous case, the algorithm may not converge. Our main goal is to study the properties of the method used for training large models with combined model and data parallelism. We believe that the quadratic problem is very well demonstrative for our purposes. In addition, as of today, we are not aware of any optimization theory for deep neural networks that does not simplify the actual practical settings.

There were already attempts to perform analysis of similar classes of methods for a different class of loss functions. There is a discussion of their results in Section 4.3 and Appendix D in more detail. We find their convergence bounds unsatisfying from a theoretical viewpoint due to too restrictive additional assumptions (e.g., on bounded gradient norm or sparsification parameter), which lead to vacuous bounds in some instances. That is why we decided to take a step back and start with a quadratic problem setting, which allowed us to perform a precise theoretical analysis and reveal the advantages and limitations of IST. Generalizing our results to a non-quadratic setting is currently an open and potentially challenging problem. When we tried to solve this issue ourselves, it was found that we are not aware of a theoretical framework that allows to perform analysis for a general class of $L$-smooth functions due to challenges (e.g., biased gradient estimator) mentioned in Section 2.1 and before 4.3. We would greatly appreciate it if the reviewers shared any ideas on how to extend our theoretical results.