Paper deep dive
Adaptive Decentralized Composite Optimization via Three-Operator Splitting
Xiaokai Chen, Ilya Kuruzov, Gesualdo Scutari
Intelligence
Status: succeeded | Model: Gemma-4-26B-A4B | Prompt: intel-v1 | Confidence: 93%
Last extracted: 7/20/2026, 11:40:19 PM
Summary
This paper proposes adaptive decentralized composite optimization algorithms for agents minimizing locally smooth convex losses and nonsmooth convex terms over a network. The method utilizes a three-operator splitting (Davis-Yin) applied to a BCV-preconditioned reformulation, enabling agents to adjust stepsizes via local backtracking and min-consensus protocols. Theoretical guarantees include sublinear convergence under convexity and linear convergence under strong convexity and partial smoothness.
Entities (8)
Relation Signals (7)
Adaptive Step Size → usesmechanism → Local Backtracking
confidence 96% · agents adaptively adjust their stepsize via local backtracking procedures
Decentralized Optimization → solvedby → Three-Operator Splitting
confidence 95% · The paper studies decentralized optimization... Our design stems from a three-operator splitting factorization
Proposed Methods → guarantees → Sublinear Convergence
confidence 94% · Under mere convexity, the proposed methods converge with a sublinear rate.
Proposed Methods → guarantees → Linear Convergence
confidence 94% · Under strong convexity... we further prove linear convergence.
Adaptive Step Size → usesmechanism → Min-Consensus
confidence 93% · coupled with lightweight min-consensus protocols
Three-Operator Splitting → isvariantof → Davis-Yin Splitting
confidence 92% · our design builds on a Davis-Yin three-operator splitting
BCV Preconditioning → enables → Decentralized Implementation
confidence 90% · BCV preconditioning metric... enables efficient decentralized implementation
Cypher Suggestions (0)
No Cypher suggestions yet.
Abstract
Abstract:The paper studies decentralized optimization over networks, where agents minimize a sum of {\it locally} smooth (strongly) convex losses and plus a nonsmooth convex extended value term. We propose decentralized methods wherein agents {\it adaptively} adjust their stepsize via local backtracking procedures coupled with lightweight min-consensus protocols. Our design stems from a three-operator splitting factorization applied to an equivalent reformulation of the problem. The reformulation is endowed with a new BCV preconditioning metric (Bertsekas-O'Connor-Vandenberghe), which enables efficient decentralized implementation and local stepsize adjustments. We establish robust convergence guarantees. Under mere convexity, the proposed methods converge with a sublinear rate. Under strong convexity of the sum-function, and assuming the nonsmooth component is partly smooth, we further prove linear convergence. Numerical experiments corroborate the theory and highlight the effectiveness of the proposed adaptive stepsize strategy.
Tags
Links
- Source: https://arxiv.org/abs/2602.17545v1
- Canonical: https://arxiv.org/abs/2602.17545v1
Trouble viewing inline? Open PDF directly →
Full Text
110,979 characters extracted from source content.
Expand or collapse full text
remarkRemark Decentralized Composite OptimizationX. Chen, I. Kuruzov, and G. Scutari [][nocite]supplement Adaptive Decentralized Composite Optimization via Three-Operator Splitting †thanks: Submitted to the editors February, 2026. work of Chen and Scutari has been supported by the Office of Naval Research (ONR Grant N. N000142412751). Xiaokai Chen Edwardson School of Industrial Engineering, Purdue University, West Lafayette, IN 47906 USA ( and , ). Ilya Kuruzov Gesualdo Scutari33footnotemark: 3 Abstract The paper studies decentralized optimization over networks, where agents minimize a sum of locally smooth (strongly) convex losses and plus a nonsmooth convex extended value term. We propose decentralized methods wherein agents adaptively adjust their stepsize via local backtracking procedures coupled with lightweight min-consensus protocols. Our design stems from a three-operator splitting factorization applied to an equivalent reformulation of the problem. The reformulation is endowed with a new BCV preconditioning metric (Bertsekas–O’Connor–Vandenberghe), which enables efficient decentralized implementation and local stepsize adjustments. We establish robust convergence guarantees. Under mere convexity, the proposed methods converge with a sublinear rate. Under strong convexity of the sum-function, and assuming the nonsmooth component is partly smooth, we further prove linear convergence. Numerical experiments corroborate the theory and highlight the effectiveness of the proposed adaptive stepsize strategy. keywords: Adaptive stepsize, convex optimization, decentralized optimization, networks. 1 Introduction We study decentralized optimization problems in the form (P) minx∈ℝdu(x):=∑i=1mfi(x)⏟:=f(x)+∑i=1mri(x)⏟:=r(x), _x ^d u(x):= _i=1^mf_i(x)_:=f(x)+ _i=1^mr_i(x)_:=r(x), -2.84544pt where fi:ℝd→ℝf_i:R^d is the loss of agent i∈[m]:=1,…,mi∈[m]:=\1,…,m\, assumed to be (strongly) convex and locally smooth, and ri:ℝd→ℝ∪−∞,+∞r_i:R^d ∪\-∞,+∞\ is a convex, nonsmooth proper extended value function. Both fif_i and rir_i are private functions assumed to be known only to agent i. Agents are embedded in a communication network, modeled as a fixed, undirected and connected graph G, with no central servers. Problem (P) arises in several applications of interest, including signal processing, machine learning, multi-agent systems, and communications. The literature abounds with decentralized methods for (P) under the standing assumption that the fif_i’s are globally smooth and identical ri=r_i=r for all i; we refer to the tutorials (and reference therein) [Nedic_Olshevsky_Rabbat2018, Xin_Pu_Nedic_Khan_2020] and monograph [Sayed-book] for comprehensive reviews. Global smoothness aside, these methods impose conservative stepsize bounds that depend on parameters such as the global Lipschitz constants of the agents’ gradients, the spectral gap of the graph gossip matrix, and other topological network properties. Such information is generally unavailable locally to agents in real-world deployments. As a result, stepsizes are frequently selected via manual tuning, yielding performance that is unpredictable, problem-dependent, and difficult to reproduce. Moreover, these approaches may fail when the agents’ losses are only locally smooth; see Sec. 1.1 for further discussion. This paper addresses these limitations by proposing adaptive-stepsize decentralized algorithms that solve (P) under local smoothness, private, nononsmooth functions rir_i, and without requiring global problem/network information. 1.1 Related works 1. Adaptive centralized methods: There has been a growing interest in developing adaptive stepsize methods in centralized optimization. Representative examples include line-search [bertsekas2016nonlinear], Polyak’s [polyak1969minimization] and Barzilai-Borwein’s [BarzilaiBorwein1988] rules, curvature based estimate rules [Malitsky2019AdaptiveGD, Malitsky_Mishchenko_2024, Zhou24], and adaptive gradient methods such as AdaGrad/Adam/AMSGrad and variants [duchi2011adaptive, kingma2014adam, Reddi2018OnTC, Orabona19, Ward20, jordan6muon]. However, these schemes are generally ill-suited for mesh networks since they rely on a central server to aggregate updates and enforce a common stepsize. Among the above, only [bertsekas2016nonlinear, polyak1969minimization, duchi2011adaptive] naturally handle nonsmooth, identical convex terms r. 2. Adaptive decentralized methods: The landscape of adaptive decentralized methods is comparatively limited [Nazari_Tarzanagh_Michailidis_2022, chen2023convergence, li2024problem, kuruzov2024achieving, Zhou24, Notarstefano24]. Most existing works focus on stochastic/online (non)convex smooth optimization (i.e., ri≡0r_i≡ 0), and obtain adaptivity through gradient normalization or history-based scaling rules [Nazari_Tarzanagh_Michailidis_2022, chen2023convergence, li2024problem]. Except for [li2024problem], these approaches assume globally Lipschitz continuous gradients, which supports convergence under standard diminishing stepsizes of order (1/k)O(1/ k) (with k denoting the iteration index). Moreover, [Nazari_Tarzanagh_Michailidis_2022, chen2023convergence] require a priori knowledge of problem-dependent constants. The recent work [Notarstefano24] introduces a Port–Hamiltonian framework for smooth, strongly convex, unconstrained problems: while the method is parameter-free in the centralized setting, decentralized convergence (global asymptotic stability) is shown only under specific graph topologies (e.g., complete or ring graphs) or graph-dependent stepsize restrictions requiring global network information; additionally, no explicit convergence rate is provided. Finally, [kuruzov2024achieving] proposes an adaptive decentralized method for smooth, strongly convex instances of (P), proving linear convergence and improved theoretical and practical performance relative to non-adaptive baselines. Composite objectives and local smoothness. None of the above decentralized methods addresses composite problems of the form (P), nor do they accommodate instances where fif_i’s are only locally smooth. While adaptive proximal schemes for composite optimization exist in centralized settings [Yura-Pock-LSPrimal-dual-18, Latafat_23b], their decentralization faces substantial limitations. In particular, [Yura-Pock-LSPrimal-dual-18] would require, at every line-search trial: (i) transmitting ambient-dimensional vectors, leading to prohibitive communication overhead; and (i) computing (and disseminating) the smallest trial stepsize over the entire network. The method in [Latafat_23b] avoids line-search, but still requires computing and propagating global scalar quantities at each iteration, and its stepsize selection depends on a global network constant that is not locally available. Conservative local upper bounds of this parameter destroy adaptivity, slow convergence, and make performance sensitive to tuning parameters–this is corroborated by the numerical results in Sec. 6. Overall, existing adaptive decentralized methods do not solve composite optimization problems as (P) using only neighbor-to-neighbor communications, let alone under merely local smoothness. To the best of our knowledge, the algorithms proposed in this paper are the first parameter-free decentralized methods that close this gap. 1.2 Major contributions Our main contributions are summarized as follows. 1. Algorithm design: We introduce an adaptive stepsize decentralized algorithm tailored to the composite structure of (P). To handle the nonsmooth terms, our design builds on a Davis-Yin three-operator splitting applied to a BCV-type reformulation of (P) [bertsekas2016nonlinear, o2020equivalence]. A key novelty is the design of an appropriate metric in the BCV transformation that enables a fully decentralized implementation supporting local backtracking stepsize updates at each agent while using only single-hop communications. Endowing decentralized methods with backtracking is challenging: there is no canonical notion of a descent direction available to each agent; agents’ updates are coupled through the network and are not, by themselves, optimization steps for the global objective u. We resolve this issue by identifying a suitable agent-wise update direction and a backtracking test on local agents’ losses that, via a descent inequality of a properly chosen Lyapunov function, certifies global convergence. To coordinate stepsizes, we propose two implementations based on global and local min-consensus protocols, respectively; they complement applications in different networking settings. Remarkably, neither implementation requires knowledge of global optimization constants or global network parameters. 2. Convergence guarantees: We provide a comprehensive convergence analysis for both proposed algorithms. We prove that all agents’ iterates consensually converge to a solution of (P). Under mere convexity of the fif_i’s, we establish a sublinear rate of order (1/k)O(1/k) for a suitable optimality gap. 3. Linear convergence rate with strongly convex fif_i and partly smooth rir_i: When each fif_i is locally strongly convex and each rir_i is partly smooth relative to a 2C^2 embedded manifold (Def. 5.1) around the limit point of the algorithms, we prove linear convergence. Our results are twofold: (i) if the aforementioned active manifold is affine, we establish finite-time manifold identification followed by a global linear rate, together with an explicit iteration-complexity bound; (i) if the active manifold is a general 2C^2 manifold, we obtain asymptotic linear convergence. 4. An adaptive three-operator splitting: As a by-product of our design, we also obtain an adaptive three-operator splitting algorithm (a backtracking variant of Davis–Yin splitting) for composite optimization in the form (P), with locally smooth f, implementable in centralized or federated (master/client) architectures. This new method inherits the same convergence guarantees as its decentralized counterpart discussed above (global convergence under convexity and linear convergence under strong convexity plus partial smoothness), while remaining parameter-free (no knowledge of any optimization parameter is required). We believe this scheme is of independent interest as an adaptive splitting primitive for large-scale composite optimization. In addition to the above guarantees, numerical experiments show that the proposed adaptive methods significantly outperform existing decentralized algorithms applicable to (P), which rely on non-adaptive (conservative) stepsize choices. A preliminary version of this work appeared in [chen2025parameter]. The present paper substantially extends [chen2025parameter] by providing: (i) more principled and less restrictive adaptive stepsize rules based on a new merit function and an inexact descent analysis, leading to faster algorithms; (i) a more comprehensive convergence theory, including iterate convergence and linear rates under local strong convexity of the fif_i’s and partial smoothness of the rir_i’s; and (i) complete proofs and expanded experiments. A related preprint appeared during the preparation of this manuscript [xu2025accelerated], and after [chen2025parameter]. It develops an adaptive decentralized algorithm for a variant of (P) including conic constraints; an accelerated sublinear convergence is shown for convex losses and convex constraints. Adaptivity is achieved via local backtracking procedures coupled with a global max-consensus mechanism. Our method differs from [xu2025accelerated] in the following key features: (i) it can handle locally smooth losses fif_i’s (rather than globally smooth); (i) adaptive stepsize updates can be implemented using only neighboring communications; and (i) it provably achieves linear convergence (in the sense discussed above) when the agents’ losses are strongly convex. 1.3 Notation and paper organization Let ℝ¯:=(−∞,+∞] R:=(-∞,+∞]; [m]:=1,…,[m]:=\1,…, mm\; 1m1_m and 0m0_m denote the all-one and all-zero m-dimensional vectors (dimension omitted when clear); [x]+:=max(x,0)[x]_+:= (x,0), intended component-wise for x∈ℝdx ^d; the fraction 0/00/0 is interpreted as +∞+∞. Capital letters denote matrices while boldface capital letters denote stacked agent variables, e.g., =[x1,…,xm]⊤ X=[x_1,…,x_m] , where the i-th row corresponds to agent i. We use calligraphic/script letters to denote stacked multiple matrices. Let mS^m, +mS^m_+ , and ++mS^m_++ be the set of m×m× m (real) symmetric, symmetric positive semidefinite, and symmetric positive definite matrices, respectively; (A) null(A) and (A) span(A) denote the nullspace and range of A, respectively. The eigenvalues of A∈mA ^m are ordered in nonincreasing order, denoted by λmax(A):=λ1(A)≥⋯λm(A)=:λmin(A) _ (A):= _1(A)≥·s _m(A)=: _ (A). Let ⟨X,Y⟩:=(X⊤Y) X,Y := tr(X Y), for any X and Y of suitable size, where (∙) tr( ) is the trace operator; ‖X‖M:=⟨MX,X⟩\|X\|_M:= MX,X , for any M∈++mM ^m_++ and X∈ℝm×dX ^m× d. For an operator T, () Fix(T) is the set of its fixed points; and :=(+)−1J_T:=(I+T)^-1 is the resolvent of T. For two operators A and B, (∘)(∙)(A )( ) stands for ((∙))A(B( )); I is the identity operator and 0 represents the zero operator. For a nonempty set C, aff() aff( C), and conv() conv( C), denote its affine hull, convex hull, respectively; par()=span(−) par( C)= span(C-C) is the subspace parallel to a convex set C. For an extended-value function ℒ L, dom(ℒ) dom( L) denotes its effective domain. We use δ _ C to denote the indicator function on the set C and f∗f^* stands for the Fenchel conjugate of function f, namely, f∗(y):=supx⟨y,x⟩−f(x)f^*(y):= _x \ y,x -f(x) \. Given x∈ℝdx ^d, α>0α>0 and r:ℝd→ℝ∪−∞,∞r:R^d ∪\-∞,∞\, α() prox_α r(x) denotes the proximal operator, defined as αr(x):=y∈ℝdr(y)+12α‖x−y‖2. prox_α r(x):= argmin_y ^dr(y)+ 12α\|x-y\|^2. Given a subspace T of ℝdR^d, P(x)P_T(x) denotes the unique orthogonal projection of x∈ℝdx ^d onto T. For some matrix-valued functions g,hg,h, we write g(X)=o(‖h(X)‖)g(X)=o(\|h(X)\|) if and only if limh(X)→0‖g(X)‖/‖h(X)‖=0 _h(X)→0\|g(X)\|/\|h(X)\|=0. Let ℳM be a 2C^2-smooth manifold of ℝdR^d around a point x. For any x′∈ℳx near x, we denote by ℳ(x′)T_M(x ) and ℳ(x′)N_M(x ) the tangent and normal spaces of ℳM at x′x , respectively. Sec. 2 presents the design of the proposed algorithm along with its decentralized implementation based on global-min consensus protocols on the agents’ stepsize values (Algorithm 1). Sec. 3 analyzes Algorithm 1 under convexity and establishes a sublinear convergence rate. Sec. 4 introduces a variant of Algorithm 1 (Algorithm 3) implementable using only neighboring communications running min-consensus, and proves its convergence. Sec. 5 establishes linear convergence of the proposed algorithms when the fif_i’s are strongly convex and r is partly smooth. Numerical experiments are reported in Sec. 6. 2 Algorithm Design We study Problem (P) under the following assumptions. Assumption 1. The objective function in (P) satisfies the following: (i) Each fi:ℝd→ℝf_i:R^d is convex on ℝdR^d and locally smooth; (i) Each ri:ℝd→ℝ∪−∞,∞r_i:R^d ∪\-∞,∞\ is convex, proper and lower-semicontinuous; and (i) f+rf+r is lower bounded. Assumption 2. The network underlying Problem (P) is modeled as an undirected, connected graph =(,ℰ)G=(V,E) with diameter d≥0d_G≥ 0, where =[m]V=[m] and (i,j)∈ℰ(i,j) if and only if there is an edge between agent i and j. Definition 2.1 (gossip matrices). W_G denotes the set of symmetric, doubly stochastic, gossip matrices W~:=(w~ij)i,j=1m W:=( w_ij)_i,j=1^m that are compliant with G, i.e., w~ii>0 w_i>0, for all i∈[m]i∈[m]; w~ij>0 w_ij>0 for all (i,j)∈ℰ(i,j) ; and w~ij=0 w_ij=0 otherwise. Gossip matrices are standard in the decentralized optimization literature, e.g., [Nedic_Olshevsky_Rabbat2018, Sayed-book]. 2.1 A three-operator splitting-based algorithm The proposed algorithm design hinges on the following reformulation of (P) leveraging the BCV technique: introducing local copies xi∈ℝdx_i ^d of x and slack variables x~i∈ℝd x_i ^d,the program (P’) min,~∈ℝm×dF()⏟:=F~(,~)+R()+δ0(~)⏟:=R~(,~)+δ0(Ł+M~)⏟:=G~(,~), _X, X ^m× d F(X)_:= F(X, X)+ R(X)+ _\0\( X)_:= R(X, X)+ _\0\( X+M X)_:= G(X, X), is equivalent to the original Problem (P). In (P’), we defined F():=∑i=1mfi(xi),R():=∑i=1mri(xi);F(X):= _i=1^mf_i(x_i), R(X):= _i=1^mr_i(x_i); δ0:ℝm×d→ℝ∪∞ _\0\:R^m× d ∪\∞\ is the indicator function of 0\0\; Ł∈m ^m satisfies null(Ł)=span(1m) null( )= span(1_m), and M∈++mM ^m_++ is the BCV metric. The matrix Ł enforces consensus among the agents’ variables xix_i’s via Ł=0 X=0. The choice of M will be shown to be crucial to enable a fully decentralized implementation of the proposed algorithm as well as adaptive local stepsize selection. This justifies the presence of G~ G in (P’), which is unconvential in the classical decentralized optimization literature. Under Assumption 1, finding a solution of Problem (P’) is equivalent to solving: (1) find :=[~]∈ℝ2m×d such that 0∈(++ℂ),find X:= bmatrixX\\ X bmatrix ^2m× d such that 0∈(A+B+C) X, where :=∂G~A:=∂ G, :=∂R~B:=∂ R and ℂ:=∇F~C:=∇ F. Invoking the Davis-Yin three-operator splitting [davis2017three], (1) is equivalent to (2) find ,∈ℝ2m×d s.t. α= and =α,find X, U ^2m× d\, s.t. \,D_α U= U\, and \, X=J_ U, where (3) α:=−α+α∘(2α−αℂ∘α),D_α:=I-J_ +J_ (2J_ -I- _ ), and α>0α>0 plays the role of the stepsize. Notice that α∂R~J_α∂ R (resp. α∂G~J_α∂ G) is equivalent to the proximal operator proxαR~ prox_α R (resp. proxαG~ prox_α G). One can solve (2) via the fixed-point Krasnosel’skii-Mann iteration [davis2017three]. Specifically, denoting by k:=[k;~k]∈ℝ2m×d A^k:=[A^k; A^k] ^2m× d the intermediate variable obtained by applying αJ_ , and allowing iteration-dependent stepsize values αk>0α^k>0, we have: (4) k=proxαR~k, X^k= prox_α R U^k, k+1=proxαG~(2k−k−α∇F~(k)), A^k+1= prox_α G (2 X^k- U^k-α∇ F( X^k) ), k+1=k+k+1−k. U^k+1= U^k+ A^k+1- X^k. Next, we design adaptive rules for αkk≥0\α^k\_k≥ 0 that guarantee convergence of (4). 2.2 Adaptive stepsize selection The proposed approach consists to identifying a suitable merit function that assesses the convergence of (4), and then devising stepsize update rules that guarantee a (possibly inexact) descent property for such a measure. To this end, we introduce the Lagrangian function (5) ℒ(,):=F~()+G~()+⟨,⟩−R~∗(), -2.84544ptL( X, S):= F( X)+ G( X)+ S, X - R^*( S), and interpret (4) as a primal–dual scheme for the saddle-point reformulation of (P’): min∈ℝ2m×dmax∈ℝ2m×dℒ(,), _ X ^2m× d _ S ^2m× dL( X, S), where X are the primal variables and S are the dual variables, the latter defined absorbing the U-variable in (4) as =[~]:=1α(−). S= bmatrixS\\ S bmatrix:= 1α ( U- X ). Using the S-variables, (4) reads (k+1,k+1):=αk(k,k)( X^k+1, S^k+1):=T_α^k( X^k, S^k), where (6a) k+1=proxαkR~(k+1+αkk),k+1=k+1αk(k+1−k+1), X^k+1= prox_α^k R ( A^k+1+α^k S^k ), S^k+1= S^k+ 1α^k( A^k+1- X^k+1), (6b) k+1=proxαkG~(k−αkk−αk∇F~(k)). A^k+1= prox_α^k G ( X^k-α^k S^k-α^k∇ F( X^k) ). Denoting by ∗×∗ P^*× D^* the set of saddles points of (5), we propose the following merit function: given (∗,∗)∈∗×∗( X^*, S^*)∈ P^*× D^* and αkk≥0\α^k\_k≥ 0, let (7) ∗∗k:=‖k−∗‖2+(αk−1)2‖k−∗‖2,k≥0. V_ X^* S^*^k:=\| X^k- X^*\|^2+(α^k-1)^2\| S^k- S^*\|^2, k≥ 0. Convergence of ∗∗k V_ X^* S^*^k is established in Lemma 2.5, which builds on Lemma 2.2, 2.4. Lemma 2.2. Suppose Assumption 1 holds. For any given (k,k,k)( A^k, X^k, S^k), αk>0α^k>0, and fixed (,)∈dom(ℒ)( X, S)∈ dom( L), (k+1,k+1,k+1)( A^k+1, X^k+1, S^k+1) given by (6a) satisfies: (8a) ‖k+1−‖2≤ \| X^k+1- X\|^2≤ ‖k−‖2+‖k+1−k+1‖2 \| X^k- X\|^2+\| A^k+1- X^k+1\|^2 −2αk(ℒ(k+1,k+1)−ℒ(,k+1)) -2α^k (L( A^k+1, S^k+1)-L( X, S^k+1) ) −‖~k+1−~k‖2−(1−αkLk)‖k+1−k‖2, -\| A^k+1- X^k\|^2- (1-α^kL^k )\|A^k+1-X^k\|^2, (8b) ‖k+1−‖2≤ \| S^k+1- S\|^2≤ ‖k−‖2−(1αk)2‖k+1−k+1‖2 \| S^k- S\|^2- ( 1α^k )^2\| A^k+1- X^k+1\|^2 +2αk(ℒ(k+1,k+1)−ℒ(k+1,)), + 2α^k (L( A^k+1, S^k+1)-L( A^k+1, S) ), where LkL^k is the local estimate of the curvature of F at kX^k along k+1−kA^k+1-X^k: (9) Lk:=2F(k+1)−F(k)−⟨∇F(k),k+1−k⟩‖k+1−k‖2≥0.L^k:=2\, F(A^k+1)-F(X^k)- ∇ F(X^k),A^k+1-X^k \|A^k+1-X^k\|^2≥ 0. Proof 2.3. See Sec. 2.4. Invoking ℒ(,∗)−ℒ(∗,)≥0,∀(,)∈dom(ℒ), L( X, S^*)- L( X^*, S)≥ 0, ∀( X, S)∈ dom( L), one infers from Lemma 2.2, the following inexact descent of ∗∗k V_ X^* S^*^k. Lemma 2.4. Under the conditions of Lemma 2.2, if αkα^k satisfies (9), then for all k≥0k≥ 0 and any given (∗,∗)∈∗×∗( X^*, S^*)∈ P^*× D^*, (10) ∗∗k+1≤∗∗k− V_ X^* S^*^k+1≤ V_ X^* S^*^k- ‖~k+1−~k‖2−(1−αkLk)‖k+1−k‖2−2αk∗∗k+1 \| A^k+1- X^k\|^2-(1-α^kL^k)\|A^k+1-X^k\|^2-2α^k G_ X^* S^*^k+1 +[(αk)2−(αk−1)2]‖k−∗‖2, + [(α^k)^2-(α^k-1)^2 ]\| S^k- S^*\|^2, where ∗∗k+1:=ℒ(k+1,∗)−ℒ(∗,k+1)≥0 G_ X^* S^*^k+1:= L( A^k+1, S^*)- L( X^*, S^k+1)≥ 0. In the inexact descent of ∗∗k V_ X^* S^*^k above, the only potentially positive contribution is [(αk)2−(αk−1)2]‖k−∗‖2. [(α^k)^2-(α^k-1)^2 ]\| S^k- S^*\|^2. To control this term while keeping the negative residuals in (10) effective, we propose the following updating rule for stepsize αkα^k: (11) 0<αk≤δLk,(αk)2−(αk−1)2≤min1−δ4‖k−k−1‖2‖k−0‖2,nk,0<α^k≤ δL^k, (α^k)^2-(α^k-1)^2≤ \ 1-δ4 \|A^k-X^k-1\|^2\| S^k- S^0\|^2,n^k \, where nk≥0k≥−1\n^k≥ 0\_k≥-1 is a sequence to be properly chosen, and δ∈(0,1)δ∈(0,1). The first condition, 1−αkLk≥1−δ>01-α^kL^k≥ 1-δ>0, ensures a uniform decrease contributed of ∗∗k+1 V_ X^* S^*^k+1 through the residual term ‖k+1−k‖2\|A^k+1-X^k\|^2 while the second condition controls the term [(αk)2−(αk−1)2]‖k−∗‖2[(α^k)^2-(α^k-1)^2]\| S^k- S^*\|^2 on the RHS of (10), by (12) [(αk)2−(αk−1)2]‖k−∗‖2≤1−δ2‖k−k−1‖2+2nk‖0−∗‖2. [(α^k)^2-(α^k-1)^2 ]\| S^k- S^*\|^2≤ 1-δ2\|A^k-X^k-1\|^2+2\,n^k\| S^0- S^*\|^2. The first term on the RHS above can be absorbed by a one-step shift of the Lyapunov function: ∗∗k V_ X^* S^*^k is replaced by the companion ∗∗k+1−δ2‖k−k−1‖2 V_ X^* S^*^k+ 1-δ2\|A^k-X^k-1\|^2. The second term in (12) is handled by requesting a summable budget ∑knk<∞ _kn^k<∞, given the lack of knowledge of ∗ S^*. This motivates the introduction of the merit function: (13) ~⋆⋆k:=⋆⋆k+1−δ2‖k−k−1‖2−2‖0−⋆‖2∑t=−1k−1nt, V_ X S ^k:= V^k_ X S + 1-δ2\|A^k-X^k-1\|^2-2\| S^0- S \|^2 _t=-1^k-1n^t, -5.69046pt which convergences monotonically along the iterates (6a), as summarized next. Lemma 2.5. Let (k,k,k)\( A^k, X^k, S^k)\ be the sequence generated by (6a), under Assumption 1, with αk\α^k\ satisfying (11), for some summable nk>0\n^k>0\. Then, for any given (∗,∗)∈∗×∗( X^*, S^*)∈ P^*× D^*, (14) ~∗∗k+1≤~∗∗k−‖~k+1−~k‖2−1−δ2‖k+1−k‖2−∗∗k+1. V_ X^* S^*^k+1≤ V_ X^* S^*^k-\| A^k+1- X^k\|^2- 1-δ2\|A^k+1-X^k\|^2- G_ X^* S^*^k+1. Moreover, limk→∞k+1−k=0 _k→∞ A^k+1- X^k=0. Therefore, the sequence ∗∗k\ V_ X^* S^*^k\ converges. Notice that the rule (11) produces nonmonotone, adaptive stepsize sequences. 2.3 Decentralized implementation The scheme in (6a), coupled with the stepsize update (11), is not yet decentralized. Indeed, the computation of proxαkG~ prox_α^k G and the quantities entering the stepsize rule require global information and thus cannot be carried out locally and independently by the agents. In this section, we address these two obstacles and derive a fully decentralized implementation of (6a). We begin decentralizing the computation of proxαkG~ prox_α^k G, leveraging the degree of freedom offered by the BCV rule (M matrix). Lemma 2.6 ([ryu2022large]). Let g(u)=f∗(A⊤u)g(u)=f^*(A u), with f:ℝn→ℝ∪−∞,∞f:R^n ∪\-∞,∞\ assumed to be convex, closed and proper. Suppose, ridomf∗∩range(A⊤)≠∅ ri\, dom\,f^*∩ range(A )≠ . Then v=proxα,g(u)v= prox_α,g(u) if and only if there exists x∈ℝnx ^n such that (15) x∈argminyf(y)−⟨u,Ay⟩+α2‖Ay‖2andv=u−αAx.x _y\f(y)- u,Ay + α2\|Ay\|^2\ v=u-α Ax. -2.84544pt Notice that G~=(δ0∗)∗∘[Ł,M] G=( _\0\^*)^* [ ,M], with δ0∗ _\0\^* denoting the conjugate of δ0 _\0\. Since δ0∗ _\0\^* is convex, closed and proper and ridomδ0∩Range([Ł,M]])≠∅ ri dom\, _\0\∩ Range([ ,M]])≠ , we can use (15) to express proxαkG~ prox_α^k G. Hence, (6b) can be rewritten as (16) k+1=[k+1~k+1]=[k−αkk−α∇F(k)~k−αk~k]−αk[ŁM]k+1, A^k+1= bmatrixA^k+1\\ A^k+1 bmatrix= bmatrixX^k-α^kS^k-α∇ F(X^k)\\ X^k-α^k S^k bmatrix-α^k bmatrix \\ M bmatrixY^k+1, where (17) k+1∈ ^k+1∈ argminδ0∗()−⟨~k−αk~k,M⟩ argmin_Y \ _\0\^*(Y)- X^k-α^k S^k,MY . −⟨k−αk−αk∇F(~k),Ł⟩+αk2(∥Ł∥2+∥M∥2). - ^k-α^kS^k-α^k∇ F( X^k), Y + α^k2 (\| Y\|^2+\|MY\|^2 )\. We proceed choosing M so that (17) admits a closed form solution, computable locally at the agents’ sides. Combining (6a), (16), and (see (6a)) (18) k+1=proxαkR(k+1+αkk)and~k+1=,X^k+1= prox_α^kR(A^k+1+α^kS^k) X^k+1=0, we have ~k=−Mk S^k=-MY^k, k≥1k≥ 1. Substituting ~k S^k in (17) and using δ0∗()=0δ^*_\0\(Y)=0, yields k+1∈argminαk‖−k∥Ł2+M22−2⟨Ł(k−αkk−αkŁk−αk∇F(k)),⟩. \!\!\!\!\!Y^k+1\!\!∈ argmin_Y\, \α^k\|Y-Y^k\|^2_ ^2+M^2\!-2 (X^k-\!α^kS^k-α^k Y^k-α^k∇ F(X^k)),Y \. Choosing M:=I−Ł2M:= I- ^2, Yk+1Y^k+1 admits a closed form expression: (19) k+1= ^k+1\!\!= k+1αkŁ(k−αkk−αkŁk−αk∇F(k)). ^k+ 1α^k (X^k\!-\!α^kS^k\!-\!α^k Y^k-α^k∇ F(X^k)). Introducing k:=ŁkD^k:= Y^k, and setting Ł2=I−W ^2=I-W, with W=(1−c)I+cW~∈W=(1-c)I+c W∈ W_G and c∈(0,1/2)c∈(0,1/2), (19) can be rewritten in terms of the D-variables as (20) k+1=k+1αk(I−W)(k−αk(k+k+∇F(k))),D^k+1=D^k+ 1α^k(I-W)(X^k-α^k(S^k+D^k+∇ F(X^k))), and so the update of the A-variables (using (16)): (21) k+1=Wk−αkW(∇F(k)+k+k)).A^k+1=WX^k-α^kW(∇ F(X^k)+S^k+D^k)). Finally, from (6a), we directly obtain the update of the S-variables. In summary, the proposed algorithm is given by (18), (20), (21), and (6a). The algorithm is now fully decentralized in the updates of X-, S- and D-variables. We are left to address the implementability of the adaptive stepsize selection rule (11) over the network. To make ‖k−0‖2=‖k−0‖2+‖~k−~0‖2\| S^k- S^0\|^2=\|S^k-S^0\|^2+\| S^k- S^0\|^2 computable from the agents, we need a decentralized way to evaluate (or upper bound) the slack term ‖~k−~0‖2\| S^k- S^0\|^2. To this end, we exploit the fact that (19) evolves kY^k through increments lying in range(Ł) range( ). We therefore introduce a tracking variable k∈ℝm×dT^k ^m× d (initialized at 0=0T^0=0) via k+1=k+1αkk−k−k−∇F(k),T^k+1=T^k+ 1α^kX^k-S^k-D^k-∇ F(X^k), -5.69046pt so that by construction and induction Łk=k−0 T^k=Y^k-Y^0. Recalling that ~k=−Mk S^k=-MY^k, we obtain ~k−~0=−MŁk. S^k- S^0=-M T^k. Consequently, ‖k−0‖2=‖k−0‖2+‖~k−~0‖2≤‖k−0‖2+2c‖k‖2. \| S^k- S^0\|^2=\|S^k-S^0\|^2+\| S^k- S^0\|^2≤\|S^k-S^0\|^2+2c\|T^k\|^2. This bound makes the stepsize rule implementable without maintaining ~k S^k (or kY^k). To satisfy the first condition in (11), we exploit the additive separability of LkL^k (see (9)), yielding the following sufficient condition for 0<αk≤δ/Lk0<α^k≤δ/L^k: for each agent i, find the largest αik>0 _i^k>0 satisfying the following local backtracking condition: (22) fi(aik+1)≤fi(xik)+⟨∇fi(xik),aik+1−xik⟩+δ2αik‖aik+1−xik‖2,f_i(a_i^k+1)≤ f_i(x_i^k)+ ∇ f_i(x_i^k),a_i^k+1-x_i^k + δ2α_i^k\|a_i^k+1-x_i^k\|^2, and set αik←αk:=mini∈[m]αik _i^k←α^k:= _i∈[m]α_i^k. In (22), aika_i^k, dikd_i^k, siks_i^k, xikx_i^k and tikt_i^k are the i−i-th row of kA^k, kD^k, kS^k, kX^k and kT^k, respectively. The proposed decentralized algorithm combining all the steps above is summarized in Algorithm 1, with the backtracking procedure provided in Algorithm 2. Algorithm 1 Decentralized Adaptive Three Operator Splitting Data: (i) Initialization: α−1∈(0,∞)α^-1∈(0,∞), 0,0∈ℝm×nX^0,S^0 ^m× n and −1,0,0,0=X^-1,A^0,D^0,T^0=0; (i) Backtracking parameters: summable sequence nk\n^k\, η∈(0,1)η∈(0,1), δ∈(0,1)δ∈(0,1); (i) Gossip matrix W=(1−c)I+cW~W=(1-c)I+c W, c∈(0,1/2)c∈(0,1/2). 1:(S.1) Communication Step: k+1/2=Wk,k+1/2=W(∇F(k)+k+k);X^k+1/2=WX^k, ^k+1/2=W(∇ F(X^k)+S^k+D^k); 2:(S.2) Decentralized line-search: Each agent updates αikα_i^k according to: (23) α~ik=(αik−1)2+min1−δ4‖aik−xik−1‖2‖sik−si0‖2+2c‖tik‖2,nk, α_i^k= ( _i^k-1)^2+ \ 1-δ4 \|a_i^k-x_i^k-1\|^2\|s_i^k-s_i^0\|^2+2c\|t_i^k\|^2,\,n^k \, αik=Linesearch(α~ik,xik,xik+1/2,−dik+1/2,η,δ);α_i^k= Linesearch( α_i^k,x_i^k,x_i^k+1/2,-d_i^k+1/2,η,δ); 3:(S.3) Global min-consensus: αik←αk:=mini∈[m]αik;α^k_i←α^k:= _i∈[m]α_i^k; 4:(S.4) Updates of the primal dual and tracking variables: (24a) k+1 ^k+1 =k+1/2−αkk+1/2, =X^k+1/2-α^kD^k+1/2, (24b) k+1 ^k+1 =proxαkR(k+1+αkk), = prox_α^kR(A^k+1+α^kS^k), (24c) k+1 ^k+1 =k+1αk(k+1−k+1), =S^k+ 1α^k(A^k+1-X^k+1), (24d) k+1 ^k+1 =k+1/2−∇F(k)−k+1αk(k−k+1/2), =D^k+1/2-∇ F(X^k)-S^k+ 1α^k(X^k-X^k+1/2), (24e) k+1 ^k+1 =k−k−k−∇F(k)+1αkk. =T^k-S^k-D^k-∇ F(X^k)+ 1α^kX^k. 5:(S.5) If a termination criterion is not met, k←k+1k← k+1 and go to step (S.1). Algorithm 2 Linesearch(α,x1,x2,d,η,δα,x_1,x_2,d,η,δ) 1:x+:=x2+αdx^+:=x_2+α d; set t=1t=1; 2:while f(x+)>f(x1)+⟨∇f(x1),x+−x1⟩+δ2α‖x+−x1‖2f(x^+)>f(x_1)+ ∇ f(x_1),x^+-x_1 + δ2α\|x^+-x_1\|^2 do 3: α←ηα←ηα; 4: x+←x2+αdx^+← x_2+α d; 5: t←t+1t← t+1; return α. On the global-min consensus: Step (S.3) in Algorithm 1 runs a network-wide min-consensus to enforce a common stepsize, αk=mini∈[m]αikα^k= _i∈[m] _i^k. This operation is compatible with modern wireless mesh networks that support multiple interfaces, e.g., WiFi and LoRa (Long- Range) [Kim_Lim_Kim_2016, Janssen_BniLam_Aernouts_Berkvens_Weyn_2020]: WiFi, which provides high-speed, short-range communication capabilities, can be used for exchanging vector variables in Step (S.1); and LoRa–supporting long-range communication over low rates–can broadcast the scalar αik _i^k to all nodes (possibly after coarse quantization) in a single communication to implement Step (S.3). A purely neighbor-based alternative relying on local min-consensus is developed in Sec. 4. 2.4 Proof of Lemma 2.2 Proof 2.7. By (6b), it holds that (25) 1αk(k−αkk−αk∇F~(k)−k+1)∈∂G~(k+1). 1α^k ( X^k-α^k S^k-α^k∇ F( X^k)- A^k+1 )∈∂ G( A^k+1). Invoking convexity of F~ F and G~ G yields (26) ‖k+1−‖2= \| X^k+1- X\|^2= ‖k−‖2−‖k+1−k‖2+‖k+1−k+1‖2 \| X^k- X\|^2-\| A^k+1- X^k\|^2+\| X^k+1- A^k+1\|^2 −2⟨k−k+1,k+1−⟩+2⟨k+1−k+1,k+1−⟩⏟term I -2 X^k- A^k+1, A^k+1- X +2 X^k+1- A^k+1, A^k+1- X _ term I Replacing the − X-update (6a) in the second part of term I, we have (27) term I≤(25) term I eq:subgradient G≤ −2αk(G~(k+1)−G~()−⟨k+1,k+1−⟩) -2α^k( G( A^k+1)- G( X)- S^k+1, A^k+1- X ) −2αk(F~(k)−F~())−2αk⟨∇F~(k),k+1−k⟩ -2α^k( F( X^k)- F( X))-2α^k ∇ F( X^k), A^k+1- X^k =(5) eq:new Lagarangian= −2αk(ℒ(k+1,k+1)−ℒ(,k+1)) -2α^k (L( A^k+1, S^k+1)-L( X, S^k+1) ) +2αk(F~(k+1)−F~(k)−⟨∇F~(k),k+1−k⟩)⏟term I. + 2α^k( F( A^k+1)- F( X^k)- ∇ F( X^k), A^k+1- X^k )_ term I. By the lifted structure of F~ F and definition of LkL^k in (9), it follows term I=2αk(F(k+1)−F(k)−⟨∇F(k),k+1−k⟩)=Lkαk‖k+1−k‖2. term I=2α^k(F(A^k+1)-F(X^k)- ∇ F(X^k),A^k+1-X^k )=L^kα^k\|A^k+1-X^k\|^2. Using the above expression along with (27) in (26), leads to (8a). We prove now (8b). By (6a), we have (28) k+1∈∂R~(k+1)⇒k+1∈∂R~∗(k+1). S^k+1∈∂ R( X^k+1) X^k+1∈∂ R^*( S^k+1). -5.69046pt By (6a) and convexity of R~∗ R^*, ‖k+1−‖2= \| S^k+1- S\|^2= ‖k−‖2−(1αk)2‖k+1−k+1‖2 \,\| S^k- S\|^2- ( 1α^k )^2\| A^k+1- X^k+1\|^2 +2⟨k+1−,1αk(k+1−k+1)⟩ +2 S^k+1- S, 1α^k( A^k+1- X^k+1) ≤(28) eq:subgradient R*≤ ‖k−‖2−(1αk)2‖k+1−k+1‖2 \| S^k- S\|^2- ( 1α^k )^2\| A^k+1- X^k+1\|^2 +2αk(⟨k+1−,k+1⟩−(R~∗(k+1)−R~∗())) + 2α^k ( S^k+1- S, A^k+1 - ( R^*( S^k+1)- R^*( S) ) ) =(5) eq:new Lagarangian= ‖k−‖2−(1αk)2‖k+1−k+1‖2 \| S^k- S\|^2- ( 1α^k )^2\| A^k+1- X^k+1\|^2 +2αk(ℒ(k+1,k+1)−ℒ(k+1,)). + 2α^k (L( A^k+1, S^k+1)-L( A^k+1, S) ). 3 Convergence Analysis of Algorithm 1 For analytical convenience, we will work with the stacked formulation (6a). Since 0=0∈span(I−W)D^0=0∈ span(I-W), Algorithm 1 is equivalent to (6a), provided that the stepsize αkα^k is updated according to the backtracking rule in (S.3). Henceforth, we will freely refer to (6a) while implicitly invoking this equivalence. Accordingly, we will use ~∗,∗k\ V^k_ X^*, S^*\ as defined in (13)–with ∗,∗k\ V^k_ X^*, S^*\ given by (7)–to be evaluated along the iterates generated by Algorithm 1 (with a slight abuse of notation). 3.1 Asymptotic convergence Building on Lemma 2.5, we begin establishing boundedness of the iterates and the stepsizes generated by Algorithm 2. Lemma 3.1. Let (k,k,k)\( A^k, X^k, S^k)\ be the sequence generated by Algorithm 1 under Assumption 1, and some summable nk>0\n^k>0\ in (23); the following hold: (i) For any k≥0k≥ 0, (29) ~∗∗k+1≤~∗∗k−‖~k+1−~k‖2−1−δ2‖k+1−k‖2−∗∗k+1, V_ X^* S^*^k+1≤ V_ X^* S^*^k-\| A^k+1- X^k\|^2- 1-δ2\|A^k+1-X^k\|^2- G_ X^* S^*^k+1, -5.69046pt and limk→∞k+1−k=0 _k→∞ A^k+1- X^k=0; hence ∗∗k\ V^k_ X^* S^*\ convergences; and kk≥0\ X^k\_k≥ 0, αk−1kk≥0\α^k-1 S^k\_k≥ 0 and kk≥0\ A^k\_k≥ 0 are bounded. Consequently, the set ℋ:=conv H:= conv (∪k=0∞[k,k+1]) ( _k=0^∞[X^k,A^k+1] ) is compact and there exists Lf∈(0,∞)L_f∈(0,∞) such that F is LfL_f-smooth on ℋ H. Furthermore, (30) αk≥α¯:=minα−1,ηδLf>0,∀k≥0,α^k≥ α:= \α^-1, ηδL_f \>0, ∀ k≥ 0, -2.84544pt and thus kk≥0\ S^k\_k≥ 0 is bounded; (i) αk\α^k\ converges and limk→∞αk=α≥α¯ _k→∞α^k=α≥ α. Proof 3.2. (i) Notice that the stepsize sequence, as generated from (S.2) and (S.3) in Algorithm 1, still satisfies the bounds (11). Therefore the conclusions of Lemma 2.5 are applicable also to Algorithm 1. This proves (29), convergence of ~∗∗\ V_ X^* S^*\, and limk→∞k+1−k=0 _k→∞ A^k+1- X^k=0. Consequentially, ∗∗k\ V^k_ X^* S^*\ also convergence. Convergence of ∗∗k\ V^k_ X^* S^*\ implies the boundedness of k\ X^k\ and αk−1k\α^k-1 S^k\; and, from ‖k+1−k‖→0\| A^k+1- X^k\|→ 0, also that of k\ A^k\. Therefore ℋ H is compact and F is smooth on ℋ H. The line-search then guarantees the uniform lower bound (30). Finally, boundedness of αk−1k\α^k-1 S^k\ together with αk−1≥α¯α^k-1≥ α implies boundedness of k\ S^k\. (i) Using (αk)2≤(αk−1)2+nk(α^k)^2≤(α^k-1)^2+n^k, for all k≥0k≥ 0, yields (αk)2≤(α0)2+∑t=1knt≤α¯(α^k)^2≤(α^0)^2+ _t=1^kn^t≤ α, for some α¯<∞ α<∞, due to the summability of nk\n^k\. Therefore, α¯≤αk≤α¯ α≤α^k≤ α. We next show that the line-search decreases αkα^k only finitely many times. If a strict decrease occurs at iteration k≥1k≥ 1, αk<αk−1α^k<α^k-1, it must be (31) αk≤η(αk−1)2+nk.α^k≤η (α^k-1)^2+n^k. Since ∑t=0∞nt<∞ _t=0^∞n^t<∞, there exists K≥1K≥ 1 such that (32) ∑t=k∞nt<1−η22(α¯)2,∀k≥K. _t=k^∞n^t< 1-η^22( α)^2, ∀ k≥ K. -2.84544pt Suppose a strict decrease happens at k≥Kk≥ K. Then for any k′≥k ≥ k, it holds (αk′)2≤η2[(αk−1)2+nk]+∑t=k+1k′nt≤(32)(η2+1−η22)(αk−1)2<(αk−1)2.(α^k )^2≤η^2 [(α^k-1)^2+n^k ]+ _t=k+1^k n^t eq:never come back≤ (η^2+ 1-η^22 )(α^k-1)^2<(α^k-1)^2. Thus after k≥Kk≥ K, every strict decrease at k maintains αk′<αk−1α^k <α^k-1 for all subsequent k′≥k ≥ k. Since αk≥α¯>0α^k≥ α>0 for all k, these decrease events can occur only finitely many times; hence, αk\α^k\ is eventually nondecreasing; being also bounded, it converges. We are now ready to state the asymptotic convergence of Algorithm 1. Theorem 3.3. Under the conditions of Lemma 3.1, the iterates (k,k)k≥0\( X^k, S^k)\_k≥ 0 converge to to some (∗,∗)∈∗×∗( X^*, S^*)∈ P^*× D^*. Moreover, letting x∗x^* being any minimizer of Problem (P), it holds limk→∞k=∗:=1(x∗)⊤ _k→∞X^k=X^*:=1(x^*) . Proof 3.4. By Lemma 3.1(i), the sequences k\ X^k\, k\ S^k\ (and k\ A^k\) are bounded; hence there exists a subsequence Nk⊂ℕ+\N_k\ _+ such that (Nk,Nk)→(∗,∗),( X^N_k, S^N_k)→( X^*, S^*), and αNk→α^N_k→α. Further, since limk→∞k+1−k _k→∞ A^k+1- X^k=0, it can be derived that the sequence (Nk+1,Nk+1)\( X^N_k+1, S^N_k+1)\ also converge to (∗,∗)( X^*, S^*). Since (k+1,k+1)=αk(k,k)( X^k+1, S^k+1)=T_α^k( X^k, S^k) and α(,)T_α( X, S) is continuous in (,,α)( X, S,α), passing to the limit (along Nk\N_k\) yields (∗,∗)=α(∗,∗)( X^*, S^*)=T_α( X^*, S^*). Following similar steps as in [davis2017three, Lemma 2.2], one can show that (∗,∗)∈⋆×⋆( X^*, S^*) ×D . We now prove convergence of the whole sequence. By Lemma 2.5, for any saddle point (∗,∗)( X^*, S^*) the merit sequence ∗∗k V^k_ X^* S^* in (7) convergences (to some finite limit). On the other hand, along the subsequence Nk\N_k\ we have (Nk,Nk)→(∗,∗)( X^N_k, S^N_k)→( X^*, S^*), so ∗∗Nk→0 V^N_k_ X^* S^*→ 0. Therefore, it must be ∗∗k→0 V^k_ X^* S^*→ 0. This implies k→∗ X^k→ X^*. Moreover, since αk−1≥α¯>0α^k-1≥ α>0, we also obtain ‖k−∗‖2≤α¯−2∗∗k→0\| S^k- S^*\|^2≤ α^-2 V^k_ X^* S^*→ 0, i.e., k→∗ S^k→ S^*. Hence (k,k)→(∗,∗)( X^k, S^k)→( X^*, S^*). From (∗,∗)∈⋆×⋆( X^*, S^*) ×D , ∗ X^* is a primal optimal solution of (P); thus ∗=(x∗)⊤ X^*= 1(x^*) for some minimizer x∗x^*, and consequently limk→∞k=∗=1(x∗)⊤ _k→∞X^k=X^*=1(x^*) . On the design of the summable sequence nk\n^k\ The sequence nk\n^k\ controls the amount of increase of the stepsize between two consecutive iterations. For convergence nkn^k\ is requested to be summable. This naturally suggests the following rule (33) nk=β(k+1)p,β>0,p>1.n^k= β(k+1)^p, β>0,\ \ p>1. -2.84544pt This choice may be conservative when occasional backtracking events make αkα^k drop. To be adaptive, nk\n^k\ should not decay solely because k grows, especially during phases in which αkα^k is forced to remain small due to a large local curvature estimate LkL^k. Next we propose a rule that “restarts” nkn^k after a significant drop of the stepsize. More formally, for fixed η′∈(η,1)η ∈(η,1), define the set of “drop times” up to k as (34) k:=j∈0,…,k:αj≤η′min0≤t≤j−1αt,K^k:= \j∈\0,…,k\:\ α^j≤η _0≤ t≤ j-1α^t \, with the convention min0≤t≤−1αt=α−1 _0≤ t≤-1α^t=α^-1 Define the reset counter and time since last reset respectively as rk:=|k|andτrk:=k−maxk,r^k:=|K^k| _r^k:=k- ^k, with the convention max∅=−1 =-1 (so if no drop occurs up to k, then τrk=k+1 _r^k=k+1). Fix β>0β>0 and exponents p>1p>1, q>1q>1. Define, for all k≥0k≥ 0, (35) nk:=β(rk+1)q⋅1(τrk+1)p.n^k:= β(r^k+1)^q· 1( _r^k+1)^p. The rationale of the above rule is the following: τrk _r^k grows while no new drop occurs (so the decay persists during “stalls”), whereas rkr^k grows with the number of drops (so the total remains summable even if drops happen often). Lemma 3.5. The sequence nk\n^k\ defined in (35) is summable, for every sequence αk>0\α^k>0\, β>0β>0, and p,q>1p,q>1. Specifically, letting Sp:=∑t=1∞t−p<∞S_p:= _t=1^∞t^-p<∞ and Sq:=∑t=1∞t−q<∞S_q:= _t=1^∞t^-q<∞, it holds ∑k=0∞nk≤βSpSq. _k=0^∞n^k≤β\,S_p\,S_q. 3.2 Complexity analysis Next we establish the convergence rate of Algorithm 1. For any given saddle-point (∗,∗)( X^*, S^*) of ℒL, let ℬX×ℬSB_X×B_S be a bounded set containing (∗,∗)( X^*, S^*); and let us introduce the partial primal-dual gap function [chambolle2011first]: (36) ℬX×ℬS(,):=max′∈BSℒ(,′)−min′∈ℬXℒ(′,).G_B_X×B_S( X, S):= _ S ∈ B_SL( X, S )- _ X _XL( X , S). -2.84544pt Notice that ℬX×ℬS(,)≥0G_B_X×B_S( X, S)≥ 0, for any (,)∈dom(ℒ)( X, S)∈ dom(L). Yet, ℬX×ℬSG_B_X×B_S is not a valid measure of optimality because it might vanish for (,)( X, S) not being a saddle-point of ℒL [chambolle2011first]. However, if ℬX×ℬS(,)=0G_B_X×B_S( X, S)=0 for (,)∈dom(ℒ)( X, S)∈ dom(L) and, in addition, (,)( X, S) lies in the interior of ℬX×ℬSB_X×B_S, then (,)( X, S) is a saddle-point of ℒL. Since (k,k,k)( X^k, A^k, S^k) generated by Algorithm 1 is bounded (Lemma 3.1), one can always choose a “sufficiently large” ℬX×ℬSB_X×B_S such that ℬX×ℬS(,)G_B_X×B_S( X, S) is a valid measure of optimality for (,)( X, S). We provide next the convergence rate decay of ℬX×ℬSG_B_X×B_S. Define the ergodic sequences of the iterates k\ A^k\ and k\ S^k\: (37) ¯k:=1θk∑t=1kαt−1t and ¯k:=1θk∑t=1kαt−1t, with θk:=∑t=1kαt−1. A^k:= 1θ^k _t=1^kα^t-1 A^t\,\, and \,\, S^k:= 1θ^k _t=1^kα^t-1 S^t,\,\, with \,\,θ^k:= _t=1^kα^t-1. -8.5359pt Theorem 3.6. Under the assumptions of Lemma 3.1, fix any saddle point (∗,( X^*, ∗)∈⋆×⋆ S^*) ×D and consider the set (38) ℬX×ℬS:=(,):‖−∗‖2+(α¯)2‖−∗‖2≤10ℛ∗∗,B_X×B_S:= \( X, S):\| X- X^*\|^2+( α)^2\| S- S^*\|^2≤ 10\, R_ X^* S^* \, where ℛ∗∗ R_ X^* S^* is defined in (40a) below. Then: (i) (∗,∗)∈ℬX×ℬS( X^*, S^*) _X×B_S; (i) (k+1,k+1)∈int(ℬX×ℬS)( A^k+1, S^k+1)∈ int(B_X×B_S), for all k≥0k≥ 0; and (i) for all k≥1k≥ 1, (39) ℬX×ℬS(¯k,¯k)≤1k⋅ℛ¯∗∗min(α−1,(ηδ)/L∇k)=(1k),G_B_X×B_S( A^k, S^k)≤ 1k· R_ X^* S^* (α^-1,(ηδ)/L_∇^k )=O ( 1k ), where L∇k(≤Lf)L_∇^k(≤ L_f) is the Lipschitz constant of ∇F∇ F over ℋk=conv(∪t=0k−1[t,t+1]) H^k= conv ( _t=0^k-1[X^t,A^t+1] ) and ℛ¯∗∗ R_ X^* S^* is defined in (40b). Shorthands used in Thm. 3.6. Define (40a) ℛ∗∗:=∗∗0+‖0−∗‖2∑t=0∞nt<∞,and set R_ X^* S^*:= V^0_ X^* S^*+\| S^0- S^*\|^2 _t=0^∞n^t\;<\;∞, set -14.22636pt (40b) ℛ¯∗,∗:=cαℛ∗∗,withcα:=5(α−1)2+∑t=0∞nt(α¯)2. R_ X^*, S^*:=c_α\, R_ X^* S^*, c_α:=5\, (α^-1)^2+ _t=0^∞n^t( α)^2. -8.5359pt Proof 3.7. From (29) in Lemma 3.1(i) and 0=−1=A^0=X^-1=0, we have ∗∗k≤ℛ∗∗ V^k_ X^* S^*≤ R_ X^* S^*, for all k≥0k≥ 0. Item (i) is immediate from (38). By (6a), it holds (k+1,k+1)∈int(ℬX×ℬS)( A^k+1, S^k+1)∈ int(B_X×B_S); hence ℬX×ℬS(¯k,¯k) G_ B_X× B_S( A^k, S^k) is a valid measure of optimality and progress of the algorithm. Replacing (∗,∗)( X^*, S^*) in (29) with any (′,′)( X , S ) and telescoping, yield: for any k≥1k≥ 1, (41) 2∑t=1kαt−1(ℒ(t,′)−ℒ(′,t))≤′,′0+‖0−′‖2∑t=0∞nt.2 _t=1^kα^t-1( L( A^t, S )- L( X , S^t))≤ V^0_ X , S +\| S^0- S \|^2 _t=0^∞n^t. -5.69046pt Dividing both sides of (41) by 2θk2 _k, leveraging convexity of ℒ(∙,′)−ℒ(′,∙) L( , S )- L( X , ), and taking the maximum of (′,′)( X , S ) over ℬX×ℬS B_X× B_S on both sides, yields ℬX×ℬS(¯k,¯k)G_B_X×B_S( A^k, S^k) ≤(ℛ¯∗∗)/θk≤( R_ X^* S^*)/θ^k, where θk≥∑t=1kmin(α−1,(ηδ)/L~t−1)≥k⋅min(α−1,(ηδ)/L~k).θ^k≥ _t=1^k (α^-1,(ηδ)/ L^t-1 )≥ k· (α^-1,(ηδ)/ L^k). Theorem 3.6 proves that Algorithm 1 attains a sublinear (1/k)O(1/k) rate, matching state-of-art algorithms for decentralized convex optimization problems. Crucially, it does so without requiring prior knowledge of optimization or network parameters, unlike existing native decentralized schemes for Problem (P) (e.g., [shi2015proximal, guo2023decentralized]). Moreover, the bound in (39) is governed by local Lipschitz constants L∇k\L^k_∇\, along the trajectory, which are often much smaller than the global constants used in non-adaptive methods—highlighting DATOS’ adaptation to the local geometry of F. 4 From Global to Local Min-consensus In this section we introduce a variant of Algorithm 1 wherein the global min-consensus in (S.3) is replaced by a local one–see Algorithm 3. Step (S.3) therein produces different local stepsizes, collected in Λk:=diag(α1k,α2k,⋯,αmk) ^k:= diag( _1^k, _2^k,·s, _m^k), and requires only neighboring communications. We also used the shorthand proxΛk,R():=[proxα1kr1(x1), prox_ ^k,R(X):=[ prox_ _1^kr_1(x_1), ⋯,proxαmkrm(xm)]⊤.·s, prox_ _m^kr_m(x_m)] . Algorithm 3 Decentralized Adaptive Three Operator Splitting with local min-consensus (local_DATOS) Data: (i) Initialization: αi−1∈(0,∞) _i^-1∈(0,∞), 0,0∈ℝm×nX^0,S^0 ^m× n and −1,0,0,0=0X^-1,A^0,D^0,T^0=0; (i) Backtracking parameters: summable sequence mk\m^k\, η∈(0,1)η∈(0,1), δ∈(0,1)δ∈(0,1); (i) Gossip matrix W=(1−c)I+cW~W=(1-c)I+c W, c∈(0,1/2)c∈(0,1/2). 1:(S.1) Communication Step: k+1/2=Wk,k+1/2=W(∇F(k)+k+k);X^k+1/2=WX^k, ^k+1/2=W(∇ F(X^k)+S^k+D^k); 2:(S.2) Decentralized line-search: Each agent updates αik _i^k according to: α~ik=(αik−1)2+mk, α_i^k= ( _i^k-1)^2+m^k, αik=Linesearch(α~ik,xik,xik+1/2,−dik+1/2,η,δ); _i^k= Linesearch( α_i^k,x_i^k,x_i^k+1/2,-d_i^k+1/2,η,δ); 3:(S.3) Local min-consensus: Each agent updates αik _i^k according to: αik←minj∈iαjk; _i^k← _j∈ N_i _j^k; 4:(S.4) Extra scalar communication step: Let Λk:=diag(α1k,α2k,⋯,αmk) ^k:= diag( _1^k, _2^k,·s,α^k_m), Λk=(I−W)(Λk)−1k;D_ ^k=(I-W)( ^k)^-1X^k; 5:(S.5) Updates of the primal and dual variables: (42a) k+1 ^k+1 =k+1/2−Λkk+1/2, =X^k+1/2- ^kD^k+1/2, (42b) k+1 ^k+1 =proxΛk,R(k+1+Λkk), = prox_ ^k,R(A^k+1+ ^kS^k), (42c) k+1 ^k+1 =k+(Λk)−1(k+1−k+1), =S^k+( ^k)^-1(A^k+1-X^k+1), (42d) k+1 ^k+1 =k+1/2+Λk−∇F(k)−k; =D^k+1/2+D_ ^k-∇ F(X^k)-S^k; 6:(S.6) If a termination criterion is not met, k←k+1k← k+1 and go to step (S.1). In step (S.2), the proposed stepsize updating enforces (43) 0<αmink≤δLk,maxi∈[m][(αik)2−(αik−1)2]≤mk,0< _ ^k≤ δL^k, _i∈[m] [( _i^k)^2-( _i^k-1)^2 ]≤ m^k, -2.84544pt where mk\m^k\ is a summable sequence and αmink:=mini∈[m]αikα^k_ := _i∈[m] _i^k. At a high level, using the same slack sequence mk\m^k\ across agents prevents persistent stepsize heterogeneity and is instrumental to ensure that eventually Λk ^k becomes close to αminkI _ ^kI (indeed equal, under a mild lower bound); this property is key in the convergence analysis. Lemma 4.1 (finite-time min-consensus). Consider Algorithm 3 under Assumptions 1 and 2.1. If αmink≥α¯ _ ^k≥ α, for some α¯>0 α>0 and all k≥0k≥ 0, then there exists K′>1K >1 such that Λk=αminkI ^k=α^k_ I, for all k≥K′k≥ K . Proof 4.2. Define αmaxk:=maxiαik _ ^k:= _i _i^k and let d_G be the graph diameter. Since mk\m^k\ is summable, there exists K>0K>0 such that (44) ∑t=k∞mt<1−η22(α¯)2,∀k≥K. _t=k^∞m^t< 1-η^22( α)^2, ∀ k≥ K. -2.84544pt Fix k≥Kk≥ K. Suppose that at iteration k some agent i∈[m]i∈[m] decreases its stepsize (i.e., it backtracks in (S.2)). Then necessarily (αik)2≤η2[(αik−1)2+mk].( _i^k)^2≤η^2[( _i^k-1)^2+m^k]. Next, we relate this decrease at agent i to αmax _ after at most d_G iterations. By the local min-consensus step (S.3), the value αik _i^k is propagated through the network and affects all agents within d_G iterations; meanwhile, by (43), the squared stepsizes can increase by at most mtm^t at each iteration. Therefore, for any k′≥k+dk ≥ k+d_G it holds (αmaxk′)2≤(αik)2+∑t=k+1k′mt≤(44)(η2+1−η22)(αik−1)2≤η2+12(αmaxk−1)2.( _ ^k )^2≤( _i^k)^2+ _t=k+1^k m^t eq:never come back 2≤ (η^2+ 1-η^22 )( _i^k-1)^2≤ η^2+12( _ ^k-1)^2. -2.84544pt Hence, αik _i^k can decrease only finitely many times; otherwise, repeated contractions would force αmaxk→0 _ ^k→ 0, contradicting the assumption αmink≥α¯>0 _ ^k≥ α>0. Therefore, there exists K0≥K_0≥ K such that no agent decreases its stepsize for any k≥K0k≥ K_0. Once no stepsizes decrease, (S.3) makes all stepsizes equal within at most d_G iterations. Therefore, there exists K′:=K0+dK :=K_0+d_G such that Λk=αminkI ^k= _ ^kI for all k≥K′k≥ K . Remark 4.3. Lemma 4.1 assumes αmink _ ^k is bounded away from 0. This holds e.g., when each fif_i is globally smooth, or when k\X^k\ is bounded (for example, if rir_i’s contain the indicator function of a compact set). With Lemma 4.1, there exists K′>1K >1 such that, for all k≥K′k≥ K , Λk=αminkI ^k= _ ^kI. Hence, from iterate K′K onword, Algorithm 3 enerates the same recursion as Algorithm 1, with the uniform stepsize αk:=αminkα^k:= _ ^k. Therefore, the convergence analysis of Algorithm 1 can be restarted at time K′K , taking (K′,K′)( X^K , S^K ) as the new “initial point”. Since the descent inequality in (29) holds for all k≥K′k≥ K , the asymptotic convergence of Algorithm 3 is proved following the same arguments as in Theorem 3.3 (∗∗k V^k_ X^* S^* is defined here as in (7) but with αk=αminkα^k= _ ^k). To establish a convergence rate for Algorithm 3, we follow the proof of Theorem 3.6, starting from k≥K′k≥ K . The rate therein is derived via telescoping argument on (29) and it requires a bounded set ℬX×ℬSB_X×B_S containing the trajectory, so that the partial gap ℬX×ℬSG_B_X×B_S is a valid measure of optimality. Since k\ X^k\ is already controlled by the Lyapunov descent once the stepsize is uniform, it is sufficient to guarantee boundedness of the dual iterates k\ S^k\ after K′K . This is established next, using summability of mk\m^k\; ∗∗k V^k_ X^* S^* below is defined as in (7) with αk=αminkα^k= _ ^k. Lemma 4.4. Under the conditions of Lemma 4.1, for any k≥K′k≥ K , (45) ‖k−∗‖2≤RS:=(2∗∗K′)/(α¯)2.\| S^k- S^*\|^2≤ R_S:=(2 V^K _ X^* S^*)/( α)^2. Proof 4.5. Without loss of generality, take K′K large enough so that (44) holds with k=K′k=K . We prove (45) by induction on k≥K′k≥ K . For k=K′k=K , using αminK′≥α¯ _ ^K ≥ α, we have (α¯)2‖K′−∗‖2≤∗∗K′( α)^2\| S^K - S^*\|^2≤ V^K _ X^* S^*. Assume now that ‖t−∗‖2≤RS\| S^t- S^*\|^2≤ R_S for all t=K′,…,kt=K ,…,k. Since Λt=αmintI ^t= _ ^tI for all t≥K′t≥ K (Lemma 4.1), starting from Lemma 2.4, the same descent estimate as in (29) (Lemma 3.1(i)) can be proved here from K′K onward, with the increment budget controlled by mtm^t; in particular, combining this result with the induction hypothesis yields (α¯)2‖k+1−∗‖2≤∗∗K′+RS∑j=K′kmj≤(44)2∗∗K′⇒‖k+1−∗‖2≤RS.( α)^2\| S^k+1- S^*\|^2≤ V^K _ X^* S^*+R_S _j=K ^km^j eq:never come back 2≤2 V^K _ X^* S^* \| S^k+1- S^*\|^2≤ R_S. This completed the proof by induction. Lemma 4.1 and Lemma 4.4 allow us obtain sublinear convergence of Algorithm 3 for all k≥K′k≥ K , repeating the same argument used in the proof of Theorem 3.6. Theorem 4.6. Let (k,k,k)\( X^k, A^k, S^k)\ be the iterates generated by Algorithm 3, under Assumptions 1 and 2.1; and suppose αmink≥α¯ _ ^k≥ α, for some α¯>0 α>0 and all k≥0k≥ 0. Then (k,k)\( X^k, S^k)\ converges to some (∗,∗)∈⋆×⋆( X^*, S^*) ×D . Moreover, for any given (∗,∗)∈⋆×⋆( X^*, S^*) ×D , there exist a bounded set ℬX×ℬSB_X×B_S and K′≥1K ≥ 1, such that (i) (∗,∗)∈ℬX×ℬS( X^*, S^*) _X×B_S, and (k,k)∈int(ℬX×ℬS)( A^k, S^k)∈ int(B_X×B_S), for all k≥K′k≥ K ; and (i) for any k≥K′k≥ K , it holds (46) ℬx×ℬS(¯k,¯k)≤1k−K′⋅CK′+(1+αK′−120(α¯)2+3)2∗,∗K′2⋅min(α−1,δ/(2L~k)),G_B_x×B_S( A^k, S^k)≤ 1k-K · C_K + (1+α^K -1 20( α)^2+3 )^2V^K _ X^*, S^*2· (α^-1,δ/(2 L^k) ), where CK′:=2∑t=1K′αmint−1ℬX×ℬS(t,t)C_K :=2 _t=1^K α^t-1_ G_B_X×B_S( A^t, S^t), and (¯k,¯k)( A^k, S^k) is defined as in (37) (with the convention that the averaging starts at K′K ). Theorem 4.6 certifies convergence of Algorithm 3 at sublinar rate. The primary distinction between the local-min and global-min consensus procedures is that the local-min does not guarantee a monotonically decrease of the merit function during the initial K′K iterations. Nevertheless, as shown numerically in Sec. 6, Algorithm 3 performs comparably to Algorithm 1 while requiring only neighbor communications. 5 Linear Convergence for Partly Smooth Functions In this section, we strengthen the convergence guarantees of the proposed adaptive algorithms by establishing an asymptotic linear rate, for instances of Problem (P) where the agents’ losses are (locally) strongly convex at the limit point and the nonsmooth (convex) term R enjoys a partial smoothness property. This is necessary because, for Davis-Yin three-operator splitting, linear convergence generally cannot be guaranteed under the sole assumption that F is strongly convex when R is an arbitrary convex nonsmooth function, due to the possible irregularity of subgradients (see, e.g., [davis2017three, Theorem 3.5]). Partly smooth functions [lewis2002active] form a broad class that arises in many areas, including signal processing/machine learning, imaging, and control and system identification, among others [liang2017activity]. Due to space limitations, we present the analysis only for Algorithm 1; analogous conclusions can be established for Algorithm 3. 5.1 Partial Smoothness amd finite identification Let ℳM be a 2C^2 embedded submanifold of ℝdR^d around x∈ℳx . Given a function r:ℝd→ℝ¯r:R^d→ R, the restriction of r to ℳM is the function r|ℳ:ℳ→ℝ¯r|_M:M→ R defined by r|ℳ(z)=r(z)r|_M(z)=r(z) for all z∈ℳz . We say that r|ℳr|_M is 2C^2-smooth around x∈ℳx if there exist an open neighborhood V⊆ℝdV ^d of x and a 2C^2 function r^:V→ℝ r:V such that r^(z)=r(z) r(z)=r(z) for all z∈ℳ∩Vz ∩ V; any such r r is called a 2C^2 representative (extension) of r|ℳr|_M around x. Definition 5.1 (Partly smoothness [lewis2002active, Def. 2.7]). Given the set ℳ⊆ℝdM ^d, let r:ℝd→ℝ¯r:R^d→ R be proper, lower semicontinuous, and convex, and let x∈ℳx be given such that r has subgradient at x and any point close to x in ℳM. We say that r is partly smooth at x∈ℳx relative to ℳM if ℳM is a 2C^2-manifold around x and (i) (Restricted smoothness) r|ℳr|_M is 2C^2-smooth around x; (i) Sharpness: ℳ(x)≡par(∂r(x))⟂T_M(x)≡ par(∂ r(x)) ; (i) Continuity: ∂r∂ r is inner semicontinuous at x relative to ℳM. This class is denoted by psfℳ(x) psf_M(x). By Theorem 3.3, the iterates generated by Algorithm 1 converge to an optimal consensual point ⋆=(x⋆)⊤X =1(x ) , for some solution x⋆x of (P). In the remainder of this section, we postulate the following local structure at these limit points. Assumption 3 (Local structure around x⋆x ). Let ⋆=(x⋆)⊤X =1(x ) be the limit point of the sequence generated by Algorithm 1, as provided by Theorem 3.3. Assume: (i) (local strong convexity) There exist μ>0μ>0 and a neighborhood U of ⋆X such that F is μ-strongly convex on U, with μ>0μ>0; (i) (partly smoothness) There exists a 2C^2 manifold ℳM around x⋆x such that ri∈psfℳ(x⋆)r_i∈ psf_M(x ), for every i∈[m]i∈[m]; (i) Non-degeneracy: −∇F(⋆)∈ri(∂R(⋆))-∇ F(X )∈ ri(∂ R(X )). Under Assumption3(i), by separability of partial smoothness [lewis2002active, Prop. 4.5], R()=∑i=1mri(xi)∈psfℳR(⋆),ℳR≜ℳ×⋯×ℳ⊆ℝm×d.R(X)= _i=1^mr_i(x_i)∈ psf_M_R(X ), _R ×·s×M ^m× d. -5.69046pt A key consequence of partial smoothness is the finite time identification: after a finite number of iterations, the primal iterates of Algorithm 1 enter (and remain on) the active manifold containing the limit point. This property is formalized next. Theorem 5.2 (identification). Let k\X^k\ be the (primal) sequence generated by Algorithm 1 in the setting of Theorem 3.3, k→⋆=(x⋆)⊤X^k =1(x ) . If Assumption 3 holds at ⋆X , then there exists K2≥K1K_2≥ K_1 such that k∈ℳRX^k _R, for all k≥K2k≥ K_2. Proof 5.3. By Theorem 3.3, we have k→⋆X^k and k→⋆S^k , with k∈∂R(k)S^k∈∂ R(X^k) for all k, which together with the outer semicontinuity of ∂R∂ R, yields ⋆∈∂R(⋆)S ∈∂ R(X ). Therefore, dist(∗,∂R(k))→0 dist(S^*,∂ R(X^k))→ 0. Moreover, under Assumption 1(i), each rir_i is subdifferentially continuous on its domain (e.g., [rockafellar2009variational, Ex. 13.30]); hence, R(k)→R(⋆)R(X^k)→ R(X ). By Assumption 3(i), R∈psfℳR(⋆)R∈ psf_M_R(X ), and by Assumption 3(i) we have ⋆∈ri(∂R(⋆))S ∈ ri(∂ R(X )). Therefore, we can apply [hare2004identifying, Thm. 5.3] to the tilt function ↦R()−⟨⋆,⟩X R(X)- ,X , and use k→⋆X^k , R(k)→R(⋆)R(X^k)→ R(X ), and dist(⋆,∂R(k))→0 dist(S ,∂ R(X^k))→ 0 to conclude that there exists K2≥K1K_2≥ K_1 such that k∈ℳRX^k _R, for all k≥K2k≥ K_2. Equipped with Theorem 5.2, we can now establish a linear rate. Due to space limitations, we present the argument for the case of affine manifold ℳRM_R. This setting already covers a broad range of structured nonsmooth functions of practical interest, including polyhedral gauges and piecewise linear models (e.g., ℓ1 _1, mixed ℓ1,2 _1,2 and ℓ∞ _∞ norms) 5.2 Affine manifold ℳRM_R Throughout this subsection, we assume that ℳRM_R in Assumption 3 is affine. Since ⋆∈ℳRX _R (Th. 5.2), we can write ℳR=⋆+ℳR(⋆)M_R=X +T_M_R(X ), where ℳR(⋆)T_M_R(X ) is a linear subspace of ℝdR^d. We set R:=ℳR(⋆)T_R:=T_M_R(X ) and R:=ℳR(⋆)=R⟂N_R:=N_M_R(X )=T _R; and we denote the corresponding row-wise orthogonal projections by PR(⋅)P_T_R(·) and PR(⋅)P_N_R(·), respectively. For ∈ℝm×dZ ^m× d, we write =()R+()RZ=(Z)_T_R+(Z)_N_R, with ()R:=PR()(Z)_T_R:=P_T_R(Z) and ()R:=PR()(Z)_N_R:=P_N_R(Z). The linear convergence analysis builds on the following refined descent inequality that follows the proof of Lemma 2.4 now exploiting the local strong convexity of F. Lemma 5.4. Under Assumption 3(i)-(i) there exists K1≥0K_1≥ 0 such that (47) ‖k+1−⋆‖2 \|X^k+1-X \|^2 +(αk)2(‖(k+1)R−(⋆)R‖2+‖(k+1)R−(⋆)R‖2+‖k+1−⋆‖M22) +(α^k)^2 (\|(S^k+1)_T_R-(S )_T_R\|^2+\|(S^k+1)_N_R-(S )_N_R\|^2+\|Y^k+1-Y \|_M^2^2 ) ≤‖k−⋆‖2 ≤\|X^k-X \|^2 +(αk)2(‖(k)R−(⋆)R‖2+‖(k)R−(⋆)R‖2+‖k−⋆‖M22) +(α^k)^2 (\|(S^k)_T_R-(S )_T_R\|^2+\|(S^k)_N_R-(S )_N_R\|^2+\|Y^k-Y \|_M^2^2 ) −(αk⋆k+(1−δ)‖k+1−k‖2+(αk)2‖k−k+1‖M22), - (α^k D^k_X +(1-δ)\|A^k+1-X^k\|^2+(α^k)^2\|Y^k-Y^k+1\|_M^2^2 ), for all k≥K1k≥ K_1, where ⋆k:=αkμ2‖k−⋆‖2+αk2Lf‖∇F(k)−∇F(⋆)‖2. D^k_X := α^kμ2\|X^k-X \|^2+ α^k2L_f\|∇ F(X^k)-∇ F(X )\|^2. Proof 5.5. Repeating the derivation of Lemma 2.4 while using the local μ-strong convexity of F around ⋆X (Assumption 3(i)), and the LfL_f-Lipschitz continuity of ∇F∇ F over ℋ H (Lemma 3.1), we infer that there exists K1≥0K_1≥ 0 such that, for all k≥K1k≥ K_1, (48) ⋆⋆k+1≤⋆⋆k−‖~k+1−~k‖2−(1−δ)‖k+1−k‖2−αk⋆k.V_ X S ^k+1 _ X S ^k-\| A^k+1- X^k\|^2-(1-δ)\|A^k+1-X^k\|^2-α^k D_X ^k. The inequality (5.4) follow from (48) using ~k+1=αkM(k−k+1) A^k+1=α^kM(Y^k-Y^k+1) (due to (16)) and ~k= X^k=0 (eq. (18)); and the orthogonal decomposition of the subgradient variables, i.e., ‖t−⋆‖2=‖(t)R−(⋆)R‖2+‖(k)R−(⋆)R‖2\|S^t-S \|^2=\|(S^t)_T_R-(S )_T_R\|^2+\|(S^k)_N_R-(S )_N_R\|^2, t=k,k+1t=k,k+1. We proceed controlling the subgradient errors ‖(t)R−(⋆)R‖2\|(S^t)_T_R-(S )_T_R\|^2 and ∥(k)R\|(S^k)_N_R −(⋆)R∥2-(S )_N_R\|^2 in (47) leveraging the partial smoothness of R (Assumption 3). Lemma 5.6. Assume Theorem 5.2 and that ℳRM_R therein is affine. Then, (a) Tangent component: There exist Lr≥0L_r≥ 0 and K3≥K2K_3≥ K_2 such that (49) ‖(k)R−(⋆)R‖≤Lr‖k−⋆‖,∀k≥K3;\|(S^k)_T_R-(S )_T_R\|≤ L_r\|X^k-X \|, ∀ k≥ K_3; (b) Normal component: For all k≥K2k≥ K_2, (50) ‖(k+1)R−(⋆)R‖≤‖∇F(k)−∇F(⋆)‖.\|(S^k+1)_N_R-(S )_N_R\|≤\|∇ F(X^k)-∇ F(X )\|. Proof 5.7. (a) Since R∈psfℳR∈ psf_M_R, the restriction R|ℳR|_M_R is 2C^2 around ⋆X . Hence, there exist an open neighborhood U of ⋆X and R^∈2() R ^2(U) such that R^()=R() R(X)=R(X), for all ∈ℳR∩X _R . Denoting ∇ℳR() _M_RR(X) the manifold gradient of R|ℳR|_M_R at X [boumal2023introduction, Def. 3.58]. Possibly shrinking U (still denoted by U), the following holds: (∂R())R=(a)∇ℳR()=(b)(∇R^())R(∂ R(X))_T_R (a)=\ _M_RR(X)\ (b)= (∇ R(X) )_T_R for all ∈ℳR∩X _R , where (a) and (b) follow from [liang2017activity, Fact 3.3] and [boumal2023introduction, Prop. 3.61], respectively. Since k→⋆X^k (Theorem 3.3) and k∈ℳRX^k _R for all k≥K2k≥ K_2 (Theorem 5.2), there exists K3≥K2K_3≥ K_2 such that k∈ℳR∩X^k _R , for all k≥K3k≥ K_3. Thus, taking k∈∂R(k)S^k∈∂ R(X^k) and ⋆∈∂R(⋆)S ∈∂ R(X ), yields (k)R−(⋆)R=(∇R^(k))R−(∇R^(⋆))R(S^k)_T_R-(S )_T_R= (∇ R(X^k) )_T_R- (∇ R(X ) )_T_R, for all k≥K3k≥ K_3; which together with the non-expansiveness of PRP_T_R and smoothness of ∇R^∇ R on U (due to R^∈2() R ^2(U)), proves (49). (b) Fix k≥K2k≥ K_2. By Theorem 5.2, k∈ℳRX^k _R, hence k−⋆∈RX^k-X _R and therefore (k)R=(⋆)R(X^k)_N_R=(X )_N_R (recall that RN_R is a linear subspace). Noting the commuting property of row-wise projections with left multiplication, (A)R=A()R(AZ)_N_R=A\,(Z)_N_R for all ∈ℝm×dZ ^m× d, we have W(⋆)R=(W⋆)R=(⋆)RW(X )_N_R=(WX )_N_R=(X )_N_R, where the last equality follows from ⋆=(x⋆)⊤X =1(x ) and W1=1W1=1; hence R⋆X _N_R is also consensual. By Step (S.1) of Algorithm 1 and the above relations, we have (k+1/2)R=(Wk)R=W(k)R=W(⋆)R=(⋆)R.(X^k+1/2)_N_R=(WX^k)_N_R=W(X^k)_N_R=W(X )_N_R=(X )_N_R. Combining with (k+1)R=(⋆)R(X^k+1)_N_R=(X )_N_R gives (51) (k+1/2−k+1)R=0and(k−k+1/2)R=0.(X^k+1/2-X^k+1)_N_R=0 (X^k-X^k+1/2)_N_R=0. From (24a)–(24c), k+1=k+1αk(k+1/2−k+1)−k+1/2.S^k+1=S^k+ 1α^k (X^k+1/2-X^k+1 )-D^k+1/2. -2.84544pt Taking the RN_R-component and using (51) yields (52) (k+1)R=(k)R−(k+1/2)R.(S^k+1)_N_R=(S^k)_N_R-(D^k+1/2)_N_R. Denote ∇k:=∇F(k)∇^k:=∇ F(X^k). By Step (S.1), k+1/2=W(∇k+k+k)D^k+1/2=W(∇^k+S^k+D^k); therefore (53) (k+1/2)R=W((∇k)R+(k)R+(k)R).(D^k+1/2)_N_R=W ((∇^k)_N_R+(S^k)_N_R+(D^k)_N_R ). Substituting (53) into (52) yields (54) (k+1)R=(k)R−W((k)R+(k)R+(∇k)R).(S^k+1)_N_R=(S^k)_N_R-W ((D^k)_N_R+(S^k)_N_R+(∇^k)_N_R ). We now turn (54) into a bound involving only the gradient differences (∇k)R−(∇k−1)R(∇^k)_N_R-(∇^k-1)_N_R. To do so, we eliminate the term (k)R(D^k)_N_R. From (24d) and (51), (k+1)R=(k+1/2)R−(∇k)R−(k)R(D^k+1)_N_R=(D^k+1/2)_N_R-(∇^k)_N_R-(S^k)_N_R. Substituting (53) into this expression yields (55) (k+1)R=W((k)R+(k)R+(∇k)R)−(k)R−(∇k)R.(D^k+1)_N_R=W ((D^k)_N_R+(S^k)_N_R+(∇^k)_N_R )-(S^k)_N_R-(∇^k)_N_R. Adding (54) and (55) cancels the W(⋅)W(·) terms and gives the explicit relation (k+1)R(S^k+1)_N_R +(k+1)R=−(∇k)R+(D^k+1)_N_R=-\,(∇^k)_N_R, which substituted in (54) yields (56) (k+1)R−(k)R=−W((∇)Rk−(∇k−1)R),∀k≥K2+1.(S^k+1)_N_R-(S^k)_N_R=-W ((∇)^k_N_R-(∇^k-1)_N_R ), ∀ k≥ K_2+1. -2.84544pt Fix k≥K2k≥ K_2 and let N≥k+1N≥ k+1. Summing (56) over t=k+1,k+2,…,Nt=k+1,k+2,…,N yields (N+1)R−(k+1)R=−W((∇N)R−(∇k)R),k≥K2andN≥k+1.(S^N+1)_N_R-(S^k+1)_N_R=-\,W ((∇^N)_N_R-(∇^k)_N_R ), k≥ K_2\,\,and\,\,N≥ k+1. -2.84544pt Letting N→∞N→∞ and using RN+1→R⋆S^N+1_N_R _N_R and (∇N)R→(∇F(⋆))R(∇^N)_N_R→(∇ F(X ))_N_R, we obtain (57) (k+1)R−(⋆)R=W((∇F(⋆))R−(∇F(k))R),∀k≥K2.(S^k+1)_N_R-(S )_N_R=W ((∇ F(X ))_N_R-(∇ F(X^k))_N_R ), ∀ k≥ K_2. The inequality (50) follows readily from (57) using ‖W‖2≤1\|W\|_2≤ 1 and the nonexpansiveness of the orthogonal projector. We proceed now proving linear convergence. Let K3K_3 be as in Lemma 5.6. For k≥K3k≥ K_3, define the Lyapunov function (58) affk+1:= ^k+1_ aff= ‖k+1−⋆‖2+(αk)2‖(k+1)R−(⋆)R‖2 \|X^k+1-X \|^2+(α^k)^2\|(S^k+1)_T_R-(S )_T_R\|^2 +(1+14αkLf)(αk)2‖(k+1)R−(⋆)R‖2+(αk)2‖k+1−⋆‖M22. + (1+ 14α^kL_f )(α^k)^2\|(S^k+1)_N_R-(S )_N_R\|^2+(α^k)^2\|Y^k+1-Y \|_M^2^2. Moreover, denote (59) γk:=(αk)2(αk−1)2,k≥0,γ^k:= (α^k)^2(α^k-1)^2, k≥ 0, -5.69046pt and define, for k≥K3k≥ K_3, (60) ρaffk:=max1αk‖k−⋆‖,‖∇F(k)−∇F(⋆)‖,‖k+1−k‖M2‖k−⋆‖M2,k≠⋆;+∞,k=⋆.\!\!\! _ aff^k:=\! cases \ 1α^k\|X^k-X \|,\;\|∇ F(X^k)-∇ F(X )\|,\;\|Y^k+1-Y^k\|_M^2 \\|Y^k-Y \|_M^2,&\!\!Y^k ;\\[8.99994pt] +∞,&\!\!Y^k=Y . cases Using Lemma 5.6 in (47), we obtain the following descent result for affkV^k_ aff. Proposition 5.8. Assume the setting of Lemma 5.4 & Lemma 5.6, and that ℳRM_R is affine. Then, holds that affk+1≤ϑkaffk,V^k+1_ aff≤ ^k\,\,V^k_ aff, for all k≥K3k≥ K_3, where ϑk:= ^k:= max1−αkμ8,γk(1−αkμ8Lr2(αk−1)2),γk1+14αk−1Lf, \1- α^kμ8,\;γ^k (1- α^kμ8L_r^2(α^k-1)^2 ),\; γ^k1+ 14α^k-1L_f,\; (61) 1−(ρaffk)2minαkμ4,14αkLf, 1. 1-( _ aff^k)^2 \ α^kμ4,\; 14α^kL_f,\;1 \ \. The above result ensures a sufficient decrease of affkV^k_ aff when ρaffk _ aff^k is not too small. The next lemma shows that if ρaffk _ aff^k is small, then ρaffk+1 _ aff^k+1 must be large enough. Lemma 5.9. Assume the setting of Proposition 5.8. (a) If ρaffk<1 _ aff^k<1 and k≥K3k≥ K_3, then (62) ρaffk+1≥1γk+1⋅11+αkLr(c(1−λ2(W~))−3ρaffk(1−ρaffk)); _ aff^k+1≥ 1 γ^k+1· 11+α^kL_r ( c(1- _2( W))- 3 _ aff^k(1- _ aff^k) ); (b) For every k≥K3k≥ K_3, (63) maxρaffk,ρaffk+1≥ρ¯affk:=c(1−λ2(W~))(1+αkLr)γk+1+c(1−λ2(W~)). \ _ af^k, _ af^k+1\≥\ ρ^k_ af:= c(1- _2( W))(1+α^kL_r) γ^k+1+ c(1- _2( W)). Proof. We begin proving (62). Using the updates of Algorithm 1, (64) k+1=k−αk(k+1+k+1+∇F(k)).X^k+1=X^k-α^k(S^k+1+D^k+1+∇ F(X^k)). By Theorem 3.3 and αk≥α¯>0α^k≥ α>0, it follows ⋆+⋆+∇F(⋆)=0S +D +∇ F(X )=0. Subtracting ⋆X on the LHS and αk(⋆+⋆+∇F(⋆))=0α^k(S +D +∇ F(X ))=0 on the RHS, we obtain: for k≥K3k≥ K_3, (65) 1αk‖k+1−∗‖ 1α^k\|X^k+1-X^*\| =‖(k+1−⋆)−[1αk(k−∗)−(k+1−⋆)−(∇F(k)−∇F(∗))]‖ = \|(D^k+1-D )- [ 1α^k(X^k-X^*)-(S^k+1-S )-(∇ F(X^k)-∇ F(X^*)) ] \| ≥‖Ł(k+1−∗)‖−2‖∇F(k)−∇F(∗)‖−1αk‖k−∗‖−Lr‖k+1−∗‖, ≥\| (Y^k+1-Y^*)\|-2\|∇ F(X^k)-∇ F(X^*)\|- 1α^k\|X^k-X^*\|-L_r\|X^k+1-X^*\|, where the inequality follows from decomposing k+1−⋆S^k+1-S into R/RT_R/N_R components and applying Lemma 5.6 to bound ‖(k+1)R−(⋆)R‖\|(S^k+1)_T_R-(S )_T_R\| and ∥(k+1)R−⋆)R∥\|(S^k+1)_N_R-S )_N_R\|. Next, in (65), we use the lower bound ‖Ł(k+1−⋆)‖≥c(1−λ2(W~))∥k+1\| (Y^k+1-Y )\|≥ c(1- _2( W))\,\|Y^k+1 −⋆∥-Y \| (note that ≠k+1−⋆∈span(Ł)0 ^k+1-Y ∈ span( )) and the definition of ρaffk _ aff^k (eq. (60)); rearranging terms we obtain: for k≥K3k≥ K_3, (66) 1αk‖k+1−∗‖≥11+αkLr(c(1−λ2(W~))‖k+1−∗‖−3ρaffk‖k−∗‖M2). 1α^k\|X^k+1-X^*\|≥ 11+α^kL_r ( c(1- _2( W))\|Y^k+1-Y^*\|-3 _ aff^k\|Y^k-Y^*\|_M^2 ). Moreover, still by (60) and M2=WM^2=W, we have (67) ‖k+1−∗‖≥‖k−∗‖M2−‖k+1−k‖M2≥(1−ρaffk)‖k−∗‖M2.\|Y^k+1-Y^*\|≥\|Y^k-Y^*\|_M^2-\|Y^k+1-Y^k\|_M^2≥(1- _ aff^k)\|Y^k-Y^*\|_M^2. Using (66), (67), and ρaffk<1 _ aff^k<1, we finally obtain: for k≥K3k≥ K_3, ρaffk+1≥αkαk+11αk‖k+1−∗‖k+1−∗‖≥1/γk+11+αkLr(c(1−λ2(W~))−3ρaffk(1−ρaffk)). _ aff^k+1≥ α^kα^k+1 1α^k \|X^k+1-X^*\|\|Y^k+1-Y^*\|≥ 1/ γ^k+11+α^kL_r ( c(1- _2( W))- 3 _ aff^k(1- _ aff^k) ). This proves (62). We prove now (63). First consider the case ρaffk≥1 _ aff^k≥ 1. Since ρ¯affk<1 ρ_ aff^k<1, we have maxρaffk,ρaffk+1≥ 1≥ρ¯affk. \ _ aff^k, _ aff^k+1\\ ≥\ 1\ ≥\ ρ_ aff^k. Now consider the case ρaffk<1 _ aff^k<1. Set x:=ρaffk∈[0,1)x:= _ aff^k∈[0,1), and define a:=c(1−λ2(W~))(1+αkLr)γk+1,b:=3(1+αkLr)γk+1.a:= c(1- _2( W))(1+α^kL_r) γ^k+1, b:= 3(1+α^kL_r) γ^k+1. Then (62) reads ρaffk+1≥a−bx1−x;andmaxρaffk,ρaffk+1≥maxx,a−bx1−x. _ aff^k+1\ ≥\ a-b\, x1-x; \ _ aff^k, _ aff^k+1\\ ≥\ \x,\;a-b\, x1-x \. It is not difficult to prove maxx,a−bx1−x≥a+b+1,∀x∈[0,1). \x,\;a-b\, x1-x \\ ≥\ aa+b+1, ∀ x∈[0,1). Substituting a and b in the lower bound yields (63). □ Using Lemma 5.9 in Proposition 5.8, leads to the following contraction property of affk+2 V^k+2_ aff every two consecutive iterations. Theorem 5.10 (Linear convergence). Let k,k,k\X^k,S^k,Y^k\ be generated by Algorithm 1 in the setting of Theorem 3.3, k→⋆=(x⋆)⊤X^k =1(x ) . Further assume Assumption 3 at ⋆X , with ℳRM_R affine. Then (68) affk+2≤maxγkγk+1,1⋅(1−rk)⋅affk,∀k≥K3, V^k+2_ aff≤ \γ^kγ^k+1,1\·(1-r^k)· V^k_ aff, ∀ k≥ K_3, where K3≥1K_3≥ 1 is such that Lemma 5.6 holds for all k≥K3k≥ K_3, and rk:=minαkμ8,αkμ8Lr2(αk−1)2,11+4αk−1Lf,(ρ¯affk)2⋅minαkμ4,14αkLf,1.r^k:= \ α^kμ8, α^kμ8L_r^2(α^k-1)^2, 11+4α^k-1L_f,( ρ^k_ af)^2· \ α^kμ4, 14α^kL_f,1 \ \. Furthermore, there exists an index K4≥K3K_4≥ K_3 such that (69) raff:=supk≥K4(maxγkγk+1, 1⋅(1−rk))∈(0,1),r_ aff:= _k≥ K_4 ( \γ^kγ^k+1,\,1\·(1-r^k) )\;∈\;(0,1), and consequently (70) affk≤raff⌊(k−K4)/2⌋affK4,∀k≥K4.V_ aff^k\;≤\;r_ aff (k-K_4)/2 \,V_ aff^K_4, ∀ k≥ K_4. Therefore ‖k−⋆‖→0\|X^k-X \|→ 0 R-linearly. Proof 5.11. The inequality (68) follow readily applying twice affk+1≤ϑkaffkV^k+1_ aff≤ ^k\,\,V^k_ aff (Proposition 5.8)–yielding affk+2≤ϑk+1ϑkaffkV^k+2_ aff\ ≤\ ^k+1 ^k\,V^k_ aff– factoring out maxγkγk+1, \γ^kγ^k+1, 11\ from ϑk+1ϑk ^k+1 ^k, and finally using the lower bound (63) (Lemma 5.9). We are left to prove that raff∈(0,1)r_ aff∈(0,1). (i) Using 0<α¯≤αk≤α¯0< α≤α^k≤ α and γk=(αk)2(αk−1)2≤α¯2α¯2<+∞γ^k= (α^k)^2(α^k-1)^2≤ α^2 α^2<+∞ for all k, we deduce rk≥r¯>0r^k≥ r>0 for all k≥K3k≥ K_3 and some r¯ r (each term in the minimum defining rkr^k is bounded below by a strictly positive constant). (i) Furthermore, since αk→α∞>0α^k→α^∞>0, we have γk→(α∞)2(α∞)2=1γ^k→ (α^∞)^2(α^∞)^2=1, implying maxγkγk+1,1→1. \γ^kγ^k+1,1\→ 1. Pick any ε∈(0,r¯/(2(1−r¯))) ∈ (0, r/(2(1- r)) ). By the above limit, there exists K4≥K3K_4≥ K_3 such that, for all k≥K4k≥ K_4, maxγkγk+1,1≤ 1+ε. \γ^kγ^k+1,1\\ ≤\ 1+ . Combining (i) and (i), we deduce raffk=maxγkγk+1,1(1−rk)≤(1+ε)(1−r¯)< 1−r¯2=:raff∈(0,1).r_ aff^k= \γ^kγ^k+1,1\(1-r^k)\ ≤\ (1+ )(1- r)\ <\ 1- r2=:r_ aff\ ∈(0,1). This proves (69). From Theorem 5.10 and following the same line of proof as in [kuruzov2024achieving, Lemma 12] we can finally obtain the following complexity for an ε solution. Corollary 5.12. Assume the setting of Theorem 5.10; and let Let κf:=Lf/μ _f:=L_f/μ and κr:=Lr/μ _r:=L_r/μ, Then ‖k−⋆‖≤ε\|X^k-X \|≤ , for all k≥Nεk≥ N_ , with (71) Nε=(κf(1+κr2)1−λ2(W~)log(1ε)).N_ =O ( _f(1+ _r^2)1- _2( W) ( 1 ) ). Corollary 5.12 shows that the proposed algorithms enter a linear convergence regime after the finite-time manifold identification in Theorem 5.2. In (71), the network dependence is standard via the inverse spectral gap, while partial smoothness affects the rate only through (1+κr2)(1+ _r^2), where κr=Lr/μ _r=L_r/μ and LrL_r comes from the tangent subgradient control in Lemma 5.6(a). Thus, the complexity matches existing non-adaptive methods up to constants, with an extra factor capturing the local variability of R along the active manifold. This factor vanishes for polyhedral penalties (e.g., ri(x)=λi‖x‖1r_i(x)= _i\|x\|_1), for which Lr=0L_r=0 (hence κr=0 _r=0) after identification. In this regime, DATOS recovers exactly the same asymptotic iteration complexity as the aforementioned non-adaptive baselines, while retaining the benefit of an adaptive stepsize selection prior to (and after) identification. 6 Numerical Results This section reports numerical experiments comparing Algorithms 1 (global_DATOS) and 3 (local_DATOS) with representative decentralized baselines. As nonadaptive benchmarks, we consider SONATA [sun2019distributed] and PG-EXTRA [shi2015proximal], both relying on constant stepsizes that depend on (global) problem and network parameters. For these methods, we perform a manual grid-search over admissible stepsizes and report the best-performing choice yielding stable and fast convergence. We further include decentralized implementation of the adaptive centralized method adaPDM [Latafat_23b]. We stress that adaPDM is not designed to be decentralized; when implemented in decentralized settings, it is not fully parameter-free, as it requires the knowledge at the agents’ side of the global network-related quantity ‖I−W‖\|I-W\|. To illustrate the effect of such knowledge, we simulate two variants: (i) adaPDM–assuming access to ‖I−W‖(≤2)\|I-W\|(≤ 2); and (i) adaPDM2–using the conservative network-agnostic upper bound 22 for ‖I−W‖2\|I-W\|2. In both cases, we manually tune the parameter t (as appears in [Latafat_23b]) to obtain the best observed convergence behavior. We anticipate that both adaPDM and adaPDM2 are very sensitive to the choice of t. We generate Erdős–Rényi graphs with m=20m=20 agents and edge probability p∈0.1,0.5,0.9p∈\0.1,0.5,0.9\, spanning poorly to well connected regimes. All methods employ Metropolis-Hastings gossip weights (see, e.g., [Nedic_Olshevsky_Rabbat2018]). For Algorithms 1 and 3, we initialize 0X^0 and 0S^0 randomly and set α−1=10α^-1=10, δ=0.9δ=0.9, and c=1/3c=1/3. 6.1 Logistic regression with ℓ1 _1-regularization Consider the decentralized logistic regression problem with ℓ1 _1-regularization, which is an instance of (P), with fi(x)=1n∑j=1nlog(1+exp(−bij⋅⟨x,aij⟩)),r(x)=λ‖x‖1,f_i(x)= 1n _j=1^n (1+ (-b_ij· x,a_ij )), r(x)=λ\|x\|_1, -5.69046pt where aij∈ℝda_ij ^d and bij∈−1,1b_ij∈\-1,1\. The data set (aij,bij)j=1n\(a_ij,b_ij)\_j=1^n is owned by agent i. We use the MNIST dataset from LIBSVM [chih2libsvm], taking the first N=6000N=6000 samples (hence n=300n=300). The feature dimension is d=784d=784. We set λ=10−5λ=10^-5. Figure 1 plots the optimality gap (1/m)∑i=1mu(xiν)−u∗(1/m) _i=1^mu(x_i^ν)-u^* achieved by all the algorithms versus the number of iterations ν, where u∗u^* is the minimum value of u. Both global_DATOS and local_DATOS consistently outperform SONATA and PG-EXTRA, while requiring no manual stepsize tuning. Moreover, they improve markedly over adaPDM in both variants (adaPDM and adaPDM2). Finally, the performance gap between local_DATOS (local min-consensus) and global_DATOS (global min-consensus) is negligible, particularly on well connected graphs. Figure 1: Logistic regression with ℓ1 _1-regularization: 1m∑i=1mu(xi)−u(x∗) 1m _i=1^mu(x_i)-u(x^*) v.s. # iterations. Comparison of PG-EXTRA, SONATA, adaPDM, adaPDM2, global_DATOS and local_DATOS on Erdos-Renyi graphs with edge-probability p=0.1p=0.1 (left); p=0.5p=0.5 (middle); and p=0.9p=0.9 (right). 6.2 Maximum Likelihood (ML) estimate of the covariance matrix We consider decentralized estimation of an inverse covariance matrix, an instance of (P) with variable X∈++dX ^d_++ and fi(X)=−n(log(det(X)))−trace(XYi),r(X)=δC(X),f_i(X)=-n( ( det(X)))- trace(XY_i), r(X)= _C(X), where C=X∈++d:aI⪯X⪯bIC=\X ^d_++:aI X bI\, for some 0<a≤b0<a≤ b, and Yi=1n∑j=1nyji(yji)⊤Y_i= 1n _j=1^ny_j^i(y_j^i) for yji\y_j^i\ sampled from a Gaussian distribution with covariance matrix Σ∈++d ^d_++. We set n=100n=100 and d=5d=5. This is a representative case where f is only locally smooth; consequently, SONATA and PG-EXTRA do not come with global convergence guarantees, and stable behavior requires conservative stepsize choices. We again tune their stepsizes for best stable performance. Figure 2 reports u¯k−u⋆ u^k-u versus the iteration counter, where u⋆u is computed via a centralized proximal-gradient method with line-search up to tolerance 10−3010^-30. The plots show that global_DATOS and local_DATOS consistently outperform SONATA and PG-EXTRA–which require conservative stepsize selections to ensure stable global convergence–including both adaPDM variants. We also note that, in this experiment, the iterates generated by local_DATOS (and global_DATOS) remain bounded due to the compact constraint set enforced by r(X)=δC(X)r(X)= _C(X). Therefore, the boundedness /local-smoothness hypotheses required by Theorem 4.6 are automatically satisfied. Figure 2: ML estimate of the covariance matrix: 1m∑i=1mu(xi)−u(x∗) 1m _i=1^mu(x_i)-u(x^*) v.s. # iterations. Comparison of PG-EXTRA, SONATA, adaPDM, adaPDM2, global_DATOS and local_DATOS on Erdos-Renyi graphs with edge-probability: p=0.1p=0.1 (left); p=0.5p=0.5 (middle); and p=0.9p=0.9 (right). 6.3 Linear regression with elastic net regularization We finally consider a strongly convex composite instance of (P), namely ℓ2 _2-regularized least squares with an ℓ1 _1 penalty: (72) fi(x)=1n‖Aix−bi‖2+γi2‖x‖2,r(x)=λ‖x‖1,f_i(x)= 1n\|A_ix-b_i\|^2+ _i2\|x\|^2, r(x)=λ\|x\|_1, -2.84544pt where (Ai,bi)∈ℝn×d×ℝn(A_i,b_i) ^n× d×R^n is agent i’s local dataset. The entries of AiA_i and bib_i are sampled i.i.d. from the standard normal distribution. We set n=20n=20 (hence N=400N=400), d=500d=500, λ=10−5λ=10^-5, and γi=0.1+(i−1)×0.1 _i=0.1+(i-1)× 0.1, which yields heterogeneous local smoothness constants and a condition number of f equal to κ≈82.62κ≈ 82.62. Figure 3: Linear regression with elastic net regularization: ‖k−∗‖2\|X^k-X^*\|^2 v.s. # iterations. Comparison of PG-EXTRA, SONATA, adaPDM, adaPDM2, global_DATOS and local_DATOS on Erdos-Renyi graphs with edge-probability: p=0.1p=0.1 (left); p=0.5p=0.5 (middle); and p=0.9p=0.9 (right). Figure 3 reports the error ‖k−⋆‖2\|X^k-X \|^2 versus the iteration counter. Consistent with the previous experiments, global_DATOS and local_DATOS improve substantially over the nonadaptive benchmarks, with the largest gains on sparse graphs. The observed slopes corroborate the linear convergence behavior predicted by our analysis. References