Efficient and Provable Algorithms for Wasserstein Distributionally Robust Optimization in Machine Learning

Wasserstein distance-based distributionally robust optimization (DRO) has received much attention lately due to its ability to provide a robustness interpretation of various learning models. In recent years, it has been shown that various DRO formulations of learning models admit tractable convex reformulations. However, most existing works propose to solve these convex reformulations by standard off-the-shelf solvers (e.g., IPOPT, MOSEK, CPLEX). Nevertheless, these solvers often rely on general-purpose interior-point or nonlinear programming methods, which do not scale well with problem size. Such a state of affairs severely limits the applicability of the DRO approach in large-scale settings.On the other hand, there are very few works that attempt to develop fast iterative methods to solve these DRO problems, which typically possess complicated structures.In this thesis, we take a first step towards resolving the above difficulty by developing two complementary (i.e., deterministic and incremental) efficient and provable first-order algorithms tailored to a class of Wasserstein distance-based distributionally robust risk minimization problems in machine learning. To ensure algorithm efficiency, the hidden structures in the dual formulation are carefully identified, isolated, and fully exploited. Thus, the updates in these algorithms can be computed in a highly efficient manner. Moreover, we show that various learning problems considered in this thesis satisfy a Hölderian growth condition with explicitly determined growth exponents. Consequently, we are able to establish the convergence rates of proposed algorithms under different settings. Our extensive numerical results not only are presented to corroborate our technical results but also demonstrate that our methods are orders of magnitude faster than the state-of-the-art, and the performance gap grows considerably as the problem size increases.以 Wasserstein 距離為度量的分布魯棒優化模型由於能夠對各類機器學習模型提供魯棒性解釋，因此受到了廣泛的關註。近年來，大量工作表明很多分布魯棒優化問題可以轉化成可解的凸優化形式。 然而，這些工作一般使用現成的優化求解器（例如, IPOPT, MOSEK, CPLEX）對其進行求解。通常，這些標準的優化求解器都依賴於通用的內點法或者其他非線性規劃算法，但是這些方法都不能很好地適應問題的大小。這種情況嚴重限制了分布魯棒優化模型在大規模問題中的適用性。另一方面，由於分布魯棒優化問題本身具有的復雜結構，很少有工作嘗試開發快速叠代方法來求解它們。 在本文中，我們邁出了解決上述困難的第一步。 針對機器學習中一類分布魯棒風險最小化問題，本文開發了兩種互補（即確定性和增量性）高效且具有收斂性保證的一階算法。為確保算法效率，本文對對偶形式中的隱藏結構進行仔細甄別，分割以及充分利用。 因此，算法中的更新步驟都可以得以高效計算。此外，本文考慮的各種學習問題滿足具有確定增長指數的霍爾德增長條件。因此，本文能夠對於不同問題形式證明所提算法的收斂速度。最後，本文提供了大量數值實驗結果。 這些結果不僅佐證了本文的理論結果，而且證明了所提方法比最先進的方法快了幾個數量級，並且隨著問題規模的增加，性能差距顯著增加。LI, Jiajin.Ph.D. Chinese University of Hong Kong 2021.Includes bibliographical references (leaves )Abstracts in English and Chinese.Title from PDF title page (viewed on ...