Introduction to Convex Optimization for Machine Learning

1 Introduction to Convex Optimization for Machine Learning John Duchi University of California, Berkeley Practical Machine Learning , Fall 2009. Duchi (UC Berkeley) Convex Optimization for Machine Learning Fall 2009 1 / 53. Outline What is Optimization Convex Sets Convex Functions Convex Optimization Problems Lagrange Duality Optimization Algorithms Take Home Messages Duchi (UC Berkeley) Convex Optimization for Machine Learning Fall 2009 2 / 53. What is Optimization What is Optimization (and why do we care?). Duchi (UC Berkeley) Convex Optimization for Machine Learning Fall 2009 3 / 53. What is Optimization What is Optimization ? Finding the minimizer of a function subject to constraints: minimize f0 (x). x fi (x) 0, i = {1, .. , k}. hj (x) = 0, j = {1, .. , l}. Duchi (UC Berkeley) Convex Optimization for Machine Learning Fall 2009 4 / 53. What is Optimization What is Optimization ? Finding the minimizer of a function subject to constraints: minimize f0 (x).

2 X fi (x) 0, i = {1, .. , k}. hj (x) = 0, j = {1, .. , l}. Example: Stock market. Minimize variance of return subject to getting at least $50.. Duchi (UC Berkeley) Convex Optimization for Machine Learning Fall 2009 4 / 53. What is Optimization Why do we care? Optimization is at the heart of many (most practical?) Machine Learning algorithms. Linear regression: minimize kXw yk2. w Classification (logistic regresion or SVM): n X. log 1 + exp( yi xTi w).. minimize w i=1. n or kwk2 + C. X. i i 1 yi xTi w, i 0. i=1. Duchi (UC Berkeley) Convex Optimization for Machine Learning Fall 2009 5 / 53. What is Optimization We still Maximum likelihood estimation: n X. maximize log p (xi ).. i=1. Collaborative filtering: X. log 1 + exp(wT xi wT xj ).. minimize w i j k-means: k X. kxi j k2. X. minimize J( ) =. 1 ,.., k j=1 i Cj And more (graphical models, feature selection, active Learning , control). Duchi (UC Berkeley) Convex Optimization for Machine Learning Fall 2009 6 / 53.

3 What is Optimization But generally We're screwed. Local (non global) minima of f0. All kinds of constraints (even restricting to continuous functions): h(x) = sin(2 x) = 0. 250. 200. 150. 100. 50. 0. 50. 3. 2. 3. 1 2. 0 1. 1 0. 1. 2 2. 3 3. Duchi (UC Berkeley) Convex Optimization for Machine Learning Fall 2009 7 / 53. What is Optimization But generally We're screwed. Local (non global) minima of f0. All kinds of constraints (even restricting to continuous functions): h(x) = sin(2 x) = 0. 250. 200. 150. 100. 50. 0. 50. 3. 2. 3. 1 2. 0 1. 1 0. 1. 2 2. 3 3. Go for Convex problems! Duchi (UC Berkeley) Convex Optimization for Machine Learning Fall 2009 7 / 53. Convex Sets Convex Sets Duchi (UC Berkeley) Convex Optimization for Machine Learning Fall 2009 8 / 53. Convex Sets Definition A set C Rn is Convex if for x, y C and any [0, 1], x + (1 )y C. y x Duchi (UC Berkeley) Convex Optimization for Machine Learning Fall 2009 9 / 53. Convex Sets Examples All of Rn (obvious).

