# Generalized ADMM in Distributed Learning via Variational Inequality

Saeedeh Parsaeefard Alberto Leon Garcia
Electrical and Computer Engineering
University of Toronto
Toronto, ON., M4P 1A6
saeideh.fard, alberto.leongarcia @utoronto.ca

###### Abstract

Due to the explosion in size and complexity of modern data sets and privacy
concerns of data holders, it is increasingly important to be able to solve
machine learning problems in distributed manners. The Alternating Direction
Method of Multipliers (ADMM) through the concept of consensus variables is a
practical algorithm in this context where its diverse variations and its
performance have been studied in different application areas. In this paper,
we study the effect of the local data sets of users in the distributed
learning of ADMM. Our aim is to deploy variational inequality (VI) to attain
an unified view of ADMM variations. Through the simulation results, we
demonstrate how more general definitions of consensus parameters and
introducing the uncertain parameters in distribute approach can help to get
the better results in learning processes.

##  1 Introduction and Motivation

Applications of machine learning (ML) are proliferating in many areas, e.g.,
Internet of things, smart factories, and health. These applications are built
over highly distributed data gathering nodes, and the data sets are highly
complex and large scale. As a result, it is highly desirable that the
collection and storage of the data and accompanying algorithms be distributed.
Distributed approaches are also promote the privacy of end-users who do not
wish to share their data sets with third parties. In applied optimization
theory, there is a large body of work facilitating distributed learning, such
as primal-dual decomposition approaches, block-coordinate descent method, and
alternating direction method of multipliers (ADMM). The latter has a simple
but powerful structure (D.P. Bertsekas and Tsitsiklis, 1999; Boyd and et al.,
2011) where for a set of local data owners/users/nodes/machines, i.e,
$\mathcal{N}=\\{1,\cdots,N\\}$, the following optimization problem is
introduced

$\displaystyle\min_{(\textbf{w}_{n})_{n\in\mathcal{N}},\textbf{z}}\sum_{n\in\mathcal{N}}V_{n}(\textbf{w}_{n},\textbf{x}_{n},\textbf{y}_{n}),\,\,\,\,\,\,\text{Subject
to}:\,\,\,\text{C}1:\textbf{w}_{n}=\textbf{z},\,\,\,\forall n\in\mathcal{N},$
(1)

in which $\textbf{x}_{n}$ and $\textbf{y}_{n}$ are a feature set and a label
set of user $n$, $\textbf{w}_{n}$ is local model of user $n$, and z is a
common/consensus/global variable. This problem can be directly solved by its
own augmented Lagrangian approach or simply as a special case of the
constraint optimization problem Boyd and et al. (2011). ADMM is highly
relevant to other distributed approaches such as proximal point method,
projection method, and Douglas-Rachford splitting (Kumar et al., 2019). Since
ADMM can be fit into diverse categories of ML applications, it has been
studied from different perspectives, e.g., in (Boyd and et al., 2011; He et
al., 2018; Jung, 2021; Ling et al., 2016; Mota et al., 2013).

C1 in (1) is a tight constraint which causes slow convergence behavior of ADMM
algorithm, and consequently, leads to extra message overhead among server and
users. To overcome this implementation problem, there exist two main research
streams in this literature: 1) Developing quantization and hierarchical
methods, e.g., (Elgabli et al., 2020, 2020);2) Introducing relaxed versions of
the consensus constrain in ADMM, e.g., (França and Bento, 2016; Nishihara et
al., 2015; Ghadimi et al., 2015; Giselsson and Boyd, 2016). Following by the
former research trend, in this paper, we aim to introduce a more general
version of the consensus constraints in ADMM for distributed learning to speed
up the convergence rate. We also take into account the effect of distributed
data sets of users in the performance of ADMM which to the best of our
knowledge, has not been addressed in this literature. We introduce a worst
case representation of the objective function in (1) where the effect of
truncated /fragmented/local data sets of users is modeled as an unknown
function which its values fall into the bounded uncertainty region
(Parsaeefard et al., 2019).

Since there exists no closed form solution of our proposed generalized ADMM,
we use variational inequality (VI) (Facchinei and Pang, 2003) and arrive at a
unified view for studying the proposed problem. We show how the solutions of
ADMM in variations of the consensus constraints are related and how the worst
case robust representation of ADMM can help to justify the regularization
parameters in traditional approach. VI is also applied in (Chen et al., 2014)
for deriving divergence condition of ADMM, in (Wang and Zhao, 2019) for the
non-convex formulation of ADMM, and in (Du and Jiang, 2020) for the
convergence of ADMM with Bergman-distance formulation of C1 which can
generalized ADMM for proximal and quadratic constraints. In this work, we show
that VI can present an unified framework for study ADMM in general form of C1
without a need to have a closed form of mapping for the solution.

##  2  Problem Representation for Generalized ADMM

The intuition behind introducing generalized formulation of ADMM is to allow
users to search for the solution in a more flexible manner and study the
effect of local data set of users in a distributed setup. Consequently, we
introduce the generalized ADMM formulation as follows for all $n$ in
$\mathcal{N}$:

$\displaystyle\min_{(\textbf{w}_{n})_{n\in\mathcal{N}},\textbf{z}}\sum_{n\in\mathcal{N}}\max_{\textbf{f}_{n}(\textbf{w}_{-n},\textbf{x}_{-n},\textbf{y}_{-n})\in\Re_{n}(\textbf{w}_{-n})}\widetilde{V}_{n}(\textbf{w}_{n},\textbf{x}_{n},\textbf{y}_{n},\textbf{f}_{n}(\textbf{w}_{-n},\textbf{x}_{-n},\textbf{y}_{-n})),\,\,\,$
$\displaystyle\quad\quad\,\,\,\text{Subject
to}:\widetilde{\text{C1}}:\,\,\,g_{n}^{2}(\textbf{w}_{n},\textbf{z})\leq
0,\,\,\,g_{n}^{1}(\textbf{w}_{n},\textbf{z})=0,\,\,\,\forall n\in\mathcal{N},$

where
$\textbf{w}_{-n}=[\textbf{w}_{1},\cdots,\textbf{w}_{n-1},\textbf{w}_{n+1},\cdots\textbf{w}_{N}]$,
$\textbf{x}_{-n}=[\textbf{x}_{1},\cdots,\textbf{x}_{n-1},\textbf{w}_{n+1},\cdots\textbf{w}_{N}]$,
and
$\textbf{y}_{-n}=[\textbf{y}_{1},\cdots,\textbf{y}_{n-1},\textbf{y}_{n+1},\cdots\textbf{y}_{N}]$,
and

  * •

$g_{n}^{1}(\textbf{w}_{n},\textbf{z})$ and
$g_{n}^{2}(\textbf{w}_{n},\textbf{z})$ capture a more general relationship
between $\textbf{w}_{n}$ and z. For instance, $\widetilde{\text{C1}}$ can
include norm function $p$ as
$g_{n}^{2}(\textbf{w}_{n},\textbf{z})\quad\rightarrow\quad\|\textbf{w}_{n}-\textbf{z}\|_{p}^{p}\leq\varepsilon_{n}$
for all $n$ for $\varepsilon_{n}\geq 0$. This type of soft constraints can be
considered as an over relaxation of the consensus constraints of ADMM approach
(Chapter 3 in (Boyd and et al., 2011)). Another example is a group ADMM in
(Elgabli and et al., 2020) where the users are agree to fix their solutions
with their own neighbors, i.e., $\textbf{w}_{n}=\textbf{w}_{m}$ if
$m\in\mathcal{A}_{n}$ where $\mathcal{A}_{n}$ is the adjacent list of the node
$n$.

  * •

Due to the local data sets in distributed setup, the obtained weights in
learning process misses the relationship between data sets of users
(Parsaeefard et al., 2019). Since there is no statistics that shows this
effect, we need to define a new variable to model this relation through the
worst case robust optimization theory which includes three elements: I) A new
function to show the uncertainty coming from local data sets of users:
Consider $\textbf{f}_{n}(\textbf{w}_{-n},\textbf{x}_{-n},\textbf{y}_{-n})$
which is a function to model the uncertainty caused by local date sets of
users. Consequently, the cost function is also changed to
$\widetilde{V}_{n}(\textbf{w}_{n},\textbf{x}_{n},\textbf{y}_{n},\textbf{f}_{n}(\textbf{w}_{-n},\textbf{x}_{-n},\textbf{y}_{-n}))$
which includes
$\textbf{f}_{n}(\textbf{w}_{-n},\textbf{x}_{-n},\textbf{y}_{-n})$ as a new
variable; II) An uncertainty region i.e., $\Re_{n}(\textbf{w}_{-n})$ to shows
how $\textbf{f}_{n}(\textbf{w}_{-n},\textbf{x}_{-n},\textbf{y}_{-n})$ behaves:
This uncertainty function is mathematically represented as (Ben-Tal and
Nemirovski, 1999)

$\forall\,\textbf{w}_{-n},\textbf{x}_{-n},\textbf{y}_{-n},\,\,\,\,\,\exists\,\textbf{f}_{n}(\textbf{w}_{-n},\textbf{x}_{-n},\textbf{y}_{-n})\in\Re_{n}(\textbf{w}_{-n}),\,\,\forall
n\in\mathcal{N},$

