#  A Tuning-Free Primal-Dual Splitting Algorithm for Large-Scale Semidefinite
Programming

Yinjun Wang Independent Researcher<EMAIL_ADDRESS>Haixiang Lan
Columbia University<EMAIL_ADDRESS>Yinyu Ye Stanford University, yinyu-
<EMAIL_ADDRESS>
###### Abstract

This paper proposes and analyzes a tuning-free variant of Primal-Dual Hybrid
Gradient (PDHG), and investigates its effectiveness for solving large-scale
semidefinite programming (SDP). The core idea is based on the combination of
two seemingly unrelated results: (1) the equivalence of PDHG and Douglas-
Rachford splitting (DRS) [18]; (2) the asymptotic convergence of _non-
stationary_ DRS [16]. This combination provides a unified approach to analyze
the convergence of generic adaptive PDHG, including the proposed tuning-free
algorithm and various existing ones. Numerical experiments are conducted to
show the performance of our algorithm, highlighting its superior convergence
speed and robustness in the context of SDP.

## 1 Introduction

Semidefinite programming (SDP) is an effective framework for convex
optimization, incorporating a wide range of important classes such as linear
programming (LP), convex quadratic programming, and second-order cone
programming. Aside from its recognized applications in mathematical modeling
and constructing convex relaxations of NP-hard problems, SDP is notably
effective in resolving various machine learning problems. They include but are
not limited to maximum variance unfolding [14], sparse principal component
analysis [7], matrix completion [21], graphical model inference [9], community
detection [3], $k$-mean clustering [20], neural network verification [1], etc.

The wide adoption of SDP is facilitated by efficient and robust algorithms.
Interior-point methods (IPMs), which can provably solve SDP to arbitrary
precision in polynomial time, serve as foundational approaches in traditional
SDP solvers [13]. However, their computational costs are typically high due to
the procedure of adopting Newton’s method to approximately solve a Karush-
Kuhn-Tucker (KKT) system in each iteration. Consequently, first order methods,
such as Alternating Directions Method of Multipliers (ADMM) [4] and Primal-
Dual Hybrid Gradient (PDHG) [5, 6], have much lower complexity, and thus, have
gained much popularity in recent years. Each iteration of PDHG is free from
solving a linear system, in contrast to ADMM, which requires solving a linear
system in every iteration. However, while ADMM has been the method of choice
for several popular SDP solvers [24, 28, 10, 19, 23, 27], PDHG for SDP has
gained few attentions [22].

To effectively implement PDHG in practice, a key challenge is the tuning of
its primal and dual stepsizes. The values of these two stepsizes significantly
influence its convergence speed. Relying on manual tuning is not only
computationally intensive – requiring tests across various values – but also
lacks robustness, as the stepsizes that lead to fast convergence in one
scenario may not be a good choice for another. Several stepsize-adjusting
strategies have been proposed to address this challenge. The primal-dual
balancing technique, proposed by [12, 11], aims to dynamically adjust the
ratio between the primal and dual stepsizes, keeping the primal and dual
residuals approximately equal. The idea of balancing primal and dual residuals
has been further extended by [25, 26] to take into account the local variation
of gradient directions. Moreover, a linesearch technique has been proposed in
[17], adjusting stepsizes by repeated extrapolation and backtracking.
Recently, [2] focused on PDHG for LP and proposed a stepsize-adjusting
heuristics by combining the ideas of both balancing and linesearch. Although
these stepsize-adjusting strategies [12, 11, 25, 26] can speed up convergence,
they introduce some additional hyperparameters. These new hyperparameters
still need to be carefully tuned, and as verified in our numerical
experiments, manually tuning them suffers from issues similar to those
encountered when tuning the original stepsizes.

The goal of this paper is to develop a variant of PDHG for SDP that is totally
tuning-free. We first consider a generic PDHG variant (Algorithm 1) that
allows to dynamically adjust its stepsizes in each iteration, and study its
convergence (Theorem 2.1). Motivated by the connection [18] between PDHG and
Douglas-Rachford splitting (DRS) [8, 15], we treat Algorithm 1 as DRS solving
a specific class of monotone inclusion problem, and employ the convergence
results from [16] to prove its asymptotic convergence. Note that the class of
monotone inclusion problem is only assumed to be maximally monotone. Thus, the
asymptotic convergence is a fairly standard result, since no inequality from
convexity can be exploited to prove a $\mathcal{O}(\frac{1}{k})$ convergence
rate, where $k$ is the number of iteration. It is worth noting that although
the theoretical results are presented in the context of SDP, they can be
easily extended to the setting of $f(x)+g(Ax)$, where $f$ and $g$ are convex,
closed, proper, and potentially nonsmooth. As a by-product, we show that
various adaptive variants, such as balancing primal-dual residuals [12, 11]
and aligning local variation of gradient directions [25, 26] are special cases
of Algorithm 1, and prove their convergence in an unified manner (Theorem
2.2). For the tuning-free algorithm develpoment, the stepsize-adjusting
strategy for DRS proposed in [16] enables us to develop a tuning-free variant
of PDHG (Algorithm 5), which is also a special case of Algorithm 1 (Theorem
2.3). Finally, we conduct numerical experiments and show that Algorithm 5
exhibits compelling performances on both convergence speed and robustness of
incorporating low-rank rounding.

## 2 Algorithms and Convergence

### 2.1 Notation

Define the resolvent of an operator $A$ to be
$J_{A}\coloneqq(\mathbb{I}+A)^{-1}$. Note that if $A=\partial f$, then
$J_{\partial f}=\text{Prox}_{f}$. Given $A,B\in\mathbb{R}^{n\times n}$, define
operation $\langle
A,B\rangle\coloneqq\sum_{i=1}^{n}\sum_{j=1}^{n}A_{ij}B_{ij}$. Define a linear
mapping $\mathcal{A}\colon\mathbb{S}^{n\times n}\to\mathbb{R}^{m}$ as
$\mathcal{A}(X)=\begin{pmatrix}\langle A_{1},X\rangle\\\ \langle
A_{2},X\rangle\\\ \vdots\\\ \langle A_{m},X\rangle\\\ \end{pmatrix}$, where
$A_{1},A_{2},\dots,A_{m}\in\mathbb{S}^{n\times n}$ are $m$ symmetric matrices.
Its adjoint mapping $\mathcal{A}^{T}\colon\mathbb{R}^{m}\to\mathbb{S}^{n\times
n}$ is defined as $\mathcal{A}^{T}(y)=\sum_{i=1}^{m}y_{i}A_{i}$. SDP aims to
minimize a linear objective function of $X\in\mathbb{R}^{n\times n}$ subject
to $m$ linear equality constraints, and is defined as

$\displaystyle\min_{X\in\mathbb{R}^{n\times n}}$ $\displaystyle\langle
C,X\rangle$ (1) s.t. $\displaystyle\mathcal{A}(X)=b$ $\displaystyle
X\in\mathbb{S}_{+}^{n\times n}$

Given $\mathbb{I}_{\mathbb{S}_{+}^{n\times n}}\left(X\right)=0$ if
$X\in\mathbb{S}_{+}^{n\times n}$ and $=\infty$ otherwise, and
$\mathbb{I}_{=b}\left(y\right)=0$ if $y=b$ and $=\infty$ otherwise, (1) can be
rewritten as the following nonsmooth problem:

$\displaystyle\min_{X}\quad\underbrace{\langle
C,X\rangle+\mathbb{I}_{\mathbb{S}_{+}^{n\times
n}}(X)}_{f\left(\cdot\right)}+\underbrace{\mathbb{I}_{=b}\left(\mathcal{A}(X)\right)}_{g\left(\cdot\right)}$
(2)

### 2.2 Tuning-Free PDHG for SDP

We consider a generic variant of PDHG for SDP (Algorithm 1) that allows to
dynamically adjust its stepsizes at each iteration. When $\theta_{k}$ is fixed
to be $1$ for $\forall k$, it is reduced to

$\displaystyle X^{k+1}\leftarrow\text{Proj}_{\mathbb{S}_{+}^{n\times
n}}\Big{(}X^{k}-\alpha_{k}\big{(}\mathcal{A}^{T}(y^{k})+C\big{)}\Big{)}$
$\displaystyle y^{k+1}\leftarrow
y^{k}+\beta_{k}\mathcal{A}\left(2X^{k+1}-X^{k}\right)-\beta_{k}b,$

which is first presented in [22] and can be seen as PDHG solving (2). We
develop Theorem 2.1 to guide Algorithm 1 to adjust its stepsizes at each
iteration. The idea comes from the connection [18] between PDHG and DRS. By
introducing a new variable $\hat{X}$, this connection allows us to treat PDHG
as DRS

$\displaystyle\begin{pmatrix}X^{k+1}\\\ \hat{X}^{k+1}\end{pmatrix}=J_{\alpha
A}\left(2J_{\alpha B}\left(\begin{pmatrix}X^{k}\\\
\hat{X}^{k}\end{pmatrix}\right)-\begin{pmatrix}X^{k}\\\
\hat{X}^{k}\end{pmatrix}\right)+\begin{pmatrix}X^{k}\\\
\hat{X}^{k}\end{pmatrix}-J_{\alpha B}\left(\begin{pmatrix}X^{k}\\\
\hat{X}^{k}\end{pmatrix}\right)$

solving the following monotone inclusion problem:

$\displaystyle\text{Find}\ \begin{pmatrix}X\\\
\hat{X}\end{pmatrix}\quad\text{s.t.}\quad 0\in\underbrace{\begin{pmatrix}C\\\
0\end{pmatrix}+\begin{pmatrix}\partial_{X}\mathbb{I}_{\mathbb{S}_{+}^{n\times
n}}(X)\\\ 0\end{pmatrix}+\begin{pmatrix}0\\\
\partial_{\hat{X}}\mathbb{I}_{=0}(\hat{X})\end{pmatrix}}_{B=\partial
f(X,\hat{X})}+\underbrace{\begin{pmatrix}\partial_{X}\mathbb{I}_{=b}(\mathcal{A}(X)+\mathcal{T}(\hat{X}))\\\
\partial_{\hat{X}}\mathbb{I}_{=b}(\mathcal{A}(X)+\mathcal{T}(\hat{X}))\end{pmatrix}}_{A=\partial
g(X,\hat{X})},$

where $f(X,\hat{X})=\langle C,X\rangle+\mathbb{I}_{\mathbb{S}_{+}^{n\times
n}}(X)+\mathbb{I}_{=0}(\hat{X})$,
$g(X,\hat{X})=\mathbb{I}_{=b}\left(\mathcal{A}(X)+\mathcal{T}(\hat{X})\right)$,
and $\mathcal{T}\colon\mathbb{S}^{n\times n}\to\mathbb{R}^{m}$ is a certain
linear operator that will be specified in the proof. We then can leverage the
convergence result of _non-stationary_ DRS (Theorem 3.2. in [16]) to develop
the convergence theory for Algorithm 1. The details of proof are presented in
Appendix.

Input: $X^{0},y^{0}$

for $k=0,1,2,\dots$ do

$\alpha_{k},\theta_{k},\beta_{k}$ are adjusted following Theorem 2.1

