25th Annual Conference on Neural Information Processing Systems (NIPS), Granada 2011

Convergence Rates of Inexact Proximal-Gradient Methods for Convex Optimization

author: Mark Schmidt, Department of Computer Science, University of British Columbia
published: Jan. 25, 2012, recorded: December 2011, views: 433

Slides

Slides
0:00	Convergence Rates of Inexact Proximal-Gradient Methods for Convex Optimization
0:00	Outline - 1
0:15	Composite Convex Optimization Problems - 1
0:30	Composite Convex Optimization Problems - 2
0:52	Fast Convergence Rates of Proximal-Gradient Methods - 1
0:56	Fast Convergence Rates of Proximal-Gradient Methods - 2
1:13	Fast Convergence Rates of Proximal-Gradient Methods - 3
1:29	Fast Convergence Rates of Proximal-Gradient Methods - 4
1:35	Fast Convergence Rates of Proximal-Gradient Methods - 5
1:47	Overview of the Basic Gradient Method - 1
1:54	Overview of the Basic Gradient Method - 2
2:13	Overview of the Basic Gradient Method - 3
2:22	Overview of the Basic Gradient Method - 4
2:31	Overview of the Basic Proximal-Gradient Method - 1
2:36	Overview of the Basic Proximal-Gradient Method - 2
2:42	Overview of the Basic Proximal-Gradient Method - 3
2:47	Overview of the Basic Proximal-Gradient Method - 4
2:53	Overview of the Basic Proximal-Gradient Method - 5
3:02	Special case of Projected-Gradient Methods - 1
3:15	Special case of Projected-Gradient Methods - 2
3:27	Special case of Projected-Gradient Methods - 3
3:36	Special case of Projected-Gradient Methods - 4
3:44	Special case of Projected-Gradient Methods - 5
4:17	Special case of Iterative Soft-Thresholding Methods - 1
4:27	Special case of Iterative Soft-Thresholding Methods - 2
4:36	Special case of Iterative Soft-Thresholding Methods - 3
4:39	Special case of Iterative Soft-Thresholding Methods - 4
4:42	Special case of Iterative Soft-Thresholding Methods - 5
5:05	Special case of Iterative Soft-Thresholding Methods - 6
5:26	Accelerated (Proximal-) Gradient Methods - 1
5:35	Accelerated (Proximal-) Gradient Methods - 2
5:49	Accelerated (Proximal-) Gradient Methods - 3
5:55	Exact Proximal-Gradient Methods - 1
6:03	Exact Proximal-Gradient Methods - 2
6:14	Exact Proximal-Gradient Methods - 3
6:24	Inexact Proximal-Gradient Methods - 1
6:26	Inexact Proximal-Gradient Methods - 2
6:47	Summary of Contribution - 1
6:58	Summary of Contribution - 2
7:05	Summary of Contribution - 3
7:12	Summary of Contribution - 4
7:22	Outline - 2
7:28	Prior Work: Stochastic Proximal-Gradient Methods - 1
7:37	Prior Work: Stochastic Proximal-Gradient Methods - 2
7:43	Prior Work: Stochastic Proximal-Gradient Methods - 3
7:58	Prior Work: Projected-Gradient Methods (Fixed Error) - 1
8:03	Prior Work: Projected-Gradient Methods (Fixed Error) - 2
8:08	Prior Work: Projected-Gradient Methods (Fixed Error) - 3
8:19	Prior Work: Projected-Gradient Methods (Variable Error) - 1
8:22	Prior Work: Projected-Gradient Methods (Variable Error) - 2
8:29	Prior Work: Projected-Gradient Methods (Variable Error) - 3
8:42	Prior Work: Proximal-Gradient Methods - 1
8:45	Prior Work: Proximal-Gradient Methods - 2
8:55	Prior Work: Proximal-Gradient Methods - 3
9:01	Outline - 3
9:06	Problem Setting and Algorithm - 1
9:15	Problem Setting and Algorithm - 2
9:20	Central Assumptions and Notation - 1
9:41	Central Assumptions and Notation - 2
9:58	Central Assumptions and Notation - 3
10:06	Central Assumptions and Notation - 4
10:26	Fast Convergence Rates of Proximal-Gradient Methods - 1
10:36	Fast Convergence Rates of Proximal-Gradient Methods - 2
10:43	Convexity - Basic Proximal-Gradient Method - 1
10:55	Convexity - Basic Proximal-Gradient Method - 2
11:02	Convexity - Basic Proximal-Gradient Method - 3
11:12	Convexity - Accelerated Proximal-Gradient Method - 1
11:26	Convexity - Accelerated Proximal-Gradient Method - 2
11:29	Convexity - Accelerated Proximal-Gradient Method - 3
11:44	Strongly Convex Objectives - 1
11:48	Strongly Convex Objectives - 2
12:03	Strongly Convex Objectives - 3
12:07	Strong Convexity - Basic Proximal-Gradient Method - 1
12:22	Strong Convexity - Basic Proximal-Gradient Method - 2
12:34	Strong Convexity - Accelerated Method - 1
12:47	Strong Convexity - Accelerated Method - 2
12:56	Outline - 4
13:01	CUR-like factorization with the l2-norm - 1
13:17	CUR-like factorization with the l2-norm - 2
13:39	CUR-like factorization with the l2-norm - 3
13:56	Comparison against a xed prox solution accuracy
14:23	Comparison against a xed number of prox iterations
14:33	Comparison of dierent prox accuracy decays
14:52	Discussion - 1
15:14	Discussion - 2
15:24	Discussion - 3
15:44	Summary - 1
15:51	Summary - 2
15:54	Summary - 3
15:59	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 consider the problem of optimizing the sum of a smooth convex function and a non-smooth convex function using proximal-gradient methods, where an error is present in the calculation of the gradient of the smooth term or in the proximity operator with respect to the second term. We show that the basic proximal-gradient method, the basic proximal-gradient method with a strong convexity assumption, and the accelerated proximal-gradient method achieve the same convergence rates as in the error-free case, provided the errors decrease at an appropriate rate. Our experimental results on a structured sparsity problem indicate that sequences of errors with these appealing theoretical properties can lead to practical performance improvements.