and it means for any weights, feature sets, and label sets of all users, a
value of $\textbf{f}_{n}(\textbf{w}_{-n},\textbf{x}_{-n},\textbf{y}_{-n})$ is
limited in $\Re_{n}(\textbf{w}_{-n})$ which is a set-valued map. For our
problem, we do not have any knowledge about the form of
$\Re_{n}(\textbf{w}_{-n})$. In Section 3.1, we use linear function for
$\textbf{f}_{n}(\textbf{w}_{-n},\textbf{x}_{-n},\textbf{y}_{-n})$ and bounded
norm function for $\Re_{n}(\textbf{w}_{-n})$; III) A mapping to show how the
optimization problem should tackle the uncertain parameter: Definitely, by
increasing the value of
$\textbf{f}_{n}(\textbf{w}_{-n},\textbf{x}_{-n},\textbf{y}_{-n})$, loss
function increases. Therefore, under the worst-case or maximum condition of
$\textbf{f}_{n}(\textbf{w}_{-n},\textbf{x}_{-n},\textbf{y}_{-n})$ in
$\Re_{n}(\textbf{w}_{-n})$, the weights of the model should be derived. Based
on this view, the inner optimization problem of (2) is derived as

${\Phi_{n}}=\max_{\textbf{f}_{n}\in\Re_{n}(\textbf{w}_{-n})}\widetilde{V}_{n}(\textbf{w}_{n},\textbf{x}_{n},\textbf{y}_{n},\textbf{f}_{n}(\textbf{w}_{-n},\textbf{x}_{-n},\textbf{y}_{-n})),$

where $\Phi_{n}$ is a function of all weights of users and depends on the
bound of mathematical representation of $\Re_{n}(\textbf{w}_{-n})$. For the
sake of simplicity, we omit all the variables from the definition of this
function.

The difficulty of finding a solution for (2) is twofold: 1) the objective of
$\widetilde{V}_{n}(\textbf{w}_{n},\textbf{x}_{n},\textbf{y}_{n},\textbf{f}_{n}(\textbf{w}_{-n},\textbf{x}_{-n},\textbf{y}_{-n}))$
is intertwined an uncertain function (i.e.,
$\textbf{f}_{n}(\textbf{w}_{-n},\textbf{x}_{-n},\textbf{y}_{-n})$) and there
is not a well-defined tractable formulation for this objective function, 2)
the solution of each user from (2) depends on a shared variable z among all
users. To overcome these two challenges, we apply VI for studying the solution
of (2). VI has been successfully applied in the context of distributed
algorithm with shared constraints, e.g., in (Wang and Zhao, 2019; Chen et al.,
2014) and can handle an ambiguity in definition of cost function in (2) by
considering its centralized counterpart problem (Parsaeefard et al., 2017),
i.e.,

$\displaystyle\min_{\textbf{w},\textbf{z}}\sum_{n\in\mathcal{N}}V_{n}(\textbf{w},\textbf{x}_{n},\textbf{y}_{n}),\,\,\,\forall
n\in\mathcal{N},\,\,\text{Subject to}:\widetilde{\text{C1}},$ (3)

where w incorporates $\textbf{w}_{n}$ for all $n$.

##  3  Solution of Generalized ADMM

To study the solution of Generalized ADMM with VI, we first present some
preliminary definitions.

Definition of VI problem: Given a subset $\mathcal{K}$ of the Euclidean
$n$-dimensional space $\mathbb{R}^{n}$ and a mapping
$\mathcal{F}:\mathcal{K}\rightarrow\mathbb{R}^{n}$, the VI problem, denoted by
$VI(\mathcal{K},\mathcal{F})$, is to find a vector $\textbf{x}\in\mathcal{K}$
such that (Facchinei and Pang, 2003)
${(\textbf{y}-\textbf{x})^{T}\mathcal{F}(\textbf{x})\geq
0,\,\,\,\,\,\forall\textbf{y}\in\mathcal{K}.}$ Let the solution set of above
equation be $\text{SOL}(\mathcal{K},\mathcal{F})$. VI can represent the
solution of several standard constraint/non-constraint optimization problems,
equilibrium point of game theory, and complementarity problems. For instance,
if $\mathcal{K}$ is convex and the mapping $\mathcal{F}$ is the gradient of
real-valued function $f(\textbf{x})$, then
$VI(\mathcal{K},\mathcal{F}=\bigtriangledown f(\textbf{x}))$ represent a
necessary condition for optimality of the following optimization problem: find
$\textbf{x}^{*}\in\mathcal{K}$ such that $f(\textbf{x}^{*})\leq f(\textbf{x})$
for all $\textbf{x}\in\mathcal{K}$. In case that $\mathcal{K}$ includes
inequality and equations, i.e.,
$\mathcal{K}=\big{\\{}\textbf{h}(\textbf{x})\leq\textbf{0},\,\,\,\textbf{g}(\textbf{x})=\textbf{0}\,\,\,\forall
n\in\mathcal{N}\big{\\}},$ with
$\textbf{h}:\mathbb{R}^{n}\rightarrow\mathbb{R}^{l}$ and
$\textbf{g}:\mathbb{R}^{n}\rightarrow\mathbb{R}^{m}$ being vector-values
continuously differentiable functions. The following two statements are valid
[(Facchinei and Pang, 2003) Proposition 1.3.4.]: • Consider
$\textbf{x}\in\text{SOL}(\mathcal{K},\mathcal{F})$, under Abadie’s constraint
qualifications (Section 3.2 in Facchinei and Pang (2003)), there exist
positive vectors $\boldsymbol{\lambda}\in\mathbb{R}^{m}$ and
$\boldsymbol{\mu}\in\mathbb{R}^{l}$ such that
$\displaystyle\begin{array}[]{c}\textbf{0}=\mathcal{F}(\textbf{x})+\sum_{j=1}^{l}\lambda_{j}\bigtriangledown
h_{j}(\textbf{x})+\sum_{i=1}^{m}\mu_{i}\bigtriangledown
g_{i}(\textbf{x}),\,\,\forall n\in\mathcal{N},\\\
\textbf{0}=\textbf{g}(\textbf{x}),\,\,\,\,\textbf{0}\leq\boldsymbol{\lambda}\bot\textbf{h}(\textbf{x})\geq\textbf{0},\end{array}$
(6) where $\boldsymbol{\lambda}\bot\textbf{h}(\textbf{x})$ shows the
perpendicularity of $\boldsymbol{\lambda}\geq\textbf{0}$ and
$\textbf{h}(\textbf{x})$ where $\lambda_{j}\times h_{j}(\textbf{x})=0$. •
Conversely, if each function ${h}_{j}$ is convex and each function $g_{i}$ is
linear, and if $(\textbf{x},\boldsymbol{\lambda},\boldsymbol{\nu})$ satisfies
(6), then $\textbf{x}\in\text{SOL}(\mathcal{K},\mathcal{F})$.

We refer to (Kumar et al., 2019; Scutari et al., 2010) for more examples of
using VI. From these preliminaries, we study the solution of generalized ADMM
based on VI with the help of (3) as follows. Consider
$\textbf{w}=\\{\textbf{w}_{1},\cdots\textbf{w}_{N},\textbf{z}\\}$ and the
solutions of (2) and (3) as $\widetilde{\textbf{w}}$ and w, respectively.
Assume also following practical assumptions111 For the ease of presentation,
in the followings, we omit the arguments from
$\textbf{f}_{n}(\textbf{w}_{-n},\textbf{x}_{-n},\textbf{y}_{-n})$. However,
when we will explain about the concept, we add the arguments.:

  * •

A1) $V_{n}(\textbf{w}_{n},\textbf{x}_{n},\textbf{y}_{n},\textbf{f}_{n})$ is
smooth, $L$ Lipschitz continuous, and differentiable function of
$\textbf{w}_{n}$ with bounded gradients;

  * •

A2) $V_{n}(\textbf{w}_{n},\textbf{x}_{n},\textbf{y}_{n},\textbf{f}_{n})$ is
increasing, bounded differentiable with respect to $\textbf{f}_{n}$;

  * •

A3)
$\frac{\partial^{2}V_{n}(\textbf{w}_{n},\textbf{x}_{n},\textbf{y}_{n},\textbf{f}_{n})}{\partial\textbf{w}_{n}\partial\textbf{f}_{n}}$
exist and are continuous functions;

  * •

A4) Weights of users and z are bounded i.e.,
$\textbf{w}\in\textbf{W}_{n}\subseteq\mathbb{R}^{n}$;

  * •

A5) Higher order of derivatives of
$V_{n}(\textbf{w}_{n},\textbf{x}_{n},\textbf{y}_{n},\textbf{f}_{n})$ are
approximately zero.

The solution of generalized ADMM in (2) can be represented as a solution of
$VI(\widetilde{\mathcal{Q}},\widetilde{\mathcal{F}})$ where
$\widetilde{\mathcal{F}}=(\widetilde{\mathcal{F}}_{n})_{n\in\mathcal{N}}$ in
which
$\widetilde{\mathcal{F}}_{n}=(\frac{\partial\Phi(\textbf{w})}{\partial\textbf{w}_{n}})$
and

$\widetilde{\mathcal{Q}}=\prod_{n\in\mathcal{N}}\widetilde{\textbf{W}}_{n}\cap\big{\\{}g_{n}^{2}(\textbf{w}_{n},\textbf{z})\leq
0,\,\,\,g_{n}^{1}(\textbf{w}_{n},\textbf{z})=0\,\,\,\forall
n\in\mathcal{N}\big{\\}},$