4 Duchi (UC Berkeley) Convex Optimization for Machine Learning Fall 2009 10 / 53. Convex Sets Examples All of Rn (obvious). Non-negative orthant, Rn+ : let x 0, y 0, clearly x + (1 )y 0. Duchi (UC Berkeley) Convex Optimization for Machine Learning Fall 2009 10 / 53. Convex Sets Examples All of Rn (obvious). Non-negative orthant, Rn+ : let x 0, y 0, clearly x + (1 )y 0. Norm balls: let kxk 1, kyk 1, then k x + (1 )yk k xk + k(1 )yk = kxk + (1 ) kyk 1. Duchi (UC Berkeley) Convex Optimization for Machine Learning Fall 2009 10 / 53. Convex Sets Examples Affine subspaces: Ax = b, Ay = b, then A( x + (1 )y) = Ax + (1 )Ay = b + (1 )b = b. 1. x3. 0. 1. 1. x2 0 0. x1. Duchi (UC Berkeley) Convex Optimization for Machine Learning Fall 2009 11 / 53. Convex Sets More examples Arbitrary T intersections of Convex sets: let Ci be Convex for i I, C = i Ci , then x C, y C x + (1 )y Ci i I. so x + (1 )y C. Duchi (UC Berkeley) Convex Optimization for Machine Learning Fall 2009 12 / 53.

5 Convex Sets More examples PSD Matrices, the positive semidefinite cone Sn+ Rn n . A Sn+ means xT Ax 0 for all x Rn . For 1. A, B S+ n, xT ( A + (1 )B) x z = xT Ax + (1 )xT Bx 0. 0. 1. 1. On right: 0. y 1 0. x 2 x z 0 = x, y, z : x 0, y 0, xy z 2.. S+ =. z y Duchi (UC Berkeley) Convex Optimization for Machine Learning Fall 2009 13 / 53. Convex Functions Convex Functions Duchi (UC Berkeley) Convex Optimization for Machine Learning Fall 2009 14 / 53. Convex Functions Definition A function f : Rn R is Convex if for x, y dom f and any [0, 1], f ( x + (1 )y) f (x) + (1 )f (y). f (y). f(x) + (1 - )f(y). f (x). Duchi (UC Berkeley) Convex Optimization for Machine Learning Fall 2009 15 / 53. Convex Functions First order convexity conditions Theorem Suppose f : Rn R is differentiable. Then f is Convex if and only if for all x, y dom f f (y) f (x) + f (x)T (y x). f(y). f(x) + f(x)T (y - x). (x, f(x)). Duchi (UC Berkeley) Convex Optimization for Machine Learning Fall 2009 16 / 53.

6 Convex Functions Actually, more general than that Definition The subgradient set, or subdifferential set, f (x) of f at x is f (x) = g : f (y) f (x) + g T (y x) for all y .. f (y). Theorem f : Rn R is Convex if and only if it has non-empty (x, f(x)). subdifferential set everywhere. f (x) + g T (y - x). Duchi (UC Berkeley) Convex Optimization for Machine Learning Fall 2009 17 / 53. Convex Functions Second order convexity conditions Theorem Suppose f : Rn R is twice differentiable. Then f is Convex if and only if for all x dom f , 2 f (x) 0. 10. 8. 6. 4. 2. 0. 2. 1 2. 1. 0. 0. 1. 1. 2 2. Duchi (UC Berkeley) Convex Optimization for Machine Learning Fall 2009 18 / 53. Convex Functions Convex sets and Convex functions Definition The epigraph of a function f is the epi f set of points epi f = {(x, t) : f (x) t}. epi f is Convex if and only if f is Convex . a Sublevel sets, {x : f (x) a}. are Convex for Convex f . Duchi (UC Berkeley) Convex Optimization for Machine Learning Fall 2009 19 / 53.

7 Convex Functions Examples Examples Linear/affine functions: f (x) = bT x + c. Duchi (UC Berkeley) Convex Optimization for Machine Learning Fall 2009 20 / 53. Convex Functions Examples Examples Linear/affine functions: f (x) = bT x + c. Quadratic functions: 1. f (x) = xT Ax + bT x + c 2. for A 0. For regression: 1 1 1. kXw yk2 = wT X T Xw y T Xw + y T y. 2 2 2. Duchi (UC Berkeley) Convex Optimization for Machine Learning Fall 2009 20 / 53. Convex Functions Examples More examples Norms (like 1 or 2 for regularization): k x + (1 )yk k xk + k(1 )yk = kxk + (1 ) kyk . Duchi (UC Berkeley) Convex Optimization for Machine Learning Fall 2009 21 / 53. Convex Functions Examples More examples Norms (like 1 or 2 for regularization): k x + (1 )yk k xk + k(1 )yk = kxk + (1 ) kyk . Composition with an affine function f (Ax + b): f (A( x + (1 )y) + b) = f ( (Ax + b) + (1 )(Ay + b)). f (Ax + b) + (1 )f (Ay + b). Duchi (UC Berkeley) Convex Optimization for Machine Learning Fall 2009 21 / 53.

