An Asynchronous Bundle Method for Distributed Learning Problems

Authors: Daniel Cederberg, Xuyang Wu, Stephen P. Boyd, Mikael Johansson
Primary area: optimization
Keywords: Distributed optimization; asynchronous optimization; model-based optimization

Abstract:
We propose a novel asynchronous bundle method to solve distributed learning problems. Compared to existing asynchronous methods, our algorithm computes the next iterate based on a more accurate approximation of the objective function and does not require any prior  information about the maximal information delay in the system. This makes the proposed method fast and easy to tune. We prove that the algorithm converges in both deterministic and stochastic (mini-batch) settings, and quantify how the convergence times depend on the level of asynchrony. The practical advantages of our method are illustrated through numerical experiments on classification problems of varying complexities and scales.

Decision: accept (poster)
Reviewer scores: 6, 8, 6, 8

Reviews and discussion:
<thread>
creation date:
1729309606176

thread_type:
official_review

<thread_object>
creator: reviewer_4dtz

<content>
summary:
The paper presents a bundle method for asynchronous distributed optimization. By increasing the server-side complexity, it boosts the performance. The algorithm operates under unknown (bounded) delays, while favorable is the effort for automated parameter tuning.

strengths:
+ Useful algorithmic contributions (especially embodying parameter auto-tuning).
+ Rigorous analysis (incorporating cases of practical interest such as inexact server solutions and mini-batch processing).
+ Well-written and clear paper (especially commendable is that the authors provide insights for all choices as well as their analysis).
+ Rich, well-presented, and convincing experiments.

weaknesses:
- Dubious scalability in large systems ($n \gg 1$).

Others--outweighed by the strengths--are that the contribution is an extension of previous works and that the code is not presently shared.

questions:
Questions:

1. Your analysis in (7) applies across a subsequence ($\exists k\ge K$). Can this be strengthened? For example, can you make assertions for the convergence of $\min_{j\le k} \{F(x_j) - F(x^\star)\}$? How does it compare with the literature?
Can you also comment on the reason for the discrepancy between (7) and (8) in terms of the same (the latter applies $\forall k$).
2. Can you include the adaptive tuning aspect ($\hat{L}_i$) in the analysis, or provide a remark sketching the same?
3. Can you please comment on means to boost scalability in large systems ($n \gg 1$)?


Suggestions:

- Please include the cost of solving the master problem ($O(nmd)$) in the main paper. 
- Can you rephrase the statement in lines 362-365? It seems a bit sloppy for your fluent presentation style. 
- Please explain the reasoning in line 458 (why in this case the master problem is more challenging).
- Please elaborate on "potentially discarding outdated information" in line 532 (in relation to dynamic bundle size selection).

Editing:

- line 55: "insensitive" does not seem accurate and can be misleading; please rephrase.
- line 88: counterpart -> counterparts.
- lines 108-111: please rephrase to prevent any misperception of a contradictory statement (gradients provide local; in contrast, gradients provide global).
- I suggest numbering the equation in line 207. 
- line 256: the central server for each worker $i$ -> each worker $i$ (to prevent any confusion that the server has access to user data).
- line 295: delete "weak".
- line 314: rephrase "gracefully".
- line 490: no tuning -> no tuning in these experiments (to avoid overstating).
</content>
</thread_object>

</thread>
<thread>
creation date:
1730193400867

thread_type:
official_review

<thread_object>
creator: reviewer_klum

<content>
summary:
The manuscript describes a asynchronous bundle method for distributed optimization. The results are presented well and the manuscript is well-written and clear. However, I have the following concerns that somehow limit the scope of the results.

1) Novelty
 
Bundle methods have been around for quite some time and have been also around in the machine learning community, since the 2000s (there is e.g. a well-cited paper by A. Smola). Similarly, the fact that bundle methods can be used for asynchronous parallel optimization has also been discussed several years ago (around the 2010s). Hence, the conceptual novelty of the work is very limited. 

On the technical side, early works seem to have focused on non-smooth optimization (which arguably is also the setting where bundle methods are very adequate for), while the current work looks at (essentially) strongly convex composite objectives that have a smooth and non-smooth part. In contrast to earlier results, the manuscript claims sublinear/linear convergence to a neighborhood of the solution (8). However, the current statement of Theorem 4.5/Theorem 4.10 does not prove linear/sublinear convergence of the iterates, but rather for a subsequence of the iterates. 
As such, the theorems do still allow for an arbitrarily slow convergence of the iterates (the variable k can be arbitrarily large). The usefulness of deriving a convergence rate for the subsequence is unclear to me, unless this is used as an intermediate step to argue that the entire sequence converges at the given rate (which is not done).


