Efficiency of Quasi-Newton Methods on Strictly Positive Functions

author: Yurii Nesterov, Université catholique de Louvain
published: Jan. 13, 2011, recorded: December 2010, views: 384

Slides

Slides
0:00	Efficiency of Quasi-Newton methods on strictly positive functions
3:15	Outline
4:01	Standard approach: Absolute accuracy - 1
4:09	Standard approach: Absolute accuracy - 2
4:29	Standard approach: Absolute accuracy - 3
4:44	Standard approach: Absolute accuracy - 4
4:54	Standard approach: Absolute accuracy - 5
5:25	Standard approach: Absolute accuracy - 6
5:47	Standard approach: Absolute accuracy - 7
6:26	Relative accuracy (RA) - 1
6:48	Relative accuracy (RA) - 1
7:02	Relative accuracy (RA) - 3
7:53	Relative accuracy (RA) - 4
7:57	Relative accuracy (RA) - 5
9:00	Relative accuracy (RA) - 6
9:28	Relative accuracy (RA) - 7
9:43	Relative accuracy (RA) - 8
10:01	Relative accuracy (RA) - 9
10:20	Relative accuracy (RA) - 10
10:41	Barrier subgradient method [N.10] - 1
10:50	Barrier subgradient method [N.10] - 2
11:29	Barrier subgradient method [N.10] - 3
12:15	Barrier subgradient method [N.10] - 4
13:12	Strictly positive functions - 1
13:28	Strictly positive functions - 2
14:07	Strictly positive functions - 3
14:36	Strictly positive functions - 4
14:38	Strictly positive functions - 5
14:49	Strictly positive functions - 6
15:24	Strictly positive functions - 7
15:50	Simple examples - 1
15:53	Simple examples - 2
16:12	Simple examples - 3
16:39	Simple examples - 4
16:51	Simple examples - 5
17:01	Simple examples - 6
17:11	Simple examples - 7
18:03	Particular examples - 1
18:05	Particular examples - 2
18:28	General convex functions - 1
18:34	General convex functions - 2
18:52	General convex functions - 3
19:04	General convex functions - 4
19:22	General convex functions - 5
19:41	General convex functions - 6
19:59	Shifted general optimization problem - 1
20:18	Shifted general optimization problem - 2
20:51	Shifted general optimization problem - 3
20:56	Shifted general optimization problem - 4
21:23	Shifted general optimization problem - 5
21:49	Shifted general optimization problem - 6
21:52	Shifted general optimization problem - 7
21:54	Shifted general optimization problem - 8
22:51	Optimization problem with squared objective - 1
23:05	Optimization problem with squared objective - 2
23:14	Optimization problem with squared objective - 3
23:18	Optimization problem with squared objective - 4
23:51	Optimization problem with squared objective - 5
23:53	Optimization problem with squared objective - 6
24:18	Optimization problem with squared objective - 7
24:28	Optimization problem with squared objective - 8
24:43	Optimization problem with squared objective - 9
25:00	Optimization problem with squared objective - 10
25:13	Quasi-Newton Method - 1
25:22	Quasi-Newton Method - 2
25:37	Quasi-Newton Method - 3
25:56	Quasi-Newton Method - 4
26:04	Quasi-Newton Method - 5
26:55	Quasi-Newton Method - 6
27:06	Quasi-Newton Method - 7
28:14	Evolution of the Hessians - 1
28:16	Evolution of the Hessians - 2
28:58	Evolution of the Hessians - 3
29:11	Quasi-Newton Method - 7
29:28	Evolution of the Hessians - 4
29:31	Evolution of the Hessians - 5
29:32	Evolution of the Hessians - 6
29:57	Main Lemma - 1
29:59	Main Lemma - 2
30:08	Main Lemma - 3
30:50	Main Lemma - 4
31:07	Rate of convergence - 1
31:08	Rate of convergence - 2
31:11	Rate of convergence - 3
31:12	Rate of convergence - 4
31:13	Rate of convergence - 5
31:53	Rate of convergence - 6
32:15	Mixed accuracy - 1
32:17	Mixed accuracy - 2
32:49	Mixed accuracy - 3
33:02	Mixed accuracy - 4
33:12	Mixed accuracy - 5
34:28	Mixed accuracy - 6
34:31	Mixed accuracy - 7
35:32	Relative accuracy - 1
35:39	Relative accuracy - 2
35:55	Relative accuracy - 3
37:21	Relative accuracy - 4
37:50	Relative accuracy - 5
38:09	Relative accuracy - 6
38:23	Absolute accuracy - 1
38:30	Absolute accuracy - 2
38:34	Absolute accuracy - 3
38:38	Absolute accuracy - 4
39:15	Choice of parameters - 1
39:17	Choice of parameters - 2
39:35	Choice of parameters - 3
39:42	Choice of parameters - 4
42:01	Discussion - 1
42:07	Discussion - 2
42:44	Discussion - 3
42:47	Discussion - 4
42:51	Discussion - 5
43:53	Revival of old questions - 1
44:03	Revival of old questions - 2
44:13	Revival of old questions - 3
44:24	Revival of old questions - 4
44:55	Revival of old questions - 5
45:17	Revival of old questions - 6
45:38	Revival of old questions - 7
46:20	Revival of old questions - 8
46:22	Revival of old questions - 9
46:50	Revival of old questions - 10
46:58	Revival of old questions - 11
47:12	Revival of old questions - 12
47:20	Revival of old questions - 13
47:48	Revival of old questions - 14
48:09	Revival of old questions - 15
48:26	Revival of old questions - 16
48:36	Revival of old questions - 17

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

In this talk we consider a new class of convex optimization problems, which admit faster black-box optimization schemes. For analyzing their rate of convergence, we introduce a notion of mixed accuracy of an approximate solution, which is a convenient generalization of the absolute and relative accuracies. We show that for our problem class, a natural Quasi-Newton method is always faster than the standard gradient method. At the same time, after an appropriate normalization, our results can be extended onto the general convex unconstrained minimization problems.