Timezone: »
Poster
The Physical Systems Behind Optimization Algorithms
Lin Yang · Raman Arora · Vladimir braverman · Tuo Zhao
We use differential equations based approaches to provide some {\it \textbf{physics}} insights into analyzing the dynamics of popular optimization algorithms in machine learning. In particular, we study gradient descent, proximal gradient descent, coordinate gradient descent, proximal coordinate gradient, and Newton's methods as well as their Nesterov's accelerated variants in a unified framework motivated by a natural connection of optimization algorithms to physical systems. Our analysis is applicable to more general algorithms and optimization problems {\it \textbf{beyond}} convexity and strong convexity, e.g. Polyak-\L ojasiewicz and error bound conditions (possibly nonconvex).
Author Information
Lin Yang (Princeton University)
Raman Arora (Johns Hopkins University)
Vladimir braverman (Johns Hopkins University)
Tuo Zhao (Georgia Tech)
More from the Same Authors
-
2020 Poster: Adversarial Robustness of Supervised Sparse Coding »
Jeremias Sulam · Ramchandran Muthukumar · Raman Arora -
2020 Poster: On Convergence and Generalization of Dropout Training »
Poorya Mianjy · Raman Arora -
2019 Poster: Efficient Convex Relaxations for Streaming PCA »
Raman Arora · Teodor Vanislavov Marinov -
2019 Poster: On Differentially Private Graph Sparsification and Applications »
Raman Arora · Jalaj Upadhyay -
2019 Poster: Bandits with Feedback Graphs and Switching Costs »
Raman Arora · Teodor Vanislavov Marinov · Mehryar Mohri -
2019 Poster: Meta Learning with Relational Information for Short Sequences »
Yujia Xie · Haoming Jiang · Feng Liu · Tuo Zhao · Hongyuan Zha -
2019 Poster: Efficient Approximation of Deep ReLU Networks for Functions on Low Dimensional Manifolds »
Minshuo Chen · Haoming Jiang · Wenjing Liao · Tuo Zhao -
2019 Poster: Communication-efficient Distributed SGD with Sketching »
Nikita Ivkin · Daniel Rothchild · Enayat Ullah · Vladimir braverman · Ion Stoica · Raman Arora -
2018 Poster: Dimensionality Reduction for Stationary Time Series via Stochastic Nonconvex Optimization »
Minshuo Chen · Lin Yang · Mengdi Wang · Tuo Zhao -
2018 Poster: Policy Regret in Repeated Games »
Raman Arora · Michael Dinitz · Teodor Vanislavov Marinov · Mehryar Mohri -
2018 Poster: Streaming Kernel PCA with $\tilde{O}(\sqrt{n})$ Random Features »
Enayat Ullah · Poorya Mianjy · Teodor Vanislavov Marinov · Raman Arora -
2018 Poster: Towards Understanding Acceleration Tradeoff between Momentum and Asynchrony in Nonconvex Stochastic Optimization »
Tianyi Liu · Shiyang Li · Jianping Shi · Enlu Zhou · Tuo Zhao -
2018 Poster: Differentially Private Robust Low-Rank Approximation »
Raman Arora · Vladimir braverman · Jalaj Upadhyay -
2018 Poster: Near-Optimal Time and Sample Complexities for Solving Markov Decision Processes with a Generative Model »
Aaron Sidford · Mengdi Wang · Xian Wu · Lin Yang · Yinyu Ye -
2017 Poster: Deep Hyperspherical Learning »
Weiyang Liu · Yan-Ming Zhang · Xingguo Li · Zhiding Yu · Bo Dai · Tuo Zhao · Le Song -
2017 Poster: Stochastic Approximation for Canonical Correlation Analysis »
Raman Arora · Teodor Vanislavov Marinov · Poorya Mianjy · Nati Srebro -
2017 Spotlight: Deep Hyperspherical Learning »
Weiyang Liu · Yan-Ming Zhang · Xingguo Li · Zhiding Yu · Bo Dai · Tuo Zhao · Le Song -
2017 Poster: Parametric Simplex Method for Sparse Learning »
Haotian Pang · Han Liu · Robert J Vanderbei · Tuo Zhao -
2017 Poster: On Quadratic Convergence of DC Proximal Newton Algorithm in Nonconvex Sparse Learning »
Xingguo Li · Lin Yang · Jason Ge · Jarvis Haupt · Tong Zhang · Tuo Zhao -
2016 Poster: Disease Trajectory Maps »
Peter Schulam · Raman Arora -
2014 Poster: Accelerated Mini-batch Randomized Block Coordinate Descent Method »
Tuo Zhao · Mo Yu · Yiming Wang · Raman Arora · Han Liu -
2013 Poster: Stochastic Optimization of PCA with Capped MSG »
Raman Arora · Andrew Cotter · Nati Srebro -
2009 Poster: On Learning Rotations »
Raman Arora -
2009 Spotlight: On Learning Rotations »
Raman Arora