An Asynchronous Bundle Method for Distributed Learning Problems
Authors: Daniel Cederberg
Xuyang Wu
Stephen P. Boyd
Mikael Johansson
Venue: ICLR 2025 Poster (2025)
Keywords: Distributed optimization; asynchronous optimization; model-based optimization
Primary area: 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.

Published as a conference paper at ICLR 2025
AN ASYNCHRONOUS BUNDLE METHOD FOR DISTRIBUTED LEARNING PROBLEMS
Daniel Cederberg Stanford University, USA
Xuyang Wu SUSTech, China
Stephen Boyd Stanford University, USA
Mikael Johansson KTH, Sweden
ABSTRACT
We propose novel asynchronous bundle method for solving distributed learning problems. Compared to several existing asynchronous optimization algorithms, our method computes the next iterate based on 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 rates 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.
INTRODUCTION
We consider a setting where data is distributed among n workers, each with its own smooth convex loss function f Rd Our goal compute a solution x² of
minimize F(x) A f(x) + R(x),
where f(x) Σi= -i=1 f((x) and R R + R is (possibly non-smooth) proper closed and convex regularizer. This problem template is ubiquitous in machine learning and includes lasso [Tibshirani] 1996), logistic regression (Koh et al.) 2007), and many other important problem classes.
When data is distributed among multiple workers, algorithms that require synchronization every iteration are limited by the slowest worker, creating bottleneck. Asynchronous algorithms (Bert- sekas & Tsitsiklis 1989 Assran et al. 2020) address this issue by relaxing synchronization con- straints, potentially resulting in machine learning systems that are both faster and easier to imple- ment than their synchronous counterparts (Hannah & Yin 2017). However, designing asynchronous algorithms is challenging because information computed at the workers such function values and gradients - may be obsolete by the time it reaches some coordinating mechanism like a cen- tral server. As result, convergence guarantees for asynchronous algorithms often rely bound on the information delay from the workers, which is typically large and difficult to determine. Moreover, the step sizes permitted by these guarantees tend shrink quickly as the delay bound increases. This complicates the implementation of asynchronous algorithms: if the estimated delay bound is too small, may not hold, invalidating the theoretical convergence guarantees. Conversely, setting the bound too large results in overly conservative step sizes and slow practical convergence.
upper
The design of most optimization algorithms relies on simple approximation of the objective func- tion - often referred to as a model in the optimization literature. For example, gradient descent based on the quadratic upper bound of an L-smooth convex function, while the Polyak step size (Polyak) 1964) relies a piecewise linear lower bound for a convex function with a known optimal value. However, a string of recent papers on synchronous algorithms (Davis Drusvy- atskiy 2019; Asi & Duchi 2019; Nesterov & Florea 2021) suggests that using more accurate approximation of the objective to compute the next iterate can improve performance. This naturally leads to the question of whether asynchronous algorithms could also benefit from more accurate ap- proximations of the objective, potentially resulting in asynchronous algorithms with faster practical convergence and simpler tuning.
Contributions. We propose a parallel and asynchronous optimization method that leverages a more accurate approximation of the objective function to compute the next iterate. The method is de-

---

Published as a conference paper at ICLR 2025
signed for parameter server architecture (Li et al. 2013) and decouples gradient evaluations at the workers from decision vector updates at the master, making it robust to system asynchrony. On the theoretical side, we prove that our algorithm converges for all bounded delays and can be im- plemented without knowledge of the maximum delay. (We only know of two other asynchronous algorithms (Mishchenko et al. 2018 Wu et al.] 2022) that are designed for parameter server and share these properties while also explicitly taking the regularizer R(z) into account.) On the practi- cal side, we present an algorithm that converges quickly with minimal tuning. Our method supports stochastic function and gradient evaluations and can be viewed as an asynchronous bundle method, generalizing algorithms in Nesterov & Florea (202T) and Asi & Duchi (2019) an asynchronous setting.
The paper is structured as follows. In 2 we relate our contribution to existing work. In $3 we introduce our asynchronous model-based algorithm, followed by convergence analysis Implementation details and numerical experiments are presented in [nd $6 respectively.
Outline.
in $4
Finally, we summarize our findings and conclude in 7
2 RELATED WORK
Model-based optimization. Model-based optimization is general framework in which an ap- proximation, or model, of the objective funetion is maintained and used to compute the next it- erate. This framework encompasses several well-known methods and principles, including the expectation-maximizzn
algorithm (Dempster et al.) 1977: Neal & Hinton 1998), quasi-Newton methods (Dennis & Moré 1977,, bundle methods (Mäkelä 2002), the majorization- minittiioiimnniiatioonn principle (Mairal 2015] Lange 2016), and acceleration techniques (d' Asppemontt et al., 2021). In stochastic optimization, recent research has shown that using more accurate approximations of the objective function can improve both speed and robustness to step size selection (Duchi & Ruan 2018 Davis & Drusvyatskiy 2019 Asi & Duchi 2019). For composite non-stochastic optimiza- tion. Nesterov & Florea (2021) recently demonstrated that constructing a piecewise linear model of the smooth part of the objective rather than relying solely on the most recent gradient to approx- imate the smooth part- - can lead to better performance. Our work aims to extend the idea of more accurate objective function models to asynchronous optimization.
Parallel and asynchronous optimization. For parallel optimization with a parameter server archi- tecture, asynchronous algorithms can significantly outperform their synchronous counterparts (Han- nah & Yin | 2017). They have also shown promising results for other architectures (Recht et al. 2011 Chaturapruek et al. 2015). Many asynchronous methods use diminishing step sizes (Duchi et al,,
2015 Assran & Rabbat 2020) or rely on a predetermined maximum iteration number (Koloskova ctt al. 2022 Mishchenko et al. 2022; Recht et al. 2011). Exceptions that are well-suited for pa- rameter server generally fall into two categories: (I) methods that require knowledge of upper
bound on information delays (Zhang & Kwok 2014 Peng et al., 2016 Gürbüzbalaban et al. 2017] Vanli et al. [2018] Wai al.] |020]] Sun et al. (219)) and (2) algorithms that do not rely such a bound (Feyzmahdavian et al. 2014]] 4: Mishchenko et al. 2018 2020 Wu et al., 2022 (023). In practice, however, an upper bound on the information delay is often unknown in advance. Since the admissible step sizes shrink as the upper delay bound increases, it is often difficult to guarantee that the algorithms in the first group converge practice.
Most of the asynchronous methods above perform simple, closed-form updates at the central server, while the bulk of the computational work (such as gradient and function evaluations) is offloaded to the workers. The reason for the cheap update at the central server is, using the terminology of masel-based optimization, that the server maintains a simple model of the objective function based only on the mos! recent information from each worker. Our approach differs in that we propose using a more accurate model of the objective function - one that incorporates more than just the latest information from each worker. The fact that computationally intensive tasks are handled by the workers suggests an opportunity to investigate algorithms that are slightly more complex at the server, like the one propose, to potentially improve the overall system performance.
Bundle methods. A key challenge in asynchronous optimization is that gradients provide local descent directions, making it challenging to combine gradients from different workers computed at different iterates into a meaningful search direction that ensures descent. In contrast, gradients (together with function values and convexity) provide global lower bounds the objective func-
2

---

