OPTIMIZATION AND LEARNING UNDER UNCERTAINTY - A UNIFIED ROBUSTNESS PERSPECTIVE

Abstract

Robust decision making is ubiquitous in real-world applications in machine learning, operations research and finance, etc., due to the existence of uncertainty and noise coming from measurement errors or malicious attacking. This thesis first investigates the computational aspects of distributionally robust chance constrained optimization with non-linear uncertainties, and apply this technique in machine learning both theoretically and algorithmically, i.e., we provide a new robustness interpretation of Lasso-like algorithms and regularized SVMs. Second, we consider optimization problems with unknown parameters and tackle them from a dynamic perspective: the decision maker can make a tentative decision, collect the corresponding feedbacks, and fine tune the decision. To numerically solve them, we develop and analyze two algorithms based on the epsilon-decreasing strategy and the upper confidence bound strategy, respectively. Finally, we study the dimension reduction problem with noisy and outlying observation, and propose three outlier-robust principal component analysis algorithms with solid theoretical performance guarantees.