where
$\widetilde{\textbf{W}}_{n}=\big{(}\textbf{W}_{n}\times\Re_{n}(\textbf{w}_{-n})\big{)}$.
Also, the solution of (3) can be represented as a solution of
$VI(\mathcal{Q},\mathcal{F})$ where
$\mathcal{F}(\textbf{w})=(\mathcal{F}_{n}(\textbf{w}))_{n\in\mathcal{N}}$,
$\mathcal{F}_{n}(\textbf{w})=\nabla_{\textbf{w}}V_{n}(\textbf{w})$ and
$\nabla_{\textbf{w}}V_{n}(\textbf{w})$ denotes the column gradient vector of
$V_{n}(\textbf{w})$ with respect to w; and

$\mathcal{Q}=\prod_{n\in\mathcal{N}}\textbf{W}_{n}\cap\big{\\{}g_{n}^{2}(\textbf{w}_{n},\textbf{z})\leq
0,\,\,\,g_{n}^{1}(\textbf{w}_{n},\textbf{z})=0\,\,\,\forall
n\in\mathcal{N}\big{\\}}.$ (7)

###  3.1 How to tackle Uncertain Parameters in Solution of generalized ADMM

Since $\textbf{f}_{n}(\textbf{w}_{-n},\textbf{x}_{-n},\textbf{y}_{-n})$ and
$\Re_{n}$ are unknown, it is not easy to determine a closed form or tractable
formulation for
$\widetilde{V}_{n}(\textbf{w}_{n},\textbf{x}_{n},\textbf{y}_{n},\textbf{f}_{n}(\textbf{w}_{-n},\textbf{x}_{-n},\textbf{y}_{-n}))$
and consequently, $\widetilde{\mathcal{F}}(\textbf{w})$. To overcome this
issue, we can apply two main approaches: I) Considering simplified assumptions
for the uncertainty region as well as the definition of cost functions with
uncertain parameters. For example, assume that
$\textbf{f}_{n}(\textbf{w}_{-n},\textbf{x}_{-n},\textbf{y}_{-n}))=\sum_{m\in\mathcal{N},m\neq
n}\alpha_{nm}\textbf{w}_{m}+\beta_{nm}$ where $\alpha_{nm}$ and $\beta_{nm}$
are uncertain parameters related to the correlation between the fragmented
data sets of users $n$ and user $m$ and

$\Re_{n}=\\{\textbf{f}_{n}=\frac{1}{2}(\boldsymbol{\alpha}_{-n}^{T}\textbf{w}_{-n}-\boldsymbol{\beta}_{-n})\,|\,\|\boldsymbol{\alpha}_{-n}\|_{p}\leq\varsigma_{n},+\|\boldsymbol{\beta}_{-n}\|_{p}\leq\delta_{n}\\},\quad
n\in\mathcal{N},$ (8)

where $\boldsymbol{\alpha}_{-n}$ and $\boldsymbol{\beta}_{-n}$ are two vectors
of all elements of $\alpha_{nm}$ and $\beta_{nm}$, respectively. If
$\widetilde{V}_{n}(\textbf{w}_{n},\textbf{x}_{n},\textbf{y}_{n},\textbf{f}_{n}(\textbf{w}_{-n},\textbf{x}_{-n},\textbf{y}_{-n}))$
can be decomposed for user $n$ parameters and
$\textbf{f}_{n}(\textbf{w}_{-n},\textbf{x}_{-n},\textbf{y}_{-n})$, by the
concept of protection functions, i.e., $\widehat{V}_{n}(\textbf{f}_{n})$, we
can have
$\widetilde{V}_{n}(\textbf{w}_{n},\textbf{x}_{n},\textbf{y}_{n},\textbf{f}_{n}(\textbf{w}_{-n},\textbf{x}_{-n},\textbf{y}_{-n}))\approx
V_{n}(\textbf{w}_{n},\textbf{x}_{n},\textbf{y}_{n},)+\widehat{V}_{n}(\textbf{f}_{n}(\textbf{w}_{-n},\textbf{x}_{-n},\textbf{y}_{-n}))$
for linear functions222 or,
$\widetilde{V}_{n}(\textbf{w}_{n},\textbf{x}_{n},\textbf{y}_{n},\textbf{f}_{n})\approx{V}_{n}(\textbf{w}_{n},\textbf{x}_{n},\textbf{y}_{n},)\times\widehat{V}_{n}(\textbf{f}_{n}(\textbf{w}_{-n},\textbf{x}_{-n},\textbf{y}_{-n}))$
for the log or exponential functions.. These assumptions leas to a more
tractable and closed form of both
$\widetilde{V}_{n}(\textbf{w}_{n},\textbf{x}_{n},\textbf{y}_{n},\textbf{f}_{n}(\textbf{w}_{-n},\textbf{x}_{-n},\textbf{y}_{-n}))$
and $\widetilde{\mathcal{F}}$. II) From A1-A4, we have following Lemma for
$\mathcal{F}$ and $\widetilde{\mathcal{F}}$ which helps us to study the
uniqueness condition of w and $\widetilde{\textbf{w}}$.

Lemma: When $\mathcal{F}$ is strongly monotone, $\widetilde{\mathcal{F}}$ is
strongly monotone for small value of $\varsigma_{n}$ and from A1-A5\. Proof:
See Appendix A in supplementary file $\square$.

From the above definitions, we study the existence and uniqueness solution of
ADMM.

Theorem 1: For any set of parameters and bounded uncertainty region from
A1-A4, there always exists a solution for
$VI(\widetilde{\mathcal{Q}},\widetilde{\mathcal{F}})$ and
$VI(\mathcal{Q},\mathcal{F})$. Therefore, (2) and (3) have a solution. Proof:
See Appendix B in supplementary file $\square$

While the existence condition is studied in a straightforward manner from the
definitions of VIs related to (2) and (3), the uniqueness condition is not
trivial since the uniqueness conditions depend on the nature of constraints.
To consider this point, we use KKT systems of VI for deriving the uniqueness
conditions. Consider $\textbf{g}^{2}$ and $\textbf{g}^{1}$ as the vectors of
all $g_{n}^{2}$ and $g_{n}^{1}$, respectively.The KKT condition system of
equations of (2) and (3) are, respectively,

$\displaystyle\begin{array}[]{c}\textbf{0}=\widetilde{\mathcal{F}}(\textbf{w})+\sum_{n\in\mathcal{N}}(\mu_{n}\bigtriangledown
g_{n}^{1}(\textbf{w}_{n},\textbf{z})+\lambda_{n}\bigtriangledown
g_{n}^{2}(\textbf{w}_{n},\textbf{z})),\,\,\forall n\in\mathcal{N},\\\
\textbf{C2}:\quad\textbf{0}=\textbf{g}^{1}(\textbf{w}_{n},\textbf{z}),\,\,\,\,\textbf{0}\leq\boldsymbol{\lambda}\bot\textbf{g}^{2}(\textbf{w}_{n},\textbf{z}))\geq\textbf{0},\end{array}$
(11)

and

$\displaystyle\begin{array}[]{c}\textbf{0}=\mathcal{F}(\textbf{w})+\sum_{n\in\mathcal{N}}\mu_{n}\bigtriangledown
g_{n}^{1}(\textbf{w}_{n},\textbf{z})+\lambda_{n}\bigtriangledown
g_{n}^{2}(\textbf{w}_{n},\textbf{z})\,\,\forall
n\in\mathcal{N},\quad\textbf{C2}.\end{array}$ (13)

(11) and (13) belong to MiCP and provide a set of necessary conditions which
should be satisfied for any solutions of
$VI(\widetilde{\mathcal{Q}},\widetilde{\mathcal{F}})$ and
$VI(\mathcal{Q},\mathcal{F})$, respectively. Consider
$(\boldsymbol{\lambda},\boldsymbol{\mu})$ satisfying (11) and (13) ; and
$\widetilde{\textbf{w}}$ and w are primal variables KKT points of (11) and
(13) , respectively. Now from Proposition 1.2.1 in (Facchinei and Pang, 2003),
w is a solution of (3) from $VI(\mathcal{Q},\mathcal{F})$ if there exist
$\boldsymbol{\mu}$ and $\boldsymbol{\lambda}$ holding (13). Similarly,
$\widetilde{\textbf{w}}$ is a solution of (2) from
$VI(\widetilde{\mathcal{Q}},\widetilde{\mathcal{F}})$ if there exist
$\boldsymbol{\mu}$ and $\boldsymbol{\lambda}$ holding $\textbf{C}2$. This
relation helps us to study the uniqueness condition of general ADMM where
associated with $VI(\mathcal{Q},\mathcal{F})$ and
$VI(\widetilde{\mathcal{Q}},\widetilde{\mathcal{F}})$. The solution of (11)
and (13) can be represented as tuples
$\widetilde{\boldsymbol{\varkappa}}=[\widetilde{\textbf{w}},\boldsymbol{\lambda},\boldsymbol{\mu}]$
and
$\boldsymbol{\varkappa}=[\textbf{w},\boldsymbol{\lambda},\boldsymbol{\mu}]$,
respectively. Now we define two following mappings