$X^{k+1}\leftarrow\text{Proj}_{\mathbb{S}_{+}^{n\times
n}}\Big{(}X^{k}-\alpha_{k}\big{(}\mathcal{A}^{T}(y^{k})+C\big{)}\Big{)}$

$y^{k+1}\leftarrow
y^{k}+\beta_{k}\mathcal{A}(X^{k+1}+\theta_{k}(X^{k+1}-X^{k}))-\beta_{k}b$

end for

Algorithm 1 Generic Adaptive PDHG for SDP

######  Theorem 2.1.

If the adjustment of
$\left\\{\big{(}\alpha_{k},\theta_{k},\beta_{k}\big{)}\right\\}_{k}$ in
Algorithm 1 follows that

$\displaystyle\alpha_{k}\in\left(\alpha_{\min},\alpha_{\max}\right),\quad\sum_{k=1}^{\infty}\left|\alpha_{k+1}-\alpha_{k}\right|<\infty,\quad\theta_{k}=\frac{\alpha_{k}}{\alpha_{k-1}},\quad\alpha_{k}\beta_{k}=R,$

where $0<\alpha_{\min}\leq\alpha_{\max}<\infty$ and
$R<\frac{1}{\lambda_{\max}(\mathcal{A}^{T}\mathcal{A})}$. Then Algorithm 1
weakly converges to $(X^{*},y^{*})$ such that $0\in
C+\partial_{X}\mathbb{I}_{\mathbb{S}_{+}^{n\times
n}}(X^{*})+\partial_{X}\mathbb{I}_{=b}(\mathcal{A}(X^{*}))$.

Theorem 2.1 provides an unified approach to analyze the convergence of PDHG
with adaptive stepsizes. We show that various existing variants, such as
Algorithm 2 and 3, are special cases of Algorithm 1, and thus justify their
convergence (Theorem 2.2).

Input: $X^{0}\in\mathbb{R}^{n\times
n},y^{0}\in\mathbb{R}^{m},\alpha_{0}\beta_{0}<\frac{1}{\lambda_{\max}(\mathcal{A}^{T}\mathcal{A})},(\epsilon_{0},\eta)\in(0,1)^{2}$

for $k=0,1,2,\dots$ do

$X^{k+1}=\text{Proj}_{\mathcal{S}^{n}_{+}}\Big{(}X^{k}-\alpha_{k}\big{(}\mathcal{A}^{T}(y^{k})-C\big{)}\Big{)}$

$y^{k+1}=y^{k}+\beta_{k}\bigg{(}\mathcal{A}\Big{(}X^{k+1}+\theta_{k}\big{(}X^{k+1}-X^{k}\big{)}\Big{)}-b\bigg{)}$

$p^{k+1}=\left\lVert\,\frac{X^{k}-X^{k+1}}{\alpha_{k}}-\mathcal{A}^{T}(y^{k}-y^{k+1})\,\right\rVert$

$d^{k+1}=\left\lVert\,\frac{y^{k}-y^{k+1}}{\beta_{k}}-\mathcal{A}\big{(}X^{k}-X^{k+1}\big{)}\,\right\rVert$

if $p^{k+1}>2d^{k+1}\Delta$ then

$\alpha_{k+1}=\frac{\alpha_{k}}{1-\epsilon_{k}},\
\beta_{k+1}=\beta_{k}(1-\epsilon_{k}),\ \theta_{k+1}=\frac{1}{1-\epsilon_{k}}$

else if $\frac{1}{2}d^{k+1}\leq p^{k+1}\leq 2d^{k+1}$ then

$\alpha_{k+1}=\alpha_{k},\ \beta_{k+1}=\beta_{k},\ \theta_{k+1}=1$

else

$\alpha_{k+1}=\alpha_{k}(1-\epsilon_{k}),\
\beta_{k+1}=\frac{\beta_{k}}{1-\epsilon_{k}},\ \theta_{k+1}=1-\epsilon_{k}$

end if

$\epsilon_{k+1}=\epsilon_{k}\eta$

end for

Algorithm 2 Balancing Primal and Dual Residuals (B-PDR) [12, 11]

Input: $X^{0}\in\mathbb{R}^{n\times
n},y^{0}\in\mathbb{R}^{m},\alpha_{0}\beta_{0}<\frac{1}{\lambda_{\max}(\mathcal{A}^{T}\mathcal{A})},(\epsilon_{0},\eta)\in(0,1)^{2}$

for $k=0,1,2,\dots$ do

$X^{k+1}=\text{Proj}_{\mathcal{S}^{n}_{+}}\Big{(}X^{k}-\alpha_{k}\big{(}\mathcal{A}^{T}(y^{k})-C\big{)}\Big{)}$

$y^{k+1}=y^{k}+\beta_{k}\bigg{(}\mathcal{A}\Big{(}X^{k+1}+\theta_{k}\big{(}X^{k+1}-X^{k}\big{)}\Big{)}-b\bigg{)}$

$p^{k+1}=\frac{1}{\alpha_{k}}(X^{k}-X^{k+1})-\mathcal{A}^{T}(y^{k}-y^{k+1})$
or $\frac{1}{\alpha_{k}}(X^{k}-X^{k+1})-\mathcal{A}^{T}(y^{k})$

$w_{p}^{k+1}=\frac{\langle
X^{k}-X^{k+1},p^{k+1}\rangle}{\left\lVert\,X^{k}-X^{k+1}\,\right\rVert_{\mathcal{F}}\left\lVert\,p^{k+1}\,\right\rVert_{\mathcal{F}}}$

if $w^{k+1}_{p}>0.99$ then

$\alpha_{k+1}=\frac{\alpha_{k}}{1-\epsilon_{k}},\
\beta_{k+1}=\beta_{k}(1-\epsilon_{k}),\ \theta_{k+1}=\frac{1}{1-\epsilon_{k}}$

else if $0\leq w^{k+1}_{p}\leq 0.99$ then

$\alpha_{k+1}=\alpha_{k},\ \beta_{k+1}=\beta_{k},\ \theta_{k+1}=1$

else

$\alpha_{k+1}=\alpha_{k}(1-\epsilon_{k}),\
\beta_{k+1}=\frac{\beta_{k}}{1-\epsilon_{k}},\ \theta_{k+1}=1-\epsilon_{k}$

end if

$\epsilon_{k+1}=\epsilon_{k}\eta$

end for

Algorithm 3 Aligning Local Variation of Gradient Directions (A-LV) [25, 26]

Input: $X^{0},y^{1},\alpha_{0}>0,s\in\mathbb{R}$

for $k=1,2,\dots$ do

$X^{k}\leftarrow\text{Proj}_{\mathbb{S}_{+}^{n\times
n}}\Big{(}X^{k-1}-\alpha_{k-1}\big{(}\mathcal{A}^{T}(y^{k})+C\big{)}\Big{)}$

$\alpha_{k}\in[\alpha_{k-1},\alpha_{k-1}\sqrt{1+\theta_{k-1}}]$,
$\beta_{k}=s\alpha_{k}$ and
$\theta_{k}\leftarrow\frac{\alpha_{k}}{\alpha_{k-1}}$

$y^{k+1}\leftarrow
y^{k}+\beta_{k}\big{(}\mathcal{A}(X^{k}-\theta_{k}(X^{k}-X^{k-1}))-b\big{)}$

while
$\left\lVert\,\mathcal{A}^{T}(y^{k+1})-\mathcal{A}^{T}(y^{k})\,\right\rVert>\frac{1}{\sqrt{s}\alpha_{k}}\left\lVert\,y^{k+1}-y^{k}\,\right\rVert$
do

$\alpha_{k}\leftarrow\alpha_{k}\mu$, $\beta_{k}=s\alpha_{k}$ and
$\theta_{k}\leftarrow\frac{\alpha_{k}}{\alpha_{k-1}}$

$y^{k+1}\leftarrow
y^{k}+\beta_{k}\big{(}\mathcal{A}(X^{k}-\theta_{k}(X^{k}-X^{k-1}))-b\big{)}$

end while

end for

Algorithm 4 Linesearch (LS) [17]

######  Theorem 2.2.

Algorithm 2 and 3 converge to $(X^{*},y^{*})$ such that $0\in
C+\partial_{X}\mathbb{I}_{\mathbb{S}_{+}^{n\times
n}}(X^{*})+\partial_{X}\mathbb{I}_{=b}(\mathcal{A}(X^{*}))$.

It is worth noting that Algorithm 2 and 3, as well as the linesearch strategy
(Algorithm 4), enable adaptive stepsize adjustment, but they are not tuning-
free. They introduce some additional hyperparameters that still need to be
carefully tuned. As verified in our numerical experiments, the hyperparameters
that lead to fast convergence in one scenario may not be a good choice for
another. And manually tuning them is a tedious and disturbing process. To
address this challenge, we develop a stepsize-adjusting strategy for PDHG
(Algorithm 5) that is totally tuning-free. This strategy is originally
designed for DRS [16]. We adapt it to the PDHG scenario based on the
connection [18] between PDHG and DRS. We prove its convergence by showing that
it is a special case of Algorithm 1 (Theorem 2.3).

Input:
$X^{0},y^{1},\epsilon\geq\lambda_{\max}(\mathcal{A}^{T}\mathcal{A}),\theta_{\min}=10^{-5},\theta_{\max}=10^{5},\alpha_{0}=1,\\{\omega_{k}\\}_{k}=\\{2^{-\frac{k}{100}}\\}_{k}$.

for $k=1,2,\dots$ do

$X^{k}\leftarrow\text{Proj}_{\mathbb{S}_{+}^{n\times
n}}\Big{(}X^{k-1}-\alpha_{k-1}\big{(}\mathcal{A}^{T}(y^{k})+C\big{)}\Big{)}$

$\theta_{k}\leftarrow\text{Proj}_{[\theta_{\min},\theta_{\max}]}\Big{(}\frac{\left\lVert\,X^{k}\,\right\rVert}{\left\lVert\,X^{k}-X^{k-1}+\alpha_{k-1}\mathcal{A}^{T}(y^{k})\,\right\rVert}\Big{)}$,
$\alpha_{k}\leftarrow(1-\omega_{k}+\omega_{k}\theta_{k})\alpha_{k-1}$, and
$\beta_{k}\leftarrow\frac{1}{\epsilon\alpha_{k}}$

$y^{k+1}\leftarrow
y^{k}+\beta_{k}\mathcal{A}(X^{k}+\theta_{k}(X^{k}-X^{k-1}))-\beta_{k}b$

end for

Algorithm 5 Tuning-Free PDHG for SDP

######  Theorem 2.3.

Algorithm 5 converges to $(X^{*},y^{*})$ such that $0\in
C+\partial_{X}\mathbb{I}_{\mathbb{S}_{+}^{n\times
n}}(X^{*})+\partial_{X}\mathbb{I}_{=b}(\mathcal{A}(X^{*}))$.

## 3 Numerical Experiments

We compare the performances of Algorithm 5 with three existing adaptive
alternatives: balancing primal dual residuals (B-PDR, Algorithm 2) [12],
aligning local variation of gradient directions (A-LV, Algorithm 3) [25], and
linesearch (LS, Algorithm 4) [17]. We test them on:

  1. 1.

