An Asynchronous Bundle Method for Distributed Learning Problems

We are very grateful for your detailed feedback. Thank you! Below, we provide detailed responses to each of your questions.

Analysis. Thank you for asking about more details on the analysis.

• Can we strengthen the analysis in the absence of the growth condition? We are happy to announce that we have significantly improved the convergence result in the absence of the growth condition (see Theorem 4.9 of the modified manuscript). We now prove sublinear convergence to a neighborhood of the optimal solution, rather than the convergence of a subsequence.
• What causes the discrepancy between the results with and without the growth condition? In both cases, with and without the quadratic functional growth condition, we can establish the inequality

When the growth condition holds, we can directly relate the function value gap $F(x^\star) - F(x_{k+1})$ to the iterate gap $||x_{k+1} - x^\star ||^2$. This connection enables us to derive a contraction property, ultimately proving linear convergence. In the absence of the growth condition, however, this direct relationship no longer holds. Instead, we must rely on an alternative approach, proving and applying a novel sequence result (Lemma 4.8 in the modified manuscript). Sequence results are generally weaker and more flexible tools, which leads to a looser analysis.

• How do our results compare to the literature? Under the growth condition, our asynchronous bundle method is the only one with provable linear convergence to a neighborhood of the optimal solution. Without the growth condition, our asynchronous bundle method is the only existing one with a sublinear convergence rate. (Existing asynchronous bundle methods only gurantee convergence of a subsequence. For example, the work [1] shows in their Theorem 1 that their asynchronous bundle method satisfies $\min_{j \leq k} F(x_j) \to F(x^\star)$, assuming that their subproblem is solved exactly. We should point out that unlike us, [1] assumes the existence of a convex compact constraint set and also that the local loss functions of the workers are Lipschitz. In comparison, we assume that the local loss functions are smooth.)

[1] F. Iutzeler, J. Malick, and W. Oliveira. Asynchronous level bundle methods, 2020.

Adaptive Tuning Aspect We appreciate the suggestion to incorporate adaptive smoothness parameter estimation into the analysis and agree that it is an important direction for further research. However, after revisiting our current analysis, we realized that including this aspect would require substantial additional analysis, which goes beyond the scope of the current work. Nevertheless, we will certainly keep this suggestion in mind for future work.

Scalability. We have commented on scalability in the official comment section above.

Other comments. We deeply appreciate the reviewer's meticulous reading of our paper and his or her thoughtful feedback. We have addressed the recommended suggestions and editing tips, which have enhanced the overall quality of the manuscript. Thank you once again for reviewing our paper. Is there anything else we can clarify?

Thank you for excellent feedback and for reviewing our paper. Below, we address your concerns.

Concern regarding novelty: Thank you for raising the concern about novelty. While it is true that bundle methods have been studied extensively, our algorithm has several distinguishing features compared to the paper by A. Smola [1] and existing asynchronous bundle methods [2-5]:

• Inexact subproblems. The methods in [1-5] assume that the subproblem is solved exactly. In contrast, our analysis provides a termination criterion that can be used to derive a practical "inexact" subproblem solver. (In Appendix A.3, we show that our subproblem solver is more than an order of magnitude faster than an interior-point solver that computes an "exact" solution. This contribution is therefore significant.)
• Natural interpretation of stabilization parameter. In the proximal bundle methods in [2, 4, 5], the choice of the stabilization parameter for the subproblem is based on heuristics. In contrast, our analysis allows us to directly relate the stabilization parameter to the smoothness of the workers. This relationship results in a more natural and straightforward method for selecting an appropriate value for the stabilization parameter.
• Asynchronous updates. The bundle method proposed in [1] is synchronous, whereas both our algorithm and those in [2–5] support asynchronous updates. However, unlike the asynchronous bundle methods in [2–5], our method and its analysis explicitly quantify how the level of asynchrony of the system affects the convergence rate under the growth assumption. This type of quantification does not appear in [2-5].
• Stochastic analysis. In contrast to [1–5], our analysis covers stochastic function and gradient evaluations.

We believe the distinguishing features above show that our approach is novel and advances the state-of-the-art in both the theory and practice of bundle methods for ML.