$\displaystyle\widetilde{\mathcal{F}}^{\text{Lagrange}}(\widetilde{\boldsymbol{\varkappa}})=\left(\begin{array}[]{c}\widetilde{\mathcal{F}}(\textbf{w})+\mathcal{G}^{1}\boldsymbol{\mu}^{T}+\mathcal{G}^{2}\boldsymbol{\lambda}^{T}\\\
\textbf{g}^{1}\\\
\textbf{g}^{2}\end{array}\right),\,\,\text{and}\,\,\mathcal{F}^{\text{Lagrange}}(\boldsymbol{\varkappa})=\left(\begin{array}[]{c}\mathcal{F}(\textbf{w})+\mathcal{G}^{1}\boldsymbol{\mu}^{T}+\mathcal{G}^{2}\boldsymbol{\lambda}^{T}\\\
\textbf{g}^{1}\\\ \textbf{g}^{2}\end{array}\right)\,\,$ (20)

where $\mathcal{G}^{1}$ and $\mathcal{G}^{2}$ are the vectors of
$\bigtriangledown g_{n}^{1}(\textbf{w}_{n},\textbf{w})$ and $\bigtriangledown
g_{n}^{2}(\textbf{w}_{n},\textbf{w})$, respectively.
$\widetilde{\mathcal{F}}^{\text{Lagrange}}(\widetilde{\boldsymbol{\varkappa}})$
and $\mathcal{F}^{\text{Lagrange}}(\boldsymbol{\varkappa})$ can be used to
define a new mapping between the primal and Lagrange variables which can be
used to study the uniqueness conditions of $\widetilde{\textbf{w}}$ and w.

###  3.2 Simplified Version for Linear Constraints

Another important advantage to use VI is that it is simplified when
$\textbf{g}^{1}=\textbf{d}-\textbf{C}\textbf{w}$ and
$\textbf{g}^{2}=\textbf{b}-\textbf{A}\textbf{w}$. In this case,
$\mathcal{F}^{\text{Lagrange}}$ and
$\widetilde{\mathcal{F}}^{\text{Lagrange}}$ are transformed into

$\displaystyle\mathcal{F}^{\text{Linear}}(\boldsymbol{\varkappa})=\underbrace{\left(\begin{array}[]{c}\textbf{0}\\\
\textbf{d}\\\
\textbf{b}\end{array}\right)}_{\textbf{m}}+\underbrace{\left(\begin{array}[]{ccc}\mathcal{F}&\textbf{C}^{T}&\textbf{A}^{T}\\\
-\textbf{C}^{T}&\textbf{0}&\textbf{0}\\\
-\textbf{A}^{T}&\textbf{0}&\textbf{0}\end{array}\right)}_{\textbf{M}}\boldsymbol{\varkappa}^{T},\,\widetilde{\mathcal{F}}^{\text{Linear}}(\widetilde{\boldsymbol{\varkappa}})=\textbf{m}+\underbrace{\left(\begin{array}[]{ccc}\widetilde{\mathcal{F}}&\textbf{C}^{T}&\textbf{A}^{T}\\\
-\textbf{C}^{T}&\textbf{0}&\textbf{0}\\\
-\textbf{A}^{T}&\textbf{0}&\textbf{0}\end{array}\right)}_{\widetilde{\textbf{M}}}\boldsymbol{\varkappa}^{T},$
(30)

where M and $\widetilde{\textbf{M}}$ can be rewritten as
$\textbf{M}=\textbf{M}_{1}+\textbf{M}_{2}$ and
$\widetilde{\textbf{M}}=\widetilde{\textbf{M}}_{1}+\textbf{M}_{2}$ where

$\textbf{M}_{1}=\left(\begin{array}[]{ccc}\mathcal{F}&\textbf{0}&\textbf{0}\\\
\textbf{0}&\textbf{0}&\textbf{0}\\\
\textbf{0}&\textbf{0}&\textbf{0}\end{array}\right),\,\,\,\widetilde{\textbf{M}}_{1}=\left(\begin{array}[]{ccc}\widetilde{\mathcal{F}}&\textbf{0}&\textbf{0}\\\
\textbf{0}&\textbf{0}&\textbf{0}\\\
\textbf{0}&\textbf{0}&\textbf{0}\end{array}\right),\,\,\,\,\,\,\textbf{M}_{2}=\left(\begin{array}[]{ccc}\textbf{0}&\textbf{C}^{T}&\textbf{A}^{T}\\\
-\textbf{C}^{T}&\textbf{0}&\textbf{0}\\\
-\textbf{A}^{T}&\textbf{0}&\textbf{0}\end{array}\right)$

in which $\textbf{M}_{2}$ is a skew-symmetric matrix. For instance, for
$\textbf{w}_{n}=\textbf{z}$, we have
$\textbf{z}=-\frac{1}{N}\sum_{n\in\mathcal{N}}\textbf{w}_{n}$ (Boyd and et
al., 2011). Hence, C is an $N\times N$ matrix $[C]_{nm}=1-\frac{1}{N}$ for
$m=n$ and $[C]_{nm}=\frac{1}{N}$ for $m\neq n$. For group ADMM in (Elgabli and
et al., 2020), C is $N\times N$ is matrix where $[C]_{nm}=1$ for $m=n$,
$[C]_{nm}=-1$ for $m\neq n$ and $n\in\mathcal{A}_{n}$, and $[C]_{nm}=0$,
otherwise. For both of these two cases, the study of the existence,
uniqueness, and convergence of distributed algorithms depends on the features
of $\mathcal{F}$ in ADMM and not the linear matrices.

Applying VI in ADMM also helps us to study any variation of ADMM including
adding any additional terms to the cost functions, for example (to punish or
optimize the relaxation parameters, e.g., $\varepsilon_{n}$) or any new
constraints and variables, and make a connection between solution of
simplified form and its divergence. Therefore, we get a unified view for study
the solution of ADMM for different scenarios.

##  4 Uniqueness Conditions of GADMM and Distributed Algorithms

We first focus on the case that $\boldsymbol{\lambda}$ and $\boldsymbol{\mu}$
are fixed. This is interesting in a sense that it leads to a practical
formulation of augmented Lagrange formulation in ADMM scenario and can be
considered as a first step for the scenario where the values of Lagrange
multipliers are adjusted dynamically.

###  4.1 Fixed Lagrange Multipliers

For this case, the constraints of the KKT systems in (7) and (8) are
eliminated and we have
$\mathcal{F}^{\text{Fixed}}(\textbf{w})=\mathcal{F}(\textbf{w})+\sum_{n\in\mathcal{N}}\left(\mu_{n}\bigtriangledown
g_{n}^{1}(\textbf{w}_{n},\textbf{z})+\lambda_{n}\bigtriangledown
g_{n}^{2}(\textbf{w}_{n},\textbf{z})\right)$, and
$\widetilde{\mathcal{F}}^{\text{Fixed}}(\textbf{w})=\widetilde{\mathcal{F}}(\textbf{w})+\sum_{n\in\mathcal{N}}\left(\mu_{n}\bigtriangledown
g_{n}^{1}(\textbf{w}_{n},\textbf{z})+\lambda_{n}\bigtriangledown
g_{n}^{2}(\textbf{w}_{n},\textbf{z})\right)$, which can represent two
following optimization problems :

$\min_{(\textbf{w}_{n})_{n\in\mathcal{N}}\in\textbf{W}}\sum_{n\in\mathcal{N}}\left(V_{n}(\textbf{w},\textbf{x}_{n},\textbf{y}_{n})+\mu_{n}g_{n}^{1}(\textbf{w}_{n},\textbf{z})+\lambda_{n}g_{n}^{2}(\textbf{w}_{n},\textbf{z})\right),$
${\min_{(\textbf{w}_{n})_{n\in\mathcal{N}}\in\textbf{W}}\sum_{n\in\mathcal{N}}\left(\max_{\widehat{\textbf{f}}_{n}\in\Re_{n}(\textbf{w}_{-n})}\widetilde{V}_{n}(\textbf{w}_{n},\textbf{x}_{n},\textbf{y}_{n},\textbf{f}_{n}(\textbf{w}_{-n},\textbf{x}_{-n},\textbf{y}_{-n}))+\mu_{n}g_{n}^{1}(\textbf{w}_{n},\textbf{z})+\lambda_{n}g_{n}^{2}(\textbf{w}_{n},\textbf{z})\right)},$

respectively. These two optimization problems show that (2)and (3) are
transformed into optimization problems with the objective to minimize the cost
function plus the pricing parts (fixed Lagrange multipliers multiplied by
$\textbf{g}_{1}$ and $\textbf{g}_{2}$). Therefore, the related optimization
problems are simplified and their related VI mappings are changed to
$VI(\textbf{W},\mathcal{F}^{\text{Fixed}})$ and
$VI(\widetilde{\textbf{W}},\widetilde{\mathcal{F}}^{\text{Fixed}})$.

Theorem 2: For a given $\boldsymbol{\lambda}\geq\textbf{0}$ and
$\boldsymbol{\mu}\geq\textbf{0}$, when $\varsigma_{n}$ is small and
$g_{n}^{1}$ is linear and $g_{n}^{2}$ is convex function,
$VI(\textbf{W},\mathcal{F}^{\text{Fixed}})$ and
$VI(\widetilde{\textbf{W}},\widetilde{\mathcal{F}}^{\text{Fixed}})$ have
unique solutions if $\mathcal{F}(\textbf{w})$ is strongly monotone. Proof:
See Appendix C in supplementary file $\square$.