Random generation (RG): $C,\mathcal{A},b$ of (1) is randomly generated, while
feasibility is ensured. In the simulations, we set $m=50$ and $n=50$.

  2. 2.

Maximum cut (MC): Given an undircted graph $G=(V,E)$ comprising a vertex set
$V=\\{1,\dots,n\\}$ and a set $E$ of $m$ edges, an SDP relaxation for solving
maximum cut is

$\displaystyle\min_{x}$ $\displaystyle\quad\langle L,X\rangle$ s.t.
$\displaystyle\quad\text{diag}(X)=1$ $\displaystyle\quad X\succeq 0.$

where $L\coloneqq\sum_{\\{i,j\\}\in
E}(e_{i}-e_{j})(e_{i}-e_{j})^{T}\in\mathbb{R}^{n\times n}$. In the
simulations, we set $m=100$ and $n=100$.

  3. 3.

Sensor network localization (SNL): Given anchors
$\\{a_{1},a_{2},\dots,a_{m}\\}\subset\mathbb{R}^{p}$, distance information
$d_{ij},\ (i,j)\in\mathcal{N}_{x}\coloneqq\Big{\\{}(i,j):i<j,\ d_{ij}\
\text{is specified}\Big{\\}}$, and $\hat{d}_{kj},\
(k,j)\in\mathcal{N}_{a}\coloneqq\Big{\\{}(k,j):\hat{d}_{kj}\ \text{is
specified}\Big{\\}}$, sensor network localization finds
$\\{x_{1},x_{2},\dots,x_{n}\\}\subset\mathbb{R}^{p}$ for all $i$ such that

$\displaystyle\left\lVert\,x_{i}-x_{j}\,\right\rVert^{2}=d_{ij}^{2},\quad\forall\
(i,j)\in\mathcal{N}_{x},$
$\displaystyle\left\lVert\,a_{k}-x_{j}\,\right\rVert^{2}=\hat{d}_{kj}^{2},\quad\forall\
(k,j)\in\mathcal{N}_{a}.$

Let $X=\big{[}x_{1}\ x_{2}\ \cdots\ x_{n}\big{]}\in\mathbb{R}^{p\times n}$.
Then an SDP relaxation for solving this problem is finding a symmetric matrix
$Z\in\mathbb{S}^{(p+n)\times(p+n)}$ such that

$\displaystyle\min_{Z}$ $\displaystyle\quad 0$ s.t.
$\displaystyle\quad(e_{i}-e_{j})(e_{i}-e_{j})^{T}\bullet Y=d_{ij}^{2},\
\forall(i,j)\in\mathcal{N}_{x}$ $\displaystyle\quad\begin{pmatrix}a_{k}\\\
-e_{j}\end{pmatrix}{\begin{pmatrix}a_{k}\\\
-e_{j}\end{pmatrix}}^{T}\bullet\begin{pmatrix}I_{p\times p}&X\\\
X^{T}&Y\end{pmatrix}=\hat{d}_{kj}^{2},\ \forall(k,j)\in\mathcal{N}_{a}$
$\displaystyle\quad Z\coloneqq\begin{pmatrix}I_{p\times p}&X\\\
X^{T}&Y\end{pmatrix}\succeq 0.$

In the simulations, we set $m=10,n=50,\texttt{radius}=0.3,\texttt{degree}=5$.
Different from random generation and maximum cut, here $m$ refers to the
number of anchors and $n$ refers to the total number of sensors.

### 3.1 Settings and parameter configurations

The computational bottleneck of applying PDHG to solve large-scale SDP is the
need for full eigenvalue decomposition at each iteration when projecting onto
the positive semidefinite cone. To address this, practitioners usually adopt a
rounding heuristics, updating the primal variables $X^{k}$ by an approximate
projection onto $\mathbb{S}_{+}^{n\times n}$:

$X^{k}\leftarrow\text{A-Proj}^{r}_{\mathbb{S}_{+}^{n\times
n}}\Big{(}\underbrace{X^{k-1}-\alpha_{k-1}\big{(}\mathcal{A}^{T}(y^{k})+C\big{)}}_{\hat{X}^{k-1}}\Big{)}=\sum_{i=1}^{r}\max\\{0,\lambda_{i}\\}u_{i}u_{i}^{T}\in\mathbb{S}_{+}^{n\times
n},$

where $\lambda_{1}\geq\lambda_{2}\geq\dots\geq\lambda_{r}$ are the first $r$
eigenvalues of $\hat{X}^{k-1}$, and $u_{1},u_{2},\dots,u_{r}$ are the
associated eigenvectors. This approximation can be efficiently computed by
iterative algorithms, such as the Lanczos algorithm, which only requires
matrix-vector products. We set $r$ to be $\log(n)$ in the simulations.

For B-PDR (Algorithm 2) and A-LV (Algorithm 3), we set $\epsilon_{0}=0.5$ and
perform a grid search on $\eta\in\left\\{0.9,0.925,0.95,0.975,0.99\right\\}$.
We test each set of configurations on $33$ random generation, $34$ maximum
cut, and $33$ sensor network localization with different random seeds,
resulting in $100$ different structures of $C,\mathcal{A},b$ (See the code for
details of the generation). $\eta$ is finally set to be $0.95$, as B-PDR and
A-LV with such configuration solves $86\%$ and $83\%$ of the simulated
problems with the fastest convergence speed. For LS (Algorithm 4), we set
$s\in\\{\frac{1}{10},\frac{1}{5},1,10\\}$.

For the stopping criteria, the algorithms are terminated once
$\left\lVert\,p^{k}\,\right\rVert^{2}+\left\lVert\,d^{k}\,\right\rVert^{2}<{10}^{-6}$,
where

$\displaystyle
p^{k+1}=\frac{1}{\alpha_{k}}(x^{k}-x^{k+1})-A^{T}(y^{k}-y^{k+1})\in\partial
f(x^{k+1})+A^{T}y^{k+1}=p(x^{k+1},y^{k+1}),$ $\displaystyle
d^{k+1}=\frac{1}{\beta_{k}}(y^{k}-y^{k+1})-A(x^{k}-x^{k+1})\in\partial
g(y^{k+1})+Ax^{k+1}=d(x^{k+1},y^{k+1}).$

### 3.2 Results and discussion

For each problem in {RG, MC, SNL}, we run $100$ times with different random
seeds, resulting in $100$ different structures of $C,\mathcal{A},b$. Table 1
records the percent of the solved problems within a certain number of
iterations for each algorithm. For example, the entry $\left(2,2\right)$ in
Table 1 means the proposed tuning-free algorithm solves $38\%$ of the
simulated RG problems within $5000$ iterations. Figure 1 plots the
$\left\\{\log(\left\lVert\,p^{k}\,\right\rVert^{2}+\left\lVert\,d^{k}\,\right\rVert^{2})-\texttt{iteration}\right\\}$-curve
with respect to
$\texttt{rng(1)},\texttt{rng(2)},\texttt{rng(3)},\texttt{rng(4)}$.

The proposed tuning-free algorithm shows superior convergence speed and
robustness, outperforming other baselines. Moreover, linesearch does not have
a one-size-fit-all choice of $s$. Indeed, its performances highly depends on
problems and settings. For example, in the second row of Figure 1, linesearch
with $s=\frac{1}{5}$ achieves the fastest convergence speed for rng(3),
achieves a mediocre convergence speed for rng(1), and diverges in the rest.

Figure 1: The rows from top to bottom are the results of RG, MC, and SNL. The columns from left to right are the results of rng(1), rng(2), rng(3), and rng(4). RG | Proposed |  LS $(s=10)$ |  LS $(s=1)$ |  LS $(s=1/5)$ |  LS $(s=1/10)$ | B-PDR | A-LV
---|---|---|---|---|---|---|---
$<5000$ | $38\%$ | $5\%$ | $0\%$ | $1\%$ | $3\%$ | $8\%$ | $3\%$
$<10000$ | $55\%$ | $21\%$ | $22\%$ | $17\%$ | $18\%$ | $34\%$ | $41\%$
$<25000$ | $89\%$ | $78\%$ | $62\%$ | $75\%$ | $80\%$ | $73\%$ | $76\%$
MC | Proposed |  LS $(s=10)$ |  LS $(s=1)$ |  LS $(s=1/5)$ |  LS $(s=1/10)$ | B-PDR | A-LV
$<2500$ | $70\%$ | $0\%$ | $7\%$ | $23\%$ | $20\%$ | $45\%$ | $33\%$
$<5000$ | $87\%$ | $25\%$ | $19\%$ | $26\%$ | $35\%$ | $69\%$ | $36\%$
$<10000$ | $91\%$ | $63\%$ | $80\%$ | $73\%$ | $69\%$ | $88\%$ | $66\%$
SNL | Proposed |  LS $(s=10)$ |  LS $(s=1)$ |  LS $(s=1/5)$ |  LS $(s=1/10)$ | B-PDR | A-LV
$<7500$ | $24\%$ | $22\%$ | $0\%$ | $10\%$ | $5\%$ | $11\%$ | $1\%$
$<15000$ | $60\%$ | $30\%$ | $27\%$ | $25\%$ | $16\%$ | $34\%$ | $41\%$
$<30000$ | $73\%$ | $54\%$ | $33\%$ | $59\%$ | $40\%$ | $62\%$ | $62\%$
Table 1: The blocks from top to bottom are the results of RG, MC, and SNL.

##  Appendix A Appendix

### A.1 Proof of Theorem 2.1

See 2.1

###### Proof.

The core idea of the proof comes from Section 4 of [18], which shows that PDHG
can be viewed as a special case of DRS. It allows us to translate known
convergence results from [16] on non-stationary DRS to Algorithm 1.

We first show that Algorithm 1 is a instance of non-stationary DRS, which is
extensively studied in [16],

$\displaystyle
z^{k+1}=J_{\alpha_{k}A}\left(J_{\alpha_{k-1}B}(z^{k})+\frac{\alpha_{k}}{\alpha_{k-1}}\Big{(}J_{\alpha_{k-1}B}(z^{k})-z^{k}\Big{)}\right)+\frac{\alpha_{k}}{\alpha_{k-1}}\left(z^{k}-J_{\alpha_{k-1}B}(z^{k})\right),$

where $A$ and $B$ are two maximally monotone operators. Note that if the
stepsize is fixed, non-stationary DRS is reduced to the vanilla one

$\displaystyle z^{k+1}=J_{\alpha A}\left(2J_{\alpha
B}(z^{k})-z^{k}\right)+z^{k}-J_{\alpha B}(z^{k}).$

Similar to [18], we introduce a linear operator
$\mathcal{T}\colon\mathbb{S}^{n\times n}\to\mathbb{R}^{m}$ and then
reformulate the primal form of SDP (1) as

$\displaystyle\min_{X}\quad\langle
C,X\rangle+\mathbb{I}_{\mathbb{S}_{+}^{n\times
n}}(X)+\mathbb{I}_{=0}(\hat{X})+\mathbb{I}_{=b}\left(\mathcal{A}(X)+\mathcal{T}(\hat{X})\right),$

