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?)

2 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). x fi (x) 0, i = {1, .. , k}. hj (x) = 0, j = {1.}

3 , 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.

4 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. 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.

5 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.

6 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). 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).

7 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.

8 So x + (1 )y C. Duchi (UC Berkeley) Convex Optimization for Machine Learning Fall 2009 12 / 53. 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.

9 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.

10 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.