Federated Learning with Convex Global and Local Constraints
Authors: Chuan He
Le Peng
Ju Sun
Venue: Accepted by TMLR ()

Abstract: In practice, many machine learning (ML) problems come with constraints, and their applied domains involve distributed sensitive data that cannot be shared with others, e.g., in healthcare. Collaborative learning in such practical scenarios entails federated learning (FL) for ML problems with constraints, or FL with constraints for short. Despite the extensive developments of FL techniques in recent years, these techniques only deal with unconstrained FL problems or FL problems with simple constraints that are amenable to easy  projections. There is little work dealing with FL problems with general constraints. To fill this gap, we take the first step toward building an algorithmic framework for solving FL problems with general constraints. In particular, we propose a new FL algorithm for constrained ML problems based on the proximal augmented Lagrangian (AL) method. %The subproblems of our proposed algorithm are solved by an inexact alternating direction method of multipliers (ADMM). Assuming convex objective and convex constraints plus other mild conditions, we establish the worst-case complexity of the proposed algorithm. Our numerical experiments show the effectiveness of our algorithm in performing Neyman-Pearson classification and fairness-aware learning with nonconvex constraints, in an FL setting.

Published in Transactions on Machine Learning Research (05/2024)
Federated Learning with Convex Global and Local Con straints
Chuan He Deportment of Computer Science and Engineering, University of Minnesota
he000233 edu
Le Peng Department of Computer Science and Engineering, University of Minnesota
peng0347 edu
Ju Sun
jusun Grmm edu
Department of Computer Science and Engineering, University of Minnesota
Reviewed on OpenReview: https: // openreview. porm? id= qItaVblyfe
Abstract
In practice, many machine learning (ML) problems come with constraints, and their applied domains involve distributed sensitive data that cannot be shared with others, e.g, in health- care. Collaborative learning in such practical scenarios entails federated learning (FL) for ML problems with constraints, or FL with constraints for short. Despite the extensive de- velopments FL techniques in recent years, these techniques only deal with unconstrained FI. problems FL. problems with simple constraints that are amenable to easy projections. There is little work dealing with FL problems with general constraints. To fill this gap, we take the first step toward building algorithmic framework for solving FL problems with general constraints. In particular, we propose new FL algorithm for constrained ML problems based on the proximal augmented Lagrangian (AL) method. Assuming convex objective and convex constraints plus other mild conditions, we establish the worst-case complexity of the proposed algorithm. Our numerical experiments show the effectiveness of our algorithm in performing Neyman- Pearson classification and fairness- aware learning with nonconvex constraints, in FL setting.
1 Introduction
Federated learning (FI.) has emerged as prominent distributed machine learning (ML) paradigm that respects data privacy by design and has found extensive applications in diverse domains (Kairouz et al., 2021). In FL, ML models are trained without centralized training data: local clients hold their local data and never directly share them with other clients or the central server. Given global ML model train, typical FL strategies consist of repeated local computation and central aggregation: in cach round, cach local client performs local computation of quantities of interest (e.g,, local model parameters derivatives) based on the local data, and then the central server collects and aggregates the local results and updates the parameters of the global ML model. Since the shared local results are usually highly nonlinear functions of local data, making reverse engineering of local data unlikely, data privacy is naturally protected.
1.1 Federated learning for constrained machine learning problems
However, existing FL techniques are developed almost exclusively for unconstrained ML problems or, al best, for ML problems with simple constraints that are amenable to easy projections, despite the growing list of MI problems with general constraints- properties, e.g., robustness evaluation (Goodfellow al., 2014), fairness-aware learning (Agarwal et al., 2018), learning with imbalanced data (Saito & Rehmsmeier, 2015), neural architecture search (Zoph et al.,
constraints typically encode prior knowledge and desired

---

Published in Transactions on Machine Learning Research (05/2024)
2018), topology optimization (Christensen & Klarbring, 2008), Physics-informed machine learning (McClenny & Braga-Neto, 2020). Here, we sketch two quick examples.
Neyman-Pearson classification, or optimizing the false-positive rate with controlled false- negative rate Conventional binary classification assumes equal importance in both classes, so predictive errors in both classes are counted equally. In numerous applications, such as medical diagnosis, misclassifying one class (i.e., the priority class) is much more costly than misclassifying the other. The Neyman- Pearson classification framework addresses this asymmetry misclassification cost by explicitly controlling the error rate in the priority class while optimizing that in the other (Tong et al., 2016; Scott, 2007; Rigollet & Tong, 2011; Tong et al., 2018):
ng Σ
1 R1
min nO
2.0)
s.t.
71 Σ
(fo. rr,
(1)
where Jo is the trainable binary classifier parameterized by 0, to is the loss function serving as a proxy to he and { are the training data from class 0 and 1, respectively, The constraint imposes an upper bound on the error rate for class 1.
classification error, and {2,o)=1
Fairness-aware learning Typical ML models are known to have biases toward the majority subgroups of the input space (Agarwal et al., 2018; Celis et al., 2019; Mchrabi et al., 2021). For example, discase diagnostic model that is trained on a male-dominant dataset tends to predict much more accurately on the male subgroup than on the female subgroup. To counteract such potential model biases, a natural way enforee fairness constraints to ensure that the performance of the model on different subgroups is comparable (Agarwal et al., 2018; Celis et al., 2019; Mchrabi et al., 2021). A possible formulation for two-subgroup problems is
min 0 n
z() s.t. -85 Sal iESo
1
Σ
((forz))
1 Σ ((for 6 S
(2)
IES
where fo is the ML model parameterized by 0, {2i} is the training set, and oo is the proxy loss function, similar to the setup in Eq. (1). With Sp and S denoting the two subgroups of interest, the constraint imposes that the performance disparity of fo on So and Si should not be larger than 8 > which is usually set close to 0.
Both examples are particularly relevant to biomedical problems, where class imbalance and subgroup imbal- ance are prevalent. Morcover, there are strict regulations on the distribution and contralization of biomedical data for research, e.g., the famous Health Insurance Portability and Accountability Act (HIPAA) protection of patient privacy (OCR, 2023). Together, these underscore the importance of developing FL techniques for constrained ML problems, which is largely lacking: FL problems with only simple constraints that are amenable to casy projections have been considered in Yuan et al. (2021); Tran Dinh et al. (2021), and a small number of papers have tried to mitigale class imbalance (Shen et. al., 2021) and improve model fairness (Du et al., 2021; Chu et al., 2021; Gálvez et al., 2021) through constrained optimization in FL settings. However, those developments are specialized to their particular use cases and lack computational guarantecs for the feasibility and optimality of their solutions.
In this poper, we take the first step toward a general and rigorous FL framework for general constrained ML problems. Consider the constrained ML problems in Eqs. (1) and (2) in an FL setting with local clients, where the ith client holds local data Z; and so the whole training set is the union Z1 U... U...UZZ Zn. Since the objectives and constraints in Eqs. (1) and (2) are in the finite-sum form, both examples are special cases of the following finite-sum constrained optimization problem:
f1(0; 2.) + m0O s.t. Σ (0; Z.) < O.
min
(3)
local data coupled
2

---

Published in Transactions on Machine Learning Research (05/2024)
Note that inside the constraint, the local data are coupled which necessarily lead to communication between the local clients and the central server to allow the evaluation of the constraint function. To try to reduce such communication so that we can have more flexibility in algorithm design, we introduce decoupling variables { leading to an oquivalent formulation:
Σ f:10; 2.) + h(0)
n
min 0,8L
8 S
(0;;2,) 1sisn.
(4)
local data decoupled
no local data
which decouples the local data into local constraints. In this paper, consider the following setup for FL with global and local constraints, strict generalization of Eq. (4):
min Σ Jilw; 2.) + +Mwu) s.t.
co(w; 20) 00 c;(w; 2,) 0, Isisn.
(5)
global constraint
local constraints
In contrast to unconstrained FL or FL with simple constraints amenable to easy projections studied in existing literature, our focus lies on general convex constraints, where projections may or may not be easy to compute. Here, we assume n local clients, each with a local objective Ji(w; Z4) and a set of local constraints a(w; 2,) S (i.e., scalar constraints are vectorized) for i = I,...,n.. n. To stress the FL setting, we spell out the dependency of these local objectives and local constraints on the local data Zí's: these Z, are only accessible to their respective local clients and should never be shared with other local clients the central server. Henceforth, flexibility in modeling, we also include the global constraint co cow Zo) 0, with central data Zo that is only accessible by the central server. To facilitate the theoretical study of the algorithm that we develop, we further assume that all objective and scalar constraint functions are convex, but we also verify the applicability of our FL algorithm to classification problems with nonconvex fairness constraints in Section 5.2. To summarize, our standing assumptions on lop Eq. (5) include
omit. Z,'s in local objectives and constraints when no confusion arises. To allow
A Assumption 0. We make the following assumplion Uhroughoul this poper:
(a) The objective functions fi R2 + R, 1 isis n, and the m, scalar constraint functions inside G; : IRd R". 0 S S nt, are convex and continuuusly differentiable, and : Bd + (-o0, oo] is a simple closed conver function.
(b) For each 1 i n, only the local objective fa and local constraind 6 have access to the local data Za, which are never shared with other local clients and the central server. Only the central server has access to the global data Zo.
1.2 Our contributions
This paper tackles Eq. (5) by adopting the sequential penalization approach, which involves solving sequence of unconstrained subproblems that combine the objective function with penalization of constraint violations. In particular, we propose an FL algorithm based on the proximal augmented Lagrangian (AL) method developed in Lu & Zhou (2023). In each iteration, the unconstrained subproblem is solved by an inexact solver based on the alternating direction method of multipliers (ADMM) in a federated manner. We study the worst-case complexity of the proposed algorithm assuming locally Lipschitz continuous gradicnts. Our main contributions are highlighted below.
We propose an FL algorithm (Algorithm 1) for solving Eq. (5) based on the proximal AL method. To the best of our knowledge, the proposed algorithm is the first in solving general constrained ML problems in an FL setting. Assuming locally Lipschitz continuous gradients and other mild conditions, we establish its worst-case complexity to find an approximate optimal solution of Eq. (5). The complexity results are entirely new the literature.
We propose an ADMM basod inexact solver in Algorithm solve the unconstrained subproblems arising in Algorithm 1. We equip this inexact solver with newly introduced verifiable termination criterion and
3

---

Published in Transactions on Machine Learning Research (05/2024)
establish its global linear convergence for solving the subproblems of Algorithm 1; these subproblems are strongly convex and have locally Lipschitz continuous gradients.
We perform numerical experiments to compare our proposed FL algorithm (Algorithm 1) with the central- ized proximal AL method (Algorithm 3) on binary Neyman-Pearson classification and classification with nonconvex fairness constraints using real-world datasets (Section 5). Our numerical results demonstrate that our FL algorithm can achieve solution quality comparable to that of the centralized proximal AL method.
1.3 Related work
FL algorithms for unconstrained optimization FL has emerged as a cornerstone for learning since Google's seminal work (MeMahan et al., 2017), and has found applications in numerous domains where the protection of data privacy precludes centralized learning, including healthcare (Rieke et al., 2020; Peng et al., 2023a;b), finance (Long et al., 2020), Internet of things (Mills al., 2019), and transportation Liu al. (2020). FedAvg (MeMahan et al., 2017) is the first and also the most popular FL algorithm to date. After FodAvg, numerous FL algorithms have been proposed to improve performance and address practical issues, such as data heterogeneity (Karimireddy et al., 2020; Li et al., 2021e; Zhang el al., 2021), system beterogeneity (Li et al., 2020; Wang et al., 2020; Gong et al., 2022), fairness (Li et al., 2021b), communication efficiency (Sattler et al., 2019; Konečný et al., 2016; Mishchenko et al., 2022), convergence (Pathak & Wainwright, 2020), handling simple constraints (Yuan et al., 2021; Tran Dinh et al., 2021), incentives (Travadi et al., 2023), and hyperparameter tuning (Yao et al., 2024). Since our FL algorithm relies on applying an inexact ADMM (Algorithm 2) to solve subproblems, it is also worth mentioning that ADMM-based algorithms have been proposed to handle FL problems (Zhou & Li, 2023; Gong et al., 2022; Zhang et al., 2021) and optimization problems with many constraints in a distributed manner (Giesen & Lane, 2019). More FL algorithms and their applications can be found in the survey (Li et al., 2021a). Despite the intensive research on FL, existing algorithms focus primarily on unconstrained ML problems, versus constrained ML problems considered in this paper.
Centralized algorithms for constrained optimization Recent decades have seen fruitful algorithm developments for centralized constrained optimization in numerical optimization. In particular, there has been a rich literature on AL methods for solving convex constrained optimization problems (Aybat & Iyengar, 2013; Necoara et al., 2019; Patrascu et al., 2017: Xu, 2021; Lan & Monteiro, 2016; Lu & Zhou, 2023; Lu & Mei, 2023). In addition, variants of AL methods have been developed to solve nonconvex constrained optimization problems (Hong et al., 2017; Grapiglia & Yuan, 2021; Birgin & Martínez, 2020; Kong et al., 2023; Li et al., 2021d; He et al., 2023a;b; Lu, 2022). Besides AL methods and their variants, sequential quadratic programming methods (Boggs & Tolle, 1995; Curtis & Overton, 2012), trust-region methods (Byrd et al., 1987; Powell & Yuan, 1991), interior point methods (Wächter & Biegler, 2006), and extra-point methods Huang et al. (2022) have been proposed to solve centralized constrained optimization problems.
Distributed algorithms for constrained optimization Developing distributed algorithms for con- strained optimization has started relatively recently. To handle simple local constraints in distributed opti- mization, Nedic et al. (2010); Lin al. (2016); Wang et al. (2017) study distributed projected subgradient methods. For complicated conic local constraints, Aybat & Hamedani (2016; 2019) develop distributed primal-dual algorithms. For distributed optimization with global and local constraints, Zhu & Martínez (2011); Yuan et al. (2011) develop primal-dual projected subgradient algorithms. For overview of dis- tributed constrained optimization, see Yang et al. (2019). Notice that FL is a special distributed optimiza- tion/ /oe//ernning framework that protects data privacy by prohibiting the transfer of raw data from one client to another or to a central server. These distributed algorithms for constrained optimization do not violate the FL restriction and hence can be considered as FL algorithms, but they can only handle problems with simple global or local constraints that are amenable to easy projection. Therefore, they cannot be applied directly to our setup Eq. (5) with general global and local constraints.
FL algorithms for constrained ML applications A small number of papers have developed FL algo- rithms for particular constrained ML applications, such as learning with class imbalance and fairness-aware
4

---

Published in Transactions on Machine Learning Research (05/2024)
ML. For example, Shen et al. (2021); Chu et al. (2021) propose FL algorithms to address class imbalance and subgroup imbalance, respectively, by optimizing the Lagrangian function. Du et al. (2021) applies quadratic penalty method to deal with the constraint in fairness-aware ML. In addition, Gálvez et al. (2021) pro- poses an FL algorithm to tackle fairness-aware ML based on optimizing the AL function. However, these developments are lailored lo specific applications and lack rigorous computational guarantees regarding the feasibility and optimality of their solutions. In contrast, this paper focuses on developing algorithms with theoretical guarantees for FL with convex global and local constraints. To the best of our knowledge, this work provides the first general FL framework for constrained ML problems.
2 Notation and preliminaries
Throughout this paper, let IRd and R2 denote the d-dimensional Euclidean space and its nonnegative orthant, respectively. We use (.-) to denote the standard inner product, || to denote the Euclidean norm of vector or the spectral norm of matrix, and || ooo to denote the & -orm of vector. For any vector v E IR, [+]+ E Rd is its nonnegative part (i.e., with all negative values set to zero). We adopt the standard O notation O(-) to present complexity results; O()) represents O-)) with logarithmic terms omitted.
Given a closed convex function h : Rd + oo),, Oh and dom(h) denote the subdifferential and domain of h, respectively. The proximal operator associated with h is denoted by prox,, that is, prox, (u) = arg (1lw - wll²/2 + h(w) for all u E R Given a continuously differentiable mapping : R + RP, we write the transpose of its Jacobian as Vo(w) = (w)
[or(w)] R We say that V L- Lipschitz continuous on a Q for some L > 0 if VV(()) Vo(v)l S LIlu- ell for all u, v E Q. In addition, we say that Vø is locally Lipschitz continuous Ω if for any E Ω there exist L > 0 and open set Un containing w such that V is Ln--ipschitz continuous on Uw-
Given a nonempty closed convex set C S R² and any point u E ıRd dist(u, C) and dist C) stand for the Euclidean distance and the Chebyshev distance from u to C, respectively. That is, dist(u,CC C) = min.ec ||u- and dist (u, C)- = minwec ||u vll.o. The normal cone of at u u is denoted by Nc(u). The Minkowski sum of two sets B and C is defined as B B+C = (b+c:: c: C).
For case of presentation, we let m= Er= m; and adopt the following notations throughout this paper:
[o(w))
f(w) = F((w) c(w)
E R"
=
E
R
(6)
on (w)
Assumption 1. Throughout this paper, we ossume that the strong duality holds for Eq. (5) and its dual problem
sup (f(w) + h(w) + (H, c(w))}
(7)
#20 8
That is, both problems have optimal solutions and, moreover, their optimal values coincide.
Under Assumption 1, is known that (w, u)) E dom(h) x RI is a pair of optimal solutions of Eq. (5) and Eq. (7) if and only if it satisfies (see, e.g., Lu & Zhou (2023))
V ((w)) + ah(w) + Ve(w))) c(w) N
ee
(8)
Ww)-Nzp xT (p)
In general, is hard to find an exact optimal solution of Eq. (5) and Eq. (7). Thus, we are instead interested in seeking an approximate optimal solution of Eq. (5) and Eq. (7) defined as follows.
Definition 1. Given any 61, '2 > 0, we say (w. ()) E dom(h) x RT is an (G1, copoptmall solution of Eq. (5) and Eq. (7) if di (0, Vf(w)) + ah(w) + Ve(w))) S é1 and distoo disto) (c(w), (RT(())) S E2.
For unconstrained convex problems with differentiable objective min [ww), a natural measure of convergence is [ [w)(]) i..,, the distance between and vf(w), as the optimality condition is Vf(w)= 0. If the objective is nondifierentiable, to use the notation of subdifferential, (f))), which a for each general. this case, the optimality condition reads e (w)), and the measure of convergence the distance between and the subdifferent. set dist(O, (wr)) == min [|a]]-
need
5