which is equivalent to the following monotone inclusion problem:

$\displaystyle\text{Find}\ \begin{pmatrix}X\\\
\hat{X}\end{pmatrix}\quad\text{s.t.}\quad 0\in\underbrace{\begin{pmatrix}C\\\
0\end{pmatrix}+\begin{pmatrix}\partial_{X}\mathbb{I}_{\mathbb{S}_{+}^{n\times
n}}(X)\\\ 0\end{pmatrix}+\begin{pmatrix}0\\\
\partial_{\hat{X}}\mathbb{I}_{=0}(\hat{X})\end{pmatrix}}_{B=\partial
f(X,\hat{X})}+\underbrace{\begin{pmatrix}\partial_{X}\mathbb{I}_{=b}(\mathcal{A}(X)+\mathcal{T}(\hat{X}))\\\
\partial_{\hat{X}}\mathbb{I}_{=b}(\mathcal{A}(X)+\mathcal{T}(\hat{X}))\end{pmatrix}}_{A=\partial
g(X,\hat{X})},$ (3)

where $\partial f(X,\hat{X})$ and $\partial g(X,\hat{X})$ are maximally
monotone. Applying non-stationary DRS to (3) with $z=\begin{pmatrix}X\\\
\hat{X}\end{pmatrix}$, we get the following fixed-point iteration:

$\displaystyle\begin{pmatrix}X^{k}\\\
\hat{X}^{k}\end{pmatrix}=J_{\alpha_{k-1}\partial
f}\Bigg{(}\begin{pmatrix}Z^{k}\\\ \hat{Z}^{k}\end{pmatrix}\Bigg{)}$ (4)
$\displaystyle\begin{pmatrix}X^{k+\frac{1}{2}}\\\
\hat{X}^{k+\frac{1}{2}}\end{pmatrix}=J_{\alpha_{k}\partial
g}\Bigg{(}\begin{pmatrix}X^{k}\\\
\hat{X}^{k}\end{pmatrix}+\theta_{k}\bigg{(}\begin{pmatrix}X^{k}\\\
\hat{X}^{k}\end{pmatrix}-\begin{pmatrix}Z^{k}\\\
\hat{Z}^{k}\end{pmatrix}\bigg{)}\Bigg{)}$ (5)
$\displaystyle\begin{pmatrix}Z^{k+1}\\\
\hat{Z}^{k+1}\end{pmatrix}=\begin{pmatrix}X^{k+\frac{1}{2}}\\\
\hat{X}^{k+\frac{1}{2}}\end{pmatrix}+\theta_{k}\Bigg{(}\begin{pmatrix}Z^{k}\\\
\hat{Z}^{k}\end{pmatrix}-\begin{pmatrix}X^{k}\\\
\hat{X}^{k}\end{pmatrix}\Bigg{)}.$ (6)

(4) can be simplified to

$\displaystyle X^{k}$
$\displaystyle=\operatorname*{arg\,min}_{X}\Big{\\{}\langle
C,X\rangle+\mathbb{I}_{\mathbb{S}_{+}^{n\times
n}}(X)+\frac{1}{2\alpha_{k-1}}\left\lVert\,X-Z^{k}\,\right\rVert^{2}\Big{\\}}$
(7) $\displaystyle\hat{X}^{k}$ $\displaystyle=0$

(5) can be simplified to

$\displaystyle\begin{pmatrix}X^{k+\frac{1}{2}}\\\
\hat{X}^{k+\frac{1}{2}}\end{pmatrix}$ $\displaystyle=J_{\alpha_{k}\partial
g}\Bigg{(}\begin{pmatrix}X^{k}\\\
\hat{X}^{k}\end{pmatrix}+\theta_{k}\bigg{(}\begin{pmatrix}X^{k}\\\
\hat{X}^{k}\end{pmatrix}-\begin{pmatrix}Z^{k}\\\
\hat{Z}^{k}\end{pmatrix}\bigg{)}\Bigg{)}{}$
$\displaystyle=\Bigg{(}1+\alpha_{k}\partial
g\Bigg{)}^{-1}\Bigg{(}\begin{pmatrix}X^{k}\\\
\hat{X}^{k}\end{pmatrix}+\theta_{k}\bigg{(}\begin{pmatrix}X^{k}\\\
\hat{X}^{k}\end{pmatrix}-\begin{pmatrix}Z^{k}\\\
\hat{Z}^{k}\end{pmatrix}\bigg{)}\Bigg{)}{}$
$\displaystyle\Longleftrightarrow{}$
$\displaystyle\begin{pmatrix}X^{k}+\theta_{k}(X^{k}-Z^{k})\\\
-\theta_{k}\hat{Z}^{k}\end{pmatrix}\in\begin{pmatrix}X^{k+\frac{1}{2}}\\\
\hat{X}^{k+\frac{1}{2}}\end{pmatrix}+\alpha_{k}\mathcal{A}^{T}\bigg{(}\partial\mathbb{I}_{=b}\Big{(}\mathcal{A}\big{(}X^{k+\frac{1}{2}})+\mathcal{T}\big{(}\hat{X}^{k+\frac{1}{2}})\Big{)}\bigg{)}{}$
$\displaystyle\Longleftrightarrow{}$ $\displaystyle
y^{k+1}\in\partial\mathbb{I}_{=b}\Big{(}\mathcal{A}\big{(}X^{k+\frac{1}{2}})+\mathcal{T}\big{(}\hat{X}^{k+\frac{1}{2}})\Big{)}{}$
$\displaystyle
X^{k+\frac{1}{2}}+\alpha_{k}\mathcal{A}^{T}(y^{k+1})=X^{k}+\theta_{k}(X^{k}-Z^{k}){}$
$\displaystyle\hat{X}^{k+\frac{1}{2}}+\alpha_{k}\mathcal{T}^{T}(y^{k+1})=-\theta_{k}\hat{Z}^{k}{}$
$\displaystyle\Longleftrightarrow{}$
$\displaystyle\mathcal{A}\big{(}X^{k+\frac{1}{2}})+\mathcal{T}\big{(}\hat{X}^{k+\frac{1}{2}})\in\partial_{y}\mathbb{I}^{*}_{=b}(y^{k+1}){}$
$\displaystyle
X^{k+\frac{1}{2}}=X^{k}+\theta_{k}(X^{k}-Z^{k})-\alpha_{k}\mathcal{A}^{T}(y^{k+1}){}$
$\displaystyle\hat{X}^{k+\frac{1}{2}}=-\theta_{k}\hat{Z}^{k}-\alpha_{k}\mathcal{T}^{T}(y^{k+1}){}$
$\displaystyle\Longleftrightarrow{}$
$\displaystyle\mathcal{A}\big{(}X^{k}+\theta_{k}(X^{k}-Z^{k})\big{)}-\theta_{k}\mathcal{T}\big{(}\hat{Z}^{k}\big{)}-\alpha_{k}\mathcal{A}\big{(}\mathcal{A}^{T}(y^{k+1})\big{)}-\alpha_{k}\mathcal{T}\big{(}\mathcal{T}^{T}(y^{k+1})\big{)}\in\partial_{y}\mathbb{I}^{*}_{=b}(y^{k+1}){}$
$\displaystyle
X^{k+\frac{1}{2}}=X^{k}+\theta_{k}(X^{k}-Z^{k})-\alpha_{k}\mathcal{A}^{T}(y^{k+1}){}$
$\displaystyle\hat{X}^{k+\frac{1}{2}}=-\theta_{k}\hat{Z}^{k}-\alpha_{k}\mathcal{T}^{T}(y^{k+1}){}$
$\displaystyle\Longleftrightarrow{}$ $\displaystyle
y^{k+1}=\operatorname*{arg\,min}_{y}\Big{\\{}\mathbb{I}_{=b}^{*}(y)-\Big{\langle}\mathcal{A}\big{(}X^{k}+\theta_{k}(X^{k}-Z^{k})\big{)}-\theta_{k}\mathcal{T}\big{(}\hat{Z}^{k}\big{)},y\Big{\rangle}{}$
$\displaystyle\quad\quad\quad\quad\quad+\frac{\alpha_{k}}{2}(\left\lVert\,\mathcal{A}^{T}(y)\,\right\rVert^{2}+\left\lVert\,\mathcal{T}^{T}(y)\,\right\rVert^{2})\Big{\\}}$
(8) $\displaystyle
X^{k+\frac{1}{2}}=X^{k}+\theta_{k}(X^{k}-Z^{k})-\alpha_{k}\mathcal{A}^{T}(y^{k+1}){}$
$\displaystyle\hat{X}^{k+\frac{1}{2}}=-\theta_{k}\hat{Z}^{k}-\alpha_{k}\mathcal{T}^{T}(y^{k+1}){},$

(6) can be simplified to

$\displaystyle Z^{k+1}$
$\displaystyle=X^{k}-\alpha_{k}\mathcal{A}^{T}(y^{k+1})$ (9)
$\displaystyle\hat{Z}^{k+1}$
$\displaystyle=-\alpha_{k}\mathcal{T}^{T}(y^{k+1}).$ (10)

Substituting (9) into (7), we get

$\displaystyle X^{k}$
$\displaystyle=\operatorname*{arg\,min}_{X}\Big{\\{}\langle
C,X\rangle+\mathbb{I}_{\mathbb{S}_{+}^{n\times
n}}(X)+\frac{1}{2\alpha_{k-1}}\left\lVert\,X-\big{(}X^{k-1}-\alpha_{k-1}\mathcal{A}^{T}(y^{k})\big{)}\,\right\rVert^{2}\Big{\\}}$
$\displaystyle=\text{Prox}_{\alpha_{k-1}\left(\langle
C,\cdot\rangle+\mathbb{I}_{\mathbb{S}_{+}^{n\times
n}}(\cdot)\right)}\Big{(}X^{k-1}-\alpha_{k-1}\mathcal{A}^{T}(y^{k})\Big{)}$
$\displaystyle=\text{Prox}_{\alpha_{k-1}\mathbb{I}_{\mathbb{S}_{+}^{n\times
n}}(\cdot)}\Big{(}X^{k-1}-\alpha_{k-1}\mathcal{A}^{T}(y^{k})-\alpha_{k-1}C\Big{)}$
$\displaystyle=\text{Proj}_{\mathbb{S}_{+}^{n\times
n}}\Big{(}X^{k-1}-\alpha_{k-1}\mathcal{A}^{T}(y^{k})-\alpha_{k-1}C\Big{)}$
(11)

Substituting (9) and (10) into (8), we get

$\displaystyle y^{k+1}$
$\displaystyle=\operatorname*{arg\,min}_{y}\Big{\\{}\mathbb{I}_{=b}^{*}(y)-\langle\mathcal{A}(X^{k}+\theta_{k}(X^{k}-X^{k-1})),y\rangle+\frac{\alpha_{k}}{2}\left\lVert\,y-y^{k}\,\right\rVert^{2}_{\mathcal{A}\mathcal{A}^{T}+\mathcal{T}\mathcal{T}^{T}}\Big{\\}}.$

