Greedy and Random Quasi-Newton Methods with Faster Explicit Superlinear Convergence
Dec 6, 2021
Speakers
Dachao Lin
Speaker · 0 followers
Haishan Ye
Speaker · 0 followers
Zhihua Zhang
Speaker · 0 followers
About
In this paper we follow Rodomanov and Nesterov’s work to study quasi-Newton methods. We focus on the common SR1 and BFGS quasi-Newton methods to establish better explicit (local) superlinear convergence. First, based on greedy quasi-Newton update which greedily selects the direction so as to maximize a certain measure of progress, we improve the convergence rate to a condition-number-free superlinear convergence rate. Second, based on random quasi-Newton update that selects the direction randomly from a spherically symmetric distribution, we show the same superlinear convergence rate established as above. Our analysis is closely related to the approximation of a given Hessian matrix, unconstrained quadratic objective, as well as the general strongly convex, smooth and strongly self-concordant functions.In this paper we follow Rodomanov and Nesterov’s work to study quasi-Newton methods. We focus on the common SR1 and BFGS quasi-Newton methods to establish better explicit (local) superlinear convergence. First, based on greedy quasi-Newton update which greedily selects the direction so as to maximize a certain measure of progress, we improve the convergence rate to a condition-number-free superlinear convergence rate. Second, based on random quasi-Newton update that selects the direction randoml…
Organizer
NeurIPS 2021
Account · 1.9k followers
About NeurIPS 2021
Neural Information Processing Systems (NeurIPS) is a multi-track machine learning and computational neuroscience conference that includes invited talks, demonstrations, symposia and oral and poster presentations of refereed papers. Following the conference, there are workshops which provide a less formal setting.
Like the format? Trust SlidesLive to capture your next event!
Professional recording and live streaming, delivered globally.
Sharing
Recommended Videos
Presentations on similar topic, category or speaker
FLoRA: Single-shot Hyper-parameter Optimization for Federated Learning
Watch later
Yi Zhou, …
Total of 0 viewers voted for saving the presentation to eternal vault which is 0.0%
A Law of Iterated Logarithm for Multi-Agent Reinforcement Learning
Watch later
Gugan Thoppe, …
Total of 0 viewers voted for saving the presentation to eternal vault which is 0.0%
Controllable and Compositional Generation with Latent-Space Energy-Based Models
Watch later
Weili Nie, …
Total of 0 viewers voted for saving the presentation to eternal vault which is 0.0%
Exploiting Proximity Search and Easy Examples to Select Rare Events
Watch later
Daniel Kang, …
Total of 0 viewers voted for saving the presentation to eternal vault which is 0.0%
Near-optimal Offline and Streaming Algorithms for Learning Non-Linear Dynamical Systems
Watch later
Prateek Jain, …
Total of 0 viewers voted for saving the presentation to eternal vault which is 0.0%
Oral Session 3: Theory
Watch later
Total of 0 viewers voted for saving the presentation to eternal vault which is 0.0%