Skip to content

A collection of papers and readings for non-convex optimization

Notifications You must be signed in to change notification settings

cshjin/awesome-nonconvex-optimization

Folders and files

NameName
Last commit message
Last commit date

Latest commit

 

History

4 Commits
 
 

Repository files navigation

Awesome Non-convex Optimization (in order of time)

Last edit: March, 2018

Before 2010s

2004, Nesterov : textbook
Introductory Lectures on Convex Programming Volume: A Basic course
By Yurii Nesterov

2005, Nemirovski : SIOPT
Prox-method with rate of convergence o(1/t) for variational inequalities with lipschitz continuous monotone operators and smooth convex-concave saddle point problems
By Arkadi Nemirovski

2005, Nesterov : Mathematics Programming
Smooth minimization of non-smooth functions
By Yurii Nesterov

2006, Nesterov : Cubic regularization
Cubic regularization of Newton method and its global performance
By Yurii Nesterov, B.T. Polyak

2011

2011, Chambolle-Pock:
A First-Order Primal-Dual Algorithm for Convex Problems with Applications to Imaging
By Antonin Chambolle and Thomas Pock

2012

2012, LeRoux-Schmidt-Bach, : SAG
A stochastic gradient method with an exponential convergence rate for finite training sets
By Nicolas Le Roux, Mark Schmidt, and Francis R. Bach

2012, ShalevShwartz-Zhang, : SDCA
Stochastic Dual Coordinate Ascent Methods for Regularized Loss Minimization
By Shai Shalev-Shwartz and Tong Zhang

2012, Nesterov : RCDM/ACDM
Efficiency of Coordinate Descent Methods on Huge-Scale Optimization Problems
By Yurii Nesterov.

2013

2013, ShalevShwartz-Zhang, : AccSDCA
Accelerated Proximal Stochastic Dual Coordinate Ascent for Regularized Loss Minimization
by Shai Shalev-Shwartz, Tong Zhang

2013, BenTal-Nemirovski,
Lectures on Modern Convex Optimization
By Aharon Ben-Tal and Arkadi Nemirovski

2013, Johnson-Zhang, : SVRG
Accelerating stochastic gradient descent using predictive variance reduction
By Rie Johnson and Tong Zhang

2013, Lee-Sidford, : ACDM (better proof)
Efficient accelerated coordinate descent methods and faster algorithms for solving linear systems
By Yin Tat Lee and Aaron Sidford

2013, Zhang-Mahdavi-Jin,
Linear convergence with condition number independent access of full gradients
By Lijun Zhang, Mehrdad Mahdavi, and Rong Jin.

2013, Mahdavi-Zhang-Jin
Mixed optimization for smooth functions
By Mehrdad Mahdavi, Lijun Zhang, and Rong Jin.

2013, Ghadimi-Lan,
Stochastic First- and Zeroth-order Methods for Nonconvex Stochastic Programming
By Saeed Ghadimi, Guanghui Lan

2014

2014, Lin-Lu-Xiao, : APCG
An Accelerated Proximal Coordinate Gradient Method and its Application to Regularized Empirical Risk Minimization
By Qihang Lin, Zhaosong Lu, Lin Xiao

2014, Defazio-Bach-LacosteJulien, : SAGA
SAGA: A Fast Incremental Gradient Method With Support for Non-Strongly Convex Composite Objectives
By Defazio, A., Bach, F., & Lacoste-Julien, S.

2014, ShalevShwartz-Zhang, : AccSDCA
Accelerated Proximal Stochastic Dual Coordinate Ascent for Regularized Loss Minimization
By Shai Shalev-Shwartz and Tong Zhang

2014, Su-Boyd-Candes,
A differential equation for modeling nesterovs accelerated gradient method: Theory and insights
By Weijie Su, Stephen Boyd, Emmanuel J. Candès

2014, AllenZhu-Orecchia,
Linear Coupling: An Ultimate Unification of Gradient and Mirror Descent
By Zeyuan Allen-Zhu and Lorenzo Orecchia.

2014, Nitanda,
Stochastic proximal gradient descent with acceleration techniques
By Atsushi Nitanda.

