title: Closing the Gap: Tighter Analysis of Alternating Stochastic Gradient Methods for Bilevel Problems
abstract: Stochastic nested optimization, including stochastic compositional, min-max, and bilevel optimization, is gaining popularity in many machine learning applications. 
  While the three problems share a nested structure, existing works often treat them separately, thus developing problem-specific algorithms and analyses. 
  Among various exciting developments, simple SGD-type updates (potentially on multiple variables) are still prevalent in solving this class of nested problems, but they are believed to have a slower convergence rate than non-nested problems. 
  This paper unifies several SGD-type updates for stochastic nested problems into a single SGD approach that we term ALternating Stochastic gradient dEscenT (ALSET) method. By leveraging the hidden smoothness of the problem, this paper presents a tighter analysis of ALSET for stochastic nested problems. 
  Under the new analysis, to achieve an $\epsilon$-stationary point of the nested problem, it requires ${\cal O}(\epsilon^{-2})$ samples in total. 
  Under certain regularity conditions, applying our results to stochastic compositional, min-max, and reinforcement learning problems either improves or matches the best-known sample complexity in the respective cases. 
  Our results explain why simple SGD-type algorithms in stochastic nested problems all work very well in practice without the need for further modifications. 
authors: Tianyi Chen Yuejiao Sun Wotao Yin
hIndex: Wotao Yin 67