Timezone: »

 
Poster
Sampling without Replacement Leads to Faster Rates in Finite-Sum Minimax Optimization
Aniket Das · Bernhard Schölkopf · Michael Muehlebach

Wed Nov 30 02:00 PM -- 04:00 PM (PST) @ Hall J #310
in Poster Session 4 »

We analyze the convergence rates of stochastic gradient algorithms for smooth finite-sum minimax optimization and show that, for many such algorithms, sampling the data points \emph{without replacement} leads to faster convergence compared to sampling with replacement. For the smooth and strongly convex-strongly concave setting, we consider gradient descent ascent and the proximal point method, and present a unified analysis of two popular without-replacement sampling strategies, namely \emph{Random Reshuffling} (RR), which shuffles the data every epoch, and \emph{Single Shuffling} or \emph{Shuffle Once} (SO), which shuffles only at the beginning. We obtain tight convergence rates for RR and SO and demonstrate that these strategies lead to faster convergence than uniform sampling. Moving beyond convexity, we obtain similar results for smooth nonconvex-nonconcave objectives satisfying a two-sided Polyak-\L{}ojasiewicz inequality. Finally, we demonstrate that our techniques are general enough to analyze the effect of \emph{data-ordering attacks}, where an adversary manipulates the order in which data points are supplied to the optimizer. Our analysis also recovers tight rates for the \emph{incremental gradient} method, where the data points are not shuffled at all.

Keywords: minimax optimization · proximal point method · Shuffle Once · Incremental Gradient · Smooth Games · Sampling without Replacement · Nonconvex-Nonconcave Minimax Optimization · Gradient Descent Ascent · Alternating Gradient Descent Ascent · Random Reshuffling

Author Information

Aniket Das (Indian Institute of Technology Kanpur)
Bernhard Schölkopf (MPI for Intelligent Systems, Tübingen)

Bernhard Scholkopf received degrees in mathematics (London) and physics (Tubingen), and a doctorate in computer science from the Technical University Berlin. He has researched at AT&T Bell Labs, at GMD FIRST, Berlin, at the Australian National University, Canberra, and at Microsoft Research Cambridge (UK). In 2001, he was appointed scientific member of the Max Planck Society and director at the MPI for Biological Cybernetics; in 2010 he founded the Max Planck Institute for Intelligent Systems. For further information, see www.kyb.tuebingen.mpg.de/~bs.

Michael Muehlebach (Max-Planck Institute)

More from the Same Authors