Description
To answer above question, this thesis focuses on four concrete and fundamental questions: - In nonconvex optimization, can (stochastic) gradient descent or its variants escape saddle points efficiently? - Is gradient descent with momentum provably faster than gradient descent in the general nonconvex setting? - In nonconvex-nonconcave minmax optimization, what is a proper definition of local optima and is gradient descent ascent game-theoretically meaningful? - In reinforcement learning, is Q-learning sample efficient?
This thesis provides the first line of provably positive answers to all above questions. In particular, this thesis will show that although the standard versions of these classical algorithms do not enjoy good theoretical properties in the worst case, simple modifications are sufficient to grant them desirable behaviors, which explain the underlying mechanisms behind their favorable performance in practice.