2) Experimental evaluation

The experiments are limited and consist of (regularized) logistic regression with only a very small set of workers (n=9). This does not seem convincing to a machine learning audience for two reasons: i) the community would be interested in deploying the method at scale (meaning several 1000 workers). ii) the community would likely use more elaborate models (NNs, transformers, etc) for classification. 
Can the authors argue about scalability of the method with respect to the number of workers? How does the method empirically perform on nonconvex problems?

--

Minor questions, discussion:
- Can the authors comment on the role of the variable "m" in the convergence results Theorem 4.5/Theorem 4.10? As far as I see, the variable doesn't play a role in the results.

- Is there a good way to reduce the memory overhead? As is, the central server needs to store O(mn) gradients, where n denotes the number of workers. This seems really impractical for large scale problem instances.

strengths:
see above

weaknesses:
see above

questions:
see above
</content>
</thread_object>

</thread>
<thread>
creation date:
1730639493016

thread_type:
official_review

<thread_object>
creator: reviewer_zz8s

<content>
summary:
The authors propose a new asynchronous optimization method for solving distributed convex problems. The proposed method approximates each local function using a piece-linear model constructed from a fixed-window of past updates. The main advantage of the proposed method is that it does not assume a maximum time delay and takes performs regularization at the server. The experiments demonstrate the effectiveness of the bundle method in asynchronous settings and interestingly shows a significant improvement over standard approaches.

strengths:
The authors provide a strong argument for their methodology. It seems intuitive that using past updates can help estimate the local function

weaknesses:
The reviewer wonders if the authors can provide more detail on how the weighting is chosen. It seems that the weighting should be chosen also based on the time-delay

questions:
The reviewer wonders if the authors can comment if this applies to settings where each worker has an individual time-dela, $\tau$.
</content>
</thread_object>

</thread>
<thread>
creation date:
1730772995963

thread_type:
official_review

<thread_object>
creator: reviewer_nxcg

<content>
summary:
The authors in this paper propose an asynchronous bundle method to solve distributed learning problems with parameter server architecture. The algorithm constructs a piecewise linear model to approximate the local loss of each worker and uses this model to compute the next iterate. This method enjoys a more accurate approximation of the objective function, compared to other first-order asynchronous algorithms. The authors prove that their algorithm can converge to a neighborhood of the solution for both deterministic and stochastic settings. In addtion, they show how the convergence results depend on several key parameters, such as upper delay bound $\tau$, approximation error $\delta$ and noise variance $\sigama_1^2, \sigama_2^2$. They also report some numerical simulations to validate the effectiveness of their proposed algorithm.

strengths:
- The proposed algorithm seems novel to the reviewer, and is fast and easy to tune in practice.
- The authors provide convergence guarantee for their algorithm and clearly show that how some key parameters (e.g., $\tau$, $\delta$, $\sigma_1^2$, $\sigma_2^2$) affect the convergence rate and steady error term.
- The paper is clearly structured and seems technically correct.

weaknesses:
- There are no proper comparisons of theoretical results of the baseline algorithms: i.e., to DAve-RPG[1] and PIAG [2].
- The data heterogeneity analysis is missing. It is unclear how the proposed algorithm will perform in the case of strong data heterogeneity  in the numerical experiments.
- The scalability of the proposed algorithm is not well addreesed; note that only a system with 9 workers is considered in the numerical experiments. 

[1] Konstantin Mishchenko, Franck Iutzeler, Jer´ome Malick, and Massih-Reza Amini. A Delay-tolerant Proximal-Gradient Algorithm for Distributed Learning. Proceedings of the 35th International Conference on Machine Learning, 2018.

[2] Xuyang Wu, Sindri Magnusson, Hamid Reza Feyzmahdavian, and Mikael Johansson. Delay-Adaptive Step-sizes for Asynchronous Learning. Proceedings of the 39th International Conference on Machine Learning, 2022.

questions:
- The reviewer would like to know how their algorithm improves the complexity compaerd to the baselines DAve-RPG[1] and PIAG [2].
- How can the upper bound of delay $\tau$ be guaranteed by setting bundle size $m$ in their practical experients, or in ther words, how is the value of $\tau$ related to the value of $m$ in practice?
-  How does the proposed algorithm scale in terms of the node number? Can the authors provide some numerical experiments to illustrate this?
- What’s the limitation of the third one in Assumption 4.9?
</content>
</thread_object>