By Lemma A.1, we can find a $\mathcal{T}$ such that
$\mathcal{T}\mathcal{T}^{T}=\frac{1}{R}\mathcal{I}-\mathcal{A}\mathcal{A}^{T}$,
$\alpha_{k}\beta_{k}=R<\frac{1}{\lambda_{\max}(\mathcal{A}^{T}\mathcal{A})}$
for $k=1,2,\dots$, and then get

$\displaystyle y^{k+1}$
$\displaystyle=\text{Prox}_{\beta_{k}\left(\mathbb{I}_{=b}(\cdot)\right)^{*}}(y^{k}+\beta_{k}\mathcal{A}(X^{k}-\theta_{k}(X^{k}-X^{k-1})))$
$\displaystyle=y^{k}+\beta_{k}\mathcal{A}(X^{k+1}-\theta_{k}(X^{k}-X^{k-1}))-\beta_{k}\text{Prox}_{\frac{1}{\beta_{k}}\mathbb{I}_{=b}(\cdot)}(\frac{y^{k}+\beta_{k}\mathcal{A}(X^{k}-\theta_{k}(X^{k}-X^{k-1}))}{\beta_{k}})$
$\displaystyle=y^{k}+\beta_{k}\mathcal{A}(X^{k}-\theta_{k}(X^{k}-X^{k-1}))-\beta_{k}\text{Proj}_{=b}(\frac{y^{k}+\beta_{k}\mathcal{A}(X^{k}-\theta_{k}(X^{k}-X^{k-1}))}{\beta_{k}})$
$\displaystyle=y^{k}+\beta_{k}\mathcal{A}(X^{k}-\theta_{k}(X^{k}-X^{k-1}))-\beta_{k}b.$

Finally, we have

$\displaystyle X^{k}=\text{Proj}_{\mathbb{S}_{+}^{n\times
n}}\Big{(}X^{k-1}-\alpha_{k-1}\mathcal{A}^{T}(y^{k})-\alpha_{k-1}C\Big{)}$
$\displaystyle
y^{k+1}=y^{k}+\beta_{k}\mathcal{A}(X^{k}-\theta_{k}(X^{k}-X^{k-1}))-\beta_{k}b$

where $X^{k}$ and $y^{k+1}$ are the primal and dual variables of SDP,
respectively. Since Algorithm 1 is an instance of non-stationary DRS, we can
conclude the proof by Theorem A.1. ∎

######  Lemma A.1.

There exists linear operator $\mathcal{T}\colon\mathbb{R}^{n\times
n}\rightarrow\mathbb{R}^{m}$ such that
$\mathcal{T}\mathcal{T}^{T}=\frac{1}{R}\mathcal{I}-\mathcal{A}\mathcal{A}^{T}$.

###### Proof.

A constructive proof is provided here. Let the vectorization of
$X,A_{1},\dots,A_{m}$ be
$\text{vec}(X),\text{vec}(A_{1}),\dots,\text{vec}(A_{m})\in\mathbb{R}^{n^{2}}$,
respectively. Define the matrix representation of linear operators
$\mathcal{T}$ and $\mathcal{A}$ as

$\displaystyle T=\begin{bmatrix}\text{vec}(T_{1})^{T}\\\ \vdots\\\
\text{vec}(T_{m})^{T}\end{bmatrix}\in\mathbb{R}^{m\times n^{2}},\quad
A=\begin{bmatrix}\text{vec}(A_{1})^{T}\\\ \vdots\\\
\text{vec}(A_{m})^{T}\end{bmatrix}\in\mathbb{R}^{m\times n^{2}}.$

Define $S:=\frac{1}{R}I-AA^{T}\succ 0$. Since $m\leq n^{2}$, $T$ can be
constructed as

$\displaystyle T=\begin{bmatrix}\sqrt{\lambda_{1}}v_{1}\\\ \vdots\\\
\sqrt{\lambda_{m}}v_{m}\\\ \mathbf{0}^{m\times(n^{2}-m)}\end{bmatrix},$

where $S$ is eigenvalue-decomposed as
$S=\sum_{i=1}^{m}\lambda_{i}v_{i}v_{i}^{T}$. Since $TT^{T}=S$, $T$ is the
desired matrix representation of $\mathcal{T}$. Therefore, we have explicitly
construct the linear operator $\mathcal{T}$. ∎

######  Theorem A.1.

Let $A$ and $B$ be maximally monotone and $\\{\alpha_{k}\\}_{k}$ be a positive
sequence such as

$\displaystyle\alpha_{k}\in\left(\alpha_{\min},\alpha_{\max}\right),\quad\sum_{k=1}^{\infty}\left|\alpha_{k+1}-\alpha_{k}\right|<\infty,$

where $0<\alpha_{\min}\leq\alpha_{\max}<\infty$. Then non-stationary DRM

$\displaystyle
z^{k+1}=J_{\alpha_{k}A}\left(J_{\alpha_{k-1}B}(z^{k})+\frac{\alpha_{k}}{\alpha_{k-1}}\Big{(}J_{\alpha_{k-1}B}(z^{k})-z^{k}\Big{)}\right)+\frac{\alpha_{k}}{\alpha_{k-1}}\left(z^{k}-J_{\alpha_{k-1}B}(z^{k})\right),$

weakly converges to $z^{*}$ such that $0\in(A+B)(z^{*})$.

###### Proof.

It is the restatement of Theorem 3.2. of [16]. ∎

### A.2 Proof of Theorem 2.2

See 2.2

###### Proof.

Since $\theta_{k}=\frac{\alpha_{k}}{\alpha_{k-1}}$ and
$\alpha_{k}\beta_{k}=R<\frac{1}{\lambda_{\max}\left(\mathcal{A}^{T}\mathcal{A}\right)}$
are automatically satisfied by Algorithm 2 and 3, it suffices to shows
$\alpha_{k}\in\left(\alpha_{\min},\alpha_{\max}\right)$ and
$\sum_{k=1}^{\infty}\left|\alpha_{k+1}-\alpha_{k}\right|<\infty$. To prove the
boundedness of $\alpha_{k}$, we assume $\alpha_{k}$ is increased at each
iteration without loss of generality, i.e.,
$\alpha_{k+1}=\frac{\alpha_{k}}{1-\epsilon_{k}}=\alpha_{0}\prod_{i=0}^{k+1}\frac{1}{1-\epsilon_{i}}=\alpha_{0}\prod_{i=0}^{k+1}\frac{1}{1-\epsilon_{0}\eta^{i}}$.
We wish to show $\left\\{\alpha_{k}\right\\}$ is a convergent sequence, so
that it is bounded. And it is sufficient to show $\left\\{x_{k}\right\\}$,
where
$x_{k+1}=\log\left(\prod_{i=0}^{k+1}\frac{1}{1-\epsilon_{i}}\right)=\sum_{i=0}^{k+1}\log\left(\frac{1}{1-\epsilon_{0}\eta^{i}}\right)$,
is convergent since $\alpha_{0}$ is a constant. Since $\lim_{x\to
0}\frac{\ln(1+x)}{x}=1$, we have

$\displaystyle\lim_{i\to\infty}\frac{\log\left(\frac{1}{1-\epsilon_{0}\eta^{i+1}}\right)}{\log\left(\frac{1}{1-\epsilon_{0}\eta^{i}}\right)}=\lim_{i\to\infty}\frac{\log\left(\frac{1}{1-\epsilon_{0}\eta^{i+1}}\right)}{\frac{\epsilon_{0}\eta^{i+1}}{1-\epsilon_{0}\eta^{i+1}}}\times\frac{\frac{\epsilon_{0}\eta^{i+1}}{1-\epsilon_{0}\eta^{i+1}}}{\frac{\epsilon_{0}\eta^{i}}{1-\epsilon_{0}\eta^{i}}}\times\frac{\frac{\epsilon_{0}\eta^{i}}{1-\epsilon_{0}\eta^{i}}}{\log\left(\frac{1}{1-\epsilon_{0}\eta^{i}}\right)}=\lim_{i\to\infty}\frac{\eta-\eta^{i+1}\epsilon_{0}}{1-\eta^{i+1}\epsilon_{0}}=\eta<1.$

By ratio test, $x_{n}$ is convergent. We now show that
$\sum_{k=1}^{\infty}\left|\alpha_{k+1}-\alpha_{k}\right|<\infty$. Since
$1-\epsilon_{0}\eta^{k}>\frac{1}{2}\Leftrightarrow\log\left(\frac{1}{2\epsilon_{0}}\right)>k\log\left(\eta\right)\Leftrightarrow\underbrace{\frac{\log\left(\frac{1}{2\epsilon_{0}}\right)}{\log\left(\eta\right)}}_{=k^{*}}>k$,
we have

$\displaystyle\sum_{k=0}^{\infty}\left|\alpha_{k+1}-\alpha_{k}\right|$
$\displaystyle\leq\sum_{k=0}^{\infty}\left|\frac{\alpha_{k}}{1-\epsilon_{k}}-\alpha_{k}\right|+\sum_{k=0}^{\infty}\left|(1-\epsilon_{k})\alpha_{k}-\alpha_{k}\right|+\sum_{k=0}^{\infty}\left|\alpha_{k}-\alpha_{k}\right|$
$\displaystyle\leq\sum_{k=0}^{\infty}\frac{\epsilon_{k}}{1-\epsilon_{k}}\alpha_{k}+\sum_{k=0}^{\infty}\epsilon_{k}\alpha_{k}$
$\displaystyle\leq\alpha_{\max}\sum_{k=0}^{\infty}\left(\frac{\epsilon_{k}}{1-\epsilon_{k}}+\epsilon_{k}\right)$
$\displaystyle=\alpha_{\max}\sum_{k=0}^{\infty}\left(\frac{\epsilon_{0}\eta^{k}}{1-\epsilon_{0}\eta^{k}}+\epsilon_{0}\eta^{k}\right)$
$\displaystyle\leq\alpha_{\max}\sum_{k=0}^{\left\lceil
k^{*}\right\rceil}\left(\frac{\epsilon_{0}\eta^{k}}{1-\epsilon_{0}\eta^{k}}+\epsilon_{0}\eta^{k}\right)+\alpha_{\max}\sum_{k=\left\lceil
k^{*}\right\rceil+1}^{\infty}\left(\frac{\epsilon_{0}\eta^{k}}{\frac{1}{2}}+\epsilon_{0}\eta^{k}\right)$
$\displaystyle=\alpha_{\max}\sum_{k=0}^{\left\lceil
k^{*}\right\rceil}\left(\frac{\epsilon_{0}\eta^{k}}{1-\epsilon_{0}\eta^{k}}+\epsilon_{0}\eta^{k}\right)+3\epsilon_{0}\alpha_{\max}\sum_{k=\left\lceil
k^{*}\right\rceil+1}^{\infty}\eta^{k}$
$\displaystyle=\alpha_{\max}\sum_{k=0}^{\left\lceil
k^{*}\right\rceil}\left(\frac{\epsilon_{0}\eta^{k}}{1-\epsilon_{0}\eta^{k}}+\epsilon_{0}\eta^{k}\right)+3\epsilon_{0}\alpha_{\max}\frac{\eta^{\left\lceil
k^{*}\right\rceil+1}}{1-\eta}<\infty.$

We then conclude the proof by Theorem A.1. ∎

