Poster Session and Reception

Tuesday, June 18, 2019 - 4:30pm - 6:00pm
Lind 400
  • Non-Convex Min-Max Optimization : Algorithms and Applications in Machine Learning

    The min-max problem, also known as the saddle point problem, is a class
    of optimization problems in which we minimize and maximize two subsets
    of variables simultaneously. This class of problems can be used to
    formulate a wide range of machine learning (ML) problems (e.g
    adversarial learning). Despite its popularity, existing theory for this
    class has been mainly developed for problems with certain special {\it
    convex-concave} structure. Therefore, it cannot be used to guide the
    algorithm design for many interesting problems in ML, where some kind
    of non-convexity often arises. In this work, we consider a general
    block-wise one-sided non-convex min-max problem, in which the
    minimization problem consists of multiple blocks and is non-convex,
    while the maximization problem is (strongly) concave. We propose a class
    of simple algorithms named Hybrid Block Successive Approximation
    (HiBSA), which alternatingly performs gradient descent-type steps for
    the minimization blocks and one gradient ascent-type step for the
    maximization problem. A key element in the proposed algorithm is the
    introduction of certain properly designed regularization and penalty
    terms, which are used to stabilize the algorithm and ensure
    convergence. For the first time, we show that such simple alternating
    min-max algorithms converge to first-order stationary solutions, with
    quantifiable global rates. To validate the efficiency of the proposed
    algorithms we conduct numerical tests on the robust learning problem
    over multiple domains.
  • The Cost of a Reductions Approach to Private Fair Optimization
    Daniel Alabi (Harvard University)
    The widespread adoption of machine learning by and for non-experts has brought issues of fairness, accountability, and transparency to the frontiers of advancements in artificial intelligence. Concerns of algorithmic fairness have been accompanied by new models and algorithms to make state-of-the-art and existing systems more fair. But some of these new models don't adhere to other ethical standards such as the societal need to ensure the privacy of the data used to create the models. We focus on a reductions approach to fair optimization and learning where a black-box optimizer is used to learn a fair model for classification or regression and explore the creation of such fair models that adhere to data privacy guarantees (specifically differential privacy). For this approach, we consider two suites of use cases: the first is for optimizing convex performance measures of the confusion matrix
    (such as G-mean and H-mean); the second is for satisfying statistical definitions of algorithmic fairness (such as equalized odds, demographic parity, and the gini index of inequality).

    We abstract the reductions approach to fair optimization as the constrained group-objective optimization problem where we aim to optimize an objective that is a function of losses of individual groups, subject to some constraints. We present two differentially private algorithms: an $(\epsilon, 0)$ exponential sampling algorithm and an $(\epsilon, \delta)$ projection-free algorithm that uses a linear optimizer to incrementally move toward the best decision. We analyze the privacy and utility guarantees of these empirical risk minimization algorithms. Compared to a previous method for ensuring differential privacy subject to a relaxed form of the equalized odds fairness constraint, the projection-free differentially private algorithm provides asymptotically
    better sample complexity guarantees. Finally, we show an algorithm-agnostic lower bound on the accuracy of any solution to the problem of $(\epsilon, 0)$ or $(\epsilon, \delta)$ private constrained group-objective optimization.
  • Metric Learning for Individual Fairness
    Christina Ilvento (Harvard University)
    There has been much discussion recently about how fairness should be measured or enforced in
    classification. Individual Fairness, which requires that similar individuals be treated similarly, is a
    highly appealing definition as it gives strong guarantees on treatment of individuals. Unfortunately,
    the need for a task-specific similarity metric has prevented its use in practice. In this work, we
    propose a solution to the problem of approximating a metric for Individual Fairness based on
    human judgments. Our model assumes access to a human fairness arbiter who is free of explicit
    biases and possesses sufficient domain knowledge to evaluate similarity. Our contributions include
    definitions for metric approximation relevant for Individual Fairness, constructions for
    approximations from a limited number of realistic queries to the arbiter on a sample of individuals,
    and learning procedures to construct hypotheses for metric approximations which generalize to
    unseen samples under certain assumptions of learnability of distance threshold functions.
  • Graph Convolutional Neural Network via Scattering
    Dongmian Zou (University of Minnesota, Twin Cities)
    We construct a convolutional neural network on graphs by generalizing the scattering transform. The construction is based on graph wavelets. Any feature generated by such a network is approximately invariant to permutations and stable to signal or graph manipulations. Numerical results show that the graph scattering transform works effectively for classification and community detection problems. Generative graphmodels based on scattering also show competitive results.
  • Effects of Affirmative Action
    Juba Ziani (California Institute of Technology)
    We study a two-stage model, in which students are 1) admitted to college on the basis of an entrance exam which is a noisy signal about their qualifications (type), and then 2) those students who were admitted to college can be hired by
    an employer as a function of their college grades, which are an independently drawn noisy signal of their type. Students are drawn from one of two populations, which might have different type distributions. We assume that the employer at the end of the pipeline is rational, in the sense that it computes a posterior distribution on student type conditional on all information that it has available (college admissions, grades, and group membership), and makes a decision based on
    posterior expectation. We then study what kinds of fairness goals can be achieved by the college by setting its admissions rule and grading policy. For example, the college might have the goal of guaranteeing equal opportunity across populations: that the probability of passing through the pipeline and being hired by the employer should be
    independent of group membership, conditioned on type. Alternately, the college might have the goal of incentivizing the employer to have a group blind hiring rule. We show that both goals can be achieved when the college does not report grades. On the other hand, we show that under reasonable conditions, these goals are impossible to achieve even in isolation when the college uses an (even minimally) informative grading policy.
  • Static DNN Analysis for Robustness
    Shibbir Ahmed (Iowa State University)Rangeet Pan (Iowa State University)
    Despite numerous attempts to defend deep learning based image classifiers, they remain susceptible to the adversarial attacks. This paper proposes a technique to identify susceptible classes, those classes that are more easily subverted. To identify the susceptible classes we use distance-based measures and apply them on a trained model. Based on the distance among original classes, we create mapping among original classes and adversarial classes that helps to reduce the randomness of a model to a significant amount in an adversarial setting. We analyze the high dimensional geometry among the feature classes and identify the k most susceptible target classes in an adversarial attack. We conduct experiments using MNIST, Fashion MNIST, CIFAR-10 (ImageNet and ResNet-32) datasets. Finally, we evaluate our techniques in order to determine which distance-based measure works best and how the randomness of a model changes with perturbation.
    The project is a collaboration with: Rangeet Pan, Md Johirul Islam, Shibbir Ahmed and Hridesh Rajan.