2014, Sun-Luo,
Guaranteed Matrix Completion via Non-convex Factorization
By Ruoyu Sun and Zhi-Quan Luo

2015

2015, Zhang-Xiao, : SPDC
Stochastic Primal-Dual Coordinate Method for Regularized Empirical Risk Minimization
By Yuchen Zhang and Lin Xiao.

2015, Lan-Zhou, : RPDG
An optimal randomized incremental gradient method
By Guanghui Lan and Yi Zhou.

2015, Frostig-Ge-Kakade-Sidford, : APPA
Un-regularizing: approximate proximal point and faster stochastic algorithms for empirical risk minimization
By Roy Frostig, Rong Ge, Sham M. Kakade, and Aaron Sidford

2015, Lin-Mairal-Harchaoui, : Catalyst
A universal catalyst for first-order optimization
By Hongzhou Lin, Julien Mairal and Zaid Harchaoui

2015, AllenZhu-Yuan, : SVRG++
Improved SVRG for Non-Strongly-Convex or Sum-of-Non-Convex Objectives
By Zeyuan Allen-Zhu and Yang Yuan

2015, Bubeck-Lee-Singh,
A geometric alternative to Nesterov's accelerated gradient descent
By Sébastien Bubeck, Yin Tat Lee, Mohit Singh

2015, Garber et al, : shift and invert (two papers about the same result)
Faster Eigenvector Computation via Shift-and-Invert Preconditioning
By Dan Garber, Elad Hazan, Chi Jin, Sham M. Kakade, Cameron Musco, Praneeth Netrapalli, Aaron Sidford

2015, Garber-Hazan,
Fast and Simple PCA via Convex Optimization
By Dan Garber and Elad Hazan

2015, Arora-Ge-Ma-Moitra,
Simple, Efficient, and Neural Algorithms for Sparse Coding
By Sanjeev Arora, Rong Ge, Tengyu Ma and Ankur Moitra

2015, Chen-Candès,
Solving Random Quadratic Systems of Equations Is Nearly as Easy as Solving Linear Systems
By Yuxin Chen, Emmanuel J. Candès

2015, ShalevShwartz,
SDCA without Duality
By Shai Shalev-Shwartz

2015, Ge-Huang-Jin-Yuan,
Escaping From Saddle Points --- Online Stochastic Gradient for Tensor Decomposition
By Rong Ge, Furong Huang, Chi Jin, Yang Yuan

2016

2016, AllenZhu-Qu-Richtarik-Yuan, : NUACDM
Even Faster Accelerated Coordinate Descent Using Non-Uniform Sampling
By Zeyuan Allen-Zhu, Zheng Qu, Peter Richtarik and Yang Yuan.

2016b, AllenZhu-Hazan : reduction
Optimal Black-Box Reductions Between Optimization Objectives
By Zeyuan Allen-Zhu and Elad Hazan

2016a, AllenZhu-Hazan : non-convex SVRG
Variance Reduction for Faster Non-Convex Optimization
By Zeyuan Allen-Zhu and Elad Hazan

2016, Wibisono-Wilson-Jordan,
A Variational Perspective on Accelerated Methods in Optimization
By Andre Wibisono, Ashia C. Wilson, Michael I. Jordan

2016, AllenZhu,
Katyusha: The First Direct Acceleration of Stochastic Gradient Methods
By Zeyuan Allen-Zhu

2016, Woodworth-Srebro,
Tight Complexity Bounds for Optimizing Composite Objectives
By Blake Woodworth and Nathan Srebro

2016, Frostig-Musco-Musco-Sidford, : PCR
Principal Component Projection Without Principal Component Analysis
By Roy Frostig, Cameron Musco, Christopher Musco and Aaron Sidford.

2016, AllenZhu-Li, : LazySVD
LazySVD: Even Faster SVD Decomposition Yet Without Agonizing Pain
By Zeyuan Allen-Zhu and Yuanzhi Li.

2016a, Reddi et al.,
Stochastic variance reduction for nonconvex optimization
By Sashank J Reddi, Ahmed Hefny, Suvrit Sra, Barnabas Poczos, and Alex Smola

2016b, Reddi et al.,
Fast incremental method for nonconvex optimization
Sashank J Reddi, Suvrit Sra, Barnabás Póczos, and Alex Smola.

