Achieving Linear Convergence with Parameter-Free Algorithms in Decentralized Optimization
Authors: Ilya Kuruzov
Gesualdo Scutari
Alexander Gasnikov
Venue: NeurIPS 2024 poster (2024)
Keywords: decentralized optimization
linear convergence
parameter free
Primary area: optimization
TL;DR: Parameter Free Decentralized Optimization

Abstract: This paper addresses the minimization of the sum of strongly convex, smooth
functions over a network of agents without a centralized server. Existing decentralized algorithms require knowledge of functions and network parameters, such as the Lipschitz constant of the global gradient and/or network connectivity, for
hyperparameter tuning. Agents usually cannot access this information, leading
to conservative selections and slow convergence or divergence. This paper introduces a decentralized algorithm that eliminates the need for specific parameter
tuning. Our approach employs an operator splitting technique with a novel variable
metric, enabling a local backtracking line-search to adaptively select the stepsize
without global information or extensive communications. This results in favorable
convergence guarantees and dependence on optimization and network parameters
compared to existing nonadaptive methods. Notably, our method is the first adaptive decentralized algorithm that achieves linear convergence for strongly convex,
smooth objectives. Preliminary numerical experiments support our theoretical
findings, demonstrating superior performance in convergence speed and scalability.

Achieving Linear Convergence with Parameter-Free
Algorithms in Decentralized Optimization
Dya Kuruzov
Gesualdo Scutari
Alexander Gasnikov Innopolis University gasnikov@yandex.
Innopolis University kuruzov wa@phystech..cduu
Purdue University cuutaai@purdue edu.
Abstract
This paper addresses the minimization of the sum of strongly convex, smooth functions over network of agents without centralized server. Existing decen- tralized algorithms require knowledge of functions and network parameters, such the Lipschitz constant of the global gradient and/or network connectivity, for hyperparameter tuning. Agents usually cannot access this information, leading conservative selections and slow convergence or divergence. This paper intro- duces a decentralized algorithm that eliminates the need for specific parameter tuning. Our approach employs an operator splitting technique with novel variable metric, enabling a local backtracking line-search to adaptively select the stepsize without global information or extensive communications. This results in favorable convergence guarantees and dependence on optimization and network parameters compared to existing nonadaptive methods. Notably, our method is the first adap- tive decentralized algorithm that achieves linear convergence for strongly convex, smooth objectives. Preliminary numerical experiments support our theoretical findings, demonstrating superior performance in convergence speed and scalability.
1 Introduction
We study optimization across a network of m > agents, modeled as an undirected, static graph, possibly with no centralized server. The agents cooperatively solve the following problem:
min f(()..
(P)
where f: R" - IR the loss function agent assumed be strongly convex and smooth (i.e.. with gradient being Lipschitz continuous), and accessible only to agent i.
This formulation applies various fields, particularly emphasizing decentralized machine learning problems where datasets are produced and collected at different locations. Traditionally, statistical and computational methods in this domain have relied on a centralized paradigm, aggregating computational resources at a single, central location. However, this approach is increasingly unsuitable for modern applications with many machines, leading server congestion, inefficient communication, and high energy consumption [27, 23]. This has motivated the surge of learning algorithms that target decentralized networks with no servers, a.k.a. mesh networks, which is the setting of this paper.
Decentralized convex optimization has a long history, with numerous algorithms applicable to Problem (P); recent tutorials include [34, 41, 33, 45]. Lack of adaptivity: These methods share the hurdle relying sensibly on the tuning of hyperparameters, such as the stepsize (a.k.a. learning rate), for both theoretical and practical convergence. Existing theories ensure convergence under generally conservative bounds on the stepsize, which depend on parameters like the Lipschitz constant of the global gradient, the spectral gap the graph adjacency matrix, or other topological properties. Acquiring such information is challenging in practice, due to physical or privacy limitations and constraints. This often leads to manual tuning, which is not only tedious but also results in less predictable,
computationallcoommmiccii
and non reproduciiee performance.
38th Conference on Neural Information Processing Systems (NcurIPS 2024).

---

Parameter-free centralized methods: On the the hand, significant progress has been made in the centralized setting to automate the selection of the stepsize across various optimization and learning problem classes. (i) Traditional approaches in aptimization-sucle as line-search methods [36], Barzilai- Borwein's 8 stepsize [3], and Polyak's stepsize [37]-have been supplemented by recent adaptive stepsize rules based on estimates of local curvature [30] and subsequent techniques [31, 19, 20, 22, 50]. (ii)
In the ML community, adaptive gradient methods such as AdaGrad [1 IJ, Adam [18], AMSGrad [40], NSGD-M [9], and variants [25, 44, 29] have gained significant attention for training large-scale learning models. These methods apply to stochastic, nonconvex optimization problems. (iil) Further advancements extend adaptivity to stochastic/online convex optimization problems, e.g., 15, 15].
Distributed adaptive methods: While variant of these centralized algorithms have been adapted to federated architectures (server-client systems), e.g., in [39, 24, 8], their application to mesh networks not feasible. In federated learning, a central server aggregates local model updates, a process integral to its hierarchical structure. However, mesh networks, which lack centralized coordinating node, do not support such a direct aggregation of large-scale vectors. Recent attempts to implement some form of stepsize adaptivity for stochastic conv//onne optimization problems over mesh networks are [32, 7.21J. These methods generally achieve adaptivity by properly normalizing agents' gradients using past information. However, with the exception of [21], they rely on the strong assumption that the (population) losses are globally Lipschitz continuous (i.e.. their gradients are bounded). In fact, Lipschitz continuity in convex optimization readily unlocks parameter- free convergence by using stepsize tuning of O LK) (here, k is the iteration index). Moreover, [32, 7] still require knowledge of some optimization parameters for the stepsize tuning, to guarantee convergence.
Attempts to introduce adaptivity in decentralized optimization for solving (P) have been explored in [12, 14, 13J. These methods bring the Barzilai- -Brreein (BB)'s 's stepsize strategy into gradient tracking algorithms [43, 28, 35, 48]. (i) However, convergence of these algorithms is not guaranteed under the proposed BB strategy, unless the stepsizes remain uniformly bounded from below and above throughout the algorithm's 's trajectory-a condition the BB rule does not inherently satisfy in decentralized settings. Furthermore, these bounds for the stepsizes are typically unknown to the agents, as they depend on the strong convexity and smoothness constants of all agents' losses. Even with such knowledge, enforcing these conservative bounds contradicts the principle of adaptivity by potentially negating the advantages of variable stepsize strategy that adapts based on local loss curvature, producing stepsize values significantly larger than theoretical thresholds used in nonadaptive methods. (ii) Additionally, to ensure contraction of the iterates, studies such as [13, 14] require multiple rounds of communications per iteration (gradient evaluation) thhs demands the knowledge of network and optimization parameters the agents' sides, making practical implementation unfeasible. (iii) None of these studies offer expressions of convergent rates for the explored algorithms, leaving it unclear whether the BB stepsize rule can provably outperform nonadaptive methods. (iv) Lastly, the methods discussed employ the traditional BB rule, which is only proven in centralized settings to produce convergence methods when minimizing quadratic losses. Simulations in [12, 13] are in fact performed only on quadratic functions.
Open questions and challenges: To our knowledge, no deterministic, parameter-free decentralized algorithms exist that solve Problem (P) over mesh networks, particularly achieving linear convergence when agents' functions are strongly convex and smooth. The current decentralized adaptive stochastic methods [32, 7, 21] discussed earlier do not adequately bridge this gap. Tailored for stochastic environments, these methods merely ensure that cumulative consensus errors along the iterations remain bounded, not necessarily decreasing. This typically involves either diminishing stepsizes or adjustments based on the final horizon to manage the bias-variance trade-off. These strategies fall short in deterministic scenarios like Problem (P), failing to ensure convergence to exact solutions, and achieve faster (1/k) convergence rates in convex cases or linear rates in strongly convex scenarios.
Major contributions: This paper addresses this open problem. Our contributions are the following:
1. A new parameter-free decentralized algorithm: We propose decentralized algorithm that eliminates the need for specific tuning of the stepsize. Our approach leverages a Forward-Backward operator splitting technique combined with novel variable metric, enabling local backtracking line-search procedure to adaptively select the stepsize at each iteration without requiring global information on optimization and network parameters extensive communications, We are not aware of any other provable decentralized line-search methods over mesh networks.
2

---

Designing decentralized line-search procedures that are well-defined (terminating in finite number of steps), locally implementable, and ensure algorithm convergence through satisfactory descent on an appropriate merit function presents significant challenges. A major issue is that line- mearsh procedures merely based on the local curvature of agents' functions often fail to ensure convergence, producing excessively large, heterogeneous stepsizes that, e.g., poorly connected networks cannot support. This necessitates the identification of line-search directions and surrogate functions that encapsulate both optimization and network influences, aspects that have not yet formalized. Our design guidelines (cf., Sec. 3) are of independent interest; hopefully they will provide valuable insights for the development of other decentralized adaptive schemes, such those based on alternative operator splittings.
Convergence guarantees: We have established linear convergence for the proposed decentralized adaptive method. Our analysis identifies critical quantities that capture the interplay between opti- mization conditions and network topology, directly influencing the convergence rates. Specifically: (a) In "well-connected" networks, the convergence rate exhibits separation property: the overall rate is dictated by the slower of either the centralized gradient algorithm solving the same problem or consensus algorithm run the same mesh network. (b) Conversely, in "poorly" connected net- works, the separation property vanishes, and the convergence rates are adversely affected by network degradation terms, still exhibiting linear dependence on the condition number of the optimization loss. (ii) Unlike many existing distributed optimization frameworks, the optimization parameters in our rate expressions suss as smoothness and strong convexity constants are localized to the convex hull of the traveled iterates. This localization arises from our adaptive stepsize strategy, which employs line-search procedure tailored to local geometries, yielding more favorable dependencies on optimization parameters and thus enhanced convergence guarantees. (iii) Numerical experiments demonstrate superior performance of the proposed adaptive algorithm in convergence speed and scalability compared to existing non-adaptive methods.
1.1 Notation and paper organization
Capital letters denote matrices. Bold capital letters represent matrices where each row is an agent's ' variable, e.g., X = [x1,--.. Fmm] [ For such matrices, the i-th row is denoted by the corresponding lowercase letter with the subscript i; e.g., for X, we write æ; (as column vector). Let S"h, "T and ST4 be the set of m (real) symmetric, symmetric positive semidefinite, and symmetric positive definite matrices, respectively; At denotes the Moore-PPnrose pseudoinverse of A. The eigenvalues of W E St are ordered in nonincreasing order, and denoted by X₁ (W) 2 ... -2 bmWW). For two operators A and B of appropriate size. (AoB)( stands for A A(B())) We denote: [m]] = [1.....m. for any integer m 2 1; [x]+:= max(x, 0), E IR; 1m E I is the vector of all ones; I. (resp. 0m)) the m x m identity (resp. the m m zero) matrix; the information on the dimension omitted when not necessary; null(AA (resp. span(A)) (A))
)) is the nullspace (resp. range space) of the matrix A. Let (X,Y) == (r(XTy Y). for any X and Y of suitable size (tr())) ) is the trace operator; and || == //MX, X). for any symmetric, positive definite M and X of suitable dimensions. We still use |||]las when M is positive semidefinite and X E span(M).
Problem Setup
We investigate Problem (P) over network of [m] agents, modeled as an undirected, static, connected graph 9 = ([m),)) E), where (i E if there is communication link (edge) between and j. For
each agent i, we define by N₁ = {j= | [i,j) E E, for some i E [m]] U (i] the set of immediate neighbors of agent i (including agent itself).
Assumption 1. (i) Each function ft in (P) is L-smooth and u-strong convex on R", for some L E (0, oo) and μ (0, oo); and (ii) each agent i has access only its own function fi-
The following matrices are commonly utilized in the design of gossip-based algorithms.
Definition 2 (Gossip matrices). Let Wi denote the set of matrices W [Waj]")= that satisfy the following properties: (i) (compliance with G) Wij > 0 if (i,j) E E; otherwise Wij 0. Furthermore, W.; 0, for all E [ml] and (ii) (doubly stochastic) W E Sm and W1, = 1m
These matrices are standard in the literature on decentralized optimization algorithms, and several instances have been employed in practice; see [34, 41, 33] for some representative examples. Notice
3

---

that for any W Wg (assuming G connected) it hold: (i) (null space condition) mull(Im W)
span(lm); and (ii) (eigen-spectrum distribution) 2/ W + 1 Om
Algorithm Design
Our approach solving Problem (P) involves saddle-point reformulation tackled via variable metric operator splitting, implementable across the graph G. The innovative aspect of the proposed method lies the selection of the variable metric that, coupled with a Forward Backward Splitiing (FBS), enable adaptive stepsize selections through decentralized line-search procedures.
Introducing local copies H; E I of the shared variable æ (the i-th controlled by agent i), and the stack matrix X == [T1...., Fml" Rmxa, let us consider the following auxiliary problem:
min XeRmxx
F(KX) = [((X))) S.t. EX= =0 0.
(P')
Here, E and K are m x m matrices that meet the following criteria: (c1) L E Shh and mull(E) = span(1m); (c2) K E S and null(7- K) span(1m): and (c3) and commute. Conditions (c1) and (c2) ensure that (P) and (P") are equivalent. Specifically, any solution X of (P") has the form of X m (x=)² where x² solves (P), and vice versa. While essential, condition (c3) postulated to simplify the algorithm derivation.
Primal-dual optimality for (P') reads, with Y being the dual-variable associated with the constraints,
X* Y = 0, where A = FoFFoR K 0 and B = L 0
t.
(A + B)
Given X Y at iteration k, the update X Yk+l via FBS with metric C E S reads [4]
X (x²²)
(C B)
(y4+1)
(C A)
(1)
Monotone operator theory [4] ensures convergence of (1) under the following conditions:
(c4) B is monotone operator, C' E s and (c5) J - 1-1/2 11-12 is an averaged operator.
Condition (c4) is satisfied by construction; (c5) can be enforced through suitable selection of C 2em while leveraging the co-coercivity of A (implied by Assumption 1). Denoting by a the stepsize employed in the algorithm, we seek for C' with the following structure:
a
C 0
-
with C₁, C2 ST
C2
be determined. We proceed solving (1). Taking (C+ + B) we have
x = (1) (x)*= (()))) + (111) (X*)),
(x*)
(2)
y = -VV) (XV)
where
(T) Im a - -1 -t,,
(II) LDC
(III) = (C2ta. C2,
(3)
(TV) t. C2,
(V) = (Ca+a- "
In addition to satisfying (c5), C₁ E sT. must be strategically chosen to facilitate the design of a decentralized line-search procedure for a. We propose the following guiding principles:
(c6) The range of admissible stepsize values ensuring convergence-henee satisfying (c5)-should be independent of the network parameters; and

---

(c7) the operators (I), (IT). and (III) in (2) should be independent of a.
At a high level, (c6) aims to decouple the line-search mechanism from network-dependent constraints. By doing so, it ensures that performing the line-search from the agents' sides requires no mid- process communications during backtracking, relying solely local computations. Meanwhile, (c7) facilitates the identification of (x(1)) + (111)(Y**) in (2) as potential line-search direction. This direction must be paired with an appropriate surrogate function, which will define shortly,
Among several potential selections, in this paper, we consider the following for C₁ and Cz:
Ci K and C2 = aa=k (c 1--.--+))))
t.²), with < <1/2,
which satisfy all the specified requirements. Using (4) and (c3), the operators in (3) simplify to (T)VFoK, (ITT)= = (IV) = (T), (V) Kt. (I-
Im mm- ot2 (IT)
a
Notice that (4), (IT), and (111) are independent of the stepsize. Substituting the above expressions in (2) and introducing D := -1 LLYY,, the algorithm can be rewritten as
x (I ct. x
-I- (D* VF(KX*)).
D -I- D
a (X*=xVF((XX))
To make the above updates compliant with the graph 9 while satisfying (c1)-(c3), we set L (T- - W), with W Wg. and K = - -- -t.,, where E (0, 1/2) is a free universal constant.
Introducing W (1 I) + cW E Wg. the final decentralized algorithm can be rewritten as x = W x
D D W (D* VV++V(XA+123)
x a #+1122
(5)
D++1 = D k+1/22
1 - -
-VF
Finally, it can be verified that (c6) is met if (Vak-1/2) VF oVaa-a1 is nonexpansive, which holds if a 1/L, being independent on the network parameters. Next, we introduce line-search procedure that enables the use of an adaptive stepsize a rather than a constant one satisfying the above more conservative bound.
Decentralized backtracking: It not difficult to check that -D ++/2 descent direction of [*)) ;= (D* X) at X This naturally suggests the following backtracking procedure for at iteration A; find the largest a 0 such that
Fk (x*+1)= S F* F*(x*+1/2) (x*1/2), x - x
- (6)
2
where d E (0, 1] is a tuning parameter. However, this condition would require a communication round for each backtracking step. To reduce the communication burden, we introduce a local stepsize for each agent denoted by af. determined by backtracking line-search on the local function ff(x) = [xxx) (d/,,) .). Specifically, each of is the largest positive value satisfying
1 S f. (2, ++ 1/2) (V (2. (,112), R+I A+1/2)
-I;
8
k+1
22 2
(7)
20
Clearly a min,e[m] at also satisfies (6). Noticing that l has the same smooth (and strong convexity) constant(s) of Si, one can replace f! in (7) with ft. The proposed decentralized algorithm is summarized in Algorithm 1, with the backtracking line-search procedure detailed in Algorithm 2.
3.1 Discussion
Several comments are in order.
On the proposed algorithm: We emphasize that selecting K ş T. in (P') marks a significant departure from the commonly used saddle-point reformulations of Problem (P), where K Im. e.g., [46, 34, 33, 1]. Choosing K * Im. in conjunction with the novel variable metric C. in the FBS as
5

---

Algorithm
Data: (i) Initialization X Rmxa and D 0; (ii) initial value a-1 E (0, o0); (iii) Backtracking
parameters 8 E (0, 1|0; (iv) nondecreasing sequence {>*}* S [1, (v) Gossip matrix W (1 c) + cW, with W E Wg. and c E (0, 1/2]. Set the iteration index & = 0.
1: () Communication step: Agents updates primal and dual variables via gossiping:
X x k 1/2 W and D D = W (D* 1F((*+11))
2: (S.2) Decentralized line-search: Each agent updates at according to
Backtracking (a--1, ai
k+1/2 1/ -,,1111 .7
1/2
3: (S.3) Global min consenuus
a min k. x
4: (S.4) Local updates of the primal and dual variables:
X X at D
D *+ = D** k+/2 at (x* - x - -VF((++112))
5: (S.5) termination criterion is not met, &t + k and go to step (S 1).
Algorithm 2 Backtracking(o, f. d, 5)
1: a+ = -a;;
2: x+ x + a d; set s
3: while f(x+) > f(x) + (Vf(z), xt -x) + b
2at 1| ==112 do
4: a+ + (1/2)
5:
x+ = x + +
6:
1 1+1;
return a+..
specified in (4), is critical to obtain a valid line-search procedure that is also implementable across the network. For instance, popular decentralized algorithms such EXTRA [42] and NIDS [26] can be interpreted as FBS with suitable metrics associated with the primal-dual reformulation of (P) as (P') but with K- Im- However, these schemes do not facilitate any suitable line-search, as no stepsize- independent descent direction can be identified in their updates. Hopefully, our approach will provide decentralized algorithms, stemming from alternative decentralized formulations of (P) and their corresponding operator splittings.
principled guidelines for the design of other parameter-
On the backtracking: The following Lemma shows that the line-search procedure in Algorithm 2 is well-defined, as long as the function f therein is locally smooth.
Lemma 3. Let in Algorithm be any smmoohh and st-stongyyy convex function on the segment [x. + yad), where I.y (0, Hz E (0,co) and E (1, The following hold for Algorithm 2: (i) The returned at satisfies
)
min ya 2L2/ S <at S min (1a, μt {
S 00.
(8)
Therefore, the backtracking procedure terminates in at most max (1, [logz 2Lga7) t-steps;
(ii) For any at returned by Algorithm 2, any at E (0, a0, also satisfies the backtracking condition.
Notice that the last statement of the lemma guarantees that the each a minje[m] a satisfies the descent property (6) on the global loss Fk, as each at meets the local condition (7).
The sequence {7 Jee used line of the backtracking algorithm, with each ** 1, is introduced to favor nonmonotone, and thus potentially larger, stepsize values between two consecutive line-

---

search calls. Any sequence satisfying Xhth 4 and π=== 7 = co, is advisable. In our experiments, we found the following rule quite effective: >²= ((k+ (k) for some 3n > and B1 2 1. One can also opt for y = L, for all k, thus climinating this extra parameter, if simplicity is desired.
On the min-consensus:: Step (S.3) involves a min-consensus across the network to establish common stepsize, a² = [mn a among the agents. This procedure is easily implemented in federated systems, where server node facilitates information exchange between clients. Interestingly, this min-consensus protocol is also well-suited to current wireless mesh network technologies. Modern networks support multi-interface communications, including WiFi and LoRa (Low-Range) [17, 2, 16]. WiFi allows high-speed, short-range communications, supporting a mesh topology where nodes transmit large data volumes immediate neighbors. Conversely, LoRa facilitates long-range but low-rate communications, ideal for communication flooding that reaches all network nodes in single hop but transmits minimal information. Therefore, in multi-interface networks, the proposed algorithm operates by transmitting vector variables in Steps (S 1) via WiFi, while LoRa is used for the min-con min-consensus in Step (S.3). Furthermore, the values af 's can be quantized to their nearest lower values using a few bits before transmission. Based on Lemma 3(ii), this quantization ensures that the descent condition (6) is still met with the resultant min quantized stepsize. This approach renders the extra communication cost for implementing the global min-consensus step negligible.
For networks where LoRa technology cannot be used, Sec. 5 proposes variant of Algorithm 1 wherein the global min-consensus step (S.3) is replaced by a local min-consensus procedure.
4 Convergence Results
We begin introducing a quantity of interest that helps identifying different operational regimes of the proposed algorithm. Let (X* DD)) be a fixed point of Algorithm (whose existence is ensured by Assumption 1), and let {(X*, D be the iterates generated by Algorithm 1. Define
+ [|(1 W) (VF(X (1122)) + D*)
with M c -I
max
X - X+ D D*
[[ar)
(9)
The following comments are in order. (i) Both D* and D* lie in the span [ - W) = =span| W). for all k; and M is positive defined on this span. Consequently, | D' l1 M > 0 for D* * D
and ||D* D* O if and only if x D (ii) Under Assumption x* 1(x*)( where x* is the solution of (P). (iii) The quantity r*th reflects the algorithm's 's convergence progress through the evolution of the dual variables and consensus error. Rewriting the update of the dual variables as D = ** + (T x c(T W) (VF(X++1/2) + D*), we observe that small values of | ( - [VF((++1/)) + D || compared to | || and |X -X* [I-enccee small p values-indicals slow convergence improvements (see Lemma 8 in the appendix).
We remark that n* need not be known by the agents; it is instrumental only for the analysis and posterior assessment of algorithm performance.
Linear convergence is established below via contraction of the following merit function
V
x
x' + (a D - -D11
(10)
Theorem 4. Given Problem (P) under Assumption 1, let {(x* DD1} be the iterates generated by
Algorithm 1. Then, the following holds
at (
2 (1 min (0),)(*))))) V*,, where pf = a 2
vk+1_ < max
(1-c(1-Am (W)))
1.
(11)
1 < 22/4, then
a k+1
max at ( (1- pŁ) v*,
vk+2 < max
at .1)
(12)
where
(1 c(1 Am Am )
min (nltlaatts at LF < 1.
P =
128(7*)² max(1, Amax Amax(mm)x)) (M))
7

---

Here μt (resp. ) and L are the strong convexity and smoothness constants of (each) fs along the segment [x; k+1/2 x²) (resp. [x; k+1+1/2 ,,'),, respectively.
The theorem establishes linear convergence of Algorithm 1. As m1x faaa//a=-00 /a²= is bounded away from zero and uniformly upper bounded (with value depending on the sequence {-²}) {-se Lemma 3-the convergence rate is predominantly determined by {of), {pr}, and {r*). Notice that, in the setting of the theorem, each o .2 E [0, 1). Intriguingly. the algorithm exhibits different operational regimes based on the range of values rdt takes along the traveled trajectory. At the high level, if r remains "large", faster convergence can be guaranteed, as certified by (11); otherwise V decreases every two consecutive iterations (see (12)), yielding to slower convergence. The number of iterations required to reach a desired termination accuracy is given next.
Corollary 4.1. Instate the setting of Theorem 4, with now {n*) being chosen such that 7* S
((k: + B1) + 1)) 80 for all and some 31 1, B2 > 0. Then
- 41,2
D k+1 D' Se,
for all k 2 Ne. where N₂ is given as follows:
1fr 2 rlow == 1 min
for all k
v2
2
v (M5)
N₂ = 0 (b max
c(1 - >a(W) (1 c(1 Am bm()))) 10g(1%/e)
(13)
otherwise,
N₂ No
Am (W)))) ) log(V"/ /t)
(14)
Here k. is the condition number of each f; restricted to the convex hull of (x*, (x : and hides the dependence on 31 and 32.
o
Corollary 4.1 identifies the following two different operational regimes of the algorithm, resulting in difference performance based upon the network connectivity and optimization condition number.
(1) Strong connectivity regime: when nK 2 Tlow. for all k a fact that numerically has been observed for 'relatively good' network connectivity, the convergence rate exhibits separation in the dependence on the network and optimization parameters. Since c(1 - Am (W)) > 2c,
follows that, when c(1 - >²(W)) 2 (1 - 2c)/ VR, N reduces to O(k) (omitting the dependence on E), which matches the complexity of the centralized gradient algorithm. This suggests scenarios where the optimization problem is harder than consensus problem over the same network, resulting in the bottleneck between the two. Conversely, when the condition number λ large relative the network connectivity 1 - >x)W), the rate is determined by that the consensus algorithm running on the same network, that is, O((1 >2 -1) The above rate separation property mirrors that of certain nonadoptive primal-dual decentralized schemes including NEXT [10), AugDGM [47], Exact Diffusion [49] (with rate expression as improved in [46]), NIDS [26], and ABC [46].
(2) Worst-case regime: This regime reflects the algorithm's worst-case performance, typically registered in "weakly" connected networks: the convergence rate reads O(k/(1 - >2)))),, where optimization and network parameters are now mixed. This rate aligns with those of nonadaptive decentralized pradient-trackinn schemes, such as DGing [35], SONATA [43] (subject to sufficiently small network connectivity), and [38].
In summary, the convergence rate of Algorithm resembles in the form that of existing nonadaptive decentralized methods, but offers more favorable dependence on the condition number than that typically found in those algorithms. Specifically, the condition number in (13 and (14) ) is the local condition number, defined on the convex hull of the trajectory, which is generally much smaller than the global condition number governing decentralized algorithms in the literature. This demonstrates the algorithm's 's capability to adapt the local geometry of the optimization problem.
8

---

From Global to Local Min- Nin-Consensus
This section extends Algorithm to settings where the global min-consensus procedure in (S.3) is not implementable. For these cases, we propose to replace such a step with a local min-consensus procedure. The new algorithm is formally described in Algorithm and briefly commented next.
In step (S.3), each agent now computes its stepsize taking the minimum values among those of their immediate neighbors only (including itself). This produces possibly different stepsizes a for each agent, collected in the diagonal matrix A diag(a (a ... o.h) Because of that, in order to still guarantee D span(? - a key property for the convergence of the algorithm-we slightly modified the updates of the dual variable in (S 4), compared with the same step in Algorithm 1. Specifically, the updating direction of the dual variable as in Algorithm 1, (a*) ) X
a ( is replaced in Algorithm 3 by (A*)-1** X k++1/3
(F((++1/2), where
X 1 W (x*)- Notice that, if all the stepsizes are equal, the update (S.4) 4) in Algorithm
reduced to that in Algorithm Finally, we point out that the computation of x requires only the extra communication of neighboring stepsizes (thus scalar) values, which has a negligible cost.
Algorithm 3
Data: (i) Initialization X E Rmxn and D = O; (ii) initial value a E (0, oo); (iii) Backtracking
parameters 8 E (0, 1]; (iv) nondecreasing sequence {>*}& S oo) (v) Gossip matrix :=
(1 cm + cW, with W E Wg. and c E (0, 1/2]. Set the iteration index k = 0.
1: (S.1) Commuicattion step: Agents updates primal and dual variables via gossiping:
x ++1/2 W x and D 1 w (D -F((x+113)
2: (S.2) Decentralized line-search. Each agent updates az according to
Backtracking (a"-1, 2 k+1/2 1,+1/2 ,n ,,, 26)
3: (S.3) Local min-consensus:
of min a5, Vi e [m]: JEN:
Define A = diag(of o:)::
4: (S.4) Local updates of the primal and dual variables:
x = x A D 1+122 xk+1/2 W -A*)-
D k + (A+)
x k-1/2 VF
5: (8.5) If termination criterion is not met, k
and go to step (S 1).
Convergence of Algorithm is established in the following theorem. Theorem 5. Instate assumptions in Theorem 4, applied now to Algorithm 3, with {n being chosen such that ** < ((k + 81)/(k + 1)) 82 for all k and some 31 2 1, B2 > Further, suppose there exists a constant R > O such that V < for all k. Then
min JEL
X X +
D D
DD SE,
4L
with
N O (max (log dg + log Ne, Lo max(Ne dg)), where N₂ is defined as Corollary 4. (replacing therein Vo with R).
Interestingly, Theorem 5 states that the degradation of the convergence rate when a local-min consensus is used instead of the global one is mild. Specifically, up to log factors, the total number of iterations to e-optimality depends on de (the diameter of the graph 9), dg > N This result somehow expected, as min-consensus requires a number of iterations proportional to dg to propagate through the entire network. However, monotonicity in the decrease of the primal and dual errors can no longer be guaranteed when min-consensus is employed.

---

Numerical Results
This section presents some preliminary numerical results. We compare Algorithm 1 and Algorithm with EXTRA [42] and NIDS [26] on ridge regression problem using synthetic data. Further experiments are presented in the appendix. All experiments are run on Acer Swift 5 SF514-55TA- 56B6, with processor Intel(R) Core(TM) i5-8250U @ CPU 1.60GHz, 1800 MHz.
Ridge regression: It is instance of (P), with fx) ||A,z; b, 21 a1|2:112. where set A, E 20000 b, E IR.20 and o = 0.1.The elements of A,, b, are independently sampled from the standard normal distribution; the regularization is a 0.1. We simulated network of 20 agents, and the following three different graph topologies, reflecting varying connectivity levels: (i)
G1: Graph-path with m - edges and diameter m - i... 9 = {[m], { l))==""; (ii) G2: Erdós Rényi graph, sparsely connected; and (iii) Gy: Erdös-Rény' graph, well-connected.
Results are summarized in Fig. and Fig. 2. For EXTRA and NIDS we use grid-search tuning. chosen to achieve the best practical performance. Algorithm and Algorithm are simulated under the following choice of the line-search parameters satisfying Corollary 4.1: 7tt (k + 2)/ + 1),
5 = 1. For all the algorithms we used the Metropolis- weight matrix W E 59w [34].
1.7
12a
10'
11P
10
10
Alger thm
Aigonthhm
Aggeritmm
Alger Unn
Aigonithm
Aggrrihnn
(uned]
2003
1509
2003 2006
10300
3300
2005
2030
1000
33500
2000
2030
5000
33500
frerations
(a) Line Graph
(b) Erdós Erdös-Rényi Graph, = 0.1
(c) Feddös-Rény: Graph, p = 0.5
Figure 1: Ridge regression different graphs: (Ia) Line graph; (1b) Brdös-Rényí Graph with edge activation probability p 0.1; (Ic) Erdös-Rényi Graph with edge activation probability p 0.5
Algun trm
Aiganithn
Alganithn
NiUb (frelunss)
fins-iariel) (fieetuned)
HESS (ime-lured))
$200
$002
6000
6000
6000
2000
439 Condiionn Number
Condition Number
Condrion Number
(a) Line Graph
(b) Erdös- Graph, 0.1
(c) Erdōs-Rényi Graph, p 0.5
Figure 2: Ridge regression: Number of iterations N for X - X < 10 versus the condition number of
agents' looses different graphs; (2a) Line graph; (2b) Erdös-Rényi Rényi Graph with edge activation probability p 0.1; (2c) Frdös-Rényí Graph with edge activation probability p = 0.5
The figures demonstrate that the proposed method consistently outperforms both EXTRA and NIDS, even when using the local min-consensus strategy, with significant gap emerging as the condition number increases. This performance is particularly noteworthy given that Algorithm and operate effectively without requiring tedious tuning or global knowledge of the optimization and network parameters. Notably, Algorithms and 3 exhibit different convergence behaviors: as predicted by Theorem 5, local min-consensus results nonmonotonic error dynamics || X+ However, the practical convergence speed remains largely unaffected compared to the global min-consensus.
Acknowledgment
The work of I. Kuruzov has been supported by the Grant No. 70-2021-00144 01. 1.22211 IGK 000000D730322P540002
10

---

References
[I] S. A. Alghunaim, E. K. Ryu, K. Yuan, and A. H. Sayed. Decentralized proximal gradi- ent algorithms with linear convergence rates. IEEE Transactions on Automatic Control, 66(6))2787-2794, June 2021.
[2] A. Askhedkar, B. Chaudhari, and M. Zennaro. Hardware and software platforms for low-power wide-area networks, page 397-407. Elsevier, 2020.
[3] J. Barzilai and J. M. Borwein. Two-point step size gradient methods. IMA Journal of Numerical Analysis, 8( 8(1):141-148 1988.
[4] H. H. Bauschke and P.L. Combettes. Convex Analysis and Monotone Operator Theory in Hilbert Spaces. CMS Books in Mathematics. Springer New York, New York, NY, 2011.
[5] Y. Carmon and O. Hinder. Making sgd purameter-free. In Proceedings of Thirty Fifth Conference on Learning Theory, volume 178 of Proceedings of Machine Learning Research, pages 2360- 2389. PMLR, 02-05 Jul 2022.
[6] T. Chang, M. Hong, H. Wai, X. Zhang, and S. Lu. Distributed learning in the nonconvex world: From batch data to streaming and beyond. IEEE Signal Processing Magazine, 3763):26-38, 2020.
[7] X. Chen, B. Karimi, W. Zhao, and P. Li. On the convergence of decentralized adaptive gradient methods. In Asian Conference on Machine Learning, pages 217-232. PMLR, 2023.
[8] X. Chen, X. Li, and P. Li. Toward communication efficient adaptive gradient method. In Proceedings of the 2020 ACM-IMS Foundations of Data Science Conference, page 119-128, Virtual Event USA, October 2020. ACM.
[9] A. Cutkosky and H. Mehta. Momentum improves normalized SGD. In Hal Daumé III and Aarti Singh, editors, Proceedings of the 37th International Conference on Machine Learning, volume 119 of Proceedings of Machine Learning Research, pages 2260-2268, PMLR, 13-18 Jul 2020.
[10] Di Lorenzo and G. Scutari. NEXT: In-network nonconvex optimization. IEEE Trans. Signal
Inf. Process. Neww, 2(2): June 2016.
[11] Duchi, E. Hazan, and Y. Singer. Adaptive subgradient methods for online learning and stochas- tic optimization. In Proceedings of the 24th International Conference on Neural Information Processing Systems, pages 257-265, 2011.
[12] Iyanuoluwa and Chinwendu E. Q-linear convergence of distributed optimization with barzilai-borwein step sizes. In 58th Annual Allerton Conference on Communication, Control, and Computing (Allerton), pages 1-8, 2022.
[13] Gao, XW. Liu, YH. Dai, HUang Y., and P. Yang. Achieving geometric convergence for distributed optimization with barzilai-borwein step sizes. Sci. China Inf. Sci., 65: 15:1449204, 2022.
[14] J. Hu, X. Chen, L. Zheng, L. Zhang, and H. Li. (rectified version) the barzilai borwein method for distributed optimization over unbalanced directed networks. 1.Xiv:2335.1146600 2024.
[15] M. Ivgi, O. Hinder, and Carmon. DoG is SGD's best friend: A parameter-free dynamic step size schedule. In Proceedings of the 40th International Conference on Machine Learning. volume 202 Proceedings of Machine Learning Research, pages 14465-14499, PMLR, 23-29 Jul 2023.
[16] T. Janssen, N. BniLam, M. Aemouts, R. Berkvens, and M. Weyn. Lora 2.4 ghz communication link and range. Sensors, 20316), August 2020.
[17] D.H. Kim, J.Y. Lim, and J.D. Kim. Low-power, long-range, bigh-data transmission using wi-fi and lora. In 2016 6th International Conference on IT Convergence and Security (ICFFCS), page 1-3, Prague, Czech Republic, September 2016. IEEE.
[18] D. Kingma and J. Ba. Adam: method for stochastic optimization. CoRR, abs/ 191.6990,,,
2014.

---

[19] P. Latafat, A. Themelis, and P. Patrinos. Adaptive proximal algorithms for convex optimization under local lipschitz continuity of the gradient. arXiv preprint arXiv:2301.04431 2023.
[20] Latafat, A. Themelis, and P. Patrinos. On the convergence of adaptive first order methods: proximal gradient and alternating minimization algorithms. arXiv preprint arXiv:2311.18431, 2023.
[21] Li, X. Chen, S. Ma, and M. Hong. Problem- Gooblem-parameter-iie decentralized nonconvex stochastic optimization. arXiv preprint arXiv:2402.0888; 2024.
[22] T. Li and G. Lan. A simple uniformly optimal method without line search for convex optimiza- tion. arXiv preprint arXiv:2310.10082, 2023.
[23] T. Li, A. K. Sabu, A. Talwalkar, and V. Smith. Federated learning: Challenges, methods, and future directions. IEEE Signal Processing Magazine, 37(3):50 00:00-600200 2020.
[24] X. Li, B. Karimi, and P. Li. On distributed adaptive optimization with gradient compression. In International Conference on Learning Representations (ICLR), 2022.
[25] X. Li and F. Orabona. On the convergence of stochastic gradient descent with adaptive stepsizes. In Proceedings of the 22nd International Conference Artificial Intelligence and Statistics (AISTAT). PMLR, 2019.
[26] Z. Li, W. Shi, and M. Yan. A decentralized Sokimal-gradient method with network indepen- dent step-sizes and separated convergence rates. IEEE Transactions on Signal Processing. 67(17 67(17):4494-4506 2019.
[27] X. Lian, C. Zhang, H. Zhang, C. Hsieh, W. Zhang, and J. Liu. Can decentralized algorithms outperform centralized algorithms? A case study for decentralized parallel stochastic gradient descent. In Advances in Neural Information Processing Systems, pages 5330-5340, 2017.
[28] P. Di Lorenzo and G. Scutari. NEXT: In-network nonconvex optimization. IEEE Transactions on Signal and Information Processing over Networks, 202):120-136, 2016.
[29] L. Luo, Y. Xiong, Y. Liu, and X. Sun. Adaptive gradient methods with dynamic bound of learning rate. In Proceedings of the 7th International Conference on Learning Representations, New Orleans, Louisiana, May 2019.
[30] Y. Malitsky and K. Mishchenko. Adaptive gradient descent without descent. In International Conference Machine Learning, 2019.
[31] Y. Malitsky and K. Mishchenko. Adaptive proximal gradient method for convex optimization. arXiv preprint arXivv2308.02236 2024.
[32] Nazari, D.A. Tarzanagh, and G. Michailidis. Dadam: consensus- baased distributed adaptive gradient method for online optimization. IEEE Transactions on Signal Processing, 70:6065-6079, 2022.
[33] A. Nedic. Distributed gradient methods for convex machine learning problems in networks: Distributed optimization. IEEE Signal Processing Magazine, 37(3):22-101, 2020.
[34] A. Nedić, A. Olshevsky, and M. Rabbat. Network topology and communication-compptaaiii tradeoff's in decentralized optimization. Proceedings of the IEEE, 106:953-976,, 2018.
[35] A. Nedić, A. Olshevsky, and W. Shi. Achieving geometric convergence for distributed op- timization over time-narying graphs. SIAM Journal on Optimization, 27:2597-2633, July 2016.
[36] J. Nocedal and S. Wright. Numerical Optimization. Springer, 2 edition, 2006.
[37] B.T. Polyak. Minimization of unsmooth functionals. USSR Computational Mathematics and Mathematical Physics, 93)):14-29 1969.
[38] G. Qu and N. Li. Harnessing smoothness to accelerate distributed optimization. IEEE Transac- tions on Control of Network Systems, 5(3):1245-1266 Sept 2018.
12

---

[39] S. Reddi, Z. Burr Charles, M. Zaheer, Z. Garrett, K. Rush, J. Koneven, S. Kumar, and B. McMa- han. Adaptive federated optimization. International Conference Learning Representations (ICLR), 2021.
[40] S. J. Reddi, S. Kale, and S. Kumar. On the convergence of adam and beyond. In International Conference on Learning Representations (ICLR), 2018.
[41] A. H. Sayed. Adaptation, learning, and optimization over networks. Foundations and Trends in Machine Learning, 7:311-800 January 2014.
[42] W. Shi, Q. Ling, G. Wu, and W. Yin. EXTRA: An exact first-order algorithm for decentralized consensus optimization. SIAM J. on Optimization, 25(2):944-966, November 2015.
[43] Y. Sun, G. Scutari, and A. Daneshmand. Distributed optimization based on gradient- gradient-tracking revisited: Enhancing convergence rate via surrogation. SIAM J. on Optimization, 32:354-38. 2022.
[44] R. Ward, X. Wu, and L. Bottou. Adagrad stepsizes: Sharp convergence nonconvex landscapes. The Journal of Machine Learning Research, 21:1-30, 2020.
[45] R. Xin, S. Pu, A. Nedic, and U. A. Khan. general framework for decentralized optimization with first-order methods. Proceedings the IEEE, 108(11):1869-15 November 2020.
[46] Xu, Y. Tian, Sun, and G. Scutari. Distributed algorithms for composite optimization: Unified framework and convergence analysis. IEEE Transactions on Signal Processing, 69:3555 2021.
[47] Xu, S. Zhu, Y.-.. Soh, and L. Xie. Augmented distributed gradient methods for multi- agent optimization under uncoordinated constant stepsizes. In Proceedings of the 54th IEEE Conference on Decision and Control, pages 2055-2060, 2015.
[48] Xu, Zhu, Chai Soh, and L. Xie. Convergence of asynchronous distributed gradient methods over stochastic networks. IEEE Trans. Automat. Contr,, 63(2):434-448, 2017.
[49] K. Yuan, B. Ying, X. Zhao, and A. H. Sayed. Exact diffusion for distributed optimization and learning-pan sertingg-artiiio i: Algorithm development. IEEE Transactions on Signal Processing, 67(3)7708- 723, 2018
[50] D. Zhou, Ma, Jnd Yang. Adabb: Adaptive barzweai-borwein method for convex optimization. arXiv preprint 4rXhv:2401.08024,200 2024.
13

---

Appendix
A Proof of Lemma 3
The proof of the lemma is quite standard, and it reported here for the sake of completeness.
(i) Smoothness of f implies that Algorithm 2 terminates when at I L.L Therefore, it must be Furthermore, it follows from the strong convexity of f that (2(2+t p/2; at 2 min(6/2L,, hence, a+ I min(8/p, pu, ya.). This proves (8).
Further, by the lower bound above, one infers that the backtracking procedure terminates when at I 1. Noting that a+ = 2 2- we deduce that = logg 20,
interations suffice.
8
(it) Let d(a) f(r ad). Notice that ó is convex and d'(0) (Vf(x), The termination condition in Algorithm 2 can be equivalently rewritten in terms of Φ as
8
<(a - (00) + (0))) at + +a 2 _lld
(15)
Given x E [0, 1], let ā = >a Invoking convexity of o, we can write
((a) = Φ (Aa+* + + -1- (1-) S >x(a*) + + A)o(0)
5
- (0)) + (0) (Aa=t) + (Aa+))
)
2
which completes the proof.
B Proof of Theorem 4
We begin establishing the dynamics of V defined in (10) along two consecutive updates.
Lemma 6. The following holds along the update (D* x + (D++1, x++1);
pk+
X x+1 + ) D*
|X X 1| (a ( D b 113
(16)
2 (VF VF(X'), x
Proof. See Appendix E.I.
Using the properties of the backtracking procedure (Lemma 3) and leveraging strong convexity and smoothness of F, the inner product in (16) can be bounded as follows.
Lemma 7. The following holds:
(VF(x*1122) VF(X*), X -
S
8
x
X 12
2a
max
1
1
V + +
2L
where 4h (resp. L* is the strong convexity (resp. smoothness) constant of each f, along the segment [a 1/1 x²).
Proof. See Appendix E.2.
Combining Lemma 6 and Lemma 7, after some algebraic manipulation, we obtain the following.
Lemma 8. In the setting above, it holds
k++ < X x
-
a
-x112 L IVF + +DD1P²) max |1aa+11x++1/2
(17)
-8 (1x (a ool (VE(x--1)) + D*) (1))
(VF(X*+1/2)
M
14

---

Proof. See Appendix E.3.
Lemma 8 suggests the path for the rest of the analysis: the decrease of Vk+1 relies on the values of the terms
| Beal cu-ww + w)) (VF(X++1))) + D* |
and
a IVF + D'13
max
relative to the the primal and dual optimality gaps | 1 and (a D At the high-level, one can say that "higher" values of such quantities relative to || D - D* determine larger decrease of y
D D* li, respectively.
X X+1 and
The above argument be formally recorded by the following quantities:
2 |o[ W) (VF(X*+1/2) DD)
(a
| c(I-W)
+
M
(18)
max
X X+ I1, D MM
and
gº max
X
X+1.
VF(X (1())++12)++0 +
(19)
D
D
Using n* and g in (17), the next lemma establishes contraction of Vk+1, with a contraction factor depending in particular on such quantities. Lemma 9. The following holds
a
V++1 < max
( (1 min (pi:5*)) Vē,
(20)
where
a
p 2 (1-c1- Am (a1-)((W)) <
and
8(r3)3 22 min a o(1 Am 111-Am(WW)) (W)))²
ch : max
2
Proof. See Appendix E.4.
The final expression (11) Theorem 4 follows easily from 5h 2 8(14))2
The above result ensures "sufficient" descent of b*+1 when n* (or g²) is large enough. However, the contraction factor in (20) becomes vacuous for arbitrarily small values of (or g*).
Next, we examine the unfavorable case where both n.t and g are "small", leading to the proof of the decay of yk-1 as stated in (12) of Theorem We build on the following key property of the sequence g in this scenario: under low p values, if g is "small", the subsequent value g*+1 cannot become arbitrarily small.
Lemma 10. Suppose
1 - 11-4/2
V2
and g+ < min
2 / (14)
(21)
Then,
x X 1
2g / /mmax (M)
(22)
(a
D
1
Aunae (M)
1 p /2
Proof. See Appendix E.5.
15

---

We infer from Lemma 10 that
X X*
A+1
a k+1
D
D- AM
(1 2g Amax (M)
7 (M)
1-r /2
where we used a²/aa* R+1 2 1/7 (due to a h+1 I a* sec Step I of Algorithm 2). Notice that (i) the term in the parenthesis will be around one for small enough values of gd and r*: and (ii) the sequence {f²} } is chosen being eventually uniformly lower bounded. Therefore, the above bound implies that r and ge cannot both progressively diminish along the iterates. Consequently. in the unfavorable scenario described by (21), Vk+1 still decreases, albeit over two consecutive iterations. This outcome is formalized in the following lemma
Lemma 11. Suppose condition (21) holds. Then,
h+1
at 1) 2
2 ak a ) (1- pb) v*,
v max
max
(23)
where
k+ k+l (1 c(1 - Am (W))
( 20 /Amux (M) 1.
p2
2 max( Ammax (M),
ph /2
Here, 4 is the strong convexity constants of (each) fi along the segment [a] (++1)+1/2
x
Proof. See Appendix E.6.
The final convergence result as stated (12) is obtained using Lemma and Lemma 11, with the variable g², absorbed, as outlined next. We strengthen condition on n* in (21) by n S v2/4. We consider two cases for the value of g² in the above scenario. Specifically, (Case 1) g is bounded away from zero, implying ç* in (20) to be so. Therefore, (1 min (*) < 1. This will be sufficient to ensure enough descent for yk++1, though in two consecutive iterations. (Case 2): g may be arbitrarily small; in this case, f in (23) remains bounded away from zero, ensuring contraction though from 4 p More formally we have the following.
Case 1: Consider (20), under (21) strengthened by rK S v2/4. If
g 2 min 8 (
8
(24)
then
c(1 - Am (W)))²
1
min (pn.
16 max 8Amax (M1) min fraa at a
Using lower bound above in (20), yields
k+1
(attl ( at
2
at a (1 (1- V4,
v < max
at 1
pk+1 S max
,1
max
with
11-(1 Am (W))
pf 16 max(1, &A (M)) min H p "a*
(25)
Lk
Notice that if the interval of admissible values for gh, as specified by (21) and (24) is empty, this case does not apply.
Case 2: Consider (23) under (21) strengthened by nk v2/4. If
< gh < min
1, 8 (imaaxa
16

---

then
29 v //max (M)
v2v22
2'
where we used p* 22/4. This implies
0 1 k+1 c(1 Am (W)) 2
8()k)2 max max(Xmax (M), 1)
Using this lower bound (23), yields
a ak 11 max
at (a=111) (1- P3) Vk,
vk+2 max
with
(m (W]))
4 + a
p
(26)
8 mmax(Xmax (M)) 1)
(7*
Combining Case and Case above- tarvee-tkinngg.o.o the minimum between (25) and (26) and using the fact that 7thh 1, leads to the desired decay of Vk+1 as in (12).
This completes the proof of Theorem
C Proof of Corollary 4.1
Let us consider the first N iterations of Algorithm 1. Let us denote by L and μ the constants of smoothness and strong convexity of each fi restricted to the convex hull of {x*, (af 24 We proceed lower bounding p and p given in Theorem 4. We will use the following facts:
k+1/2 1 )
k+1 a I Zzx
a 2 8/(2T), a 8/1, and
due to Lemma 7, and given Amax (M)xxMM = (c(1 - A2 (2) 1,
1
(mx)) 2 c(1 - >2))) and
2 c(1 A2(W)).
Amax
We can bound p and p
(1 - c(1 - Am (W)) 2
c(1 x2()))
p 2 8 1b 4L
(1-c(1-Ammm (W)))² and
3 8 L
Vk S N.
256(>*)2
(27)
Using (27), we can simplify the rate decay of V N in Theorem 4 as follows.
Case 1: Suppose
(11
2 Flor = 22
min 2'
Wk 2 N.
(28)
V'
Substituting the lower bounds of pt and n in (11), we obtain the following simplified convergence
rate:
V
II
1
5 min
1 (1 (1-cd c(1 Am (w)) ,c(1 - xe(W))) Vo.
I
k==
Case
2: Condition (28) does not hold. For the values of Io such that nu
min
/ we can use (12). Substituting threin the lower bound for P2 and
21 \/max(M) (M)
*
((k: (kk 1))32 2 gf2 yields
(1 (1- c(1 - Am (W))) (2 H
vk+2 < (t/z))2)² 1
T. vt
(29)
256 2
17

---

On the other hand, for i such that n*t iterations, we have vk+2 <(7+t))8yk-
min
(mmmmc()) (31)
using (11) on two consecutive
v2
(zgghti)²
8
(1 [1-(11 c(1 Am (W))) : A2 >((11)) r*
1
min
8
c(1 - Am (w)) (e() >2(W)) -
4)) v*.
6
(30)
256
Therefore, in either situations of Case 2, one can ensure contraction after two consecutive iterations by a factor
8 (1 c1 Am (W))) ((x))(())())) 1 1.
2 22
Using Vk+1 S ( we can merge (29) and (30) as follows:
[N/2]
VV
II +++
1
(1 - Am (W))) 72
V
256,3
N-1
(1
(1-00- Am
W
Pa(1 X2
(N-1)/2
II *+))
256,3
L
k=0
N-1
(1-001-0-
(1-6
c(1 Am
(W)))a((1 - >2( /1 11)
())
N-1
Vo
512
k=
Case 1 Case 2: We can combine the rate expressions derived in the two cases above as follows:
NN-1
VN
<
II
* (1- N-
k=
where
min
11
(1 c(1 Am (W))) c(1 >2((W))
if
v2 min
( ('nnmaa(M))
for all k;
4L
6 c1 Am (W)) -c((11>2(WW))
else
L'
Notice that p E 1).
Finally, we can obtain the desired asymptotic convergent rate noting that the growth of II, 7 is dominated by the geometric decay of the contraction factor. This is formalized next.
Lemma 12. Le = ((k + f1) + 12 with 31 2 1, B2 2 0. Then the following holds:
N-1
II
x < 8 1 12(
(31)
k=
Furthermore, for any given p E (0, 1), have
N
2
II
(1- (I- (11
(32)
k=
for all
3 + 48,3, 83,32
> No
max
2,32(T311 + 1) +1)
18

---

Proof. See Appendix E.7
Inequality (32) provides the asymptotic rate expression, as stated in the corollary where O hides the dependence on 31 and 32.
D Proof of Theorem 5
We begin noticing that the stepsizes in Algorithm are identical across agents, Algorithm 3 reduces to Algorithm 1. For the iterates where this happens, one rely the convergence guarantees established for Algorithm Specifically, we have the following result, whose proof is straightforward.
Lemma 13. Suppose that exists some kg 2 1 such that a Then one can guarantee
am for k he...., ke Ne.
X X
1 - S.
412
where Ne is defined as in Corollary 4.1 (replacing therein v with Vk=)
The remainder of the proof focuses on characterizing the properties of certain key events identified as detrimental for the local-min consensus algorithm to achieve convergence. We will demonstrate that the occurrence of such events within N consecutive iterations is of the order of log N, indicating that these are sporadic events relative to the total of N iterations.
Given af s, defined in Step (S.3) of Algorithm 3, let denote their minimum across all agents at time k: as
min o EE m)
min
If the backtracking loop (steps 3-6 in Algorithm 2) is not activated at iteration A 1 in any of the agents' local line searches, then all output stepsizes at will increase by the same factor 7*t that is, af = >=aa, k- hence, does a On the other hand, if all stepsizes are consensual at iteration k: 1 and the backtracking procedure at some of the agents' side enters its steps- 3-6, "desynchronization" of the stepsizes occurs. This event can be detected by the condition
an <7
a
k-1 min
When the stepsize at time k 1 not consensual, the condition above identifies increases in stepsize disagreements from iteration i- to k; measured by
max O ]E(m]
O'min
k-1 7*t max oj Cr k-11 (j((m)
This motivates the definition of the following index set: given N = 1,2,.... k-11
In = {K E [M] oiin < x
The key properties of interest of this set are summarized below. ..., the following statements hold:
Lemma 14. For any given N- 1,2....,
1. If af aiin for all i [m]. and k + 1 & IN, then a k+1 k+1 o for all i E [m]]
2. If E IN, N- dG. and k + 1, k dg $ In. then a ktdd k+do
a'inn for all i E [m];
3. Iv/ max [DnaL In N * In 3.).
Proof. See Appendix F.I.
words, the first statement confirms that consensus on the stepsizes is maintained if none of the local backtracking procedures are triggered. The second statement ensures that, the local-min consensus algorithm requires at most de iterations to converge, from any initialization, provided that during those iterations no backtracking events alter the minimum stepsize across agents. Lastly, the third
19

---

assertion provides limit on the maximum number of detrimental events that can occur during the N iterations under consideration. If this number is small relative N, a fact that will be proved shortly, one we can find (multiple) window(s) of consecutive iterations wherein the stepsizes remain consensual across all agents. Within these windows, Lemma 13 can be applied, to establish convergence. This idea is formalized next.
Lemma 15. Suppose V S R. Then,
min JELLN++]
x-1 + 4L2
D - S,
(33)
if
N
>
(34)
No + dg
Here, Ng is defined in Corollary 4.1 (replacing therein Vo with Rt.
Proof. See Appendix F.2.
To finalize our proof, let us simplify an upper bound of [Iv] when 7* simplicity, we consider the case N 2 1. Invoking Lemma 12, we have
k+ k41
-For the sake of
31 2 S
In + In
In + 82(131] 1) In 31 + B2(1 NN
(2(181] 1) In 31 8o - 1) In In N
=g N, where the constant & depends on the algorithm parameters. Therefore, one can guarantee (33), under the following condition
N
2 No + dø.
(35)
In N + on
A sufficient condition for (35) is
N
max(s, 1) max (Nex dg).
max (In N, In agT.
Let No be the smallest iteration for which the above inequality holds. Then, N Ommax [log dg + log No. log L) max(Ne, dg)).
E Proof of the Intermediate Results in Appendix B
E.1 Proof of Lemma 6
Let us rewrite pk++1 in terms of | 1 and - D* link back V*:
pk++
X
x X+1 + (a ) 1*1
| x 1 2 (a | D 1
(36)
(x
x x x x -2 (a (D k+ D* D*
D
term II
where the equality follows from ||a||2 |661
||0 b12 2(a, b-), a).
Notice that the negative terms on the RHS of (36) will contribute to the decrease of Vk+1 We are thus left to deal with term and term II. The idea is to bound them that they can overall being controlled by the backtracking inequality.
20

---

Let us proceed bounding term and term II using the algorithm dynamics. We have the following:
term I= (X* - a D X x x x a (VF(x*+12) x X
= (x* -
- X x + (Di-1-D'
- D D X*)
(37)
aa -
VF(X') X x
where in the second equality we used VF(X*) = - Note that the last term in the expression above can be controlled through the backtracking procedure. Hence, we proceed bounding term to "cancel" out the other terms on the RHS of (37). Specifically,
term II = 0* D -D" D*, -1 ( (- (D -D - + a - a²Dát1)
=- a² (DetI-D -D", X a VF - a a - -x))
(38)
a² (D*+1- - x*, -x),
where we used the update of X k+1 and the facts D E span(I-W) and X E mull([-W).
Summing up (37) and (38), obtain
term I + term II (X*
X X" - + DD' X x xx*)
[VF(X++112) VF(X') ) X - -x#+1)
a (D -D', D** x*)
(x" X xtX* x x -a & (D - -D' x - -x*)
a² (VF(***)) ++ 11/11= - VF(X*) X xx++1
x X 1 at (x+ x - D + D*
(39)
VF +1/22 - VF(X X - x
8 X" X", VF(X+11) VF(X))
a (VF(X*+12) - VF(X') X - -x++1
VF(X', = - X - -X++1)
VF(
The statement of the Lemma follows readily substituting (39) (36).
F.2 Proof of Lemma
We preliminary notice that, in view of Lemma 3, the backtracking inequality (6) on F holds with k min af, where each a the outcome of the backtracking procedure on the local S Since and Fh have the same curvature, follows that (6) holds also on F, that is,
F(X*+1) F(X + (VF(X++122 X k+I xx+1/2) +
2a X k+1
5
X 1+122 (40)
We proceed now bounding (VF(X++122) VF(X)), -x*t)))))) building on (40). To do so, we decompose the inner product as follows
VF(x*+1/22 - VF(X*) x k+1
VF((*+1/2) x x 11/2
(VF(X++1/2) x x + (VF((')) x')
(41)
21

---

We bound term I invoking strong convexity and co-coercivity of F while we use (40) to bound term II. Specifically,
(by strong convexity)
term ISF(X") - F(X -F(X+11)) +
VF(x + +D11
(by co-coercivity);
21
where we also used VF(X*) = D Therefore
term I F(x)) - F(X*+1/3) max
x X*
1
VF((*+1/22 + D
2T
(42)
Using (40), term II can be bounded as
term II S FF F(X
8
x
x
(43)
2
Using (42) and (43) in (41), yields
x / - VF(X*) X - -x+t1
I x k++ 12/2 max
8
F
x 1/2 x x-
1
/F(x + +D+1()
2
2T
F(X))
x x
=((
This completes the proof.
E.3 Proof of Lemma 8
Combining Lemma 6 and Lemma 7, we can write
pk+1
<
X
x
(a*) ? - -
max
n X
k+1/2
X 112
1
V X 1
+
1112
2
X
11
(a
2
x
1+1122
tern
term II
tern III
Next, we demonstrate that the sum of the last three terms contributes to the decrease of V++1
Using the definition of X k++1 and x++1/2 1/2 we can bound term III follows:
term III
X 8+1 x²)
x k+1/2 x²
1 x
x X -X*X*+1-X*+11
x + ||x xx11
|lace W)X
2a (DR+1/2 c
oll -
-W)x +
- 11x+1-X'"0
|0(1 W)X
||
2 ((-c(l- (V/( cell - -W)x*
+ |X x
112
Proceeding with | D k+
112 we have
term II II= = (a+) 2
-c(1 - W) (VF(X++1) +1/2 + DD* + c _1 - W)xx
M
- -||e(1 - W)xx | + *11 1xx""121-18
-2 (( ( -l- (VE(X + +D*
,o(1 - -ol-W)xx*
+ +att)2 ||c[ W) (VF(X*+1/2) + +D* )
22

---

where the second equality follows from the definition of M = (I- Combining the three terms yields
((--W) W)t -.. I.
term I - term II óterm III
8 term term II + term III) (1 -))(term I + term II)
<ō term term II + term III)
( W) (VF(X++1/2) + D* D*) ||=
8
|||
(
which proves the statement of the lemma.
E.4
Proof of Lemma 9
The proof involves further bounding the RHS of (17) in Lemma 8, appropriately in terms of r* and g², To achieve this, we construct two alternative bounds of the RHS of (17), as discussed below.
The first bound will reveal the dependence on r², and it is based on using in (17)
a - 11 max (2ta11x4t1/22-22
a
L L
+ DD11)
2
|
x+121/2
1
2
along with
(1 (1-c(1 -x
Am (w))
|x*
x x
(44)
We obtain
vk+1
x x-1 + +aa))) -D'I
a
2 (1 - c(1
-
6 x 1le [w - -ō(a o ww) (VF(x*+1/2) + +
(18)
x x+11²
D
a²a
(1 c(1 Am (m))))) 121 112
p²aa
2 (1 -cll - (m))) |x* x- 6(1))))) I - -D - 12.
The second bound of the RHS of (17) aims to obtain an explicit dependence on _.. This is done by just neglecting the last negative terms in the RHS of (17):
vh+1= < X
( - 1 x
a IVF( D'133
- -X-11
max
LE
x X-1 + \ -
at
(u*at(1 c(1 - Am (W))) x
x 111
VF #++1/2) -D'1())
max
T,
4 #
< x x x-112 (a D 1
(1
c(1
Am (W))) X-122
(1'(at)(11-)
o(1 Am ()))
kk
(at}² x 12 |VF(X++112) + +D*113
min
max
2
2
23

---

a (1 (1-o(1 Am (w)))) ||* xx11
c(1 Am c(
2 )) (at)) I D-
(g (1 min
11 1
The final result follows combining the above two bounds while using the definition of pf and Ç*. 0
E.5 Proof of Lemma 10
Invoking the update of the primal variable in the form
X ++ X & a (VF(X*+1/3 + aa" (D*+1
where we used D VF(X*) 0, and the definition of g*, we can write
1 a
xkt X
ス | 1+++1 - D
X X - (VF((++122 + D
a
>ID k+1 - D 2g² | D*
(45)
D k+1 - -D - 2(gg))
-
Amax (M)
Let us proceed lower bounding
D D* Using the update of the dual variable, in the form
D = D*
+ a
ax W)X* - c(1 (VF +1/3)) + +D*),
obtain
1 कh
| 2 ||D*
(46)
Using
| - W) M S X loy
the following holds for the last two terms on the RHS of (46):
1
1
+ --le([--W (VF-WWWVV(XXIIXXI (x + 1
(a
((I-W)
-2a max (akky | - | - -D'll3,
S (n max(()"))1DD 1
M | - -D*133
(1-0 max((g") )² D)I|D* D 1
(DDD) 1
where the last equality follows from g² < 1 (as postulated in (21)). Finally, using a2 + 2 a a b. we deduce
D D* 2 (1- V2r" | - D
Substituting the above inequality in (45) yields the desired result.
24

---

E.6 Proof of Lemma 11
Using (22) and (44) in (17) (while neglecting therein the last two negative terms on the RHS), yields
vk+22
<
x x+| + (a + 1 - liv f - X+1
(44)
x k x + (a ( D -D a d( Am ( - 1-
(2)
(1 - h+ 114 (1 d(1 Am (W))3)/2)11x 1+1 -X-12 + (a D -
D3 11
2 (1- 29 v Amax (M)
(1 c(1 Am Amax (1f)
(a+) D711
1 r-r222
5(1 - 1 h+2 b+2 (1 c(1 - Am (W))3)/2)|1X x -x+11
(1 (1- 2(7 (1 - c(1 - Am (W)))²
1
2g / /mmxx (M) ( (1-
+
)mnax(M)
n /2
x (a*+))3|D k+t - 11
where the last inequality follows from a² +t1 1/7
We deduce
aatt1 a _ 1 )² (1 [ nr a0llatt1(( ( c(1 Am ()))2
20th V Amax (M)
v++ I
max
1
2(7x)2 (mmxx (Mmax(M), 1)
(g
1 pch 122
The final statement of the lemma follows from the above inequality and
pk-1 < max ( a
(at11: V..
due to (20) and p <
E.7 Proof of Lemma 12
92 we can bound the product of 7 as
Let us consider the case N 2 [81] +2 Using 7h
k-t-9
k+1
N-1
N-1
++ 81
In
k
32
Σ
In
k+1
k=
k=
[9]
N-1
1
31 - 1
In
+ 32
Σ
In
1+
k+1
k 1
k=
k=
1+1
N-1
(47)
< 3,((1811 + 31 + -1
11
Σ
1
k+
k= [+ 1+1
N-1 1
< 52([11] + 1) In 81 + 32 1) Σ
k=1 k+1
< 12[1 + 1) 31 + 3 1) In N,
which proves (31). Notice that the above bound holds also if N < [ + Let us determine now No such that (32) holds. Condition (32) met if the following inequality holds
N 1-11
2
In
II
k + (N 1) 1n (1)))/211) s O.
k=
25

---

where we used that 1 1 --p
(1-p/2)² for p (0, 1). Bounding the LHS yields
2
In
II k=
xx
+ (N 1NN-1) - p/2) (47)
2.2 + +22 1) In (N 1) p/2)
<23][[B1] 1) In(1 p/2)
+ + 23r 1011(11111111 1) N
2
+ + +n2 - 2.
follows that (32) holds if
2 + 1) +
and
832(31 - 1) N.
N
sufficient condition for the last inequality to hold is
16 N 2 In 83331
This completes the proof.
Proof of the Intermediate Results in Appendix D
F. Proof of Lemma 14
1. This assertion comes readily from the definition Iy and the backtracking procedure.
2. Let (K) be the set of neighbors of agent i that are at most k 2 1 hops away from agent i, including agent itself. For notational consistency, (1) = Ma (i).Using (k)),, we can rewrite the local-min consensus step of each agent at iteration l as
min JEN((I
where at the stepsizes produced by the line-search of agent j iteration k.
Let be an iteration such that + 1....,I To &
IN. It must be
aiii = --a Vt k: +1,+1.... I,...,k. k.
In particular, this implics which leads
min aj JEN((1)
W= A 1, I...,k
of
II (m
7
min at.
JEN,(L+K-B)
Finally, taking To + dg and noting (:(dg) = [m], we proved the second statement of the lemma.
3. From the backtracking line-search and the definition In follows that
nht a
i & Ini
min if IN.
Applying the above relation iteratively, yields
N S 02-
amin
k=
26

---

At the same time, it follows from Lemma 3 that
B 2L 7 )
Omin
min
Combining the lower and upper bounds above, yields the desired result
N-1
INl S max [InooL + In
II
7 In
2
8
k=
F.2 Proof Lemma 15
From (34), it follows
N N₂ + dg
[Iv|-
Then, according the Dirichlet's principle there exists two iteration indices and lę such that
1. vk [k k2] = k & IN: and
2. h2 k 2 N + dg.
Invoking Lemma 14.(1) and Lemma 14.(2), it follows that all agents' stepsizes reach consensus after k1 + dg iterations and remain consensual for the subsequent N₂ iterations. One can then invoke Lemma 13, and conclude
X k2
x
1
D
D
M S E.
4L2
This concludes the proof.
G
Additional Numerical Results
This section presents additional experiments for the Ridge Regression problem, introduced in Sec- tion 6. Here, we consider additional graph topologies, namely: 1) Ring Graphs; 2) Random Regular Graphs with degree 3; and 3) Random Regular Graphs with degree 10. The rest of the setup (including algorithms'' tuning) is the same of that described in Section 6.
The experiments are summarized in Fig. 3. The findings comoobortee the conclusions presented in
1.
10"
Algor thm
Algorthin 3
Algoritin
Alger
Aggortiin 1ime tanac)
Algonttin
NIDS
10
10
(fine tuned)
.802
112 Iterotioes
1230
ARE
10600
20:1
(a) Ring Graph
(b) Regular graph, degree 3
(c) Regular graph, degree 10
Figure 3: Ridge regression on different regular graphs: (3a) Ring graph; (3b) Random Regular
Graph, with degree 3; (3c) Random Regular Graph with degree 10.
Sec. 6: both Algorithm and Algorithm 3 outperform EXTRA and NIDS, which were finely tuned for rapid practical convergence. Quite interestingly, the performance of the proposed methods appears to be less affected by network topology and depends primarily on network connectivity.
27

---

NeurIPS Paper Checklist
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification: Abstract gives accurate presentation of our result. Part Major contributions of Introduction contains full description of our work.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made in the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made the paper and important assumptions and limitations. A No or NA answer to this question will not be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings.
It is fine to include aspirational goals as motivation long is clear that these goals are not attained by the paper.
2. Limitations
Question: Does the paper discuss the limitations of the work performed by the authors? Answer:[Yes]
Justification:
The main limitaion of proposed procedure is min-consensus. The technology for its implementation carefully discribed part 3.1.
Guidelines:
The answer NA means that the paper has limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create a separate "Limitations" section in their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (c.g.. independence assumptions, noiseless settings, model sell-speciiiatiinn asymptotic approximations only holding locally). ). The authors should reflect on how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, e.g., if the approach was only tested on few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect on the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution low or images are taken in low lighting. Or speech-to-tex, system might not be used reliably to provide closed captions for online lectures because it fails handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and faimesss.
While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, a worse outcome might be that reviewers discover limitations that aren't 't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an impor- tant role in developing norms that preserve the integrity of the community, Reviewers will be specifically instructed to not penalize honesty concerning limitations.
3. Theory Assumptions and Proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
28

---

Answer: [Yes]
Justification: Main assumptions and definitions are presented in Section 2. All main theoretical results presented in Section with all required assumptions. Proofs are placed in Appendix A-F because of their large size.
Guidelines:
The answer NA means that the paper does not include theoretical results, All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated or referenced in the statement of any theorems.
The proofs can either appear in the main paper or the supplemental material, but they appear in the supplemental material, the authors are encouraged to provide short proof sketch to provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental Result Reproducibility
Does the paper fully disclose all the information needed to reproduce the main ex- perimental results the paper to the extent that affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided or not)?
Question:
Answer: [Yes]
Justification: All setup for numerical experiments are described in Section 5. It is enough to reproduce all experiments.
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, No answer this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is a novel architecture, describing the architecture fully might suffice, or if the contribution is specific model and empirical evaluation, it may be necessary to either make it possible for others to replicate the model with the same dataset, or provide access the model. In general. releasing code and data is often one good way to accomplish this, but reproducibility can also be provided via detailed instructions for how replicate the results, access a hosted model (e.g.. in the of large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed.
While NeurIPS does not require releasing code, the conference does require submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) the contribution is primarily a new algorithm, the paper should make clear how reproduce that algorithm. (b) If the contribution is primarily
model architecture, the paper should describe the architecture clearly and fully.
(c) the contribution is a new model (e.g., a large language model), then there should either be way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset or instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case authors are welcome describe the particular way they provide for reproducibility. In the case of closed-source models, it may be that access to the model is limited in some way (e.g., to registered users), but it should possible for other researchers to have some path to reproducing verifying the results.
29

---

5. Open access to data and code
Does the paper provide open access to the data and code, with sufficient instruc- tions faithfully reproduce the main experimental results, described in supplemental material?
Question:
Answer: [Yes]
Justification: code the form of an attached archive.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurIPS code and data submission guidelines (https://nips.cm cc/
onooolicy)) for more details.
While we encourage the release of code and data, we understand that this might be possible, so "No" is an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurlPS code and data submission guidelines (https:
/ wttpps.ccppubll//ppp wwcpublic/geteeececccccccceeeece teliiccggudes////e seoiiddee/oeeuumiieee ProodeSumiissionPoo
for more details.
The authors should provide instructions on data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, preserve anonymity, the authors should release anonymized versions (if applicable).
Providing much information possible in supplemental material (appended to the paper) recommended, but including URLs to data and code permitted.
6. Experimental Setting/Details
Question: Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [Yes]
Justification: Our paper demonstrates performance of optimization algorithm. Because of that, we do not need test some models. But Section 5 contains full information about our experiments.
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core of the paper to level of detail that is necessary to appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, as supplemental material.
7. Experiment Statistical Significance
Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Question:
Answer: [No]
Justification: Numerical experiments demonstrate performance of optimization algorithm given problems. Besides, our algorithm is deterministic.
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by emror bars, confi- dence intervals, or statistical significance tests, least for the experiments that support the main claims of the paper.
30

---

The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall run with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)
The assumptions made should be given (e.g., Normally distributed errors).
It should be clear whether the error bar is the standard deviation or the standard error of the mean.
is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that are out range (e.g. negative еπτог rates).
If error bars are reported in tables or plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables text.
8. Experiments Compute Resources
For each experiment, does the paper provide sufficient information the com- puter resources (type of compute workers, memory, time execution) needed to reproduce the experiments?
Question:
Answer: [Yes]
Justification: Information is given at the end of Section 5.
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate type of compute workers CPU or GPU, internal cluster, cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental runs as well as estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported the paper (e.g., preliminary or failed experiments that didn't make it into the paper).
9. Code Of Ethics
Question: Does the research conducted the paper conform, in every respect, with the NeurlPS Code of Ethics https httpp:://////ipp/// cc cctpublic////cccccccccccccccclll wetpuli//thhiiio htwhhhhiihciiieeeeee...
Answer: [Yes]
Justification: Authors are familiar with NeurIPS Code of Ethics and paper conform it.
Guidelines:
The answer NA means that the authors have reviewed the NeurIPS Code of Ethics.
the authors answer No, they should explain the special cireumstances that require deviation from the Code of Ethics.
The authors should make to preserve anonymity (e.g., if there is special consid- eration due to laws or regulations their jurisdiction..
10. Broader Impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [NA]
Justification: There are different methods of distributed optimization. The paper propose new method of distributed optimization that has no additional societal impact as the authors think.
Guidelines:
The answer NA means that there is no societal impact of the work performed.
31

---

If the authors answer NA or No, they should explain why their work has no societal impact or why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), faimess considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
The conference expects that many papers will be foundational research and tied to particular applications, let alone deployments. However, if there is direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used intended and functioning correctly, harms that could arise when the technology is being used as intended but gives incorrect results, and harms following from (intentional unintentional) misuse of the technology.
If there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms to monitor how system learns from feedback over time, improving the efficiency and accessibility of ML).
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data models that have high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification:
The proposed method does not require safeguard.
Guidelines:
The answer NA means that the paper poses such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards challenging, and many papers do not require this, but encourage authors to take this into account and make best. faith effort.
12. Licenses for existing assets
Question: Are the creators or original owners of assets (e.g., code, data, models), used in the paper. properly credited and are the license and terms of use explicitly mentioned and properly respected?
Answer: [Yes]
Justification: Numerical experiments use one of datasets from LIBSVM. Authors cite corresponding work of owners (see reference [6] in Section 5 and References)
Guidelines:
The answer NA means that the paper does
existing assets.
The authors should cite the original paper that produced the code package or dataset.
The authors should state which version of the asset used and, possible, include a URL.
The name of the license (e.g., CC-BY 4.0) should be included for each asset.
For scraped data from a particular source (e.g., website), the copyright and terms of service of that source should be provided.
32

---

If assets are released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, paperswi thcode. com datastts has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
For existing datasets that are re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided.
If this information not available online, the authors are encouraged to reach out to the asset's s creators.
13. New Assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [Yes]
Justification.contains contains README file with sufficient description.
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details of the dataset/code/moodl as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent obtained from people whose asset used.
At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
14. Crowdsoureing and Research with Human Subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well details about compensation (if any)?
Answer: [NA]
Justification: Paper does not involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper doess not involve crowdsourcing nor research with human subjects.
Including this information the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then much detail as possible should be included in the main paper.
According to the NeurIPS Code of Ethics, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional Review Board (IRB) Approvals or Equivalent for Research with Human Subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or equivalent approval/review based the requirements of your country institution) were obtained?
Answer: [NA]
Justification: Paper does not involve crowdsourcing nor research with human subjects
Guidelines:
The answer NA means that the paper does not involve crowdsourcing research with human subjects.
Depending the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
33

---

We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors adhere the NeurIPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review.
34


Reviews:
[{"review_id": "h9ekj7u7vS", "reviewer": "Reviewer_aLXV", "summary": "This paper introduces a new algorithm for decentralized optimization.  The main advantage over previous work in this domain is that it allows adaptive stepsize selection (via backtracking) that is independent of the properties of the functions being minimized.  The analysis of the algorithm recovers the linear rate for convergence for functions that are smooth and strongly convex, and the standard sublinear rate for the convex case.", "questions": "It is outside the scope of this submission, but I would be interested to know if this type of adaptive stepsize selection made a difference in practice in the stochastic setting.", "limitations": "None.", "rating": 7, "confidence": 4, "soundness": 4, "presentation": 3, "contribution": 3, "strengths": "As the authors state, this seems to be the first fully decentralized algorithm with adaptive stepsize selection that has strong convergence guarantees.  I found the operator splitting method for solving the KKT conditions innovative, and it is nice that this leads naturally to a way to do local stepsize adaptation.", "weaknesses": "While the numerical experiments are sufficient, new results on ridge and logistic regression can only get one so excited.  \n\nThe exposition of the saddle point reformulation at the beginning of Section 3 could be improved.\nLine 142: Does the optimization in (P') involve y at this point?  Should x be capitalized?\nLine 143: Some discussion about why K is being introduced here would help the exposition a lot, along with a little more on why the solutions of (P) and (P') match.  A lot of work is being left to the reader at this critical point.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the Referee for reviewing our paper and her/his positive assessment. We are glad that she/he recognized the major novelty of the proposed approach, i.e., the novel operator splitting technique that naturally leads to local stepsize adaptation. \n\nOur reply to her/his questions follows. \n\n1. **Simulations:** We agree that more simulations will be useful. We plan to add new experiments as follows: **i)** logistic and ridge regression problems on other topologies; **ii)** a new comparison between the proposed method and EXTRA and NIDS where for the latter we hand tune the stepsize for the best practical performance (as requested by other Referees); and **iii)** simulation (and comparison with the aforementioned schemes) of a newly added adaptive method wherein the global min consensus is now replaced with the local one (to address some concerns of Referee H817).\n\n2. **Exposition:** We thank the Referee for her/his feedback. **i)** The Reviewer is right, in Line 142, there is a typo: y should not be there and x should be capitalized. **ii)** We will provide some insight on why K is introduced in (P'). This goes along with some clarification on why (P) and (P') have the same solution, under the condition that K satisfies condition (c2) (which serves exactly this purpose). We will clarify these aspects in the revised manuscript. \n\n\n\n3. **Adaptivity in the stochastic setting:** The difficulty in implementing adaptivity in the stochastic setting lies in the line-search procedure, which is notoriously difficult in the presence of noise. This is a subject of our future investigation. \nHowever, a positive answer to the Reviewer's question can be  provided for the class of stochastic optimization problem for which a *Retrospective Approximation Approach* is feasible for the line search.  Specifically, at each iteration $t$, a sample approximation $f_i(x_i; \\xi_i^t)$  and $\\nabla f_i(x_i; \\xi_i^t)$ is constructed for the population function $f_i(x_i)=\\mathbb{E}_{\\xi}[f_i(x;\\xi)]$ and its gradient $\\nabla f_i(x_i)$ ($\\xi_i^t$ is the sample batch drawn by agent $i$ at iteration $t$), and the proposed  local line-search procedure is performed using  now $f_i(\\bullet; \\xi_i^t)$  and $\\nabla f_i(\\bullet; \\xi_i^t)$. The difference with a classical stochastic line-search is that here the batch sample $\\xi_i^t$ is kept *fixed* during the entire backtracking procedure (of course it can change from one iteration to another).  Within this setting, all the results of the paper are preserved if read in expectation.  While this Retrospective Approximation Approach does not cover stochastic oracles in their generality, it is a reasonable model for certain machine learning problems, for example those where evaluating $f_i(\\bullet; \\xi_i^t)$  and  $\\nabla f_i(\\bullet; \\xi_i^t)$ at a given point $x$ corresponds to perform one pass on the data batch $\\xi_i^t$. \nQuite interestingly, in an early version of the manuscript, we had this result, which was removed in the final version because of space limit. We can add it back, maybe removing the study of deterministic convex functions.\n\nWe thank again the Referee for her/his valuable comments.", "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": "7y8aDMsym3", "reviewer": "Reviewer_H817", "summary": "This paper studies adaptive parameter determination in decentralized optimization. It is a meaningful and interesting topic to investigate. They propose a decentralized method to solve consensus optimization, develop an adaptive parameter strategy, and show the linear convergence of their algorithm.", "questions": "No", "limitations": "No", "rating": 6, "confidence": 4, "soundness": 1, "presentation": 2, "contribution": 1, "strengths": "The main strength of the paper lies in the high value of the topic they studied, which is indeed a very meaningful and also a difficult topic to explore.", "weaknesses": "I was very excited when reading the abstract of this paper, because I know the difficulty of this topic. I was worried about the global min-consensus step, while the authors developed a local min-consensus strategy to replace it, which well addressed my concerns.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the Referee for the review. We kindly disagree with her/his assessment, which is an oversimplification and trivialization of our contributions, missing the challenges our work addresses.  Details follow.\n\n1)**About the global min-consensus:** The Referee's sole concern is the presence of a min-consensus step in the algorithm, whereby agents evaluate the minimum of their local stepsizes over the network at each iteration. The Referee questions the implementability of this step in practice. **The reality is quite the opposite**. As discussed in our paper (lines 212-225), the min-consensus step **is implemented seamlessly** in commercial wide-area mesh networks without changes to existing communication protocols or additional hardware. This is facilitated by the  *decade-old* Long Range (LoRa), commercialized by Semtech and widely integrated into most commercial transceivers in wide-area networks. The Referee may want to know that LoRa is used in various fields, including industry, smart cities, environmental monitoring, agriculture, healthcare, and long-range, low-power Internet of Things (IoT) applications [2, 14, 15] (references as in our paper). LoRa supports communication ranges of hundreds of kilometers in free space, hundreds of meters in indoor environments, and half a kilometer in urban settings [14], with a maximum data rate of hundreds of kbit/s on average and a few kbits/sec at the longest possible range. **This technology is ideal for implementing the min-consensus step**: each agent broadcasts a few bits representing the quantization of its stepsize over the LoRa channel, which reaches all other agents in the network thanks to the extensive range of the LoRa signal. Each agent can then compute the minimum of all the stepsizes. **This resolves the issue of implementability raised by the Referee**. This is not merely our claim; it is a fact backed by existing technology. The Referee cannot overlook this well-established technology and solution.\n \n2)**From the global to the *local* min-consensus:** Intellectually, we agree that developing a method without the global min-consensus is worthwhile. We can address this by providing a first variant of the algorithm where the *global* min-consensus is replaced by a **local** min-consensus. Specifically, we replace  step 3 of Algorithm 1 with \n$\\\\alpha^k_i=\\\\text{min}_{j\\\\in\\\\mathcal{N}_i}$, where $\\\\mathcal{N}_i$ is the the set of neighbors of agent $i$ (including agent $i$ itself).  Then, in the other steps the common stepsize is replaced by a diagonal matrices containing the individual stepsize $\\alpha^k_i$ above. \n\n\nThe convergence analysis can be readily adapted to this variant (see box 'Official comments' below), yielding: the number of iterations $N$ for  $\\\\min\\_{k\\\\in \\\\{1,...,N\\\\}} V^k\\\\leq \\varepsilon$ reads $$N=\\\\widetilde{\\\\mathcal{O}}(d\\_{\\\\mathcal{G}}N\\_{\\\\varepsilon}),$$ \nwhere $N_\\\\varepsilon$ is the number of iterations achieved using the *global* min-consensus (this is what we defined as $N$  in Corollary 4.1, for the three cases) and $d_{\\\\mathcal{G}}$  is  the diameter  of the graph. This shows that if a global consensus is replaced by a min-consensus, there is a  degradation of the overall number of iterations by a  factor $d_\\\\mathcal{G}$.  This is not surprising, because it is known that  a min-consensus algorithm convergences on a network in a *finite* number of iteration of the order of the diameter. We believe that the multiplicative dependence of the convergence rate on $d_\\\\mathcal{G}$ can be improved or removed, see the box 'Official comments' below. \n\nWe tested this new variant running new simulations reported in the attached pdf in the global comment section. \n\nWe hope that this satisfies the intellectual curiosity of the Referee. We can add this variant to the revised paper, if the Referee wishes so.  \n\n3)**The Referee is overlooking our major contributions:** Our contributions cannot be trivialized to the min-consensus step only. In fact, equipping existing decentralized algorithms such as DGD, EXTRA, or NIDS with a global min-consensus procedure *does not grant them adaptivity*; even worse, it will jeopardize their convergence. **It is not even clear how to identify for them a   (descent) 'direction'**  (and local merit function)  along with  performing the adaptive step-size selection,  see lines 190-195 in the paper. The  tuning of the stepsize in decentralized algorithms must depend on network properties, as stepsize values similar to centralized settings generally lead to divergence. Thus, any candidate direction should contain information on the optimization **and** network. There is no understanding of how the network should influence the direction and how to encode in the candidate direction optimization and network information. **We offer the first principle-based procedure to resolve these issues, addressing the major challenge that has prevented the migration of centralized adaptive stepsize techniques to the decentralized setting**. Hopefully this will be trigger new works in this direction. \nLast but not least, our algorithm is provable convergent also when applied to functions that are **only locally smooth** (and locally strongly convex), which is not the case for the majority of existing decentralized algorithms, e.g., EXTRA and NIDS. This enlarges significantly the classes of problems our scheme can be applied. \n\nWe hope this clarification helps the Referee appreciate the importance of our contribution. \n \n**In summary:**  **(i)**  We proved that *existing technology supports global min-consensus for free*. **(ii)** Still, we addressed the Referee's comment by providing and numerically testing a variant of the algorithm that removes global min-consensus. **(iii)** We clarified that our major contribution is not the global min-consensus and demonstrated that even with a global consensus step, existing schemes do not achieve adaptivity for free,  let alone convergence guarantees.", "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": "i8BXgmkcLX", "reviewer": "Reviewer_ioM9", "summary": "This paper proposed a parameter-free method for decentralized learning and showed that the method converges to the optimal solution linearly without hyperparameter tuning.", "questions": "See the above comments.", "limitations": "See the above comments.", "rating": 5, "confidence": 3, "soundness": 2, "presentation": 1, "contribution": 2, "strengths": "This paper proposed a novel decentralized method and the convergence rate is analyzed under the general setting.", "weaknesses": "1. Theorem 4 provided the convergence rate of the proposed method without hyperparameter tuning, but Corollary 4.1 provides the results with some $\\beta_1$ and $\\beta_2$. Thus, the reviewer thinks that the results in Corollary 4.1 require hyperparameter tuning. The author discussed the convergence rate in Corollary 4.1, but this result is not the convergence rate of the parameter-free method. The reviewer thinks that it is necessary to discuss the results in Theorem 4 and compare these results with one of the existing methods.\n2. The reviewer does not understand what the author would like to conclude from Theorem 5 (in the weakly convex setting). Theorem 5 only shows that the amount of parameter updates (i.e., $\\| X^j - X^{j+1} \\|^2$) is bounded from above by some factor and does not show that the proposed method converges to the optimal solution.\n3. The author did not tune the stepsize for EXTRA and NIDS in Fig. 1 and did not mention how to tune the stepsize in Fig. 2. The author claimed that the proposed method consistently outperforms EXTRA and NIDS in Figs 1 and 2, but these results are not convincing because the results of NIDS and EXTRA are suboptimal, at least in Fig. 1. The reviewer would like to see the results of EXTRA and NIDS with well-tuned stepsize and see the comparison between the proposed method and the prior methods. \n4. The line 3 in Algorithm 3 can not be calculated in a decentralized manner.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the Referee for her/his comments, which will help us to clarify some parts of the paper  as well as improve the revised version. Our detailed reply follows.\n\n1. **The reviewer thinks that the results in Corollary 4.1 require hyperparameter tuning\"**: We apologize for this misunderstanding, due to the lack of adequate comments from our side. **There is no need of  hyperparameter tuning here**. The two parameters $\\beta_1\\geq1$ and $\\beta_2>0$ are just *extra* degrees of freedom to offer further flexibility in the algorithm design (see comment below), but they are not necessary. In fact, **(i)** the theoretical convergence rate as in Th. 4 (or Corollary 4.1) does not depend (asymptotically) on $\\beta_1$ and $\\beta_2$. **(ii)** One can set $\\beta_1=\\beta_2=1$ and they will disappear from the algorithm. We could have introduced the algorithm directly setting   $\\beta_1=\\beta_2=1$.  Notice that all our simulations are conducted under this choice, $\\beta_1=\\beta_2=1$, which provides quite compelling performance.  \n**Further comments on  $\\beta_1$ and $\\beta_2$**: at the high level, the introduction of these two parameters is to allow practitioners to use 'larger' stepsizes $\\alpha_i^t$   out of the line-search, via the   *nonmonotone* sequence $\\{\\gamma^k\\}$, where $\\gamma^k=\\left(\\frac{k+\\beta_1}{k+1}\\right)^{\\beta_2}$. This helps in practice to achieve better performance, if one is willing to explore this extra degree of freedom. This is however not necessary for the theoretical convergence and, as mentioned, one can either choose $\\beta_1=\\beta_2=1$ or directly set $\\gamma^k=1$ for all iterations $k$. We discussed this matter in lines 207-211 of the original submission. We will further clarify this aspect  in the revised version of the paper. \nIn general we talk about `` hyperparameter tuning''  when the parameter involved are not free but must satisfy some conditions *coupling* them with other parameters of the algorithm  (such as the stepsize, etc.). In that case, their choice would be no longer free.  This is not the case here, because there are no such requirements on $\\beta_1$ and $\\beta_2$, but $\\beta_1\\geq1$ and $\\beta_2>0$ (hence not restricting the choice of any other algorithm tuning parameter).\n\n2. **About  Theorem 5 (in the weakly convex setting)**: We thank the Referee for the comment. The result establishes the asymptotic optimality of any limit point of the sequence generated by the algorithm. However, we agree that the nonasymptotic convergence result is not particularly strong. Given that the strongly convex case is more challenging in terms of guaranteeing linear convergence, and considering the new anticipated results from other Referees' comments, we will remove the convex case. This will allow us to use the space to introduce the local min-consensus variant and its convergence, and possibly the stochastic case under the Retrospective Approximation framework. We hope that the Referee will agree that the convex case is not the major result of the paper. \n\n3. **The author did not tune the stepsize for EXTRA and NIDS in Fig. 1 ...:** It is challenging to fairly compare our scheme with existing ones because the existing decentralized schemes require full knowledge of the network and optimization parameters, whereas our scheme does not.  We agree that other choices could have been made for  the tuning of EXTRA and NIDS.  Some question to guide the process are:\n**(i)** Should the comparison be done using the *theoretical* tuning recommended in the papers to ensure convergence? By doing so, the comparison would be fair in the sense that all algorithms are guaranteed to converge. However, this approach may result in quite stringent stepsize values\nOr **(ii)** Should one take a more practical approach, ignoring theoretical conditions (and thus convergence guarantees) and hand-tuning for the best observed convergence?\n\nBoth approaches introduce some level of unfairness. In our paper, we followed the former approach: we used the tuning recommended in the respective papers for our scheme, EXTRA, and NIDS to guarantee convergence. However, it can still be argued that the comparison is unfair because NIDS and EXTRA require full knowledge of the network and optimization parameters, while our scheme does not. But in this case, the unfairness is towards our scheme.  \n\nTo address the Referee's suggestion, we have conducted new experiments where we hand-tuned EXTRA and NIDS for their best practical performance and compared them with our method. Note that in this setting, EXTRA and NIDS lack theoretical convergence guarantees, while our method maintains them. We kindly refer the Referee to the global rebuttal section for more details on the experiments and the new figures (attached pdf therein). We are open to conduct alternative comparisons if the Referee has something different in mind to share. \n\n4.**The line 3 in Algorithm 3 can not be calculated in a decentralized manner.** This method is actually implementable in the existing wide area networks, thanks to the LoRa technology. This has been briefly discussed in the paper  (lines 212-225) and further elaborated in the Reply to Reviewer H817, please refer therein to item 1 **About the global min-consensus**. Also, we provided a variant of the algorithm that replaces the global min-consensus with a **local** min-consensus (see **From the global min-consensus to the local min-consensus** in the reply to Reviewer H817). This variant has been simulated and results provided in the attached pdf in the section of general comments. \n\nHope the Referee is willing to reconsider her/his initial assessment, cosidering that this is the *first* adaptive methods in the decentralized literature, even just focusing on strongly convex problems. Achieving adaptivity posed several challenges, resolved in this work for the first time. We elaborated further on this aspect in point 3) of our reply to Reviewer H817, which we refer the Referee to.", "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": "MwnJqSWxPu", "reviewer": "Reviewer_E8C7", "summary": "The paper introduced a new parameter-free algorithm based on forward-backward splitting technique and variable metric for decentralized learning problems for convex locally smooth functions. Convergence guarantee with favorable rate and analysis are provided.", "questions": "See weaknesses.", "limitations": "No.", "rating": 5, "confidence": 2, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "1. The paper proposed the first parameter-free decentralized training algorithm integrating line search and splitting technique.\n2. Convergence guarantee and analysis under milder conditions than previous studies are provided.\n3. The guidelines of design seems to be of independent interest and further investigation.", "weaknesses": "1. The proposed algorithm is complicated, and it seems that in each iteration, a lot of computation needs to be carried out. How does the algorithm compares to the previous ones in terms of computational complexity?\n2. The proposed algorithm needs more experimental evaluation.\n3. In certain parts, the paper is a bit hard to follow.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the Referee for reviewing our work and the positive assessment on the novelty of the paper. Our reply to her/his comments/questions follows. \n\n1.  **\"The proposed algorithm is complicated\":** The proposed algorithm has comparable communication cost  (step S.1 and S.2) and computational complexity (gradient evaluation) of all  existing notorious decentralized algorithms that converge to an *exact* solution of the optimization problem, such as  EXTRA, NIDS, and Gradient Tracking, *except for the line-search procedure*, which results in some extra computation in the evaluation of the function value. This extra computation is what allows one to achieve adaptivity of the algorithm, that is, convergence with **no knowledge** of any optimization or network parameter. On the contrary, **all** the existing decentralized algorithms require  **full  knowledge** of the optimization and network parameters to converge. In practice, this information is not available at the agents' side, and needs to be acquired, if one wants to implement these schemes. This calls for some nontrivial procedure that produces reasonable estimates of these optimization and network parameters,  which results in additional computation and communication costs.         \nOn our side, the backtracking procedure is the only extra (reasonable) computational cost one needs to pay, to obtain for the first time a decentralized algorithm that does not require any centralized knowledge and implementable in practice without any additional procedure.  In the future, it will be interesting to replace the line-search with some other adaptive procedures that require less function evaluations. \n\n2. **\"The proposed algorithm needs more experimental evaluation\"**: We thank the Referee for her comment. We will expand the numerical evaluation, along the following directions:  i) logistic and ridge regression problems on other network topologies; ii) a new comparison between the proposed method and EXTRA and NIDS where for the latter we hand-tune the stepsize for the best practical performance (as requested by other Referees); and iii) simulation (and comparison with the aforementioned schemes) of a newly added adaptive method wherein the global min consensus is now replaced with the local one (to address some concerns of Referee H817).  \nWe added in the general rebuttal section a pdf with some of the above results. We kindly refer the Referee to that section for more details on the experiments and the figures.  We hope that the additional experiment will address the Referee's request. We are open to suggestions, if the Referee had something else in mind for the experimental evaluation. \n\n3. **\"In certain parts, the paper is a bit hard to follow\":** We will be happy to improve the presentation and provide all the necessary clarifications, if the Referee can be more specific on which part is ``hard to follow''. We appreciate if the Referee can point us to the parts that are not clear to her/him. \n\n 4. We would like to stress one more time that this is the first attempt to bring adaptivity in the decentralized setting providing a systematic approach, and algorithms provably achieving linear convergence.   The main challenge in bringing adaptivity in the  *decentralized* setting is to identify in (existing) distributed algorithms a (descent) 'direction' (and local merit function) along with performing the adaptive step-size selection. The tuning of the stepsize in decentralized algorithms must depend on network properties, as stepsize values similar to centralized settings generally lead to divergence. Thus, any candidate direction should contain information on the optimization *and* network. There is no understanding of how the network should influence the direction and how to encode in the candidate direction optimization and network information. We offer the first principle-based procedure to resolve these issues, addressing the major challenge that has prevented the migration of centralized adaptive stepsize techniques to the decentralized setting. Hopefully this will be trigger new works in this direction.  Last but not least, our algorithm is provable convergent also when applied to functions that are **only locally** smooth (and locally strongly convex), which is not the case for the majority of existing decentralized algorithms, e.g., EXTRA and NIDS. This enlarges significantly the classes of problems our scheme can be applied. \n\nWe would appreciate an assessment of the paper from the Referee based on this important contribution. \n\nThanks again for the feedback on the paper. Please let us know if our answer and additional posted material satisfactorily have addressed all the Referee's comments/requests.", "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:
We thanks all the Referees for reviewing our paper and their feedback and suggestions. We did our best to address any concern in the individual reply, which we refer to for details. Below we only discuss the new added experiments. 

A common request from multiple Referees has been expanding the experiments, which we have done it. Some new experiments  (more in the revised paper) are reported in the attach a pdf.  More specifically, we did the following: 

1. As requested by one Referee, we have changed the tuning of the benchmark (nonadaptive)  algorithms, NIDS and EXTRA. We now select the stepsize by **hand-tuning** aiming for the best practical performance (fastest observed rate). Notice that in this case, NIDS and EXTRA are *no longer* guaranteed to convergence theoretically, because stepsize values typically violates the conditions for convergence. On the contrary our scheme has theoretical convergence guarantees. Furthermore, and quite remarkably, it compares favorably even with this hand-tuned instances of NIDS and EXTRA. 

2. We have introduced and  simulated also a new version of our algorithm, that replaces the global min-consensus with the **local** min consensus. This is to address a comment from the Reviewer H817 who considers the global min-consensus not desirable (we kindly disagree with this assessment, as *current technology supports scalar min-consensus over network for free*). The new variant still has good practical performance and convergence guarantees. 
 
3. We have compared  the above decentralized algorithms (NIDS, EXTRA, our original scheme based on global min-consensus, and the new variant based on local min-consensus) over different graph topology (not present in the original submission), namely (a) a line graph, (ii) a ring, and (iii) a random regular graph  (with two degree values).  On each graph we report experiments for logistic and ridge regression problems. 

**Some comments on the numerical results**

1. The figures demonstrate that our original scheme, based on global min-consensus, consistently outperforms EXTRA and is almost always superior to NIDS, even when these algorithms are hand-tuned. This holds true across different optimization problems and network topologies. This is particularly noteworthy considering that hand-tuning is neither desirable nor easily implementable in practice, especially when the network topology is unknown. Additionally, hand-tuning generally compromises theoretical convergence guarantees. On the contrary our schemes do not require any intervention and more importantly have theoretical guarantees. 

2. The new variant of the proposed adaptive algorithm based on local min-consensus still shows strong performance, holding well against hand-tuned EXTRA and NIDS. **(i)** While the convergence rate remains linear, the error curves may exhibit some 'spikes.' This is consistent with the new convergence analysis provided (see details in the Reply to Reviewer H817) and is due to the min-consensus converging in a finite number of iterations proportional to the graph diameter. The correct way to interpret the convergence is that the minimum of the error gap within N iterations falls below the desired accuracy *geometrically fast*. **(ii)** As expected, as the graph becomes more connected, the new variant of the algorithm using local min-consensus matches the performance of the original algorithm using global min-consensus. 

3. On convex problems (logistic regression) the gap in performance of the different algorithms (but EXTRA) is less pronounced than that  in the strongly convex case.

Meta-review: This work studies decentralized optimization and proposes a method that utilizes backtracking line search to avoid tuning the step size parameters. Unlike previous work, this algorithm's convergence does not require step sizes to be dependent on problem parameters, making it adaptive. A linear convergence rate is established for strongly convex costs, and sublinear rates are demonstrated for the convex case.

Overall, the reviewers find the contribution meaningful. The guidelines of design are of independent interest and further investigation.
 However, the presentation of the paper could be improved, and the paper would benefit from enhancing the numerical experiments, which the authors have done. Additionally, there are several works on adaptive step sizes based on the Barzilai–Borwein method that the authors need to discuss in the final version.

Hu, Jinhui, et al. "The Barzilai–Borwein Method for distributed optimization over unbalanced directed networks." Engineering Applications of Artificial Intelligence 99 (2021): 104151.

Zhang, Xuexue, Sanyang Liu, and Nannan Zhao. "An accelerated algorithm for distributed optimization with Barzilai-Borwein step sizes." Signal Processing 202 (2023): 108748.

Emiola, Iyanuoluwa, and Chinwendu Enyioha. "Q-linear Convergence of Distributed Optimization with Barzilai-Borwein Step Sizes." 2022 58th Annual Allerton Conference on Communication, Control, and Computing (Allerton). IEEE, 2022.
Decision: Accept (poster)