For this scenario, the iterative prototype algorithm based on the proximal
response point can be applied as presented in Algorithm 1 (Palomar and Eldar,
2010). In proximal point method, for any $\textbf{w}_{n}\in\mathcal{Q}$, the
solution of

$\textbf{w}_{n}^{t}=\min_{\textbf{w}_{n}}\widetilde{V}_{n}(\textbf{w}_{n},\textbf{x}_{n},\textbf{y}_{n},\textbf{f}_{n})+\mu_{n}\bigtriangledown
g_{n}^{1}(\textbf{w}_{n},\textbf{z})+\lambda_{n}\bigtriangledown
g_{n}^{2}(\textbf{w}_{n},\textbf{z})+\underbrace{\frac{1}{2}\|\textbf{w}^{t}_{n}-\textbf{w}^{t-1}_{n}\|}_{\text{Proximal
term}}.$ (31)

For z, the similar proximal term can be considered. This algorithm is based on
the sequential distributed algorithm where all users starts to solve their
problems by sending their solution back to the centralized cloud. With a very
slight modification, this algorithm can be applied for the server-less
algorithm.

Table 1: Proximal Point Method for GADMM with Fixed and Variable Lagrange Multipliers  | Algorithm 1
---
Step 0: For given $\boldsymbol{\lambda}$, $\boldsymbol{\mu}$, and
$\textbf{z}^{0}$, $0<\zeta<<1$, $t=0$
Step 1: 1.1) Users update $\textbf{w}_{n}^{t+1}$ from (31)
1.2) Each user sends its $\textbf{w}_{n}^{t+1}$ to the server
Step 2: The server updates $\textbf{z}^{t+1}$ and sends to users
If $\|\textbf{w}^{t-1}-\textbf{w}^{t}\|_{2}\leq\zeta$, End;
Otherwise $t=t+1$, continue;
| Algorithm 2
---
Step 0: For given $0<\zeta,\tau<<1$, $\textbf{z}^{0}$, $t=0$,
Step 1.1 ) similar to Algorithm 1
Step 1.2) similar to Algorithm 1
1.3) Update $\boldsymbol{\lambda}^{t}$ and $\boldsymbol{\mu}^{t}$
from one of (34) to (36)
Step 2: Similar to Algorithm 1

Consider the norm 2 uncertainty region in (8) with the linear regression cost
function and $\textbf{C}1$ for ADMM from (1), the protection function against
$\textbf{f}_{n}$ is $\varsigma_{n}\|\textbf{w}_{-n}^{t}\|_{2}^{2}+\delta_{n}$
for each user $n$, and the optimization problem of proximal response map for
each user $n$ can be rewritten

$\displaystyle
V_{n}^{\text{Proxi}}=\underbrace{\frac{1}{2}(\textbf{x}_{n}^{T}\textbf{w}_{n}^{t}-\textbf{y}_{n})}_{V_{n}(\textbf{w}_{n},\textbf{x}_{n},\textbf{y}_{n})}+\underbrace{\mu_{n}(\textbf{w}_{n}^{t}-\textbf{z})}_{\text{ADMM
Constraint}}+\underbrace{\varsigma_{n}\|\textbf{w}_{-n}^{t}\|_{2}^{2}+\delta_{n}+\frac{1}{2}\|\textbf{w}_{n}^{t}-\textbf{w}_{n}^{t-1}\|_{2}^{2}}_{\text{Regularization
Paramter}}.$ (32)

(32) is an augmented version of ADMM via the weights of each user as well as
the other users and $\varsigma_{n}$ and $\delta_{n}$. (32) highlights that
with representation of distributed learning via worst case optimization theory
based on ADMM and proximal response method, the utilization of regularization
factor in ADMM approach can be supported. With different definition of
uncertainty region, we obtain a different regularization factor. Hence, this
representation mathematically supports applying regularization factors in ADMM
to reach the better solutions. Convergence conditions of Algorithm 1 are
presented in Appendix D in supplementary file.

###  4.2 Variable Lagrange Multipliers

For this scenario, we just focus on $\boldsymbol{\lambda}$ for the sake of
notation simplicity. The followings can be easily extended with considering
$\boldsymbol{\mu}$ as well. Therefore, we study that under which condition for
the unique solution of w, there is a solution for $\boldsymbol{\lambda}$ which
hold KKT systems for both (3) and (2), and $\boldsymbol{\lambda}$ is a
solution of

$\displaystyle\text{NCP}:\quad\textbf{0}\leq\boldsymbol{\lambda}\perp\textbf{g}^{2}(\bar{\boldsymbol{\varkappa}})\geq\textbf{0},$
(33)

where $\bar{\boldsymbol{\varkappa}}=\\{\textbf{w},\boldsymbol{\mu}\\}$. To
study this uniqueness conditions for $\bar{\boldsymbol{\varkappa}}$ and
$\boldsymbol{\lambda}$, consider
$\boldsymbol{\gamma}(\boldsymbol{\lambda})=\mathcal{G}^{2}\boldsymbol{\lambda}^{T}$
and define a mapping $\boldsymbol{\phi}$ as
$\boldsymbol{\phi}:\,\,\boldsymbol{\lambda}\rightarrow\textbf{g}^{2}(\bar{\boldsymbol{\varkappa}},\gamma(\boldsymbol{\lambda}))$.
For this scenario, we need to show that under which condition
$\boldsymbol{\phi}$ is co-coercive function of $\boldsymbol{\lambda}$ with
constant $c_{\text{coc}}(\boldsymbol{\phi})$ where
$\big{(}\boldsymbol{\lambda}^{1}-\boldsymbol{\lambda}^{2})^{T}(\boldsymbol{\phi}(\boldsymbol{\lambda}^{1})-\boldsymbol{\phi}(\boldsymbol{\lambda}^{2}))\geq
c_{\text{coc}}(\boldsymbol{\phi})\|\boldsymbol{\phi}(\boldsymbol{\lambda}^{1})-\boldsymbol{\phi}(\boldsymbol{\lambda}^{2})\|_{2}^{2}$.

Theorem 3: If $\mathcal{F}$ is strong monotone, the solution of
$VI(\mathcal{Q},\mathcal{F})$ and
$VI(\widetilde{\mathcal{Q}},\widetilde{\mathcal{F}})$ are unique and it must
be
$\textbf{w}^{VI}=\textbf{w}^{*}(\boldsymbol{\gamma}(\boldsymbol{\lambda}^{\text{NCP}}))$
and
$\widetilde{\textbf{w}}^{VI}=\widetilde{\textbf{w}}^{*}(\boldsymbol{\gamma}(\boldsymbol{\lambda}^{\text{NCP}}))$.
There is a convex solution set for $\boldsymbol{\lambda}$. Proof: See Appendix
E in supplementary file. $\square$

####  4.2.1 Distributed Algorithms to Solve (33)

One scheme of a distributed algorithm for (33) is presented in Algorithm 2
which is based on the primal-dual update variables. First, server each user
updates its own local variable $\textbf{w}_{n}$ based on initial values of
$\textbf{z}^{0}$ . Then, each user should update the Lagrange multipliers
which involves different implementation challenges such as: 1) The signaling
required between server and users to pass required information, 2) The
computational burden for calculating $\boldsymbol{\lambda}$, 3) The
convergence speed, 4) The convergence analysis, 5) The sensitivity of the
solution for $\boldsymbol{\lambda}$ to the step-size. Based on the definition
of consensus general constraints in our setup, e.g.,
${g}_{n}^{1}(\textbf{w}_{n},\textbf{z})$ and
${g}_{n}^{2}(\textbf{w}_{n},\textbf{z})$, each user can update
$\lambda_{n}^{t}$ and $\mu_{n}^{t}$. However, computational complexity and
choosing the step size for updating these parameters are important for
$\textbf{w}^{t}$. We study some of the famous approaches to update the
Lagrange multiplier as follows (Facchinei and Pang, 2003; Pang et al., 2010).

  * •

Projection Algorithm with random variable step where $\boldsymbol{\lambda}$
are updated as follows

$\displaystyle\boldsymbol{\lambda}^{t}=[\boldsymbol{\lambda}^{t-1}-\tau\boldsymbol{\phi}(\boldsymbol{\lambda})]^{+},$
(34)

where to guarantee the convergence of the algorithm, $0\leq\tau\leq 2\times
c_{\text{coc}}(\boldsymbol{\phi})$ (Theorem 12.1.8 in (Facchinei and Pang,
2003))). Since this value usually cannot be attained in a distributed setup,
very small value for $\tau$ is considered with the cost of slow convergence
rate. The positive side of this approach is that it does not involve high
computational complexity.

  * •

The Hyperplane Projection Algorithm is proposed to handle the difficulty of
choosing the value of $\tau$ in the projection mapping. This algorithm has
three steps to update the Lagrange multipliers:

    1. 1.

Compute
$\boldsymbol{\lambda}^{(t-1)+\frac{1}{4}}=[\boldsymbol{\lambda}^{t-1}-\boldsymbol{\phi}(\boldsymbol{\lambda})]^{+}$.

    2. 2.