### A.3 Proof of Theorem 2.3

See 2.3

###### Proof.

Since $\langle C,X\rangle+\mathbb{I}_{\mathbb{S}_{+}^{n\times
n}}(X)+\mathbb{I}_{=0}(\hat{X})$ and
$\mathbb{I}_{=b}(\mathcal{A}(X)+\mathcal{T}(\hat{X}))$ are closed, convex,
proper functions with respect to $\begin{pmatrix}X\\\ \hat{X}\end{pmatrix}$,
we have

$\displaystyle\begin{pmatrix}C\\\
0\end{pmatrix}+\begin{pmatrix}\partial_{X}\mathbb{I}_{\mathbb{S}_{+}^{n\times
n}}(X)\\\ 0\end{pmatrix}+\begin{pmatrix}0\\\
\partial_{\hat{X}}\mathbb{I}_{=0}(\hat{X})\end{pmatrix}$

and

$\displaystyle\begin{pmatrix}\partial_{X}\mathbb{I}_{=b}(\mathcal{A}(X)+\mathcal{T}(\hat{X}))\\\
\partial_{\hat{X}}\mathbb{I}_{=b}(\mathcal{A}(X)+\mathcal{T}(\hat{X}))\end{pmatrix}$

are maximally monotone operators. Since

$\displaystyle\omega_{i}\min\\{|1-\theta_{\text{min}}|,|1-\theta_{\text{max}}|\\}\leq|(1-\omega_{i}+\omega_{i}\theta_{i})-1|=\omega_{i}|1-\theta_{i}|\leq\omega_{i}\max\\{|1-\theta_{\text{min}}|,|1-\theta_{\text{max}}|\\},$

$\omega_{i}>0,\ \forall i$ and $\sum_{i=0}^{\infty}\omega_{i}<\infty$, we have
$\sum_{i=0}^{\infty}|(1-\omega_{i}+\omega_{i}\theta_{i})-1|<\infty$. It
implies $(1-\omega_{i}+\omega_{i}\theta_{i})\rightarrow 1$ and
$\prod_{i=1}^{k}(1-\omega_{i}+\omega_{i}\theta_{i})\rightarrow c$ for a
certain $c\in\mathbb{R}_{++}$. Therefore, we have

$\displaystyle\alpha_{k}=(1-\omega_{k}+\omega_{k}\theta_{k})\alpha_{k-1}=\prod_{i=1}^{k}(1-\omega_{i}+\omega_{i}\theta_{i})\alpha_{0}\rightarrow
c\alpha_{0}>0\Longrightarrow\sum_{i=1}^{\infty}|\alpha_{k}-\alpha_{k-1}|<\infty.$

Moreover, since

$\displaystyle\theta_{\text{min}}=\min\\{1,\theta_{\text{min}}\\}\leq(1-\omega_{i}+\omega_{i}\theta_{\text{min}})\leq(1-\omega_{i}+\omega_{i}\theta_{i})\leq(1-\omega_{i}+\omega_{i}\theta_{\text{max}})\leq\max\\{1,\theta_{\text{max}}\\}=\theta_{\text{max}},$

we have

$\displaystyle\theta_{\text{min}}\alpha_{0}\leq\alpha_{k}=\prod_{i=1}^{k}(1-\omega_{i}+\omega_{i}\theta_{i})\alpha_{0}\leq\theta_{\text{max}}\alpha_{0},$

which implies $\alpha_{k}$ is uniformly bounded. We then conclude the proof by
Theorem A.1. ∎

## References

  * [1] Aws Albarghouthi “Introduction to neural network verification” In _Foundations and Trends® in Programming Languages_ 7.1–2 Now Publishers, Inc., 2021, pp. 1–157
  * [2] David Applegate et al. “Practical large-scale linear programming using primal-dual hybrid gradient” In _Advances in Neural Information Processing Systems_ 34, 2021, pp. 20243–20257
  * [3] Afonso S Bandeira, Nicolas Boumal and Vladislav Voroninski “On the low-rank approach for semidefinite programs arising in synchronization and community detection” In _Conference on learning theory_ , 2016, pp. 361–382 PMLR
  * [4] Stephen Boyd et al. “Distributed optimization and statistical learning via the alternating direction method of multipliers” In _Foundations and Trends® in Machine learning_ 3.1 Now Publishers, Inc., 2011, pp. 1–122
  * [5] Antonin Chambolle and Thomas Pock “A first-order primal-dual algorithm for convex problems with applications to imaging” In _Journal of mathematical imaging and vision_ 40 Springer, 2011, pp. 120–145
  * [6] Laurent Condat “A primal–dual splitting method for convex optimization involving Lipschitzian, proximable and linear composite terms” In _Journal of optimization theory and applications_ 158.2 Springer, 2013, pp. 460–479
  * [7] Alexandre d’Aspremont, Laurent Ghaoui, Michael Jordan and Gert Lanckriet “A direct formulation for sparse PCA using semidefinite programming” In _Advances in neural information processing systems_ 17, 2004
  * [8] Jim Douglas and Henry H Rachford “On the numerical solution of heat conduction problems in two and three space variables” In _Transactions of the American mathematical Society_ 82.2, 1956, pp. 421–439
  * [9] Murat A Erdogdu, Yash Deshpande and Andrea Montanari “Inference in graphical models via semidefinite programming hierarchies” In _Advances in Neural Information Processing Systems_ 30, 2017
  * [10] Michael Garstka, Mark Cannon and Paul Goulart “COSMO: A conic operator splitting method for convex conic problems” In _Journal of Optimization Theory and Applications_ 190.3 Springer, 2021, pp. 779–810
  * [11] Tom Goldstein, Min Li and Xiaoming Yuan “Adaptive primal-dual splitting methods for statistical learning and image processing” In _Advances in neural information processing systems_ 28, 2015
  * [12] Tom Goldstein et al. “Adaptive primal-dual hybrid gradient methods for saddle-point problems” In _arXiv preprint arXiv:1305.0546_ , 2013
  * [13] Gurobi Optimization, LLC “Gurobi Optimizer Reference Manual”, 2023 URL: https://www.gurobi.com
  * [14] Brian Kulis, Arun C Surendran and John C Platt “Fast low-rank semidefinite programming for embedding and clustering” In _Artificial Intelligence and Statistics_ , 2007, pp. 235–242 PMLR
  * [15] Pierre-Louis Lions and Bertrand Mercier “Splitting algorithms for the sum of two nonlinear operators” In _SIAM Journal on Numerical Analysis_ 16.6 SIAM, 1979, pp. 964–979
  * [16] Dirk A Lorenz and Quoc Tran-Dinh “Non-stationary Douglas–Rachford and alternating direction method of multipliers: adaptive step-sizes and convergence” In _Computational Optimization and Applications_ 74.1 Springer, 2019, pp. 67–92
  * [17] Yura Malitsky and Thomas Pock “A first-order primal-dual algorithm with linesearch” In _SIAM Journal on Optimization_ 28.1 SIAM, 2018, pp. 411–432
  * [18] Daniel O’Connor and Lieven Vandenberghe “On the equivalence of the primal-dual hybrid gradient method and Douglas–Rachford splitting” In _Mathematical Programming_ 179.1-2 Springer, 2020, pp. 85–108
  * [19] Brendan O’donoghue, Eric Chu, Neal Parikh and Stephen Boyd “Conic optimization via operator splitting and homogeneous self-dual embedding” In _Journal of Optimization Theory and Applications_ 169 Springer, 2016, pp. 1042–1068
  * [20] Jiming Peng and Yu Wei “Approximating k-means-type clustering via semidefinite programming” In _SIAM journal on optimization_ 18.1 SIAM, 2007, pp. 186–205
  * [21] Benjamin Recht, Maryam Fazel and Pablo A Parrilo “Guaranteed minimum-rank solutions of linear matrix equations via nuclear norm minimization” In _SIAM review_ 52.3 SIAM, 2010, pp. 471–501
  * [22] Mario Souto, Joaquim D Garcia and Álvaro Veiga “Exploiting low-rank structure in semidefinite programming by approximate operator splitting” In _Optimization_ 71.1 Taylor & Francis, 2022, pp. 117–144
  * [23] Defeng Sun, Kim-Chuan Toh, Yancheng Yuan and Xin-Yuan Zhao “SDPNAL+: A Matlab software for semidefinite programming with bound constraints (version 1.0)” In _Optimization Methods and Software_ 35.1 Taylor & Francis, 2020, pp. 87–115
  * [24] Zaiwen Wen, Donald Goldfarb and Wotao Yin “Alternating direction augmented Lagrangian methods for semidefinite programming” In _Mathematical Programming Computation_ 2.3-4 Springer, 2010, pp. 203–230
  * [25] Tatsuya Yokota and Hidekata Hontani “An Efficient Method for Adapting Step-size Parameters of Primal-dual Hybrid Gradient Method in Application to Total Variation Regularization” In _2017 Asia-Pacific Signal and Information Processing Association Annual Summit and Conference (APSIPA ASC)_ , 2017, pp. 973–979 IEEE
  * [26] Lena Zdun and Christina Brandt “Fast MPI reconstruction with non-smooth priors by stochastic optimization and data-driven splitting” In _Physics in Medicine & Biology_ 66.17 IOP Publishing, 2021, pp. 175004
  * [27] Xin-Yuan Zhao, Defeng Sun and Kim-Chuan Toh “A Newton-CG augmented Lagrangian method for semidefinite programming” In _SIAM Journal on Optimization_ 20.4 SIAM, 2010, pp. 1737–1765
  * [28] Yang Zheng et al. “Chordal decomposition in operator-splitting methods for sparse semidefinite programs” In _Mathematical Programming_ 180.1-2 Springer, 2020, pp. 489–532


11institutetext: University College Dublin, Dublin, Ireland 22institutetext:
The Insight Centre for Data Analytics, Dublin, Ireland 22email:
<EMAIL_ADDRESS>
22email<EMAIL_ADDRESS>
# Healthcare Data Governance, Privacy, and Security - A Conceptual Framework

Amen Faridoon 1122 0000-0002-2129-4218 M. Tahar Kechadi 1122

###### Abstract

The abundance of data has transformed the world in every aspect. It has become
the core element in decision-making, problem-solving, and innovation in almost
all areas of life, including business, science, healthcare, education, and
many others. Despite all these advances, privacy and security remain critical
concerns of the healthcare industry. It’s important to note that healthcare
data can also be a liability if it is not managed correctly. This data
mismanagement can have severe consequences for patients and healthcare
organisations, including patient safety, legal liability, damage to
reputation, financial loss, and operational inefficiency. Healthcare
organisations must comply with a range of regulations to protect patient data.
We perform a classification of data governance elements/components in a manner
that thoroughly assesses the healthcare data chain from a privacy and security
standpoint. After deeply analysing the existing literature, we propose a
conceptual privacy and security-driven healthcare data governance framework.

###### Keywords:

Healthcare Data Governance Electronic Health Record Governance Medical Data
Protection Conceptual Health Data Governance Framework

##  1 Introduction

