Multi-machine distributed learning systems
A system comprises a network of computers comprising a master computer and slave computers. For a machine learning problem that is partitioned into a number of correlated sub-problems, each master computer is configured to store tasks associated with the machine learning problem, and each of the slave computers is assigned one of the correlated sub-problems. Each slave computer is configured to store variables or parameters or both associated with the assigned one of the correlated sub-problems; obtain information about one or more tasks stored by the master computer without causing conflict with other slave computers with regard to the information; perform computations to update the obtained information and the variables or parameters or both of the assigned sub-problem; send the updated information to the master computer to update the information stored at the master computer; and store the updated variables or parameters or both of the assigned sub-problem.
1. A system comprising:
a network of computers comprising
a master computer, and
two or more slave computers,
wherein for a machine learning problem that is partitioned into a number of correlated NP hard non-convex optimization sub-problems, the machine learning problem comprising determining a solution to an objective function problem
min
A
,
B
F
(
A
,
B
)
=
∑
i
,
j
∈
I
(
x
ij
-
A
i
B
j
)
2
+
∑
i
λ
A
i
2
+
∑
i
λ
B
j
2
for completing an incomplete data matrix X having N×D dimensions, where X is approximated by a product of matrices A and B, and where A i represents a sub-matrix of the matrix A that has the same number of columns as the matrix A, and B j represents a sub-matrix of the matrix B that has the same number or rows as the matrix B, the master computer being configured to store tasks associated with the machine learning problem, and each of the slave computers being assigned one of the NP hard non-convex optimization sub-problems and being configured to:
store variables or parameters or both associated with the assigned NP hard non-convex optimization sub-problem;
query information about one or more tasks stored by the master computer without causing conflict with other slave computers with regard to the information; and
solve the assigned NP hard non-convex optimization sub-problem, comprising performing computations to update i) the queried information about the one or more tasks, and ii) the variables or parameters or both of the assigned NP hard non-convex optimization sub-problem, wherein performing the computations comprises updating Ai and Bj in iterations by a slave computer based on the following equation:
(
A
i
t
,
B
j
t
)
=
arg
min
A
i
,
B
j
{
(
x
ij
-
A
i
B
j
)
2
+
λ
t
A
i
-
A
i
t
-
1
2
+
λ
t
B
j
-
B
j
t
-
1
2
}
where λ t is a sequence of step sizes, and t is current number of iterations.
2. The system of claim 1 , wherein performing computations to update i) the queried information about the one or more tasks, and ii) the variables or parameters or both of the assigned NP hard non-convex optimization sub-problem comprises performing computations that are computationally harder than stochastic gradient descent.
3. The system of claim 1 , wherein the two or more slave computers are configured to asynchronously:
store variables or parameters or both associated with the assigned NP hard non-convex optimization sub-problem;
query information about one or more tasks stored by the master computer without causing conflict with other slave computers with regard to the information; and
perform computations to update i) the queried information about the one or more tasks, and ii) the variables or parameters or both of the assigned NP hard non-convex optimization sub-problem.
4. The system of claim 1 , wherein the slave computer includes a quantum processor, and A i t-1 , B i t-1 , and λ t are input into the quantum processor and A i t and B i t are output from the quantum processor.
5. The system of claim 1 , wherein:
workers operate on respective slave computers,
a submitter operates on one of the slave computers, wherein the submitter is configured to update and maintain a summary task containing a summary of tasks carried out by the workers, and
the workers and the submitter work together without using mutex locks, and wherein at any given time, information stored or to be stored in the master computer is not updated or written simultaneously by more than one of the workers and the submitter.
6. A system comprising:
a network of computers comprising
a master computer, and
two or more slave computers,
wherein for a machine learning problem that is partitioned into a number of correlated NP hard non-convex optimization sub-problems, the machine learning problem comprising determining a minimum of an objective function
R
(
w
)
=
∑
i
=
1
n
L
(
〈
y
i
x
i
,
w
〉
)
=
∑
i
=
1
n
L
(
∑
j
=
1
d
y
i
x
ij
w
j
)
for binary classification problem that has a data set
X
=
(
x
1
1
x
1
2
…
x
1
D
x
2
1
x
2
2
…
x
2
D
∶
∶
…
∶
x
N
1
x
N
2
…
x
ND
)
=
(
x
1
x
2
∶
x
N
)
,
with labels y={y 1 , . . . , y n }∈{+1, −1} n and parameter w=(w 1 w 2 . . . w D ) T , the master computer being configured to store tasks associated with the machine learning problem, and each of the slave computers being assigned one of the NP hard non-convex optimization sub-problems and being configured to:
store variables or parameters or both associated with the assigned NP hard non-convex optimization sub-problem;
query information about one or more tasks stored by the master computer without causing conflict with other slave computers with regard to the information; and
solve the assigned NP hard non-convex optimization sub-problem, comprising performing computations to update i) the queried information about the one or more tasks, and ii) the variables or parameters or both of the assigned NP hard non-convex optimization sub-problem, wherein performing computations to update i) the queried information about the one or more tasks, and ii) the variables or parameters or both of the assigned NP hard non-convex optimization sub-problem comprises updating a sub-group of parameters w sp in iterations by a slave computer according to the following equation:
w
S
p
t
=
arg
min
w
S
p
{
∑
i
∈
I
p
L
(
∑
j
∈
S
p
y
i
x
ij
w
j
+
∑
j
∉
S
p
y
i
x
ij
w
j
t
-
1
)
+
λ
t
w
S
p
-
w
S
p
t
-
1
2
}
.
where S p is a sub-group of 1, . . . , D, t is a current iteration, and L is a loss function of the binary classification.
7. The system of claim 6 , wherein the slave computer includes a quantum processor.
8. A computer implemented method comprising:
for a machine learning problem that is partitioned into a number of correlated NP hard non-convex optimization sub-problems, wherein the machine learning problem comprises determining a solution to an objective function problem
min
A
,
B
F
(
A
,
B
)
=
∑
i
,
j
∈
I
(
x
ij
-
A
i
B
j
)
2
+
∑
i
λ
A
i
2
+
∑
i
λ
B
j
2
for completing an incomplete data matrix X having N×D dimensions, where X is approximated by a product of matrices A and B, and where A i represents a sub-matrix of the matrix A that has the same number of columns as the matrix A, and B j represents a sub-matrix of the matrix B that has the same number or rows as the matrix B:
storing, by a master computer, tasks associated with the machine learning problem; and
for each of multiple slave computers being assigned a respective NP hard non-convex optimization sub-problem of the correlated NP hard non-convex optimization sub-problems;
storing variables or parameters or both associated with the assigned NP hard non-convex optimization sub-problem;
querying information about one or more tasks stored by the master computer without causing conflict with other slave computers with regard to the information; and solving the assigned NP hard non-convex optimization sub-problem, comprising performing computations to update i) the queried information about the one or more tasks, and ii) the variables or parameters or both of the assigned NP hard non-convex optimization sub-problem, wherein performing the computations comprises updating A i and B j in iterations by a slave computer based on the following equation:
(
A
i
t
,
B
j
t
)
=
arg
min
A
i
,
B
j
{
(
x
ij
-
A
i
B
j
)
2
+
λ
t
A
i
-
A
i
t
-
1
2
+
λ
t
B
j
-
B
j
t
-
1
2
}
where λ t is a sequence of step sizes, and t is a current number of iterations.
9. The method of claim 8 , wherein performing computations to update i) the queried information about the one or more tasks, and ii) the variables or parameters or both of the assigned NP hard non-convex optimization sub-problem comprises performing computations that are computationally harder than stochastic gradient descent.
10. The method of claim 8 , wherein
storing variables or parameters or both associated with the assigned non-convex optimization NP hard sub-problem,
querying information about one or more tasks stored by the master computer without causing conflict with other slave computers with regard to the information, and
performing computations to update i) the queried information about the one or more tasks, and ii) the variables or parameters or both of the assigned NP hard non-convex optimization sub-problem,
are performed asynchronously.
11. The method of claim 8 , wherein the slave computer includes a quantum processor, and A i t-1 , B i t-1 , and λ t are input into the quantum processor and A i t and B i t are output from the quantum processor.
12. A computer implemented method comprising:
for a machine learning problem that is partitioned into a number of correlated NP hard non-convex optimization sub-problems, wherein the machine learning problem comprises determining a minimum of an objective function
R
(
w
)
=
∑
i
=
1
n
L
(
〈
y
i
x
i
,
w
〉
)
=
∑
i
=
1
n
L
(
∑
j
=
1
d
y
i
x
ij
w
j
)
for binary classification problem that has a data set
X
=
(
x
1
1
x
1
2
…
x
1
D
x
2
1
x
2
2
…
x
2
D
∶
∶
…
∶
x
N
1
x
N
2
…
x
ND
)
=
(
x
1
x
2
∶
x
N
)
,
labels y={y 1 , . . . , y n }∈{+1, −1} n and parameter w=(w 1 w 2 . . . w D ) T ;
storing, by a master computer, tasks associated with the machine learning problem; and
for each of multiple slave computers being assigned a respective NP hard non-convex optimization sub-problem of the correlated NP hard non-convex optimization sub-problems;
storing variables or parameters or both associated with the assigned NP hard non-convex optimization sub-problem;
querying information about one or more tasks stored by the master computer without causing conflict with other slave computers with regard to the information; and solving the assigned NP hard non-convex optimization sub-problem, comprising performing computations to update i) the queried information about the one or more tasks, and ii) the variables or parameters or both of the assigned NP hard non-convex optimization sub-problem, wherein performing computations to update i) the queried information about the one or more tasks, and ii) the variables or parameters or both of the assigned correlated NP hard sub-problem comprises updating a sub-group of parameters w sp in iterations by a slave computer according to the following equation:
w
S
p
t
=
arg
min
w
S
p
{
∑
i
∈
I
p
L
(
∑
j
∈
S
p
y
i
x
ij
w
j
+
∑
j
∉
S
p
y
i
x
ij
w
j
t
-
1
)
+
λ
t
w
S
p
-
w
S
p
t
-
1
2
}
.
where S p is a sub-group of 1, . . . , D, t is a current iteration, and L is a loss function of the binary classification.
13. The method of claim 12 , wherein the slave computer includes a quantum processor.