Compute
$\boldsymbol{\lambda}^{t-\frac{1}{2}}=\boldsymbol{\lambda}^{t-1}+2^{-l_{n}}(\boldsymbol{\lambda}^{(t-1)+\frac{1}{4}}-\boldsymbol{\lambda}^{t-1})$
where $l_{n}$ is the smallest positive integer $l$ where $\tau=2^{-l}$, and
for $\delta\in(0,1)$, we have
$[\boldsymbol{\lambda}^{t-1}-\boldsymbol{\lambda}^{(t-1)+\frac{1}{4}}]\boldsymbol{\phi}(\boldsymbol{\lambda}^{t-1}-\tau(\boldsymbol{\lambda}^{t-1}-\boldsymbol{\lambda}^{(t-1)+\frac{1}{4}})\geq\delta\|\
\boldsymbol{\lambda}^{t-1}-\boldsymbol{\lambda}^{(t-1)+\frac{1}{4}}\|$.

    3. 3.

Update

$\boldsymbol{\lambda}^{t}=\big{[}\boldsymbol{\lambda}^{t-1}-\frac{[\boldsymbol{\lambda}^{t-1}-\boldsymbol{\lambda}^{(t-1)+\frac{1}{4}}]\boldsymbol{\phi}(\boldsymbol{\lambda}^{t-\frac{1}{2}})}{\|\boldsymbol{\phi}(\boldsymbol{\lambda}^{t-\frac{1}{2}})\|^{2}}\boldsymbol{\phi}(\boldsymbol{\lambda}^{t-\frac{1}{2}})\big{]}^{+}.$
(35)

Obviously this approach has more computational complexity compared to the
projection algorithm and there is no guarantee for the uniqueness solution for
$\boldsymbol{\lambda}$.

  * •

The Tikhonoc Regularization Algorithm is which instead of $\boldsymbol{\phi}$,
its perturbed version, i.e., $\boldsymbol{\phi}+\zeta_{n}\textbf{I}$ is solved
where I is the identity matrix and $\zeta_{n}$ is a small value which is
decreased during the sequence. Therefore, the updating of the Lagrange
multipliers for each $t$ is changed as follows:

$\displaystyle\widehat{\boldsymbol{\lambda}}_{n}^{l+1,t}=\big{[}\widehat{\boldsymbol{\lambda}}^{l,t}-\frac{1}{\tau_{n}}(\boldsymbol{\phi}(\boldsymbol{\lambda}^{t})+\zeta_{n}\widehat{\boldsymbol{\lambda}}^{l,t})\big{]}^{+}$
(36)

where $l=0,1,\cdots$ and this algorithm converges when
$\tau_{n}>\frac{(\frac{1}{c_{\text{coc}}}+\zeta_{n})^{2}}{2\zeta_{n}}$. This
approach has an advantage to attain the unique least-norm solution of the
NCP($\boldsymbol{\phi}$) for each $t$.

Algorithm 2 continuous until the convergence condition holds. Under strong
monotonicty of $\mathcal{F}$, their convergence are studied in Theorems
12.1.8, 12.1.16, and 12.1.2 in (Facchinei and Pang, 2003), respectively.

##  5 Evaluation Results

To evaluate the generalized ADMM, we deploy the setup of Matlab codes from
(Boyd and et al., 2011; Elgabli and et al., 2020). We evaluate the performance
in terms of numbers of iterations for convergence and we define $\Delta$ which
is the difference between solution in (2) and (3). The distributed algorithm
will be stopped when the difference between the solution of consecutive
iterations is less than $10^{-4}$. We simulate for both logistic and Linear
regression objective over the data set 29 in (Elgabli and et al., 2020). We
use the projection algorithm to update the value of $\boldsymbol{\lambda}$
where we have $\tau=0.0002$. For the protection function, we use norm 2, i.e.,
$\varsigma_{n}\|\textbf{w}_{-n}^{t}\|_{2}^{2}+\delta_{n}$ where we set
$\varsigma_{n}=5\times 10^{-3}$ and $\delta_{n}=0.1$.

The effect of soft constraints in the distributed solution of ADMM is studied
in Table 2. The results reveal that by increasing the value of
$\varepsilon=\varepsilon_{n}$ for all $n\in\mathcal{N}$, the error is
increased since the users are allowed to choose the solution close to each
other and not exactly similar to each other. However, interestingly, the
convergence time is decreased significantly since users can choose the
solution that is in proximity of the consensus variables. Therefore, soft
constraints allow us to make a trade-off between convergence and error.

Note that we examine the solution of ADMM for $\varepsilon<0.02$ and
$\varepsilon<0.5$. In the former scenario, $\Delta$ is approaching zero and
there is no significant difference between soft constraints and the
traditional consensus constraint. For the latter scenario, the error is not
acceptable and the solution is not within an acceptable bound of accuracy. For
linear regression, the error value is normalized with the value of the error
of gradient descent method. The trend of increasing $\Delta$ and decreasing
iteration numbers with increasing $\varepsilon$ are similar to those of
logistic regression.

For large value of $\varepsilon$, i.e., $\varepsilon=0.5$, the error of ADMM
with soft constraint is larger than that of the gradient algorithm, while it
has a very fast convergence. Note that to reach the convergence for large
value of $\varepsilon$, we decrease the steps sizes of the iterative
parameters. Since in distributed setting for the large value of $\varepsilon$,
due to flexibility of the choosing the values of weights of users, there is a
chance that the weights of users oscillate. Therefore, there is a need to
adjust the learning parameters in this scenarios with small values for better
convergence.

Table 2: Performance of ADMM in presence of soft constraint versus $\varepsilon=\varepsilon_{n}$ for all $n\in\mathcal{N}$ | Logistic Regression | Linear Regression
---|---|---
| $\varepsilon=0.05$ | $\varepsilon=0.1$ | $\varepsilon=0.5$ | $\varepsilon=0.01$ | $\varepsilon=0.05$ | $\varepsilon=0.5$
$\Delta$ | 3.8 $\times 10^{-3}$ | 1.5 $\times 10^{-2}$ | 0.03 | 0.80% | 0.95% | 135%
Iterations | 6000 | 3000 | 1700 | 300 | 200 | 16
Figure 1: $\Delta$ versus number of iterations for logistic regression and L2
as a protection function.

In Fig. 1, we study the effect of the protection function and the value of
$\varsigma$ on the performance of proximal point method for generalized ADMM
(proxi-ADMM) in Algorithm 2 for logistic regression problem. We plot the
values of $\Delta$ versus iteration numbers for $\varsigma=10^{-3}$ and
$\varsigma=2\times 10^{-3}$. The protection function is $L2$ norm. Fig. 1
shows that $\varsigma=10^{-3}$ improves the performance of the proxi-ADMM in
terms of $\Delta$ and convergence rate compared to those for proxi-ADMM
without the protection function. However, for $\varsigma=2\times 10^{-3}$, we
cannot see the same improvement. This results indicates the importance of
adjusting the value of protection functions and its non-uniform behavior in
terms of improving performance as reported in similar trend of research e.g.,
(Parsaeefard et al., 2019).

##  6 Conclusion

We study the generalized ADMM for distributed learning which includes
different variation of consensus constraints and the effect of local data sets
in each user. We study its solution through variational inequality which gives
us a unified view for study this type of problems. We study the existence,
uniqueness and distributed algorithm for our proposed setup.

Appendix A.

###### Proof.

Proof of this Lemma is as follows. Consider the Taylor series expansion of
$\widetilde{\mathcal{F}}$ with respect to $\textbf{f}_{n}$ as

$\widetilde{\mathcal{F}}=[\widetilde{\mathcal{F}}]_{\varsigma_{n}}+[\sum_{i=1}^{\infty}(\frac{1}{i!})(\varsigma_{n})^{i}\bigtriangledown_{\textbf{f}_{n}^{i}}\widetilde{\mathcal{F}}]_{\varsigma_{n}}.$

When $\varsigma_{n}$ is small, the first term is equal to $0$, and from A2-A3,
the second term has a bounded value such that there exists
$q^{\text{max}}\leq\infty$ where $\|\mathcal{F}-\widetilde{\mathcal{F}}\|\leq
q^{\text{max}}$. Now, we have

$(\textbf{w}_{1}-\textbf{w}_{2})(\widetilde{\mathcal{F}}(\textbf{w}_{1})-\widetilde{\mathcal{F}}(\textbf{w}_{2}))\geq(\textbf{w}_{1}-\textbf{w}_{2})({\mathcal{F}}(\textbf{w}_{1})-{\mathcal{F}}(\textbf{w}_{2}))\geq
c\|\textbf{w}_{1}-\textbf{w}_{2}\|$ (37)

where $c>0$ is a strong monotonicity constant of $\mathcal{F}$, and the last
inequality comes from strong monotone assumption of $\mathcal{F}$. ∎

Appendix B.

###### Proof.

For this theorem, we first should proof the following Lemma.
Lemma 1: 1) For the closed, convex uncertainty region in
$\Re_{n}(\textbf{w}_{-n})$, $\widetilde{\textbf{W}}_{n}$ is a closed, bounded
and convex set. 2) $\Phi_{n}$ is a continuous and differentiable of
$\textbf{w}_{n}$ and
$\textbf{f}_{n}(\textbf{w}_{-n},\textbf{x}_{-n},\textbf{y}_{-n})$. If
$V_{n}(\textbf{w}_{n},\textbf{x}_{n},\textbf{y}_{n})$ is convex with respect
to $\textbf{w}_{n}$, $\Phi_{n}$ is a convex function.

