Timezone: »

 
Poster
Closing the Gap: Tighter Analysis of Alternating Stochastic Gradient Methods for Bilevel Problems
Tianyi Chen · Yuejiao Sun · Wotao Yin

Thu Dec 09 04:30 PM -- 06:00 PM (PST) @
in Poster Session 7 »
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.
Keywords: Theory · Optimization · Reinforcement Learning and Planning · Machine Learning

Author Information

Tianyi Chen (Rensselaer Polytechnic Institute)
Yuejiao Sun (University of California, Los Angeles)
Wotao Yin (Alibaba US, DAMO Academy)

Related Events (a corresponding poster, oral, or spotlight)

More from the Same Authors