2016c, Reddi et al.,
Fast Stochastic Methods for Nonsmooth Nonconvex Optimization
Sashank J Reddi, Suvrit Sra, Barnabás Póczos, and Alex Smola.

2016, Carmon-Duchi-Hinder-Sidford,
Accelerated Methods for Non-Convex Optimization
By Yair Carmon, John C. Duchi, Oliver Hinder and Aaron Sidford

2016, Agarwal et al.,
Finding Approximate Local Minima Faster Than Gradient Descent
By Naman Agarwal, Zeyuan Allen-Zhu, Brian Bullins, Elad Hazan, Tengyu Ma

2017

2017, Lei-Jordan,
Less than a Single Pass: Stochastically Controlled Stochastic Gradient
By Lihua Lei and Michael I. Jordan.

2017, Lei-Ju-Chen-Jordan,
Nonconvex Finite-Sum Optimization Via SCSG Methods
By Lihua Lei, Cheng Ju, Jianbo Chen, and Michael I. Jordan.

2017, AllenZhu-Li, : PCR
Faster Principal Component Regression and Stable Matrix Chebyshev Approximation
By Zeyuan Allen-Zhu and Yuanzhi Li

2017, Shibagaki-Takeuchi, : mini-batch SPDC
Stochastic primal dual coordinate method with nonuniform sampling based on optimality violations
By Atsushi Shibagaki and Ichiro Takeuchi.

2017, Murata-Suzuki, : DASVRDA
Doubly accelerated stochastic variance reduced dual averaging method for regularized empirical risk minimization
By Tomoya Murata and Taiji Suzuki

2017, Li-Yuan,
Convergence Analysis of Two-layer Neural Networks with ReLU Activation
By Yuanzhi Li and Yang Yuan

2017, AllenZhu,
Natasha: Faster Non-Convex Stochastic Optimization via Strongly Non-Convex Parameter
By Zeyuan Allen-Zhu

2017, Carmon- Duchi-Hinder-Sidford,
"Convex Until Proven Guilty": Dimension-Free Acceleration of Gradient Descent on Non-Convex Functions
By Yair Carmon, John C. Duchi, Oliver Hinder and Aaron Sidford

2017, Jin et al.,
How to Escape Saddle Points Efficiently
By Chi Jin, Rong Ge, Praneeth Netrapalli, Sham M. Kakade, Michael I. Jordan

2017, Zhou-Mertikopoulos-Bambos-Boyd-Glynn
Mirror descent in non-convex stochastic programming
By Zhengyuan Zhou, Panayotis Mertikopoulos, Nicholas Bambos, Stephen Boyd, Peter Glynn

2018

2018, AllenZhu
Natasha2: Faster Non-Convex Optimization Than SGD
By Zeyuan Allen-Zhu

2018, AllenZhu
Katyusha X: Practical Momentum Method for Stochastic Sum-of-Nonconvex Optimization
By Zeyuang Allen-Zhu

2018, AllenZhu-Li
Neon2: Finding Local Minima via First-Order Oracles
By Zeyuang Allen-Zhu, Yuanzhi Li

2018, Yun-Stra-Jadbabaie
Global Optimality Conditions for Deep Neural Networks
By Chulhee Yun, Suvrit Sra, Ali Jadbabaie

2018, Hong-Lee-Razaviyayn
Gradient Primal-Dual Algorithm Converges to Second-Order Stationary Solutions for Nonconvex Distributed Optimization
By Mingyi Hong, Jason D. Lee, Meisam Razaviyayn

2018, Zhang-Aragam-Ravikumar-Xing
DAGs with NO TEARS: Smooth Optimization for Structure Learning
By Xun Zheng, Bryon Aragam, Pradeep Ravikumar, Eric P. Xing

2018, Xu-Jin-Yang: NEON
First-order Stochastic Algorithms for Escaping From Saddle Points in Almost Linear Time
By Yi Xu, Rong Jin, Tianbao Yang

Licenses

License

CC0

To the extent possible under law, Hongwei Jin has waived all copyright and related or neighboring rights to this work.

Releases

No releases published

Packages

No packages published