###### Proof.

This proof has two parts:

  * •

When $\textbf{f}_{n}(\textbf{w}_{-n},\textbf{x}_{-n},\textbf{y}_{-n})$ is a
linear additive function of other user’s wights. Moreover the norm function is
a convex function bounded to $\varsigma_{n}$ (Sec 2.2.2 Boyd and Vandenberghe
(2004)). Hence $\widetilde{\textbf{W}}_{n}$ is closed, bounded set.

  * •

From A1-A3, $\Phi_{n}$ is contentious and differentiable. If
$V_{n}(\textbf{w}_{n},\textbf{x}_{n},\textbf{y}_{n})$ is convex, its maximum
over the convex and closed set is also convex (Boyd and Vandenberghe, 2004).

∎

From assumptions A1-A4 and Lemma 1, it is straightforward to show Lemma 3.1
and Theorem 3.2 in (Nishimura et al., 2009) hold for our setup. Therefore,
both $VI(\mathcal{Q},\mathcal{F})$ and
$VI(\widetilde{\mathcal{Q}},\widetilde{\mathcal{F}})$ have at least one
solution. ∎

Appendix C.

###### Proof.

From Theorem 2.3.3.(b) in (Facchinei and Pang, 2003), if
$\mathcal{F}+\boldsymbol{\lambda}\mathcal{G}^{1}+\boldsymbol{\mu}\mathcal{G}_{2}$
is strongly monotone, the solution of this optimization problem is unique.
when $g_{n}^{1}$ is linear and $g_{n}^{2}$ is convex, we have

$(\textbf{w}-\textbf{w}^{\prime})(\mathcal{G}^{2}(\textbf{w})-\mathcal{G}^{2}(\textbf{w}^{\prime}))\geq
0$

and

$(\textbf{w}-\textbf{w}^{\prime})(\mathcal{G}^{1}(\textbf{w})-\mathcal{G}^{1}(\textbf{w}^{\prime}))\geq
0,$

and it is straightforward that when $\mathcal{F}$ is strong monotone,
$\mathcal{F}^{\text{Fixed}}$ is strong monotone. From Appendix A, and from
(37) in this supplementary file , when $\mathcal{F}^{\text{Fixed}}$ is strong
monotone, $\widetilde{\mathcal{F}}^{\text{Fixed}}$ is strong monotone.
Therefore both $VI(\textbf{W},\mathcal{F}^{\text{Fixed}})$ and
$VI(\widetilde{\textbf{W}},\widetilde{\mathcal{F}}^{\text{Fixed}})$ have a
unique solution when $\mathcal{F}$ is strong monotone Facchinei and Pang
(2003). ∎

Appendix D

###### Proof.

For this proof, we first define the P-matrix property of one matrix:

Definition: For any nonzero vector x, we have
$x_{n}(\boldsymbol{\Upsilon}\textbf{x})_{n}>0$ where $x_{n}$ is the
$n^{\text{th}}$ element of x.

The strong monotone condition of mapping $\mathcal{F}$ can be replaced by a
$P$-matrix condition of $\boldsymbol{\Upsilon}$ where (Palomar and Eldar,
2010)

$\displaystyle[\Upsilon]_{nm}=\left\\{\begin{array}[]{c}\alpha_{n}^{\text{min}},\,\,\,\,\,\qquad\text{if}\qquad\,m=n,\\\
-\beta_{nm}^{\text{max}},\,\qquad\text{if}\qquad\,m\neq n,\\\
\end{array}\right.$ (40)

in which

$\alpha_{n}^{\text{min}}\triangleq\inf_{\textbf{w}\in\textbf{W}}\alpha_{n}(\textbf{w}),$
$\beta_{nm}^{\text{max}}\triangleq\sup_{\textbf{w}\in\textbf{W}}\beta_{nm}(\textbf{w}),$
$\alpha_{n}(\textbf{w})\triangleq\text{smallest eigenvalue
of}\nabla^{2}_{\textbf{w}_{n}}V_{n}(\textbf{w}),$

and

$\beta_{nm}(\textbf{w})\triangleq\|\nabla_{\textbf{w}_{n}\textbf{w}_{m}}V_{n}(\textbf{w})\|_{2},\quad\forall
n\neq m,$

where $\nabla^{2}_{\textbf{w}_{n}}V_{n}(\textbf{w})$ and
$\nabla_{\textbf{w}_{n}\textbf{w}_{m}}V_{n}(\textbf{w})$ are the $K\times K$
Jacobian matrices of $\mathcal{F}_{n}(\textbf{w})$ with respect to
$\textbf{w}_{n}$ and $\textbf{w}_{m}$, respectively, and
$\|-\nabla_{\textbf{w}_{n}\textbf{w}_{m}}V_{n}(\textbf{w}_{n})\|_{2}$ is the
$l_{2}$-norm of $V_{n}(\textbf{w}_{n})$.

Now for all $n\in\mathcal{N}$, we have
$\frac{\partial^{2}V_{n}}{\partial\textbf{w}_{n}\partial\textbf{f}_{n}}\ll\frac{\partial^{2}V_{n}}{\partial^{2}\textbf{w}_{n}}$
which indicates that the effect of the weight of user $n$ on its own
optimization problem is much stronger than the effect of other users on its
own solution, conducting that matrix $\mathcal{J}$ is strictly semipositive
matrix where
$[\mathcal{J}]_{nn}=\frac{\partial^{2}V_{n}}{\partial^{2}\textbf{w}_{n}}$ and
$[\mathcal{J}]_{nm}=\frac{\partial^{2}V_{n}}{\partial\textbf{w}_{n}\partial\textbf{f}_{n}}\times\frac{\textbf{f}_{n}}{\partial\textbf{w}_{n}}$
and $\frac{\textbf{f}_{n}}{\partial\textbf{w}_{n}}\geq 0$. Algorithm 1
converges when $\boldsymbol{\Upsilon}$ is a P-matrix and the third order of
derivatives of $V_{n}$ with respect to $\textbf{w}_{n}$ are negligible i.e.,
A5 Palomar and Eldar (2010).

∎

Appendix E

###### Proof.

The proof of this theorem include three steps.

  * •

Step1: For any value of fixed $\boldsymbol{\lambda}$, the solution of the
mapping (11) for w and $\widetilde{\textbf{w}}$ come from solution of
$VI(\textbf{W},\mathcal{F}^{\text{Fixed}})$ and
$VI(\widetilde{\textbf{W}},\widetilde{\mathcal{F}}^{\text{Fixed}})$. In
Appendix C, we show that when $\mathcal{F}$ is strong monotone, the solution
of $VI(\textbf{W},\mathcal{F}^{\text{Fiexed}})$ and
$VI(\widetilde{\textbf{W}},\widetilde{\mathcal{F}}^{\text{Fiexed}})$ are
unique. Let $(\textbf{w}^{*},\boldsymbol{\lambda}^{*})$ be a solution of (3)
which exists according to Theorem 1. From monotonocinity of $\mathcal{F}$,
$\textbf{w}^{*}$ is unique and $\boldsymbol{\lambda}^{*}$ is a solution of the
NCP in (11). Conversely, if $\boldsymbol{\lambda}^{*}$ is any solution of the
NCP, then $(\textbf{w}^{*},\boldsymbol{\lambda}^{*})$ should be a solution of
(2) (Pang et al., 2010). The same is true for (2) and
$\widetilde{\textbf{w}}^{*}$.

  * •

Step2: If NCP in (11) is monotone, there is a convex set of solutions for this
equations which interestingly all of them leads to $\textbf{w}^{*}$. NCP in
(11) is monotone, if $\boldsymbol{\phi}$ is co-coercive, i.e.,

$\big{(}\boldsymbol{\lambda}^{1}-\boldsymbol{\lambda}^{2})^{T}(\boldsymbol{\phi}(\boldsymbol{\lambda}^{1})-\boldsymbol{\phi}(\boldsymbol{\lambda}^{2}))\geq
c_{\text{coc}}(\boldsymbol{\phi})\|\boldsymbol{\phi}(\boldsymbol{\lambda}^{1})-\boldsymbol{\phi}(\boldsymbol{\lambda}^{2})\|_{2}^{2}$

which conducts us to have Lipschitz continuous property for mapping
$\boldsymbol{\phi}$. The same is true for
$QVI(\widetilde{\mathcal{Q}},\widetilde{\mathcal{F}})$.

  * •

Step3: To study the co-corrective condition of $\boldsymbol{\phi}$, for any
given $\boldsymbol{\gamma}$, let
$\textbf{w}^{*}=\textbf{w}^{*}(\boldsymbol{\gamma})$ be a unique solution of
VI of $\mathcal{F}^{\text{Lagrange1}}(\boldsymbol{\varkappa})$, from
$VI(\mathcal{Q},\mathcal{F}^{\text{Lagrange1}}(\boldsymbol{\varkappa}))$, we
have

$(\textbf{w}^{*}(\boldsymbol{\gamma}^{1})-\textbf{w}^{*}(\boldsymbol{\gamma}^{2}))[\mathcal{F}(\textbf{w}^{*}(\boldsymbol{\gamma}^{2}))-\boldsymbol{\gamma}^{2})]\geq
0$