Digital data collection has undergone a transformative journey since its
inception. It started with manual data entry and simple electronic databases
in the mid $20^{th}$ century. Since then, the process has gained momentum with
the proliferation of computers and the internet. The $21^{st}$ century has
witnessed an explosion in data sources, from social media and IoT devices to
advanced sensors and machine-generated data. This influx prompted the
development of advanced data collection techniques, including big data
analytics, machine learning, and AI-driven insights. Similarly, healthcare
data collection spans several centuries, evolving from rudimentary record-
keeping to sophisticated digital systems. The $20^{th}$ century saw the rise
of electronic health records (EHRs), allowing for more efficient patient
information storage and retrieval. With the advent of the $21^{st}$ century,
technological advancements enabled the integration of various data sources,
such as wearable devices and mobile apps, contributing to the growth of
comprehensive and real-time healthcare data collection. This evolution has
significantly enhanced healthcare delivery, research, and policy-making by
providing insights into disease patterns, population health trends and
treatment effectiveness.

However, this evolution has also raised concerns about privacy, security, and
ethical considerations, leading to stringent data protection regulations to
balance innovation with individual rights. Healthcare data often contains
sensitive and personal patient information, including medical history,
diagnoses, treatments, prescriptions, test results, social security numbers,
and home addresses, making it highly valuable and vulnerable to misuse and
theft. Table 1 represents the types of information stored in the electronic
health records and their sensitivity level. Data privacy and security are
essential for protecting patient rights, preventing identity theft and cyber-
attacks, maintaining trust in the healthcare system, ensuring continuity of
care, and complying with legal and ethical standards. Unfortunately,
healthcare organizations remain a popular target for hackers due to the
sensitive nature of the data they possess. For instance, in 2020, there were
616 reported data breaches affecting healthcare organizations in the United
States, according to the HIPAA Journal. Recently, in January 2023, LifeBridge
Health in Maryland exposed the personal and medical information of
approximately 1.4 million patients, including names, birth dates, medical
diagnoses, and treatment information. These data breach cases demonstrate the
insufficient implementation and management of security and privacy measures.

Table 1: Types of Information Present in Electronic Health Records and Their
Sensitivity Level

Common Features |  Description |  Sensitivity Level
---|---|---
Entity Identifiers |  Personal identification information such as; name, address, email, phone number etc. |  Identifiable
Demographic Information |  Classification of a person in a specific group such as; age, education, gender, area etc. |  Quasi-Identifiable
Clinical Records |  Patient’s medical history include treatments, diagnoses, medication,n etc. |  Quasi-Identifiable and sensitive
Medical Biometrics |  Patient’s physical health-related information such as; blood pressure, heart rate, X-Ray, test reports etc. |  sensitive
Mental Health Information |  Patient’s psychological related information such as; sleep problems, dietary information, psychosocial issues etc. |  sensitive
Activities and lifestyle |  Person’s physical activities and their lifestyle-related information such as; physical activities, nutrition, exercise plans, etc. |  sensitive
Financial Information |  Person’s financial data such as; health insurance, billing, reimbursements, financial class etc. |  Quasi-Identifiable and sensitive
IoT and Wearable Data |  Person’s wearable and monitoring data include healthcare wearable devices, healthcare IoT devices, sensors data, etc. |  Quasi-Identifiable and sensitive

Inadequate management of data can lead to potential legal responsibilities.
Healthcare organizations need to proactively safeguard patient information
through solid security and privacy protocols to counter various risks.
Considering the sensitivity, usability, and multiple access to electronic
health records, healthcare institutions should adopt preemptive data
governance frameworks. These frameworks ensure operational efficiency without
compromising the confidentiality of data, even from internal individuals with
authorised system access who might have malicious intent. The concept of
Electronic Health Record (EHR) Governance was first introduced by the
Institute of Medicine (IOM) in their 2003 report titled ”Key Capabilities of
an Electronic Health Record System” [4]. This report emphasized the necessity
of a systematic approach to managing EHR systems, including the requirement of
governance structures that could supervise the development, implementation and
maintenance of these systems. Similarly, the report ”Nationwide Privacy and
Security Framework for Electronic Exchange of Individually Identifiable Health
Information” was issued by the US Department of Health and Human Services
(HHS) in 2008 111https://digital.ahrq.gov/health-it-tools-and-
resources/health-it-bibliography/privacy-and-security/nationwide-privacy-and.
This report accentuates the need for governance frameworks to guarantee the
secure and efficient utilisation of Electronic Health Records. Organisations
like the Office of the National Coordinator for Health Information Technology
(ONC) have created guidelines and frameworks to assist EHR governance. These
resources concentrate on aspects such as data privacy, data security, data
quality, and data interoperability. Data governance encompasses the
comprehensive administration of data within an organization. It entails
assigning roles and duties for data management, establishing regulations and
protocols for ensuring data accuracy, confidentiality, protection, and
adherence to regulations, and setting up mechanisms to uphold these
regulations. The primary goal of data governance is to establish well-defined
principles/guidelines for gathering, retaining, accessing, and utilizing data
to optimize its usefulness while minimising potential hazards like data
breaches and legal violations.

##### Contributions:

We have managed to conduct a wide review of the concerns related to data
privacy and security by focusing on or analysing data governance activities in
the healthcare industry. After deeply analyzing the literature, we categorised
data governance activities presented in section 3. The primary goals of this
critical evaluation are as follows:

  * •

Study the existing state-of-the-art healthcare data governance models/systems.

  * •

Categorize the data governance activities/elements in such a way that deeply
analyses the healthcare data chain with the privacy and security perspective.

  * •

Propose a privacy and security-driven conceptual healthcare data governance
framework.

##  2 Existing Healthcare Data Governance Models

Delving into Helen Nissenbaum’s approach (explains privacy as more than just a
right to secrecy or control; instead, it is about the suitable flow of private
information within specific social contexts) to privacy (2010), the study [24]
presenting a fascinating work for accessing data governance in a specific
context of private health data. This study examines the use scenario involving
the Royal Free Trust and Alphabet’s AI Venture DeepMind Health initiative. It
sheds light on the clashes among the partners concerning crucial aspects,
particularly the governance systems, objectives and gain attained via
initiative. Researchers emphasize the intricacies of governing PHI data to
foster healthcare innovation and advancement while safeguarding privacy and
serving the public benefit. In a study [23], the authors discovered six
interconnected yet distinct models for governing Personal Health Information
(PHI) by focusing on what types of value are possibly afforded by PHI beyond
the fundamental concerns of data privacy and security. Five analytical aspects
should be used to administer data governance in the realm of Personal Health
Information (PHI): the field of data, those who are engaged, the significance
or utilization of the PHI, the governance objective, and the governance
platform.

In [13], the authors examined the fundamental model of contemporary data
governance and emphasised five crucial data decision fields: data postulates,
metadata, accuracy, access management, and information management cycle.
Whereas a composite synthesis of research paper [1] evaluates 145 academic and
practitioner papers related to data governance, encompassing the period from
2001 to 2019. The second one suggests a pyramidal governance system that uses
governance mechanisms to balance data, realm, and organizational capacity.
These mechanisms are all structured by organizational ethical and
technological “antecedents” pre-data ingestion and impacted by risk control
and performance-driven “consequences” post hoc. A comparative data governance
activities examination found in academic and practitioner articles is
conducted in [3]. The analysis explored a total of 120 information management
elements that are classified as domains of governance, action, and decision
areas. Authors [6] constructed an organization governance model derived from a
case study, the proposed framework includes three levels and their
interconnections with one another. At the strategic level of an organization,
a data governance council’s responsibilities include approving guidelines,
coordinating business and data projects, and assessing budget requests for
data-related projects. In addition, significant roles are played by data
custodians and data stewards on the tactical level. The significant data
stakeholders from various categories (user groups) operate at the lowest
level. This model aids in comprehending what organisational layer data
governance duties should work on; but, it does not provide a way to set up
data governance.

Furthermore, the study [21] determines the condition, factors influencing, and
potential obstacles to data governance in Kenyan health professional
regulating entities. The primary focus of this paper is to construct a
framework which can be applicable to develop an official data governance
initiative at these healthcare governing bodies. This particular work
determined the quality of data maintenance, attaining customer satisfaction,
safeguarding security and control of the data, and reaching a state of
operational effectiveness as the driving force behind data governance in the
governing authorities. These bodies encounter challenges such as insufficient
knowledge of data governance, lack of management ownership and backing, and
constrained distribution of funds and resources, each functioning as a barrier
to efficient data administration. The scholarly article [15] suggested a
comprehensive layout for the governance of big data drawn from an analysis of
ten representative case studies of medical information exchange organizations
in China. The framework was condensed into the following three domains: drive
domain, capability domain and support domain. It also incorporates a total of
12 elements, such as massive data strategy formation, legal and regulatory
aspects, business actions practices, assistance, big medical data maintenance
authority, collection of data, preservation, process and analysis, usage,
resource utilization, quality management, and data protection safeguards that
pertain to each respective domain.

However, other studies [2, 8, 9, 11, 12, 17, 18] are also considered which are
not directly investigate the healthcare data governance activities, frameworks
or elements but highlight the needs and importance of data governance
frameworks or activities focusing on privacy and security perspective,
challenges and risks associated with data governance regarding big data,
involvement of IoT devices, data access controls or ownership, regulating
multiple data actors, data quality dimension in healthcare etc. These studies
provide the basic elements or activities that should be part of the healthcare
data governance frameworks

##  3 Healthcare Data Privacy & Security Framework

These studies provide comprehensive data governance
frameworks/elements/activities via which we categorised them into three
distinct pillars: (1) Data Governance Organization, (2) Data Communication,
and (3) Data Privacy and Security by Design, as shown in Figure 1. This
categorisation underscores healthcare data’s security and privacy concerns
throughout the chain, from records collection to sharing analysed results or
data. However, existing state-of-the-art healthcare data governance frameworks
treated privacy as an afterthought or an add-on feature, but instead as an
integral part of the entire design process.

Figure 1: Healthcare Data Protection Governance - A Conceptual Framework

###  3.1 Data Governance

Data governance is critical to a successful data governance program. It
provides a structured approach to managing data by defining policies, rules,
regulations, and procedures. The framework outlines the roles and
responsibilities of various stakeholders, including owners, stewards,
custodians, and users of data. Moreover, employees’ training and
accountability are also necessary and challenging components of the data
governance organization pillar in healthcare.

####  3.1.1 Policies, Standards, Regulations:

Fair Information Practice Principles (FIPPs)
222https://www.ftc.gov/sites/default/files/documents/reports/privacy-online-
report-congress/priv-23a.pdf are a set of principles that form the basis of
modern data protection laws and regulations. These principles were first
established by the United States in 1970s and have since been adopted by many
countries worldwide. The FIPPs provide a framework for gathering, utilizing,
and revealing individual information fairly and transparently. In healthcare,
the principles of FIPPs are reflected in various regulations and acts,
including the General Data Protection Regulation (GDPR) [14, 19] in the
European Union, in the United States, the Health Insurance Portability and
Accountability Act (HIPAA) [7], the Personal Information Protection and
Electronic Documents Act (PIPEDA) 333”Office of the Australian Information
Commissioner (OIAC)”, https://www.cdr.gov.au/ in Canada, etc. Additionally,
healthcare organizations must establish internal policies and regulations that
provide a framework for data privacy, security, consent management, and other
critical aspects of healthcare compliance.

