Robust solution schemes for clustering and decision-making problems under uncertainty

This dissertation broadly focuses on developing robust machine learning and optimization approaches for prediction and decision-making problems uncertainty. Specifically, we consider important problems in two different domains, namely robust clustering and data-driven stochastic optimization. The primary focus of the dissertation is to develop novel tractable algorithms for these problems and obtain a theoretical understanding of the algorithms by deriving statistical guarantees on their performances. In the first part of the dissertation, we consider the problem of clustering datasets in the presence of arbitrary outliers. Traditional clustering algorithms such as k-means and spectral clustering are known to perform poorly for datasets contaminated with even a small number of outliers. We develop a provably robust variant of the spectral clustering algorithm that applies a simple rounding scheme to denoise a Gaussian kernel matrix built from the data points and uses vanilla spectral clustering to recover the cluster labels of data points. We analyze the performance of our algorithm under the assumption that the "good" data points are generated from a mixture of sub-gaussians, while the outlier points can come from any arbitrary probability distribution. For this general class of models, we show that the mis-classification error decays at an exponential rate in the signal-to-noise ratio, provided the number of outliers is a small fraction of the inlier points. Surprisingly, this derived error bound matches with the best-known bound for semidefinite programs (SDPs) under the same setting without outliers. We conduct extensive experiments on a variety of simulated and real-world datasets to demonstrate that our algorithm is less sensitive to outliers compared to other state-of-the-art algorithms proposed in the literature. The second part of the dissertation considers the generic stochastic optimization problem in the presence of side or contextual information, which constitutes observable exogenous covariates that alter the distribution of the random problem parameters. For most real-world problems, however, the exact joint probability distribution of the side information covariates and the random problem parameters is unknown, and instead, only the historical data is available. We formulate the risk minimization problem in a data-driven manner based on the Nadaraya Watson kernel regression estimator that serves as a proxy for the true conditional distribution given the side information. Furthermore, we derive out-of-sample performance guarantees for our proposed formulation by leveraging techniques from moderate deviations theory. Our analysis motivates the use of a variance-based regularization scheme, which in general, leads to a non-convex optimization problem. We adopt ideas from distributionally robust optimization (DRO) and develop approximation schemes based on piecewise linear convex loss functions to come up with tractable formulations. We demonstrate the effectiveness of our proposed regularization scheme through numerical experiments for several instances of portfolio optimization and newsvendor problems. In the last part of the dissertation, we develop a novel modeling framework for a class of optimization problems in which operational decisions are altered as a system transitions stochastically between world states. Our framework addresses the problem of minimizing reconfiguration costs associated with changing the operational decisions and ensuring good quality solutions in each individual state. We compare this framework with existing modeling frameworks such as Markov decision processes, stochastic programming, and robust optimization. Finally, we implement our framework to formulate a large real-world communications network problem and present the results.Operations Research and Industrial Engineerin