Published as a conference paper at ICLR 2025
tion, making it easier to combine gradients evaluated at widely different points into a valid lower bound of the objective function. This observation motivates our method, which can be viewed as an asynchronous bundle method.
In the non-smooth optimization literature, several versions of asynchronous bundle methods have been proposed (Emiel & Sagastizábal 2010; Tutzeler al., 2020 van Ackooij & Frangioni 2018 de Oliveira & Eckstein (201)) Since non-smooth optimization covers a wide range of problems, the convergence results for existing asynchronous bundle methods are generally weak. (For ex- ample, a typical convergence result is that any cluster point of the iteration sequence solves the problem (Emiel& & Sagastizábal 2010, Proposition 4).) However. our setting this paper is differ- ent. While the aforementioned works assume that the non-smoothness of the objective is present in the finite-sum structure, we assume that the finite-sum structure arises in a smooth part of the objective, and the non-smoothness of the objective is caused by a regularizer. This key distinction allows us to derive much stronger convergence guarantees - not only do we prove convergence, but we also derive convergence rates (see Theorem 4.5 and Theorem 4.9)
and
Bundle methods have also received direct attention from the machine learning community (Teo et al. 2007; |Fannc& & Sönnenburg, 2009. Teo et al.] 2010) Chu et al. 2017 Paren et al. 2022). The first three works design variants of bundle methods for general empirical risk minimization, but they differ from our method in several ways. (For example, these methods maintain a piecewise linear model of the sum f f= Ei= fa. whereas our algorithm maintains separate piecewise linear models for each fi- Furthermore, unlike our method, these methods require the workers to synchronize in every iteration.) Bundle methods have also been successfully applied to non-convex problems (see, for example. Hare& & Sagastizábal (2010)). In particular, the special case of the Polyak step size, where the bundle only consists of the current cut and a lower bound on the objective, has proven to yield strong performance in deep neural network training (Loizou et al. 2021 Wang et al. 2023a).
ALGORITHM
In this section we present model-hased algorithm for solving ( asynchronously. We use a param- eter server architecture (Li et al.) 2013) with one central server and n workers. The central server maintains a copy of the global decision variable and can query each worker for its function value and gradient. Based on this information, the central server builds up a piecewise linear model of each worker's s loss function, and then uses this model to compute the next iterate. A notable feature of the algorithm is that its implementation does not require knowledge of an upper bound on the information delay.
3.1 MAIN IDEA
To simplify the presentation the method we consider a fixed iteration and drop the iteration index. We assume that the iteration number is sufficiently large to ensure that the central server has received information from each worker in at least m previous iterates. The parameter m is referred to as the bundle size. For i E {1....,n] n) we introduce an algorithmic parameter M, > 0 which, roughly speaking, represents the smoothness parameter of worker and we let M A Σ M; (An exact definition of M; is given in $4) We will later show that in practical implementation of our method, the parameters M,, I...., n are estimated adaptively and require no tuning.
Let =} for j = 1,..., ,n denote the m previous iterates in which the central server has received information from worker i. We label the iterates so that =jn is the most recent iterate for which the central server has received information from worker i, and let z & M E.= M,2 denote weighted average of these points. The server maintains the following piecewise linear model of f::
f((z) = max (f(()) + (Vf(()), - 2/)}. 15/5m
(2)
When the server receives information from one or several workers, it replaces the oldest iterate in the bundle for those workers. The next iterate is then computed as approximate solution of
Σ f((x) + R(x) +
M >| 2
minimize
(3)
3

---

Published as a conference paper at ICLR 2025
(We will later specify what mean by approximate solution.) Note in particular that the bundle center in (3) is chosen as a weighted average of the most recent iterates for the workers; this is essential for the convergence analysis in $
In our method, the central server must store m gradients of size d for all n workers, resulting in total memory complexity of order (mnd).. This is more than the ((d)) memory required by methods that only store the most recent gradient of each worker, but often substantially less than the (df) requirement of methods such (Soori et al. 2020) that store approximation of the Hessian at the central server.
3.2 SOLVING THE MASTER PROBLEM
In every iteration the central server must solve the master problem 3 which for common regu- larizers such R(x)= A||a=|| can be formulated as quadratic program with linear inequality constraints. If the dimension is large, solving (3) can become a computational bottleneck. How- when an aggregated piecewise linear model of the objective function is used and R(x) 0, is well known that the dual of (3) is a low-dimensional quadratic program over the probability simplex (see, for example, (HiriartUrruuty & Lemarechal 1993] p. 296)). As the following lemma shows, a similar observation can be made when a disaggregated piecewise linear model of f is used and when R(x) * 0. To state the lemma we define matrices G; E Rdxm containing old gradient information of fa by
G, = [(((z)
[[((=)))
For 1, n, let va RD be defined componentwise by (v:); (V)(( fi(=f) and let (#1..... Ux) Rm Recall that for y the Moreau envelope of R and the proximal operator of R are defined by
(R(v) = min R(x) + 27
100 JlBi.. prox,R(U) = arg min R(x) + 2
11 - y
24
Lemma 3.1. Let A E R" i 1,...., n and = (A1....,AAa) A,)) E Rm Define Rm - R by
M || M Σ
GAlll H!M : M
n G.NL) + (v,
2(A)
2
The Lagrange dual of
3 is given by
minimize
g( 1º>;
(4)
subject to
=
2,
1=
Furthermore, if X is optimal in 4. then the unique solution of 3
denoted by Fexees is given by
1 1 Σ
n
Texact = prox d R
G.
(5)
M
Proof. The proofs of this and all forthcoming results are given in the appendix.
3.3 AN EFFICIENT APPROXIMATE MASTER PROBLEM SOLVER
solve the master problem 3 by solving its low-dimensional dual ( However, even the dual is dimesimnniinna,, it can be too expensive to solve it to high accuracy since the second term in the definition of the dual objective function itself involves minimization problem in x. Therefore, in our algorithm, we only generate approximate solutions to (3) using inexact solutions to 4p. The goal of this subsection
According to Lemma 3.1
introduce equation (6) below, which defines a termination criterion that we use to specify what we mean by an inexact solution.
Denote the feasible set of (4 by A C mM The dual objective function g is differentiable since the Moreau envelope is differentiable. Hence, from optimality conditions for convex optimization (see, for example, (Nesterov] 2018 p. 177)), X solves (4 if and only if
(Vg(A*), X) < for all X A.

---

Published as a conference paper at ICLR 2025
Algorithm 1
Setup: parameters M,, bundle size m, tolerance 5 0 Initialization: the central server receives fe( and (ar) i ,,..,, while not interrupted by central server: each worker i do
receive æ from the server, compute fi(z) and Vz)( and send them back to the server end while
while not converged: central server do for = ...... n. do
if received information from worker i then update the bundle of worker i by throwing out the oldest information end if end for
compute À satisfying 6 and then update according to send back x all workers that the server received information from end while
As in Nesterov & Florea (2021), allow for inexact solution of (4) by introducing parameter
> 0 together with the requirement that we compute point satistying
(Vg(A), - A\ s for all E A.
(6)
The next iterate, denoted by x., is then computed as (cf.
5
1 1
n
G.A.
z+ prox t n
&
M
summary of the algorithm we propose given in Algorithm
Implementation details, including
how to find À satisfying (6), are given in $5
3.4 EXTENSION TO STOCHASTTIC FUNCTION VALUES AND GRADIENTS
While the main focus of this paper is the setting where exact (full batch) function and gradient eval- uations used, will also analyze variant that uses stochastic (mini-batch) function values and gradients. For this setting we assume that each worker E .,. has access to an oracle that when queried point v, draws random variable & from some distribution and outputs both stochastic function value (2;x)) approximating fi(x), and a stochastic gradient (z; {) approxi- mating V (z). In this stochastic setting, the central server replaces the piecewise linear model (2) of fa with the following stochastic piecewise linear model:
f((
(F((e):)) + x 15/5m
max
Here E/ is the random variable from the query of the oracle of worker in the point z)., and the bold & represents all randomness used to construct the current bundle.
4 CONVERGENCE ANALYSIS
In this section we study the convergence of Algorithm D and its stochastic extension. Our main results are Theorem 4.5 and Theorem 4.9 showing that the algorithm converges to a neighborhood of an optimal solution whose size depends on the accuracy used to solve the master problem. They also characterize how the information delay affects the convergence rate. The convergence analysis uses two sequences of points: the sequence of iterates Ig for E Z+ - {0, 20.., and the sequence of points =k., for k E Z4, E (1,..., n) and E (1.....m) m} used to construct the piecewise linear model of fs in iteration k. (These points are previous iterates, i.e., for (k, E Z, x (I,...,,.) m) {I,..., m) there exists a non-negative integer si. < k such that 2 = 2 "
We will assume that the points labeled such that = denotes the most recent iterate in which the central server has received information from worker i in iteration k. With this convention, the
5

---

Published as a conference paper at ICLR 2025
quantity i: -- sk
is called the delay of worker in iteration k. Our first assumption is standard Feyzmahdavian et al. (2014); Gürbüzbalaban et al. (017); Vanli et al. (2018);
(see, for example. Mishchenko et al.
2018)) and states that the maximum delay is bounded by an integer 2
Assumption 4.1. In every iteration & the delay of worker i is bounded by In other words, for (k, E 2+ x nI....,n) it holds that k - sk ST. T.
We will also make the following standard assumption on the objective function. Assumption 4.2. The loss function of worker E (1....,n) smooth with parameter L4-
Occasionally we will further make the following common growth assumption that similar to, but weaker, than strong convexity (see, for example, Necoara et al. (2019)).
Assumption 4.3. The full objective function F has a quadratic functional growth with parameter > O, meaning that F(x) F(x*)= z (n/2)][æ - x= 11 for all x E R
4.1 ANALYSIS FOR EXACT FUNCTION VALUES AND GRADIENTS
We now present a convergence analysis when exact (non-stochastic) function values and gradients are used. First we need an additional assumption.
Assumption 4.4. The loss function fi of worker i E {1,...,n] is star-convex, meaning that fi(x*) 2 (x) + (V)(r), - x) for all x E Rd.
Under the growth assumption we can show linear convergence to neighborhood of solution.
Theorem 4.5. Under Assumptions 4.1
4.2
4.3
and
4.4
the iterates of Algorithm using M;
L, = I,...,n nastisf
Iatk x=
112
S p² 1100
x=13 +
(
where p (I/(L. + (1)) and cs 28/uu
Remark 4.6. notable feature of our algorithm that neither its implementation nor its tuning requires any information about the level of asynchrony in the system. The method converges with default parameters as long as the information delay from all workers are finite, and under Assump- tion the convergence rate decreases the level of asynchrony in the system increases.
Remark 4.7. Rather than relying on the common yet unrealistic assumption of solving the sub- problem (3) exactly, analysis explicitly accounts for and characterizes the impact of inexact subproblem solutions. As a result, an error term depending on å naturally appears the conver- gence result. However, should point out that in practice, the algorithm we propose has no issues with finding highly accurate solutions (see C
For the analysis without the growth assumption we will use the following new sequence result that might be of independent interest.
Lemma 4.8. Suppose that (Vx) and (W+) non-negative sequences satisfying
V8+1 S max StSk)
Ve Wk+1 +
k == 0, 1,
for a non-negative constant r. Then, any le 2 1,
(T+ 1)% +r.
min W. ISk
Using Lemma 4.8 we can prove sublinear convergence in terms of the function value gap.
Theorem 4.9. Under Assumptions 4.1 4.2 and
4.4 the iterates of Algorithm Jusing M, = Li, =
1,... satisfy that for any 1,
min F(x.) - F(x*) (T + 1)Ll t
xx 11 8.
2k
Table compares the convergence rates of our method (with 6 0) against two asynchronous prox-
imal gradient methods: DAve-RPG (Mishchenko et al. 2018
2020 and PTAG with delay-tracking

---

Published as a conference paper at ICLR 2025
(Wu et al. 2022), under the assumptions used in this paper. These methods operate under the same conditions as ours that they rely on a parameter server, do not require explicit maximum delay in- formation in their parameters, and explicitly incorporate the regularizer. The comparison shows that all three methods achieve similar convergence rates under standard convexity assumptions. How- ever, in the strong convexity-like setting, DAve-RPa RPG exhibits the fastest rate. This is expected as our method is more complex, making the analysis more challenging and leading to looser bound.
Assumptions
DAve-PPG
Delay-tracking PIAG
Algorithm
General convexity
minigA |s: 0(1kk)
F( F(z)) 01/1))
millaga F(x)) F(x") 0(1/3)
Strong convexity-like
1xp
Pfl x'l; F(xe) F(x") (1F(())) F(a")
12x x 11 All 2'13
Table I: Comparison of convergence guarantees under different assumptions, Here pt ((L (L ())3/rt)) = (/99((++))))) v 51(7+ and P3 = =L/(L+ (L/(++i))
-
4.2 ANALYSIS FOR STOCHASTIC FUNCTION VALUES AND GRADIENTS
When stochastic function values and gradients are used we will make the following assumptions. Assumption 4.10. For each worker i E f1,....,}}
1. The oracle is star-convex, i.e., ; (((x;) (G:(1;)), -x) for all Rd. Furthermore, EIF((z, <)] fx) and [zG E) V(())) for all E R
2. The variance of the stochastic gradients is bounded by some finite constant o3 > 0, mean- ing that (x, <) (x) S oî for æ E Rd.
3. The function value noise at the optimal solution xt is bounded by some finite constant of O, meaning that (x f((x))) S of.
Relation previous assumptions in the literature. The second assumption bounding the noise of the gradients is common in the analysis stochastic algorithms (see, for example, Koloskova et al. (2022); Mishchenko al. (2022)) ) The third assumption is less common, since most algorithms often only use stochastic gradients and not function values. However, recent analysis of stochastic algorithms that use stochastic function values addition to stochastic gradients make similar assumption (see, for example, Loizou et al. (2021); Wang et al. (2023b)).
Theorem 4.11. Consider Algorithm | with M, = aLi, = 1...., where > 1. Assume that stochastic function values and gradients are used. Under Assumptions 4.1 4.2 and 4.14.11 the iterates of Algorithm satisfy that for any k 2 1,
min EiF()] F(x*) < a(T + 1)
roll
+
(9)
2k
where e EB + Cor + Co. with
a
= 6,
Eo1 = no mm,
2(a
L
1=1
If. in addition, Assumption 4.3 holds, then
E Ell x
p 1a2 +112++22111 26/U.
where p = (aL/(aL + /(4+))
Remark 4.12. Compared to algorithms with a simple explicit update rule of the form Tx+1 prox. (T + yyd)) where da is direction and is a step size, the update mechanism of Algorithm iss more implicit since it involves solving the dual subproblem 4 approximately. This makes the analysis challenging. One of the main technical challenges in the proof in the stochastic setting is to carefully manage correlations between recently queried gradients G, (2)),, the dual variable X, and the next iterate 1 all of which correlated random variables.
7

---

Published as a conference paper at ICLR 2025
Remark 4.13. The size of the neighborhood of the solution that za converges in expectation depends on three terms: one term Eg which depends on the accuracy 6, and two other terms 6o, and Cou which depend the strength of the noise. The noise terms coi and cr2 depend on n, which may seem uncommon. This dependency arises because we analyze the canonical form (() = Di=1 (a) instead of the more common form f(x) (1/n) En fi(x). Under the latter form, the noise terms would not depend on n.
5 IMPLEMENTATION
When implementing Algorithm | two issues must be addressed.
Solving the subproblem. First, we must find an approximate solution to (4 by finding À R satisfying (6). Since A is Cartesian product of simplices, it is cheap to verify condition (6) by
noting that
sup (Vg(1), (V)()).)) inf (Vg(A), - (Vg(A), Σ min V.g(A), AEA
DEA
where min V V.g(A) is the smallest element of (A). (Here V,g(A) is the gradient of with respect Aa.) To find À we have implemented an accelerated projected gradient method for solving (4) Beck 2017 page 291). Each iteration requires the gradient of and projecting onto the feasible set A. Since is a Cartesian product of low-dimensional simplices, the projection can be done efficiently (Condat) 2016). Furthermore, from properties of the Moreau-envelogee (Beck) 2017 p. 166) it follows that the gradient of g with respect A; is
Vig(A) = G. (u prox R(())) - G u + tu =u G prox + R(U),
(10)
where v = M Σm= G.A.
In the appendix we compare the cost of solving the subproblem using this specialized method versus a high-performance interior-ooin solver. The main conclusion is that this specialized approach is more than an order of magnitude faster and that the complexity for solving the subproblem of
order ((nmd).
Adaptive estimation of smoothness parameters. First-order methods for solving ① typically require knowledge of smoothness parameters. These parameters are often unknown expensive compute in practice. To eliminate the need for choosing a suitable value on L, in Algorithm we propose to estimate it adaptively using similar ideas to Malitsky & Mishchenko (2020).
Recall that V(((=))) is the most recent gradient that the central server has received from worker and let (f((2m-1) denote the next most recent gradient. Given 2/, Vfi(=,)) 2 and Vf(())))). a natural estimate of the local smoothness of fr is the quantity L, = [V fi 122/1/// - 1|2. Every time the central server receives a new gradient from worker i, propose update the smoothness parameter L, using this estimate.
EXPERIMENTS
We consider binary and multiclass classification problems based on logistic model. For the binary classification, we use the objective function f(x) = (I/N) E
j= (log(1 + ee ",, a)) + 2 11=)
and the regularizer R(x) A| where a1,... AN E R are the feature vectors and y1....,yN 11 are the corresponding labels. Due to the space limitations, we defer the results for multiclass classification to the appendix.
We conduct experiments on three datasets (mnist ftttssttmmiiiimiiiii LIBSVM library (Chang & Lin 2011) and the SVHN dataset (Netzer al. 2011). We pick Ag = 1/N, and tune x for each dataset to obtain a classifier x* with 10-20% non-zero entries. The dataset mnist 8m corresponds to a multiclass problem with 10 different labels. To use it for binary classification, we select data corresponding to the digits 7 and and discard the rest. Table 2 in Appendix A.4 shows shows the dimensions of each problem and the value of \₁-
epsilon, rev1) from the
8

---

Published as a conference paper at ICLR 2025
All methods evaluated central server and the remaining n = 9 cores are workers. The data is distributed evenly among the workers. The code is written in Python using MPI4PY (Dalcin & Fang 2021) and is available at https: /tpps://qiie http:////ttttt thub. com danncnnce dence hatAAsyychooooco ronooss-uuddl e me hod To evaluate the objective value and the gradients sparse linear algebra for rcvl.
workstation using 10 cores. One core is assigned the role as the
PyTorch (Paszke et al. 2019) for the dense datasets, and
6.1 BENCHMARKING
To benchmark asynchronous bundle method (ABM) we compare it with two asynchronous proxi- mal gradient methods, namely DAve RPG (Mishchenko et al. (0118) and P PIAG with delay-tracking Wu et al. 2022 We selected these methods since they operate under the same conditions ABM in the sense that they use a parameter server, require no maximum delay information in parameters, and explicitly incorporate the regularizer. Both DAve-RPS and P PIAG use exact gradients so also use exact function values and gradients for ARM.
bundle size For ARM DAve-RPG has two hyperparameters: the step size yy and the number of inner prox- estimation.
10, master problem tolerance 5 = 10-7, and adaptive smoothness
steps p. We use step size 7 = 1/ Livergge where Laverage the average smoothness parameter of the workers, and 1 inner prox-steps (as in Mishchenko et al. (2018)). For P PIG with delay-tracking we implemented the first adaptive step size strategy described in Wu al. (2022).
The first row of Figure shows the relative suboptimality see that ABM clearly outperforms the other two methods. The second row shows the suboptimality versus the number of gradients received by the server. We see that ABM achieves much higher accuracy with fewer gradients received by the server. For revl the difference is striking: in 300 seconds the central server in ABM receives about 4000 gradients, while the servers of DAve-RPG and PIAG receive more than 70000 gradients in the same amount of time. This is in contrast to mnist 8m and epsilon where all servers receive roughly the same number of gradients in the same amount time. The reason underlying this observation
- versus the runtime. We
that the gradients are cheap to compute for the sparse data set revl and more expensive to compute for the dense datasets (cf. Table 2 in Appendix A.4). Consequently, for revl, the time required to solve the subproblem at the central server is non-negligible compared to the time needed to evaluate gradients. In contrast, for the dense datasets, this computation time is almost negligible.
ABM
Milt
12.2
P46
1953
(064 -WP
15w- 1R1
35
Radee
Pa
13
17"
(00g) DP
12:4
10"
1550 470
1081
401
8200
1090
1990 20091 WES3 IREE NOOE 1990 7981 8il
300
420
.723
1000
1980 18709
Figure 1: The progress of ABM, DAve-RPG and PTAG on the binary classification problems. The datasets arranged in the order mni st st&m, revl and epsi 1 from the left.
6.2 SENSITIVITY TO HYPERPARAMETERS
Strictly speaking, ABM has two hyperparameters: the tolerance 8 and the bundle size We will now investigate the sensitivity the algorithm's 's performance to these parameters. The first row of 2 shows the progress of ABM for fixed 8 10-7 and bundle size {2, 5, 10). Increasing

---

Published as a conference paper at ICLR 2025
the bundle size from 2 to E (5, 10) results in much faster convergence for mnista 8m. Furthermore, ABM makes no progress with bundle size m = for revl and epsilon, but with bundle size m E {5, 10) the convergence is fast. This indicates the advantage of using more accurate approximation of the objective function for computing the next iterate. Next, we run ABM with fixed bundle size the second row of Figure 2 We see that ABM has good performance for all three values on 6. This experiment suggests that ABM essentially requires no tuning in these experiments: the values and 8 = 10- seem to work well. In particular, the performance of ABM is not as sensitive to its hyperparameters as, for example, stochastic gradient descent its step size.
10 and tolerance å (10-5, 10-7 10-9). The result is shown in
10
(0xg) - T1P
11:7
m-22
36"
17"
10
107
(052
27
26
230
25.
206
250
305
24 1.00 2.5
250
300
10c
255
25c
26
Figure 2: Sensitivity of ARM'S performance with respect to hyperparameters. The first row shows the performance for different bundle sizes m and fixed tolerance 8. The second row shows the per- formance for different tolerances and fixed bundle size. Each column corresponds to one dataset, and the columns arranged the order mni 8m, rcvl, epsilos lon.
6.3 FURTHER EXPERIMENTS
In the appendix conduct further experiments when À2 0, i.e., when the objective function is convex but not strongly convex, and we also conduct experiments on multiclass classification. The main conclusion is that ABM outperforms DAve-RPO RPG and PIAG with delay tracking (see Figure and in the appendix). We also test the stochastic version of ABM using mini-batches for multiclas- sification on the biggest data set mnis isttsto 8m. The experiment indicates that mini matchin can speed up ABM if only a modest accuracy is required (see Figure 5 the appendix).
DISCUSSION
We have presented asynchronous bundle method that is suitable for distributed learning problems. The algorithm constructs a piecewise linear model to approximate the local loss of each worker and uses this model compute the next iterate. Compared other first-order asynchronous algorithms, our proposed method employs more refined model of the objective function. This allows it to converge quickly practice with minimal tuning or specification of unknown constants.
Our method uses fixed bundle size. An interesting extension would be to design scheme that dy- namically adjusts the bundle size based on the actual delays, potentially discarding outdated function value information that hasn't 't been used recently in the server subproblem. (The jth linear approxi- mation f: is not used in the server subproblem if X; = 0, where A the solution of (4) Another extension could be to let the central server maintain low-rank approximation of the Hessian for each worker, enabling better approximation of the curvature of the loss function, and possibly faster convergence. We leave these extensions for future work.
10

---

Published as a conference paper at ICLR 2025
REFERENCES
Martin Skovgaard Andersen, Joachim Dahl, Zhang Liu, and Lieven Vandenberghe. Interior-point methods for large-scale cone programming. MIT Press, 2011. ISBN 9780262016469.
Hilal Asi and John C. Duchi. The importance of better models in stochastic optimization.
Proceedings of the National Academy of Sciences, 116(46):2224-22953) 2019. doi: 10.
1908018816
URL https: htop:://wwww.o www.wwww..aaocppm.mmmmcm........ org wttp:///...///..111000100
1908018116
By Mahmoud Assran, Arda Aytekin, Hamid Reza Feyzmahdavian, Mikael Johansson, and Michael G. Rabbat. Advances Asynchronous Parallel and Distributed Optimization. Pro- ceedings of the IEEE, 108(11):2013-200 2020. doi: 10. 1..10//PRC..2220.0006660
Mahmoud Assran and Michael G Rabbat. Asynchronous gradient push. IEEE Transactions on
Automatic Control, 66(1):168- 2020.
Amir Beck. First-Order Methods in Optimization. Society for Industrial and Applied Mathemattcs, Philadelphia, PA, 2017. doi: 10.1 17771 Utthttts:///ppbs siam. org/ .rrg
doi/abs/ 10. 111113771111111197999999
Dimitri Bertsekas and John N. Tsitsiklis. Parallel and Distributed Computation: Numerical Methods. Prentice-Hal Hall, Inc., USA, 1989. ISBN 0136487009.
Stephen Boyd and Lieven Vandenberghe. Convex Optimization. Cambridge University Press, March 2004. ISBN 0521833787.
Chih-Chume Chang and Chih-Jen Lin. LIBSVM: A Library for Support Vector Machines. ACM Trans. Intell. Syst. Technol. 2(3), may 2011. ISSN 2157-6904. doi: 10. 1896619999996111999 1961 199.
URL https:://d/d .rgg 11..1..1111111 961 189. 11199.996111 1961199
Sorathan Chaturapruek, John C Duchi, and Christopher Ré. Asynchronous stochastic convex op- timization: the noise is in the noise and SGD don't care. In C. Cortes, N. Lawrence, D. Lec, M. Sugiyama, and R. Garnett (eds.), Advances in Neural Information Processing Systems, vol- ume 28. Curran Associates, Inc., 2015. URL https /ttp::::////cccpeeeeeeeeeoo hewp::edddiinnnnnnnessee......ee neurips.......
Dejun Chu, Changshui Zhang, and Qing Tao. A Faster Cutting Plane Algorithm with Ac- celerated Line Search for Linear SVM. Pattern Recogn., 67(C):127-138, jul 2017. ISSN 0031-3203. doi: 10. 10.1006/j.ppacog.. 201..oo.201..0...00 7.000.00006. URL https://doi.cr//1.. 1016//.. patcog.
Laurent Condat, Fast projection onto the simplex and the 4 ball. Mathematical Programming, 158(1):575 585, 07 2016. ISSN 1436-4646. doi: 10. 10.1007710000--055-0466666 URL https:
Lisandro Dalcin and Yao-Lung Fang. mpi4py: Status Update After 12 Years of Development. Computing in Science & Engineering. 23(4):47-54, 2021. doi: 10. 10.1000//SE...21....00 202...8216..
Damek Davis and Dmitriy Drusvyatskiy. Stochastic Model-Based Minimization of Weakly Convex
Functions. SIAM Journal Optimization, 29( 2027-223,,, 2019. doi: 10.1137/18MI 178244.
URL httpt:tt/////o/ http:://oooooggg//// www.//////.. 10. 1137/1 8M1 78244
Welington de Oliveira and Jonathan Eckstein. Bundle method for exploiting additive structure in difficult optimization problems. Optimization Online,, 2015.
A. P. Dempster, N. M. Laird, and D. B. Rubin. Maximum Likelihood from Incomplete Data via the EM Algorithm. Journal of the Royal Statistical Society. Series B (Methodologicall, 39(1):1-38, 1977. URL
http: www. jstor wwtp::/wsttororosttaaaaaee wttp://or//staaaeeeeeeee..
E. Dennis, Jr. and Jorge Moré. Quasi-Newton Methods, Motivation and Theory. SIAM Review, 19(1):46-89 1977. doi: 10.1137/1019005. URL htt..ttts:://// //do: wowpoooorrg//// 1 9005

---

Published as a conference paper at ICLR 2025
John C. Duchi and Feng Ruan. Stochastic Methods for Composite and Weakly Convex Optimization Problems. SIAM Journal on Optimization, 28(4):3229 3259, 2018. doi: 10.1137/17M1 135086.
URL http:tts//oo...o////11// /ttp://ooooooog10..1113311111111
John C Duchi, Sorathan Chaturapruek, and Christopher Ré. Asynchronous stochastic convex opti-
mization. XrXiv preprint 1508. 2015.
Alexandre d' Aspremont, Damien Scieur, and Adrien Taylor. Acceleration methods. Foundations and Trends in Optimization, 5(1-2):1 2021. ISSN 2167-3888. doi: 10.1561/4000000066.
URL http://........rr/000.1151////00
Grégory Emiel and Claudia A. Sagastizābal. Incremental-like bundle methods with application to energy planning. Comput. Optim. Appl., 46()):30533333, 2010.
Hamid Reza Feyzmahdavian, Arda Aytekin, and Mikael Johansson. A delayed proximal gradient method with linear convergence rate. In 2014 IEEE International Workshop on Machine Learning for Signal Processing (MLSP), pp. 1-6, 2014, doi: 10.1 10.1109/M..S222144665555
V. Franc and S. Sönnenburg. Optimized Cutting Plane Algorithm for Large-Scale Risk Mini- mization. Journal of Machine Learning Research, 10(76)2157-2192, 2009. URL http:
wwwpl...rg//apes///ll/// wwwp://///aooaa....m html
Paul Goulart and Yuwen Chen. Clarabel: A library for optimization and control, 2021. URL
bttps://oxxorrdcntttee www.oo..githae gwt.hb.........
M. Gürbüzbalaban, A. Ozdaglar, and P. A. Parrilo. On the Convergence Rate of Incremental Ag- gregated Gradient Algorithms. SIAM Journal Optimizatioon 27(3):0035-1048, 2017. doi:
10.1137711MM04496555 htt.://0S.......a.////////oo....
Robert Hannah and Wotao Yin. More Iterations per Second, Same Quality Why Asynchronous
Algorithms may Drastically Outperform Traditional Ones, 2017. URL httpt: htttt::://axii..rrrtttt
abs/17 108. 05136
Warren Hare and Claudia Sagastizábal. A redistributed proximal bundle method for nonconvex optimization. SIAM Journal Optimization, 2065):442-2243,, 2010. doi: 10.1 177/0909775 URL httpttt/p//oiii 111.//........111777773...0...0.
J.B. Hiriart-Urruty and C. Lemarechal. Analysis and Minimization Algorithms II: Advanced Theory and Bundle Methods. Grundlehren der mathematischen Wissenschaften. Springer Berlin Heidelberg, 1993. ISBN 9783662064092. URL
Id=OinsCAARQBAJ
Franck Iutzeler, Jérôme Malick, and Welington de Oliveira. Asynchronous level bundle methods. Mathematical Programming, 184:319-344 348, November 2020. doi: 10. 10.10077/110007--1194144444
Kwangmoo Koh, Seung-Jean Kim, and Stephen Boyd. An Interior-Poii Method for Large-Scale 11-Regularized Logistic Regression. Journal of Machine Learning Research, 8(54): 2007. /ttptttp://mmlr wwwp:/rrorgppppp..eeeee http://///k/ooaaaaoe koh0ka.00a... html
Anastasiia Koloskova, Sebastian Stich, and Martin Jaggi. Sharper convergence guaran- tees for asynchronous sgd for distributed and federated learning. In S. Koyejo, S. Mo- hamed, A. Agarwal, D. Belgrave, K. Cho, and Oh (eds.), Advances in Neural formation Processing Systems. volume 35, pp. 17202-17215. Curran Associates, Inc., 2022. URL
File/ (at.aaa8275533310666223331000-00
Kenneth Lange. MM Optimization Algorithms. Society for Industrial and Applied Mathematics, Philadelphia, PA, 2016. doi: 10. 10.113771.97811119977
URL/attps://epubs swreeuussssaa.... org/
doi Boi/abs// 10. 13711. 978161 974409
Mu Li, Li Zhou, Zichao Yang, Aaron Li, Fei Xia, David G Andersen, and Alexander Smola. Param- eter server for distributed machine learning. In Big Learning NIPS Workshop, volume 6, pp. 2, 2013.
12

---

Published as a conference paper at ICLR 2025
Nicolas Loizou, Sharan Vaswani, Issam Hadj Laradji, and Simon Lacoste-Julien. Stochastic Polyak Step-size for SGD: An Adaptive Learning Rate for Fast Convergence. In Arindam Baner- jee and Kenji Fukumizu (eds.), Proceedings of The 24th International Conference Artifi- cial Intelligence and Statistics, volume 130 of Proceedings of Machine Learning Research, pp- 1306-1314. PMLR, 13-15 Apr 2021. URL https: http:s://proceelli ngs. ml pre3s/v13/ 3r
Loizou2la.html
Julien Mairal. Incremental Majorization MuijorzationnMMmmmizzziooo Optimization with Application to Large- Scale Machine Learning. SIAM Journal on Optimization, 25(2):829-855, 2015.
Yura Malitsky and Konstantin Mishchenko. Adaptive Gradient Descent without Descent. In Hal Daumé III and Aarti Singh (eds.), Proceedings of the 37th International Conference on Machine Learning, volume 119 of Proceedings of Machine Learning Research, pp. 6702- 6712. PMLR, 13-18 Jul 2020.
URL https: sttps::/proceeedingg mlr. wtt.sp..ss..119/////
malitsky20a.htmm
K. Mishchenko, F. lutzeler, and J. Malick. A Distributed Flexible Delay-Toleram Proximal Gradient Algorithm. SIAM Journal on Optimization, 30(1):933-99, 2020. doi: 10.1137/18M1 194699.
htl.httss://oot ltopoooorg/1.1111301 10.00.11371111 8M1 194699
Konstantin Mishchenko, Franck lutzeler, Jérôme Malick, and Massih-Reza Amini. A Delay-tolerant Proximal-Gradient Algorithm for Distributed Learning. In Jennifer Dy and Andreas Krause (eds.). Proceedings of the 35th International Conference on Machine Learning, volume 80 of Proceedings of Machine Learning Research, pp. 3587-3595 PMLR, 10-15 Jul 2018. URL https::/prrcees ngs ml press Vv/0 m shchenko Ba html
Konstantin Mishchenko, Francis Bach, Mathieu Even, and Blake E Woodworth. Asyn- chronous sgd beats minibatch sgd under arbitrary delays. In S. Koyejo, S. Mo- hamed, A. Agarwal, D. Belgrave, K. Cho. and A. Oh (eds.), Advances in Neu- ral Information Processing Systems, volume 35, pp. 420-433, Curran Associates, Inc., ffrfffllleee wtapapprrfflllepppperreeeep
2022. URL 2ttp:/2222.222333311111111144442
nww.iee.is...... ips httppppcccppppeeeeeeeeee wow.pppeerrroocaaeeeee.eaeeeeeee
Marko Mäkelä. Survey of Bundle Methods for Nonsmooth Optimization. Optimization Methods and Software, 17(1):1-29, 2002. doi: 10. 0000000005577882200272333 URL htttp:://oo. org 1080
Radford M. Neal and Geoffrey E. Hinton. A View of the Em Algorithu that Justifies Incremental, Sparse, and other Variants, pp. 355-368. Springer Netherlands, Dordrecht, 1998.
Ion Necoara, Yurii Nesterov, and François Glineur. Linear convergence of first order methods for non-strongly convex optimization. Mathematical Programming, 175 May 2019. ISSN 1436-4646. doi: 10.10077/10107-0088 1232-1. URL 610107-018-1232-
Y. Nesterov. Lectures Convex Optimization. Springer Publishing Company, Incorporated, 2nd edition, 2018. ISBN 3319915770.
Yurii Nesterov and Mihai I. Florea. Gradient methods with memory. Optimization Methods and Software, 000): 2021, doi: 10. 1w..180000556778.2200111552 05.1000/115557000 2w215555768822222... 2020 1858831
URL/attps://act org/
Yuval Netzer, Tao Wang, Adam Coates, Alessandro Bissacco, Bo Wu, and Andrew Y. Ng. Read- ing Digits in Natural Images with Unsupervised Feature Learning. NIPS Workshop on Deep Learning and Unsupervised Feature Learning 2011, URL htap::://fllll.ss.t
aet//houseenumberr//iippggg
hwwsehumberss.eeee...... houoeeessseepp0000oooooeeeueeeer .pdf
Alasdair Paren, Leonard Berrada, Rudra PK Poudel, and M Pawan Kumar. A Stochastic Bundle
Method for Interpolating Networks. Journal of Machine Learning Research, 23:1-57, 2022.
Adam Paszke, Sam Gross, Francisco Massa, Adam Lerer, James Bradbury, Gregory Chanan, Trevor Killeen, Zeming Lin, Natalia Gimelshein, Luca Antiga, Alban Desmaison, Andreas Köpf, Ed- ward Yang, Zach Vito, Martin Raison, Alykhan Tejani, Sasank Chilamkurthy, Benoit Steiner,
13

---

Published as a conference paper at ICLR 2025
Lu Fang, Junjie Bai, and Soumith Chintala. PyTorch: an imperative style, high-performance deep learning library. Curran Associates Inc., Red Hook, NY, USA, 2019.
Zhimin Peng, Yangyang Xu, Ming Yan, and Wotao Yin. ARock: Algorithmic Framework for Asynchronous Parallel Coordinate Updates. SIAM Journal Scientific Computing, 38(5);
A2851-A2879, 2016.
doi: 10.1137/15M10249500 URL
15M1024957
Boris T Polyak. Some methods of speeding up the convergence of iteration methods. USSR compu- tational mathematics and mathematical physics, 4(5):1-17, 1964.
Benjamin Recht, Christopher Re, Stephen Wright, and Feng Niu. Hogwild!: Lock- Ap- proach to Parallelizing Stochastic Gradient Descent. Advances in Neural Information Processing Systems, 24:693-701, 2011.
Saced Soori, Konstantin Mishchenko, Aryan Mokhtari, Maryam Mehri Dehnavi, and Mert Gur- buzbalaban. DAve-QN: A Distributed Averaged Quasi-Newton Method with Local Superlin- ear Convergence Rate. Silvia Chiappa and Roberto Calandra (eds.), Proceedings of the Twenty Third International Conference on Artificial Intelligence and Statistics, volume 108 of Proceedings of Machine Learning Research, pp. 1965-1976. PMLR, 26-28 Aug 2020. URL
https://proseedingg.... mlr wrw.sppess..oooo htte:///v1.///ooo22aaaa.a..
Tao Sun, Yuejiao Sun, Dongsheng Li, and Qing Liao. General proximal incremental aggregated gradient ulgorithms: better and novel results under general scheme, Curran Associates Inc., Red Hook, NY, USA, 2019.
Choon Hui Teo, Alex Smola, S. V.N. Vishwanathan, and Quoc Viet Le. A Scalable Modular Convex Solver for Regularized Risk Minimization. In Proceedings of the 13th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. KDD *07, pp. 727-736, New York, NY, USA, 2007. Association for Computing Machinery. ISBN 9781595936097. doi: 10.1145/1281 1281199..1211777 URL BtRLhhtps:://oo www.oogg//......... 145/ / 1281270
Choon Hui Teo, S. V.N. Vishwanthan, Alex J. Smola, and Quoe V. Le. Bundle methods for regular- ized risk minimization. Mach. Learn. Res., 11:311-365, mar 2010. ISSN 1532-4435.
Robert Tibshirani. Regression Shrinkage and Selection via the Lasso. Journal of the Royal Statistical Society, Series B (Methodologicaal) 58(1):667-288, 1996. ISSN 00359246. URthttp: / www.
jstor. 1tt.oo.00o/sttaae//335555
Wim van Ackooij and Antonio Frangioni. Incremental Bundle Methods using Upper Models. SIAM Journal on Optimization, 28(1):379-410, 2018. doi: 10.1137/16M1089997. URL https://
doi. 1oo..oog/10.113//661000000
D. Vanli, M. Gürbüzzaaabaan, and A. Ozdaglar. Global Convergence Rate of Proximal Incremental Aggregated Gradient Methods. SIAM Journal on Optimization, 28(2): 1282-1300, 2018. 10. N0.11377/6M1094415. URL https:
doi:
//tpii:///ii.o /ww.. wwwpio.org/1...111111 11377/..111//11 6M1 094415
Hoi-To Wai, Wei Shi, César A. Uribe, Angelia Nedić, and Anna Scaglione. Accelerating incremental gradient optimization with curvature information. Computational Optimiza- fion and Applications, 76(2)344-380, June 2020. doi:
URL
s10589 020-003300-0013-110
Xiaoyu Wang, Mikael Johansson, and Tong Zhang. Generalized polyak step size for first order optimization with momentum. In International Conference on Machine Learning, pp. 35836- 35863, PMLR, 2023a.
Xiaoyu Wang. Mikael Johansson, and Tong Zhang. Generalized Polyak Step Size for First Order Optimization with Momentum. In Proceedings of the 40th International Conference on Machine Learning, ICML'23. JMLR. 2023b.
14

---

Published as a conference paper at ICLR 2025
Xuyang Wu, Sindri Magnusson, Hamid Reza Feyzmahdavian, and Mikael Johansson. Delay- Adaptive Step-sizes for Asynchronous Learning. Kamalika Chaudhuri, Stefanie Jegelka, Le Song, Csaba Szepesvari, Gang Niu, and Sivan Sabato (eds.), Proceedings of the 39th In- ternational Conference on Machine Learning, volume 162 of Proceedings of Machine Learning Research, pp. 24093 PMLR, 17-23 Jul 2022. URL prttps::/proceed:: ngs. .mlr. press/v162 http:///222ghmm...
Xuyang Wu, Changxin Liu, Sindri Magnússon, and Mikael Johansson. Delay-agnostic asyn- chronous coordinate update algorithm. In Proceedings of the 40th International Conference on Machine Learning, volume 202 of Proceedings of Machine Learning Research, pp. 37582-37606.
PMLR, 23-29 Jul 2023.
Ruiliang Zhang and James Kwok. Asynchronous Distributed ADMM for Consensus Optimization. In Bric P. Xing and Tony Jebara (eds.), Proceedings of the 31st International Conference Machine Learning, volume 32 of Proceedings of Machine Learning Research, pp. 1701-1709, Bejing, China, 22-24 Jun 2014. PMLR. URL htthttps: httpsssspprcceeeiigg...iiiii mir prr.s/ss///....e.r///////// changel4.hes
15

---

Published as a conference paper at ICLR 2025
A APPENDIX
In this appendix we present proofs and additional numerical experiments.
A.1 DUAL SUBPROBLEM
Lemma A.1. Let X E Rm i= 1= 1...... n. and X = -A11...., An) E Rmmn Define g R - R by
9(A)
M
2| M Σ G - H1!M 2
-
M Σ G. + (2,
2
The Lagrange dual of (3) is given by
minimize subject
g( 1 X; = A
(1I)
2,,
Furthermore, if X* optimal in 4. then the unique solution of 3). denoted by Texaen is given by
1
Eexeer prox
1 37
Σ G M
(12)
1=1
Proof. In the proof we use the notation of stochastic function values and gradients. The setting with exact function evaluations can be recovered by doing the substitutions Fi(x; E) = (z) and Gx (z(()..
Problem 3 can be formulated as
TI
M
minimize
Σ
r 1x- R(x)
(13)
subject to r, 2 Fi(ef:E) Ef) + (G.(s): (5), 25), j = 1....,m,,
m, i 1..... n,
with variables r R" and x E Rd. For i I,...,n, n, introduce a Lagrange multiplier vector
X R" The Lagrangian is given by
[(x, r, "i, An)
P
+
x
+ (G:(e)))))) -r)) + R(x)
2
1=1
M
1 1 1- Xo
1=
ri +
|| =122 Σ (Xis G x v.) + R(x),
2
==1
where
G, = (+f())))
G.(zini E Rdxm
and 0; E Rd is defined componentwise by
(v,), = (G.(e::))) - Fe(e): {))
The Lagrangian is unbounded unless 1 1T); 1, i 1,.... n. Furthermore, for such mini- mizing the Lagrangian over yields
inf L(x, r, A1 AI,..., An) = inf R(x) + M || - E Σ (Gddn
Σ (A
2
1=1
inf z
R(x) +
MM
r (z
1 n
Σ
M
a
G
M 2
Illl
Σ
A, vz)
M-
M
-H
1/M
1 n
Gidi
M
||
Σ
G
M
|
Σ
Do vz)-
M
2
M
i=1
1=1
1=1
16

---

Published as a conference paper at ICLR 2025
By dropping the term Af || it follows that dual problem is given by
minimize g(A) = - H L
2 M Σ
G
+ 2
= M Σ
G.A. 2 + > (Ai, oz)
(1,
subject to ΛEA.
Since Slater's constraint qualification (Boyd & Vandenberghe, 2004 page 226) is satisfied, strong duality holds and the point Texact defined by (12) minimizes [ax, r, Xi..... 2,)
over x (here the
value of is arbitrary since the Lagrangian is independent of for any value of À that is dual
feasible). The function x + C(x, r, Xi...., ...,..,,))).. X²) has a unique minimizer, so it follows that Zexact given by indeed solves
A.2 CONVERGENCE ANALYSIS
In the analysis below we analyze the progress Algorithm D makes in iteration k. To simplify the notation we drop the iteration index. In other words, the notation 2),, j L..... m below refers to the points used to construct the piecewise linear model of f. in iteration k.
In the first few results we will stick with the convention of using stochastic function values and gradients. The setting with exact function evaluations can be recovered by doing the substitutions (x = fz) and (z; (x))
We will analyze Algorithm 1 by using 77.. This will make the analysis depend on the dual variable X. The following result (inspired by Nesterov & Florea (2021)) will be useful to partly remove the dependence on À from the analysis.
Lemma A.2. Assume satisfies
6 and let Ik+1 be given by 7 Then
Xy ()((())))))))))))))))))))))))))) + (G.(2): - 23ح1 2 f((++11E)) - 8.
Proof. Since 6 is satisfied we have (A, g((( 2 supxea (A, vV(()) 88 Note that
(7, - -o(())
Σ TL Vg
()((())))))) + (G.(2): F011 2i>1
sup (A, Vo(Ai) sup
[lee) -2)1== Σ f((++11) E)
AEA
A
Lemma A.3. The next iterate 1x+1 satisfies
1
1
|
x²13
Mil 2
x11 <
(R(x')- - R(E++1) 2M
- -
2
2M
M
1
+
())G)(():))) xb+1).
M
(14)
Proof. In the proof we will apply the identity
M lly 11-- - M
1
M₁
M m
112
||
M
2M 1=1
2
i=1
1=1
twice; once with = x and once with y = Ik+1-
Using the three-points points lemma -lbbb c|1 1 ||a c|2 (a - b, b)
_/1laa -bll3 we get
1
2 || | - 211
2 1 x x²1 11 = (a rk+1, x- - xb+1)
| - -
(15)
17

---

Published as a conference paper at ICLR 2025
Since 2x+1 prox, R 31 Σ
d Gz)): it follows from optimality conditions Thm 3.1.23)
i=
M for convex optimization that (Nesterov
2018
m
R(xx+1)= S R(y) + M (I (2
X G.G rx41) for all y E Rd.
M
==
If we let y = xx and rearrange we get (3 22+1, -I--1
1 (R(x') R((x+1)) +
1
Σ
E
May (G((tt)))) xxt1)..
M
M
i=
Using this bound in
15 shows that
2 |a - x²13 2
||
(R(x*) - R((x+1)) +
ΣΣ
Aug (x)((()):)) - -x+11)
M
M
1 | 2212
2
1 n
(R(x*) R((x++1)) +
Auy ((.))) - xx+11
M
M i=1 j=1
1
M
rb++1 | 2 +
M
Σ
12m 11
M
2
2M
2
i=1
1=1
We can rearrange to obtain
1
(1
1
2 | - x-113
M
- x1
M 6
M
M
mm
M
1=1
1=1
1=1
$
(R(x*) R((x+1))
+
dey (G]( ()) x² IK+1)
M, ||+|+++111111 - -
M
M
2M
i= 1=
Note that
n
n
1 n
M
Mi
x²1
x
M
Mizi i 2
m
+
M
My 1
i=1
i=1
2
M
||*
1
=
112
2 112
Σ
Mi
|| 112
M
M
2M
2
f=1
1=1
2
M,
1
xx"
2
112
M M - 2mm 112-
M
2
M
i=1
2=1
Hence, we conclude that
| - x=13
M,l
-
(R(x') - R((x+1))
Milaat11 - 2
2
2M
M
2M
1 n m
(x(G,(sfi))), Ix+1))
+
M i=1
Lemma A.4. The next iterate 24+1 satisfies
Mill - -1113 < (R(x*) - R((x+1))+ + M f(xx)) + 8
|
2
2M
M
M
( Eim) + (G.(= 061 - = + Mi
Σ
| - 2.,113
M
2
12 m
ΣΣ
Xg(P(1= - f((z)))
18

---

Published as a conference paper at ICLR 2025
Proof. Note that
m
m
17
X7
X)(G((2):E)). Ix+1)
-) (G(()))))) mxt1))
m
(F(((()))) -(()) 2f -zx+1))
Σ +
2)))
= A1 - Σ {))
Ø=1
In the first inequality above we used the star-convexity of the oracle (see Assumption 1.10 for the stochastic case and Assumption 4.4 for the deterministic case). In the second inequality we used Lemma A.2
Inserting this into Lemma A.3 yields
2 [k+1 - 2²112
Mi pm
=x112 5
(R(x") - R(Ex+1)) +
1
Σ
Fe("
2M
M
M
2=1
1=1 j=1
1
M
6
(M(T)+1)) +
|
M
M
The result now follows from adding and subtracting (1/L)f(z*) from the right side of the inequality and dropping all but the most recent cut for every piecewise linear model.
We now distinguish between the deterministic and stochastic case. Feyzmahdavian et al. (2014) will be useful.
The following result from
Lemma A.5. Let (V+) be a non-negative sequence satisfying
Ve+1 S qV& +D
max (K-T)+SPCK
Vi +r,
k: k= 0, 0,
for some non-negative constants p. 9 and r. 1f4 + p < 1, then
V& S p Vo +,,
0,1,2,....
where = (p+ //att)) rat1prr11ppppp1 q) and (k - T)+ = mnax(k-T,0)
Lemma A.5 will be used to analyze the algorithm under the quadratic functional growth assumption. For the analysis of the convex case, we present new sequence result that may be of independent interest.
Lemma A.6. Suppose that (Vx) and (W are non-negative sequences satisfying
Va+1 < max (K-T)+5I5k
Ve - Wh+1 +r,
k == 0, 0,1,2.....
(16)
for a non-negative constant r. Then, for any k 2 1,
min W (T 11V
+r.
(17)
Proof. We prove 17 by contradiction. Suppose that for some 2 1, (17) fails to hold. Then, for
all l K,
W4 (T + 1)
+r.
(18)
K
Define Iy = {0} and for any t 2 1,
Ij = [[t 1)(7 1) + 1.1(7 + 1)].
19

---

L L Published as a conference paper at ICLR 2025
Substituting (8) into (6) gives that for all k K 1,
Ve (++ 1)Vo
Va+1 < max
(19)
(k-T)+
K
Let i [K/(T + 1)1. For any & S i, I. S [0, KJ. Then, using
we can derive that for all
1 1 1.
(T + 11V6
max kEI++1
V/ < max V
kEZ,
K
Summing the above equation over & 00 - and noting that maxkEIo Vi: Vo yields
1(T 1)Vo
max V V/8 KEI;
(20)
Note that / = [K/(T 1)J. i K/(T + 1), then
ï(T + 1)Vo
-Vo
K
substituting which into 20 yields maxkez, V& 0, which cannot be true because V22 2 0 for all
k 2
i < K/(T+ 1), then we have K > +((++1) + 1). Then, by
19
(T + 1)Vo
VK < max V2
KET;
K
Moreover, since 2 K/(T 11 1, from 20 we have
(T + 1)Vo
max
V
kEZ;
K
Combining the above two equations, we obtain
VK < O,
which cannot hold.
Concluding the above, 17 holds for all & 2 1.
EXACT FUNCTION VALUES AND GRADIENTS
First we prove convergence for exact (full-batch) function values and gradients.
Theorem A.7. Under Assumptions
and 4.4 the iterates of Algorithm usiin M; =
L,, = 1,...,, satisfy
I x= 112 S pt 1 x=1 co. and Es 28/ μ.
(21)
where p = (L/(L /(++)
Proof. We insert M, Li, M = L and Fi(x;; E9) fa(x*) into Lemma A.4 and use that fi is smooth with parameter L; (see Assumption 4.2
to conclude that
1 -
1
1 (R(x*) R(xx+1))
1 f(x²)
8
| - 11
L.llet
x1 <
2
2L
L
1
2 (f( + (V Ik+1 - = +
Li
| 2..
2
1=1
< 7 (R(x*) R(xx+1)) + 7, f(x*) + - ((x+1)
(F(x*) F((x++1))
+ L
20

---

Published as a conference paper at ICLR 2025
Now suppose that the quadratic functional growth condition of F (see Assumption 4.3 holds. We conclude that
8 L
#k+1 - x²11
L 2
x1133
| - x² 2²11 +
2L 1=1
2L
After rearranging terms we get
28
|
2=
Li 2
x=112 112 +
L μ
i=1
L
28
| x²112 + L P
max L+ ( SPCk
Applying Lemma A.5 yislds yields the desired result.
We now consider the case without the growth assumption.
Theorem A.8. Under Assumptions 4.1 4.2 and the iterates of Algorithm Tusing M, Li;
1,..., n, satisfy that for any 2 1.
(T +
1) - x 11
min F(x)) - F(x*) < tsk
+ 5.
(22)
2k
Proof. From the proof of Theorem A.7
we know that
L Tsllam - =111 1 (F(x") - F(xx+1)) 5
| -
x²12
2
2L
L
Note that || - x=113 max -) Sesk || 1+1 for any I,..., Equation 22 follows
by applying Lemma A.6 with Vi } |1 1=1 Wa-1 = (F(xx+1) - F(x*)) and
5
L
STOCHASTIC FUNCTION VALUES GRADIENTS
Next we prove the convergence for stochastic function values and gradients.
Theorem A.9. Consider Algorithm ! with M; = aLi, i = 1,..., where a > 1. Assume that
stochastic function values and gradients are used. Under Assumptions 4.1 4.2 and and 4.10 the iterates of Algorithm 7 satisfy
min E[Fxx) F(x*) < a(T + 1)L[
ro
+
(23)
2k
where E Eg + Eo, + Eag with
n
Eg = 6,
Co1 = ==:=111v no
602
2(a - 1)
Li
i=1
If. in addition, Assumption holds, then
Bl|a - x² x11 < p² 11:00 x0122 +2/1u
where p (aT.((aT, +)) ((4+))
Proof. According to Lemma A.4 we have
1
f(=)) 8
| x11
Mill zm
x0133
(1(x))
2M
M
Mi
Pi ) + (z e 2x411
+
||
=
M
2
(24)
2T.
1 m
Nag (F((2 -((()(()))))))) }
M
21

---

Published as a conference paper at ICLR 2025
Using the Cauchy-Schwand inequality together with M, aL; and the assumption that worker i is smooth with parameter L5. we bound T1 according to (this holds for all I....,n) n.
Li | 2mm11
T = (((=)) + (VS((=m) T8+1 - =m/) +
2
(a - 1)L; |
+ ( - f((mm)) + (mi (m)) fi( ( ; 2k+1 2mm)
2/1112
2 f((x41) + Fe(chi Sim) f((mm)) (a (a-1)44
[x++1 -2 = l12
-IIGi(Eii Ei)) vf((=m)) 12 |,++1 - 2n1l2
2 f((T441) + Filhh: (tm) fe(emm) 2(a 1) 1
1
( (
where we in the last inequality used that (b/2)(2 - al 2 -a²²/22) for all / E R, R and b > 0. Inserting this bound into (24) allows to conclude that
Mil =m - =011 M (M(x') - R(xx+)) + 1
M / (x*) + 8 M
2 [k+1 - -
2M
1
(f(()))) Pr(= S((2/))
|| [G:((zm:: V.fa (1²)
- 2(a-1)44
N ( f((x)).
By taking expectations conditioned on all randomness up the current iteration and using that ( ( [l) = f2())) where the expectation is conditional, we get
1
1
8 E[P(**) F(x++1)]+
E E1| 12]
Mi 2mm
x=1 < M
2
2M
M
+ M
BIIIG )
2(a - 1)L,
M
1=1
From the assumption of bounded variance (see Assumption 4.10 we have T3 S oz. Hence,
1
1
M - x1113 1 E(F(x*) F( 5 M
E
Dk41 - 211
2
2M
M
03
+ 2(a
N (F(() - fx())))
1)M
L,
M
am1
After taking expectations again and using the tower property of conditional expectations we get
8
E El| - 1111
M,
E||
- xz 1121 < M
B[F(x*) F(X++1))+ + M
2M
1=1
02
1
D (Fi(2 - f((2t))
+ 2(a
E
M)M
M
22

---

Published as a conference paper at ICLR 2025
To bound T's note that for i = 1, ...., n. by the Cauchy-Schwarrd Schwarz inequality, it holds that
m T'
S E
Xij
|F(( Ej) - fi(x")]
1/2
1/2 Σ (Fi(d -(()))))))))))))))))
E
E
(a(E(t : ) 1/2
Σ
S dıvm.
Hence,
8 M, Bl| - S M B[F(x*) F(x++1)) + M
E 21 - x1
x1'1
2M i=1
o2
1
no1
m
+ 2(a M)M
Li
M
1=1
Note that E 81112 - x²1 S m Sesk
Elllet -1 for any = I,...,n. n. Then, M7 (E[F(xx++1) - F(x*)]) and r
by Lemma A.6 with Vi = 2 E[|k= x+
WE+1
5 M
+
Di= 1 L
+ noivim we have (23
2(a 1)M
Now further assume that the quadratic functional growth of F (see Assumption 4.3) holds. We have
1
E
x11
1
M
-
S
/1
E Tx41
x= x=1
5
2
2M
2M
M
02
no m
+ 2(a
Σ
1)M L
M
Rearranging the terms shows that
E El - 11 <
M M MEI - -x"1121 +
2
8 + nonn +
1
M + M
2(a (Q--) 1) i=1 L.
M
Bll - x1) +
2
1 + 2(a - 1)
o2
n
max M + (k-T)-SPS
M + #
L
Applying Lemma
A.5 yields the desired result.
A.3 SOLVING THE MASTER PROBLEM
Here we discuss the complexity of solving the master problem 3 approximately. We use an accel- erated projected gradient method to solve the dual problem
minimize
g(A)
(25)
subject to A A.
The objective function g(A) is defined in Lemma 3.1 and A R is the Cartesian product of n probability simplices of dimension m. In each iteration we must project onto A, which can be done at cost of order (nm log m.) The cost for evaluating the gradient (10) of the objective function g(A) dominated by a term of order (wwdd) in addition to the cost of evaluating the proximal operator of R. (We recall that n. is the number of workers, dimension of x..) If, for example, R(x) = a||æ= ||2, then the cost of evaluating the proximal operator is (d). in this case the total cost per iteration of the projected gradient method is dominated by a term of order (mnd). In practice we found that only a dozen of iterations was often sufficient to satisfy the termination criteria (
is the bundle size, and d is the
23

---

Published as a conference paper at ICLR 2025
Table Properties of the datasets that we use. The total number of data points is denoted by . and d is the dimension of the decision variable. The column labeled DENS I TY shows the percentage of non-zero entries. The label DENSE means that the data matrix is stored as a dense matrix.
DATASET
N
d
DENSITY
A
MN STTM
(BINARY)
164 8890
784
DENSE
3e-3
ROVI
(BINARY)
677 399
47236
0.15%
3e-6
EPSILON
(BINARY)
500 000
2000
DENSE
Se-5
(MULTICLASS)
630 420
10240
DENSE
le-3
MNIST8M
(MULTICLASS)
8100 000
7840
DENSE
8e-3
Modern interior-point solvers are fast, easy-to-use, robust, and good at exploiting sparsity. It is therefore natural the master problem can be formulated as a quadratic program with a separable objective function and coefficient matrix that is quite sparse (see, for example, Andersen al. (2011))
solver for solving the master problem (3.. If R(x)= = \||==|1,
To investigate the impact of our specialized approach for solving the subproblem, we ran ABM twice and solved the master problem with either the projected gradient method applied to the dual (25 Prorr-ooooooo
ing accuracy 5 = 10-7 or the state-of-the-ar interior-point solver Clarabel (Goulart Chen 2021 applied the quadratic programming formulation of 3) For mn st.8, revl and eps on, the average time to solve the master problem was 0.017, 0.29, and 0.027 seconds for the gradient method, versus 0.20, 13.4, and 0.66 seconds for Clarabel. In other words, the gradient method (im- plemented in Python) is more than an order of magnitude faster. This comparison is not completely fair, since Clarabel in general finds a solution with higher accuracy. However, as shown in Theorem it is not necessary to solve the master problem exactly to maintain convergence guarantees.
4.5
A.4 ADDITIONAL NUMERICAL EXPERIMENTS
DIMENSION OF DATA SETS
Table 2
shows the dimensions of the data sets and the value of the regularization parameter A
CONVEX EXPERIMENTS
Figure 3 shows the performance of ABM, DAve-RPG and P PIAG for binary logistic regression with A2 = 0, i.e., when the objective function is convex but not strongly convex. The optimization very similar to the progress in the strongly convex case for mn 8 and epst ip on, but removing the strong convexity degrades the performance on revl for all three methods (cf. Figure i in the main text). Nevertheless, ABM outperforms the two competitors.
trajectories
BENCHMARKING ON MULTINOMIAL LOGISTIC REGRESSION
For the multiclass classification problems the objective function
f(x) 1
e
22
1 {y k} log
|
N
ΣK 1==1
exp(x
Uz))
k=1
K
R(x) A
|
k=1
where .i..... UN E (1,2..... K} are the labels. Here the decision variable x = (x1.... Fx where each 2j. 1 S j < K is vector with dimension equal to the number of features. Figure shows the relative suboptimality of ABM, DAve-RPG and P PIGG on the two multiclass datasets SVHN and mn at 8m. (The dimension of the problems can be found in Table 2)
24

---

Published as a conference paper at ICLR 2025
(66) C"
397
237
3344
484
RA0
Ferlire
Ratien11
Purdar
AMM
15"
004) FUP
15"
351
RAc 877
70060
337
10080
1600
namber predeer
Nombor prochres
Figure 3: The progress of ABM, DAve RPG and PIAG the binary classification problems for
2 = 0. The datasets are arranged in the order mnist 8m, rcvl and epsilon from the left.
ABM
DAve-RPG
PIGG
10:1
DAve-RPG
PAGG
100
200
300
400
500
500
100
200
300
400
500
600
Buntinn 64)
Buntime (4)
Figure 4: The progress of ABM, DAve-RPe and PIAG on the multiclass classification problems. The datasets are arranged in the order SVHN and mnist from the left.
STOCHASTIC FUNCTION VALUES AND SUBGRADIENTS
We test the stochastic extension of ABM using mini-batches for multiclass classification the data set mnist 8m. We split each worker's data set into 100 mini- mai-batches. For ABM based on exact function and gradient evaluations we estimate the smoothness parameters as described in $5 For the stochastic variant using mini-batches we estimate the smoothness parameters as follows. Each worker stores the last point, say = it was queried in, and when queried again in point 2 the worker draws representing mini-batch and then evaluates both G. {) and Gi(z) The worker then estimate the smoothness parameter L, with
[G { G2 G. G:(=m--i:))l
L
|| 2 1
The worker then sends back both the gradient G.(z E) and the smoothness estimate i to the central server.
For comparison also implemented synchronous proximal stochastic gradient method. The step size parameter was carefully tuned. The left part of Figure shows the progress of ABM, the stochastic extension (ABMStoch). and the proximal stochastic gradient method (ProxSGD), The right part of Figure 5 shows the progress in the presence of some struggling workers. (For the right part we let one third of the workers have random delays uniformly distributed the interval [2tgrad, 4t gfgd every time they compute gradient, where fgrad is the time required to compute the gradient.) It is interesting to note that while ProxSGD performs much worse for simulated delays, both ABM and oBMStoch are barely affected by the delays.
25

---

Published as a conference paper at ICLR 2025
[ft))
(b)
Figure 5: Left: The progress of ABM, the stochastic variant ABMStoch and tuned synchronous proximal stochastic gradient method P PrxxGG, Right: The progress under simulated delays.
26


Reviews:
[{"review_id": "fAr6TcZh2s", "reviewer": "Reviewer_NXCg", "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.", "questions": "- The reviewer would like to know how their algorithm improves the complexity compaerd to the baselines DAve-RPG[1] and PIAG [2].\n- 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?\n-  How does the proposed algorithm scale in terms of the node number? Can the authors provide some numerical experiments to illustrate this?\n- What’s the limitation of the third one in Assumption 4.9?", "limitations": "", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "- The proposed algorithm seems novel to the reviewer, and is fast and easy to tune in practice.\n- 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.\n- 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].\n- 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.\n- The scalability of the proposed algorithm is not well addreesed; note that only a system with 9 workers is considered in the numerical experiments. \n\n[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.\n\n[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.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "41i7w55ivo", "reviewer": "Reviewer_zZ8S", "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.", "questions": "The reviewer wonders if the authors can comment if this applies to settings where each worker has an individual time-dela, $\\tau$.", "limitations": "", "rating": 8, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "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", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "KOSWNM9W4C", "reviewer": "Reviewer_KLUM", "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.\n\n1) Novelty\n \nBundle 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. \n\nOn 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. \nAs 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).\n\n\n2) Experimental evaluation\n\nThe 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. \nCan the authors argue about scalability of the method with respect to the number of workers? How does the method empirically perform on nonconvex problems?\n\n--\n\nMinor questions, discussion:\n- 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.\n\n- 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.", "questions": "see above", "limitations": "", "rating": 6, "confidence": 3, "soundness": 2, "presentation": 3, "contribution": 2, "strengths": "see above", "weaknesses": "see above", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "YgsQVlARwr", "reviewer": "Reviewer_4dTz", "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.", "questions": "Questions:\n\n1. 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?\nCan you also comment on the reason for the discrepancy between (7) and (8) in terms of the same (the latter applies $\\forall k$).\n2. Can you include the adaptive tuning aspect ($\\hat{L}_i$) in the analysis, or provide a remark sketching the same?\n3. Can you please comment on means to boost scalability in large systems ($n \\gg 1$)?\n\n\nSuggestions:\n\n- Please include the cost of solving the master problem ($O(nmd)$) in the main paper. \n- Can you rephrase the statement in lines 362-365? It seems a bit sloppy for your fluent presentation style. \n- Please explain the reasoning in line 458 (why in this case the master problem is more challenging).\n- Please elaborate on \"potentially discarding outdated information\" in line 532 (in relation to dynamic bundle size selection).\n\nEditing:\n\n- line 55: \"insensitive\" does not seem accurate and can be misleading; please rephrase.\n- line 88: counterpart -> counterparts.\n- lines 108-111: please rephrase to prevent any misperception of a contradictory statement (gradients provide local; in contrast, gradients provide global).\n- I suggest numbering the equation in line 207. \n- line 256: the central server for each worker $i$ -> each worker $i$ (to prevent any confusion that the server has access to user data).\n- line 295: delete \"weak\".\n- line 314: rephrase \"gracefully\".\n- line 490: no tuning -> no tuning in these experiments (to avoid overstating).", "limitations": "", "rating": 8, "confidence": 5, "soundness": 4, "presentation": 4, "contribution": 3, "strengths": "+ Useful algorithmic contributions (especially embodying parameter auto-tuning).\n+ Rigorous analysis (incorporating cases of practical interest such as inexact server solutions and mini-batch processing).\n+ Well-written and clear paper (especially commendable is that the authors provide insights for all choices as well as their analysis).\n+ Rich, well-presented, and convincing experiments.", "weaknesses": "- Dubious scalability in large systems ($n \\gg 1$).\n\nOthers--outweighed by the strengths--are that the contribution is an extension of previous works and that the code is not presently shared.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (Poster)