Local Composite Saddle Point Optimization
Authors: Site Bai
Brian Bullins
Venue: ICLR 2024 poster (2024)
Keywords: Saddle Point Optimization
Distributed Optimization
Federated Optimization
Composite Optimization
Dual Extrapolation
Mirror Prox
Convex Optimization
Bregman Divergence
Primary area: optimization
TL;DR: We propose Federated Dual Extrapolation (FeDualEx), an extra-step primal-dual algorithm with local updates that encompasses both saddle point optimization and composite objectives under the distributed paradigm.

Abstract: Distributed optimization (DO) approaches for saddle point problems (SPP) have recently gained in popularity due to the critical role they play in machine learning (ML). Existing works mostly target smooth unconstrained objectives in Euclidean space, whereas ML problems often involve constraints or non-smooth regularization, which results in a need for composite optimization. Moreover, although non-smooth regularization often serves to induce structure (e.g., sparsity), standard aggregation schemes in distributed optimization break this structure. Addressing these issues, we propose Federated Dual Extrapolation (FeDualEx), an extra-step primal-dual algorithm with local updates, which is the first of its kind to encompass both saddle point optimization and composite objectives under the distributed paradigm. Using a generalized notion of Bregman divergence, we analyze its convergence and communication complexity in the homogeneous setting. Furthermore, the empirical evaluation demonstrates the effectiveness of FeDualEx for inducing structure in these challenging settings.

