Thesis Defense: Optimization Theory and Machine Learning Practice: Mind the Gap

Thesis Committee:
Prof. Suvrit Sra (Supervisor)
Prof. Ali Jadbabaie (Supervisor)
Prof. Asu Ozdaglar
Prof. Ohad Shamir

Among all different kinds of algorithms, optimization is one of the most fundamental building blocks behind machine learning. Optimization selects a variable in a constraint set to minimize an objective. Such a procedure happens in machine learning applications whenever data determines model parameters. Over the past years, gradient method has become the dominant algorithms in deep learning for its scalability and its natural bound to back propagation in neural networks. However, despite the popularity of gradient-based algorithms, our understanding of them from a theory prospective seems far from sufficient. On one hand, within the current theory framework, most upper and lower bounds are closed, and the theory problems seem solved. On the other hand, the theoretical convergence analysis hardly generates empirically faster algorithms than those found by practitioners. In this thesis, we review the theoretical analysis of gradient methods, and point out the discrepancy between theory and practice. We then provide an explanation for why the mismatch happens and propose some initial solutions by developing theories supported by empirical observations.