18.657 Mathematics of Machine Learning, Lecture 14 Notes

18.657: Mathematics of Machine Learning Lecture 14 Oct. 26, 2015 Lecturer: Philippe Rigollet Scribe: Sylvain Carpentier In this lecture we will wrap up the study of optimization techniques with stochastic optimization. The tools that we are going to develop will turn out to be very efficient in minimizing the ϕ-risk when we can bound the noise on the gradient. 3. STOCHASTIC OPTIMIZATION 3.1 Stochastic convex optimization We are considering random functions x 7→ ℓ(x, Z) where x is the optimization parameter and Z a random variable. Let PZ be the distribution of Z and let us assume that x 7→ ℓ(x, Z) is convex PZ a.s. In particular, IE[ℓ(x, Z)] will also be convex. The goal of stochastic convex optimization is to approach minx∈C IE[ℓ(x, Z)] when C is convex. For our purposes, C will be a deterministic convex set. However, stochastic convex optimization can be defined more broadly. The constraint can be itself stochastic : C = {x, IE[g(x, Z)] ≤ 0}, C = {x, IP[g(x, Z) ≤ 0] ≥ 1 − ε}, g convex PZ a.s. “chance constraint” The second constraint is not convex a priori but remedies are possible (see [NS06, Nem12]). In the following, we will stick to the case where X is deterministic. A few optimization problems we tackled can be interpreted in this new framework. 3.1.1 Examples Boosting. Recall that the goal in Boosting is to minimize the ϕ-risk: min IE[ϕ(−Y fα (X))] , α∈Λ where Λ is the simplex of IRd . Define Z = (X, Y ) and the random function ℓ(α, Z) = ϕ(−Y fα(X)), convex PZ a.s. Linear regression. Here the goal is the minimize the ℓ2 risk: min IE[(Y − fα (X))2 ] . α∈IRd Define Z = (X, Y ) and the random function ℓ(α, Z) = (Y − fα (X))2 , convex PZ a.s. Maximum likelihood. We consider samples Z1 , . . . , Zn iid with density pθ , θ ∈ Θ. For instance, Z∼ N (θ, 1). The likelihood functions associated to this set of samples is θ 7→ Qn ∗ p (Z i ). Let p (Z) denote the true density of Z (it does not have to be of the form pθ θ i=1 for some θ ∈ Θ. Then Z n Y p∗ (z) ∗ 1 IE[log pθ (Zi )] = − log( )p (z)dz + C = −KL(p∗ , pθ ) + C n pθ (z) i=1 1 where C is a constant in θ. Hence maximizing the expected log-likelihood is equivalent to minimizing the expected Kullback-Leibler divergence: maxIE[log θ n Y i=1 pθ (Zi )] ⇐⇒ KL(p∗ , pθ ) External randomization. Assume that we want to minimize a function of the form n f (x) = 1X fi (x) , n i=1 where the functions f1 , . . . , fn are convex. As we have seen, this arises a lot in empirical risk minimization. In this case, we treat this problem as deterministic problem but inject artificial randomness as follows. Let I be a random variable uniformly distributed on [n] =: {1, . . . , n}. We have the representation f (x) = IE[fI (x)], which falls into the context of stochastic convex optimization with Z = I and ℓ(x, I) = fI (x). Important Remark: There is a key difference between the case where we assume that we are given independent random variables and the case where we generate artificial randomness. Let us illustrate this difference for Boosting. We are given (X1 , Y1 ), . . . , (Xn , Yn ) i.i.d from some unknown distribution. In the first example, our aim is to minimize IE[ϕ(−Y fα (X))] based on these n observations and we will that the stochastic gradient allows to do that by take one pair (Xi , Yi ) in each iteration. In particular, we can use each pair at most once. We say that we do one pass on the data. We could also leverage our statistical analysis of the empirical risk minimizer from previous lectures and try to minimize the empirical ϕ-risk n R̂n,ϕ (fα ) = 1X ϕ(−Yi fα (Xi )) n i=1 by generating k independent random variables I1 , . . . , Ik uniform over [n] and run the stochastic gradient descent to us one random variable Ij in each iteration. The difference here is that k can be arbitrary large, regardless of the number n of observations (we make multiple passes on the data). However, minimizing IEI [ϕ(−YI fα (XI ))|X1 , Y1 , . . . , Xn , Yn ] will perform no better than the empirical risk minimizer whose statistical performance is limited by the number n of observations. 3.2 Stochastic gradient descent If the distribution of Z was known, then the function x 7→ IE[ℓ(x, Z)] would be known and we could apply gradient descent, projected gradient descent or any other optimization tool seen before in the deterministic setup. However this is not the case in reality where the true distribution PZ is unknown and we are only given the samples Z1 , . . . , Zn and the random function ℓ(x, Z). In what follows, we denote by ∂ℓ(x, Z) the set of subgradients of the function y 7→ ℓ(y, Z) at point x. 2 Algorithm 1 Stochastic Gradient Descent algorithm Input: x1 ∈ C, positive sequence {ηs }s≥1 , independent random variables Z1 , . . . , Zk with distribution PZ . for s = 1 to k − 1 do ys+1 = xs − ηs g̃s , g̃s ∈ ∂ℓ(xs , Zs ) xs+1 = πC (ys+1 ) end for k 1X return x̄k = xs k s=1 Note the difference here with the deterministic gradient descent which returns either x̄k or x◦k = argmin f (x). In the stochastic framework, the function f (x) = IE[ℓ(x, ξ)] is x1 ,...,xn typically unknown and x˚k cannot be computed. Theorem: Let C be a closed convex subset of IRd such that diam(C) ≤ R. Assume that he convex function f (x) = IE[ℓ(x, Z)] attains its minimum on C at x∗ ∈ IRd . Assume that ℓ(x, Z) is convex PZ a.s. and that IEkg̃k2 ≤ L2 for all g̃ ∈ ∂ℓ(x, Z) for all x. Then √ , if ηs ≡ η = LR k LR IE[f (x̄k )] − f (x∗ ) ≤ √ k Proof. f (xs ) − f (x∗ ) ≤ gs ⊤ (xs − x∗ ) = IE[g̃s⊤ (xs − x∗ )|xs ] 1 = IE[(ys+1 − xs )⊤ (xs − x∗ )|xs ] η 1 = IE[kxs − ys+1 k2 + kxs − x∗ k2 − kys+1 − x∗ k2 |xs ] 2η 1 2 ≤ (η IE[kg̃s k2 |xs ] + IE[kxs − x∗ k2 |xs ] − IE[kxs+1 − x∗ k2 |xs ] 2η Taking expectations and summing over s we get k 1X ηL2 R2 f (xs ) − f (x∗ ) ≤ + . k s=1 2 2ηk Using Jensen’s inequality and chosing η = R √ , L k we get LR IE[f (x¯k )] − f (x∗ ) ≤ √ k 3 3.3 Stochastic Mirror Descent We can also extend the Mirror Descent to a stochastic version as follows. Algorithm 2 Mirror Descent algorithm Input: x1 ∈ argminC∩D Φ(x), ζ : Rd → Rd such that ζ(x) = ∇Φ(x), independent random variables Z1 , . . . , Zk with distribution PZ . for s = 1, · · · , k do ζ(ys+1 ) = ζ(xs ) − ηg̃s for g̃s ∈ ∂ℓ(xs , Zs ) xs+1 = ΠΦ C (ys+1 ) end for P return x = k1 ks=1 xs Theorem: Assume that Φ is α-strongly convex on C ∩ D w.r.t. k · k and R2 = sup Φ(x) − min Φ(x) x∈C∩D x∈C∩D take x1 = argmin x∈C∩D Φ(x) (assume that it exists). Then, Stochastic Mirror Descent q R 2α with η = L R outputs x ¯k , such that ∗ IE[f (x̄k )] − f (x ) ≤ RL r 2 . αk Proof. We essentially reproduce the proof for the Mirror Descent algorithm. Take x♯ ∈ C ∩ D. We have f (xs ) − f (x♯ ) ≤ gs⊤ (xs − x♯ ) IE[g̃s⊤ (xs − x∗ )|xs ] 1 = IE[(ζ(xs ) − ζ(ys+1 ))⊤ (xs − x♯ )|xs ] η 1 = IE[(∇Φ(xs ) − ∇Φ(ys+1 ))⊤ (xs − x♯ )|xs ] η i 1 h = IE DΦ (xs , ys+1 ) + DΦ (x♯ , xs ) − DΦ (x♯ , ys+1 ) xs η i 1 h ≤ IE DΦ (xs , ys+1 ) + DΦ (x♯ , xs ) − DΦ (x♯ , xs+1 ) xs η i η 1 h 2 ♯ ♯ ≤ IE[kg̃ k |x ] + IE D (x , x ) − D (x , x ) x s s ∗ s Φ s Φ s+1 2α2 η 4 where the last inequality comes from DΦ (xs , ys+1 ) = Φ(xs ) − Φ(ys+1 ) − ∇Φ(ys+1 )⊤ (xs − ys+1 ) α ≤ [∇Φ(xs ) − ∇Φ(ys+1 )]⊤ (xs − ys+1 ) − kys+1 − xs k2 2 α 2 ≤ ηkg̃s k∗ kxs − ys+1 k − kys+1 − xs k 2 η 2 kg̃s k2∗ ≤ . 2α Summing and taking expectations, we get k 1X ηL2 DΦ (x♯ , x1 ) [f (xs ) − f (x♯ )] ≤ + . k 2α kη (3.1) s=1 We conclude as in the previous lecture. 3.4 Stochastic coordinate descent Let f be a convex L-Lipschitz and differentiable function on IRd . Let us denote by ∇i f the partial derivative of f in the direction ei . One drawback of the Gradient Descent Algorithm is that at each step one has to update every coordinate ∇i f of the gradient. The idea of the stochastic coordinate descent is to pick at each step a direction ej uniformly and to choose that ej to be the direction of the descent at that step. More precisely, of I is drawn uniformly on [d], then IE[d∇I f (x)eI ] = ∇f (x). Therefore, the vector d∇I f (x)eI that has only one nonzero coordinate is an unbiased estimate of the gradient ∇f (x). We can use this estimate to perform stochastic gradient descent. Algorithm 3 Stochastic Coordinate Descent algorithm Input: x1 ∈ C, positive sequence {ηs }s≥1 , independent random variables I1 , . . . , Ik uniform over [d]. for s = 1 to k − 1 do ys+1 = xs − ηs d∇I f (x)eI , g̃s ∈ ∂ℓ(xs , Zs ) xs+1 = πC (ys+1 ) end for k 1X return x̄k = xs k s=1 q 2 If we apply Stochastic Gradient Descent to this problem for η = R L dk , we directly obtain r 2d ∗ IE[f (x¯k )] − f (x ) ≤ RL k We are in a trade-off situation where the updates are much easier to implement but where we need more steps to reach the same precision as the gradient descent alogrithm. 5 References [Nem12] Arkadi Nemirovski, On safe tractable approximations of chance constraints, European J. Oper. Res. 219 (2012), no. 3, 707–718. MR 2898951 (2012m:90133) [NS06] Arkadi Nemirovski and Alexander Shapiro, Convex approximations of chance constrained programs, SIAM J. Optim. 17 (2006), no. 4, 969–996. MR 2274500 (2007k:90077) 6