Super-Linear Convergence of Dual Augmented Lagrangian Algorithm for Sparse Learning

author: Ryota Tomioka, Fraunhofer Institute for Intelligent Analysis and Information Systems
published: Jan. 19, 2010, recorded: December 2009, views: 538

Slides

Slides
0:00	Super-Linear Convergence of Dual Augmented Lagrangian Algorithm for Sparse Learning
0:18	Objective
1:31	Where does the difficulty come from?(1)
2:23	Where does the difficulty come from?(2)
2:57	Proximation wrt φλ can be computed analytically
3:11	Outline
3:56	Iterative Shrinkage/Thresholding (IST) (1)
4:29	Iterative Shrinkage/Thresholding (IST) (2)
4:45	Dual Augmented Lagrangian (DAL) method (1)
4:55	Dual Augmented Lagrangian (DAL) method (2)
5:18	Dual Augmented Lagrangian (DAL) method (3)
8:12	Difference: How do we get rid of the couplings? (2)
8:18	Difference: How do we get rid of the couplings? (1)
8:32	Difference: How do we get rid of the couplings? (3)
9:27	Numerical examples
9:46	Theorem 1 (exact minimization)
11:13	Theorem 2 (approximate minimization)
11:36	Theorem 2 (approximate minimization), Theorem
12:53	Proof (in essence) of Theorem 1
13:40	Proof (in essence) of Theorem 2
14:30	Empirical results: ℓ1-logistic regression
16:51	Summary 1
17:43	Summary 2
18:05	Summary 3
18:28	Summary 4

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.

Lecture popularity: You need to login to cast your vote.

Description

We analyze the convergence behaviour of a recently proposed algorithm for sparse learning called Dual Augmented Lagrangian (DAL). We theoretically analyze under some conditions that DAL converges super-linearly in a non-asymptotic and global sense. We experimentally confirm our analysis in a large scale ℓ1-regularized logistic regression problem and compare the efficiency of DAL algorithm to existing algorithms.