####  3.1.2 Roles & Responsibilities:

Data governance requires collaboration and communication among various
stakeholders to ensure data is managed effectively, efficiently and securely.
The roles and responsibilities in data governance may differ according to the
size of the organization, structure, and industry. Data Governance
organisational structure describes typical roles: 1) the composition, charter,
and leadership of the Data Governance Committee; 2) the tasks of other
relevant Data Governance committees 3) positions in huge organisations; links
to other groups and entities and 4) top-level funding. In addition, the
structure demonstrates how the Data Governance process gives supervision to
owners of data, administrators, guardians, IT staff, compliance officers, and
users of data, who are typically involved in the data warehouse management.

####  3.1.3 Employees Training:

Healthcare workers are less tech-savvy and have less understanding of the
safety of data, and technologies related to healthcare lag well behind those
of the financial sector. Consequently, an understanding of data protection
concerns requires education and training. Staff training works well for
handling low-tech breaches of data. Keeping end-users informed about medical
provider policies and fundamental security precautions is a part of preserving
the privacy of data. Accidental interference can be prevented by teaching
staff members about security risks including tapping on email links, pressing
the computer desk login credentials, and visiting unapproved web pages.

####  3.1.4 Accountability:

Systems for evaluation and surveillance must be put in place by healthcare
businesses to make certain that staff members are abiding by the regulations
of the company. They create guidelines to prevent security lapses and specify
precisely how infractions will be handled. Healthcare data is ideal for the
identity thief. Being proactive and putting plans into action is essential.
Reactive actions, like playing catch-up after a security breach happens, are
not an effective approach.

###  3.2 Data Communication

Organizing or listing data elements with their description and other valuable
information (metadata) enables numerous insights into the core data or
business concepts and terminologies. Everyone implicated in the data
management cycle uses the same terms to discuss the same things, making
communication easy. Effective communication reduces operational friction and
minimises data misuse due to inaccurate understanding. We further categorise
this pillar into five components to keenly analyse the security and privacy
situation in the healthcare industry.

####  3.2.1 Data Warehouse Governance (DWG):

Data Warehouse Governance gives guidelines, rules and practices to guarantee
gain, utility, significance and risk management. Strategic choice-making and
monitoring should ideally be the main concern of data warehouse governance,
with secondary objectives including resource distribution, value of
investment, and minimizing risk. Nevertheless, DWG could be more concerned
regarding security and confidentiality, compliance, and risk prevention in
healthcare settings given the delicate nature of protected health information.

####  3.2.2 Data Analytic:

Since the end of the 1950s, interest in artificial intelligence (AI) has
cycled through periods of hope and disappointment due to unsatisfactory
performance of algorithms and computing infrastructure [20]. While, the
development of big data, machine learning, deep learning algorithms, and
suitable computing infrastructure has rekindled interest in artificial
intelligence (AI) technology and expedited its uptake across a number of
industries. Even though modern AI techniques like machine learning have just
recently been used in the healthcare industry, the prospects for better
healthcare outcomes are encouraging. [22]. Analyzing, or mining, the data
without disclosing personally identifying or delicate private data about
specific persons is known as privacy-preserving data analytics.

####  3.2.3 Data Access:

Institutions and people are both impacted by breaches of data and fraud. To
safeguard patients’ confidential information, the majority of healthcare
organizations have developed sophisticated security protocols. [10]. While,
software flaws, phishing, identities being stolen, and fraudulent attempts
allow cyber criminals to get access and capture private information, which can
lead to theft of identity, financial loss, anxiety, depression, prejudice,
humiliation, assault, and other issues. [5, 16]. Insider dangers, however, are
far more challenging to identify and stop than external ones. Insider threat
is any harm carried out by users with authorized access to an organization’s
network, apps, or data repositories. Therefore, strong security management
structures are needed to guard against unauthorized access to healthcare
information by outside parties and malevolent insider threats.

####  3.2.4 Data Quality:

Healthcare data quality is critical for delivering safe, efficient, and
effective patient care, driving medical research and innovation, informing
healthcare policies, facilitating quality improvement initiatives, ensuring
interoperability, and complying with legal and regulatory requirements.
Governing bodies should design a data quality management framework composed of
six key dimensions: accuracy, completeness, consistency, uniqueness,
timelessness and validity because privacy and security compliance can only be
achieved with accurate and consistent data.

###  3.3 Data Privacy & Security by Design

The third pillar of the proposed data governance framework focuses on data
fortification by design. Data Privacy and Security by Design (PSbD) is an
approach to developing systems, products, and services with a strong focus on
privacy and security. Integrating privacy and security considerations into any
system’s design, development, and implementation stages. After reviewing the
legal perspective through law articles, the privacy-by-design framework has
been defined. By doing so, medical data privacy risks can be minimized, and
individuals can have more control over their personal and sensitive data.

####  3.3.1 Privacy Enhancing Technologies:

Privacy-enhancing technologies (PETs) are tools, techniques, and systems
designed to protect and enhance privacy in the digital realm. They aim to
safeguard sensitive information, limit data collection and sharing, and give
individuals greater control over their data. PETs can be applied in various
contexts of the data life-cycle and help healthcare providers meet their legal
and ethical obligations regarding data protection.

####  3.3.2 Policy-Based Automated Compliance Checking:

Automated compliance checking involves leveraging technology, such as software
applications or platforms, to systematically evaluate the organization’s
activities, processes, and behaviour to comply with the established policies.
To identify deviations or violations, these automated systems can analyze
various data sources, including logs, records, and transactions. As
regulations and policies evolve, the systems can be updated with new rules and
requirements. This adaptability can enable healthcare providers to stay
compliant with the latest industry standards and regulations, even in a
rapidly changing healthcare landscape.

##  4 Conclusion

The proliferation of data has brought about profound changes across various
domains. Likewise, using cutting-edge technology for Electronic Medical
Records not only transforms illness treatment but also benefits insurance, law
enforcement, pharmaceutical, and other product-selling businesses. However,
the healthcare industry is still grappling with persistent concerns related to
data protection. It is noteworthy that mishandling healthcare data can lead to
significant liability, impacting patients and organisations. Healthcare
entities must adhere to a multitude of regulations to safeguard patient data.
After thoroughly examining the literature, we have determined that the
previously established cutting-edge healthcare data governance frameworks
often regarded privacy as a secondary consideration rather than an inherent
and essential component integrated into the design process. We have conducted
an in-depth review of existing studies and proposed a conceptual healthcare
data governance framework with a primary focus on data privacy and security.

## References

  * [1] Abraham, R., Schneider, J., Vom Brocke, J.: Data governance: A conceptual framework, structured review, and research agenda. International journal of information management 49, 424–438 (2019)
  * [2] Al-Badi, A., Tarhini, A., Khan, A.I.: Exploring big data governance frameworks. Procedia computer science 141, 271–277 (2018)
  * [3] Alhassan, I., Sammon, D., Daly, M.: Data governance activities: A comparison between scientific and practice-oriented literature. Journal of enterprise information management 31(2), 300–316 (2018)
  * [4] Aspden, P., Corrigan, J.M., Wolcott, J., Erickson, S.M., et al.: Key capabilities of an electronic health record system: Letter report. In: Patient Safety: Achieving a New Standard for Care. National Academies Press (US) (2004)
  * [5] Chabot, Y., Bertaux, A., Nicolle, C., Kechadi, T.: An ontology-based approach for the reconstruction and analysis of digital incidents timelines. Digital Investigation 15, 83–100 (2015)
  * [6] Cheong, L.K., Chang, V.: The need for data governance: a case study. ACIS 2007 proceedings p. 100 (2007)
  * [7] Office for Civil Rights, H.: Standards for privacy of individually identifiable health information. final rule. Federal register 67(157), 53181–53273 (2002)
  * [8] Dasgupta, A., Gill, A., Hussain, F.: A conceptual framework for data governance in iot-enabled digital is ecosystems. In: 8th International Conference on Data Science, Technology and Applications. SCITEPRESS–Science and Technology Publications (2019)
  * [9] Fleissner, B., Jasti, K., Ales, J., Thomas, R.: The importance of data governance in healthcare.: 1–11. October.[White Paper] (2014)
  * [10] Greenaway, K.E., Chan, Y.E., Crossler, R.E.: Company information privacy orientation: A conceptual framework. Information Systems Journal 25(6), 579–606 (2015)
  * [11] Juddoo, S., George, C., Duquenoy, P., Windridge, D.: Data governance in the health industry: Investigating data quality dimensions within a big data context. Applied System Innovation 1(4), 43 (2018)
  * [12] Kariotis, T., Ball, M.P., Tzovaras, B.G., Dennis, S., Sahama, T., Johnston, C., Almond, H., Borda, A.: Emerging health data platforms: From individual control to collective data governance. Data & Policy 2, e13 (2020)
  * [13] Khatri, V., Brown, C.V.: Designing data governance. Communications of the ACM 53(1), 148–152 (2010)
  * [14] Lea, N.C.: How will the general data protection regulation affect healthcare? Acta medica portuguesa 31(7-8), 363–365 (2018)
  * [15] Li, Q., Lan, L., Zeng, N., You, L., Yin, J., Zhou, X., Meng, Q.: A framework for big data governance to advance rhins: a case study of china. IEEE Access 7, 50330–50338 (2019)
  * [16] Van der Meulen, N.: The challenge of countering identity theft: Recent developments in the united states, the united kingdom, and the european union. Report Commissioned by the National Infrastructure Cyber Crime program (NICC). Retrieved May 20, 2007 (2006)
  * [17] Paparova, D., Aanestad, M., Vassilakopoulou, P., Bahus, M.K.: Data governance spaces: The case of a national digital service for personal health data. Information and Organization 33(1), 100451 (2023)
  * [18] Perez-Pozuelo, I., Spathis, D., Gifford-Moore, J., Morley, J., Cowls, J.: Digital phenotyping and sensitive health data: Implications for data governance. Journal of the American Medical Informatics Association 28(9), 2002–2008 (2021)
  * [19] Regulation, G.D.P.: General data protection regulation (gdpr). Intersoft Consulting, Accessed in October 24(1) (2018)
  * [20] Salathé, M., Wiegand, T., Wenzel, M.: Focus group on artificial intelligence for health. arXiv preprint arXiv:1809.04797 (2018)
  * [21] Were, V., Moturi, C.: Toward a data governance model for the kenya health professional regulatory authorities. The TQM Journal 29(4), 579–589 (2017)
  * [22] Whittlestone, J., Nyrup, R., Alexandrova, A., Dihal, K., Cave, S.: Ethical and societal implications of algorithms, data, and artificial intelligence: a roadmap for research. London: Nuffield Foundation (2019)
  * [23] Winter, J.S., Davidson, E.: Investigating values in personal health data governance models. 23rd Americas Conference on Information Systems (AMCIS) (2017)
  * [24] Winter, J.S., Davidson, E.: Big data governance of personal health information and challenges to contextual integrity. The Information Society 35(1), 36–51 (2019)