---

Published in Transactions on Machine Learning Research (05/2024)
Here, the two different tolerances E1 f2 are used for measuring stationarity and feasibility violation, respec- tively. This definition is consistent with the e-KKT solution considered in Lu & Zhou (2023) except that Definition uses the Chebyshev distance rather than the Euclidean distance.
3 A proximal AL based FL algorithm for solving Eq. (5)
In this section, we propose an FL algorithm for solving Eq. (5) based on the proximal AL method. Specifically, we describe this algorithm in Section 3.1, and then analyze its complexity results in Soction 3.2. Assumption 2. Throughout this section, we assume that (a) The prozimal operalor for h can be eraclly evaluated. (b) The gradients V f,,, f, 1 i S n, and the transposed Jocobians Ve, 0 S S n, are locally Lipschitz continuous on R.
Assumption 2(b) clearly holds all Vh's and Vey's are globally Lipschitz continuous on R but this assumption holds for a broad class of problems without global Lipschitz contimuity on Vf's and Ve,ss. For example, the quadratic penalty function of c(w) s O, namely [[((w)]++11, only has a locally Lipschitz continuous gradient even if Vc is globally Lipschitz contimuous gradient of a convex high-degree polynomial, such as ||w]|| with w E Rdd is locally Lipschitz continuous but not globally Lipschitz continuous on Rd.
Rd (sce Remark 4.1). In addition, the
3.1 Algorithm description
In this subsection, we describe proximal AL-based FL algorithm (Algorithm 1) for finding an (21, optimal solution of Eq. (5) for prescribed 61 E (0, 1). This algorithm follows a framework similar to a
centralized proximal AL method described in Appendix D; see Section 11.K in Rockafellar Wets (2009) or Lu & Zhou (2023) for more details of proximal AL. At each iteration, it applies an inexact ADMM solver (Algorithm 2) find an approximate solution =+1 the proximal AL subproblem associated with Eq. (5):
min (x) = Σ f(lw) h(w) +
23 (1114 (c.(w))+ ||x+11])
1
2B ||w 1
(9)
augmented Lagrangian function
proxinal
Then, the multiplier estimates are updated according to the classical scheme:
M k+1 = [u + Be 1) 0 S S n.
Notice that the subproblem in Eq. (9) can be rewritten as
min 3
(&(w) E (w)(w)) h(w)
(12)
where Pi,s, 0 0 S n, are defined
Po,(ww)= = 23 (1lia) + Sco(w))++1 -1 + 2(n + 1)3 w| - 11
(13)
1
Piu(w) fi(w) 23 (Il[ + Sc((w)++ 11- + 2(n + 1)B3 w| 11w-w w01l
visiS
(14)
When Algorithm 2 (see Section 4) is applied to solve Eq. (12), the local merit function PLx. constructed from the local objective fi and local constraint e, is handled by the respective local client i, while the merit function Po.x is handled by the central server. We observe that Algorithun with the subproblem in Eq. (12) solved by Algorithm 2 meets the basic FL requirement: since local objective fi's and local constraint ej 's are handled by their respective local clients and the central server only performs aggregation and handles the global constraint co, no raw data are shared between local clients and the central server, i.., Assumption 0(b) is obeyed.

---

Published in Transactions on Machine Learning Research (05/2024)
Algorithm A proximal AL based FL algorithm for solving Eq. (5)
Input: tolerances e e2 E (0, w" E dom(h), p 2 0 for 0 S i S n. s 0, and 3 >>> 0. 1: for k = 0, 2, ... do
Set T = s/ck + +
Call Algorithm 2 (see Section 4 below) with (T, w0) (Tx, w to find approximate solution w++1
to Eq. (12) in federated manner such that
d0, 00. (l S Tk-
(10)
Server update: The central server updates Mo = JuB 3co Communication (broadcast): Each local client i, 1 I n, receives wh+1 from the central server. Client update (local): Each local client
S S updates u4 k+1 lu (c,(w*+1)]+
8: Communication: Each local client i, 1 S i S n, sends ||,," 1 to the central server.
9: Termination (server side): Output (w*+1 k1) and terminate the algorithm
| - 1lo0 + 8Tk S BE1.
flk k+1 - M4 1lo0 S Beg. osign
max
(11)
10: end for
Remark 3.1. We now make the Jollowing remarks on Algorilhm
(a)
For haperparameters of Algorithm 1,
62 E (0, 1) only depend on the numerical accuracy that the user aims lo achieve;
the initial iterates w and pf, 1 i n, are usually randomly generated or set as a constant vector; These finâte, non-zero tolerances allow us solve the subproblems inezactly but can still guarantee convergence, hence saving compulational costs. In particular, setting {Tk} to diminish rapidly towards zero the order of O(1/k²) can guorantee convergence of Algorithm 1. In practice, only needs to be set as O(1).
> controls the tolerance sequence {Tk] for the subproblems in Algorithm
(b) Compared to the centralized prozimal AL developed in Lu & Zhou (2023), we have made the following major changes to arrive at Algorithm 1.
add communication steps to allow dual updates in on FL manner;
to solve the subproblem, we cannot directly apply the accelerated gradient method (AGM) as in Lu & Zhou (2023). It is possible to develop FL version of AGM by eagerly aggregating gradients from local clients, but that induces heavy communication between clients and the centrol server. To address this, we first reformulate the subproblem
finile-sum problem and then propose inexacl A ADMM solver to solve it. The inexact ADMM solver allows multiple steps of local updates before aggregation of model weights at the central server, hence it is communication friendly. We also propose new stopping crilerion for the inexact ADMM (Algorithm 2). Delailed explanations can be found in Remark 4.2.
For ease of later reference, refer to the update from w to w and call one iteration of Algorithm 2 for solving Eq. (9) one inner iteration of Algorithm 1. In the rest of this section, we study the following measures of complexity for Algorithm 1.
outer iteration of Algorithm 1,
Outer ileration complerity, which measures the number of outer iterations of Algorithm (one outer iteration refers to one execution from Line to Line Algorithm 1);
Total inner iteration complenity, which measures the total number of iterations of Algorithm 2 that are performed in Algorithm (one inner ileration refers to execution from Line 3 to Line 10 in Algorithm 2).
The following theorem concerns the output of Algorithm 1, whose proof deferred to Appendix A.1.
Theorem 3.1 (output of Algorithm 1). If Algoritim successfully terminates, its output (w++1 p s41) is an (e1, -oppimal solution of Fq. (5).

---

Published in Transactions on Machine Learning Research (05/2024)
3.2 Complexity analysis
In this subsection, establish the outer and total inner iteration complexity for Algorithm 1. To proceed, we let (w", (²") be any pair of optimal solutions of Eq. (5) and Eq. (7), First, we establish a lemma to show that all iterates generated by Algorithm 1 are bounded. Its proof can be found in Appendix A.2.
Lemma 3.1 (bounded iterates of Algorithm 1). Suppose that Assumptions 0 to 2 hold. Let {w" all the iterates generated by Algorithm I. Then we have w E =Q for all 2 0, where
Q1 {w R² || w'll S ro + 2/n33}
with ro = 11( p²) (w" 1 ,ا))1,+
(15)
and wo, n0, 8, and are inpuls of Algorithm 1.
This boundedness result allows to utilize the Tipschitz continuity on bounded set to establish the conver- gence rate for Algorithm 1. The following theorem states the worst-case complexity results of Algorithm 1, whose proof is relegated to Appendix A.3.
Theorem 3.2 (complexity results of Algorithm 1). Suppose that Assumptions 0 to 2 hold. Then, (a) the number of outer iteration of Algorithom 1 is at most O(maxfe -2 E2 2)););; and (b) the total number of inner iterations of Algorithm
most O(max (ma (
Remark 3.2. (a) the best of our knowledge, Theorem 3.2 provides the first worsl-case complerity resulls for finding an opprozimate optimal solution of Eq. (5) in an FL framework; (b) The number of outer and inner iterations of Algorithm with detailed dependencies the algorithm huperparameters can be found in Eqs. (48) and (84) in the proofs, respectively.
3.3 Communication overheads
In the outer loop of Algorithm 1, single communication round occurs after solving proximal AL sub- problem. During this round, the central server sends the current weights w*11 to all local clients, and each client sends back the maximum change in their respective multiplicrs, mcasured by Ilu pflloo, to the central server. The communication overheads of the inner solver Algorithm 2 are discussed in Section 4.3. The communication complexity of Algorithm is O(max(e]" .6,)) 2]).
4 An inexact ADMM for FL
In this section, we propose an inexact ADMM-basee FL algorithm to solve the subproblem in Eq. (12) (the same as Eq. (9)) for Algorithm 1. Before proceeding, we show that P.P.s, 0 osis S n, are locally Lipschitz continuous on Rdd whose proof is deferred to Appendix B.I.
Lemma 4.1 (local Lipschitz continuity of P;,)). Suppose that Assumptions 0 to 2 hold. Then the gradients V Pi,k, 0 S n. are locally Lipschitz continuous on Bd
Remark 4.1. It worth noting that P.P.k, 0 n, are typically not globally Lipschitz continuous on Rd even if f., < < n, and VG, 0 < i S n, are globally Lipschitz continuous on RRd For ezample, consider co(w) = || 2- 1. By Eq. (13), one has that
(w) = 2(10 + 3(11w]12 - 1)]+ + (n 1)33 (w w²).
In this case, it is not hard to verify that Vea is globally Lipschitz continuous on IRd, but Po. is not. Thus, analyzing the complexity results for solving the subproblems in Eq. (12) using local Lipschitz conditions of V.Pkk, 0 < sis < n, is reasonable.
Moreover, it is easy to see that Pa.e are strongly convex with the modulus 1/(m++1) for all 0 s i iiS n and all A 2
Since both the local Lipschitz and the strong convexity (including its modulus) properties hold for all k: 2 0, and need to solve the subproblem of the same form each k, below drop & and focus solving the
8

---

Published in Transactions on Machine Learning Research (05/2024)
following model problem in an FL manner:
min ((w) = Σ
P:(w: Z,) + h(w)
(16)
1=0
where the data Z are only accessible to their corresponding local/globar functions P/'s, necessitating FL. We will drop Z henceforth for simplicity. The model problem in Eq. (16) satisfies:
1. The functions P. S iis n. are continuously differentiable, and moreover, VP, 0 n, are locally Lipschitz continuous on IR";
2. The functions P, S I n, are strongly convex with a modulus o > on R that is
(V)( VP.(v), u u) 2 aluu-ol3 Vu, R. 0 05i n.
(17)
4.1 Algorithm description
Algorithm An inexact ADMM based FL algorithm for solving Eq. (16)
Input: tolerance
(0, 1], 9 e (0, 1), To E dommh), and pi > for I S m; 1: Set w = w", and (u,, X2, a.) = ( (v", T - VP((w")/p)) for S is n.
2: for t = 0, 1, 2,... do
3: Set Ei+1 = q²;
Server update: The central server finds an approximate solution a11 to
min (o. = Po(w)= h(w)
Pi u 2
w/
(18)
5: such that dist (0, (. Et+1.
Communication (broadcast): Each local client i, 1 S S n, receives w from the server.
Client update (local): Each local client S n, finds an approximate solution u d++ to
min (p.)(u)) = P.(14) + (A u w w mi
Pi ||u, w 2112
(19)
2
such that [Vprt(u(*))lll S Es+1, and then updates
X X + pr(u w(11)
(20)
att1 us + 1
(21)
& [ Pi(w - 1l)
(22)
Communication: Each local client i, 1 Ssiii n, sends (ū " Ec,+1) back to the central server. Termination (server side): Output w111 and terminate this algorithm if
10:
E111 Eust ST.
(23)
11: end for
In this subsection, propose an inexact ADMM-based FL algorithm (Algorithm 2) for solving Eq. (16). To make each participating client handle their local objective P; independently (see Section 3.1), we introduce decoupling variables un's and obtain the following equivalent consensus reformulation for Eq. (16):
min Σ P((w)) + Po(w) + +k(w) s.t. u, = w, 1 i n,
(24)
9

---

Published in Transactions on Machine Learning Research (05/2024)
which allows each local client to handle the local variable u, and the local objective function P. while imposing consensus constraints that force clients' local parameters u, equal to the global parameter w. This reformulation enables the applicability of an inexact ADMM that solves Eq. (24) in a federated manner. At each iteration, an ADMM solver optimizes the AL function associated with Eq. (24):
u,( = Σ (((u.) + (Aa, u - w) + 2 llu, w||² Po(ww) + h(w)
(25)
2
with respect to the variables w, u, and À alternately, where a luf...., N and M = collect all the local paramcters and the multipliers associated with the consensus constraints, respectivcly. Specifically, in iteration 4, one performs
w²+1 = arg min Cp(w, u N²),
(26)
u arg arg min Cp u, N²)))
(27)
x = X + ( (ut+ -utt)
A1 visisn
(28)
By the definition of Lp in Eq- (25), one can verify that the step in Eq. (26) is equivalent to Eq. (18), and also the step in Eq, (27) can be computed parallel, which corresponds to Eq. (19). Therefore, the ADMM updates naturally suit the FL framework, as the separable structure in Eq. (25) over the pairs {(u, A,} enables the local update of (w;; A4) at each client i while is updated by the central server.
Since the subproblems in Eq. (18) and Eq. (19) are strongly convex, their approximate solutions w and ut+1, 1 S < n, can be found using gradient- algorithm with global linear convergence rate (Nesterov et al., 2018). Furthermore, the value É,,41 in Eq. (22) serves as a measure of local optimality and consensus for client i. By summing up ε,,41 for < I n and including Et+1, one can obtain a stationarity measure for the current iterate (see (Eq. (23))), as presented in the following theorem. Its proof can be found in Appendix B.2.
Remark 4.2. We now make the following remarks Algorithm 2.
(a) On hyperparameters of Algorithm 2,
(r, w)) is specified as (Tk, w²) at the kth iteration of Algorithm 1.
From Eq. (18), Pi, 1 S < can be viewed as weighting parameters for aggregation. Therefore, it is natural to set P: = am; for 1 < i where my is the number of samples in client i and a is global constant. We follow this rule when setting 's.
E (0,1) determines the tolerance sequence {El+1he2o for the subproblems in Eq. (18). These tol- erances in solving subproblems reduce compulational cosls. Selling {Ee+1)e20 to rupidly diminish toward zero rapidly a geometric rate ensures the convergence of Algorithu 1. In practice, we suggest setting q ((1).
(b) The main innovations we have here compared to the eristing literature ADMM- Masedd FL algorithms (e-g, Zhou & Li (2023); Gong et al. (2022); Zhang et al. (2021)) include:
We establish the complerity results of an inexact ADMM-bosed FL algorithu under local Lipschitz conditions, us. global Lipschitz conditions in other work. Our complexity results can be found in Theorem 4.2.
We propose novel and rigorous stopping criterion (Eq. (23)) that is easily verifiable, communication- light, and compatible with the ouler ilerations (as our inexact ADMM FL algorithm serves subproblem solver in overall algorithu framework).
Thcorem 4.1 (output of Algorithm 2). If Algorithm 2 terminates at some iteration T 2 0, then its oulpul T+1 salisfies distoc (0, (+1)) T.
Theorem 4.1 states that Algorithm 2 outputs point that approximately satisfics the first-order optimality condition of Eq. (5). In addition, it follows from Theorem 4.1 that Algorithm 2 with (r, @o) (Tk, w*) finds approximate solution #+1 to Eq. (12) such that Eq. (10) holds.
10

---

Published in Transactions on Machine Learning Research (05/2024)
4.2 Complexity analysis
In this subsection, we establish the iteration complexity for the inexact ADMM, namely, Algorithm 2. Recall from Eq. (17) that Eq. (16) is strongly convex and thus has a unique optimal solution. We refer to this optimal solution of Eq. (16) as w" throughout this section. The following lemma shows that all the iterates generated by Algorithm lie a compact set. Its proof can be found in Appendix B.3.
Lemma 4.2 (bounded iterates of Algorithm 2). Suppose that Assumplions to 2 hold and let fuf-"hsisma and fwt be all the iterates generated by Algorithm 2. Then holds that all these ilerates stay in a compact set 2, where
polliö - - 1 IIVP,((0* VV.(00)) }
n2 + 1
+ 1 Σ
= V: |10 1
(29)
0² 92)
Pi
The iteration complexity of Algorithm established in the following theorem, whose proof is relegated to Appendix B.4.
Theorem 4.2 (iteration complexity of Algorithm 2). Suppose that Assumptions 0 to 2 hold. Then Algorithm 2 terminales in at most O(looT))) iterations.
Remark 4.3. We now make the following remarks on the complexity results in Theorem 4.2.
(a) Algorithm 2 enjoys a global linear convergence rate when solving the problem in Eq. (16). The result generalizes classical convergence results for ADMM in the literature, which typically require a strongly conver objective with globally Lipschitz conlinuous grudient (e.g., see Lin el al. (2015)). In contrust, our result the first establish global linear convergence of an inexact ADMM assuming a strongly conver objective with only a locally Lipschitz continuous gradient.
(b) The number of iterations of Algorithm 2 with dependencies all the algorithm hyperporameters can be found in Eq. (74) in the proofs.
(c) The general research on complerity analysis for optimization algorithms under local Lipschitz assump- tions is relatively new. For ezample, Lu & Mei (2023) proposes accelerated gradient methods for conver oplimization problems with locally Lipschilz conlinuous gradienis, and Zhang & Hong (2024) proposes accelevated gradient methods for noncoveer optimization problems with locally Lipschitz continnous gra- dients.
4.3 Communication overheads
In each iteration of Algorithm 2, a single communication round happens between the clients and the central server. During this round, the central server transmits the global weight w²*11 to all clients, and subsequently each local client performs multiple local updates to solve local subproblem and then sends the updated local weights a/t+1 and a local stationarity mcasure εi,411 back to the central server. The communication complexity of each call of Algorithm 2 is O( logT).
5 Numerical experiments
Here, conduct numerical experiments evaluate the performance of our proposed FL algorithm (Algo- rithm 1). Specifically, we benchmark our algorithm against centralized proximal AL method (cProx-AL, described in Algorithm 3) on convex Neyman-Pearson classification problem (Section 5.1) and a fair- aware learning problem (Section 5.2) with real-world datasets, and further on finear-equalily-consttrii quadratic programming problems with simulated data (Appendix E.2). All experiments are carried out on Windows system with an AMD EPYC 7763 64-core processor, and all algorithms are implemented in Python. The code to implement the proposed algorithm on these numerical examples is available https://githin
http:://gtttuuu..coos////////// cttp:l.9//c/////cc//// Coons///onstrrre FL.
11

---

Published in Transactions on Machine Learning Research (05/2024)
Table 1: Numerical results for solving Eq. (30) using our algorithm vs. using cProx-AL. Inside the parentheses are the respective standard deviations over 10 random trials. For feasibility, we include the mcan and maximum losses for class 1 among all local clients.
objective (loes for
leasibiity (loes for cluss (S 0.2))
dataset
Algorithm
eProx-AL
relative difference
Algorithm
cProx-AL
mocn
max
meam
max
0.27
(1.326004)
0.27 (3.02e-05)
7.00e-04
(2.02e-04)
0.20 (1.80e007)
0.20 (1.80e007)
0.20 (1.84c-08)
0.20 (1.84e-08)
0.34 (4.50e002)
0.33 (4.55e402)
1.15e402 (5.17e-03)
0.19 (7.33e-06)
0.20 (1.08e006)
0.19 (1.13e-04)
0.20 (1.72e-05)
10
0.37 (1.08e-01)
0.37 (1 (1.08)401)
3.92e-04
(2.76e-01)
0.17 (1.15e-05)
0.20 (6. (5.05e-09)
0.17 (1.1de-05)
0.20 (2 (2.96e-(18)
0.46 (2. 22112-01)
0.45 (2.12e-01)
3-43e-02
(2.91e-02)
0.16 (3.62e-06)
0.20 (3.76e-06)
0.16 (7.03e-06)
0.20 (7.70e-08)
0.73 (2. 19:19-01)
0.73 25e-44
2.21e-01 (3. (6.16)-04)
0.20 (6.30e-07)
0.20 (6.30e-07)
(3e-06)
0.20 (1.73e-00)
0.74 (1.03e-02)
0.74 (1 03e-22)
4.26e-03 (7.44e004)
0.20 (2414))04)
0.20 (2.80x-04)
0.20 (1.21e-05)
0.20 (2.28e-00)
adult-a
10
0.77 (1.98e
0.77 (1 (1.98)402)
2. 2.60-033 (3.24e-03)
0.19 (6.41e-05)
0.20 (9.76e005)
0.19 (2.00e-05)
0.20 (1.233-05)
0.78 (2.86e-02)
0.79 81e-422)
13e-402 (1.11e-03)
(6. (0400)
(6.59e-05)
(1.96e-05)
0.20 (3.19e-06)
1.38 (7.61e-05)
1.58 (7. (7.5)
1.39-415 (1.09e-03)
0.20 (1. (1009-07)
0.20 (1.09e-07)
0.20 (3.01e-07)
0.20 (3.01e-07)
1.65 (8. 30--2)
1.65 (8. 11e-02)
2 288-00 (1.8te-04)
0.19 (6.39e-00)
0.20 (5.39e-00)
0.19 (5.01e-06)
0.20 (5. (..60-))7
monks-1
1.71 (1.18<001)
1.71 (1-18e-01)
4.50e-04
(3:32e-04)
(3.98e-05)
(4.46n-05)
(6.44e-06)
(1.00e-00)
1.81 (1.49<-01)
1.79 61.-0)
1.78e002 (1.38e-122
0.17 (1.68e-44
0.20 (2:24e-04)
0.17 (4.60e-06)
0.20 (1.62e-06)
breast-cencer-wisc (n-5)
adult-a (n-5)
monks-1 (n-5)
0.7
0.00
0.6
0.45
0.55
Teasibility
855
0.00-
objective
844-
0.35
0.50
2.3
0.30
F00d of bo Nw this Jce.
0.25
fozelb e solow this line
0.20
fnactble baloe mic
12 outer iterations
24
27
à outer iterations
5
0
15
20
25
outer iterations
Figure Convergence behavior of local objective and local fcasibility in one random trial over the outer iterations of Algorithm 1 on three real-world datasets. The solid blue and brown lines indicate the mean local objective and the mean local feasibility over all clients, respectively. The blue and the brown areas indicate the cross-client variations of local objectives and local feasibility, respectively. The dashed black line indicates the fcasibility threshold.
5.1 Neyman-Pearson classification
In this subsection, we consider the Neyman-Pearson classification problem:
min 1
(10) 0)) s. t. 1 (ww; (z)
1 mi1
Σ ow: (af ,1) Sra. isisn, n,
(30)
m40
where (2 hsssma and {zz ( hsisma are the sets of samples at client i associated with labels 0 and 1. respectively, and & is the binary logistic loss (Hastie et al., 2009)
o(w; (z, v)) = -yw x + log(1 + ee "
) y E 10,
(31)
Then, both the objective and the constraints in Eq. (30) are convex. We consider three real-world datasets, namely brress-cannce-wiic"" 'adult-a', and 'monks-1', from the UCI repository² and described in Ap- pendix 1. For each dataset, we perform the Neyman-Pearson classification that minimizes the loss of classification for class 0 (majority) while ensuring that the loss for class (minority) is less than a threshold r; = 0.2. To simulate the FL setting, divide cach datasct into folds, mimicking local clients, each holding the same amount of data with equal ratios of the two classes.
We apply Algorithm 1 and cProx-AL (Algorithm 3) to find a (10-3, -optimall solution of Eq. (30). We run 10 trials of Algorithm 1 and AL. For each run, both algorithms have the same initial point wo.
see httpp://archhve ics. uci. edu/datasete.
12

---

Published in Transactions on Machine Learning Research (05/2024)
randomly chosen from the unit Euclidean sphere. We set the other parameters for Algorithm 1 and cProx-AL as 14 = 0) v0 < i S n, 5 = 0.001 and 8 = 300. We also set P: = 0.01 A1 S S n for Algorithm 2.
Comparing the objective value and feasibility of solutions achieved by Algorithm 1 and cProx-AL in Table 1, we see that both algorithms can yield solutions of similar quality. Given the small standard deviations, we observe that the convergence behavior of Algorithm remains stable across 10 trial runs. These observations demonstrate the ability of Algorithm to reliably solve Eq. (30) in the FL setting without compromising solution quality. From Fig. we observe that Algorithm 1 consistently achieves feasibility for all local constraints while also minimizing all the local objectives.
5.2 Classification with fairness constraints
In this subsection, we consider fairness-aware learning with global and local fairness constraints:
mi owu; 2 STh
min 11
1 olw; 2 (1)) s.t. -Ti S
olw; 2
Osism. n. (32)
m.
Here, (3) = (v)) ) E R {0, : === ....., ,,...,,,,3. I,..., m.} is the training set, where indexes is further divided into two subgroups {$) Jisism, and (8) Jisss, based on certain subgroup attributes. The constraints with = L..... n refer to local constraints at client i, while the constraints with i 0 refer to global constraints at the central server.
M)
the central server /local clients. For each i 0, O,..., n, the dataset tzy
We choose & as the binary logistic loss defined in Eq. (31), leading to nonconvex constraints in Eq. (32). For the real-world dataset, we consider 'adult-b'3; each sample in this dataset has 39 features and one binary label. To simulate the FL setting, we divide the 22, 654 training samples from the 'adult-b' dataset into n folds and distribute them to n local clients. The central server holds the 5, 659 test samples from the 'adult- b' dataset. Note that although we have taken both the "training" and "test" samples from the 'adult-b' dataset here, these samples are used simulate our local samples and central samples, respectively, The focus here is to test optimization performance, not generalization-wee do not have test step, unlike in typical supervised learning.
We apply Algorithm 1 and cProx-AL (Algorithm 3) to find a (10-3, 10 )-opimmll solution of Eq. (32). We run 10 trials of Algorithm 1 and cLrox-AL. For each run, both algorithms have the same initial point wo, randomly chosen from the unit Euclidean sphere. We set the other parameters for Algorithm 1 and cProx-AL 0) VO sis n, 5 = 0.001 and B = 10. We also set pj = 10sh V1 S i n for Algorithm 2.
as 1 0))
Comparing the objective value and feasibility of solutions achieved by Algorithm and cProx-AL in Table 2 reveals that Algorithm 1 and cProx-AL can produce solutions of similar quality. Given the small standard deviations, we observe that the convergence behavior of Algorithm 1 remains stable across 10 trial runs. These observations demonstrate the ability of Algorithm 1 to reliably solve Eq. (32) in the FL setting without compromising solution quality. It also suggests the potential of our algorithm in solving FL problems with nonconvex constraints. From Fig. 2, we see that our proposed method consistently achieves feasibility for all local and global constraints while also minimizing all the local objectives.
6 Concluding remarks
In this paper, we propose an FL algorithm for solving general constrained ML problems based on the proximal AL method. We analyze the worst-case iteration complexity of the proposed algorithm, assuming convex objective and convex constraints with locally Lipschitz continuous gradients. Finally, we perform numerical experiments to assess the performance of the proposed algorithm for constrained classification problems, using real-world datasets. The numerical results clearly demonstrate the practical efficacy of our proposed algorithm. Since our work is the first of its kind, there are numerous possible future directions. For example,
3This dataset can be found in https: http:/gghuuu.coooeeyaaeeeeeeeeee htt.a//aecettttsieeeeeeeeeeeeeee fatirnnss/rrre/msttttaaaat//////
13

---

Published in Transactions on Machine Learning Research (05/2024)
Table 2: Numerical results for Fq. (32) using our algorithm vs. using cProx-AL. Inside the parentheses are the respoctive standard deviations over 10 random trials. For foasibility, we include the mcan and maximum loss disparities (absolute difference between losses for two subgroups) among all clients and the central server. objective value
feasibility (loss disparity (s 0.1))
Algorithm
cProx-AT.
relative difference
Algorithm
AT.
mncn
max
0.37 (9.83e-05)
0.37 (4.14e.05)
1.97e-03 (2.53e004)
0.10 (1)14e004)
0.10 (1.36e-04)
0.10
(3.69e-06)
0.10 (5.38e-06)
0.37 (3.99e-08)
0.37 (4.05e-03)
1. 1.86e-03 (4.69e-04)
0.09 (5.34e-05)
0.10 (7.51e-05)
0.09 (3.68e-05)
0.10 (4.36e-06)
0.37 (6.39e-03)
0.37 (6.52e-03)
2.39e-03 (8. (8.40e-04)
0.08 (1.68e-04)
0.10 (2.15e-05)
0.08
(1.52e-04)
0.10 (6.56e-06)
0.38 (9.46c-03)
(9.866-03)
4.61e-03 (2.43e-03)
0.08 (9.75e-05)
0.10 (1.01c-04)
(4.90c-05)
0.10 (6.06e-06)
adult-b (n-5)
adult-b (n-10)
adult-b (n-20)
0.10
feasible beloy this line
Seasible if below lic.
fassill if helow this line
0.70
0.50
feasiblity
0.07
local meon
dooa
local mean global
local mesn
0bjectt
0.50
0.05
0.85
0.35
3
8
10
outer iterations
outer iterations
outer iterations
Figure Convergence of local objective, local feasibility, and the feasibility for global constraints one random trial over the outer iterations of Algorithm 1. The solid blue and brown lines indicate the mean local objective and the mean local feasibility over all clients, respectively. The blue and brown areas indicate the cross-client variations of local objectives and local feasibility, respectively. The dashdot blue line indicates the feasibility for global constraints, The dashed black line indicates the feasibility threshold.
could try to extend our FL algorithms allow partial client participation and stochastic solvers at local clients. In addition, developing FL algorithms for general constrained ML. with convergence guarantees in nonconvex settings remains largely open. Lastly, constrained FL with fixed iteration and communication budget, espocially stringent ones, is a very useful but challenging future rescarch topic.
Acknowledgments
C. He is partially supported by the NIH fund RO1CA287413 and the UMN Research Computing Seed Grant. L. Peng is partially supported by the CISCO Rescarch fund 1085646 PO USAD00EP390223.. J. Sun is partially supported by the NIH fund RO1CA287413 and the CISCO Research fund 1085646 PO USA00EEP390223, The authors acknowledge the Minnesota Supercomputing Institute (MST) at the University of Minnesota for providing resources that contributed to the research results reported this article. The content is solely the responsibility of the authors and does not necessarily represent the official views of the National Institutes of Health.
14

---

Published in Transactions on Machine Learning Research (05/2024)
References
Alckh Agarwal, Alina Beygelzimer, Miroslav Dudik, John Langford, and Hanna Wallach. A reductions approach to fair classification. In International Conference Machine Learning, pp. 60 69. PMLR, 2018
Necdet S Aybat and Erfan Y Hamedani. A primal-dual method for conic constrained distributed optimization problems. Advances in Neural Information Processing Systems, 29, 2016.
Necdet Aybat and Erfan Hamedani. A distributed ADMM-like method for resource sharing over time- varying networks. SIAM Journal on Optimization, 2934):3036 3068, 2019.
Necdet S Aybat and Garud lyengar. An augmented Lagrangian method for conic convex programming. arXiv preprint XrXi::1802 6322, 2013.
Heinz H Bauschke and Patrick L Combettes. Conver Analysis and Monotone Operator Theory in Hilbert Spaces. Springer, 2nd edition, 2017.
Ernesto G Birgin and José Martínez. Complexity and performance of an augmented Lagrangian algorithm. Optimization Methods and Software, 35(5):885-920, 2020.
Paul T Boggs and Jon W Tolle. Sequential quadratic programming. Acta Numerica, 4:1-51, 1995.
Richard H Byrd, Robert B Schnabel, and Gerald Shultz. A trust region algorithm for nonlincarly con-
strained optimization. SIAM Journal on Numerical Analysis, 24(5):1152-1177) 1987.
Elisa Celis, Lingxiao Huang, Vijay Keswani, and Nisheeth K Vishnoi. Classification with fairness constraints: A meta-algorithm with provable guarantecs. In Proceedings of the Conference on Fairness, Accountabilitt, and Transporency, pp. 319 328, 2019.
Peter W Christensen and Anders Klarbring. An Introduction to Structural Optimization, volume 153. Springer Science & Business Media, 2008.
Lingyang Chu, Lanjun Wang, Yanjie Dong, Jian Pei, Zirui Zhou, and Yong Zhang. FedFair: Training fair models in cross-silo federated learning. arXiv preprint Stl:2109.006663 2021.
Frank E Curtis and Michael L Overton. A sequential quadratic programming algorithm for nonconvex, nonsmooth constrained optimization. SIAM Journal on Optimization, 22(2):474-500, 2012.
Wei Du, Depeng Xu, Xintao Wu, and Hanghang Tong. Fairness-aware agnostic federated learning. In Proceedings of the 2021 SIAM International Conference on Data Mining (SDM), pp. 181-189. SIAM, 2021.
Borja R Gálvez, Filip Granqvist, Rogier Dalen, and Matt Seigel. Enforcing fairness in private federated learning via the modified method of differential multipliers. In NeurIPS 2021 Workshop Privacy in Machine Learning, 2021.
Joachim Giesen and Sören Laue. Combining ADMM and the augmented Tagrangian method for efficiently handling many constraints. In International Joint Conference on Artificial Intelligence, pp. 4525 4531, 2019.
Yonghai Gong, Yichuan Li, and Nikolaos M Freris. FedADMM: A robust federated deep learning framework with adaptivity to system heterogeneity, In 2022 IEEE 38th International Conference on Data Engineering (ICDE), pp. 2575-2588 IEEE, 2022.
Ian J Goodfellow, Jonathon Shlens, and Christian Szegedy. Explaining and harnessing adversarial examples. arXiv preprint Xrv: 1xXi::1412.657. 2014.
Geovani N Grapiglia and Ya-xiang Yuan. On the complexity of an augmented Lagrangian method for nonconvex optinization. IMA Journal of Numerical Analysis, (2) 2021.
15

---

Published in Transactions on Machine Learning Research (05/2024)
Trevor Hastie, Robert Tibshirani, and Jerome H Friedman. The Elements of Statistical Learning: Data Mining, Inference, and Prediction. Springer, New York, 2nd edition, 2009.
Chuan He, Heng Huang, and Zhaosong Lu. A Newton-Cke CG based barrier-augmennt Lagrangian method for general nonconvex conic optimization. arXiv preprint wxXiu2231.042000 2023a.
Chuan He, Zhaosong Lu, and Ting Kei Pong. A Newton-CG based augmented Lagrangian method for finding second-order stationary point of nonconvex equality constrained optimization with complexity guarantees. STAM Journal on Oplamization, 33(3):1734-1766) 2023b.
Mingyi Hong, Davood Hajinezhad, and Ming- Min Zhao. Prox-PDA: The proximal primal-dual algorithm for fast distributed nonconvex optimization and learning over networks. In International Conference on Machine Learning, pp. 1529-1538. PMLR, 2017.
Kevin Huang, Nuozhou Wang, and Shuzhong Zhang. An accelerated variance reduced extra- extra-point approach to finite-sum VI and optimization. arXiv preprint arXiv:2211005 033269,, 2022.
Peter Kairouz, H Brendan McMahan, Brendan Avent, Aurélien Bellet, Mehdi Bennis, Arjum Nitin Bhagoji, Kallista Bonawitz, Zachary Charles, Graham Cormode, Rachel Cummings, al. Advances and open problems in federated learning. Foundations and Trends@ in Machine Learning. 14(1-2):1-2 11-2:2112100 210, 2021.
Sai P Karimireddy, Satyen Kale, Mehryar Mohri, Sashank Reddi, Sebastian Stich, and Ananda T Suresh. Scaffold: Stochastic controlled averaging for federated learning, In International Conference on Machine Learning, pp. 5132-5143 PMLR, 2020.
Jakub Konečný, H Brendan McMahan, Felix Yu, Peter Richtárik, Ananda T Suresh, and Dave Bacon. Federated learning: Strategies for improving communication efficiency. arXiv preprint arXiv:1610.055: 05499, 2016.
Weiwei Kong, Jefferson G Melo, and Renato DC Monteiro. Iteration complexity of an inner accelerated inexact proximal augmented Lagrangian method based on the classical Lagrangian function. STAM Journal on Optimization, 33(1):181-21) 210, 2023.
Guanghui Lan and Renato DC Monteiro. Iteration-complexity of first-order augmented Lagrangian methods for convex programming. Mathematical Programming, 155(1-2):511 547, 2016.
Qinbin Li, Zeyi Wen, Zhaomin Wu, Sixu Hu, Naibo Wang, Yuan Li, Xu Liu, and Bingsheng He. survey on federated learning systems: Vision, hype and reality for data privacy and protection. IEEE Transactions on Knowledge and Data Engineering, 2021a.
Tian Li, Anit K Sahu, Manzil Zaheer, Maziar Sanjabi, Amect Talwalkar, and Virginia Smith. Federated optimization in heterogeneous networks. Proceedings of Machine Learning and Systems, 2:429 450, 2020.
Tian Li, Shengyuan Hu, Ahmad Beirami, and Virginia Smith. Ditto: Fair and robust federated learning through personalization. In International Conference on Machine Learning, pp. 6357 6368. PMT.R, 2021b.
Xiaoxiao Li, Meirui Jiang, Xiaofei Zhang, Michael Kamp, and Qi Dou. FedBN: Federated learning on non-iid features via local batch normalization. arXiv preprint arXiv:2102.077 076622 2021c.
Zichong Li, Pin-Yu Yu Chen, Sijia Liu, Songtao Lu, and Yangyang Xu. Rate-improved inexact augmented Lagrangian method for constrained nonconvex optimization. In International Conference Arlificial Intelligence and Statistics, pp. 2170-21 2170-2178. PMLR, 2021d.
Peng Lin, Wei Ren, and Yongduan Song. Distributed multi-agent optimization subject to nonidentical constraints and communication delays. Automatica, 65:120 131, 2016.
Tianyi Lin, Shiqian Ma, and Shuzhong Zhang. On the global linear convergence of the ADMM with multi- block variables. STAM M Journal Optimization, 25(3):1478 -49447777777 2015.
16

---

Published in Transactions on Machine Learning Research (05/2024)
Yi Liu, JQ James, Jiawen Kang, Dusit Niyato, and Shuyu Zhang. Privacy-preserving traffic flow prediction: A federated learning approach. TEEF Internet of Things Journal, 7(8):7751-777) 17766, 2020.
Guodong Long, Yue Tan, Jing Jiang, and Chengqi Zhang. Federated learning for open banking. In Federaled Learning: Privacy and Incentive, pp. 240 254. Springer, 2020.
Songtao Lu. A songle-loop gradient descent and perturbed ascent algorithm for nonconvex functional con- strained optimization. In International Conference on Machine Learning, pp. 14315 14357. PMLR, 2022.
Zhaosong Lu and Sanyou Mei. Accelerated first-order methods for convex optimization with locally Lipschitz continuous gradient. SIAM Journal on Optimization, 33(3):2275-233 2310,, 2023.
Zhaosong Lu and Zirui Zhou. Iteration-complexitty of first-order augmented Lagrangian methods for convex conic programming. SIAM Journal on Optimization, 33(2):1159 1190, 2023.
Levi McClenny and Ulisses Braga-Neto. Self-adaptive physics-informet neural networks using soft attention mechanism. arXiv preprint ar Xiv::20009 04544, 2020.
Brendan McMahan, Eider Moore, Daniel Ramage, Seth Hampson, and Blaise Agüera y Arcas. Communicttion-cffcien learning of deep networks from decentralized data. In Artificial Intelligence and Slatistics, pp. 1273 1282. PMLR, 2017.
Ninarch Mchrabi, Fred Morstatter, Nripsuta Saxena, Kristina Lerman, and Aram Galstyan. A survey bias and fairness in machine learning. ACM Compuling Surveys (CSUR), 54(6): 2021.
Jed Mills, Jia Hu, and Geyong Min. Commmunication-ellfccien federated learning for wireless edge intelligence in IoT. IEEE Internet of Things Journal, 7(7) 5994, 2019.
Konstantin Mishchenko, Grigory Malinovsky, Sebastian Stich, and Peter Richtárik. Proxskip: Yes! local gradient steps provably lead to communication acceleration! finally! In International Conference on Machine Learning, pp. 15750-15769. PMLR, 2022.
Ton Necoara, Andrei Patrascu, and Francois Glineur. Complexity of first-order inexact. Lagrangian and penalty methods for conic convex programming. Optimization Methods and Software, 34(2):305 335, 2019.
Angelia Nedic, Asuman Ozdaglar, and Pablo A Parrilo. Constrained consensus and optimization in multi- agent networks. IEEE Transactions on Automatic Control, (5(4):922-935 2010.
Yurii Nesterov et al. Lectures on conver optimization, volume 137. Springer, 2018.
OCR. Hipaa Home. HHS.gou, Aug 2023. URL https://www hhs haths.goo/hppaaindneeeeo windeaaa/iiiiiaaeeee .hmll.
Reese Pathak and Martin J Wainwright. FedSplit: An algorithmic framework for fast federated optimization.
In Advances in neural information processing systems, volume 33, pp. 7057 7066, 2020.
Andrei Patrascu, Ion Necoara, and Quoe Tran-Dinh. Adaptive inexact fast augmented Lagrangian methods for constrained convex optimization. Optimization Letters, 11:609 626, 2017.
Le Peng, Gaoxiang Luo, Andrew Walker, Zachary Zaiman, Emma K Jones, Hemant Gupta, Kristopher Kersten, John L Burns, Christopher Harle, Tanja Magoc, Benjamin Shickel, Scott D Steenburg. Tyler Loftus, Genevieve B Melton, Judy W Gichoya, Ju Sun, and Christopher J Tignanelli. Evaluation of federated learning variations for COVID-19 diagnosis using chest radiographs from 42 US and European hospitals. Journal of the American Medical Informatics Association, 30(1):54 63, 2023a.
Le Peng, Sicheng Zhou, Jiandong Chen, Rui Zhang, Ziyue Xu, and Ju Sun. A systematic evaluation of federated learning biomedical natural language processing. In International Workshop on Federated Learning for Distributed Data Mining, 2023b. URL https://openrevieer http::/www.tt.ooommmccccpppaaaa.
MJD Powell and Ya-xiang Yuan. A trust region algorithm for equality constrained optimization. Mathemat- ical Programmming, 49(1):189 211, 1991.
17

---

Published in Transactions on Machine Learning Research (05/2024)
Nicola Ricke, Jonny Hancox, Wenqi Li, Fausto Milletari, Holger R Roth, Shadi Albarqouni, Spyridon Bakas, Mathieu N Galtier, Bennett A Landman, Klaus Maier-Hein, Sébastien Ourselin, Micah Sheller, Ronald M Summers, Andrew Trask, Daguang Xu, Maximilian Baust, and M Jorge Cardoso. The future of digital health with federated learning. NPJ Digital Medicine, 3(1):119, 2020.
Philippe Rigollct and Xin Tong. Neyman-Pearson classification, convexity and stochastic constraints. Journal of Machine Learning Reseavch, 2011.
R Tyrrell Rockafellar. Augmented Lagrangians and applications of the proximal point algorithm in convex programming. Malhemalics of Operalions Research, 12))97--116, 1976.
R Tyrrell Rockafellar and Roger J-B Wets. Varialional Analysis, volume 317. Springer Science & Business Media, 2009.
Takaya Saito and Mare Rehmsmeier. The precision-recall plot is more informative than the ROC plot when evaluating binary classifiers on imbalanced datascts. PloS one, 10(3):c0118432) 2015.
Felix Sattler, Simon Wiedemann, Glaus-Robert Müller, and Wojeiech Samek. Robust and communication- efficient federated learning from non-IID data. IEEE Transactions on Neural Networks and Learning Systems, (9):334400-4411 2019.
Clayton Scott. Performance measures for Neymau-Pearson classification. IEEE Transactions on Information Theory, 53(8):2852 2863, 2007.
Zebang Shen, Juan Cervino, Hamed Hassani, and Alejandro Ribeiro. An agnostic approach to federated learning with class imbalance. In International Conference on Learning Representations, 2021.
Xin Tong, Yang Feng. and Anqi Zhao. A survey on Neyman-Pearson classification and suggestions for future research. Wiley Interdisciplinary Reviews: Compulational Statistics, 8(2):64-81, 2016.
Xin Tong, Yang Feng, and Jingyi Jessica Li. Neyman-Pearson classification algorithms and NP receiver operating characteristies. Science Advances, ((2):eax01659, 2018.
Quoc Tran Dinh, Nhan H Pham, Dzung Phan, and Lam Nguyen. FedDR randomnand Douglas- Rachford splitting algorithms for nonconvex federated composite optimization. In Advances in Neural Information Processing Systems, volume 34, pp. 30326 30338, 2021.
Yash Travadi, Le Peng, Xuan Bi, Ju Sun, and Mochen Yang. Welfare and fairness dynamics in federated learning: A client selection perspective. Statistics and Its Interface, 2023.
Andreas Wächter and Lorenz T Biegler. On the implementation of an interior-point filter line-search algo- rithm for large-scale nonlinear programming. Mathematical Programming. 106:25 57, 2006.
Jianyu Wang, Qinghua Liu, Hao Liang, Gauri Joshi, and Vincent Poor. Tackling the objective inconsistency problem in heterogencous foderated optimization. Advances in Neural Information Processing Systems, 33:7611 7623, 2020.
Pong Wang, Peng Lin, Wei Ron, and Yongduan Song. Distributed subgradient- based multiagent optimization with more general step sizes. IEEE Transactions on Automatic Control, (3()):2295-233) 2302, 2017.
Yangyang Xu. Iteration complexity of inexact augmented Lagrangian methods for constrained convex pro- gramming. Mathematical Progremming, 1e11-1992444 2021.
Tao Yang, Xinlei Yi, Junfeng Wu, Ye Yuan, Di Wu, Ziyang Meng, Yiguang Hong, Hong Wang, Zongli Lin, and Karl H Johansson. A survey of distributed optimization. Annual Reviews in Control, 47:278 305, 2019.
Wei Yao, Chengming Yu, Shangzhi Zeng, and Jin Zhang- Constrained bi-level optimization: Proximal Lagrangian value function approach and Hessian-free algorithm. In International Conference on Machine Learning, 2024.
18

---

Published in Transactions on Machine Learning Research (05/2024)
Deming Yuan, Shengyuan Xu, and Huanyu Zhao. Distributed primal-dual subgradient method for multiagent optimization via consensus algorithms. TEEE Transactions on Systems, Man, and Cybernelics, Part. B (Cybernetics), 41(6):1715 1724, 2011.
Honglin Yuan, Manzil Zaheer, and Sashank Reddi. Federated composite optimization. In International Conference Machine Learning, pp. 12253-12266. PMLR, 2021.
Junyu Zhang and Mingyi Hong. First-order algorithms without Lipschitz gradient: A sequential local optimization approach. INFORMS Journal on Optimization, 2024.
Xinwei Zhang, Mingyi Hong, Sairaj Dhople, Wotao Yin, and Yang Liu. FedPD: A federated learning framework with adaptivity to non-iid data. IEEE Transactions on Signal Processing, 69:6055 6070, 2021.
Shenglong Zhou and Geoffrey Ye Li. Federated learning via inexact ADMM. IEEE Transactions Pattern Analysis and Machine Intelligence, 2023.
Minghui Zhu and Sonia Martínez. On distributed convex oplimization under inequality and equality con- straints. IEEE Transactions on Automatic Control, 57(1):151 1641,114,111 2011.
Barret Zoph, Vijay Vasudevan, Jonathon Shlens, and Quoc Te. Learning transferable architectures for scalable image recognition. In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, pp. 8697 8710, 2018.
19

---

Published in Transactions on Machine Learning Research (05/2024)
Appendix
In Appendices A to C, we provide proofs of the main results in Scctions 3 and 4. Appendix D presents proximal AL method for centralized constrained optimization. In Appendix E, we include some extra numerical results.
A Proofs of Theorem 3.1, Lemma 3.1, and Theorem 3.2(a)
First, we set up the technical tools necessary for the proof, following Lu & Zhou (2023). With the abbrevi- ations in Eq. (6), we define the Lagrangian function associated with Eqs. (5) and (7) as
f(w) + h(w)) + (1, e(w))
if w E dom (h) and μ 2 0, if w E dom(h) and μ 2 0, if w g dom(h);
[w,
00
0
Then, verify that
V Vf(w) + @h(w) + Vo(w)/ (w)) NN (1)
if w E dom(h) and f 2 O,
alw p1)
(33)
otherwise.
We also define a set-valued operator T associated with Eqs. (5) and (7):
T: (w + {(u, R x R", (u,-v) (l(.,))) V(w, 14) E RR R"
(34)
which is maximally monotone (sce, c.g., Section 2 of Rockafellar (1976)). Finding KKT solution of Eq. (5) can be viewed as solving the monotone inclusion problem (Rockafellar, 1976):
Find (w, E Rd
T. such that (0,0) ((w,
(35)
Furthermore, applying the proximal AT method to solve Eq. (5) is equivalent applying the proximal point algorithm (PPA) to solve this monotone inclusion problem (Rockafellar, 1976; Bauschke & Combettes, 2017), that is,
k+1 arg min (w), nht = 1ut + (c(
(w--1, phtl) = J(w ,M), Vk 2 0, (36)
where (w.,p%) E dom(h) RT and J the resolvent of T defined
J -==
(37)
with I being the identity operator. When the arg min la (w) subproblem is only solved up to approximate stationarity, that is, dist (0, (l)(w(+)) S Ta as in our Algorithm 1, the error Tę will propagate to the next iterate that we obtain. This quantitatively captured by the following result.
Lemma A.1 (adaptation of Lemma 5 of Lu & Zhou (2023)). Suppose that Assumptions 0 to 2 hold. Let [w ph }220 be generated by Algorithm 1. Then for any k 2 0, we have
(1 +1) - J(w , S B B
where I is the resolvent T T defined in Eq. (37).
Proof. Notice from Eq. (10) that d0st(O, ( < Vndist (0, dl (wx+1)) $ VITu. By this and Lemma 5 of Lu & Zhou (2023), the conclusion of this lemma holds.
20

---

Published in Transactions on Machine Learning Research (05/2024)
A.1 Proof of Theorem 3.1
Proof of Theorem 3.1. Notice from Eqs. (6) and (9) that
1
(w) f(w) + h(w) +
2 (ll + Be(w)]+111 -11+1111)1111)))) +
2,3 11 u 11
By this, Eq. (33), and the fact that 1 = 1uth + Bo(w++2))+ one has
(lu(w+t))- (w wh) Vf(w+t1) + ah(wwtt) + Te( + Bc( (e(ww++)))
=Vf(w+t)) + ah(wwt)) + V ) Oal (ul(wttt 1,
(38)
Notice that
1 11th + Bo(w arg min || (1+ + Bc(w WEBT
By the optimality condition of this projection, we have which together with Eq. (33) implies that
E μ h+ (1+ + B)(w + NN (1 1,),
g (( - -+²)= Onlluttt (att)).
(39)
In view of this, Eqs. (10), (11) and (38), we can see that
Eq. (38)
dist (0, Ond (wt 1)+1))
dist 0l 00 (w++t)))
1 - 1l
+ ||
3
Eq. (10)
Fg. (11)
Tk +
B 11 - w* 1
2 61.
Eq. (39) 1
Eq. (11)
dist (0, wwt(w 1)
B glluttt - 101000
E2.
These along with Eq. (33) and Definition 1 imply that (w++1 11 an (21,e2)KKKT solution of Eq. (5),
which proves this theorem as desired.
A.2 Proof of Lemma 3.1
Define
w arg min (w),
r = lat + Bo(ww))+ vk 2 0.
(40)
which, by Eq. (36), is equivalent to
(w I (w p²
(41)
Recall that (w", ,4") is assumed to be any pair of optimal solutions to Eq. (5) and Eq. (7). Toward the proof, we first present an intermodiate result, which mostly follows the fact that J firmly nonexpansive.
Lemma A.2. Suppose that Assumptions to hold. Let {(w*, (ock,p") 1 be generated by Algorithm Let (wt,, ) be defined in Eq. (40) for all 2 0. Then the following relations hold.
I1 11²) - (w 11 + [1( ).:) - (1")2=)11 < I1( ,11²) -
Vk Vk
(42)
R-1
I1 ((=x,,²)) (w", "0,,,"")] S [[ ,20) (w* p , 3 n Σ Tj v 0.
(43)
21

---

Published in Transactions on Machine Learning Research (05/2024)
Proof. Since (w" ,p)) is solution to the monotone inclusion problem Eq. (35), we have
(0,0) T(w", """,,"") and (w", [ww", "w"),")"
(44)
Moreover, since T is maximally monotone, its resolvent I is firmly nonexpansive (see, e.g., Corollary 23.9 of Bauschke & Combettes (2017)), that is, [1, - -[w" ,r)l2 + II(I - [w,, (I- p()l = (1 (1) - x2)le for any feasible pains (w, (4) and (w', Using Eqs. (41) and (44), we obtain that
((w",,"" (w (==,,=1)1² p²)1
(wu,, ; m²) (w", ""'
Eqs. (41jand (44) 11(I (w 1/) (I (I- 1 1=) + +112++11100 I1 , -
$ [[("*, ,1*h (w" n 111 (firm nonexpansiveness of J)
Hence, Eq. (42) holds as desired. Now we prove Eq. (43). It suffices to consider the case where k 2 1. We have
[(w ,**) (w" ,-=' I1(w", ,,)) T(w || + (100 : 1 11--11 J(w", ,n''ll
S B 11( - (w" ,1²),:
(45)
where we have invoked Lemma A.1 and the nonexpansivenees of J to obtain the final upper bound. Re- peatedly applying Eq. (45) for iterates
through ( we have
k-1 B [1( 1,,,--,,1-1- 11-1)- (w" ;1 S B Σ
T3 + 11( ,00) -
(46)
==
completing the proof.
Proof of Lemma 3.1. Notice from Algorithm 1 that Th 8/(k + 1)² for all k 2 0. Therefore, one has Σs=o Ty I 28. In view of this, Eq. (15), and Lemma A.2, we observe that
max[Il** w"'l, 1| 1²l1, Ilw will, || w 113 ro + 2Vns88
Vk 2 0.
(47)
where is defined in Eq. (15), and 8 and s are inputs of Algorithm 1. Eq. (47) implics that wh E Qi for all k 2 0, completing the proof.
A.3 Proof of Theorem 3.2(a)
To prove Theorem 3.2(a), we first present general technical lemma the convergence rate of an inexact PPA applied to monotone inclusion problems.
Lemma A.3 (restatement of Lemma of Lu & Zhou (2023)). Let T R2 = R2 be maximally monotone operalor and z" E R such that E T(*). Let {2*} be a sequence generated by an ineract PPA, starting with zd and obtaining 2t1 by approzimately evaluating I (2**) such that
|| - [2* S ek
for some 8 > O and ex 2 0, where I = (I -1 and I is the identity operator. Then, for any K 2 1, we have
22 1120 - 2011 + 2
k= EN
min K<kS2K
VK
Proof of Theorem 3.2( Obscrve that Algorithm terminates when two consccutive iterates Tu4t,,pe+t and (w* ,p²) are close. We use this observation and Lemmas A.1 and A.3 derive the maximum number of outer iterations of Algorithm 1.
22

---

Published in Transactions on Machine Learning Research (05/2024)
28. Recall that Σド= Ty S 23. It follows from Lemmas A.1 and A.3 that
v2 (1(10) (10) (w" -1- + Σr= 73)
B Ill(uttt -patt) - (w ,1>)1| s
min K KSRS2K
BVK +1
v2 (Il(w", - (w", nl'I| + +V778))
V2 + 4v/33)
BVK+1
BVK K +1
which then implies that
min { Th 3 KSk
1
glloott1 w* 1100 5
8
(r + 4v
V2 + 4v
1
S 8
(K + 1)2
3vK+1
8
+K+I
V2 + 4/n38)
min K KSkS2K
z gllaAt1
10 S
3VK +1
We see from these and the termination criterion in Eq. (11) that the number of outer iterations of Algorithm 1 is al most.
Ka,.2 = 8 V2(ro + 4Vn533)
max (exx ((T,55)) = O(max (m (5)
(48)
8
Hence, Theorem 3.2(a) holds as desired.
B Proofs of the main results in Section
Throughout this section, we let (w","") be the optimal solution of Eq. (24), and A be the associated Lagrangian multiplier. Recall from the definition of up in Algorithm 2 and Eq. (21) that
पे ut + A/Pi, siss 2.
(49)
B.1 Proof of Lemma 4.1
For notational convenience, write fo(w)= = Then, by Eqs. (13) and (14), one can verify that
= V\) Ve((Wuu + Bc(())+ + (n + 1)B (w - w²), AA S i S n.
(50)
Proof of Lemma 4.1. Fix an arbitrary w E Rd and a bounded open set Uw containing w. We suppose that Vi is Two.--ipschitz continuous on Uw, and Ve, is Tw.g--ipschitz continuous on Uy Also, let Un.11 supwez,,, [ww](w]]| and U supwez. [[Ve;())]. By Eqs. (13), (14) and (50)) one has for each S i S n and E Uw that
Eq. (50) <
[VVia(u)) - (Pra(v))
[Vi(()) - VA+0 - + (c,(w)++1l
+ +1ll4* [c(()+++++++ - In + 3c (a)
(n + 1)33 11u ell
$ Lma - wll + (11411 || + AU ". 1 Lw. 2wwellu 1 v
1
+B]a(u)) (v(v)) Vc((v)l (n + 1).3 11 ---lll mll
1
< Ino,1 - ((1+f+ I| + BU,,. 1 Tow
BU2 w.2 +
||u al|-
(n + 1)5
Therefore, (u) is locally Lipschitz continuous Rd and the conclusion holds desired.
23

---

Published in Transactions on Machine Learning Research (05/2024)
B.2 Proof of Theorem 4.1
Proof of Theorem 4.1. In view of the lermination criterion Eq. (23), it sulfices to show that
dist (0, 0l( S E741 +
ELT+1.
By the definition of l in Eq. (16), one has that
ol( + = Σ VP((w + 0 (+1)
(51)
In addition, notice from Eqs. (18), (19) and (49) that
@ VPo + Σ (1= + 0h(w(+1)
V.olw + Σ 1pi(w - -ff) X + ah(w
VPi.T(W (11) VP( + + V1 sisn.
Combining these with Eq. (51), we obtain that
dl(w @ +2) + V ( p.
uf }/))]
which together with dist (0, I (w (+1) S ET+1 (see Algorithm and Eq. (22)) implics that (+ - pi T+1 - uu lloc
dist (0, (0..0(w=+11 S dist (0, (w (+1))
n
I ET+1 +
as desired.
B.3 Proof of Lemma 4.2
To prove Lemma 4.2, we use convergence analysis techniques for ADMM show that the distances between iterates (uthisss and w and the optimal solution w¹ are controlled by the distance between the initial iterate Th and wt To the best of our knowledge, such boundedness results without assuming global Lipschitz continuity are entirely new in the literature ADMM.
Proof of Lemma 4.2. From the optimality conditions and stopping criteria for Eq. (18) and Eq. (19), there exist et 's for 0 i isin n with |e I I Eeti and h++1 E ah(w"-1) so that:
x
+
VPo(w*+)) c11
pi(w+t1 - -it)
Fg. (49)
Poo 1011 +
[p u;) AM
Eq. (20)
VPol + +
Ipslut - utt) 1
(52)
1=1
and
11 Vyle(u((t)
Eq. [19 (19) VP((u(t)) + + +(((ttt =11 Eq. Eq__20) (20)
P. (11 + +
LA visiA n. (53)
24

---

Published in Transactions on Machine Learning Research (05/2024)
Moreover, since Ct and u² are the optimal solution of Eq. (24) with the associated Lagrangian multiplier X" E IR"", we have by the optimality condition that there exists he E @h(w") such that
VPi(u,)+ + O, Vo((w") + h"
x 0, un = visisn.
(54)
Recall that P;; S is n, are strongly convex with the modulus a > 0, we have
ollu** 11 - (u) ",, V..(ut V((("")
(strong convexity of P.)
(u, ~., - + x + ) (0" = u; VP((u;) = Mi, and Eq. (53))
I (w/t1 o², , - + x3 + ||u + / 1 + 20 1
((a s 1/21|a112 2 + 121) |6012 for all a, b Rd and 1> 0),
and
[1 S (w0+11 w., ( + +h4 -VPo(')) - h") (strong convexity of Po + h)
= (w w
12 2/- -pi ut)l + ) (Eq. (52) and Eq. (54))
I <(w't1 w. > D - - p((utt) w()) +
2 -gl - 10 ---1--01'"
- 1:= 1
1
20
1=1
((a, b) S 1/2 + 1 1/(21) for all a, b e Rd and 1> 0).
Summing up these inequalities and rearranging the terms, we obtain that
(1| -0=12 + | +1 111
2
, x 1+1 - \;- - -i(lttt - w()) + 1
w 11 - -
1 +
( (1) 4+1
.. -1,4 + +X2) +
|| 112)
20
20
i=1
i=1
+1
u
+1 , Xx y++ }3) + Σ p:(1ut1 -,, - u 21 +
1211 1
20 E1+1
2
i=1
1=1
(|cg+ S Eet1
for all 0 S i < n and 120)
Eq. (20)
Σ
1 (X - x 1 x + pi (1 -w;
w¹ un u
4+1
n2 + 1
2
(55)
20
E1+1
i=1
Notice that the following well-known identities hold:
(w - w² ut - u1 1-) = マ (1lu u 1122 - || - u/ + 11 ut/12 - 11:00 - -ug+-== 112)
(56)
(14-141, N -77> (112; 2/112= - 1|; - X 122 | - - 1(+2112).
(57)
These along with Eqs. (20) and (55) imply that
_ -11o0t1-0000 1 1/
| +1 20 113) Σ
n
Pi 110++1100 uu/112
n n 2
20 E1+
Eq. (55))
1
1
(2}
X
1+1 (+1 x3) + Σ
Pe pe( 111 -w0", ur u
1+1 +
2 |/ - -n(11²
Pi
i=1
1=1
Eq. (56)
n
(X}
x x r+1 -x;) + Σ
Ps (1100=
uf|1² - |100 - u/ ++ 1|2 + 1
2
i=1
1=1
25

---

Published in Transactions on Machine Learning Research (05/2024)
_q_ (20)
n
1
(2 X
x1) +
1
|1 1111
Pi
(1|03* -ntll 1|10=*
119)
Pi
2pi
2
i=1
i=1
i=1
Eq. (57)
(112
- x112 - |1 - 112 +
Σ
Pi
(1100 - u/ll - 11 u 11t1112)
2ps
2
==1
1=1
= -
12
Pi 2
100"
ut11²+ + 1 | 11139) - 11+5 - u,,t -11
u1,1112=
2p: 1 - - 1991
(58)
2p
Summing up this inequality over 1= o,.... T for any T 2 0, we obtain that
Ps 1 -n/l1= - n+ 1
| - w= +
|| - - 1/
+
20 1111
2
2
t=0
i=1
i=1
Pt :/ - -u912 + 2p:
|| - 2912)
Pt
-1 - up,
11 + _ 1| - 27 11-1
(59)
2
2p:
Recall from Algorithm that ē q', up - ,o and X = -VP((D)). Notice from Eq. (54) that w un and X (u,)), By these and Eq. (59), one can deduce that
2 (1luttt -w"1l= 3
+
++
w 131
2t
Pi
u2l1++ + - 2/1 11 - -2113)
20
2
2p.
1=1
1=0
1=1
5 20 (2)
n+1
+
Ps 100" -u 21 + 2p
|| - x912
2
i=1
n n+1
+
a
Pi 180"
w21 +
1
[|VP)(wT) VP((W))1))
20 q2)
2p
In view of this and the definition of Q in Eq. (29), we observe that w E Q and nf eQ for all t 2 0
and 1 sis n. Hence, the conclusion of this lemma holds as desired.
]
B.4 Proof of Theorem 4.2
We first prove an auxiliary recurrence result that will be used later.
Lemma B.1. Assume that r, c > 0 and q E 10. Let {arheo be sequence satisfying
(1+r)a++ S ae + ca V2
(60)
Then we have
1+1
- ) 4 2 O.
01+1 S max q [trl
ag + 1 1-
(61)
Proof. It follows Eq. (60) that
1
1
2t-
aq² 2
a+11 <
aj +
cg <
+
+
1 1+7 Itr
(1 + r)z
(1 + r)
r)
1+r
29
....5 (1 (1+r)04100
+
(1 (1+))+4 ao +
(1 + -111-
1=0
1=0
S (1+r)e+1 40 + mmaxx 9:
11rr
1=0
( < max 1/(1))1111111)11)11) + +)) and 1/(1 +
)
& 1/(1 1))(4--
26

---

Published in Transactions on Machine Learning Research (05/2024)
1
++1
(1 + r)++1 140
max
9: +r
1
1-g
9
< max
9:
au
+
1 1tr
1 1-6 q
Hence, Eq. (61) holds as desired.
The following lemma proves the Lipschitz contimuity of V.P on Q Lemma B.2. Let Q be defined in Eq. (29). Then there crists some Lvp > such that [VV.(u)) - VP(())I - Lvrllu- o|l, Vu,u
(62)
Proof. Notice from Eq. (29) that the set Q is convex and compact. By this and the local Lipschitz continuity of VP; on Rd one can verify that there exists some constant Lyp > such that Eq. (62) holds (see also Lemma 1 in Lu & Mei (2023)).
We introduce a potential function Se to measure the convergence of Algorithm 2:
S. : Σ Pi Illl" utll? + 2pt 11 - AEIP) v2 0. 2
(63)
The following lemma gives recursive result of S., which will play key role on establishing the global convergence rate for Algorithm/ 2 in Theorem 4.2.
Lemma B.3. Suppose that Assumptions 0 to 2 hold. Let tw 3220 and {u, ++1 hissn,02 be all the iterates generated by Algorithm 2. Then we have
].
n +
St S dt
So +
420
(64)
1-
20
21
where a and Lvp are given in Eq. (17) and Lemma B.2, respectively, a and Pi, S i S n, are imputs of Algoritim 2, and
{ 1
opi
4r = max
9:
r=
min Isisn
(65)
1+rr
1 + 2T PP
Proof. Recall from Eq. (58) that
n
S.
Σ
Pi |
2
+ -
|1 - x{(12)
2p:
(i +
|00""
u 1 112 + 2ps
|| - 1141 12
Pi
|w - u1(11
2 [|
-00112-
n 1
20 447
2
1=1
Pi + σ
|/00"
2 112 + 2p,
||; - x 1p) xpt1(p)
n2 +
20 Ex+1
(66)
2
i=1
Also, notice from Eqs. (53), (54) and (62) that
|| - 122 Eqs. (53)and (54)
Eq. (62)
(IVPP(W")) (P 11)
S - + 26
which implies that
||"0" us 12
2p
Pi "
-o0--uff 112 + 2p:
12 - x(-11p)
20
(67)
po + 2
p. + 212
27

---

Published in Transactions on Machine Learning Research (05/2024)
Plugging this into Eq. (66), have
St
Eq. (67)
1
Pi
Opi
21
Pi 111000
1 2px
| 12
n n 2r
20
9
Pi + 21 2
n+1
=1++))S++1
q²t
(r (r min pp/l +2
20
Pi + 2L
15
==1
When t= =0 Eq. (64) holds clearly. When 2 1, by the above incquality, Eq. (65), and Lemma B.1 with >i=1 p7 72110
(ar, = -Si, 2x
a+1
) we obtain that
St S max
So
n1 1+1
+
Σ
1
20
P5
21
1=1
71 +++1
6
So +
+
1
20
Pi
+
21
t=1
Therefore, the conclusion of this lemma is true as desired.
Proof of Theorem 4.2. Notice that Algorithm 2 terminates when Ea+1 + Ei= ε1,41 is small. Next, we show that this quantity is bounded by S, defined in Eq. (63) plus other small quantities, and then use Lemma B.3 to bound the maximum number of iterations of Algorithm 2.
By Eq. (22), and the fact that (V loo I Ea41 (see Algorithm 2), one can obtain that
E1T1 + Σ
Eq. (22)
Ec+1 +
[[ [V - p: - -,)]l
(u + م|ا Σ |1 (VVetttt Vecc(1t (1 + Σ pillw -
Sett1 +
(1lulloo S ||ll| for all u E Rd and the triangle inequality)
n
(n 1) + + wf wf Σ pillu u/il.
(68)
where the second inequality follows from
(19) S
(V -Vpal(ut |||
V [Vttttt)1) - - + -
- uut11
Eq. (62)
(Lop + pi) |10 utt 1
visisn. n.
Next, derive upper bounds for || - 2 || and pellwtt1 -2il, respectively. First, by Eqs. (58), (63)
and (64), we have
1 11
ut
112
110 - -
+ o gl - 10
2
2
Eq. (58)
Pi
u²/12 +
|| 1 + n +
6741
(69)
2
2pr
2x
i=1
n n+1
= St +
9"
(the definition S, in Eq. (63) and EL+1 = q² for all 2 0)
20
Eq. (64)
v d
So +
1
n 1
+
σ
+ n +
2
1 - 9
2x
p
+ 2L2
2
2a
i=1
28

---

Published in Transactions on Machine Learning Research (05/2024)
1/2
1/2
So +
1
n+1 1
+ -
+
+ 1
9
9
20
P
+
22
20
1=1
(a² b² I (a b)2 for all a.b2 0).
(70)
Using again Eqs. (58), (63) and (64), we obtain that
Pel //
Pi
++
- =)(13)
(Cauchy-Schwarz incquality)
2
2
i=1
Eq.
(68)
Ps)
Pi
|100
utl
+
| 11119)
+ 1 pi)
20 ++1
1
2
2
2p
im1
{=1
1
n1 + 2
p()
St
(the definition of St in Eq. (63) and Eat1 = q¹ for all t 2 0)
20
Eq. (64)
n
1
11+1 1
n
pi)
So +
q
q
20
P + 2L
20
1/2
1
Pi)
/2
So
1
n n+ 1
+
+
+ 1
9
q
2x
P
+ 22
20
1=1
i=1
(a² + b² S (a + b)2 for all a. b.b20.0 0).
(71)
Combining Eqs. (68), (70) and (71), obtain that
E+I +
Σ
n
E1441 S (n+ 1)q' +
Vo
2
n Σ
(LPP+P))
2 2
Pi
1/2
So
1
q
n n+1
20
n
p + 22
///2
+
V
+ 1 2a
9
2 8
12
s (n 1)q²/22
(Lop+ + pi)+ +
Pt
Vo
1/2
So +
n+1
Σ
n
0
T. + 1
9//2
1- 9
20
p 2L2pp
20
iml
(q S 9r S q. < 1).
(72)
Recall from Algorithm 2 and Eq. (54) that (9) = (w0, )))((tt))) and Ae = V P.("))) By these and Eq. (63), one has
So
1012 + VP:((")- -VP(""'-((((0')13
(73)
2
2p:
For convenience, denote
2
b =
Vo
(Le ps)
11 1=1
2 ">n0
Pi
1=1
1/2
Ps
10- 2
w0 + 2p:
1
VP:(k") - VP(((9)11)
+ 1-9
n n++1
+ Σ
0
2x
P 21
i=1
V
n +
+
2x
29

---

Published in Transactions on Machine Learning Research (05/2024)
Using this, Eqs. (72) and (73), we obtain that
1 + Eu41 S (n + 1 1+ b)g,
This along with the termination criterion in Eq. (23) implics that the number of iterations of Algorithm 2 is bounded above by
2 log(T/(n 1+1100 b))
+1= O([
(74)
log 4r
Hence, the conclusion of this theorem holds as desired.
We observe from the proof of Theorem 4.2 that under Assumptions 0 to 2, the number of iterations of Algorithm 2 is bounded by the quantity in Eq. (74).
C Proof of Theorem 3.2(b)
To establish the total inner-iteration complexity, we first show that all the inner iterates produced by Algorithm for solving all the subproblems of form Eq- (12) within Algorithm 1 are in a compact set (i.e., 22 later), and then estimate the Lipschitz modulus of V.,. for all S i S n and all over Q2. Then we can bound the inner-iteration complexity based on the size of Q2 and the Lipschitz modulus.
Boundedness of all inner iterates Recall from Eq. (15) that Q1 is compact set. Let
U sup max [V(())] WEQ 18i5
UVe = sup max WEE, OSi5n
[es Ue := sup max [[a(w)]. weD, osisn
(75)
Since Ví for all 1 < i < are locally Lipschitz, they are Lipschitz on @1 with some Lvf > 0. Similarly, Vc, for all 0 < i < n are Lispchitz on Qı with some modulus L > 0. Hence, VP,. for all 0 s is and all i are Lipschitz continuous on Q1:
Eq. (50) [V[(()) - VA(U))+ + 114 + [G.(w]++1]V Ve(v))l
[Ptx(u) - VPaa(v)ll
S
+ Il Bos(1))+++++ - Lut (BBc(v))
| ell
(n + 1)
Eq. (81)
T - r/| + (1143l + 11 - 1ill + BU.) Ivollu w- m||
1
+BU w|l
|/u w|l
(n + 1)3
Eg. (47)
-ep,illu-ol m|l
(76)
where
LPP.1= Log + [||x*||++r 2/728 + BU.)LV. + BU? + (n + 1)8
(77)
The next lemma says that all the inner iterates generated by Algorithm 2 stay in compact set.
Lemma C.1. Suppose that Assumptions 0 to hold and let (wh+t1) Jizo and ( Jisisna20 be all the inner ilerates generated by Algorithm 2 for solving the subproblems of form Eq. (12) in Algorithm 1. Then it holds that all these iterates stay in compact set Q2, where
(n + 1)332
72
u ve (ro + 2/788}3
Q2 u: u112 2
+ (n+ 1),3
Ps
+
VP.
(78)
(1 (1-92) q2)
Pi
and Lypn and 2i as defined in Egg. (77) and Egg. (15), respectively.
30

---

Published in Transactions on Machine Learning Research (05/2024)
Proof. Recall that for any k O, the subproblem in Eq. (12) has optimal solution w (see Eq. (40)), the initial iterate of Algorithm 2 for solving Eq. (12) is wt and Pi,k, 0 & S n, are strongly convex with modulus 1/[(n + 1).3. By Lemma 4.2 with (P,, n ,ū,o) ,0 = (Pi,e, w w", 1/l(m + 1)8)), we obtain that (w Jo20 k.1+1 ssgnn stay in set defined and {ug
12+1)880 (1-
pillo - u w1 + - [...(w.)) VPaa(w()1P) } P:
2 = v: 11 w11l
(n 1)3 Σ
Thus, to show the boundedness of all the inner iterates, it suffices to derive upper bounds for I| w*1l and ( - (P.,(("))) || that are independent of k. Since w², w E Q1, we have
IV VPax(w & Lopallu - ==
(79)
due to Eq. (76), where we note that Lvra is independent of k. Moreover, | w* S ro 2 from Eq. (47) provides a k-independent upper bound for | - w³ Thus, we have
Σ (aillut w012 - [IVP. VP(
(
LEP
(ro (ro 2 2
(80)
Pi
Finally, combining the above results and noting that w E Q1 completes the proof.
Lipschitz modulus of &.P for all 0 0 i S and all & over Q2 Let L be the Lipschitz constant of fa, ssisn, n, on 22, and Lv.2 be the Lipschitz constant of Vc,, 0 0 n, on Q2. Also, define
Uv
sup max wEQ, USi5n
U2 sup max ||q(w)]]. weQ, Usisn
(81)
Using similar arguments as for deriving LVp,1 in Eq. (77), we can see that VP.. 0 siis n, are Lipschitz continuous on Q2 with modulus Læp2 defined as
LVp2 L092 + (1)A") + ro + 2//38 (V22 + A (n + 1)3"
(82)
Proof of Theorem 3.2(b) Recall that Theorem 4.2 has established the number of iterations of Algo- rithm for solving each subproblem of Algorithm 1. In the rest of this proof, derive upper bound for the total number of inner iterations for solving all subproblems of Algorithm 1.
We see from Lemma C.1 that all iterates generated by Algorithm 2 for solving Eq. (12) lie in 22. Also, V.,. s n, are Lippscipschtzz continuous on 22. Therefore, by Theorem 4.2 with (T, o, LVp, w", ,,") (Tx, Pr,,, 1/s(nnn(nn/// (1)(n+1)))), L. wh, w²) and the discussion at the end of Appondix B.4, one has that the number of iterations of Algorithm for solving Eq. (12) during the k-th outer loop is no more than
2 llog(TA Tk / (n + + bx))
Tk =
+1
(83)
log gr
where
Pi (n + 1)5(p7 + +222 P2
Tr = max
=: min Isi5n
"1+7
by = 2 (n+ 22 1)3
Σ
Lop2+ +.) +
+1
2 2 pr)
1=1
1=1
Σ
Pi
" 2
- +1
1
[VPak(W - VPra(wo)))
2p:
31

---

Published in Transactions on Machine Learning Research (05/2024)
(n + 1)2B3
Σ ]+
R
1/2
11 3
+
+ (n
(n + 1)B3 iml P + 22 P.2
Plugging Eq. (80) into b, we have that by I b, where
b: 22((n (n + 1)3
Σ
(LVP2 P:)
2 Σ
Pi)
i=1
i=1
1/2
P
+ L.PA
1
(n + 1)
B 1 (n 1)
(ro + 2/T53)²
+ 1-
+
2pi
2
(n 1)3
i=1 Pi + 21
P.2
which is independent of k. By by I Th = 5/(k: + 1)? I Ken,e where Ken.z the upper bound for the number of outer iterations defined in Appendix A.3, and Eq. (83), one has that
2 log((n + 1 (K + 1)2/8)
T -
+ 1.
log(
Therefore, by Ken,a (f C2 22,,, one can see that the total number of inner iterations of Algorithm 1 is at most
K
Th S (Kerez +1) + b) ())((210(((+11 + 1122/8)
Σ k=
+1) Ö(maxfc (2)
(84)
log(g,
Hence, Theorem 3.2(b) holds as desired.
Algorithm 3 A centralized proximal AL method for solving Eq. (85)
Input: tolcrances ç,, 62 E 1), w E dom(h), 1a 2 0, nondecrcasing positive {TH hazo and B > 0.
for 0, 1,2,,... do Apply centralized solver to find approximate solution ++1 to:
min [a(w)= f(w) + h(w) + 23 (II + Sc(w)]+ -1 + 23 || w011
1
such that
dist (0, 10.00((w** S Tk.
Update the Lagrangian multiplier:
A+ lytt + Be(w )]+
Output (w1 1 ) and terminate the algorithm
x+1 1l + BT& S $6,,
11 - 11 S 9c2.
end for
D A centralized proximal AL method
In this part, we present a centralized proximal AL method (adapted from Algorithm 2 Lu Zhou (2023)) for solving the convex constrained optimization problem:
min f(w) + h(w) s. t. c(w) < 0,
(85)
where the function f dRd + R and the mapping e: Rd Rm are continuous differentiable and convex, and h is closed convex.
32

---

Published in Transactions on Machine Learning Research (05/2024)
E Extra Numerical Results
E.1 Dataset description for Neyman-Pearson classification
In this part, we describe the datasets for Neyman- Pearson classification in Section 5.1. "breast-cancer-veee 'adult-a', and 'monks-1' three binary classification datasets. We present the total number of samples for class 0 and class 1 and the number of features.
Table 3: Datasets for Neyman-Pearson classification
dataset
class 0/class
feature dimension
crner--ca
455/240
adult-a
24715/7840
21
monks-1
275/275
21
E.2 Linear equality constrained quadratic programming
In this subsection, we consider the linear equality constrained quadratic programming:
1 WTA.w A. u +ou+o bTw) s.t. Caw + d. = 0, Osisn,
min
(86)
where A; E Rdxd 15 < n, are positive semidefinite, b, E Rd 1 1 i n, C2 E R mid 0 n, and
de RR 0 sisn.
For each (d, n, m)) we randomly generate an instance of Eq. (86). In particular, for each isiS S n, we first generate random matrix A₁ by letting A, U,D.U?, where D; Badd is diagonal matrix. The diagonal entries of D; are generaled randomly from uniform distribution over [0.5, 1], and U; E Rdxd is randomly generated orthogonal matrix. We then randomly generate C, 0 < i n, with all entries drawn from a normal distribution with mean zero and a standard deviation of 1/vd. Finally, we generate bi, 1 isisn and d;, & < n as random vectors uniformly selected from the unit Euclidean sphere.
We apply Algorithm and cProx-AL (Algorithm 3) to find a (10-3, 100 -optimall solution of Eq. (86), and compare their solution quality. In particular, when implementing Algorithm 1, we exactly solve the quadratic subproblems in Eqs. (18) and (19). We run 10 trials of Algorithm 1 and cProx-AL, where for each run, both algorithms share the same initial point wo, randomly chosen from the unit Euclidean sphere. We set the
other parameters for Algorithm and cProx-AL as n = (O...., 0)2 4A < Eis iin, n, 5 = 0.1 and B = 10. We also set = 1 for each 1 < < n for Algorithm 2.
Table 4: Numerical results for Eq. (86) using our algorithm vs. using cProx-AL, Inside the parentheses are the respective standard deviations over 10 random trials.
objective value
feasibility violation
d
Algorithm
cProx-AL
relative difference
Algorithm
cProx-AL
100
1
-0.23 (4.65e-6)
-0.23 (2.38e-5)
1.63e-3 (1.01e-4)
3.33e-4
(1.14e-5)
5.68e-4 (2.82e-5)
1
300
3
-0.37 (2.74e-6)
-0.37 (1.32e-6)
1.01e-3 (3.51e-5)
3.52e-4
(1.44e-5)
4.45e-4
(1.70e-5)
500
5
-0.30 (1.36e-5)
-0.30 (7.54e-6)
1.34e-3
(4.62e-5)
4.38e-4
(5.36e-5)
3.85e-4
(1.05e-5)
100
1
9.81 (7.18e-5)
9.80 (1.46e-5)
1.09e-3
(7.96e-6)
1.34c-4
(9.02e-6)
8.03e-4
(1.57e-6)
5
300
3
8.47
(8. 120-5)
8.45 (1-30e-5)
1.36e-
(9.62e-6)
1.09e-
(1.31e-5)
8.28e-4
(1.98e-6)
500
5
9.92
(4.43o-5)
9.91 (4.87c-6)
8.26c-4 (4.27c-6)
1.33c-
(9.68c-6)
3.73c-4
(2.43e-7)
100
1
49.40 (9.02e-5)
49.37 (5.82e-6)
5.59e-4
(1.67e-5)
7.31e-5
(7.54e-6)
5.88e-4 4 (1.34e-7)
10
300
3
41.49 (7.04e-5)
41.44 (5.48e-6)
1.1e-3
(1.77e-6)
8.56e-5
(2.27e-7)
8.73e-4
(7.26e-6)
500
5
41.45 (2.25e-5)
41.41 (5.30e-6)
9.39e-4 (4.94e-7
9.29e-1
(2.55e-6)
7.66e-4 ( (1.37e-7)
33

---

Published in Transactions on Machine Learning Research (05/2024)
We observe that Algorithm 1 and cProx-AL capable of finding nearly feasible solutions, and achieve similar objective value. In view of the small standard deviations, we observe that the convergence behavior of Algorithm remains stable across 10 trial runs.
34


Reviews:
[{"review_id": "LDBjzVsZit", "reviewer": "Reviewer_TZnp", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strength:\n1. Detailed illustration on problem transformation to fit the federated structure\n2. First work in FL with general constraints with a systematical study\n3. The presentation is easy to follow.\n\n\nWeakness:\n1. I am a bit confused on your statement regarding you are the \"first result\" extending to local Lipschitz in related FL literature. Following your proof (e.g., Lemma B.2, Theorem 3.2(b)), the radius of the set $\\mathcal{Q}$ depends on many parameters like the number of client $n$, and accuracy $q$, basically I think they can be arbitrarily large (say high accuracy, or large client size), and you ask the local Lipschitz to **hold in every possible $\\mathcal{Q}\\subseteq\\mathbb{R}^d$ (i.e., $\\mathcal{Q}_1$ and $\\mathcal{Q}_2$)**. Also with the presence of $q$, I suspect possibly the corresponding Lipschitz constant $L_P$, can be very large, and I fear there is not a very significant difference compared to the common global Lipschitz assumption. Could you please provide more comments or insights on why such local Lipschitz is important?\n2. Even though claimed to be the first work in constrained FL problems, the proof strategy relies on the work of Lu & Zhou (2023), also there lacks a detailed discussion on how to understand the results, for example, a discussion on the sample/communication complexity based on Theorem 3.2 (i.e., setting detailed values of $\\epsilon_1$ and $\\epsilon_2$) will be helpful. \n3. Also you mentioned cProx-AL algorithm adapted from Lu & Zhou (2023), and applied it in the experiments. They derived the complexity is $O(\\epsilon^{-1}\\log\\epsilon^{-1})$, I am wondering whether cProx-AL algorithm you mentioned also enjoy the rate in FL regime, and how do you compare the (theoretical) rates between your algorithm and cProx-AL.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "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": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This work studied federated learning with functional constraints in convex regimes. Byproximal augmented lagrangian, authors proposed an algorithm to solve such FL problems, and further analyzed its complexities. Numerical experiments result reveals comparable performances with respect to centralized algorithms.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "1. Typo: \n   - Page 2, \"... patient privacy (, OCR)...\"\n2. My search shows that there is a recent work which also studied Lagrangian method with applications in constrained FL: *Yao, Wei, et al. \"Constrained Bi-Level Optimization: Proximal Lagrangian Value function Approach and Hessian-free Algorithm.\" arXiv preprint arXiv:2401.16164 (2024)* (in Appendix A.1.3, also they seems to be in bilevel problems which are more general than yours) or https://openreview.net/forum?id=xJ5N8qrEPl (more than 3 months earlier regarding their ICLR submission time stamp, but I agree the time relative to your TMLR submission is tricky). Would you mind commenting on it comparing to your work?", "broader_impact_concerns": "/", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "ThPlWziKqR", "reviewer": "Reviewer_VnvW", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "**Strengths:**\n\n+ The first two pages illustrate the significance of the investigated problem. Moreover, using the convergence metric inspired by Lu & Zhou (2023) adds originality to the results.\n\n**Weaknesses:**\n\n* The theoretical findings are not sufficiently exploited. The algorithm's parameters are not included in the results, and incorporating them could illustrate the influence of these parameters.\n\n* Some sections are more difficult to follow, e.g., the introduction of Eq~(9). Perhaps the author should add more discussion at this stage.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "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": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "The paper presents two algorithms for solving a Federated Learning (FL) problem under convex constraints. The authors motivate their approach with two practical applications and later demonstrate their efficiency through numerical simulations. Additionally, theoretical guarantees are provided to ensure the validity of their proposed methods.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "* The definition of a $(\\epsilon_1,\\epsilon_2)$-solution is interesting but differs from the classic measure of convergence for convex optimization algorithms. Can a broader discussion on the relevance of this metric be included?\n\n* The result of Theorem 3.1 is based on the assumption: \"If Algorithm 1 successfully terminates\". But can we check if this assumption is valid? Furthermore, Lemma 3.1 shows that the iterates are bounded. Clarity could be improved with the addition of an explanation of the importance of this result for studying the convergence of Algorithm 1.\n\n* Several parameters are introduced, such as $\\rho_i, \\epsilon_{i, t+1}, \\epsilon_{t+1}$. A recommendation on tuning these parameters could improve the practical aspect of the algorithms. Is there an optimal choice for these parameters, and how should they be chosen with a fixed iteration and communication budget?\n\n* [1] study the optimization of a similar FL problem (up to the Lagrangian dual transformation of Eq~5). Perhaps mentioning their work could be relevant.\n\n[1] Konstantin Mishchenko, Grigory Malinovsky, Sebastian Stich, Peter Richt\\'arik -- Proxskip: Yes! local gradient steps probably lead to communication acceleration! finally!", "broader_impact_concerns": "Including a discussion on potential societal impact does not seem relevant.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "11ewZzDRnH", "reviewer": "Reviewer_SQkm", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n\n- The paper is well-organized and the theoretical statements appears correct\n- The proposed method handles local constraints that can only be accessed locally without relying on projections\n- Relaxing global Lipschitz assumption to local Lipschitz appears to be new\n\nWeaknesses:\n\n- In its current form there are unnecessary overclaims concerning being first to address constrained problems in FL\n- The writing currently lacks proper comparison with existing literature\n\nSee requested changes below for details.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "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": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "- The work considers a federated learning problem with local inequality constraints (that can only be evaluated locally) and additionally a global nonsmooth term and global inequality constraint\n- They propose an inexact ADMM with verifiable termination criteria\n- They show that local Lipschitz of the local objectives and constraints are sufficient for establishing convergence of their method under convexity", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "Concerning lacking proper comparison to existing literature:\n\n- Most of the construction and proofs seems to rely heavily on the centralized proximal AL of (Lu & Zhou 2023) which handles constraints. I suggest spending more time comparing up front and stating how you extend the results (i.e. local Lipschitz and federated setting)\n- The application of inexact ADMM to federated learning has been proposed before (albeit without handling local constraints) [1,2,3,4] and the paper is not currently attributing proper credit.\n\nMy current understand is that the paper extends the results of (Lu & Zhou 2023) to a federated setting using a similar construction as [1], while relaxing the global Lipschitz condition to local Lipschitz. It would be very helpful to have this kind of comparison appear in the paper.\n\n\n[1] https://arxiv.org/pdf/2204.10607.pdf\n\n[2] https://www.ijcai.org/proceedings/2019/0629.pdf\n\n[3] https://arxiv.org/pdf/2204.03529.pdf\n\n[4] https://arxiv.org/pdf/2005.11418.pdf\n\n----\n\nConcerning overclaims:\n\nThe abstract claims that existing techniques \"only deal with unconstrained FL problems\". I would rephrase, since a proper comparison appears to be much more subtle than that. The work seems to specifically address the problem of _(private) local constraints for which the projection is not available or too expensive_. When projections are available constraints have been treated under federated composite optimization [5] and operator splitting approaches like Douglas-Rachford splitting [6,7,8].\n\n\nCurrently the text until page 2 suggests that the literature either does not handle constraints or at best treats very specific constraints such as class imbalance and fairness. Only under related work is it briefly mentioned that global and local constraints are treated but only when \"simple\".\nI suggest:\n\n- Specifying what is meant by \"simple\", since moving beyond \"simple\" is one of the main contributions. I would include a discussion as early as possible, but also after equation 5 would be a convenient place to address the difficulty of the local constraint considered.\n- I would mention previous work on constraint problems much earlier.\n\n[5] https://arxiv.org/pdf/2011.08474.pdf\n\n[6] https://arxiv.org/pdf/2011.08474.pdf\n\n[7] https://arxiv.org/pdf/2103.03452.pdf\n\n[8] https://proceedings.neurips.cc/paper/2020/file/4ebd440d99504722d80de606ea8507da-Paper.pdf\n\n-----\n\nMinor:\n\n- Appendix B.3 it is mentioned that \"To the best of our knowledge, such boundedness results without assuming global Lipschitz continuity are entirely new in the literature on ADMM.?\". It would be helpful to include references to local Lipschitz results in the centralized setting and explain what the main difficulty in extending it is.\n- It might be misleading to write \"establish its global linear convergence assuming strong convexity and locally Lipschitz continuous gradients.\" under contribution. If stepsizes are set appropriately my understanding is that the subproblem should be strongly convex when used as a subroutine in Algorithm 1. It would be good to mention that these assumptions are automatically satisfied under the convexity/smoothness assumption in Section 3.\n\n\n----\n\nI consider removing the overclaim important for recommending acceptance.", "broader_impact_concerns": "N/A", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "9ypcrTVKgP", "reviewer": "Reviewer_oLi8", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "I should acknowledge that I'm not from the ADMM community, so I can easily miss some important points. The problem considered is well-motivated and valid. Indeed, not many works analyze constrained optimization problems in the FL setting. The authors provided a good overview of the problem's current state. In general, the work looks promising and provides some insights to the ADMM community. I'll leave some questions that would help to understand the paper in more detail:\n1. It is clear that the constrained distribution problem is a somewhat old problem. There should be many previous baselines and approaches that tackle this problem. While the authors discuss some of them in the related work section, I would like to see a more detailed comparison with previous baselines. For instance, the authors provide Theorem 3.2. It would be nice if they compare this complexity result with previous ones.\n2. How do authors choose $\\rho_i$? Why does the convergence rate not depend on these parameters? When the authors call Alg.2 in Alg.1, they should specify input parameters. The same question is to other parameters, including $\\bar{s}, \\dots$\n3. Minor comment: Theorem 3.2 is slightly confusing. It provides complexity results for outer iterations and inner iterations of Alg.1, but I can see only one loop in Alg. 1. Is inner iterations of Alg.1 = iterations of Alg.2?", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "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": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "The paper considers distributed and federated learning optimization problems. Unlike many previous works, the authors focus their attention on problems with constraints. In this setup, they developed a new method based on the alternating direction method of multipliers (ADMM), proved convergence guarantees, and ran experiments that support their claims.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "-", "broader_impact_concerns": "-", "additional_comments": "", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: The authors have addressed most of the concerns raised by the reviewers. Therefore, the reviewers concur that the paper represents a valuable addition to the existing literature and recommend its acceptance. I am in agreement with this assessment.
Decision: Accept (poster)