IEEE Signal Processing - July 2018 - 24
summarized in Theorem 5, which abstracts out the key results in
the previously cited work.
f (x) = ixxT - 11Ti2
F
6
Theorem 5 (optimizing strict saddle functions)
4
2
0
1
x2 0
-1
-1
0
1
x1
Figure 3. An example of a two-dimensional strict saddle function
Assume that g : R N " R is b-smooth and (e, c, g) -strict saddle. There exist algorithms (such as PGD in Algorithm 3 with
appropriate choices of the parameters) that output a solution that
is g-close to a local minimum of g, with the required number
of iterations upper bounded by a polynomial function of
N, b, 1/e, c and 1/g.
Specializing to the low-rank matrix estimation problem, it
remains to verify that 1) the loss function defined on (L, R) is
strict saddle and 2) all its local minima are "good," in the sense
that they correspond to a low-rank matrix equal to (in the noisy
case, close to) the true matrix X. To this end, we consider the
same loss function as before for matrix sensing:
g A (L, R) = fA (L, R),
2
g (x ) = xx T - 11 T F , where x = [x 1, x 2] T and 1 = [1, 1] T . This function
has two local minima, x * = [1, 1] T and x * = [- 1, - 1] T , and a strict
saddle point x saddle = [0, 0] T . The Hessian d 2 g (x saddle) at the saddle point
T
has a strictly negative eigenvalue with the eigenvector 8 12 , 12 B , which
corresponds to the descent direction x * - x saddle.
where fA is defined in (22). For matrix completion, we consider
a regularized loss function:
g X (U, V ) = fX (L, R) + mQ a (L, R),
Algorithm 3. The PGD for escaping saddle points [75].
where fX is given in (23), the regularizer is given by [50]
Input: algorithm parameters d thres, t thres, g thers, h, R;
Q a (L, R) =
Initialization: Let x 0 = 0;
e Ti L
i=1
for t = 0, 1, 2, f do
1) if dg (x t ) 2 # d thres and t - t last 2 t thres then x last = x t , t last = t ;
x t = x last + p, where p is sampled uniformly from the unit ball centered at zero with radius R;
2) if t - t last = t thres and g (x t ) - g (x last) 2 - g thres then return x last;
3) x t + 1 = x t - hdg (x t ).
direction will make progress in decreasing the value of g (x)
and eventually converge to a local minimum. Many algorithms
have been shown to enjoy this property, include cubic regularization [72], trust-region algorithms [73], stochastic gradient descent [74], and other more recent variants [75]-[77]. In
Algorithm 3, we describe one such algorithm-the perturbed
gradient descent (PGD) algorithm from [75]. PGD is based
on the standard gradient descent algorithm with the following
additional steps:
■ when the gradient is small, indicating potential closeness to a
saddle point, PGD adds a random perturbation to the current
iterate (which is done at most once every t thres iterations)
■ if the last perturbation occurs t thres iterations ago and the
function value does not decrease sufficiently since, then PGD
terminates and outputs the iterate before the last perturbation.
We do not delve further into the details of these saddleescaping algorithms, as their parameter choices and run-time
guarantees are somewhat technical. Rather, for the purpose of
analyzing low-rank matrix estimation problems, we simply rely
on the existence of such algorithms and the fact that their running
time depends polynomially on the problem parameters. This is
24
n1
/`
- a j+ +
4
2
n2
/`
j=1
e Tj R
- a j+,
4
2
a and m are regularization parameters, and (x) + = max {x, 0}.
The regularization plays a similar role as the projections
PL, PR previously used: it encourages incoherence of L and
R. Replacing projections with regularization leads to an unconstrained formulation that fits into the strict-saddle framework
above. The following theorems, from [54], [55], and [70], show
that these loss functions indeed have the desired strict-saddle
property with high probability under sample complexity conditions similar to before.
Theorem 6 (matrix sensing)
Suppose that the measurement operator A satisfies RIP- , 2 /, 2
with parameter d 2r = max {d 2r, dr r} = 1/20. For any e 2 0, the
above loss function g A satisfies the following: 1) it is
^e, X (v r), O ^ ver hh- strict saddle, and 2) all its local minima satisfying LR T = X.
Theorem 7 (matrix completion)
Suppose that the observation probability satisfies
p $ X `^ n 4 r 6 log (n 1 + n 2)h (n 1 + n 2) j, and one chooses
2
a = H ^ nrv 1 (n 1 + n 2) h and m = H ^ (n 1 + n 2) nr h. Then,
with probability at least 1 - (n 1 + n 2) -1, the above loss function
g X satisfies the following: 1) it is ^e, X (v r), O ^e v r hh-strict
saddle for any e # poly ` n 4 r 4 v 41 (n 1 + n 2) 2 j, and 2) all its
local minima satisfy LR T = X.
Combining Theorem 5 with Theorems 6 and 7, we conclude
that iterative algorithms optimizing over the factor variables
(L, R) converge globally to some pair satisfying LR T = X in
a polynomially number of iterations from any arbitrary initial
IEEE Signal Processing Magazine
|
July 2018
|
Table of Contents for the Digital Edition of IEEE Signal Processing - July 2018
Contents
IEEE Signal Processing - July 2018 - Cover1
IEEE Signal Processing - July 2018 - Cover2
IEEE Signal Processing - July 2018 - Contents
IEEE Signal Processing - July 2018 - 2
IEEE Signal Processing - July 2018 - 3
IEEE Signal Processing - July 2018 - 4
IEEE Signal Processing - July 2018 - 5
IEEE Signal Processing - July 2018 - 6
IEEE Signal Processing - July 2018 - 7
IEEE Signal Processing - July 2018 - 8
IEEE Signal Processing - July 2018 - 9
IEEE Signal Processing - July 2018 - 10
IEEE Signal Processing - July 2018 - 11
IEEE Signal Processing - July 2018 - 12
IEEE Signal Processing - July 2018 - 13
IEEE Signal Processing - July 2018 - 14
IEEE Signal Processing - July 2018 - 15
IEEE Signal Processing - July 2018 - 16
IEEE Signal Processing - July 2018 - 17
IEEE Signal Processing - July 2018 - 18
IEEE Signal Processing - July 2018 - 19
IEEE Signal Processing - July 2018 - 20
IEEE Signal Processing - July 2018 - 21
IEEE Signal Processing - July 2018 - 22
IEEE Signal Processing - July 2018 - 23
IEEE Signal Processing - July 2018 - 24
IEEE Signal Processing - July 2018 - 25
IEEE Signal Processing - July 2018 - 26
IEEE Signal Processing - July 2018 - 27
IEEE Signal Processing - July 2018 - 28
IEEE Signal Processing - July 2018 - 29
IEEE Signal Processing - July 2018 - 30
IEEE Signal Processing - July 2018 - 31
IEEE Signal Processing - July 2018 - 32
IEEE Signal Processing - July 2018 - 33
IEEE Signal Processing - July 2018 - 34
IEEE Signal Processing - July 2018 - 35
IEEE Signal Processing - July 2018 - 36
IEEE Signal Processing - July 2018 - 37
IEEE Signal Processing - July 2018 - 38
IEEE Signal Processing - July 2018 - 39
IEEE Signal Processing - July 2018 - 40
IEEE Signal Processing - July 2018 - 41
IEEE Signal Processing - July 2018 - 42
IEEE Signal Processing - July 2018 - 43
IEEE Signal Processing - July 2018 - 44
IEEE Signal Processing - July 2018 - 45
IEEE Signal Processing - July 2018 - 46
IEEE Signal Processing - July 2018 - 47
IEEE Signal Processing - July 2018 - 48
IEEE Signal Processing - July 2018 - 49
IEEE Signal Processing - July 2018 - 50
IEEE Signal Processing - July 2018 - 51
IEEE Signal Processing - July 2018 - 52
IEEE Signal Processing - July 2018 - 53
IEEE Signal Processing - July 2018 - 54
IEEE Signal Processing - July 2018 - 55
IEEE Signal Processing - July 2018 - 56
IEEE Signal Processing - July 2018 - 57
IEEE Signal Processing - July 2018 - 58
IEEE Signal Processing - July 2018 - 59
IEEE Signal Processing - July 2018 - 60
IEEE Signal Processing - July 2018 - 61
IEEE Signal Processing - July 2018 - 62
IEEE Signal Processing - July 2018 - 63
IEEE Signal Processing - July 2018 - 64
IEEE Signal Processing - July 2018 - 65
IEEE Signal Processing - July 2018 - 66
IEEE Signal Processing - July 2018 - 67
IEEE Signal Processing - July 2018 - 68
IEEE Signal Processing - July 2018 - 69
IEEE Signal Processing - July 2018 - 70
IEEE Signal Processing - July 2018 - 71
IEEE Signal Processing - July 2018 - 72
IEEE Signal Processing - July 2018 - 73
IEEE Signal Processing - July 2018 - 74
IEEE Signal Processing - July 2018 - 75
IEEE Signal Processing - July 2018 - 76
IEEE Signal Processing - July 2018 - 77
IEEE Signal Processing - July 2018 - 78
IEEE Signal Processing - July 2018 - 79
IEEE Signal Processing - July 2018 - 80
IEEE Signal Processing - July 2018 - 81
IEEE Signal Processing - July 2018 - 82
IEEE Signal Processing - July 2018 - 83
IEEE Signal Processing - July 2018 - 84
IEEE Signal Processing - July 2018 - 85
IEEE Signal Processing - July 2018 - 86
IEEE Signal Processing - July 2018 - 87
IEEE Signal Processing - July 2018 - 88
IEEE Signal Processing - July 2018 - 89
IEEE Signal Processing - July 2018 - 90
IEEE Signal Processing - July 2018 - 91
IEEE Signal Processing - July 2018 - 92
IEEE Signal Processing - July 2018 - 93
IEEE Signal Processing - July 2018 - 94
IEEE Signal Processing - July 2018 - 95
IEEE Signal Processing - July 2018 - 96
IEEE Signal Processing - July 2018 - 97
IEEE Signal Processing - July 2018 - 98
IEEE Signal Processing - July 2018 - 99
IEEE Signal Processing - July 2018 - 100
IEEE Signal Processing - July 2018 - 101
IEEE Signal Processing - July 2018 - 102
IEEE Signal Processing - July 2018 - 103
IEEE Signal Processing - July 2018 - 104
IEEE Signal Processing - July 2018 - 105
IEEE Signal Processing - July 2018 - 106
IEEE Signal Processing - July 2018 - 107
IEEE Signal Processing - July 2018 - 108
IEEE Signal Processing - July 2018 - 109
IEEE Signal Processing - July 2018 - 110
IEEE Signal Processing - July 2018 - 111
IEEE Signal Processing - July 2018 - 112
IEEE Signal Processing - July 2018 - 113
IEEE Signal Processing - July 2018 - 114
IEEE Signal Processing - July 2018 - 115
IEEE Signal Processing - July 2018 - 116
IEEE Signal Processing - July 2018 - 117
IEEE Signal Processing - July 2018 - 118
IEEE Signal Processing - July 2018 - 119
IEEE Signal Processing - July 2018 - 120
IEEE Signal Processing - July 2018 - 121
IEEE Signal Processing - July 2018 - 122
IEEE Signal Processing - July 2018 - 123
IEEE Signal Processing - July 2018 - 124
IEEE Signal Processing - July 2018 - 125
IEEE Signal Processing - July 2018 - 126
IEEE Signal Processing - July 2018 - 127
IEEE Signal Processing - July 2018 - 128
IEEE Signal Processing - July 2018 - 129
IEEE Signal Processing - July 2018 - 130
IEEE Signal Processing - July 2018 - 131
IEEE Signal Processing - July 2018 - 132
IEEE Signal Processing - July 2018 - 133
IEEE Signal Processing - July 2018 - 134
IEEE Signal Processing - July 2018 - 135
IEEE Signal Processing - July 2018 - 136
IEEE Signal Processing - July 2018 - 137
IEEE Signal Processing - July 2018 - 138
IEEE Signal Processing - July 2018 - 139
IEEE Signal Processing - July 2018 - 140
IEEE Signal Processing - July 2018 - Cover3
IEEE Signal Processing - July 2018 - Cover4
https://www.nxtbook.com/nxtbooks/ieee/signalprocessing_201809
https://www.nxtbook.com/nxtbooks/ieee/signalprocessing_201807
https://www.nxtbook.com/nxtbooks/ieee/signalprocessing_201805
https://www.nxtbook.com/nxtbooks/ieee/signalprocessing_201803
https://www.nxtbook.com/nxtbooks/ieee/signalprocessing_201801
https://www.nxtbook.com/nxtbooks/ieee/signalprocessing_1117
https://www.nxtbook.com/nxtbooks/ieee/signalprocessing_0917
https://www.nxtbook.com/nxtbooks/ieee/signalprocessing_0717
https://www.nxtbook.com/nxtbooks/ieee/signalprocessing_0517
https://www.nxtbook.com/nxtbooks/ieee/signalprocessing_0317
https://www.nxtbook.com/nxtbooks/ieee/signalprocessing_0117
https://www.nxtbook.com/nxtbooks/ieee/signalprocessing_1116
https://www.nxtbook.com/nxtbooks/ieee/signalprocessing_0916
https://www.nxtbook.com/nxtbooks/ieee/signalprocessing_0716
https://www.nxtbook.com/nxtbooks/ieee/signalprocessing_0516
https://www.nxtbook.com/nxtbooks/ieee/signalprocessing_0316
https://www.nxtbook.com/nxtbooks/ieee/signalprocessing_0116
https://www.nxtbook.com/nxtbooks/ieee/signalprocessing_1115
https://www.nxtbook.com/nxtbooks/ieee/signalprocessing_0915
https://www.nxtbook.com/nxtbooks/ieee/signalprocessing_0715
https://www.nxtbook.com/nxtbooks/ieee/signalprocessing_0515
https://www.nxtbook.com/nxtbooks/ieee/signalprocessing_0315
https://www.nxtbook.com/nxtbooks/ieee/signalprocessing_0115
https://www.nxtbook.com/nxtbooks/ieee/signalprocessing_1114
https://www.nxtbook.com/nxtbooks/ieee/signalprocessing_0914
https://www.nxtbook.com/nxtbooks/ieee/signalprocessing_0714
https://www.nxtbook.com/nxtbooks/ieee/signalprocessing_0514
https://www.nxtbook.com/nxtbooks/ieee/signalprocessing_0314
https://www.nxtbook.com/nxtbooks/ieee/signalprocessing_0114
https://www.nxtbook.com/nxtbooks/ieee/signalprocessing_1113
https://www.nxtbook.com/nxtbooks/ieee/signalprocessing_0913
https://www.nxtbook.com/nxtbooks/ieee/signalprocessing_0713
https://www.nxtbook.com/nxtbooks/ieee/signalprocessing_0513
https://www.nxtbook.com/nxtbooks/ieee/signalprocessing_0313
https://www.nxtbook.com/nxtbooks/ieee/signalprocessing_0113
https://www.nxtbook.com/nxtbooks/ieee/signalprocessing_1112
https://www.nxtbook.com/nxtbooks/ieee/signalprocessing_0912
https://www.nxtbook.com/nxtbooks/ieee/signalprocessing_0712
https://www.nxtbook.com/nxtbooks/ieee/signalprocessing_0512
https://www.nxtbook.com/nxtbooks/ieee/signalprocessing_0312
https://www.nxtbook.com/nxtbooks/ieee/signalprocessing_0112
https://www.nxtbook.com/nxtbooks/ieee/signalprocessing_1111
https://www.nxtbook.com/nxtbooks/ieee/signalprocessing_0911
https://www.nxtbook.com/nxtbooks/ieee/signalprocessing_0711
https://www.nxtbook.com/nxtbooks/ieee/signalprocessing_0511
https://www.nxtbook.com/nxtbooks/ieee/signalprocessing_0311
https://www.nxtbook.com/nxtbooks/ieee/signalprocessing_0111
https://www.nxtbook.com/nxtbooks/ieee/signalprocessing_1110
https://www.nxtbook.com/nxtbooks/ieee/signalprocessing_0910
https://www.nxtbook.com/nxtbooks/ieee/signalprocessing_0710
https://www.nxtbook.com/nxtbooks/ieee/signalprocessing_0510
https://www.nxtbook.com/nxtbooks/ieee/signalprocessing_0310
https://www.nxtbook.com/nxtbooks/ieee/signalprocessing_0110
https://www.nxtbook.com/nxtbooks/ieee/signalprocessing_1109
https://www.nxtbook.com/nxtbooks/ieee/signalprocessing_0909
https://www.nxtbook.com/nxtbooks/ieee/signalprocessing_0709
https://www.nxtbook.com/nxtbooks/ieee/signalprocessing_0509
https://www.nxtbook.com/nxtbooks/ieee/signalprocessing_0309
https://www.nxtbook.com/nxtbooks/ieee/signalprocessing_0109
https://www.nxtbook.com/nxtbooks/ieee/signalprocessing_1108
https://www.nxtbook.com/nxtbooks/ieee/signalprocessing_0908
https://www.nxtbook.com/nxtbooks/ieee/signalprocessing_0708
https://www.nxtbook.com/nxtbooks/ieee/signalprocessing_0508
https://www.nxtbook.com/nxtbooks/ieee/signalprocessing_0308
https://www.nxtbook.com/nxtbooks/ieee/signalprocessing_0108
https://www.nxtbookmedia.com