Beyond Worst-Case Analysis of Optimization in the Era of Machine Learning

Worst-case analysis (WCA) has been the dominant tool for understanding the performance of the lion share of algorithmic arsenal of theoretical computer science. While WCA has provided us a thorough picture for a variety of problems over the last few decades, the advent of Machine Learn- ing era renewed our interest in several important optimization problems whose actual complexity have been elusive for empirical and real-world instances. More interestingly, while state-of-the- art ML models become deeper, larger in scale, sequential and highly nonconvex, the backbone of modern learning algorithms are simple algorithms such as Local Search, Gradient Descent and Follow The Leader variations (in the case of multi-agent tasks). Thus, a basic question endures: Why do simple algorithms work so well even in these challenging settings? A rapidly developing recent line of research, the so-called beyond worst-case analysis of algo- rithms (BWCA), aims to bridge this gap between theory and practice considering the design and analysis of algorithms using more realistic models or using natural structural properties. In this the- sis, we continue the line of work of BWCA by making contributions in several areas. Specifically, we focus on four main problems and models: 1. In combinatorial optimization, can simple flip local search methods compute local optima efficiently? 2. In continuous optimization, are the gradients necessary to compute efficiently local optima in the general nonconvex setting? 3. In multi-agent optimization, what is the computational complexity of generalized Nash Equi- libria and how simple dynamics behave on them? 4. In the special case of nonconvex-nonconcave minmax optimization, are there rich classes of ML well-motivated games with an effectively unique game theoretic solution that is selected by standard optimization techniques (e.g gradient descent) ? Leveraging machinery like the celebrated Smoothed Analysis of Spielman and Tang and the widely studied Lyapunov’s Stability Analysis, in this thesis we 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