8 Convex Functions Examples More examples Norms (like 1 or 2 for regularization): k x + (1 )yk k xk + k(1 )yk = kxk + (1 ) kyk . Composition with an affine function f (Ax + b): f (A( x + (1 )y) + b) = f ( (Ax + b) + (1 )(Ay + b)). f (Ax + b) + (1 )f (Ay + b). Log-sum-exp (via 2 f (x) PSD): n ! X. f (x) = log exp(xi ). i=1. Duchi (UC Berkeley) Convex Optimization for Machine Learning Fall 2009 21 / 53. Convex Functions Examples Important examples in Machine Learning 3. SVM loss: [1 - x]+. f (w) = 1 yi xTi w +.. Binary logistic loss: log(1 + ex ). f (w) = log 1 + exp( yi xTi w).. 0. 2 3. Duchi (UC Berkeley) Convex Optimization for Machine Learning Fall 2009 22 / 53. Convex Optimization Problems Convex Optimization Problems Definition An Optimization problem is Convex if its objective is a Convex function, the inequality constraints fj are Convex , and the equality constraints hj are affine minimize f0 (x) ( Convex function). x fi (x) 0 ( Convex sets).

9 Hj (x) = 0 (Affine). Duchi (UC Berkeley) Convex Optimization for Machine Learning Fall 2009 23 / 53. Convex Optimization Problems It's nice to be Convex Theorem If x is a local minimizer of a Convex Optimization problem, it is a global minimizer. 4. x . 3. 2. 1. 0 1 2 3 Duchi (UC Berkeley) Convex Optimization for Machine Learning Fall 2009 24 / 53. Convex Optimization Problems Even more reasons to be Convex Theorem f (x) = 0 if and only if x is a global minimizer of f (x). Proof. f (x) = 0. We have f (y) f (x) + f (x)T (y x) = f (x). f (x) 6= 0. There is a direction of descent. Duchi (UC Berkeley) Convex Optimization for Machine Learning Fall 2009 25 / 53. Convex Optimization Problems LET'S TAKE A BREAK. Duchi (UC Berkeley) Convex Optimization for Machine Learning Fall 2009 26 / 53. Lagrange Duality Lagrange Duality Duchi (UC Berkeley) Convex Optimization for Machine Learning Fall 2009 27 / 53. Lagrange Duality Goals of Lagrange Duality Get certificate for optimality of a problem Remove constraints Reformulate problem Duchi (UC Berkeley) Convex Optimization for Machine Learning Fall 2009 28 / 53.

10 Lagrange Duality Constructing the dual Start with Optimization problem: minimize f0 (x). x fi (x) 0, i = {1, .. , k}. hj (x) = 0, j = {1, .. , l}. Form Lagrangian using Lagrange multipliers i 0, i R. k X l X. L(x, , ) = f0 (x) + i fi (x) + j hj (x). i=1 j=1. Form dual function . k X l X . g( , ) = inf L(x, , ) = inf f0 (x) + i fi (x) + j hj (x). x x . i=1 j=1. Duchi (UC Berkeley) Convex Optimization for Machine Learning Fall 2009 29 / 53. Lagrange Duality Remarks Original problem is equivalent to " #. minimize sup L(x, , ). x 0, . Dual problem is switching the min and max: h i maximize inf L(x, , ) . 0, x Duchi (UC Berkeley) Convex Optimization for Machine Learning Fall 2009 30 / 53. Lagrange Duality One Great Property of Dual Lemma (Weak Duality). If 0, then g( , ) f0 (x ). Proof. We have g( , ) = inf L(x, , ) L(x , , ). x k X l X. = f0 (x ) + i fi (x ) + j hj (x ) f0 (x ). i=1 j=1. Duchi (UC Berkeley) Convex Optimization for Machine Learning Fall 2009 31 / 53.