Method and device for preserving privacy of linear regression distributed learning
The present disclosure relates to a method and device for preserving privacy of linear regression distributed learning, in particular for preserving privacy of linear regression distributed learning using a LASSO (least absolute shrinkage and selection operator)—VAR (vector autoregressive) model, further in particular for preserving privacy of distributed learning using a LASSO-VAR model using convex optimization like alternating direction method of multipliers (ADMM) or using coordinate descent optimization. It is disclosed a device and method for preserving privacy of a linear regression model used in distributed learning by a set of agents indirectly sharing covariate data or target data when sharing coefficient matrixes for said model, comprising obtaining a perturbation matrix for encrypting the data being shared.
1 . A computer implemented method for preserving privacy of a linear regression model used in distributed learning by a set of agents, said set of agents being a plurality of computer processors communicatively coupled and sharing covariate data and/or target data for said model, each computer processor of the plurality of computer processors comprising a memory storing instructions that, when executed, cause the computer processor to perform the method, the method comprising obtaining an invertible random perturbation matrix, as an algebraic encryption key given by multiplication of a plurality of invertible randomly generated perturbation sub-matrixes, there being a perturbation sub-matrix for each respective agent,
wherein the invertible random perturbation matrix is to be used as an algebraic encryption key by left-multiplication of the data to be encrypted,
wherein an invertible perturbation sub-matrix is privately and randomly generated by each individual agent;
the method comprising the steps of:
for each individual agent, the individual agent privately generating a first random invertible matrix and a second random invertible matrix, multiplying a horizontally concatenated matrix of covariate and/or target data to be encrypted by said individual agent and said first matrix, with the second matrix, to obtain a resulting multiplication and sharing the resulting multiplication with a receiving agent selected from one of the remaining agents;
the receiving agent receiving the shared resulting multiplication, and multiplying the perturbation sub-matrix of the receiving agent by the received multiplication to obtain a following resulting multiplication, and sharing the following resulting multiplication with another receiving agent selected from one of the remaining agents, repeating until a last remaining agent receives a resulting penultimate multiplication, and then the last remaining agent multiplying the perturbation sub-matrix of the last remaining agent by the received resulting penultimate multiplication to obtain a resulting last multiplication, and sharing the resulting last multiplication back with the individual agent;
for each individual agent, the individual agent recovering the encrypted data of said individual agent by computing the multiplication of the shared resulting last multiplication with the individual agent with the inverse of the second matrix, horizontally decatenating from the computed multiplication a left-side matrix and a right-side matrix, wherein the right-side matrix is the encrypted data of said individual agent as encrypted by the perturbation matrix; and
for each individual agent, the individual agent sharing the encrypted data of said individual agent with all other agents, receiving the encrypted data of all other agents, and fitting said model to the received encrypted data of all other agents to solve a learning problem in a distributed manner.
2 . The computer implemented method according to claim 1 , used in distributed learning by a set of n agents, said set of n agents being said plurality of computer processors communicatively coupled, sharing covariate data and/or target data for said model, each said computer processor comprising a memory storing instructions, that when executed, cause computer processor to perform matrix operations, the method further comprising obtaining, by execution of said instructions on the computer processors, an invertible random perturbation matrix M, as an algebraic encryption key, being M∈ T×T ,
given by multiplication of invertible sub-matrixes M A i ∈ T×T privately generated randomly by i-th agent given by:
M
=
M
A
1
…
M
A
n
′
(
11
)
such that MX is given by:
MX
=
[
M
A
1
…
M
A
n
X
A
1
︸
=
MX
A
1
,
…
,
M
A
1
…
M
A
n
X
A
n
︸
]
=
MX
A
n
,
(
12
)
where A i denotes the i-th agent, i=1, . . . , n, and n is the total number of agents, T is the number of observations, X∈ T×ns is the data to be encrypted of all agents, X=[X A 1 , . . . , X A n ], X A i ∈ T×s is the data to be encrypted of each i-th agent, s is the number of covariates observed from each agent, and wherein invertible matrix M A i is privately and randomly generated by each i-th agent by the execution of instructions on the computer processor,
comprising the steps of:
agent i-th, said i-th computer processor privately generating random invertible matrices C A i and D A i , being C A i ∈ T×(r−s) , D A i ∈ r×r , and sharing W A i ∈ T×r with a n-th agent, where W A i is obtained by:
W
A
i
=
[
X
A
i
,
C
A
i
]
D
A
i
(
13
)
the n-th agent receiving W A i and sharing M A n W A i with a (n−1)-th agent, which then receives M A n W A i and shares M A n−1 M A n W A i with a (n−2)-th agent; and repeating until a 1-st agent receives M A 2 . . . M A n W A i and computes MW A i =M A 1 M A 2 . . . M A n W A i ;
the 1-st agent sends MW A i to agent i-th;
agent i-th recovers MX A i from:
[
MC
A
i
,
MX
A
i
]
=
MW
A
i
D
A
i
-
1
(
14
)
wherein
D
A
i
-
1
is the matrix inverse of D A i ,
and subsequently each agent sending the recovered MX A i as the encrypted data to be transmitted to the other agents.
3 . The computer implemented method according to claim 2 , further comprising, for encrypting M −1 , wherein M −1 is the inverse of the perturbation matrix M, comprising encrypting
X
A
i
⊤
M
-
1
,
with
X
A
i
⊤
being the transpose of the matrix X A i and
M
-
1
=
M
A
n
-
1
M
A
n
-
1
-
1
…
M
A
1
-
1
being the inverse of the perturbation matrix M, the matrix W A i is transposed in
W
A
i
T
and wherein said method steps are carried out and further include:
the n-th agent receiving
W
A
i
T
and sharing
W
A
i
T
M
A
n
-
1
with a (n−1)-th agent, which then receives
W
A
i
T
M
A
n
-
1
and shares
W
A
i
T
M
A
n
-
1
M
A
n
-
1
-
1
with a (n−2)-th agent; and
repeating until a 1-st agent receives
W
A
i
T
M
A
n
-
1
M
A
n
-
1
-
1
…
M
A
2
-
1
and computes
W
A
i
T
M
-
1
=
W
A
i
T
M
A
n
-
1
M
A
n
-
1
-
1
…
M
A
1
-
1
;
the 1-st agent sending
W
A
i
T
M
-
1
to agent i-th;
agent i-th recovering
X
A
i
T
M
-
1
from:
[
X
A
i
T
M
-
1
,
C
A
i
T
M
-
1
]
=
(
D
A
i
T
)
-
1
W
A
i
T
M
-
1
wherein
(
D
A
i
T
)
-
1
is the matrix inverse of
D
A
i
T
,
and subsequently each agent sending the recovered
X
A
i
T
M
-
1
as the encrypted data to be transmitted to the other agents.
4 . The computer implemented method according to claim 2 , further comprising, by execution of instructions stored in memory of the plurality of computer processors, obtaining a perturbation matrix Q, defined as an algebraic encryption key in the form of a diagonal matrix of size ns×ns , formed by diagonal matrices Q A i ∈ s×s , which are random matrices privately generated by each agent i, for post-multiplying the data to be encrypted X=[X A 1 , . . . , X A n ], where X A i ∈ T×s is the data to be encrypted of each i-th agent, such that XQ is given by:
[
X
A
1
,
…
,
X
A
n
]
︸
=
X
[
Q
A
1
0
⋱
0
Q
A
n
]
︸
=
Q
=
[
X
A
1
Q
A
1
,
…
,
X
A
n
Q
A
n
]
.
(
10
)
the method comprising the steps of:
each i-th agent generating random matrix Q A i ,
and sharing X A i Q A i with every other agent.
5 . The computer implemented method according to claim 2 , wherein privacy of linear regression distributed learning is by using a least absolute shrinkage and selection operator vector autoregressive, LASSO-VAR, model.
6 . The computer implemented method according to claim 5 , wherein the least absolute shrinkage and selection operator-vector autoregressive, LASSO-VAR, model uses convex optimization.
7 . The computer implemented method according to claim 6 , further comprising Z and Y which are data to be encrypted and transmitted by each agent, said each agent being a computer processor comprising a memory storing instructions, wherein Z=[Z A 1 , . . . , Z A n ] is a covariate matrix and Y=[Y A 1 , . . . , Y A n ] is a target matrix, where covariate matrix Z is split by model features, comprising each of said agents computing MZ A i , MY A i and
Z
A
i
⊤
M
-
1
for obtaining the encrypted data to be transmitted to the other agents.
8 . The computer implemented method according to claim 4 , further comprising ZQ which is a covariate matrix and further comprising Y that is a target matrix, where Z=[Z A 1 , . . . , Z A n ] and Y=[Y A 1 , . . . , Y A n ] are data to be encrypted and transmitted, where covariate matrix ZQ is split by model features, comprising each of said agents being a plurality of computer processors comprising a memory storing instructions that, when executed, cause the processors to compute MZ A i Q A i , MY A i and
Q
A
i
⊤
Z
A
i
⊤
M
-
1
for obtaining the encrypted data to be transmitted to the other agents.
9 . The computer implemented method according to claim 8 , wherein, given the product Z A i Q A i ∈ T×s , said product has u unique values to recover and Y A i ∈ T×g has v unique unknown values that are not in Z A i , comprising the steps of executing each agent, said agent being a computer processor comprising a memory storing instructions that, when executed, causing the processor to compute MZ A i Q A i and
Q
A
i
⊤
Z
A
i
⊤
M
-
1
using the smaller integer r,
which is chosen according to the number of unique values on X A i and represents the size of the new variable space, such that
T
s
-
u
<
r
<
T
/
2
∧
r
>
p
,
p being a number of lags for the vector autoregressive, VAR, model,
and to compute MY A i using the smaller integer r′,
where r′ is chosen such that
-
u
+
T
s
-
r
2
-
v
+
T
g
<
r
′
<
T
-
2
r
∧
r
′
>
g
,
wherein T and g are matrix dimensions of Y A i .
10 . The computer implemented method according to claim 7 , for obtaining a non-encrypted least absolute shrinkage and selection operator-vector autoregressive, (LASSO-VAR), model, further comprising executing each agent, said each agent being a computer processor comprising a memory storing instructions that, when executed, carrying out the steps of:
obtaining said least absolute shrinkage and selection operator-vector autoregressive, LASSO-VAR, model, by execution of instructions on the computer processor, where coefficient matrix B (l) ∈ n×n which represents a coefficient matrix at lag l=1, . . . , p wherein variable B, comprising the concatenation of coefficients for all p lags where B∈ pn×n , is replaced by auxiliary variable H in a least absolute shrinkage and selection operator, LASSO, regularization term, with the added the constraint H=B to obtain model iterative coefficients B k+1 ,
wherein said instructions configure the processor to compute, through variables Z, k, ρ, U, H, I, λ, S λ/ρ , wherein U is the scaled dual variable associated with the constraint H=B, I is an identity matrix with proper dimension, k is an iteration of the optimization method, S λ/ρ is the soft thresholding operator, λ is a scalar parameter, by iterating:
B
k
+
1
=
(
Z
T
Z
+
ρ
I
)
-
1
(
Z
T
Y
+
ρ
(
H
¯
k
-
U
k
)
)
(
6
a
)
H
¯
k
+
1
=
S
λ
/
ρ
(
B
k
+
1
+
U
k
)
(
6
b
)
U
k
+
1
=
U
k
+
B
k
+
1
-
H
¯
k
+
1
(
6
c
)
11 . The computer implemented method according to claim 10 , further comprising executing each agent, said each agent being a computer processor comprising a memory storing instructions that, when executed, cause the processor to compute B A i in parallel as
B
A
i
k
+
1
which is obtained by:
B
A
i
k
+
1
=
arg
min
B
(
Z
A
i
B
A
i
k
+
H
_
k
-
ZB
_
k
-
U
k
-
Z
A
i
B
A
i
2
2
+
λ
B
A
i
1
)
,
(
8
a
)
H
_
k
+
1
=
1
N
+
ρ
(
Y
+
ρ
ZB
_
k
+
1
+
U
k
)
(
8
b
)
U
k
+
1
=
U
k
+
ZB
_
k
+
1
-
H
_
k
+
1
,
(
8
c
)
wherein ZB k is defined as the average
1
n
∑
j
=
1
n
Z
A
j
B
A
j
k
,
ZB
_
k
+
1
=
1
n
∑
j
=
1
n
Z
A
j
B
A
j
k
+
1
,
and
B
A
i
k
+
1
∈
ℝ
p
×
n
,
Z
A
i
∈
ℝ
T
×
p
,
Y
,
H
_
,
U
∈
ℝ
T
×
n
,
i
=
1
,
…
,
n
and B A i is estimated through an alternating direction method of multipliers, (ADMM), by
arg
min
B
(
Y
^
A
i
–
Σ
i
Z
A
i
B
A
i
2
2
+
λ
^
Σ
i
H
A
i
1
)
,
(
9
)
where
Y
¯
A
i
=
Z
A
i
B
A
i
k
+
H
¯
k
-
ZB
_
k
-
U
k
and
λ
ˆ
=
λ
/
ρ
,
wherein B A i is the non-encrypted solution to the least absolute shrinkage and selection operator-vector autoregressive, LASSO-VAR, model.
12 . The computer implemented method according to claim 11 , further comprising executing each agent, said each agent being a computer processor comprising a memory storing instructions that, when executed, cause the processor to obtain the alternating direction method of multipliers, ADMM, solution for the optimization problem:
argmin
B
′
(
1
2
MY
-
Σ
i
MZ
A
i
Q
A
i
B
A
i
′
2
2
+
λΣ
i
Q
A
i
B
A
i
′
1
)
(
17
)
where
B
A
i
′
=
Q
A
i
B
A
i
is the encrypted solution to the least absolute shrinkage and selection operator-vector autoregressive, LASSO-VAR, model.
13 . The computer implemented method according to claim 1 , wherein said linear regression model is for forecasting wind or solar power.
14 . A non-transitory storage media comprising computer program instructions for implementing a computer implemented method for preserving privacy of a linear regression model used in distributed learning by a set of agents, said set of agents being a plurality of computer processors communicatively coupled and sharing covariate data and/or target data for said model, each computer processor of the plurality of computer processors comprising a memory storing instructions that, when executed, cause the computer processor to perform the method, the method comprising obtaining an invertible random perturbation matrix, as an algebraic encryption key given by multiplication of a plurality of invertible randomly generated perturbation sub-matrixes, there being a perturbation sub-matrix for each respective agent,
wherein the invertible random perturbation matrix is to be used as an algebraic encryption key by left-multiplication of the data to be encrypted,
wherein an invertible perturbation sub-matrix is privately and randomly generated by each individual agent;
the method comprising the steps of:
for each individual agent, the individual agent privately generating a first random invertible matrix and a second random invertible matrix, multiplying a horizontally concatenated matrix of covariate and/or target data to be encrypted by said individual agent and said first matrix, with the second matrix, to obtain a resulting multiplication and sharing the resulting multiplication with a receiving agent selected from one of the remaining agents;
the receiving agent receiving the shared resulting multiplication, and multiplying the perturbation sub-matrix of the receiving agent by the received multiplication to obtain a following resulting multiplication, and sharing the following resulting multiplication with another receiving agent selected from one of the remaining agents, repeating until a last remaining agent receives a resulting penultimate multiplication, and then the last remaining agent multiplying the perturbation sub-matrix of the last remaining agent by the received resulting penultimate multiplication to obtain a resulting last multiplication, and sharing the resulting last multiplication back with the individual agent;
for each individual agent, the individual agent recovering the encrypted data of said individual agent by computing the multiplication of the shared resulting last multiplication with the individual agent with the inverse of the second matrix, horizontally decatenating from the computed multiplication a left-side matrix and a right-side matrix, wherein the right-side matrix is the encrypted data of said individual agent as encrypted by the perturbation matrix; and
for each individual agent, the individual agent sharing the encrypted data of said individual agent with all other agents, receiving the encrypted data of all other agents, and fitting said model to the received encrypted data of all other agents to solve a learning problem in a distributed manner.