and

$(\textbf{w}^{*}(\boldsymbol{\gamma}^{2})-\textbf{w}^{*}(\boldsymbol{\gamma}^{1}))[\mathcal{F}(\textbf{w}^{*}(\boldsymbol{\gamma}^{1}))-\boldsymbol{\gamma}^{1})]\geq
0.$

By adding the above two terms and rearranging terms and following the strong
monotonicity of $\mathcal{F}$, we have

$(\boldsymbol{\gamma}^{1}-\boldsymbol{\gamma}^{2})(\textbf{w}^{*}(\boldsymbol{\gamma}^{1})-\textbf{w}^{*}(\boldsymbol{\gamma}^{2}))\geq
c(\mathcal{F})\|\textbf{w}^{*}(\boldsymbol{\gamma}^{1})-\textbf{w}^{*}(\boldsymbol{\gamma}^{2})\|_{2}^{2}$
(41)

where $c(\mathcal{F})$ is strong monotone constant of $\mathcal{F}$. From
convexity of $\textbf{g}^{2}$ and definitions of $\boldsymbol{\phi}$ and
$\boldsymbol{\gamma}$, we have

$(\textbf{w}^{*}(\boldsymbol{\gamma}^{1})-\textbf{w}^{*}(\boldsymbol{\gamma}^{2}))\geq\frac{1}{\mathcal{G}^{2}}\boldsymbol{\phi}(\textbf{w}^{*}(\boldsymbol{\gamma}^{1})-\boldsymbol{\phi}(\textbf{w}^{*}(\boldsymbol{\gamma}^{2})$

and from the definition of $\boldsymbol{\gamma}$, we can show that left term
of (41) in this supplementary file is less than
$(\boldsymbol{\lambda}^{1}-\boldsymbol{\lambda}^{2})(\boldsymbol{\phi}(\boldsymbol{\lambda}^{1})-\boldsymbol{\phi}(\boldsymbol{\lambda}^{2})),$
and therefore, we deduce that

$(\boldsymbol{\lambda}^{1}-\boldsymbol{\lambda}^{2})(\boldsymbol{\phi}(\boldsymbol{\lambda}^{1})-\boldsymbol{\phi}(\boldsymbol{\lambda}^{2})))\geq\frac{c(\mathcal{F})}{\mathcal{G}^{2}}\|\boldsymbol{\phi}(\boldsymbol{\lambda}^{1})-\boldsymbol{\phi}(\boldsymbol{\lambda}^{2})\|_{2}^{2}.$

This inequality proofs the desired co-coercivity property of
$\boldsymbol{\phi}$. From this, we can reach to the convex set of the solution
of NCP. From Appendix A, the above results can be derived for the
$\widetilde{\mathcal{F}}$ with minor modifications. Here, we have
$c_{\text{coc}}=\frac{c(\mathcal{F})}{\mathcal{G}^{2}}$.

Note that this theorem does not show the uniqueness condition of
$\boldsymbol{\lambda}$. However, it shows that $\boldsymbol{\lambda}$ belongs
to convex set. ∎

## References

  * D.P. Bertsekas and Tsitsiklis [1999] D.P. Bertsekas and J. Tsitsiklis.  _Parallel and Distributed Computation: Numerical Methods_.  Prentice Hall, 1999.
  * Boyd and et al. [2011] Stephen Boyd and et al.  Distributed optimization and statistical learning via the alternating direction method of multipliers.  _Foundations and Trends in Machine Learning_ , 3:1–122, 01 2011.
  * Kumar et al. [2019] Sandeep Kumar, Ketan Rajawat, and Daniel P. Palomar.  Distributed inexact successive convex approximation ADMM: Analysis-part I.  _https://arxiv.org/abs/1907.08969_ , pages 1–15, 06 2019.
  * He et al. [2018] Lie He, An Bian, and Martin Jaggi.  Cola: Decentralized linear learning.  In _32nd Conference on Neural Information Processing Systems (NeurIPS 2018), Montréal, Canada_. 2018.  URL https://papers.nips.cc/paper/7705-cola-decentralized-linear-learning.pdf.
  * Jung [2021] D. Jung.  Distributed feature selection for multi-class classification using ADMM.  _IEEE Control Systems Letters_ , 5(3):821–826, 2021.
  * Ling et al. [2016] Q. Ling, Y. Liu, W. Shi, and Z. Tian.  Weighted ADMM for fast decentralized network optimization.  _IEEE Transactions on Signal Processing_ , 64(22):5930–5942, 2016.
  * Mota et al. [2013] J. F. C. Mota, J. M. F. Xavier, P. M. Q. Aguiar, and M. Püschel.  D-ADMM: A communication-efficient distributed algorithm for separable optimization.  _IEEE Transactions on Signal Processing_ , 61(10):2718–2723, 2013.
  * Elgabli et al. [2020] Anis Elgabli, Jihong Park, and et al.  Q-GADMM: Quantized group ADMM for communication efficient decentralized machine learning.  _arXiv:1910.10453v3_ , 2020.
  * Elgabli et al. [2020] A. Elgabli, J. Park, S. Ahmed, and M. Bennis.  L-FGADMM: Layer-wise federated group ADMM for communication efficient decentralized deep learning.  In _2020 IEEE Wireless Communications and Networking Conference (WCNC)_ , pages 1–6, 2020.
  * França and Bento [2016] Guilherme França and José Bento.  An explicit rate bound for over-relaxed ADMM.  In _2016 IEEE International Symposium on Information Theory (ISIT)_ , pages 2104–2108. IEEE, 2016.
  * Nishihara et al. [2015] Robert Nishihara, Laurent Lessard, Benjamin Recht, Andrew Packard, and Michael I. Jordan.  A general analysis of the convergence of ADMM.  In _Proceedings of the 32nd International Conference on International Conference on Machine Learning - Volume 37_ , ICML’15, page 343–352. JMLR.org, 2015.
  * Ghadimi et al. [2015] E. Ghadimi, A. Teixeira, I. Shames, and M. Johansson.  Optimal parameter selection for the alternating direction method of multipliers (ADMM): Quadratic problems.  _IEEE Transactions on Automatic Control_ , 60(3):644–658, 2015.
  * Giselsson and Boyd [2016] Pontus Giselsson and Stephen Boyd.  Linear convergence and metric selection in douglas-rachford splitting and ADMM.  _IEEE Transactions on Automatic Control_ , 62:1–1, 01 2016\.  doi: 10.1109/TAC.2016.2564160.
  * Parsaeefard et al. [2019] Saeedeh Parsaeefard, Iman Tabrizian, and Alberto Leon Garcia.  Representation of federated learning via worst-case robust optimization theory.  _Foundations and Trends in Machine Learning_ , 3:1–122, 01 2019.
  * Facchinei and Pang [2003] F. Facchinei and J. Pang.  _Finite-Dimensional Variational Inequalities and Complementarity Problems_.  Springer, 2003.
  * Chen et al. [2014] C. Chen, B. He, Y. Ye, and X. Yuan.  The direct extension of ADMM for multi-block convex minimization problems is not necessarily convergent.  _Mathematical Programming_ , 155(3):57–79, 2014\.
  * Wang and Zhao [2019] Junxiang Wang and Liang Zhao.  Nonconvex generalization of ADMM for nonlinear equality constrained problems.  _https://arxiv.org/pdf/1705.03412.pdf_ , 2019.
  * Du and Jiang [2020] P. Du and H. Jiang.  On the convergence of bregman ADMM with variational inequality.  _IEEE Access_ , 8:29608–29615, 2020.
  * Elgabli and et al. [2020] Anis Elgabli and et al.  GADMM: Fast and communication efficient framework for distributed machine learning.  _arXiv:1909.00047v3 [cs.LG] 24 Mar 2020_ , 2020.
  * Ben-Tal and Nemirovski [1999] A. Ben-Tal and A. Nemirovski.  Robust solutions to uncertain programs.  _Operations Research Letters_ , 25, 1999.
  * Parsaeefard et al. [2017] Saeedeh Parsaeefard, Ahmad Reza Sharafat, and Nader Mokari.  _Robust Resource Allocation in Future Wireless Networks_.  Springer,, 2017.
  * Scutari et al. [2010] G. Scutari, D. P. Palomar, F. Facchinei, and J. Pang.  Convex optimization, game theory, and variational inequality theory.  _IEEE Signal Processing Magazine_ , 27(3):35–49, 2010.
  * Palomar and Eldar [2010] D. P. Palomar and Y. C. Eldar.  _Convex Optimization in Signal Processing and Communications_.  Cambridge, U.K.: Cambridge Univ. Press, 2010.
  * Pang et al. [2010] J. Pang, G. Scutari, D. P. Palomar, and F. Facchinei.  Design of cognitive radio systems under temperature-interference constraints: A variational inequality approach.  _IEEE Transactions on Signal Processing_ , 58(6):3251–3271, 2010.
  * Boyd and Vandenberghe [2004] Stephen Boyd and Lieven Vandenberghe.  _Convex Optimization_.  Cambridge University Press, 2004.
  * Nishimura et al. [2009] R. Nishimura, S. Hayashi, and M. Fukushima.  Robust Nash equilibria in n-person non-cooperative games: Uniqueness and reformulation.  _Pac. J. Optim._ , 5:237–259, May 2009.