</thread>
<thread>
creation date:
1732398848871

thread_type:
official_comment

<thread_object>
creator: authors

<content>
title:
A comment on convergence and scalability

comment:
We thank the reviewers for their thoughtful feedback and valuable suggestions. We appreciate their careful evaluation of our work and agree with many of the concerns they have raised. We have modified our manuscript and addressed these points in detail below on a reviewer-specific basis. Additionally, we would like to make a general comment on a new convergence result we have derived and also on the scalability of our method.

**Comment on convergence result:** Two reviewers essentially asked for a stronger convergence result for the case where we don't assume the quadratic functional growth assumption. We are happy to announce that we have been able to derive a novel sequence result that allows us strengthen the analysis significantly. We now prove that the function value gap decreases at a rate $\mathcal{O}(1/k)$ (see Lemma 4.8 and Theorem 4.9 in our modified manuscript). 

**Comment on scalability:** We thank the reviewers for raising concerns about the scalability of our algorithm. Scalability is indeed a critical aspect of modern optimization techniques, particularly in Federated learning (FL) and other large-scale distributed settings. Below, we address the scalability challenges and clarify the contexts in which our algorithm excels.

 * Federated learning is used in diverse scenarios, from coordination of massive networks of resource-constrained devices (cross-device FL) to collaborative model training across data-rich institutions (cross-silo FL). It is unlikely that there is a single algorithm that is superior in all scenarios. Different contexts face different challenges and require systems optimized for different performance measures: some prioritize training speed and parallelization, while others focus on robustness and ease of deployment. Our algorithm, at least in its present form, caters more to the cross-silo setting, where it allows for fully asynchronous implementations without manual tuning, and often gives faster training than alternatives.
 * In large-scale distributed training environments with a modest number of computer nodes, each node being equipped with multiple GPUs, it is natural to treat each *node* as a worker. In a training environment like this, it is reasonable to have a couple of tens of nodes or workers, rather than in the order of thousands. Our algorithm is particularly well-suited for this distributed setup, since each worker can fully exploit its available hardware, leveraging as much parallelism as possible, to evaluate its gradient. Additionally, the asynchronous nature of our algorithm ensures that the performance of one node remains unaffected by latency or delays in others, enabling robust training.
 * A potential computational bottleneck of our algorithm, compared to other asynchronous methods, is solving the subproblem at the server. However, in many cross-silo applications, the server has significant computational power. For example, we collaborate with a medical equipment manufacturer that uses federated learning to perform training on data drawn from installations at different sites. In their current solution, the server uses a fast multi-core CPU and constitutes only a small fraction of the overall system cost.
    
   The main cost of solving the subproblem is evaluating the gradient of the dual objective function (cf. equation (11) in the paper), which is done using matrix-vector multiplication. This can be parallelized effectively with a GPU if solving the subproblem, rather than the communication between the server and the workers, is the computational bottleneck. To further reduce the workload at the server, the bundle size $m$ can be adjusted adaptively. Notably, when $m = 1$, the subproblem has a closed-form solution.

   Furthermore, although we may not have time during the rebuttal period to conduct additional experiments to investigate the empirical performance further, we can provide quantitative insights based on our current experiments and the theoretical cost of solving the subproblem, which is $\mathcal{O}(mnd)$ where $d$ is the dimension of the decision variable, $n$ is the number of workers, and $m$ is the bundle size. For example, for the dataset *epsilon*, our Python implementation of the subproblem solver running on a single CPU takes on average 0.027 seconds for $n = 9$ workers (see appendix A.3 in the manuscript). Given the linear scaling in the number of workers, we could scale up to 300 workers and still be able to solve the subproblem in a second.  
    
We acknowledge the reviewers' concerns regarding scalability and recognize the importance of addressing these challenges in large-scale settings. We hope our detailed discussion above clarifies the contexts where our algorithm excels and sheds light on its potential for scaling effectively.

**We sincerely thank the reviewers for their thorough evaluation of our paper and for considering our rebuttal when assigning their final scores.**

Best regards,
The authors
</content>
</thread_object>

</thread>


Metareview:
metareview:
The paper has proposed a novel algorithm with strong convergence guarantees. I concur with the positive evaluation of the reviewers. Recommend accept.