Dissertation
Efficient algorithms for distributionally robust optimization and its applications
University of Iowa
Doctor of Philosophy (PhD), University of Iowa
Autumn 2023
DOI: 10.25820/etd.006942
Abstract
Distributionally Robust Optimization (DRO) learning aims to enhance model robustness by modeling data uncertainty without prior knowledge of the probability distribution. It has gained significant attention due to its effectiveness in addressing various challenges in machine learning, such as data imbalance, label noise, and fairness. Consequently, the design of scalable and efficient algorithms for distributionally robust learning remains critical. While existing primal-dual algorithms have been extensively studied in the literature, they pose several limitations for DRO optimization. These limitations include 1) per-iteration sample complexity being dependent on data size, limiting DRO's capabilities in large-scale applications; 2) lack of compatibility with sequential data; and 3) a scarcity of comprehensive empirical studies on deep learning applications.
In this thesis, I am working on design principled efficient stochastic optimization algorithms for DRO problems and their applications. From the theoretical perspective, we design
1) an online variance reduction stochastic algorithm, RECOVER (Qi, Guo, Xu, et al., 2021b), to address KL-divergence regularized DRO objective that achieves the optimal sample complexity for the non-convex objectives.
2) a moving average stochastic algorithm, ABSGD (Qi, Xu, Yin, et al. (2022)), to efficiently solve large-scale data imbalanced and label noisy classification tasks, which achieves 1st Place among all submissions based on ResNet50 without extra labeling costs in the Standford iWildcam out-of-distribution competition.
3) a stochastic compositional algorithm, SCDRO (Qi, Lyu, Bai, Yang, et al. (2022)), for solving constrained DRO objective that achieves near-optimal complexity bounds for non-convex losses and optimal complexity for convex losses.
When it comes to applications, besides the comprehensive studies of data imbalanced problems in long-tail image classification, we design a simple and effective DRO framework, (Qi, Yan, Wu, et al. (2020)), to handle the pair imbalance problem in deep metric learning. In addition, as a side work of the data imbalance problem and following the same optimization framework as the DRO problem, we propose a principle technique, (Qi, Luo, Xu, et al. (2021)), for directly optimizing Area Under Precision-Recall Curves (AUPRC) metric for large-scale imbalance medical image problems.
In this thesis, we will commence with an introduction, followed by a presentation of preliminary work on stochastic optimization for Distributionally Robust Optimization (DRO). Subsequently, we will delve into our research contributions, addressing both optimization techniques and their practical applications in the ensuing chapters. Finally, we will synthesize our findings and draw meaningful conclusions.
Details
- Title: Subtitle
- Efficient algorithms for distributionally robust optimization and its applications
- Creators
- Qi Qi
- Contributors
- Tianbao Yang (Advisor)Bijaya Adhikari (Committee Member)Peng P Jiang (Committee Member)Octav O Chipara (Committee Member)Qihang Q Lin (Committee Member)
- Resource Type
- Dissertation
- Degree Awarded
- Doctor of Philosophy (PhD), University of Iowa
- Degree in
- Computer Science
- Date degree season
- Autumn 2023
- Publisher
- University of Iowa
- DOI
- 10.25820/etd.006942
- Number of pages
- xi, 218 pages
- Copyright
- Copyright 2023 Qi Qi
- Language
- English
- Date submitted
- 12/03/2023
- Description illustrations
- Illustrations, tables, graphs, charts
- Description bibliographic
- Includes bibliographical references (pages 194-218).
- Public Abstract (ETD)
Distributionally Robust Optimization (DRO) is a cutting-edge approach in machine learning, enhancing model robustness by accounting for data uncertainty without relying on known probability distributions. Its effectiveness in tackling challenges like data imbalance, label noise, and fairness has attracted significant attention. However, existing algorithms for DRO optimization have limitations that hinder their scalability and efficiency.
This thesis focuses on developing efficient stochastic optimization algorithms for DRO problems and their real-world applications. From a theoretical standpoint, we introduce:
- RECOVER: an online variance reduction stochastic algorithm designed to address KL-divergence regularized DRO objectives, achieving optimal sample complexity for non-convex objectives.
- ABSGD: a moving average stochastic algorithm tailored for efficiently solving largescale data imbalanced and label noisy classification tasks, showcasing success in a prominent competition without incurring extra labeling costs.
- SCDRO: a stochastic compositional algorithm for solving constrained DRO objectives, demonstrating near-optimal complexity bounds for non-convex losses and optimal complexity for convex losses.
In terms of applications, beyond comprehensive studies on data imbalanced problems in long-tail image classification, we present a simple and effective DRO framework for addressing pair imbalance in deep metric learning. Furthermore, as an extension of our work on data imbalance, we propose a technique for directly optimizing the Area Under Precision-Recall Curves (AUPRC) metric for large-scale imbalance medical image problems.
- Academic Unit
- Computer Science
- Record Identifier
- 9984546943702771
Metrics
13 File views/ downloads
48 Record Views