Dissertation
Provable methods for non-convex min-max optimization and models for interpretable machine learning
University of Iowa
Doctor of Philosophy (PhD), University of Iowa
Summer 2020
DOI: 10.17077/etd.005549
Abstract
The recent innovations in Machine Learning (ML) and its applications in decision-making have made it an integral part of human lives. Our work focuses on two of the major challenges of ML: optimization and interpretability. Optimization methods help compute parameters for an ML model designed to make decisions based on yet-unseen data. Interpretability refers to the ease of understanding the ML model and its decision-making process by humans. Given that the ML models are in use for high stakes decision-making such as parole decisions, diagnosis of life-threatening diseases, and classification of environmental conditions. It is imperative to develop interpretable models, especially for applications that affect human lives directly.
Interestingly many ML problems reduce to fundamental optimization problems. Optimization problems are further classified w.r.t convexity and smoothness, where non-convex (NC) and non-smooth (NS) problems pose the most severe challenges. We focused on min-max (aka saddle$-$point) problems, a special case of NC and NS optimization problems. In chapter 2, we study a family of non-convex min-max problems, whose objective function is weakly convex in the variables of minimization and is concave in the variables of maximization. We propose a proximally guided stochastic subgradient method and a proximally guided stochastic variance-reduced method for the non-smooth and smooth instances, respectively. We analyze the time complexities of the proposed methods for finding a nearly stationary point of the outer minimization problem corresponding to the min-max problem.
The chapter 3 addresses the min-max problem where the maximization is over a finite set of non-convex smooth functions. We define first and second order, non-negative, criticality measures to capture the optimal solution. And we propose a second-order trust-region method to reduce the size of criticality measures below the desired thresholds ( which corresponds to an approximate solution). Also, we analyze the oracle complexity to get the approximate solution.
Many ML models are black-box models such as neural networks and ensembles, which are desirable due to their ability to yield high accuracy results. A black-box model does not reveal its internal workings, and thus, its predictions are hard to understand by humans. Without the understandability and transparency, the predictive models can have severe consequences on our society when used for high-stakes decision-making. Interpretable ML models make the predictions and behavior of ML systems understandable to humans. Some examples are linear regression models, logistic regression, and decision rules/trees. In chapter 4, we propose a novel type of hybrid model for multi-class classification, which utilizes competing linear models to collaborate with an existing black-box model, promoting transparency in the decision-making process. Our proposed hybrid model brings together the interpretable power of linear models and the good predictive performance of the state-of-the-art black-box models. We formulate the training of a MALC model as a convex optimization problem, which optimizes the predictive accuracy and transparency (defined as the percentage of data captured by the linear models) in the objective function. Experiments show that MALC offers more model flexibility for users to balance transparency and accuracy, in contrast to the currently available choice of either a pure black-box model or a pure interpretable model.
Reinforcement learning is an emerging sub-field of ML and Decision-making under uncertainty, where the goal is to learn a policy (set of actionable decisions) for a given task where decisions are taken at each step. For every decision, we get a certain reward, and the goal is to learn a policy that maximizes the total reward. Most current methodologies to learn policy are black-box in nature. In chapter 5, we propose a hybrid approach to determine a policy where the user can control the percentage of interpretable decisions in the learned policy while keeping the desired level of reward.
Details
- Title: Subtitle
- Provable methods for non-convex min-max optimization and models for interpretable machine learning
- Creators
- Hassan Rafique
- Contributors
- Qihang Lin (Advisor)Tong Wang (Committee Member)Weimin Han (Committee Member)Samuel Burer (Committee Member)Tianbao Yang (Committee Member)
- Resource Type
- Dissertation
- Degree Awarded
- Doctor of Philosophy (PhD), University of Iowa
- Degree in
- Applied Mathematical and Computational Sciences
- Date degree season
- Summer 2020
- DOI
- 10.17077/etd.005549
- Publisher
- University of Iowa
- Number of pages
- xv, 134 pages
- Copyright
- Copyright 2020 Hassan Rafique
- Language
- English
- Description illustrations
- color illustrations
- Description bibliographic
- Includes bibliographical references (pages 124-134).
- Public Abstract (ETD)
The recent innovations in Data Science, Machine Learning (ML), and their applications in decision-making have made them an integral part of human lives. Some examples are recommendation systems of Amazon and Netflix, self-driving cars, virtual assistants like Iphone’s Siri. Our work focuses on two of the major challenges of ML: optimization and interpretability.
Optimization methods help compute parameters for an ML model designed to make decisions based on yet-unseen data. With more companies relying on data analytics and quantitative decision making, the role of optimization is instrumental in many industries. In this thesis, we study two variants of important and challenging non-convex min-max optimization problem. We propose solutions to solve these problems and also analyzed how fast these problems can be solved.
Many ML models are black-box models and their predictions are hard to understand by humans. Without the understandability and transparency, these predictive models can have severe consequences when used for high stakes decision-making such as parole decisions and diagnosis of life-threatening diseases. Interpretable ML models make the predictions and behavior of ML systems understandable to humans. In chapter 4 and 5, we present new hybrid models that combine the intuitive power of an interpretable model and the excellent predictive performance of any black-box model. The hybrid model makes it possible to reach some controllable middle ground where understandability and excellent predictive performance are possible.
- Academic Unit
- Interdisciplinary Graduate Program in Applied Mathematical & Computational Sciences
- Record Identifier
- 9983988297002771
Metrics
22 File views/ downloads
159 Record Views