[1] Bundle Methods for Regularized Risk Minimization, 2010.

[2] Incremental-like bundle methods with application to energy planning, 2009.

[3] Asynchronous level bundle methods, 2020.

[4] Incremental Bundle Methods using Upper Models, 2018.

[5] Bundle method for exploiting additive structure in difficult optimization problems, 2015.

Clarification on convergence results: We appreciate your comments and agree that our convergence results were not presented with sufficient clarity in the original submission. To address this, we have reorganized the manuscript to emphasize:

• Linear convergence: Under the growth condition, we establish linear convergence of the iterates to a neighborhood of the optimal solution in Theorem 4.5 of the modified manuscript. Our asynchronous bundle method is the only existing one with this provable rate under the growth condition.
• Sublinear convergence: Without the growth condition, we have derived a new result that shows sublinear convergence to a neighborhood of the optimal solution (see Theorem 4.9 in the modified manuscript). Our asynchronous bundle method is the only existing one with a provable sublinear convergence rate without the growth condition.

Experimental evaluation: We commented on scalability in the official comment section above.

Role of the bundle size $m$: You are correct that the bundle size $m$ does not appear explicitly in the convergence results. When analyzing bundle-like optimization algorithms, employing a piecewise-linear model with $m > 1$ is not advantageous from the perspective of worst-case complexity analysis [6]. However, empirical evidence suggests that increasing the bundle size from $m = 1$ can significantly improve the performance. (We show this in the paper in Figure 2 where increasing the bundle size from $m = 2$ to $m = 5$ makes our method much faster.)

[6] Y. Nesterov. Primal-dual subgradient methods for convex problems, 2009.

Memory overhead: We acknowledge that our method requires more memory at the central server compared to SGD-based methods. However, it uses substantially less memory than other distributed asynchronous algorithms that store Hessian approximations. Importantly, in our method the server only needs to store gradients, not training data, which mitigates memory concerns in many practical setups. For example, consider a training environment with a modest number of computer nodes where each node is treated as a worker (as described in the official comment above). With bundle size $m=5$ and $n=30$ workers, and an ML model with 10 million parameters, the server requires approximately 6 GB of memory to store the gradients in single precision. In many cases this is substantially less than the memory required by the workers who store the actual training data.

Once again, thank you for excellent feedback. Is there anything we can clarify? We hope that our answers have clarified the many advantages of our algorithm, and that you are willing to consider raising your score.

We deeply appreciate your feedback and your questions. Below we address them one by one.

Question 1: Provide more details on how the weighting is chosen.

Response: To construct the bundle center $\bar{z}$ we weight together the most recent query points for each worker according to

where $z^i_m$ is the most recent query point for which the server has received information from worker $i$. The weight $w_i$ is given by $w_i = L_i / L$, where $L_i$ is the smoothness of worker $i$ and $L = \sum_{i=1}^n L_i$ is the total smoothness.

At first glance, it might seem natural to adjust the weight $w_i$ to account for the actual delay experienced by worker $i$. However, our convergence analysis reveals a surprising result: the method converges robustly with this choice of the bundle center, regardless of the actual delays. Our intuition for why this approach works is that, even if $z^i_m$ is an outdated iterate, the information derived from it remains relevant because it provides a valid lower bound on $f_i$. Thus, we do not need to compensate for the actual delays when weighting together to form the bundle center.

Question 2: Do the results apply to settings where each worker has an individual maximum time delay?

Response: Excellent question. In the literature it is most common to assume a shared maximum information delay for the workers, but let's assume for a moment that the workers have different maximum delays. Denote the maximum delay for worker $i$ by $\tau_i$. Then we can refine our analysis to prove an inequality of the form

where $\beta_i = L_i/(L + \mu)$ and $\epsilon = 2\delta/(L+\mu).$ This should be compared to our current analysis that is based on a common maximum time delay $\tau$ and the inequality

Intuitively it feels like the first inequality should give a better convergence rate than the second, but we have not yet been able to prove it rigorously.

We hope that we have now addressed your questions in a clear way.

Thank you for your detailed feedback and for reviewing our paper. We are very grateful. Below, we address your concerns.