Published as a conference paper at ICLR 2024
LOCAL COMPOSITE SADDLE POINT OPTIMIZATION
Site Bai
Brian Bullins
Department of Computer Science
Department of Computer Science
Purdue University
Purdue University
bai123@purdue.edu
bbul 1 lins@purduee...... edu
ABSTRACT
Distributed optimization (DO) approaches for saddle point problems (SPP) have recently gained in popularity due to the critical role they play in machine learning (ML). Existing works mostly target smooth unconstrained objectives in Euclidean space, whereas MI. problems often involve constraints or non-smooth regular- ization, which results in a need for composite optimization. Moreover, although non-smooth regularization often serves to induce structure (e.g.. sparsity), standard aggregation schemes in distributed optimization break this structure. Addressing these issues, we propose Federated Dual Extrapolation (FeDualEx), an extra-step primal-dual algorithm with local updates, which the first of its kind to encompass both saddle point optimization and composite objectives under the distributed paradigm. Using a generalized notion of Bregman divergence, we analyze its con- vergence and communication complexity in the homogencous setting. Furthermore, the empirical evaluation demonstrates the effectiveness of FeDualEx for inducing structure in these challenging settings.
INTRODUCTION
notable fraction of machine learning (ML) problems belong to saddle point problems (SPP), including adversarial robustness (Madry et al., 2018; Chen & Hsieh, 2023), generative adversarial networks (GAN) (Goodfellow et al., 2014), matrix games (Abernethy et al., 2018), multi-agent reinforcement learning (Wai et al., 2018), among others. These applications call for effective distributed saddle point optimization as their scale evolves beyond centralized learning. In typical distributed optimization (DO) approaches, a central server coordinates collaborative learning among clients through rounds communication. In each round, clients learn a synchronized global model locally without sharing their private data, then send the model to the server for aggregation, usually through averaging (McMahan et al., 2017; Stich, 2019), to produce a new global model. The cost of communication is known to dominate the optimization process (Konečný al., 2016).
Although preliminary progress has been made in distributed saddle point optimization (Beznosikoy al., 2020; Hou et al., 2021), would note that machine learning problems commonly associated with task-specific constraints or non-smooth regularization, which results in a need for composite optimization (CO). Moreover, common purpose for non-smooth regularization is to induce structure. Typical ones include & norm for sparsity and nuclear norm for low- www-rankeess which show up in examples spanning from classical LASSO (Tibshirani, 1996), sparse regression (Hastie al., 2015) to deep learning such as adversarial example generation (Moosavi-Dezzoolli et al., 2016), sparse GAN (Zhou et al., 2020), convexified learning (Sahiner et al., 2022; Bai et al., 2024) and others.
Meanwhile, Yuan et al. (2021) identified the "curse of primal averaging" in standard aggregation structure on the client models may no
schemes of DO, where the specific regularization-imposs longer hold after direct averaging on the server. For instance, each client may be able to obtain a sparse solution, yet averaging the solutions across clients yields dense solution. To address this issue for convex optimization, they adopted the dual averaging technique (Nesterov, 2009), but this approach is not specifically designed for SPP. Even in the sequential deterministic setting, dual averaging or mirror descent (Nemirovskij & Yudin, 1983) achieve only a ((1VVT) rate for SPP (Bubeck et al., 2015), whereas extra-step methods achieve (1/TT) rate (Nemirovski, 2004; Nesterov, 2007). At the same time, existing distributed methods for SPP fail to cover these composite scenarios and address associated challenges, summarized in Table 1.

---

Published as a conference paper at ICLR 2024
Composite & Constrained & Non-Euclidean
Convexity Assumption
Task
Method
Convergence Rate
FedAvg
X
BR RK
e0t
(Khaled et al., 2020)
MERSKS
Já på KaRa
convex
Min
(Yuan et al., 2021)
AvdDua
92 AK
M2 ná x
+
nå
convex
FeDualEx
V
88
a at
o03
230888 sh R²
(Ours)
RX
ktRž
M7 R
convex
Extra Step Local SGD
X
B Bexp(- akR)
o +
g9,2 K"""
e-strongly
Min-Max
(Beznosikov et al., 2020)
MKR
convex-concave
SCCAFFOLD (Hou et al., 2021)
X
8º B Buxpl
o²
a-strongly convex-concave
MKR
R
FeDualEX (Ours)
38 a
oBa
a g
TK
K KER
R
convex-concave
Table 1: We list existing convergence rates on composite convex optimization and smooth saddle point optimization in distributed settings similar ours. Notations are Rt: communication rounds; K: local steps; 3: smoothness; B: diameter; G: gradient bound; M: clients; a²: gradient variance. FedAvg is also included as a reference. We further note that none of the work other than ours covers composite SPP. They are included only for completeness.
We present the distributed paradigm for composite saddle point optimization defined in (1). In particular, we propose Federated Dual Extrapolation (FeDualFxx (Algorithm 1), which builds on Nesterov's dual extrapolation (Nesterov, 2007), a classic extra-step algorithm suited for SPP. carries out a two-step evaluation of proximal operator (Censor & Zenios, 1992) defined by the Bregman Divergence (Bregman, 1967), which allows for SPP beyond the Euclidean space. To adapt to composite regularization, FeDuulEEx also draws inspiration from recent progress in composite convex optimization (Yuan et al., 2021) and adopts the notion of generalized Bregman divergence (Flammarion & Bach, 2017) instead, which merges the regularization into its distance-generatingg function. With some novel technical accommodations, we provide the convergence rate for FeDualEx under the homogeneous setting, which is, the best of our knowledge, the first convergence rate for composite saddle point optimization under the DO paradigm. In support of the proposed method, we conduct numerical evaluations verify the effecttivnness of FeDualEx on composite SPP.
To further demonstrate the quality of the induced structure, we include the primal twin of FeDualEx based on mirror prox (Nemirovski, 2004), namely "Federated Mirror Prox (FedMiP)", as a baseline for comparison in Appendix H. This is in line with the dichotomy between Federated Mirror Descent (FedMiD) and Federated Dual Averaging (FedDualAvg) (Yuan et al., 2021), from which Yuan et al. (2021) identified the "curse of primal averaging" in DO, i.e., the specific regularization-imppeed structure on the client models may no longer hold after primal averaging on the server. It highlights that FeDualEx naturally inherits the merit of dual aggregation from FedDualAvg. In addition, analyze FeDualEx for federated composite convex optimization and show that FeDualEx recovers the same convergence rate FedDualAvg under the convex setting.
Last but not least, by reducing the number of clients to one, we show for the sequential version of FeDualEx that the analysis naturally yields a convergence rate for stochastic composite saddle point optimization which, to our knowledge, is the first such algorithm for non-Euclidean settings and matches the O (T) rate in general stochastic saddle point optimization (Mishchenko al., 2020; Juditsky et al., 2011). Further removing the noise from gradient estimates, FeDualEx still generalizes dual extrapolation to deterministic composite saddle point optimization with a O(F) convergence rate that matches the smooth case and also the pioneering composite mirror prox (CoMP) (He et al., 2015) as presented in Table 2.
Our Contributions:
We propose FeDualEx for distributed learning of SPP with composite possibly non-smooth regularization (Section 4.1). In support of the proposed algorithm, we provide convergence rate for FeDualEx under the homogeneous setting (Section 4.2). To the best of our knowledge, FeDualEx is the first of its kind that encompasses composite possibly non-smooth regularization for SPP under a distributed paradigm, as shown in Table 1.
Additionally, we showcase the structure-preserty achieved through dual-space averaging. In particular, we present its primal twin FedMiP as a baseline to highlight this contrast (Appendix H).
(e.g., sparsity) advantage of FeDualEx
2

---

Published as a conference paper at ICLR 2024
Noise
Kate
Composite SPP
Smooth SPP
Mirror Prox (Nemirovski. 2004)
Deterministic
O (+)
CoMP (He 2015)
Dual Extrapolation (Nesterov, 2007)
Deterministic FeDualEX (Ours)
Accelerated Proximal Gradient (Tseng, 2008)
Extragradeiat (Euclidean) (Mishchenko et al.. 2020)
Mirror Prox Uuditsky et al., 2011)
Stochastic
O
Sequential FeDualEx (Ours)
Sequential FeDualEx (Ours)
Table 2: Convergence rates for convex-concave SPP. The deterministic version of FeDualEx general- izes dual extrapolation (DE) to composite SPP, and the sequential version of FeDualFxx generalizes DE to both smooth and composite stochastic saddle point optimization.
FeDualEx produces several byproducts in the CO realm, demonstrated in Table 2: (1) The sequential version of FeDualEX leads to the stochastic dual extrapolation for CO and yields, to our knowledge, the first convergence rate for the stochastic optimization of composite SPP in non-Euclidean settings (2) Further removing the noise leads to its deterministic version, with rates matching existing ones in smooth and composite saddle point optimization (Section 5).
We demonstrate experimentally the effectiveness of FeDualEXx on various composite saddle point tasks, including bilinear problems on synthetic data with & and nuclear norm regularization, as well as the universal adversarial training of logistic regression with MNIST and CIFAR-10 (Section 6).
RELATED WORK
We provide brief overview of some related work and defer extended discussions to Appendix B.
The distributed optimization paradigm we consider aligns with that in Local SGD (Stich, 2019),
which is also the homogeneous setting of Federated Averaging (FedAvg) (McMahan et al., 2017).
Stich (2019) provides the first convergence rate for FedAvg, and it has been improved with tighter analysis and also analyzed under heterogeneity (e.g., (Khaled et al., 2020; Woodworth al., 2020b)).
Recently, Yuan et al. (2021) extended FedAvg to composite convex optimization and proposed FedDualAvg that aggregates learned parameters in the dual space and overcomes the "curse of primal averaging" in federated composite optimization.
For SPP, Beznosikov al. (2020) investigate the distributed extra-gradient method for strongly- convex strongly-concave SPP in the Euclidean space. Hou et al. (2021) propose FedAvg-S and SCAFFOLD based on FedAvg (MeMahan al., 2017) and SCAFFOLD (Karimireddy al., 2020) for SPP, which yields similar convergence rate to (Beznosikov et al., 2020). In addition, Ramezani- Ramezani-Kebrya et al. (2023) study the problem from the information compression perspective with the measure of communication bits. Yet, the aforementioned works are limited to smooth and unconstrained SPP in the Euclidean space. The more general setting of composite SPP is only found in sequential optimization literature, where the representative composite mirror prox (CoMP) (He et al., 2015) generalizes the classic mirror prox (Nemirovski, 2004) yet keeps the ( convergence rate. In the stochastic setting, Mishchenko et al. (2020) amalyzed variant of stochastic mirror prox (Juditsky et al., 201 which is then capable of handling composite terms in the Euclidean space. We will later show that the sequential analysis of our proposed algorithm also yields the same rate for dual extrapolation (Nesterov, 2007) in composite optimization, utilizing different proving techniques. As result, we focus on the distributed optimization of composite SPP and propose FeDualEx.
PRELIMINARIES AND DEFINITIONS
We provide some preliminaries and definitions necessary for introducing FeDualExx More details are included Appendix C. To begin with, we lay out the notations.
Notations. We use [n] to represent the set 21, n... We use || || to denote an arbitrary norm, -| to denote the dual norm, and || ||2 to denote the Euclidean norm. We use V for gradients, for subgradients, and (---) for inner products. Related to the algorithm, we use English letters (e.g.. 2, xr y) to denote primal variables, Greek letters (e.g., w, S. μ., 1) to denote dual variables. We use R for communication rounds, K for local updates. B for diameter bound, G for gradient bound, for smoothness constant, a for standard deviation, for random samples. We use h² to denote the convex conjugate of function h.
3

---

Published as a conference paper at ICLR 2024
Composite Saddle Point Optimization. We study composite saddle point optimization. Its objective is formally given in the following definition.
Definition 1 (Composite SPP). The objective of composite saddle point optimization is defined as min max 6(x, v) = f(x, v) + +1(z)) <b2(y)
oEX wEY
where ((,,8) Em=i (2, v) and 4/ (2)), (1) are possibly non-smooth.
typically evaluated by the duality gap: Gap(ă, 0) = maxyey ((ē,)) y) - minzex p(x, Q)-
Mirror Prox and Dual Extrapolation. Mirror prox (Ne- mirovski, 2004) and dual extrapolation (Nesterov, 2007) are classic methods for convex-concave SPP. Both are proxi- mal algorithms based on the proximal operator defined as arg min, {(,22) V (z)), in which (x) h(z) - h(2') (Vh(2') x - x²) is the Bregman divergence generated by some closed, strongly convex, and differentiable function h. Both algorithms conduct two evaluations of the proximal operator, while dual extrapola- tion carries out updates in the dual space. Figure gives a brief illustration of dual extrapolation with the proximal operator as in (Cohen et al., 2021), with details in Appendix C.I.
21 Prox 2 (me)
1t+1/2 Prox l (ng(2:))
Me+1 = Pt + 179 112+)
Prox //
Figure 1: Dual Extrapolation.
Generalized Bregman Divergence. Recent advances in composite convex optimization (Yuan et al., 2021) have utilized the Generalized Bregman Divergence (Flammarion & Bach, 2017) for analyzing composite objectives. incorporates the composite term into the distance-generatie function of the vanilla Bregman divergence, and measures the distance in terms of one variable and the dual image of the other, with the key insight being the conjugate of a non-smooth generalized distance-genesn generating function is differentiable.
Definition (Generalized Bregman Divergence (Flammarion & Bach, 2017)). Generalized Bregman divergence is defined to be th (x)
(uVh))())((( "ju',x-VVi Vh)(h(())) where lúg = h++ Lmp generalized distance -ennnnccgnn function that is closed and strongly convex, t is the current number of iterations, 17 is the step size, h is the convex conjugate of h4, and p¹ is the dual image of x', i.e., μí' E Öh,(x') and x' (n)
Generalized Bregman divergence is suitable not only for non-smooth regularization but also for any convex constraints C, taking (xxx) = if x E C and too otherwise.
4 FEDERATED DUAL EXTRAPOLATION (FEDUALEX)
To tackle composite SPP in the DO paradigm, we acknowledge the challenges from several aspects. Specifically, the generality afforded by composite and/or saddle point problems results in need for more sophisticated techniques that work with this additional structure. These concerns are further complicated by the challenges that arise for DO, where communication and aggregation need be carefully handled under the distributed mechanism. In particular, Yuan et al. (2021) identified the "the curse of primal averaging" in composite federated optimization and advocated for dual aggregation. Dealing with these challenges altogether is rather non-trivial, as the techniques that are naturally suited for one would fail for another. In this regard, we first present FeDualEx (Algorithm and several relevant novel definitions proposed for its adaptation to composite SPP. Then we analyze the convergence rate in the homogeneous setting.
4.1 THE FEDUALEX ALGORITHM
FeDualEx builds its core on the classic dual extrapolation, an extra-step algorithm geared for saddle point optimization. Its effectiveness has been widely verified in vanilla smooth convex-concave SPP. Furthermore, its updating sequence lies in the dual space which would naturally inherit the advantage of dual aggregation in composite federated optimization. The challenge remains for composite optimization, as relevant work is limited, and the existing composite extension for the extra-step method (He et al., 2015) is quite technically involved. Given that the smooth analysis of dual extrapolation is already non-trivial (Nesterov, 2007), no attempts were previously made for generalizing dual extrapolation the composite optimization realm.
4

---

Published as a conference paper at ICLR 2024
Algorithm 1 TEDDERATDD-DUUA-AETT...OOO
(FeDualEx) for Composite SPP
(2 Input: (0z) - (zr v) th (a) (2(()) Em= Sm(a, +t) 1/2 (y): objective function;
M
{(=): distance-generating function; 9m (2)
(2: y)): gradient operator.
Hyperparameters: R: number of communication rounds; K: number of local update iterations; ry":
server step size; 77: client step size.
Dual Initialization: So = initial dual variable, ç: fixed point in the dual space.
Output: Approximate solution 2 = (z, to min maxzey Φ(x, y) do 2: Sample subset of clients C. S [M]
1: for 0, l.....
3: for m E C, in parallel do
4:
Sr.0 5,
5:
for 1 = 0, ........ - do
6:
Prox (sttk)
Two-step evaluation of the generalized proximal operator
knittl (17² 9m ( br,k))) 1/2 = Prox 5-
7:
8:
S,,+1 = S 17" gm (2 +,,+ 17/2)
Dual variable update
9:
end for
10: end parallel for
11:
A,
C, Emec. (S7, - m Sr,U) + D,
12: Sy+1
> Server dual update
end for
14:
Return: RK
1 EP= Z==0 2r,2+1/2 with 2r,4+1/2 defined in (4).
Inspired by recent advances in composite convex optimization, we recognize the Generalized Bregman Divergence (Flammarion & Bach, 2017) as a powerful tool for analyzing proximal methods for composite objectives. Adapting to the context of composite SPP, we make an extension to the Generalized Bregman Divergence for saddle functions, and provide the definition below.
Definition 3 (Generalized Bregman Divergence for Saddle Functions). The generalized distance- generating function for the optimization of (1) is (z(z) = E(2)+ tmpb(z), where {(z) = (x) + h2(u), hy and h2 are distance-generating generating functions for and y, xb(2) = (1(()) +/2 ) r the step size, and is the current number of iterations. It generates the following generalized Bregman divergence:
V Ce(z) tx(z)) - (s', z²), =2);,
where 5' is the preimage =f with respect to the gradient of the conjugate of lu i.e., x' Vet(s").
Yet as we notice in previous works (Flammarion & Bach, 2017: Yuan et al., 2021), generalized Bregman divergence is applied only for theoretical analysis. In terms of algorithm design, the previous proximal operator for composite convex optimization is based on the vanilla Bregman divergence plus the composite term, specifically, arg min, {(; x²) + (x) + <p)(2)) (Duchi et al., 2010; He et al., 2015), and arg min, ((, .²) hh(x) + ntv(z)} in (Xiao, 2010; Flammarion & Bach, 2017). However, we find this definition insufficient for dual extrapolation. as its dual update and the composite term from the extra step break certain parts of the analysis. In this effort, we propose novel technical change to the proximal operator, directly replacing the Bregman divergence in the proximal operator with the generalized Bregman divergence.
Definition 4 (Generalized Proximal Operator for Saddle Functions). A proximal operation in the composite setting with generalized Bregman divergence for Saddle Functions is defined to be
ft Prox o (g) = arg min (g, z) + V (x)).
where s' is the dual image of z', i.e., z' (s))s)), and 5' 001(22) = Vi(==) + ((0)((z)).
Compared with the vanilla proximal operator in Section 3, this novel design for the composite adaptation of dual extrapolation is quite natural. It is different from previous proximal operators, which after expanding take the form arg ming(( {(-- Vi(2'), 2) (x)) (Duchi al., 2010) or arg min, (1, 2) (z)) (Xiao, 2010), whereas ours is Prox
h è (+) = arg min <²,2) (())).
These adaptations are necessary for technical reasons, as our algorithm involves prox operators on both the clients and the server to induce structure in the aggregated solution, which would otherwise
5

---

Published as a conference paper at ICLR 2024
break the conventional analysis. (Specifically, using these previous notions yields extra composite terms in the analysis that do not cancel out but rather accumulate, thus hindering the convergence.)
With the novel definitions above. we are able to formally present FeDualEx in Algorithm 1. It follows the general structure of DO. For each client, the two-step evaluation of the generalized proximal operator and the final dual update dual extrapolation updates in Figure To align with our generalized proximal operator, we also move the primal initialization æ in the original dual extrapolation to the dual space as Ç. On the server, the dual variables from clients are aggregated first the dual space, then projected to the primal with a mechanism later defined in (4).
highlighted in green which resembles the classic
4.2 CONVERGENCE ANALYSIS OF FEDUALEX
In this section, we provide the convergence analysis of FeDualEx for the homogeneous DO of composite SPP. We further assume the full participation of clients in each round for simplicity, but this condition can be trivially removed by lengthy analysis. We start by showing the equivalence between primal-dual projection and the generalized proximal operator, and for the convenience of analysis, reformulating the updating sequences with another pair of auxiliary dual variables.
Projection Reformulation. Generalized proximal operators can be presented as projections, i.e., the gradient of the conjugate of the generalized distance-generating function in Appendix C.2. Thus, line 6 to 8 in Algorithm can be expanded by Definition 4, and rewrite as: (1) =r
7 1/2 Vé ( ((5 - s7tk) of 9m (27,,5 <7,k)): )); (3) 5,,41 5 + 1f 9m m & s1))ss (2)
1/// ( 571+1/2)) em
Further define auxiliary dual variable w = 5- Sy It satisfies immediately that 27, = V (w)))) in which G, is the conjugate of l, = = (rr*K + k)n And define w 1//11/2 to be the dual
image of the intermediate variable 2 2,,k+1/2 such that 2 2,,+1/22 Vli (w,x+1/22) Then get an equivalent updating sequence with the auxiliary dual variables.
11/+1//2 with 79m (27 S7,)),
W with
5m 5rx+1/2) 79m (2
Define their average across clients, Wr, H7 2 k Fr,k we can analyze the following averaged dual shadow sequences:
M
1 Em 9m 9m(22 (2 k (
Then
M7
Wr, Wr,k 77 Jr.k.
(2)
Wr Wy 1f 9r,
(3)
In the meantime, their shadow primal projections on the server are defined as k = V (wykk)
2,, = Vl, (
(4)
Next, we list the key assumptions. Detailed presentation and additional remarks that ease the understanding of proofs are also provided in Appendix C.3.
Assumptions For the composite saddle function Φ(I,8) = M its gradient operator is given by g (Vaf, v and g 3/ EM Im. We assume that
1 -M Sm( v) + (b(())) v2(()).
a. CCnvexity of f) Vm E [M], fmn y) is convex in x and concave in y.
b. (Convexity of 1b) thn (a:) is convex ar and vb2(u) is convex in y. [=fm(u.)) c. (Lipschitzness of g) (z) (Vyfi(( is 3-Lipschitz: (1.m(() 9m S 8112 - 2'1l
d.(Unbi (Unbiased Estimate and Bounded Variance) Vm E [M, for random sample gm (='
Eg (9m [ (2"),, and IEg (=""; 5"h) (Bounded Gradient) Vm [M], Il (=m".""))) smm)]== S G
50²
f. The distance- distance-generating finctiinn is Legendre function that is 1-strongly convex, i.e., Vz, 2', {(2') ((2) (Vl(z), 2) 211=²² -2l?
g. The optimization domain compact w.r.t. Bregman divergence, i.e., Vz, E Z, V+(()) < B.
We would note that Assumption e (bounded gradient) is standard assumption in classic distributed composite optimization (Duchi et al., 201 1), and is made in other DO analysis (Stich, 2019; Li et al., 2020b; Yu et al., 2019; Yuan et al., 2021).
Main Theorem. Under the aforementioned assumptions, we present the following theorem that provides the convergence rate of FeDualEx in terms of the duality gap.

---

Published as a conference paper at ICLR 2024
Theorem 1 (Main). Under assumptions, the duality gap evaluated with the ergodic sequence generated by the intermediate steps of FeDualEx in Algorithm 1 is bounded by
R-1K- 1-1
B RRK
50
E
Gap
2+++1/2)
+ 203
+ M
+ 2 Bnf KGBt.
RK
Choosing step size of min
B²
B
Bi
320'
20t
'2oRddx
1 RK
]
5 RK
5toBt M
E
Gap
2r,4+1/2
K. R
R
P=0 Km
To the best of our knowledge, this is the first convergence rate for federated composite saddle point optimization. The O( !x and O( VMRK terms roughly match previous DO algorithms, where the noise term decays with the number of clients M. . large enough, then the (11/R)) term takes domination in terms of communication complexity. The convergence analysis further validates the effectiveness of FeDualEx, which then advances distributed optimization to a broad class of composite saddle point problems. The complete proof of Theorem can be found in Appendix E.
On Composite Convex Optimization. We also analyze the convergence rate for FeDualEx under the federated composite convex optimization setting. As the following theorem shows, FeDualEx achieves the same (11/ /R²) in (Yuan al., 2021). The proof is provided in Appendix F.
Theorem 2. Under the convex counterparts of previous assumptions, choosing step size nf = B
Bd
B$
min 52 3' 20 2 s 333 }, the ergodic intermediate sequence gener- ated by FeDualEx for composite convex objectives satisfies
R-1 K-1
3BBB RK Kin
B
dloB3 M +
B R$
E
2r,41//2 - b(x)] s
RK
Even though this rate is not preserved in composite saddle point optimization, note that the optimization of SPP is much more general, and convexity itself is a stronger assumption. More specifically, the complicated setting, including the non-smooth term, the primal-dual projection, the extra-step saddle point optimization, etc., together limit the tools available for analysis.
Remark On Heterogeneity. Even for federated composite optimization (Yuan al., 2021), the heterogencous setting presents sigmificant hurdles. Specifically, the involvement of heterogeneity is limited quadratic functions, under which assumption the is gradient linear, and this simplifies the analysis. It further relies on the norm generated by its Hessian. For saddle functions, "quadraticity" (as well matrix-induced norm) is less well-defined, as the Jacobian of their gradient operator is not (symmetric) positive semidefinite in general. Such further advancements go beyond the scope of this paper. Thus, we regard Theorem as a significant start for federated learning of composite SPP.
FEDUALEX IN SEQUENTIAL SETTINGS
Stochastic Composite Saddle Point Optimization FeDualEx can be naturally reduced to sequen- tial stochastic optimization of composite SPP, which we term as Sequential FeDualEx or Stochastic Dual Extrapolation. By reducing the number of clients to one, thus eliminating the need for communi- cation, the convergence analysis follows through smoothly and yields O (T)) rate (denoting as T) expected for first-order stochastic algorithms. This is the first such rate in the non-Euclidean setting, matching the previous Euclidean rate (Mishchenko al., 2020) and non compoompo rate (Juditsky et al., 2011). Theorem 3 gives the result with proof in Appendix G.I.
Theorem 3. Under the sequential versions of previous assumptions. '2 Z. choosing step size 77 minf
1__ B3 x the ergodic intermediate sequence of stochastic dual extrapolation satisfies
32g' "
E Gap(# ET=1 21+1/2)] < 32 BB B + sto
T
7

---

Published as a conference paper at ICLR 2024
min max (Ax b,y) + X||x||| - A|ly|1 xEd yey
min max Tr - Y) + X/ XEX YEY
R A
x- -
|| 100 - D),
A A
A'= = -R | - D),
DER"
y- {R= y S D}.
B B
y { || S D).
Figure 2: The composite SPP with L regular- ization for sparsity (Jiang Mokhtari, 2022).
Figure 3: The composite SPP with nuclear norm low-
rank regularization.
Deferministic Composite Saddle Point Optimization Further removing the noise in gradient, FeDualEx reduces to a deterministic algorithm for composite SPP. Even so, we are still generalizing the classic dual extrapolation algorithm to CO, and thus term the algorithm Deterministic FeDualEx or Composite Dual Extrapelation. Following a similar analysis, we are able to get the (++) rate as in previous work for CO (He et al., 2015) well the smooth dual extrapolation (Nesterov, 2007). in Appendix G.2 which a much simpler one based on the recently
The proof for Theorem proposed Relative Lipschitzness (Cohen et al., 2021).
Theorem 4. Under the basic convexity assumption and B-Lipschitzness of g, Vz E Z and S #
composite dual extrapolation satisfies Gap(? ? Et= 2+4122 S
3B T
6 EXPERIMENTS
To complement our largely theoretical results, we verify in this section the effectiveness of FeDualEx
by numerical evaluation. Additional experiments and detailed settings are deferred to Appendix A.
We first test FeDualEEx on composite bilinear problems with synthetic data. The problems considered are demonstrated in Figure and 3, in which m 600, n 300, p = 20, A = 0.1, D 0.05. The corresponding composite terms are l regularization with & ball constraint and nuclear regularization with spectral constraint. The purpose of & regularization is to encourage sparsity and nuclear regularization to encourage solution with low rank.
Composite Bilinear SPP.
We compare FeDualEx against AvdDualAvg, FedMiD (Yuan et al., 2021), and FedMiP proposed in Algorithm 2 in Appendix H. We note that methods like Extra Step Local SGD (Beznosikov et al., 2020) and SCAFFOLD-S (Karimireddy et al., 2020) are not suited to problems with non- smooth terms, but we include of them for completeness, given that their rates similar. For such a comparison, one can only compute the sub- aab-gradient instead of the gradient (which does not everywhere exist). Projection needs be applied as well to account for the constraints.
FeDualEX
FedMiP
FedDualAvg
.....
FedMiD
1.0
10
Duality Gap
10
Sparsity
Sparsity
Duality
10a
0.8
0.8
0.6
10-1
10-1
0.6
4000
Communication on Rounds
Communication Rounds
Communication Rounds
Communication Rounds
(a) One Local Update (K-
(b) Ten Local Updates (K 10)
Figure 4: Duality gap and sparsity of the solution for E regularized SPP with loo constraint.
Dualty cap
10a
15
15
(a)
20
40
80
100
20
40
60
80
100
20
40
60
80
100
Communication Rounds
Comm uniccaionn Rounds
Communication Rounds
10
20
20
Dualty Enp
(b) K =
10
10-2
10
10
10
Communication Rounds
Communication Rounds
Commurication Rounds
Figure 5: Duality gap and rank of the solution to the nuclear norm regularized SPP.
8

---

Published as a conference paper at ICLR 2024
FeDualEX
Projected Gradient Descent Ascent
1.5
Accuracy
80
Lo56
1.0
70
0.5
10
15
10
15
Communication Rounds
Communication Rounds
(a) MNIST
2.2
Accuracy
30
20
2.0
10
20
40
20
40
Communication Rounds
Communication Rounds
(a) FeDualEX
(b) PGDA
(b) CIFAR-10
Figure 7: Attack generated from the trained logistic
Figure 6:
Universal adversarial training loss and validation accuracy of logistic regression on unattacked data.
regression on MNIST and CIFAR-10.
We evaluate the convergence in terms of the duality gap and also demonstrate the structure of the solution, i.e, sparsity or low-rankness. The duality gap of the problems of interest can be evaluated in elosed form, which derived in Appendix A. and A.2. The sparsity is measured by the ratio of non-zero entries to the parameter size, and we regard numbers less than 10-S as zeros. For DO, we simulate M 100 clients. For the gradient query of each client in each local update, we inject Gaussian noise from (00, d²), where a = 0.1. The evaluation is conducted for two different settings: (a) K local update (b) K 10 local updates. The results are demonstrated Figure and 5.
From the duality gap curves in Figure 4, we see that extra-step methods, i.e., FeDualEx and FedMiP converge to the order of 10-1 whereas FedDualAvg and FedMiD stay above 10 Thus, is evident that methods for composite convex optimization are no longer suited for composite saddle point optimization, and FeDualEXx provides the first effective solution addressing the challenge. From the sparsity of the solution, see that the dual methods demonstrate better adherence to regularization. Among the methods superior in saddle point optimization, FeDualEx reaches a sparsity of around 0.7 while FedMiP is around 0.95. This aligns with the previous analysis the advantage of dual aggregation and further validates the effectiveness of FeDualEx for solving composite SPP. In addition, methods for smooth unconstrained optimization like ExtraStepLocallG]] do not converge for SPP with composite non-smooth terms, nor does it impose any desired structure, e.g., sparsity. We observe similar advantages of FeDualEx in convergence and inducing low-rankness from Figure 5 as well.
Universal Adversarial Training of Logistic Regression. We also consider the task of universal adversarial training (Shafahi al., 2020) of logistic regression, i.c. the adversarial training against a universal adversarial perturbation (Moosavi-Dezfood) et al., 2017) targeted for all images in the dataset. In order to encourage the sparsity of the attack, we also impose an l regularization on the attack. The problem formulation is given in Appendix A.3. We compare FeDualEx against direct aggregation of projected gradient descent ascent (PGDA) proposed in (Shafahi al., 2020) Alg.
We evaluate convergence with training loss, which is by no means an exact reflection of the duality gap. Still, we observe in Figure that FeDualEx converges faster and delivers a hetter-hardened model with higher validation accuracy unattacked data. Meanwhile, the vanilla aggregation of PGDA solutions yields a dense attack whereas FeDualEx achieves much better sparsity, as visualized in Figure 7. Furthermore, we observe that the attack generated by distributed PGDA is not only dense but also smoothed out to small values close to zero, averaged by the number clients.
CONCLUSION AND FUTURE WORK
We advance distributed optimization to the broad class of composite SPP by proposing FeDualEx and providing, to our knowledge, the first convergence rate of its kind. We demonstrate the effectiveness of FeDualEx for inducing structures with empirical evaluation. We also show that the sequential version of FeDualEx provides solution composite stochastic saddle point optimization in the non- Euclidean setting. We recognize further study of the heterogeneous federated setting of composite saddle point optimization would be challenging direction for future work.

---

Published as a conference paper at ICLR 2024
REFERENCES
Jacob Abernethy, Kevin A. Lai, Kfir Y. Levy, and Jun-Kun Wang. Faster rates for convex-concet games. Sébastien Bubeck, Vianney Perchet, and Philippe Rigollet (eds.), Proceedings of the 31st Conference On Learning Theory, volume 75 of Proceedings of Machine Learning Research, pp. 1595-1625, PMLR, 06-09 Jul 2018. URL httph: http:::/ppooceeeeeeeeeeee/ /ptp:////cocceeess..c.oo. www.mmll.ll...... abernethy18a html.
Kimon Antonakopoulos, Veronica Belmega, and Panayotis Mertikopoulos. An adaptive mirror-pros method for variational inequalities with singular operators. Advances in Neural Information Processing Systems, 32, 2019.
K. J. Arrow, L. Hurwicz, and H. Uzawa. Studies in linear and non-linear programming. Stanford University Press, 1958.
Jean-François Aujol and Antonin Chambolle. Dual norms and image decomposition models. Interna- tional journal of computer vision, 63:85-104, 2005.
Necdet Serhat Aybat and Erfan Yazdandoost Hamedani. A primal-dual method for conic constrained distributed optimization problems. Advances in neural information processing systems, 29, 2016.
Site Bai, Chuyang Ke, and Jean Honorio. On the dual problem of convexified convolutional neural networks. Transactions on Machine Learning Research, 2024. ISSN 2835-8856. URL https:/ http::///ppeeeeeeeeeeeeeeeeeeeee net [orumiid--yyuueezw.
Amir Beck and Mare Teboulle. Mirror descent and nonlinear projected subgradient methods for convex optimization. Operations Research Letters, 31()):677-175, 2003.
Aleksandr Beznosikov and Alexander Gasnikov. Similarity, compression and local steps: Three pillars of efficient communications for distributed variational inequalities. arXiv preprint arXiv:2302.07615. 2023.
Aleksandr Beznosikov, Valentin Samokhin, and Alexander Gasnikov. Distributed saddle-point problems: Lower bounds, optimal and robust algorithms. arXiv preprint arXiv:2010.13112, 2020.
Alcksandr Beznosikov, Gesualdo Scutari, Alexander Rogozin, and Alexander Gasnikov. Distributed saddlc-point problems under data similarity. Advances in Neural Information Processing Systems, 34:8172-8184. 2021.
Aleksandr Beznosikov, Pavel Dvurechenskii, Anastasiia Koloskova, Valentin Samokhin, Sebastian U Stich, and Alexander Gasnikov. Decentralized local stochastic extra-gradient for variational inequalities. Advances in Neural Information Processing Systems, 35:381 16-38133, 2022.
Ekaterina Borodich, Vladislav Tominin, Yaroslav Tominin, Dmitry Kovalev, Alexander Gasnikov, and Pavel Dvurechensky. Accelerated variance-reduced methods for saddle-point problems. EURO Journal on Computational Optimization, 10: 10:100048, 2022.
Ekaterina Borodich, Georgiy Kormakov, Dmitry Kovalev, Aleksandr Beznosikov, and Alexander Gasnikov. Optimal algorithm with complexity separation for strongly convex- concave composite saddle point problems. arXiv preprint arXiv:2307.119414 2023.
Stephen P Boyd and Lieven Vandenberghe. Convex optimization. Cambridge university press, 2004.
Kristian Bredies, Dirk A Lorenz, and Stefan Reiterer. Minimization of non-smooth, non-convex functionals by iterative thresholding. Journal of Optimization Theory and Applications, 165: 78-112, 2015.
L.M. Bregman. The relaxation method of finding the common point of convex sets and its ap- plication to the solution problems in convex programming. USSR Computational Mathe- matics and Mathematicaal Physics, 7(3):200-217, 1967. ISSN 0041-5553. doi: https://doi.org/ 10.1011600441555567777000044 URL https: www.:.sienneeieeee...... com/ www.sciin//eeeeeeeeoeeeccecccoce science/ /
10

---

Published as a conference paper at ICLR 2024
Antoni Buades, Bartomeu Coll, and Jean-Michel Morel. A review of image denoising algorithms, with a new one. Multiscale modeling simulation, 4(2):490- 530, 2005.
Sébastien Bubeck et al. Convex optimization: Algorithms and complexity. Foundations and Trends in Machine Learning, 8(3-4):231-357, 2015.
Brian Bullins and Kevin A Lai. Higher-order methods for convex-concave min-mat max optimization and monotone variational inequalities. SIAM Journal on Optimization, 32(3):2208-22)) 2229,, 2022.
Brian Bullins, Kshitij Patel, Ohad Shamir, Nathan Srebro, and Blake E Woodworth. A stochastic newton algorithm for distributed convex optimization. Advances in Neural Information Processing Systems, 34:26818 18- 8-26630, 2021.
Jian-Feng Cai, Emmanuel Candès, and Zuowei Shen. A singular value thresholding algorithm for matrix completion. SIAM Journal on optimization, 20(4): 1956-1982, 2010.
Xuanyu Cao, Tamer Başar, Suhas Diggavi, Yonina C Eldar, Khaled B Letaief, H Vincent Poor, and Junshan Zhang. Communication--ffiiieee distributed learning: An overview. IEEE journal on selected areas in communications, 2023.
Y Censor and SA Zenios. Proximal minimization algorithm with d-functions. Journal of Optimization Theory and Applications, 73(3):451 1464, 1992.
A. Chambolle and Thomas Pock. A first-order primal-dual algorithm for convex problems with applications to imaging. Journal of Mathematical Imaging and Vision, 40: 40:120-145, 2011.
Antonin Chambolle and Thomas Pock. On the ergodic convergence rates of first-order primal-dual algorithm. Mathematical Programming, 159(1-2):553-877 2016.
Cheng Chen, Luo Luo, Weinan Zhang, and Yong Yu. Efficient projection-free algorithms for saddle point problems. Advances Neural Information Processing Systems, 33:10799-10809 2020.
Pin- Yu Chen and Cho-Jui Hsieh. Chapter 12 adversarial training. In Pin- Yu Chen and Cho-Jui Hsieh (eds.), Adversarial Robustness for Machine Learning, pp. 119-125, Academic Press, 2023. ISBN 978-0-12-824020-5. doi:
wttt:///rr//.00101090000-1-----0 // //ww: www.:cecieecciccccoc rect. com/
URL https
Michael B. Cohen, Aaron Sidford, and Kevin Tian. Relative lipschitzness in extragradient methods and a direct recipe for acceleration. In James R. Lee (ed.), 12th Innovations in Theoretical Computer Science Conference, ITCS 2021, January 6-8, 2021, Viriual Conference, volume 185 of LIPlcs, pp. 62:1-62:18. 18. Schloss Dagstuhl Leibniz--Zentrum für Informatik, 2021. doi: 10.4230/ pFCS.20211 62.
LIPIes.ITCS.200 2021.62. URL https:
doi org/10.../.. http:/10.433//IIPIIC
Patrick L Combettes and Jean- -hrristist Pesquet. Primal-dual splitting algorithm for solving inclusions with mixtures of composite, lipschitzian, and parallel-sum type monotone operators. Set-Valued and variational analysis, 20(2):307-330, 2012.
Alexandros Dimakis, Anand D Sarwate, and Martin Wainwright. Geographic gossip: Efficient aggregation for sensor networks. In Proceedings of the 5th international conference on Information processing in sensor networks, pp. 69-76, 2006.
John C Duchi, Shai Shalev-Shwartz, Yoram Singer, and Ambuj Tewari. Composite objective mirror descent. In Conference on Learning Theory (COLT), volume 10, pp. 14-26. Citeseer, 2010.
John C Duchi, Alckh Agarwal, and Martin Wainwright. Dual averaging for distributed optimization: Convergence analysis and network scaling. IEEE Transactions on Automatic control, 57(3): 592-606, 2011.
Nicolas Flammarion and Francis Bach. Stochastic composite least-squares regression with conver- gence rate o(1/n). In Conference Learning Theory (COLT), pp. 831-875. PMLR, 2017.
Margalit R Glasgow, Honglin Yuan, and Tengyu Ma. Sharp bounds for federated averaging (local sgd) and continuous perspective. In International Conference on Artificial Intelligence and Statistics, pp. 9050-9090. PMLR, 2022.
11

---

Published as a conference paper at ICLR 2024
Ian Goodfellow, Jean Pouget-Abadie, Mehdi Mirza, Bing Xu, David Warde-Farley, Sher- jil Ozair, Aaron Courville, and Yoshua Bengio. Generative adversarial nets. In Z. Ghahramani, M. Welling, C. Cortes, N. Lawrence, and K.Q. Weinberger (eds.), Ad- vances in Neural Information Processing Systems, volume 27. Curran Associates, Inc., 2014. URL https: http:///ooooeeee.ceeeeee www.iipp.ccpppprrr......... cc/paper_ffiieeeeeeeeee wtt__fflss/pappr///00/ htle://abeeb222211180009sssseeee
Vipul Gupta, Avishek Ghosh, Michal Dereziński, Rajiv Khanna, Kannan Ramchandran, and Michael W. Mahoney. Localnewton: Reducing communication rounds for distributed learn- ing. In Cassio de Campos and Marloes H. Maathuis (eds.), Proceedings of the Thirty-Seventh Conference on Uncertainty in Artificial Intelligence, volume 161 of Proceedings of Machine Learning Research, pp. 642.642. PMLR, 27-30 Jul 2021. URL https: http::///proceeddngg// mlr. press serress/vvll. http//v11////g/ htpplggptaallllaaamm html.
Farzin Haddadpour, Mohammad Mahdi Kamani, Mehrdad Mahdavi, and Viveck Cadambe. Local sgd with periodic averaging: Tighter analysis and adaptive synchronization. Advances Neural Information Processing Systems, 32, 2019.
Trevor Hastie, Robert Tibshirani, and Martin Wainwright. Statistical learning with sparsity: the lasso and generalizations. CRC press, 2015.
Niao He, Anatoli Juditsky, and Arkadi Nemirovski. Mirror prox algorithm for multi-term composite minimization and semi-separable problems. Computational Optimization and Applications, 61: 275-319, 2015.
Yunlong He and Renato DC Monteiro. Accelcrating Block-decomposiigg first-order methods for solving composite saddle-point and two-player nash equilibrium problems. SIAM Journal on Optimization, 25(4): 2015.
Yunlong He and Renato DC Monteiro. An accelerated hpe-type algorithm for a class of composite convex-concave saddle-point problems. SIAM Journal on Optimization, 26(1):29-56, 2016.
Jean-Baptiste Hiriart-Uruut and Claude Lemaréchal. Fundamentals of convex analysis. Springer Science & Business Media, 2004.
Charlie Hou, Kiran K Thekumparampil, Giulia Fanti, and Sewoong Oh. Efficient algorithms for federated saddle point optimization. arXiv preprint 33X1v:2102.06333, 2021.
Ruichen Jiang and Aryan Mokhtari. Generalized optimistic methods for convex-concave saddle point problems. arXiv preprint axXiv:220..0667, 2022.
Anatoli Juditsky, Arkadi Nemirovski, and Claire Tauvel. Solving variational inequalities with stochastic mirror-prox algorithm. Stochastic Systems, 1(1):17-58, 2011.
Peter Kairouz, H Brendan McMahan, Brendan Avent, Aurélien Bellet, Mehdi Bennis, Arjun Nitin Bhagoji, Kallista Bonawitz, Zachary Charles, Graham Cormode, Rachel Cummings, et al. Ad- vances and open problems in federated learning. Foundations and Trends@ in Machine Learning. 14(1-2):1-216 2021.
Sai Pranceth Karimireddy, Satyen Kale, Mehryar Mohri, Sashank Reddi, Sebastian Stich, and Ananda Theertha Suresh. Scaffold: Stochastic controlled averaging for federated learning. In International Conference on Machine Learning, pp. 5132-5143. PMLR, 2020.
Ahmed Khaled, Konstantin Mishchenko, and Peter Richtárik. Tighter theory for local sgd on identical and heterogeneous data. In International Conference on Artificial Intelligence and Statistics, pp. 4519 PMLR, 2020.
Jakub Konečný, H Brendan McMahan, Felix X Yu, Peter Richtárik, Ananda Theertha Suresh, and Dave Bacon. Federated learning: Strategies for improving communication efficiency. NeurIPS Private Multi-Party Machine Learning Workshop. 2016.
G.M. Korpelevich. The extragradient method for finding saddle points and other problem. Ekonomika Matematicheskie Metody, 12:C747-C756, 1976.
12

---

Published as a conference paper at ICLR 2024
Georgios Kotsalis, Guanghui Lan, and Tianjiao Li. Simple and optimal methods for stochastic variational inequalities, i: operator extrapolation. SIAM Journal on Optimization, 32(3):2041- 2073, 2022.
D. Kovalev, Elnur Gasanov, Peter Richtárik, and Alexander V. Gasnikov. Lower bounds and optimal algorithms for smooth and strongly convex decentralized optimization over time-varying networks. In Neural Information Processing Systems, 2021a
Dmitry Kovalev, Egor Shulgin, Peter Richtárik, Alexander V Rogozin, and Alexander Gasnikov. Adom: Accelerated decentralized optimization method for time varriig networks. In International Conference on Machine Learning, pp. 5784-5793. PMLR, 2021b.
Dmitry Kovalev, Aleksandr Beznosikov, Ekaterina Borodich, Alexander Gasnikov, and Gesualdo Scutari. Optimal gradient sliding and its application to optimal distributed optimization under similarity. Advances in Neural Information Processing Systems, 35:33494-33507, 2022.
Sucheol Lee and Donghwan Kim. Fast extra gradient methods for smooth structured nonconvex- nonconcave minimax problems. Advances in Neural Information Processing Systems, 34:22588- 22600, 2021.
Guoyin and Ting Kei Pong. Global convergence of splitting methods for nonconvex composite optimization. SIAM Journal on Optimization, 25(4):2434 2460, 2015.
Li, Yuxi Fan, Mike Tse, and Kuo- Yi Lin. A review of applications in federated learning. Computers & Industrial Engineering, 149:106854 2020a.
Xiang Li, Kaixuan Huang, Wenhao Yang. Shusen Wang, and Zhihua Zhang. On the convergence of fedavg on non-iid data. International Conference on Learning Representations, 2020b. URL
https: /eppnreviiee nnt/ /oormo d=HJNNAnVEDS..
Tianyi Lin, Chi Jin, and Michael I Jordan. Near-optimal algorithms for minimax optimization. In Conference on Learning Theory, pp. 2738-2779. PMLR, 2020.
Changxin Liu, Zirui Zhou, Jian Pei, Yong Zhang, and Yang Shi. Decentralized composite optimization in stochastic networks: dual averaging approach with linear convergence. IEEE Transactions on Automatic Control, 2022.
Weijie Liu, Aryan Mokhtari, Asuman Ozdaglar, Sarath Pattathil, Zebang Shen, and Nenggan Zheng. A decentralized proximal point-type method for saddle point problems. OPT2020: 12th Annual Workshop Optimization for Machine Learning, 2020.
Aleksander Madry, Aleksandar Makelov, Ludwig Schmidt, Dimitris Tsipras, and Adrian Vladu. To- wards deep learning models resistant adversarial attacks. In International Conference on Learn- ing Representations, 2018 URL https: /pwnrevieeeeeeeeeeeee n forum www.fooroorrrarro 2id=rJzIdfBF
Brendan McMahan, Eider Moore, Daniel Ramage, Seth Hampson, and Blaise Aguera Arcas. Communication-Effiiiie Learning of Deep Networks from Decentralized Data. In Aarti Singh and Jerry Zhu (eds.), Proceedings of the 20th International Conference on Artificial Inielligence and Statisties, volume 54 of Proceedings of Machine Learning Research, pp. 1273-1282. PMLR, 20-22 Apr 2017. URL https: ppwpeedingeegsseceeeeeeppcc...sp
mmlr ppwss/vveeeee.eeee..eeeeeeeeeese v mnncmaaannl 7 html.
Panayotis Mertikopoulos, Bruno Lecouat, Houssam Zenati, Chuan-Sheng Foo, Vijay Chandrasekhar, and Georgios Piliouras. Optimistic mirror descent in saddle-poin problems: Going the extra(- gradient) mile. In International Conference Learning Representations, 2019. URL https: // //openrevi lew net. www.nnt/ooorumiiieo.. Bdg
Konstantin Mishchenko, Dmitry Kovalev, Egor Shulgin, Peter Richtárik, and Yura Malitsky. Revisit- ing stochastic extragradient. In International Conference on Artificial Intelligence and Statistics, pp. 4573 PMLR, 2020.
Konstantin Mishchenko, Grigory Malinovsky, Sebastian Stich, and Peter Richtárik. Proxskip: Yes! local gradient steps provably lead to communication acceleration! finally! In International Conference Machine Learning, pp. 15750-15769. PMLR, 2022.
13

---

Published as a conference paper at ICLR 2024
Seyed- Moyed-Mohsen Moosavi-Dezfoolie Alhussein Fawzi, and Pascal Frossard. Deepfool: A simple and accurate method to fool deep neural networks. In 2016 IEEE Conference on Computer Vision and Patter Recognition (CVPR), pp. 2574-2582, 2016. doi: 10.1109/CVP.22016.288.
Seyed-Mohsen Moosavi-Dezfooli, Alhussein Fawzi, Omar Fawzi, and Pascal Frossard. Universal adversarial perturbations. In Proceedings of the IEEE conference on computer vision and pattern recognition, pp. 1765-1773, 2017.
Angelia Nedich et al. Convergence rate of distributed averaging dynamics and optimization in networks. Foundations and Trends@ in Systems and Control, 2(1):1-100, 2015.
Arkadi Nemirovski. Prox-method with rate of convergence (1/t) for variational inequalities with lipschitz continuous monotone operators and smooth convex-concave saddle point problems. SIAM Journal on Optimization, 15(1):229 251, 2004.
Arkadij Semenovič Nemirovskij and David Borisovich Yudin. Problem complexity and method efficiency in optimization. Wiley- eeley-Interscience, 1983.
Yu Nesterov. Smooth minimization of non-smooth functions. Mathematical programming, 103: 127-152, 2005.
Yurii Nesterov. Dual extrapolation and its applications solving variational inequalities and related problems. Mathematical Programming, 109(2-3):3193344 2007.
Yurii Nesterov. Primal-dual subgradient methods for convex problems. Mathematical 120(1):221-259, 2009.
paozeeemniccpprggaammiigg programming,
Yuyuan Ouyang and Yangyang Xu. Lower complexity bounds of first-order methods for convex- concave bilinear saddle-point problems. Mathematical Programming, 185(1-2):1-35, 2021.
Leonid Denisovich Popov. A modification of the arrow-hurwiez method for search of saddle points. Mathematical notes of the Academy of Sciences of the USSR, 88:845-848, 1980.
Michael Rabbat. Multi-agent mirror descent for decentralized stochastic optimization. In 2015 IEEE 6th International Workshop on Computational Advances in Multi-Sensor Adaptive Processing (CAMSAP), pp. 517-520. IEEE, 2015.
Ali Seanezzai-Keebrye Kimon Antonakopoulos, Igor Krawczuk, Justin Deschenaux, and Volkan Cevher. Distributed extra- gradientt with optimal complexity and communication guarantees. In The Eleventh International Conference on Learning Representations, 2023. URL https:
/ppenreviiew net. htt/://ormmiiireeee (tte://ooommmndda111ayaaaaaa
R. Tyrrell Rockafellar. Convex Analysis. Princeton Landmarks in Mathematics and Physics. Princeton University Press, 1970. ISBN 11011-4408-7317--5
Alexander Rogozin, Aleksandr Beznosikov, Darina Dvinskikh, Dmitry Kovalev, Pavel Dvurechensky, and Alexander Gasnikov. Decentralized distributed optimization for saddle point problems. arXiv preprint arXiv:2102.07758 2021.
Mher Safaryan, Rustem Islamov, Xun Qian, and Peter Richtarik. Fednl: Making newton-type
methods applicable to federated learning. International Conference on Machine Learning, pp. 18959-19010. PMLR, 2022.
Arda Sahiner, Tolga Ergen, Batu Ozturkler, Burak Bartan, John M. Pauly, Morteza Mardani, and Mert Pilanci. Hidden convexity of wasserstein GANs: Interpretable generative models with closed-form solutions. In International Conference on Learning Representations, 2022. URL https:://ppee http:////eeeeeeee..eeeeee...e... net http://wwwwweeeeteeeeeeeeeeeeeee wtt.:/oidoemieeeeeeaaaeided
Ali Shafahi, Mahyar Najibi, Zheng Xu, John Dickerson, Larry S Davis, and Tom Goldstein. Universal adversarial training. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 34, pp. 5636-5643, 2020.
Ohad Shamir, Nati Srebro, and Tong Zhang. Communication-effce distributed optimization using an approximate newton-typs type method. In International conference on machine learning, pp. 1000-1008. PMLR, 2014.
14

---

Published as a conference paper at ICLR 2024
Pranay Sharma, Rohan Panda, Gauri Joshi, and Pramod Varshney. Federated minimax optimization: Improved convergence analyses and algorithms. In International Conference on Machine Learning. pp. 19683-19730. PMLR, 2022.
Pranay Sharma, Rohan Panda, and Gauri Joshi. Federated minimax optimization with client hetero- geneity. arXiv preprini arXiv:2302.042444 2023.
Yan Shen, Jian Du, Han Zhao, Benyu Zhang, Zhanghexuan Ji, and Mingchen Gao. Fedmm: Sad- dle point optimization for federated adversarial domain adaptation. In The 22nd International Conference on Autonomous Agents and Multiagent Systems (AAMAS), 2023.
Zhan Shi, Xinhua Zhang, and Yaoliang Yu. Bregman divergence for stochastic variance reduction: saddle-point point and adversarial prediction. Advances in Neural Information Processing Systems, 30, 2017.
Mircea Sofonea and Andaluzia Matei. Variational inequalities with applications: study of antiplane frictional contact problems, volume 18. Springer Science & Business Media, 2009.
Mikhail V. Solodov and Benar Fux Svaiter. A hybrid approximate extragradient proximal point algorithm using the enlargement of maximal monotone operator. Set- Valued Analysis, 7:323-345. 1999.
Chaobing Song, Zhengyuan Zhou, Yichao Zhou, Yong Jiang, and Yi Ma. Optimistic dual extrapolation for coherent non-monotone variational inequalities. Advances in Neural Information Processing Systems, 33:14303-1431 143800--1314, 2020.
Sebastian U. Stich. Local SGD converges fast and communicates little. In International Confer- ence on Learning Representations, 2019. URL http::s///openeveee...r.. wwtp:nnnnffffiiicommmmm S1g22nnccXX.
Gilbert Strang, Linear algebra and its applications. Belmont, CA: Thomson, Brooks/Cole, 2006.
Robert Tibshirani. Regression shrinkage and selection via the lasso. Journal of the Royal Statistical Society. Series B (Methodological), 58(1):267-288 1996. ISSN 00359246. URL http: /www.
Sstoo..rg//stable/23344
Vladislav Tominin, Yaroslav Tominin, Ekaterina Borodich, Dmitry Kovalev, Alexander Gasnikov, and Pavel Dvurechensky. On accelerated methods for saddle-point problems with composite structure. arXiv preprint 2rXiv:2103.09344 2021.
Qianqian Tong, Guannan Liang. Tan Zhu, and Jinbo Bi. Federated nonconvex sparse learning. arXiv preprint arXiv:2101.0005: 2020.
Quoc Tran Dinh, Nhan H Pham, Dzung Phan, and Lam Nguyen. rando--rdddmized douglas- rachford splitting algorithms for nonconvex federated composite optimization. Advances in Neural Information Processing Systems, 34:30326-30338, 2021.
Paul Tseng, On accelerated proximal gradient methods for convex-concave optimization. submitted to SIAM Journal Optimization, 2(3), 2008
Hoi-To Wai, Zhuoran Yang, Zhaoran Wang. and Mingyi Hong. Multi-agent reinforcement learning via double averaging primal-dual optimization. Advances in Neural Information Processing Systems, 31, 2018
Jianyu Wang, Zachary Charles, Zheng Xu, Gauri Joshi, H Brendan McMahan, Maruan Al-Shedivat, Galen Andrew, Salman Avestimehr, Katharine Daly, Deepesh Data, et al. A field guide to federated optimization. arXiv preprint 1r7.v:2107.06917 2021.
Blake Woodworth, Kumar Kshitij Patel, Sebastian Stich, Zhen Dai, Brian Bullins, Brendan Memahan, Ohad Shamir, and Nathan Srebro. Is local sgd better than minibatch sgd? In International Conference on Machine Learning, pp. 10334-10343. PMLR, 2020a.
Blake E Woodworth, Kumar Kshitij Patel, and Nati Srebro. Minibatch vs local sgd for heterogeneous distributed learning. Advances in Neural Information Processing Systems, 33:6281-665 -6292, 2020b.
15

---

Published as a conference paper at ICLR 2024
Lin Xiao. Dual averaging methods for regularized stochastic learning and online optimization. The Journal of Machine Learning Research, 11:2543-2596, 2010.
Tesi Xiao, Xuxing Chen, Krishnakumar Balasubramanian, and Saeed Ghadimi. A one-sample
decentralized proximal algorithm for non-convex stochastic composite optimization. In Robin J. Evans and Ilya Shpitser (eds.), Proceedings of the Thirty-Ninth Conference on Uncertainty in Artificial Intelligence. volume 216 of Proceedings of Machine Learning Research, pp. 2324- 2334. PMLR, 31 Jul-04 Aug 2023. URL https:/ httpce//ppcceeedeeeee mlr. wttpess.mrr..rrrrr www.ppess../1... xi 2o.3a..... html.
Jinming Xu, Tian, Ying Sun, and Gesualdo Scutari. Distributed algorithms for composite opti- mization: Unified framework and convergence analysis. IEEE Transactions Signal Processing, 69:3555-3570, 2021. doi: 10. 10..1099222222..868578777
Yonggui Yan, Jie Chen, Yu Chen, Xiaodong Cui, Songtao Lu, and Yangyang Xu. Compressed decentralized proximal stochastic gradient method for nonconvex composite problems with hetero- geneous data. In International Conference on Machine Learning. 2023.
Hao Yu, Sen Yang. and Shenghuo Zhu. Parallel restarted sgd with faster convergence and less communication: Demystifying why model averaging works for deep learning. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 33, pp. 5693-5700, 2019.
Honglin Yuan and Tengyu Ma. Federated accelerated stochastic gradient descent. Advances in Neural Information Processing Systems, 33:5332-5344 2020.
Honglin Yuan, Manzil Zaheer, and Sashank Reddi. Federated composite optimization. In International Conference on Machine Learning, pp. 12253-12266. PMLR, 2021.
Fan Zhou and Guojing Cong. On the convergence properties of a k-step averaging stochastic gradient descent algorithm for nonconvex optimization. In Proceedings of the Twenty-Seventh International Joint Conference on Artificial Intelligence, IJCAI-18, pp. 3219-3227. International Joint Conferences Artificial Intelligence Organization, 7 2018. doi: 10. (0.24963/jcai.20188444 URL https: / /ttp://o..ooo//oooo/ooo org 10. 24963/244422 /jjcii..a. 2018/447.
Kang Zhou, Shenghua Gao, Jun Cheng, Zaiwang Gu, Huazhu Fu, 7hi Tu, Jianlong Yang, Yitian Zhao, and Jiang Liu. Sparse-gan: Sparsity-constraine generative adversarial network for anomaly detection in retinal oct image. In 2020 IEEE 17th International Symposium on Biomedical Imaging (ISBI), pp. 1227-1231. IEEE, 2020.
Martin Zinkevich, Markus Weimer, Lihong Li, and Alex Smola. Parallelized stochastic gradient descent. Advances in neural information processing systems, 23, 2010.
16

---

Published as a conference paper at ICLR 2024
Appendices
In Appendix A, we provide details on experiment settings and additional experiments on the universal adversarial training of non-convex convolutional neural networks. In Appendix B, an extended literature review on various related subfields is included. Appendix C and D provide additional theoretical background, including relevant preliminaries, definitions, remarks, and technical lemmas. Appendix E, F, and G provide the convergence rates and complete proofs for FeDualEX in federated composite saddle point optimization, federated composite convex optimization, sequential stochastic composite optimization, and sequential deterministic composite optimization respectively. Finally, the algorithm of FedMiP is presented Appendix H.
A Additional Experiments and Setup Details
18
Setup Details for Saddle Point Optimization with Sparsity Regularization
18
A.2 Saddle Point Optimization with Low-Rank Regularization
19
A.3 Universal Adversarial Training of Logistic Regression
20
A.4 Universal Adversarial Training of Neural Networks
21
Extended Literature Review
B.1
Distributed Optimization / Federated Learning
21
B.2 Saddle Point Optimization
................................
B.3 Composite Optimization
22
B.4
Other Tangentially Related Work
23
Additional Preliminaries, Definitions, and Remarks Assumptions
23
C.1 Additional Preliminaries
23
C.1.1 Mirror Descent and Dual Averaging
24
C.1.2 Mirror Prox and Dual Extrapolation
................................
25
C.2 Additional Definitions..
26
................................
C,3 Formal Assumptions and Remarks
26
Additional Technical Lemmas
27
E Complete Analysis of FeDualEx for Composite Saddle Point Problems
29
E.1 Main Theorem and Proof
29
E.2 Helping Lemmas
33
Complete Analysis of FeDualEx for Composite Convex Optimization
36
G FeDualEx in Other Settings
39
G.1 Stochastic Dual Extrapolation for Composite Saddle Point Optimization
39
G.2 Deterministic Dual Extrapolation for Composite Saddle Point Optimization
41
Federated Mirror Prox
42
17

---

Published as a conference paper at ICLR 2024
A ADDITIONAL EXPERIMENTS AND SETUP DETAILS
A.1 SETUP DETAILS FOR SADDLE POINT OPTIMIZATION WITH SPARSITY REGULARIZATION
We provide additional details for the SPP with the sparsity regularization demonstrated in the main text. We start by restating its formulation below:
min max max(Ax- b, + A||x A||y/|1 xEx YEy
A E R RnXm
= = [R" ||x - D), y [R" | S D).
b E Rd
hoft-Thresholding Operator for & Norm Regularization. By choosing the cestance-generating function to be = 2 12 b l2. the projection V x.)) instantiates to the following element-wise soft-thresholding operator (Hastie et al., 2015; Jiang & Mokhtari, 2022):
0
if ا S if < S otherwise
(x(()= =
(lw) X) sgn(w) D sgn(w)
which X' rT + k).
Closed-Form Duality Gap. The closed-form duality gap is given by
Gap(x, y) Ax bj +)+ + A||x|| + DIK(A yl A)+11 + (b, Alylli
where |- and (++ max (-00} are element-wise. We provide brief derivation below. Since constraint is equivalent to an indicator regularization, we move the loo constraint into the objective
and denote (-) = || 11, 92(-) 0 llxe D
By the definitions of duality gap in
do otherwise
Definition I and convex conjugate in Definition 9, the duality gap equals to
Gap(x,y) max A{{ (Ax b). (y) - g2(y) + ||x|]}}
x) + (x) + 92(x) - ||yll2 1 bbyy) y)
min A1( N (A TT),
X(a + 92)2 ( (Ax b)) + A(gi + 92))" _ ( (A y)) + A||x||1 A/y +b
1
(1)) )و2 (Ax b) - u}} inf ing ( Ty) v))
+1|/x|11 + A||y|| + +b² y:
in which the last equality holds by Theorem 2.3.2, namely infimal convolution, in Chapter of Hiriart- Etriart-Urruty & Lemaréchal (2004). By definition of the convex conjugate, the convex conjugate
of norm 9(-) || Ilp is defined to be g*) 0 if || 11g
in which || ||g is the dual
otherwise
norm of || Ip.. Given that é and loc are dual norms to each other, gi(-) (0 if 1 S
otherwise
05(-) DII [11- Therefore the infimum is achieved when Vi [m]. Vjj E [m]].
4; = (Ax - b); [sgu( (sx b).)
if I - b) : "i
( y); (sgn( + (A (AT)),
if (A y),l $ otherwise
otherwise
which yields the closed-form duality gap.
Additional Experiment Details. We generate a fixed pair of A and with each entry independently following the uniform distribution U;-11]] Each entry of the variables and is initialized indepen- dently from the distribution 4 p. As in (Jiang Mokhtari, 2022), we take m 600, n = 300, = 0.1, D 0.05. For DO, simulate M 100 clients. For the gradient query of each client
18

---

Published as a conference paper at ICLR 2024
in each local update, inject Gaussian noise from (V of). All M 100 clients participate in each round; noise on each client is i.id. with d = 0.1.
We only tune the global step size 17 and the local step size 7f. For all experiments, the parameters
are searched from the combination of 17 E {1,3e - 1, 1e - 1, 3e 2, 1e 2} and 1f E {1,3e
le 1, 3e 2, le 2e 3, le 3). We run each setting for 10 different random seeds and report the mean and standard deviation Figure
A.2 SADDLE POINT OPTIMIZATION WITH LOW-RANK REGULARIZATION
We test FeDualEx the following SPP with nuclear norm regularization for low-rankness, in which we overuse the notation! || ||~ for the matrix nuclear norm and || 2|2 for the matrix spectral norm. We Tr(-) denote the trace of square matrix. And for the purpose of feasibility and convenience. we impose spectral norm constraints on the variables as well.
min max Tr((AX- - B) Y) + X| I||I|+
XEX YEy
A ReXm
X' = [RmX) mxpx | 2 & D),
B E R"Xp,
y = (RR"XP Y| S D).
Soft-Thresholding Operator for Nuclear Norm Regularization. By choosing the distance- generating function to be l = | + Y!? where || ||r denotes the Frobenius norm, the projection V (+) instantiates to the following element-wis singular value soft-thresholding opera- tor (Cai et al., 2010):
(W) = UTx (x( diag(sgu(o, (W)) min((ax(a, (W) XX,0,
which = (T + Kk), W UΣVT is the singular value decomposition (SVD) of W, and we overuse the notation (-) to represent the singular values.
Closed-Form Duality Gap. The closed-form duality gap given by
+ Gap(X, Y) D|| (( B) 1)+ X|||| (Y) - I). Tr(B + AI|Y|
+
We provide a brief derivation below. Since constraint is equivalent to an indicator regular- ization, move the spectral norm constraint into the objective and denote g1(-)
|..
ge(+) 0 11a D Do otherwise
By the definitions of duality gap Definition I and convex conjugate
in Definition 9, the duality gap equals to
Gap(X, Y) = max AFTH(( (AX - B) - [X]+
min 7 (A +
+
IYIl, (B
= A(91 + 92) (AX B)) + X(q1 + 92)" ( YY)
+ +X|XI|1 YII. TT(BB
1 (A (YT) -) inf (P) + Ag 1 (AX- - B) - inf + أأا Aoil
+ X|IX + XII + YY),
in which the last equality holds by Theorem 2.3.2, namely infimal convolution, in Chapter H of Hiriart-Urruty & Lemaréchal (2004). By definition of the dual norm, we know that the nuclear
norm and the spectral norm are dual norms each other. Therefore, (-.) (0 if <
xo otherwise
19

---

Published as a conference paper at ICLR 2024
95(-) DII ||+. And the infimuum is achieved when
( (Ax (Ax
B))
if if B)]1 I
o, (P
sgm (H(x B)))
otherwise
or , (+ sgn (o, ( y)))
if (2 y))1 ([T)a
oy (Q)
otherwise
which yields the closed-form duality gap.
Experiment Settings. We generate fixed pair of A and B. Each entry of A and half of the columns in B follows the uniform distribution U1-111 independently. Each entry of the variables X and Y is initialized independently from the distribution 1.1). We take m = 600. n 300, = 20, 0.1, D 0.05. For DO, we simulate M 100 clients. For the gradient query of each client in each local update, we inject a Gaussian noise from (0, o²). All M = 100 clients participate in each round; noise on each client is i.i.d. with o 0.1. We only tune the global step size 17" and the local step size s7". For all experiments, the parameters are searched from the combination of ry" E {1,3e- -, 1e - 1, 3e 3--2 2, 1e-2] 2} and of 31 1. 1e- 1, 3e 2, 1e 2, 3e -3 1e-3). We run each setting for 10 different random seeds and plot the mean and the standard deviation.
We evaluate the convergence terms of the duality gap and also demonstrate the rank of the solution, for both X and Y. For the feasibility of low-rankness, the columns of B is linearly dependent on the other half. With p = 20, the optimal rank for the solution would most likely be 10. The evaluation is conducted for two different settings: (a) K 1
generate B to be of rank E. i.. half of
local update for R = 100 rounds; (b) 10 local updates for R = 20 rounds. The results are demonstrated in Figure 5 correspondingly.
Discussions. From Figure 5, we can see that in the setting for low-rankness regularization, dual methods tend perform better both in minimizing the duality gap and in encouraging a low-rank solution. In particular, FeDualEx, as a method geared for saddle point optimization, demonstrates better convergence the duality gap than FedDualAvg. In the meantime, the solution given by FeDualEx quickly reaches the optimal rank of 10. This further reveals the potential of FeDualEx in coping with a variety of regularization and constraints.
A.3 UNIVERSAL ADVERSARIAL TRAINING OF LOGISTIC REGRESSION
We provide the problem formulation and detailed experiment setting for the universal adversarial training of logistic regression demonstrated the main text.
Problem Formulation. As introduced, we impose an l regularization on the attack to encourage sparsity addition to the ball constraint. The problem can be formulated as the following SPP:
min WERd [[ S.D.D
max
Σ
[(w (x: + 0)) |
in which E is the cross-entropy loss for multiclass logistic regression; E Rdd is the parameter; X; E Rd is the data and is the label; 8 E Rd is the attack.
Experiment Settings. The training data for MNIST is evenly distributed across M 100 clients, each possessing 600. The client makes K = 5 local updates and communicates for R = 20 rounds. For the CIFAR-I0 experiments, each of the 100 clients holds 500 of the training data. The client makes K = 5 local updates and communicates for R = 40 rounds. D 0.05 for data normalized between 0 and À 0.1. Validation is done on the whole validation dataset on the server with unattacked data. As before, the hyper-parameters are searched from the combination of 1, le
17" E (1,3e-1, We run each setting for 10 different random seeds and plot the mean and the standard deviation in Figure 6.
1, 3e 2, 1e-2) 2] and of (10,3, 3, 1,3e ..3e-1,, 1e- 1, 3e 2, 1e 1e--,, 2, 3e 3, 3, le 1e-3). 3)-
Attack Visualization. The attack for MNIST has only one channel and is directly visualized with the color map from blue to red rescaled between the range of the attack, with blue being negative, red being positive, and purple being zero. The attack for CIFAR-10 contains 3 channels and can be directly visualized with RGB mode rescaled between 0 and 255. For the attack to be visible, we divide the value by its maximum then times the result by 4.
20

---

Published as a conference paper at ICLR 2024
Projected Gradient Descent Ascent
FeDualEx
x.2 10
2 10
Accuracy
40
1.8 x 10
1.6 x 10
20
1.4x 10
0
25
50
75
0
25
50
75
Communication Rounds
Communication Rounds
Figure 8: Training loss and validation accuracy of 3-layer CNN on unattacked data.
A.4 UNIVERSAL ADVERSARIAL TRAINING OF NEURAL NETWORKS
Even though the theoretical result is derived with respect to convex functions, we experimentally demonstrate the convergence FeDualEx for non-convex functions with the adversarial training of neural networks on CIFAR-10. The model tested is a 3-layer convolutional neural network (CNN) with 16, 32, and 64 filters of size x 3, each layer followed by a relu activation and a max-pooling. The performance is demonstrated in Figure 8. The loss value is by no means an exact reflection of the duality gap, nevertheless, FeDualEx also converges for non-convex functions, yielding faster numerical convergence and better-hardent models in terms of validation accuracy on unattacked data. In addition, the sparsity of the attack generated by FeDualEX is 50.38%, whereas that by the vanilla distributed version of projected gradient descent ascent is 99.31%.
B EXTENDED LITERATURE REVIEW
B.1 DISTRIBUTED OPTIMIZATION FEDERATED LEARNING
In recent years, distributed learning has received increasing attention in practice and theory. Earlier works in the field were known "parallel" (Zinkevich et al., 2010) or "local" (Zhou & Cong, 2018; Stich, 2019), which are later recognized as the homogeneous case, where data across clients are assumed to be balanced and i.i.d. (independent and identically distributed), of federated learning (FL), specifically, Federated Averaging (FedAvg) (McMahan et al., 2017), DO or FL has been found appealing in various applications (Li et al., 2020a). On the theoretical front, Stich (2019) provides the first convergence rate for Local SGD, or, FedAvg under the homogeneous setting. The distributed optimization paradigm
consider aligns with that in Local SGD (Stich, 2019). The rate for LocalSGD has been improved with tighter analysis (Haddadpour et al., 2019; Khaled et al., 2020; Woodworth et al., 2020a: Glasgow et al., 2022) and acceleration techniques (Yuan & Ma, 2020; Mishchenko et al., 2022). Others also analyze FedAvg under heterogeneity (Haddadpour et al., 2019; Khaled al., 2020; Woodworth et al., 2020b) and non-i.i.d. data (Li et al., 2020b) or in light propose improvements (Karimireddy et al., 2020). Recently, the idea of DO is further extended to higher-order methods (Bullins et al., 2021; Gupta et al., 2021; Safaryan et al., 2022). Due to the page limit, we refer the readers to (Cao et al., 2023; Wang et al., 2021; Kairouz et al., 2021) for more comprehensive reviews of DO and FL. In the meantime, we point out that none the work mentioned above covers saddle point problems or non-smooth composite constrained problems. For distributed saddle point optimization and federated composite optimization, we defer to the following subsections.
B.2 SADDLE POINT OPTIMIZATION
The study of Saddle Point Optimization dates back to the very early gradient descent ascent (Arrow et al., 1958). was later improved by the important ideas of extra-gradie extra-graddent (Korpelevich, 1976) and optimism (Popov, 1980). In light of these ideas, many algorithms were proposed for SPP (Solodov & Svaiter, 1999; Nemirovski, 2004; Nesterov, 2007: Chambolle & Pock, 2011 I; Mertikopoulos et al., 2019; Jiang& & Mokhtari, 2022). Among them, in the convex-concar setting in particular, the most relevant and prominent ones are Nemirovski's mirror prox Nemirovski (2004) and Nesterov's 's dual extrapolation Nesterov (2007). They generalize respectively Mirror Descent (Nemirovskij & Yudin, 1983) and Dual Averaging (Nesterov, 2009) from convex optimization to monotone variational inequalities (VIs) which include SPP one realization. Along with Tseng's Accelerated Proximal
21

---

Published as a conference paper at ICLR 2024
Gradient (Tseng, 2008), they the three methods that converge e-approximate solution in terms of duality gap at O ). the known best rate for a general convex-concave SPP (Ouyang & Xu, 2021; Lin et al., 2020). Mirror prox inspired many papers (Antonakopoulos al., 2019; Chen et al., 2020) and is later extended to the stochastic setting (Juditsky et al., 2011 I; Mishchenko et al., 2020), the higher-order setting (Bullins & Lai, 2022), and even the composite setring (He et al., 2015), whose introduction we defer to the review of composite optimization. Dual extrapolation is later extended to non-monotone VIs (Song et al., 2020), yet its stochastic and composite versions are, to the best of our knowledge, not found. Kotsalis et al. (2022) recently studied optimal methods for stochastic variational inequalities, yet their result is limited smooth VIs, not composite ones.
From the perspective of distributed optimization, several works have made preliminary progress for smooth and unconstrained SPP the Euclidean space. Beznosikov et al. (2020) investigate the distributed extra- -tra-ggrdiiet method under various conditions and provide upper and lower bounds under strongly-conver strongly-concave concave and non-convex non-concave assumptions. Hou et al. (2021) propose FedAvg-S and SCAFFOLD-S based on FedAvg (McMahan et al., 2017) and SCAFFOLD (Karimiredyy et al., 2020) for SPP, which achieves similar convergence rate to the distributed extra- gradient algorithm (Beznosikov et al., 2020) under the strong- convexity-concien addition, (Ramezani- Keamezani-Kebrya et al., 2023) studies the problem from the information compression perspective with the measure of communication bits. The topic of distributed or federated saddle point optimization is also found in recent applications of interest, e.g. adversarial domain adaptation (Shen et al., 2023). Yet, none of the existing works includes the study for SPP with constraints or composite possibly non-smooth regularization. Outside of our setting, Borodich et al. (2023) also studies composite SPP, but assumes composite terms be smooth as well.
assumption. In
B.3 COMPOSITE OPTIMIZATION
Composite optimization has been an important topic due to its reflection of real-world complexities. Representative works include composite mirror descent (Duchi et al., 2010) and regularized dual averaging (Xiao, 2010; Flammarion & Bach, 2017) that generalize mirror descent (Nemirovskij & Yudin, 1983) and dual averaging (Nesterov, 2009) in the context of composite convex optimization. Composite saddle point optimization, in comparison, appears dispersedly in early-day problems in practice (Buades al., 2005; Aujol Chambolle, 2005), often as a primal-dual reformulation of composite convex problems. Solving techniques such as smoothing (Nesterov, 2005) and primal-dual splitting (Combettes & Pesquet, 2012) were proposed, and numerical speed-ups were studied (He Monteiro, 2015; 2016), while systematic convergence analysis on general composite SPP came later in time (He et al., 2015; Chambolle & Pock, 2016; Jiang & Mokhtari, 2022). Recently, Tominin et al. (2021); Borodich et al. (2022) also proposed acceleration techniques for composite SPP.
Most related among them, the pioneering composite mirror prox (CoMP) (He et al., 2015) constructs auxiliary variables for the composite regularization terms non-smooth term into the problem domain. Observing that the gradient operator for the auxiliary variable is constant, CoMP operates "as if" there were composite components all (He et al., 2015), and exhibits a ( convergence rate that matches its smooth version (Nemirovski, 2004). In the stochastic setting, Mishchenko et al. (2020) analyzed a variant of stochastic mirror prox (Juditsky et al., 201 I), which is then capable of handling composite terms in the Euclidean space. In this paper, we take a different approach that utilizes the generalized Bregman divergence and get the same rate for composite dual extrapolation.
upper bound and thus moves the
For distributed composite optimization with local updates. Yuan et al. (2021) study Federated Mirror Descent, a natural extension of FedAvg that adapts to composite optimization under the convex setting, Along the way, they identified the "curse of primal averaging" specific to composite optimization in the DO paradigm, where the cnaularization-mmpoee structure on the client models may no longer hold after server primal averaging. To resolve this issue, they further proposed Federated Dual Averaging which brings the averaging step to the dual space. Tran Dinh et al. (2021) proposes federated Douglas-Racee Rachford splitting algorithm for nonconvex composite optimization. On the less related constrained optimization topic, Tong et al. (2020) proposed federated learning algorithm for nonconvex sparse learning under & constraint. To the best of our knowledge, the field of distributed optimization for composite SPP remains blank, which we regard the main focus of this paper.
22

---

Published as a conference paper at ICLR 2024
B.4 OTHER TANGENTIALLY RELATED WORK
Decentralized Optimization. Parallel to FL or DO with local updates, there is another line of work that studies decentralized optimization or consensus optimization over networks, in which machines communicate directly with each other based on their topological connectivity (Nedich et al., 2015). Classic algorithms mentioned previously are widely applied as well under this paradigm, for example, decentralized mirror descent (Rabbat, 2015) and decentralized (composite) dual averaging over networks (Duchi et al., 2011; Liu et al., 2022). Further in the context of composite optimization, Yan et al. (2023); Xiao et al. (2023) focus on composite non-convex objectives under the decentralized setting. Saddle point optimization has also been studied for decentralized optimization, including for proximal point-type methods (Liu et al., 2020) and extra-gradient methods (Rogozin et al., 2021; Beznosikov et al., 2021; 2022). In particular, Rogozin et al. (2021) 1) studies decentralized "mirror prox" " in the Euclidean space. We would like to point out that mirror prox in the Euclidean space reduces to vanilla extra- graddeett methods. In addition, Aybat & Yazdandoost Hamedani (2016); Xu et al. (2021) study the saddle point reformulation for composite convex objectives over decentralized networks, which essentially focus on composite convex optimization. In the general context of distributed learning of composite SPP, by the judgment of the authors, we came across no paper in decentralized optimization similar to ours. More importantly, decentralized optimization focuses on topics like time- varying network topology (Kovalev et al., 2021a;b) or gossip schema (Dimakis al., 2006), which are fundamentally different from our setting in terms of motivations, communication protocols, and techniques (Kairouz et al., 2021).
Manconvex-Nonconeatt Saddle Point Problems. For nonconvex-nonconeee SPP, several dis- tributed learning methods have recently been proposed, including extra-gradient methods (Lee & Kim, 2021) and the Local Stochastic Gradient Descent Ascent (Local SGDA) (Sharma et al., 2022; 2023). Yet we emphasize that our object of analysis is composite SPP with possibly non-smooth regularization, and remarked by Yuan et al. (2021), non-convex optimization for composite possi- bly non-smooth functions is in itself intricate even for sequential optimization, involving additional assumptions and sophisticated algorithm design (Li & Pong, 2015; Bredies et al., 2015), let alone distributed learning of SPP. Thus we focus on convex-concave analysis in this paper.
Finite-Sum Optimization with Function Similarity. Another line of work considers finite-sum optimization with function similarity, following the setting similar to DANE (Shamir et al., 2014). In this setting, each machine assumed to maintain a fixed set of data so that the functions across machines can be 8-similar with high probability by large-sample concentration inequalities. In the context of distributed saddle points optimization, examples include (Kovalev et al., 2022) and (Beznosikov & Gasnikov, 2023). This setting is significantly different from ours because we do not consider 5-similarity, and our optimization procedure presented in an online scheme. In (Beznosikov& & Gasnikov, 2023) in particular, local steps are also considered, but we would note that Beznosikov & Gasnikov (2023) require the server to take local steps instead of the clients, which also requires the presence of data on the server. This is done by making the first client the server and is in line with the setting in DANE (Shamir et al., 2014). In contrast, the server in our setting only aggregates the model and does not access any data, which also aligns with the purpose in FI..
C ADDITIONAL PRELIMINARIES, DEFINITIONS, AND REMARKS ON ASSUMPTIONS
In this section, we provide supplementary theoretical backgrounds for the algorithm and the con- vergence analysis of FeDualEx. We start by providing a more detailed introduction to the related algorithms, then list additional definitions necessary for the analysis. Before moving to the main proof for FeDualEx, we state formally the assumptions made and provide additional remarks on the assumptions that better link them to their usage in the proof.
C.1 ADDITIONAL PRELIMINARIES
To make this paper as self-contained as possible, in this section, we provide a brief overview of mirror descent, dual averaging, and their advancement in saddle point optimization, i.e., mirror prox and
23

---

Published as a conference paper at ICLR 2024
dual extrapolation. More comprehensive introductions be found in the original papers and in (Bubeck et al., 2015; Cohen et al., 2021). We slide into mirror descent from the simple and widely known projected gradient descent, namely vanilla gradient descent with constraint, therefore plus another projection of the updated sequence back to the feasible set.
C.I.1 MIRROR DESCENT AND DUAL AVERAGING
We start by introducing projected gradient descent. Projected gradient descent first takes the gradient update, then projects the updated point back to the constraint by finding feasible solution within the constraint that minimizes its Euclidean distance to the current point. The updating sequence given below: Vt E [T], 2z A' whereas not necessarily for z'C,
J = It (1²)
It-1 arg min 1| x 2/+1
sEX
Mirror Descent (Nemirovskij & Yudin, 1983). Mirror descent generalizes projected gradient descent to non-Euclidean space with the Bregman divergence (Bregman, 1967). We provide the definition of the Bregman divergence below.
Definition 5 (Bregman Divergence (Bregman, 1967)). Let h R -
R RUR } be prox function or distance- distance-generattng generating function that is closed, strictly convex, and differentiable in int dom h. The Bregman divergence for x E dom h and E int dom h is defined to be
V (z) = h(x) h(y) (Vh(u). x v)-
Mirror descent regards Vh as a mirror map to the dual space, and follows the procedure below:
Vh(*'+1) Vh(x,) (g())
F++1 arg min Vth
(I)
#EX
By choosing h(-)) 1 11 112 in the Euclidean space whose dual space is itself, mirror descent reduces to projected gradient descent.
Mirror descent can be presented from a proximal point of view, or in the online setting as in Beck Teboulle (2003):
arg min(ng(2.)) x) VA (z).
Te+1
2Ex
Such proximal operation with Bregman divergence studied by others (Censor & Zenios, 1992). and is recently represented by a neatly defined proximal operator (Cohen et al., 2021).
Definition 6 (Proximal Operator (Cohen et al., 2021)). The Bregman divergence defined proximal operator is given by
Prox & (-) arg min ((,2) (x)).
zEx
In this spirit, the mirror descent algorithm can be written with one proximal operation:
Ft+1 Prox 2, (ng(x:))-
Composite Mirror Descent (Duchi al., 2010). Mirror descent was later generalized to com- posite convex functions, i.e., the ones with regularization. The key modification is to include the regularization term in the proximal operator, yet not linearize the regularization term, since could be non-smooth and thus non-differentiable. The updating sequence is given by
arg min (ng(())) x) + v (z) + (z)())
Lt+1
aex
can also be represented with a composite mirror map as in (Yuan et al., 2021):
Zt+1
4(h + m (Vh(2.) ng(x:))-
24

---

Published as a conference paper at ICLR 2024
Dual Averaging (Nesterov, 2009). Compared with mirror descent, dual averaging moves the updating sequence to the dual space. The procedure dual averaging is as follows (Bubeck et al., 2015):
Vh(E(+1) = Vh(a,) -gg(T=)
arg min 1i (x), *EA -
L++1
equivalently presented in (Nesterov, 2009) with the sequence of dual variables: Vt [T]. It E X, 14 E X
Mt+1 14 - (g((z)) T++1 = Vh (1+(1)1))
This can further simplified
T++1 arg (i
Σ g g(x)), Mx))
zEX
Composite Dual Averaging (Xiao, 2010). Around the same time as composite mirror descent, composite dual averaging, also known as regularized dual averaging, was proposed with a similar idea of including the regularization term in the proximal operator. As presented in the original paper (Xiao, 2010):
F++1
arg min(n zEX
Σ g())), + 1/(h(x))) txph)x))
in which (Sehe21 is non-negative and non decreasirgnnggee input sequence. Flammarion Bach (2017)
adopted the case with constant sequence n¹
T1+1 arg min xEX
Σ g(x)),,)) + h(x)) + (mb((x))
and equivalently with composite mirror map:
M4+1 = Pt - (1+))
T++1 = (h + (mpp)" (14+1),
which is also presented in (Yuan et al., 2021).
C.1.2 MIRROR PROX AND DUAL EXTRAPOLATION
Mirror Prox (Nemirovski, 2004). Mirror prox generalizes the extra- satra-gradient method non- Euclidean space as mirror descent compared with projected gradient descent. It was proposed for variational inequalities (VIs), including SPP. We first present corresponding Bregman divergence in the saddle point setting, whose definition was not included in detail in (Nemirovski, 2004) but was later more clearly stated (Nesterov, 2007; Shi et al., 2017).
Definition 7 (Bregman Divergence for Saddle Functions (Nesterov, 2007)). Let X' (o) be a distance- distance-generatiin generating function that is closed, strictly convex, and differentiable in int dom &. For (x.y) E 2 X Y, the function and gradient are defined as
Valn (x) V (2))
E(z) h1(x) h2(3).
V((2)
The Bregman divergence for (x,y) E dom l and (x', ,v') int dom is defined to be (2) :0 - 22).
Notice that our notion of & is saddle function. slightly different from that in Shi al. (2017), but the Bregman divergence defined the same as Eq. (6) in Shi al. (2017) and Eq. (4.9) in Nesterov (2007).
25

---

Published as a conference paper at ICLR 2024
Mirror prox can also be viewed extra-step mirror descent. Most intuitively, by introducing intermediate variable 1/+1/2, 2, its procedure is as follows:
Vh((++1/2) = Vh(a,) - ng((())
24+1/2 arg min V =E2 ++1/2 (2)
Vh(z,) Vh(=(+1)
ng( 12+1
2++1 = arg min 4 (z). #EZ
And it can be represented with the proximal operator in Definition 6 as well. Following (Cohen et al., 2021), VI E [7]. 2t, #t+1/2 E 2,
1/41/2 2 = Prox & (ng(2+))
1++ Prox & (ng(#++1/2))-
Dual Extrapolation (Nesterov, 2007). As in dual averaging, dual extrapolation moves the updating sequence of mirror prox to the dual space. Slightly different from two-step dual averaging, dual extrapolation further initialize a fixed point in the primal space 2, and as presented in (Cohen et al., 2021), its procedure is follows: Vt E [T]. zts 2t41/2 E Z, we z",
2t Prox (wr)
2++1/ Prox s, (z1)(2))
Wi+1 = W. + ng 270(2++1/2)
The updating sequence presented above is equivalent that defined in the original paper (Nesterov, 2007), simply replacing the arg max with arg min, and the dual variables with its additive inverse in the dual space.
C.2 ADDITIONAL DEFINITIONS
In this subsection, we list additional definitions involved in the theoretical analysis in subsequent sections.
Definition 8 (Legendre function (Rockafellar, 1970)). A proper, convex, closed function h Rd > U {oc} is called a Legendre function or a function of Legendre-type if (a) h is strictly convex; (b) h is essentially smooth, namely h is differentiable 1:0 C int dom h converging to a boundary point of dom h as t > oc. sequence {
int dom h, and [[Vh(z)] + 0o for every
Definition (Convex Conjugate Legendre Fegendre-Feenhel 2004)). The convex conjugate of function h is defined as
Fenchel Transformation (Boyd & Vandenberghe,
h(s) sup (s. h(2)).
Definition 10 (Differentiability of the conjugate of strictly convex function (Chapter E, Theorem 4.1.1 in Hiriart-Umuty & Lemaréchal (2004))). For strictly convex function h, int dom h" # 2 and he is continuously differentiable on int dom h², with gradient defined as:
Vh (s) arg min (( ((-s, 2) h(2))
(5)
C.3 FORMAL ASSUMPTIONS AND REMARKS
In this subsection, we state the assumptions formally and provide additional remarks that may help in understanding the theoretical analysis.
Assumption (Assumptions on the objective function). For the composite saddle function 6(2)
far y) + (x) (b2()) 1/4 ΣM fm y) the (x) v/2(y), assume that
a. (Local Convexity of f) Vm [M], fm (x, y) is convex in and concave in y.
b. (Convexity of thn (2:) is convex x. and v/2(y) is convex in y-
26

---

Published as a conference paper at ICLR 2024
Assumption 2 (Assumptions the gradient operator). For f in the objective function, its gradient By the linearity of gradient operators, 9 M 2m Ims and we
V.J operator is given by -uf assume that
a. (Looaal Lipschitzness of g) Vm E [M. Im (m(2)) (= Vvlm((
L-Liscchitz:
(19m(z) (m))=)) -
b. (Local Unbiased Estimate and Bounded Variance) For any client m [M], the local gradient queried by some local random sample 5 is unbiased and also bounded in variance, i.e. Bglgm : 9m 9m (2" and
[e""l9m(="::0 9m 9m(="))12 s o²
(Bounnded Gradient) Vm [M].
SG
Assumption 3 (Assumption on the distance ceeteraeggenertting function). The distance-generrainng function h is Legendre function that 1-strongly convex, i..., Vx, V,
h(y) h(x) (Vh(x), y 2) ll 1
Assumption 4. The domain of the optimization problem compact terms of Bregman Diver- gence, i.e., V2, E Z, (z) s B. Remark 1. An immediate result of Assumption la that, Vz = (x, v), z' = (a',
J(z, v/) - [(x,,'') $ (V ,'),''''' xx), (xx,,) [( S v (1', "' y)-
Summing them up,
v²) S {,())),''') 2).
Em em Remark 2. For any sequence of i.id. random variables E0,0> em 1-2-- S1,1/2 em cm 10.1/22---
Sr/2+1/2'
lei Fr. denote the o-field generated by the set (ep. Vm [M] and ((j = r, S k) or (j
T, k E 1/2, 1/2..... 1, K 1/2}))}. Then any Sek is independent of Fr,2-1/2. and Assumption 2b implies
FF., [llgm Th (7TA)) Im 9mm(""1)l |F,A-1/22 5
Remark (Corollary 23.5.1. and Theorem 26.5. in Rockafellar (1970)). For a closed convex (not necessarily differentiable) function h, Oh is the inverse of Oh" in the sense of multi- mappings, Oh*(s) (s) if and only ifs E @h(()). Furthermore, if of Legendre-type, meaning it is essentially strictly convex and essentially smooth, then Öh yields well well-defined Vh that acts bijection, i.e., (Vh) -1 Vh"
i.e., = Oh"
Remark 4. Assumption and Remark 3 also trivially hold for & from Definition 7 in the saddle point setting, and eventually, the generalized distance sestance-genrattngg function & from Definition 3. Due to the strong convexity of &.. V is well-defined noted in Definition 10. Together with the potential non-smoothness of l,, Remark 3 implies that = - (s) if and only if E (2)
D ADDITIONAL TECHNICAL LEMMAS
In this section, we list some technical lemmas that are referenced the proofs of the main theorem and its helping lemmas.
Lemma (Jensen's 's inequality). For a convex function c(xx), variables 21, In in its domain, and positive weights 01,-.., On
Σ Ei axp((;;)
i=
<
Σn
Di=l
-==
and the inequality is reversed if ((x) is concave.
27

---

Published as a conference paper at ICLR 2024
Lemma 5 (Cauchy-Schiee Schwarz inequality (Strang, 2006)). For any and in an inner product space,
(x, v) < |
Lemma 6 (Young's inequality (Lemma 1.45. in Sofonea & Matei (2009))). Let p. q E be two conjugate exponents, that is 1 < p oo, and =. Then Va, b 2 0,
ab 1 a² 69
Lemma (AM-QM inequality). For any of positive integers En....
S
T2
(6)
1=1
i=1
Lemma 8 (Lemma 2.3 in Jiang & Mokhtari (2022)). Suppose Assumption I and hold, then
Vz = (z,y), 21..., 2T E 2 and 81...., 8r 2 with Σ O2 1, we have
T
O.31, v) - 6l0,, Σ Owwe S
0c((((z), 2) + (=+))) (=))],
in which vb(2) = 1/1 (3) + (b)))).
Proof. For (b)) = th1 (x) + (2)
((E,,0) ((x,81 ve) f(x,, v) (1(())) v2((1) (x, v1(()) + 3/2(1))
= f(x,,)) -f( + (x))) - +b22)
S (((())) - 2
((z)) +
r²(2)
where the inequality holds by convexity-concavityy of ((x, v), i.e. Remark 1. Then sum the inequality over = 1....," T,
T Σ
T
Σ
(rx Ocwe) <
[g(z)), = = + +(2)) - +b(=)]
Finally, by Jensen's 's inequality Lemma 4,
T
T
Σ (000. v) 2 0ezr, 8)
(xx 0.0 S <6(x, Σ 013/1
which completes the proof.
Lemma (Theorem 4.2.1 in Hiriart- Urruty & Lemaréchal (2004)). The conjugale of o-strongly fonexifunction is - smooohh. That is, for h that is strongly convex with modulus or > 0, Va,x',
(x) - (2)()')1 < - 1|2 -
Lemma 10 (Lemma Flammarion & Bach (2017)). Generalized Bregman divergence upper- bounds the Bregman divergence. That is, under Assumption and 3, Vz dom h. Vil e int dom hy where ht = + tmú,
Thl (x) 2 V.l(2))
in which x' (h²(1()).
28

---

Published as a conference paper at ICLR 2024
E COMPLETE ANALYSIS OF FEDUALEX FOR COMPOSITE SADDLE POINT PROBLEMS
We begin by reformulating the updating sequences with another pair of auxiliary dual variables. Expand the prox operator in Algorithm line 6 to 8 by Definition 4, and rewrite by the gradient of the conjugate function in Definition 10,
2, min (5,ck - 22 + (n,(2)) VE,, -.,A))
4//41/22 arg min (1r gm 9m (= - (T.)), + (x)+((2)) Vl (7,k)) gm
Sr,+11 kr Jm 1222
Define auxiliary dual variable witk = =5- Sy k. - It satisfies immediately that 2,,6 Ve (w"))) in which e the conjugate Lr, =( (n/* k)n v. And define w w/4+1/2 to be the dual image am of the intermediate variable *r,k+1/2 such that 2,, = V (w (T,++1/22) Then from the above updating sequence, we get an equivalent updating sequence for the auxiliary dual variables.
w 1,/+1/2 wiik 119m (Z7,ee Sr,k)
wr,++1
wi,k 119m ( 11/2 e 1r/2+1/2)
Now we analyze the following shadow sequences. Define
M
M
Wp,k
m Wrrks
em Dr.k
Im (2y,ki Sr.k)
M
M
m=1
then
1r,h+1122 Wy.k 9r,k.
(2)
Wr.4+ = Wr.h 11 1
(3)
In the meantime,
Zp VeE (wy,k)
2r,t+1/2 Ve (1/221122)
(4)
E. MAIN THEOREM AND PROOF
Theorem (Main). Under assumptions, the duality gap evaluated with the ergodic sequence generated by the intermediate steps of FeDualEx in Algorithm I is bounded by
R-1K-1
B Tp RK
20 M
E
Gap
Σ
Σ
2r,x+1122
2033
2
KGB
RK
Choosing step size 1f min
B
Bbbt
B²
32.
stoRint
R
K-1
31BB
20
5
B
Gap
Σ
2r,+1//2
]
S
RK +
RK
R MiRiKI
R
P=0 K=D
Proof. The proof of the main theorem relies on Lemma 1, the bound for the non-smooth term, and Lemma the bound for the smooth term. These two lemmas combined in Lemma and then yield the per-step progress for FeDualEx. The three lemmas are listed and proved right after this theorem. Here, finish proving the main theorem from the per-step progress.
29

---

Published as a conference paper at ICLR 2024
Starting from Lemma 3, telescope for all local updates & E {0, K 1} after the same
communication round
7 T
(o(Enitt1/2)) F 2) + (((=nk4172)) m(21]]
50 (1))
K-1
K-1
(x)
(x)
+ +0
Σ
+2
Σ
((7
1)GB*
M
k=0
50 (
K-1
K-1 +2
$ (x)
+ 20
Σ
B +
Σ
3ln R=
M
k=
< VVdr0(2) - Vlak Wr,K (2) 50 (
(0 +2
M
As we initialize the local dual updates on all clients after each communication with the dual average of the previous round's 's last update, Vr E {1.... R). the first variable in this round wp,0 is the same as the last variable w,-1,0 in the previous round. As result, taking the server step size 17" 1, can further telescope across all rounds and have
R-1K
17 E
2, 2) ((en)tii))) [1))]]
+ 200 (1 RG + (n
v (2)
M
Notice that the generalized Bregman divergence
Vla (z) V (2) V+(2)) V (z), where Wa.
(S). Thus, by Assumption 4, 12000 (2) B. Dividing of on both sides of the equation,
=o
we get
R 1
K-
11 B
z) + v (12
RK
P=0
K=U
B
22 KGB
170 RKK
M
Finally, applying Lemma completes the proof.
Lemma (Bounding the Regularization Term). V2,
of (1(2,)441/)) +x)] T (2) p (2) Vink Wr.tt
(2r,++1/2) C (2r, Wiih
+ Tf 0r,k+1/2 Kr.ki 4r/2
kp,k+i) + 1f (0r,k+1/2,
2,,2+1/2)
Proof. By the definition of generalized Bregman divergence and the updating sequence in Eq. (2),
Vz,
Dlanss (x) = (z) - fr, l (2r,,+1/2))) ( 2r,4+1/2)
= (r,x+1(2) - lr (27, (Wir - 9r,kr - 27/41122)
= -f,((2) - kr. 11/2) + 17 [x(()) [((2r10t112)
(wr, 2 1/2) + 17 (gr,k, - 2r,+1122)
Similarly, we can have for the updating sequence in Eq. (3) that Vz,
( (x. -an--eea ( + of (bb(2) w 1 (z))+
(Wrr x + 1/ gr.k+11/22 2r.41))
(8)
Plug = 2r,4ti into Eq. (7),
(2r,4+1) by A (2r,4+) (2,.61461122)) + 17 [eb (22.4+1122)
(Wyy Zn.4ii 2//41/22) + nr (gr. Zrk 2r,4+i/2)
30

---

Published as a conference paper at ICLR 2024
Add this up with Eq. (8),
p (2,,+1)
(,,((2) ( 1/2) (W0r, 2r, 1/22
11
+ 1 [b((2) (b( (
+ 77" (rrkkr 2r,t+1 2r,h 1/2) + +1 (r,,4+1/22 2r.++1)
A2
For A1 we have
A1 = (r,((z) lr, (Wnni Zr,i) - (.((Er(+1/2)) + (r.((znk) + ( 2r, k..i)
"nn Vant (2r,k+1/2)-
For A2 we have
A2 1/8 (Tr.k Rr, 2r,k+1/2) of 0r,k+1/2 2,, Fr,41/22
-r,k+1) + 1f (0r,+11/2 Arrk-1122
118 (Tr,k+1/2, 2r,k+1/2) + Tf (r,k+1/2 Dr,ki Fr,k+1/2 Zr,k+1
Plug Al and A2 back in completes the proof.
For the purpose of clarity, we demonstrate how we generate the terms to separately bounded for the smooth part with the following Lemma 2, which holds trivially by the linearity of the gradient operator g x Σm= Im and then direct cancellation.
Lemma (Bounding the Smooth Term). Vz,
M Σ m=1
(9( 2r,411/2 - 2) = 2r, 2) + M
Im ( (m (2/)11122) 9r,k+1/2, Fr 2r,
Σ
[9m (2r,++1/2)
Im gm (/ 2r,41122 2)
M
Based on the previous two lemmas, we arrive at the following lemma that bounds the per-step progress of FeDualEx.
Lemma 3 (Per-step Progress for FeDualEx in Saddle Point Setting). For of S 1
520'
of (g (2r,4+1/2) Fr, 2) + (2r,4+1/2) [=)]
Vlnn (2) wrik Wr, (x) (n) (0 + 1)202 +2
M
Proof. Based on the previous two lemmas, we can get the following simply by summing them up, in which we denote the left-hand side as LHS for simplicity.
LHS = (g( 2r, - 2) + 4b (r (1))]
((nn(22 (2) Wlantt
Writ ( (2r,0+11/2)
plnuti
(2,
Wr.t Wri
WrAti/s
+ 17" (gr,k+1/22
Tr.ki 2r,k+1/2 - Zr,k+1)
M
+ c
Im m x - Dr,k+1/2, 2r,k+1/22 2,, -2)
M
m=1
1
17
I9m (27,)41/2) 9m 9m 2r,,0+1/22 -2)
M
31

---

Published as a conference paper at ICLR 2024
For the two generalized Bregman divergence terms in A3, we bound them by Lemma 10 and the strong convexity of Remark 4,
A3 < V (2/)4+1/2)
V 2ri4+1/2
(2r,++1)
$ 2 2r, 2n,+1/211
1r, - 2r,++il
As result,
LHS & Vlnk(2) (2)
2 (2) - - 2n#+1/211
2 2r,,+1/2 Zn.tii 1|2 + of (1r8+1/2
Dr 2r,t+1/2 - kr,k+1)
A1
17"
1
Σ
9m 12 (2))4+1122) (10.222)99rr1111) 9r, 2r,t+1/2 -2)
M
M
7
Im (zr,)+1/2)
Im Im (= 2r,k+1/2 - z).
M
m==1
A4 can be bounded with Stuchy-Schwarr (Lemma 5) inequality and Young's 's inequality (Lemma 6).
A4 <
1//2+1/2
+ 1r 2n
1|,,,|+122,,++//2 En.+ill
2
1
(179)²
1 2 |2, 2r,t+il
||
1r,,+112
ž ||
gr,k+1/2 gr. +
2
)
1r,k+1122
3r
2
Then we have
(n
77 (6( (()) I (lbn
Eendet (2) - - - 2r,2-1/211 +
1r, - -9r,
2
M
+ (
Im (=m 1x,2+122) Dr.k+1/2 Fr,k+1/2 2)
M
m==1
of M
9ym (2r,6+1/22 Im (= 2 1/2 2).
Taking expectations on both sides we get
(((((rr.t+12))) <[))] < Vllntt)) (2) (2)
(1))2
E ||
2//2-1/21 12
E
[11 xr
2
122
+ E
Fm (=1k+1/22
-9,k+1/22 2r,411/2 =)]
M
m=
M Σ
+ "
E
Im 3 1122)
Im ( m
1/2)1 2r, =}]
M
m
B4
32

---

Published as a conference paper at ICLR 2024
B2 is bounded in Lemma 14. Therefore, we have
)
10o²
B1+ B2 v
+ +00 (1))
2
M
5
)
E
2r,,+112 - 2r.bil
B 21,4+1221
2
)
10
5(1)))32
+ 4033 +1)
||
2,,
2
M
50
(nf)
<
+
M
for rf S
52
B3 is after taking the expectation as shown in Lemma 11. B4 is bounded in Lemma 13. Plugging the bounds for B1 + B2, B3, and B4 back in completes the proof.
E.2 HELPING LEMMAS
In this section, we list the helping lemmas that were referenced in the proof of Lemma and 3. Lemma 11 (Unbiased Gradient Estimate). Under Assumption and 2,
M
Σ
gm gm( - 9r.k+1/2: 2r,11/2 - 2)] =
M
m==1
Proof. By the unbiased gradient estimate in Assumption 2b and its following Remark 2,
M
BF 1
Σ
Im 9m tm (Fn(2)+11/2))
Dr.+112: 2 2n,+1/2 2)}
m=1
M
= 1f E
By.,,
E E
Im 5m m (2/))+1/22) - 9r.k+122 Fr,k+1/2 - Fr,.
M
m=
O.
Lemma 12 (Bounded Client Drift under Assumption 2c), Vm E [M]. Vk E (o....,K 1-1, m
|| |
11,2+1/2 S 21 + 1)G
- x < kr
Proof. By the smoothness the conjugate of a strongly convex function, i.e., Lemma 9, ||2,,4+1/2 2,,4+1/21
V (w,,8 Vl (w
< 1,, - m 112+1
After the same round of communication, by the updating sequence, we have Vm E [M]:
with 1/2 = w 7 9m (2/ (7%))
Im (27,441/2 (7441/2) - 1f 9m (= STC
Immediately after each round of communication, all machines are synchronized, i.e., Vm,, m2 E [M]. with = w Therefore, Vk E {O...., K 1},
h-1 1 Im (2 12/21 5r,4+1/2) (2) 17 Im, (2 5m1))
w m2
m2 w
emy
1
1,/+1/22 =
+ 17
Jmg (m
(2,,441/21 (mi4112))) + 17" Jmng (2 k em1
e
2=0
33

---

Published as a conference paper at ICLR 2024
Then Vmn, my [M], vk E {O, K 1), by triangle inequality, Jensen's inequality, and the bounded gradient Assumption 2c,
k-1
|| W/2t1/22l+ S 1
Tme
Mm (2r,441/2 1
.m 1,221 |1+ + 119mi (27,61 e [|+
k-1
Σ
Imm 1,,441/225,,441122211 + 19mm (2 57,6 )l.))
t=
$ 21/ (h: + 1)G.
As result,
m Fr,k+1/2
.r,k+1/2 S Wr,t+1/2 wr,++1/211 ll
S sup || ,,+1/22 - 12 mi .
s 21/ (k + 1)G.
Similarly, we can show that
2r 27 S 21/ kG. kG
Lemma 13. Under Assumption 1-4,
M Σ
B
19m (27,6111))) - Im 9m (2n(2/41//22) 2T. 2)] 2 (() I)GBB
Proof. The proof of this lemma relies on the bounded client drift in Lemma 12. We start by splitting the inner product using Cauchy-Schward inequality in Lemma 5, and state the reference for the following derivation in the parenthesis.
M Amo (#r,k+1/2) - Im ( 2n,
17
E
Fn,+11/2 =)}
m=1
M
< E/
Igm (2r,4+1/2) - 9m (2 11ll==lllr.++//2 =II]
M
m=l
M
1
< M
E
11 (27,k+1/2) 9m (27 || =|]]
(Jensen's) 's)
m=1
1
En
8112,,41/2 - 2 - =1I]
(Smoothness)
M
S B
2,31 + +1)G||=,,R41/2 =
(Lemma 12)
M
m=1
22 < (*+
< (k 1)G
(Strong-convexity of è)
(Assumption
Lemma 14 (Difference of Gradient and Extra-gradient). Under Assumption 1-4,
10o2
gr,k+1/22 3r <
403² (n 12 + +,322 (
||, - 11]
M
34

---

Published as a conference paper at ICLR 2024
Proof. By Lemma 7,
E Exr 11 - 9r,
1 M
=B |m,41/22
Im (= (+,4411111))) 1/2)
M
m=
1
Im (2))))
gr.k
Im [gm( (1//)+1//2) Ii (+1))+1122)
M
M
M
M
Im (2(,k)
Im (2
Im (2r,k) 11: I9m (2r,++1/22
M
M
M
< 5
gr,k+1/2
Im (2 (2
+5B
Σ
Im Om(22 (277)) - gr.
M
M
m=1
m=1
C1
C2
M
+ 5 E
99m (1/2+1122 - Im 1/2])+
C3
M
1
+ 5 12
gm (Zr.k)
Im (=*t))]
+5
[9m (2r,
Im (Zr,k)
M
m=1
For C1, by Assumption 2b and its following Remark 2,
M
M Σ
C1 EF,,41//
9m ( 5/.
Im gm (=(2))+2))2)11
M
M
m=1
m=1
M
Br,
9m ( m
21/22 ( 1//)+1/22
9m (2
-1 /2) 11
M
m=1
Varz
Amm (=m 112 (2 Im ( (2
M2
m=1
VarF [10m( - 9m (2
(i.i.d)
M
M
E E
119m (37 - Im (3 1//
M m=1
M
Σ
E
EF
EF BA (/i+1/2)) 9m ( +/2/111 Frx]]
M2
m=1
M
Similarly, we have C2 < o²
3r.
For C3, by Lemma 7, f--mmoothness of fm. and finally Lemma 12, we have
M
C3
M
Im
m (1/2)11/2) - Im gm (2r,A+1/2))
M
m
3²
M
2r,41//212
M
241221/2
m=
4.32 (n
35

---

Published as a conference paper at ICLR 2024
Similarly for C4, have C4 - 43
For C5, by Lemma 7, B-smoothness fm from Assumption 2a, and finally Lemma 12,
C5 E
(9m(2),41/2)) 9m (3).
.22
M
1 E
11 (0m(2n4+172)) Im (2..)))12)
M
m=1
< B |
Plugging the bounds for Cl1, C2, C3, C4, and C55 back in completes the proof.
F COMPLETE ANALYSIS OF FEDUALEX FOR COMPOSITE CONVEX OPTIMIZATION
In this section, we reduce the problem composite convex optimization in the following form: min (xx) = f(x + (xx
ZEX
where f(x)
-m=1 (m) The analysis builds upon the strong-convexity of the distance- generating function in Assumption and the following of assumptions the convex optimization setting:
+ Em
Assumption 5. We make the following assumptions:
aCoovveeyyyy of f) Vm [M]. Jm is convex. That is, Vx, x' E Æ
- fmn(2)) S (fm (z) - x¹).
b. (Local Smoothness of f) vm E [M], fm is 3-smooth: Vx, E X, 8
fm(x) & fm((z) + (fm(x'), x²) + / 1| - 2'11.
c. (Convexity of 1) ((z) convex.
d. (Local Unbiased Estimate and Bounded Variance) For any client m E [M], the local gradient queried by some local random sample <t is unbiased and also bounded in variance, i.e., Ee 19 (x gTt) = 9m 9m(x"") (2r") and Bellig (Imi Em) - Im (I [|3] S o².
e. .Boounded Gradient) Vm [M). [1 Em)ll+ S.
Federated dual extrapolation for composite convex optimization is to replace the part of Algorithm highlighted in green with the following updating sequence, where we overuse now as the notation for dual variables in the convex setting as well.
$1,0 Sr
for k: = 0. ...., K - do
r, = Prox hr, (siTht)
Mrckt 2 1,,21/22 Prox 5-5
(n Im (1
S7 Sp n (x (4/121 S/
end for
For the proximal operator defined by by. reformulating from its Definition to VA in Definition 10 yields
A = arg min ( (s x,,) + hn,( = Vhi )/i
1//41/2 arg min (11 9m (x"")::
s,))).)) + h hr.++1())) Vhi s/h))) - 9m (2.) (7
S.41 Sitk + 9m (x. (1/2, (/2
36

---

Published as a conference paper at ICLR 2024
Similarly, we define auxiliary dual variable M9y = S, and 1 1/,+11/2 the dual image of am 72,+1/22 Then by definition, Tiy,k Vh (4T,) and xm 1/2211/2 2 (17)0-12)) The up-
dating sequence is equivalent to 11,k+112 = My 79m (#r, 57,k) followed by 17,,+1 = Pi
79 (on(("") (# r,,41122 Sr,4+1/2)- For the shadow sequence of averaged variables Mr,k = M 9r.k M Em= Im (2 S7,k
1 Em= Pr and
Pr,4+122 = Pr,k ?) Dr,k-
(10)
Mr,k+1 = Mrrk "I" 9r.++1/2-
(11)
and Finally, the projections of the averaged dual back the primal space are Fr,k Vhz,, (Tr,.))
1/, = Vhū (1r,2+1/2)
Theorem 2. Under Assumption the ergodic intermediate sequence generated by FeDualEx for composite convex objectives satisfies
K-1
B of RK
502 +28(1)8
[[O(
E
Σ
Σ
2r,441/2)
x(x)]
+ ()
RK r=0 A==
M
Choosing step size
B
B
B$
52 3 52oR
2
further yields the following convergence rale:
R-1K-1 RK
5 BB
BB
d M
2,,41/2) b(x) S
RK
KiR
R
Proof. As the proof for Theorem 1, the proof for this theorem depends Lemma 15 and Lemma 16, which further yield Lemma 17. These lemmas are presented and proved right after this theorem. Here, start from Lemma 17. Telescoping over all {o,..., K 1} and all E {0,.... R 1)
assuming 17" = yields
R K
V (x) 50 3 )
B E
ol (lz - RK [x)()) S hooo ( (x) PR.
M
+ 203 (17)) 3 RG + 23(17))3 RG
By Assumption 4, (x) (x) VA (x) < B, where (S). Dividing both sides by KR followed by applying Jensen's inequality (Lemma 4) completes the proof.
Lemma 15 (Bounding the Regularization Term). Va, v/ (117))411)))) (xx)] hh (x) p..
Fyhnees (x) Vyhne "oin
(114,411/2) Dr.k. TT..
Phnness (Fr,tii) 1r.4t172
+ 17 (Jr.441/2
Fr, + (Frk41/22 2r/+11/2)
Proof. The proof of this Lemma is almost identical to the proof of Lemma with a mere change of variables and eestance-generating function from saddle point setting to convex setting.
The following Lemma highlights the primary difference in the analysis of convex optimization and saddle point optimization. The smoothness of fm provides an alternative presentation gradient Lipschitzness that establishes the connection between 2, 1122 the primal projection of averaged dual on the central server, and x 77,k-1/2 on each client.
Lemma 16 (Bounding the Smooth Term). Vx.
M Σ
[(T - f(x) S (0r,k+1/2 2r,k112 x))
Im (m(7//1112)) - 9r.k-1/2- fr,k+1/2
M Σ
|rrk+1/2
2
m
2M
m=l
37

---

Published as a conference paper at ICLR 2024
Proof. By the smoothness fm in the form of Assumption 5b and then the convexity of fm in the form of Assumption Sa,
3
fm fm(4r/41/22 & fm (1127)41/2) + (gm (o Fr,4+1/2
1//2 +
xm
|
t 2r,++1/2
3
(m(=))41/2) + (9m 11/2) 2 1r,.1112
mm 11/2/ +
1r,,+11/2
17,++1/21
fm( (2 + 4m (z ,
2 21,+1122 -2)
m (2 1r2+1/2 x) + fm(2) + (gm
1
*r,+1 112
mm
Then for function f 1 M Em=1 sm
M
M - -(()) S (fm(01R41/2) [mm())]
M
m==1
1
3
Jm k-122-11/2)) fr,2,/ (1) x) +
1r,k+1/2 - -2,++1/211
M
2
M
3r 0r Fe Tr. 1/2 xx)
Im (x 11/22
1r.k+1/2 1r,
M
Fr,+1122 1/2 -
2r m
2M
m==1
Now we ready present the main lemma that combines Lemma 15 and Lemma 16. For the proof, we utilize again Lemma 11, Lemma 12, and Lemma 14, all of which we claim to hold trivially in the composite convex optimization setting.
Lemma 17 (Main Lemma for FeDualEx in Composite Convex Optimization). Under Assumption
2 + 1033 + 2k + 1)G²
of ((x)] S Pihn (I) - Dihntt (x) Mr,l-1
+ M
(72
2M (1 170) -28
Proof. Summing the results Lemma 15 and Lemma 16:
of (6(2.,411/2) -(xx)) < Vohn (x) PR
(x:) Dohnn (zr,
Fr.k-1/2 (2r.411)
M
11 (gr,411/2 Grike, 2r,41122 Ir.k+1) +
1rr
2M
17
Σ
(m( 2r. x).
38

---

Published as a conference paper at ICLR 2024
For the latter two generalized Bregman divergence terms -iiie bound them by Lemma 10 and the strong convexity of h in Assumption As a result,
Mrie (2r,2+1/22)
ahan+1
Praa-1/2 (Tr, 1),
of (0(E,,+11/2) - v(x)) z Vhink
(x)
(x)
Tr.k 1r,41//21
bink- - Fnati of ThA+1/2 Drk Fr,+1/22 Fr.++1)
11
Im (x
(TTx+1122 1 x)
M
M
7"3 3
| -x 1//11/211
2M
m=1
A can be bounded with Sauuchy-Schwarc inequality (Lemma 5) and Young's inequality (Lemma 6).
AS
Tr,+1//2 Fr,++1l 2 +
9r. 1 1/,,211
Tr,t+1l
(17²)
$ |2n,+1/22 Er,ttil 2|
19nk+1/2 - gn + || - Fr,k+ill
2
)
119,,+1/2 - -
Taking expectations on both sides we get
7(((0(z))+11/2) p(x)] z iohn (I) - Thhntt (x)
Pr.t-T
(n)1)
E [1 Tr,4+//21|
-E[lgr 1r. - gr,bil?]
EE
2
B1
B22
E
Σ
Im (m(
-r, Fr, 1T)
M
B3
3
E 11,
A 1/2
2M
B2 is bounded in Lemma 14. Therefore, for 17 1 53.
B1 B2 (n)) 2033 (T)
M
B3 is zero after taking the expectation by Lemma 11. B4 is bounded in Lemma 12. Plugging the bounds for B1 + B2, B3, and B4 back in completes the proof.
G FEDUALEX IN OTHER SETTINGS
In this section, we provide the algorithm along with the convergence rate for sequential versions of FeDualEx. The proofs in this section rely only on the Lipschitzness of the gradient operator. As a result, the analysis applies both composite saddle point optimization and composite convex optimization.
G.1 STOCHASTIC DUAL EXTRAPOLATION FOR COMPOSITE SADDLE POINT OPTIMIZATION
The sequential version of FeDualEx immediately yields Algorithm 3, stochastic dual extrapolation for Composite SPP. This algorithm generalizes dual extrapolation both composite and smooth
39

---

Published as a conference paper at ICLR 2024
Algorithm 3 STROCUASTTICDDUALLDKRRAAAAAAAAA
for Composite SPP
Input: ((z) = f(r,)) + + (1(2) - 1/2 (v): objective function; {(z): distance- Destance-generating function; gradient operator.
g(z) (V.f(z,)) vv, (z,
Hyperparameters: T: number of iterations; 1/. step size.
Dual Initialization: = O: initial dual variable, < S: fixed point in the dual space. Output: Approximate solution & = (z, y) to m max Φ(z y)
for / 0.1,...,
do
2 = Prox f1 (5t)
Two-step evaluation of the generalized proximal operator
& R++1/2 Prox c-c (ff((z()))
St+1
+ 1f 0/0(441//255541)/)
Dual variable update
end for
Return: T -t= 1/21/2-
1 T-1
stochastic saddle point optimization with the latter taking (b)) O. Its convergence rate is analyzed the following theorem, which to the best of our knowledge, is the first one for stochastic composite saddle point optimization.
Theorem 3. Under the sequential version of Assumption 1-4, namely with M 1, Vz 2, the ergodic intermediate sequence generated by Algorithm 3 satisfies
T-1 Σ t=
Gap T
10-1 v 1/T
+ 30
Choosing step size
B
7 min
323 3
further yields the following convergence rate:
T
3t3B 3
E Gap(
Σ 21+1/2)] s
+
T
Proof. By proof similar Lemma 1, we have
7[b(2411/2) [z)] (2) Vlli (2) V (2441/2) #441/2
Vlet1 (2141)
wit1
7/(41122 - Ir, 2011/2 -241) + +// - 2411/2)
v (2) 12)
1 2
2 |: #1+1/211
11 21+1l1 n19141/22 9t, F141/2 21+1)
(((((411/2) - 92+1/2 2+11/2 - 2) 2141/2 2).
B
where the inequality holds by Lemma 10 and the strong convexity in Remark 4, and then simply expanding the last term to build connection between the stochastic gradient and true gradient. By
40

---

Published as a conference paper at ICLR 2024
Algorithm 4 CCMPPOSTEE-DIUL-DXXAAPLLLTT
Input: (x2) = (r. (2) - 4/2 (v): objective function; {(2): distance- generratng function; g(z) (). (z, v)): gradient operator.
Hyperparameters: T: number of iterations; 7y: step size.
Dual Initialization: So = O: initial dual variable, < S: fixed point in the dual space.
Output: Approximate solution & = (z, y) to minzex maxyey ((z y)
for t 0.1,..., - do
2/ = Prox f1 (5)
Two-step evaluation of the generalized proximal operator
& 1/2 Prox
- 17 c-c (f()(z))
St+1
(2++1/2)
Dual variable update
end for Return: T Et= 1/21/2-
1
T-1
Cauchy- Sarchy-Shhwazzaee inequality (Lemma 5), Young's inequality (Lemma 6), and Lemma 7,
n² 2
19411/2 gell + 1 |l -=+1ll2
A <
1| 2111/211
#141/2
=+1112
11²
1
2+1/2112
I199+1122 9(2++122) [g(()) - sil +1((24122) s(2))]11
2
37/²
<
2 - 2++1/2|1
(19(2+112) - -(22)]12
2
3n²
3n
19t+1/2 - - 1/2)+1
(19(2)) -l
2
377² g2
|| - 2/11/211 3n2²
37/ (lg((z)) - gr 11:
||9+1/2 0(=1-122)1
2
where the last inequality holds by the B-Lipschitzness of the gradient operator. After taking expec- tations, the last two terms are bounded by the variance of the gradient σ², and B becomes zero by proof similar to Lemma 11. Therefore, for S V38
1/B (a(24422))) F+t1/2 - 2) + (((+11/2 - (>)] < (2)
West (#)++)
Telescoping over all {O...., T 1} and dividing both sides by r/f' completes the proof.
G.2 DETERMINISTIC DUAL EXTRAPOLATION FOR COMPOSITE SADDLE POINT OPTIMIZATION
Further removing the data-dependent noise the gradient, we present the deterministic sequential version of FeDualEEx which still generalizes Nesterov's 's dual extrapolation (Nesterov, 2007) to composite saddle point optimization. As result, we term this algorithm composite dual extrapolation, as presented in Algorithm 4.
We also provide convergence analysis, which shows that composite dual extrapolation achieves the ((+) convergence rate as its original non-composite smooth version (Nesterov, 2007), as well as composite mirror prox (CoMP) (He et al., 2015). We do so with a very simple proof based on the recently proposed notion of relative Lipschitzness (Cohen et al., 2021). We start by introducing the definition of relative Lipschitzness and a relevant lemma.
Definition 11 (Relative Lipschitzness (Definition in Cohen al. (2021))). For convex distance- generating function h: Z + R. we call operator Z + Z" X-relatively Lipschitz with respect to if Vz, w, u Z.
(g(w) g(z), w- u) S X(V (w) + (b))..
Lemma 18 (Lemma I in Cohen al. (2021)). If g is B-Lipschitz and h is a-strongly convex, is B --relaiively Lipschitz with respect to h.
Theorem 4. Under the basic convexity assumption and [--Lipchitzness of Vz 2 and nj B.
composite dual extrapolation satisfies Gap(+ Σt- F(41/2) ap.
41

---

Published as a conference paper at ICLR 2024
Proof. By proof similar to Lemma 1, we have
(2441/22 (b))]
Vd: (z) Vitt1 (2) Vi (2++1/2) Vica (2
(2++1)
wi+1
wi11/2
+ +1(((=0-1/2) - g(zx), 7t+1/2 - #+41) ) + ((9(2++122) z411/2).
By Lemma 18, we know that g is B-relatively Lipschitz with respect under the g-Lipschitzness assumption of g and 1-strong convexity assumption of L. Then by Definition 11, we have
n ( - +x(2 + (9(2++1/2) 12+1/2 -2]]
Wi (z) (=) (F+41122))
V/++1 (Zt+1) (g(= ((2x), F441/2 2+11) We+1/2
Vil (2) (1)t(() (2((1/))2)
Walll/2 (2++1) 17 V (2441/2) + Va (=+1))
(=()) (++t(()).
where the last inequality holds for S 3 by Lemma 10. Telescoping over all / E {o,..., T. 1} and dividing both sides by r/L' completes the proof.
H FEDERATED MIRROR PROX
We present Federated Mirror Prox (FedMiP) here in Algorithm 2 as baseline. The part highlighted in green resembles the mirror prox algorithm introduced in Section C.1.2. We use the composite mirror map representation introduced in Section C.I.1 to avoid confusion, as the composite proximal operator we proposed for FeDualEEx is slightly different from that used in composite mirror descent as discussed in Section 4.1.
Algorithm 2 FEDERATED MIRIEERD---RRRRR-OOOOROOR (FedMiP) for Composite SPP
Input: 6(2) fz, v) v1(x) (v M Σ Em= fm(-) th (z) (y): objective function;
{(=): distaacc-generaating function; 9m (=) = (x, -V vy (æ, y)): gradient operator.
Hyperparameters: R: number of rounds of communication; K: number of local update iterations;
ry: server step size; vf:: client step size.
Primal Initialization: zo initial primal variable.
Output: Approximate solution = = (z, y) to min maxzey Φ(I, y)
for 0, 1..... R do
2: Sample subset of clients C, S [M]
3: for m E C, parallel do
4: 2r,0
5:
for 1: 0, 1, ..... 1 do
6:
*r,+1122 V(L (()) :f (x)
7:
2,,+11 (el (Vb()(( 7/ 9( (7,))))2)
8: end for
9: end parallel for
10: A, = |c. Emec. (2,,, 2 A.))
11: 2r+1 Vf
12: end for
13: Return: RK
RR-1 K-1 kk= 2r.2+1/2.
42


Reviews:
[{"review_id": "HkI88EUg2U", "reviewer": "Reviewer_jzbD", "summary": "In this paper, the authors propose an Algorithm FeDualEx for solving composite saddle point problems under distributed settings. The proposed algorithm is inspired from the dual extrapolation algorithm while using a proximal operator which they define using the generalized Bregman divergence defined for saddle functions. They analyze this algorithm under homogeneous settings and derive its convergence rate for the duality gap. They also study the special cases when the number of clients equals 1, where the convergence rate of FeDualEx matches the existing rates known in the literature. The study also demonstrates that solving using the dual extrapolation has advantages of learning better sparse solutions than solving the primal.", "questions": "Questions / Comments\nIs it possible to have a similar algorithm only using the generalized bregman divergence on x ? \nSome discussion on the relation between the variables z=(x,y) and ς would help since the former already includes a primal and dual pair. \n\nTo improve the clarity, one may include convexity assumptions of the functions involved while the main problem is defined in (1).", "limitations": "", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "The paper studies federated learning of composite saddle point problems, for which there does not seem to be much existing work. The proposed convergence rates. \n\n(Novelty) The paper proposes a new bregman divergence for saddle functions and its associated proximal operator, which are used in the dual extrapolation steps. \n\n(Clarity) The main results are presented well and contrasted to the related ones. The experimental results illustrate the benefit of solving using the federated dual extrapolation over methods such as Federated Mirror Prox. The comparison to the sequential algorithms also help to position the contributions in relation to the existing work.", "weaknesses": "The algorithm is similar that of Federated Dual Averaging (Yuan et.al.) while incorporating the dual extrapolation strategy over the newly defined Bregmen divergence and the proximal operators. The challenges associated with adapting the above strategy over FeDualAvg doesn't seem to be conveyed well in the paper. \n\nFrom the motivations perspective, some examples of practical setups which required distributed learning of saddle point formulations would be useful in appreciating the contributions better.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "X5gtResnBe", "reviewer": "Reviewer_rzX1", "summary": "In this paper, the authors study composite saddle-point problems in a Federated learning setup. They propose distributed gradient methods with local updates, which they call Federated Dual Extrapolation. They provide convergence analysis and communication complexity in the homogeneous case.", "questions": "1. In section 4, it is unclear how you define $\\ell_{r,k}$. Could you add an exact expression for it from the appendix to the main part? \n\nSmall typos:\n1. on the bottom of page 5 in the second argmin the bracket is missed. \n2. In definition 4, $t\\eta$ is missed in the formula for subgradient.", "limitations": "", "rating": 5, "confidence": 4, "soundness": 2, "presentation": 2, "contribution": 3, "strengths": "The authors propose a new method, for which they provide convergence analysis. This method has their own interest.", "weaknesses": "Table 1 presents the previous and current results strangely:\n1) First of all, to compare the obtained complexity for the proposed method with the previous result in a strongly-convex concave case, it should be used standard regularization trick.\n2) From my point of you, when complexity contains several terms, each of them should be added. \n\nAbout Table 2, The authors claim that \"The sequential version of FeDualEx leads to the stochastic dual extrapolation for CO and yields, to our knowledge, the first convergence rate for the stochastic optimization of composite SPP in non-Euclidean settings .\" It is not true, there is a wide field related to operator splitting in deterministic and stochastic cases. Look at this paper please https://epubs.siam.org/doi/epdf/10.1137/20M1381678. \n\nAlso, compared to the previous works, the authors use bounded stochastic gradient assumption and homogeneity of data. In many federated learning papers, those assumptions are avoided. Despite that the authors write \"Assumption e is a standard assumption\", it would be better to provide analysis without it to have more generality. \n\nIn Theorem 1, and Theorem 2, the final result contains mistakes in complexity, because some of them were done in the proof. \nThe first mistake is made in theorem 3 and repeats in the main theorem. Please look at the last inequality on page 40:\nTo make $3\\eta^2\\beta^2 -1 \\leq 0$, the stepsize should be chosen in the following way: $\\eta \\leq \\frac{1}{\\sqrt{3}\\beta}$. This will change the complexity of the methods. The same was done in the proof of Theorems 1, and 2. Please see Lemma 3, 17.\n\nThe second mistake is made in the proof of Lemma 13, in the last two inequalities, where should be $\\dots\\sqrt{2V^l_z(\\cdot)} \\leq \\dots \\sqrt{B}$. This thing also will change the final complexity.\n\nThe appendix is hard to read in terms of the order of Lemmas. I think it would be better if the numeration of Lemmas had a strict order (for example, after Lemma 5 lemma 6 follows.)\n\nOther things dealing with weaknesses, please, see in questions.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "SFM4lBhT4b", "reviewer": "Reviewer_geTM", "summary": "The paper proposes FeDualEx a federated primal-dual algorithm for solving distributed composite saddle point problems. The authors consider a homogeneous setting and provide convergence guarantees achieved by FeDualEx when the objective function is convex-concave. The authors also evaluate the proposed algorithm experimentally on synthetic and real datasets.", "questions": "See the weaknesses section above.", "limitations": "", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "Overall. the paper is well written with the ideas clearly explained. The proposed algorithm is well-motivated and backed by strong theoretical guarantees. The experiments show the effectiveness of the proposed approach.", "weaknesses": "- The authors have missed an important reference [R1] which considers a nonconvex composite optimization and develops Douglas-Rachford Splitting Algorithms for solving the problem. \n\n- The authors should also discuss [R2] and [R3] which consider a non-convex composite problem but in a decentralized setting and without local updates. Also, in contrast to the duality-based approach taken by the authors, the works [R2] and [R3] propose primal algorithms that directly update the parameters using proximal stochastic gradient descent. The dual approach proposed by the authors is justified by the \"curse of primal averaging\". A question I have is why the algorithms [R2] and [R3] seem to work even though they are primal algorithms.\n\n- Why are the guarantees presented in the paper independent of the number of clients? The effect of the number of clients should be discussed after the main results. Importantly, does the proposed algorithm achieve linear speed-up with the number of clients in the network?\n\n- In the initial part of the paper the authors refer to the distance-generating function to be strictly convex but later it is assumed to be strongly convex. It is advisable to call it strongly convex from the beginning. \n\n- Define $h_1$, $h_2$ in Definition 3. \n\n- After Definition 3, the authors mention that the previous approaches that add the composite term to the Bregman\ndivergence may not work for dual extrapolation as certain parts of the analysis break down. Can the authors be more specific about what they mean here?\n\n[R1] Dinh et al., FedDR – Randomized Douglas-Rachford Splitting Algorithms for Nonconvex Federated Composite Optimization, 2021(https://arxiv.org/pdf/2103.03452.pdf)\n\n[R2] Yan et al., Compressed Decentralized Proximal Stochastic Gradient Method for Nonconvex Composite Problems with Heterogeneous Data, 2023 (https://arxiv.org/pdf/2302.14252.pdf)\n\n[R3] Xiao et al., A One-Sample Decentralized Proximal Algorithm for Non-Convex Stochastic Composite Optimization, 2023 (https://arxiv.org/pdf/2302.09766.pdf)", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (poster)