Fetching the paper…
Reading the bibliography…
In this paper, we study the lower complexity bounds for finite-sum optimization problems, where the objective is the average of $n$ individual component functions.
A unified analysis of extra-gradient and optimistic gradient methods for saddle point problems: Proximal point approach
Aryan Mokhtari, Asuman Ozdaglar, and Sarath Pattathil · 1901
Earlier work this paper cites.
Proximal point approximations achieving a convergence rate of O ( 1 / k ) {O}(1/k) for smooth convex-concave saddle point problems: Optimistic gradient and extra-gradient methods
Aryan Mokhtari, Asuman Ozdaglar, and Sarath Pattathil · 1906
Earlier work this paper cites.
A support vector method for multivariate performance measures
Thorsten Joachims · 2005
Earlier work this paper cites.
Robust optimization , volume 28
Aharon Ben-Tal, Laurent El Ghaoui, and Arkadi Nemirovski · 2009
Earlier work this paper cites.
A first-order primal-dual algorithm for convex problems with applications to imaging
Antonin Chambolle and Thomas Pock · 2011
Earlier work this paper cites.
Accelerating stochastic gradient descent using predictive variance reduction
Rie Johnson and Tong Zhang · 2013
Earlier work this paper cites.
Introductory lectures on convex optimization: A basic course , volume 87
Yurii Nesterov · 2013
Earlier work this paper cites.
Stochastic dual coordinate ascent methods for regularized loss minimization
Shai Shalev-Shwartz and Tong Zhang · 2013
Earlier work this paper cites.
SAGA: A fast incremental gradient method with support for non-strongly convex composite objectives
Aaron Defazio, Francis Bach, and Simon Lacoste-Julien · 2014
Earlier work this paper cites.
A proximal stochastic gradient method with progressive variance reduction
Lin Xiao and Tong Zhang · 2014
Earlier work this paper cites.
A lower bound for the optimization of finite sums
Alekh Agarwal and Leon Bottou · 2015
Earlier work this paper cites.
Variance reduced stochastic gradient descent with neighbors
Thomas Hofmann, Aurelien Lucchi, Simon Lacoste-Julien, and Brian McWilliams · 2015
Earlier work this paper cites.
Dimension-free iteration complexity of finite sum optimization problems
Yossi Arjevani and Ohad Shamir · 2016
Earlier work this paper cites.
On the ergodic convergence rates of a first-order primal–dual algorithm
Antonin Chambolle and Thomas Pock · 2016
Earlier work this paper cites.
A simple practical accelerated method for finite sums
Aaron Defazio · 2016
Earlier work this paper cites.
Stochastic variance reduction methods for saddle-point problems
Balamurugan Palaniappan and Francis Bach · 2016
Earlier work this paper cites.
Sdca without duality, regularization, and individual convexity
Shai Shalev-Shwartz · 2016
Earlier work this paper cites.
Tight complexity bounds for optimizing composite objectives
Blake Woodworth and Nathan Srebro · 2016
Earlier work this paper cites.
Stochastic online AUC maximization
Yiming Ying, Longyin Wen, and Siwei Lyu · 2016
Earlier work this paper cites.
Finding approximate local minima faster than gradient descent
Naman Agarwal, Zeyuan Allen-Zhu, Brian Bullins, Elad Hazan, and Tengyu Ma · 2017
Earlier work this paper cites.
Stochastic variance reduction methods for policy evaluation
Simon S. Du, Jianshu Chen, Lihong Li, Lin Xiao, and Dengyong Zhou · 2017
Cited alongside, same era.
An optimal randomized incremental gradient method
Guanghui Lan and Yi Zhou · 2017
Cited alongside, same era.
Sarah: A novel method for machine learning problems using stochastic recursive gradient
Lam M Nguyen, Jie Liu, Katya Scheinberg, and Martin Takáč · 2017
Cited alongside, same era.
Stochastic primal-dual coordinate method for regularized empirical risk minimization
Yuchen Zhang and Lin Xiao · 2017
Cited alongside, same era.
Katyusha X: Practical momentum method for stochastic sum-of-nonconvex optimization
Zeyuan Allen-Zhu · 2018
Cited alongside, same era.
Accelerated methods for nonconvex optimization
Yair Carmon, John C Duchi, Oliver Hinder, and Aaron Sidford · 2018
Efficient algorithms for smooth minimax optimization
Kiran K. Thekumparampil, Prateek Jain, Praneeth Netrapalli, and Sewoong Oh · 2019
Later among the works it cites.
Yan Yan, Yi Xu, Qihang Lin, Lijun Zhang, and Tianbao Yang · 2019
Later among the works it cites.
On lower iteration complexity bounds for the saddle point problems
Junyu Zhang, Mingyi Hong, and Shuzhong Zhang · 2019
Later among the works it cites.
Lower bounds for smooth nonconvex finite-sum optimization
Dongruo Zhou and Quanquan Gu · 2019
Later among the works it cites.
Coordinate methods for matrix games
Yair Carmon, Yujia Jin, Aaron Sidford, and Kevin Tian · 2020
Later among the works it cites.
Don’t jump through hoops and remove those loops: Svrg and katyusha are better without the outer loop
alphaXiv searches the wider corpus for related work and actual follow-ups.
alphaXiv is searching for related work…
Cited alongside, same era.
SBEED: Convergent reinforcement learning with nonlinear function approximation
Bo Dai, Albert Shaw, Lihong Li, Lin Xiao, Niao He, Zhen Liu, Jianshu Chen, and Le Song · 2018
Cited alongside, same era.
SPIDER: Near-optimal non-convex optimization via stochastic path-integrated differential estimator
Cong Fang, Chris Junchi Li, Zhouchen Lin, and Tong Zhang · 2018
Cited alongside, same era.
Breaking the span assumption yields fast finite-sum minimization
Robert Hannah, Yanli Liu, Daniel O’Connor, and Wotao Yin · 2018
Cited alongside, same era.
Catalyst acceleration for first-order convex optimization: from theory to practice
Hongzhou Lin, Julien Mairal, and Zaid Harchaoui · 2018
Cited alongside, same era.
Lower complexity bounds of first-order methods for convex-concave bilinear saddle-point problems
Yuyuan Ouyang and Yangyang Xu · 2018
Cited alongside, same era.
Non-convex min-max optimization: Provable algorithms and applications in machine learning
Hassan Rafique, Mingrui Liu, Qihang Lin, and Tianbao Yang · 2018
Cited alongside, same era.
Dmitry Kovalev, Samuel Horváth, and Peter Richtárik · 2020
Later among the works it cites.
On the convergence of sarah and beyond
Bingcong Li, Meng Ma, and Georgios B Giannakis · 2020
Later among the works it cites.
Near-optimal algorithms for minimax optimization
Tianyi Lin, Chi Jin, and Michael I Jordan · 2020
Later among the works it cites.
Stochastic hamiltonian gradient methods for smooth games
Nicolas Loizou, Hugo Berard, Alexia Jolicoeur-Martineau, Pascal Vincent, Simon Lacoste-Julien, and Ioannis Mitliagkas · 2020
Later among the works it cites.
Stochastic recursive gradient descent ascent for stochastic nonconvex-strongly-concave minimax problems
Luo Luo, Haishan Ye, Zhichao Huang, and Tong Zhang · 2020
Later among the works it cites.
Efficient search of first-order nash equilibria in nonconvex-concave smooth min-max problems
Dmitrii M Ostrovskii, Andrew Lowy, and Meisam Razaviyayn · 2020
Later among the works it cites.
A catalyst framework for minimax optimization
Junchi Yang, Siqi Zhang, Negar Kiyavash, and Niao He · 2020
Later among the works it cites.
Anita: An optimal loopless accelerated variance-reduced gradient method
Zhize Li · 2021
Closest in time.
Page: A simple and optimal probabilistic gradient estimator for nonconvex optimization
Zhize Li, Hongyan Bao, Xiangliang Zhang, and Peter Richtárik · 2021
Closest in time.
Near optimal stochastic algorithms for finite-sum unbalanced convex-concave minimax optimization
Luo Luo, Guangzeng Xie, Tong Zhang, and Zhihua Zhang · 2021
Closest in time.
L-svrg and l-katyusha with arbitrary sampling
Xun Qian, Zheng Qu, and Peter Richtárik · 2021
Closest in time.
The complexity of nonconvex-strongly-concave minimax optimization
Siqi Zhang, Junchi Yang, Cristóbal Guzmán, Negar Kiyavash, and Niao He · 2021
Closest in time.
Stochastic variance reduction for variational inequality methods
Ahmet Alacaoglu and Yura Malitsky · 2022
Closest in time.
Stochastic gradient descent-ascent: Unified theory and new efficient methods
Aleksandr Beznosikov, Eduard Gorbunov, Hugo Berard, and Nicolas Loizou · 2022
Closest in time.