Fetching the paper…
Reading the bibliography…
We present a randomized primal-dual algorithm that solves the problem $\min_{x} \max_{y} y^\top A x$ to additive error $\epsilon$ in time $\mathrm{nnz}(A) + \sqrt{\mathrm{nnz}(A)n}/\epsilon$, for matrix $A$ with larger dimension $n$ and $\mathrm{nnz}(A)$ nonzero entries.
Zur theorie der gesellschaftsspiele
J. V. Neumann · 1928
Earlier work this paper cites.
Linear Programming and Extensions
G. B. Dantzig · 1953
Earlier work this paper cites.
Problem Complexity and Method Efficiency in Optimization
A. Nemirovsky and D. Yudin · 1983
Earlier work this paper cites.
Perceptrons—an introduction to computational geometry
M. Minsky and S. Papert · 1987
Earlier work this paper cites.
A linear algorithm for generating random numbers with a given distribution
M. D. Vose · 1991
Earlier work this paper cites.
Nonlinear proximal point algorithms using Bregman functions, with applications to convex programming
J. Eckstein · 1993
Earlier work this paper cites.
Convex Analysis and Minimization Algorithms I
J. Hiriart-Urruty and C. Lemaréchal · 1993
Earlier work this paper cites.
A sublinear-time randomized approximation algorithm for matrix games
M. D. Grigoriadis and L. G. Khachiyan · 1995
Earlier work this paper cites.
Prox-method with rate of convergence O ( 1 / t ) {O}(1/t) for variational inequalities with lipschitz continuous monotone operators and smooth convex-concave saddle point problems
A. Nemirovski · 2004
Earlier work this paper cites.
Dual extrapolation and its applications to solving variational inequalities and related problems
Y. Nesterov · 2007
Earlier work this paper cites.
Robust stochastic approximation approach to stochastic programming
A. Nemirovski, A. Juditsky, G. Lan, and A. Shapiro · 2009
Earlier work this paper cites.
A randomized Kaczmarz algorithm with exponential convergence
T. Strohmer and R. Vershynin · 2009
Earlier work this paper cites.
Sublinear optimization for machine learning
K. L. Clarkson, E. Hazan, and D. P. Woodruff · 2010
Earlier work this paper cites.
Online learning and online convex optimization
S. Shalev-Shwartz et al · 2012
Earlier work this paper cites.
Accelerating stochastic gradient descent using predictive variance reduction
R. Johnson and T. Zhang · 2013
Earlier work this paper cites.
Stochastic dual coordinate ascent methods for regularized loss
S. Shalev-Shwartz and T. Zhang · 2013
Earlier work this paper cites.
Generative adversarial nets
I. J. Goodfellow, J. Pouget-Abadie, M. Mirza, B. Xu, D. Warde-Farley, S. Ozair, A. C. Courville, and Y. Bengio · 2014
Cited alongside, same era.
A proximal stochastic gradient method with progressive variance reduction
L. Xiao and T. Zhang · 2014
Cited alongside, same era.
A simple algorithm for a class of nonsmooth convex-concave saddle-point problems
Y. Drori, S. Sabach, and M. Teboulle · 2015
Cited alongside, same era.
Un-regularizing: approximate proximal point and faster stochastic algorithms for empirical risk minimization
R. Frostig, R. Ge, S. Kakade, and A. Sidford · 2015
Cited alongside, same era.
Efficient inverse maintenance and faster algorithms for linear programming
Y. T. Lee and A. Sidford · 2015
Cited alongside, same era.
A universal catalyst for first-order optimization
H. Lin, J. Mairal, and Z. Harchaoui · 2015
Area-convexity, ℓ ∞ \ell_{\infty} regularization, and undirected multicommodity flow
J. Sherman · 2017
Later among the works it cites.
Bregman divergence for stochastic variance reduction: Saddle-point and adversarial prediction
Z. Shi, X. Zhang, and Y. Yu · 2017
Later among the works it cites.
Optimization methods for large-scale machine learning
L. Bottou, F. E. Curtis, and J. Nocedal · 2018
Later among the works it cites.
Solving linear programs in the current matrix multiplication time
M. B. Cohen, Y. T. Lee, and Z. Song · 2018
Later among the works it cites.
SPIDER: near-optimal non-convex optimization via stochastic path-integrated differential estimator
C. Fang, C. J. Li, Z. Lin, and T. Zhang · 2018
Later among the works it cites.
alphaXiv searches the wider corpus for related work and actual follow-ups.
alphaXiv is searching for related work…
Cited alongside, same era.
Variance reduction for faster non-convex optimization
Z. Allen-Zhu and E. Hazan · 2016
Cited alongside, same era.
Stochastic variance reduction methods for saddle-point problems
P. Balamurugan and F. R. Bach · 2016
Cited alongside, same era.
Stochastic variance reduction for nonconvex optimization
S. J. Reddi, A. Hefny, S. Sra, B. Poczos, and A. Smola · 2016
Cited alongside, same era.
Accelerated proximal stochastic dual coordinate ascent for regularized loss minimization
S. Shalev-Shwartz and T. Zhang · 2016
Cited alongside, same era.
Tight complexity bounds for optimizing composite objectives
B. E. Woodworth and N. Srebro · 2016
Cited alongside, same era.
Katyusha: the first direct acceleration of stochastic gradient methods
Z. Allen-Zhu · 2017
Cited alongside, same era.
H. Lu, R. M. Freund, and Y. Nesterov · 2018
Later among the works it cites.
Towards deep learning models resistant to adversarial attacks
A. Madry, A. Makelov, L. Schmidt, D. Tsipras, and A. Vladu · 2018
Later among the works it cites.
Coordinate methods for accelerating ℓ ∞ \ell_{\infty} regression and faster approximate maximum flow
A. Sidford and K. Tian · 2018
Later among the works it cites.
Stochastic nested variance reduced gradient descent for nonconvex optimization
D. Zhou, P. Xu, and Q. Gu · 2018
Later among the works it cites.
Reducing noise in GAN training with variance reduced extragradient
T. Chavdarova, G. Gidel, F. Fleuret, and S. Lacoste-Julien · 2019
Closest in time.
Training GANs with optimism
C. Daskalakis, A. Ilyas, V. Syrgkanis, and H. Zeng · 2019
Closest in time.
Minmax optimization: Stable limit points of gradient descent ascent are locally optimal
C. Jin, P. Netrapalli, and M. I. Jordan · 2019
Closest in time.
Mirror descent in saddle-point problems: Going the extra (gradient) mile
P. Mertikopoulos, H. Zenati, B. Lecouat, C.-S. Foo, V. Chandrasekhar, and G. Piliouras · 2019
Closest in time.
Revisiting stochastic extragradient
K. Mishchenko, D. Kovalev, E. Shulgin, P. Richtárik, and Y. Malitsky · 2019
Closest in time.
A. Mokhtari, A. Ozdaglar, and S. Pattathil · 2019
Closest in time.