The 25th International Conference on Machine Learning (ICML 2008)

A Quasi-Newton Approach to Nonsmooth Convex Optimization

author: Jin Yu, NICTA

Description

We extend the well-known BFGS quasi-Newton method and its limited-memory variant (LBFGS) to the optimization of nonsmooth convex objectives. This is done in a rigorous fashion by generalizing three components of BFGS to subdifferentials: The local quadratic model, the identification of a descent direction, and the Wolfe line search conditions. We apply the resulting sub(L)BFGS algorithm to L2-regularized risk minimization with binary hinge loss, and its direction-finding component to L1-regularized risk minimization with logistic loss. In both settings our generic algorithms perform comparable to or better than their counterparts in specialized state-of-the-art solvers.

You might be experiencing some problems with Your Video player.

*Slides*
0:00	A Quasi-Newton Approach to Nonsmooth Convex Optimization
0:14	Classical Quasi-Newton Approach - 1
0:50	Classical Quasi-Newton Approach - 2
1:24	Classical Quasi-Newton Approach - 3
1:52	Classical Quasi-Newton Approach - 4
2:02	Classical Quasi-Newton Approach - 5
2:16	Classical Quasi-Newton Approach - 6
2:39	Classical Quasi-Newton Approach - 7
3:16	Classical Quasi-Newton Approach - 8
3:28	Nonsmooth Convex Functions - 1
3:54	Nonsmooth Convex Functions - 2
4:09	Nonsmooth Convex Functions - 3
4:16	Nonsmooth Convex Functions - 4
4:19	Nonsmooth Convex Functions - 5
4:33	Nonsmooth Convex Functions - 6
4:43	The Good, the Bad, and the Ugly - 1
4:52	The Good, the Bad, and the Ugly - 2
5:21	The Good, the Bad, and the Ugly - 3
5:41	The Good, the Bad, and the Ugly - 4
5:47	The Good, the Bad, and the Ugly - 5
6:06	The Good, the Bad, and the Ugly - 6
6:22	The Good, the Bad, and the Ugly - 7
6:34	The Good, the Bad, and the Ugly - 8
6:54	The Good, the Bad, and the Ugly - 9
7:10	Changing the Model - 1
7:36	Changing the Model - 2
8:03	Changing the Model - 3
8:28	Changing the Model - 4
9:14	Descent Direction Finding - 1
9:17	Descent Direction Finding - 2
9:31	Descent Direction Finding - 3
9:45	Descent Direction Finding - 4
10:05	Descent Direction Finding - 5
10:26	Descent Direction Finding - 6
10:29	Descent Direction Finding - 7
10:38	Descent Direction Finding - 8
11:34	Descent Direction Finding - 9
12:16	Descent Direction Finding - 10
12:41	Modifying Line Search - 1
13:31	Modifying Line Search - 2
14:37	L2-Regularized Hinge Loss Minimization - 1
14:49	L2-Regularized Hinge Loss Minimization - 2
14:55	L2-Regularized Hinge Loss Minimization - 3
15:02	L2-Regularized Hinge Loss Minimization - 4
15:13	SubLBFGS with Exact Line Search on MNIST
16:55	L1-Regularized Logistic Loss Minimization - 1
17:26	L1-Regularized Logistic Loss Minimization - 2
17:28	L1-Regularized Logistic Loss Minimization - 3
18:04	L1-Regularized Logistic Loss Minimization - 4
18:16	Conclusions - 1
18:32	Conclusions - 2
19:07	Conclusions - 3
19:19	Conclusions - 4
19:21	Conclusions - 5
20:09	Conclusions - 6
20:29	- Questions

Lecture rating

People found this lecture:
Worth seeing
because it is:
Valuable and informative
Well presented
Easily understandable
Acceptably recorded
You need to login to cast your vote.

Report a problem or upload files

If you have found a problem with this lecture or would like to send us extra material, articles, exercises, etc., please use our ticket system to describe your request and upload the data.
Enter your e-mail into the 'Cc' field, and we will keep you updated with your request's status.