Data heterogeneity: We agree that we could have been more explicit about data heterogeneity in our initial submission since this is a major advantage of our algorithm. While many of the classical federated learning algorithms exhibit bias when clients have diverse data distributions, our algorithm does not suffer from this phenomenon. However, the data distributions influence the smoothness parameters of the local loss functions, and thereby the convergence rate of the algorithm. Let us elaborate.

For the deterministic version of our method, we prove a convergence rate in Theorem 4.4 that depends on the quantity $L = \sum_{i=1}^n L_i$. In a heterogeneous setting where the $L_i$’s vary, this bound can be much stronger than one based on the quantity $n L_{\max}$, where $L_{\max} = \max_{i=1, \dots, n} L_i$. For example, consider a scenario where the data is distributed unevenly with one worker having much larger smoothness parameter than the others. Such a scenario would be problematic for methods with convergence rates depending on $L_{\max}$. However, our method remains robust to this heterogeneity as long as the sum of the smoothness parameters remains constant. Conceptually similar results are well-known for coordinate descent methods, see eg. [1].

That said, we wish to stress that our method and its analysis works without any strong assumptions on the data distribution, which we believe is a significant advantage.

[1] Hong, M., Wang, X., Razaviyayn, M., and Luo. Z. Iteration complexity analysis of block coordinate descent methods, 2017.

Theoretical comparison to baselines:

Analysis under strong convexity-like assumption. Under the bounded delay assumption in our paper, the convergence rate of DAve-RPG is $((L-\mu)/(L + \mu))^{2/(\tau+1)}.$ Our rate is $(L/(L+\mu))^{1/(\tau+1)}.$ If we consider fixed step-size for PIAG and assume $L\ge 2\mu$, then the linear rate of PIAG becomes $e^{-\frac{3\mu}{26L(\tau+1)}} \approx 1-\frac{3\mu}{26L(\tau+1)}.$

The first two rates are for the same merit function (squared Euclidean distance to the optimal solution), and the third rate is in terms of the function value gap.

These rates are of the same order with respect to $\tau$ and $\mu/(L+\mu)$, but the rate of DAve-RPG is the best. It is natural that our rate is not as sharp as DAve-RPG's rate, since we considered a much more complex algorithmic setting which makes the analysis more challenging and looser. On the other hand, in the numerical experiments, our method outperforms DAve-RPG.

Analysis under convexity. For all three methods, convergence can be guaranteed for general convex problems (note that the DAve-RPG paper has a SIAM Optimization extension [2] discussing convergence for convex functions without assuming strong convexity.) The work on PIAG derived $\mathcal{O}(1/k)$ rate on the function value gap $F(x_k)-F(x^\star)$, the work on DAve-RPG derived $\min_{t\le k} ||g_t||^2\le O(1/k)$ for $g_t\in \partial F(x^k),$ and our new convergence result is of the form $\min_{t\le k} F(x_t)-F^\star\le \mathcal{O}(1/k).$ All these rates are similar.

We should point out that, unlike the work on PIAG and DAve-RPG, our analysis covers stochastic gradients.

[2] Mishchenko, K., Iutzeler, F., Malick, J. A distributed flexible delay-tolerant proximal gradient algorithm, 2020.

Scalability: We have commented on your concern on scalability in the official comment section above.

Relationship between bundle size and maximum delay bound: The bundle size $m$ does not affect the maximum delay bound $\tau$. Note that $\tau$ is a bound on the delay of the most recent query point for each worker (see Assumption 4.1 in the paper). For example, if $m = \infty$ (meaning all previous gradient information is retained in the objective function approximation) and each node provides an update at least every 10th iteration, then $\tau = 10$.

Limitation of third assumption in Assumption 4.9: The assumption on the function value noise is not restrictive because 1) the bound is specified in expectation, meaning that the inequality does not need to hold uniformly, and 2) the noise is required to be bounded only at optimal solutions, rather than throughout the entire space.

Thank you for your excellent feedback. Is there anything else we can clarify? We hope that our answers have addressed your concerns, and that you are willing to consider raising your score.

The reviewer thank the authors for their efforts in clarifying and updating the results in the manuscript. The author's reply have addressed most of my comments and questions. I have no further questions and I am thus willing to raise my score to 6.