pwc-archive/papers-with-abstracts huggingface dataset:
Efficient non-conjugate Gaussian process factor models for spike countdata using polynomial approximations
Authors: Stephen Keeley, David Zoltowski, Jonathan Pillow, Spencer Smith, Yiyi Yu
Date: 2020-01-01 00:00:00
Proceeding: ICML 2020 1
Tasks: Variational Inference

Gaussian Process Factor Analysis (GPFA) hasbeen broadly applied to the problem of identi-fying smooth, low-dimensional temporal struc-ture underlying large-scale neural recordings.However, spike trains are non-Gaussian, whichmotivates combining GPFA with discrete ob-servation models for binned spike count data.The drawback to this approach is that GPFApriors are not conjugate to count model like-lihoods, which makes inference challenging.Here we address this obstacle by introduc-ing a fast, approximate inference method fornon-conjugate GPFA models. Our approachuses orthogonal second-order polynomials toapproximate the nonlinear terms in the non-conjugate log-likelihood, resulting in a methodwe refer to aspolynomial approximate log-likelihood(PAL) estimators. This approxima-tion allows for accurate closed-form evalua-tion of marginal likelihoods and fast numericaloptimization for parameters and hyperparam-eters. We derive PAL estimators for GPFAmodels with binomial, Poisson, and negativebinomial observations. We find the PAL esti-mation achieves faster convergence times andhigh accuracy compared to existing state-of-the-art inference methods. We also find thatPAL hyperparameters can provide sensible ini-tialization for black box variational inference(BBVI), which will improve BBVI accuracy.We apply these methods to data from mousevisual cortex and primate higher-order visualand parietal cortices. We demonstrate thatPreliminary work. Under review by AISTATS 2020. Do notdistribute.PAL estimators achieve fast and accurate ex-traction of latent structure from multi-neuronspike train data.
Eliminating the Invariance on the Loss Landscape of Linear Autoencoders
Authors: Reza Oftadeh, Jiayi Shen, Zhangyang Wang, Dylan Shell
Date: 2020-01-01 00:00:00
Proceeding: ICML 2020 1
Tasks: Decoder

In this paper, we propose a new loss function for linear autoencoders (LAEs) and then analytically identify the structure of the loss surface. Optimizing the conventional Mean Square Error (MSE) loss results in a decoder matrix that spans the principal subspace of the sample covariance of the data, but fails to identify the exact eigenvectors. This shortcoming originates from an invariance that cancels out in the global map. Here, we prove that our loss function eliminates this issue, i.e., the decoder converges to the exact ordered unnormalized eigenvectors of the sample covariance matrix. For this new loss, we characterize the full structure of the loss landscape in the following sense: we establish analytical expression for the set of all critical points, show that it is a subset of critical points of MSE, and that all local minima are still global. However, the invariant global minima under MSE become saddle points under the new loss. Moreover, we show that the order of computational complexity of the loss and its gradients are the same as MSE and, hence, the new loss is not only of theoretical importance but is of practical value, e.g., for low-rank approximation.
Fair k-Centers via Maximum Matching
Authors: Matthew Jones, Thy Nguyen, Huy Nguyen
Date: 2020-01-01 00:00:00
Proceeding: ICML 2020 1
Tasks: Data Summarization, Fairness

The field of algorithms has seen a push for fairness, or the removal of inherent bias, in recent history. In data summarization, where a much smaller subset of a data set is chosen to represent the whole of the data, fairness can be introduced by guaranteeing each "demographic group" a specific portion of the representative subset. Specifically, this paper examines this fair variant of the k-centers problem, where a subset of the data with cardinality k is chosen to minimize distance to the rest of the data. Previous papers working on this problem presented both a 3-approximation algorithm with a super-linear runtime and a linear-time algorithm whose approximation factor is exponential in the number of demographic groups. This paper combines the best parts of each algorithm , by presenting a linear-time algorithm with a guaranteed 3-approximation factor, and provides empirical evidence of both the algorithm's runtime and effectiveness.
Improved Communication Cost in Distributed PageRank Computation – A Theoretical Study
Authors: Siqiang Luo
Date: 2020-01-01 00:00:00
Proceeding: ICML 2020 1
Tasks: Recommendation Systems

PageRank is a widely used approach for measuring the importance of a node in a graph. Computing PageRank is a fundamental task in numerous applications including web search, machine learning and recommendation systems. The importance of computing PageRanks in a distributed environment has been recognized due to the rapid growth of the graph size in real world. However, only a few previous works can provide a provable complexity and accuracy for distributed PageRank computation. Given a constant $d>0$ and a graph of $n$ nodes and under the well-known congested-clique distributed model, the state-of-the-art approach, Radar-Push, uses $O(\log\log{n}+\log{d})$ communication rounds to approximate the PageRanks within a relative error $O(\frac{1}{\log^d{n}})$. However, Radar-Push entails as large as $O(\log^{2d+3}{n})$ bits of bandwidth (e.g., the communication cost between a pair of nodes per round) in the worst case. In this paper, we provide a new algorithm that uses asymptotically the same communication rounds while significantly improves the bandwidth from $O(\log^{2d+3}{n})$ bits to $O(d\log^3{n})$ bits. To the best of our knowledge, our distributed PageRank algorithm is the first to achieve $o(d\log{n})$ communication rounds with $O(d\log^3{n})$ bits of bandwidth in approximating PageRanks with relative error $O(\frac{1}{\log^d{n}})$ under the congested-clique model.
Instance-hiding Schemes for Private Distributed Learning
Authors: Yangsibo Huang, Zhao Song, Sanjeev Arora, Kai Li
Date: 2020-01-01 00:00:00
Proceeding: ICML 2020 1
Tasks: Federated Learning

An important problem today is how to allow a group of decentralized entities to compute on their private data on a centralized deep net while protecting data privacy. Classic cryptographic techniques are too inefficient, so other methods have recently been suggested, e.g., differentially private Federated Learning. Here, a new method is introduced, inspired by the classic notion of {\em instance hiding} in cryptography. It uses the Mixup technique, proposed by {Zhang et al, ICLR 2018} as a way to improve generalization and robustness. Usual mixup involves training on nonnegative combinations of inputs. The new ideas in the current paper are: (a) new variants of mixup with negative as well as positive coefficients, and extend the sample-wise mixup to be pixel-wise.  (b) Experiments demonstrating the effectiveness of this in protecting privacy against known attacks while preserving utility. (c)  Theoretical analysis suggesting why this method is effective, using ideas from analyses of attacks. (d) Estimates of security and the release of a challenge dataset to allow the design of attack schemes.
Label-Noise Robust Domain Adaptation
Authors: Xiyu Yu, Tongliang Liu, Mingming Gong, Kun Zhang, Kayhan Batmanghelich, DaCheng Tao
Date: 2020-01-01 00:00:00
Proceeding: ICML 2020 1
Tasks: Denoising, Domain Adaptation

Domain adaptation aims to correct the classifiers when faced with distribution shift between source (training) and target (test) domains. State-of-the-art domain adaptation methods make use of deep networks to extract domain-invariant representations. However, existing methods assume that all the instances in the source domain are correctly labeled; while in reality, it is unsurprising that we may obtain a source domain with noisy labels. In this paper, we first investigate how label noise could adversely affect existing domain adaptation methods in various scenarios. Focusing on the generalized target shift scenario, where both label distribution $P_Y$ and the class-conditional distribution $P_{X|Y}$ can change, we propose a new Denoising Conditional Invariant Component (DCIC) framework, which provably ensures (1) extracting invariant representations given examples with noisy labels in the source domain and unlabeled examples in the target domain and (2) estimating the label distribution in the target domain with no bias. Experimental results on both synthetic and real-world data verify the effectiveness of the proposed method.
Learnable Group Transform For Time-Series
Authors: Romain Cosentino, Behnaam Aazhang
Date: 2020-01-01 00:00:00
Proceeding: ICML 2020 1
Tasks: Time Series, Time Series Analysis

We propose a novel approach to filter bank learning for time-series by considering spectral decompositions of signals defined as a Group Transform. This framework allows us to generalize classical time-frequency transformations such as the Wavelet Transform, and  to efficiently learn the representation of signals. While the creation of the wavelet transform filter-bank relies on affine transformations of a mother filter, our approach allows for non-linear transformations. The transformations induced by such maps enable us to span a larger class of signal representations, from wavelet to chirplet-like filters. We propose a parameterization of such a non-linear map such that its sampling can be optimized for a specific task and signal. The Learnable Group Transform can be cast into a Deep Neural Network. The experiments on diverse time-series datasets demonstrate the expressivity of this framework, which competes with state-of-the-art performances.
Learning Opinions in Social Networks
Authors: Vincent Conitzer, Debmalya Panigrahi, Hanrui Zhang
Date: 2020-01-01 00:00:00
Proceeding: ICML 2020 1

We study the problem of learning opinions in social networks.  The learner observes the states of some sample nodes from a social network, and tries to infer the states of other nodes, based on the structure of the network.  We show that sample-efficient learning is impossible when the network exhibits strong noise, and give a polynomial-time algorithm for the problem with nearly optimal sample complexity when the network is sufficiently stable.
Message Passing Least Squares: A Unified Framework for Fast and Robust Group Synchronization
Authors: Yunpeng Shi, Gilad Lerman
Date: 2020-01-01 00:00:00
Proceeding: ICML 2020 1

We propose an efficient algorithm for solving robust group synchronization given adversarially corrupted group ratios. We first present a theoretically guaranteed message passing algorithm that estimates the corruption levels of the group ratios. We then propose a novel weighted least squares method to estimate the group elements, where the weights are initialized using the estimated corruption levels and are iteratively updated  by incorporating cycle consistency information. We demonstrate the superior performance of our algorithm over state-of-the-art methods for $SO(3)$ synchronization using both synthetic and real data.
Neural Architecture Search in a Proxy Validation Loss Landscape
Authors: Yanxi Li, Minjing Dong, Yunhe Wang, Chang Xu
Date: 2020-01-01 00:00:00
Proceeding: ICML 2020 1
Tasks: Neural Architecture Search

This paper searches for the optimal neural architecture  by minimizing a proxy of validation loss. Existing neural architecture search (NAS) methods used to discover the optimal neural architecture that best fits the validation examples given the up-to-date network weights. However, back propagation with a number of validation examples could be time consuming, especially when it needs to be repeated many times in NAS. Though these  intermediate validation results are invaluable, they would be wasted if we cannot use them to predict the future from the past. In this paper, we propose to approximate the validation loss landscape by learning a mapping from neural architectures to their corresponding validate losses. The optimal neural architecture thus can be easily identified as the minimum of this proxy validation loss landscape. A novel sampling strategy is further developed for an efficient approximation of the loss landscape. Theoretical analysis indicates that our sampling strategy can reach a lower error rate and a lower label complexity compared with a uniform sampling. Experimental results on benchmarks demonstrate that the architecture searched by the proposed algorithm can achieve a satisfactory accuracy with less time cost.
Online Bayesian Moment Matching based SAT Solver Heuristics
Authors: Haonan Duan, Saeed Nejati, George Trimponias, Pascal Poupart, Vijay Ganesh
Date: 2020-01-01 00:00:00
Proceeding: ICML 2020 1

In this paper, we present a Bayesian Moment Matching (BMM) based method aimed at solving the initialization problem in Boolean SAT solvers.  The initialization problem can be stated as follows: given a SAT formula φ, compute an initial order over the variables of φ and values/polarity for these variables such that the runtime of SAT solvers on input φ is minimized. At the start of a solver run, our BMM-based methods compute a posterior probability distribution for an assign- ment to the variables of the input formula after analyzing its clauses. This probability distribution is then used by the solver to initialize its search.  We perform extensive experiments to evaluate the efficacy of our BMM-based heuristic against 4 other initialization methods (random, survey propagation, Jeroslow-Wang, and default) in state-of-the-art solvers, MapleCOMSPS and MapleLCMDistChronotBT over the SAT competition 2018 application benchmark, as well as the best-known solvers in the cryptographic category, namely, CryptoMiniSAT, Glucose and MapleSAT.  On the cryptographic benchmark, BMM-based solvers out-perform all other initialization methods. Further, the BMM-based MapleCOMSPS significantly out-perform the same solver using all other initialization methods by 12 additional instances solved and better average runtime, over the SAT 2018 competition benchmark.

We performed extensive experiments to evaluate the efficacy of our BMM-based heuristics on SAT competition 2018 application and hard cryptographic benchmarks. We implemented our heuristics in state-of-the-art solvers (MapleCOMSPS and MapleLCMDistChronotBT for SAT competition 2018 application benchmarks) and CryptoMiniSAT, Glucose and MapleSAT (in the context of cryptographic benchmarks), against 4 other initialization methods. Our solvers out-perform the baselines by solving 12 more instances from the SAT competition 2018 application benchmark and are %40 faster on average in solving hard cryptographic instances.
On Validation and Planning of An Optimal Decision Rule with Application in Healthcare Studies
Authors: Hengrui Cai, Wenbin Lu, Rui Song
Date: 2020-01-01 00:00:00
Proceeding: ICML 2020 1

In the current era of personalized recommendation, one major interest is to develop an optimal individualized decision rule that assigns individuals with the best treatment option according to their covariates. Estimation of optimal decision rules (ODR) has been extensively investigated recently, however, at present, no testing procedure is proposed to verify whether these ODRs are significantly better than the naive decision rule that always assigning individuals to a fixed treatment option. In this paper, we propose a testing procedure for detecting the existence of an ODR that is better than the naive decision rule under the randomized trials. We construct the proposed test based on the difference of estimated value functions using the augmented inverse probability weighted method. The asymptotic distributions of the proposed test statistic under the null and local alternative hypotheses are established. Based on the established asymptotic distributions, we further develop a sample size calculation formula for testing the existence of an ODR in designing A/B tests. Extensive simulations and a real data application to a schizophrenia clinical trial data are conducted to demonstrate the empirical validity of the proposed methods.
Optimal Bounds between f-Divergences and Integral Probability Metrics
Authors: Rohit Agrawal, Thibaut Horel
Date: 2020-01-01 00:00:00
Proceeding: ICML 2020 1
Tasks: LEMMA

The families of f-divergences (e.g. the Kullback-Leibler divergence) and Integral Probability Metrics (e.g. total variation distance or maximum mean discrepancies) are commonly used in optimization and estimation. In this work, we systematically study the relationship between these two families from the perspective of convex duality. Starting from a tight variational representation of the f-divergence, we derive a generalization of the moment generating function, which we show exactly characterizes the best lower bound of the f-divergence as a function of a given IPM. Using this characterization, we obtain new bounds on IPMs defined by classes of unbounded functions, while also recovering in a unified manner well-known results for bounded and subgaussian functions (e.g. Pinsker's inequality and Hoeffding's lemma).
Prediction-Guided Multi-Objective Reinforcement Learning for Continuous Robot Control
Authors: Jie Xu, Yunsheng Tian, Pingchuan Ma, Daniela Rus, Shinjiro Sueda, Wojciech Matusik
Date: 2020-01-01 00:00:00
Proceeding: ICML 2020 1
Tasks: Multi-Objective Reinforcement Learning, reinforcement-learning, Reinforcement Learning, Reinforcement Learning (RL)

Many real-world control problems involve conflicting objectives where we desire a dense and high-quality set of control policies that are optimal for different objective preferences (called Pareto-optimal). While extensive research in multi-objective reinforcement learning (MORL) has been conducted to tackle such problems, multi-objective optimization for complex continuous robot control is still under-explored. In this work, we propose an efficient evolutionary learning algorithm to find the Pareto set approximation for continuous robot control problems, by extending a state-of-the-art RL algorithm and presenting a novel prediction model to guide the learning process. In addition to efficiently discovering the individual policies on the Pareto front, we construct a continuous set of Pareto-optimal solutions by Pareto analysis and interpolation. Furthermore, we design six multi-objective RL environments with continuous action space, which is the first benchmark platform to evaluate MORL algorithms on various robot control problems. We test the previous methods on the proposed benchmark problems, and the experiments show that our approach is able to find a much denser and higher-quality set of Pareto policies than the existing algorithms.
Preference modelling with context-dependent salient features
Authors: Amanda Bower, Laura Balzano
Date: 2020-01-01 00:00:00
Proceeding: ICML 2020 1

We consider the problem of estimating a ranking on a set of items from noisy pairwise comparisons given item features. We address the observation that pairwise comparison data often reflects irrational choice, e.g. intransitivity. Our key observation is that two items compared in isolation from other items may be compared based on only a salient subset of features. Formalizing this framework, we propose the \textit{salient feature preference model} and prove a sample complexity result for learning the parameters of our model and the underlying ranking with maximum likelihood estimation. We also provide empirical results that support our theoretical bounds and illustrate how our model explains systematic intransitivity. Finally we demonstrate the strong performance of maximum likelihood estimation of our model on both synthetic data and two real data sets: the UT Zappos50K data set and comparison data about the compactness of legislative districts in the United States.
Robust Black Box Explanations Under Distribution Shift
Authors: Himabindu Lakkaraju, Nino Arsov, Osbert Bastani
Date: 2020-01-01 00:00:00
Proceeding: ICML 2020 1

As machine learning black boxes are increasingly being deployed in real-world applications, there has been a growing interest in developing post hoc explanations that summarize the behaviors of these black box models. However, existing algorithms for generating such explanations have been shown to lack robustness with respect to shifts in the underlying data distribution. In this paper, we propose a novel framework for generating robust explanations of black box models based on adversarial training. In particular, our framework optimizes a minimax objective that aims to construct the highest fidelity explanation with respect to the worst-case over a set of distribution shifts. We instantiate this algorithm for explanations in the form of linear models and decision sets by devising the required optimization procedures. To the best of our knowledge, this work makes the first attempt at generating post hoc explanations that are robust to a general class of distribution shifts that are of practical interest. Experimental evaluation with real-world and synthetic datasets demonstrates that our approach substantially improves the robustness of explanations without sacrificing their fidelity on the original data distribution.
Statistical Bias in Dataset Replication
Authors: Logan Engstrom, Andrew Ilyas, Shibani Santurkar, Dimitris Tsipras, Jacob Steinhardt, Aleksander Madry
Date: 2020-01-01 00:00:00
Proceeding: ICML 2020 1

Dataset replication is a useful tool for assessing whether models have overfit to a specific validation set or the exact circumstances under which it was generated. In this paper, we highlight the importance of statistical modeling in dataset replication: we present unintuitive yet pervasive ways in which statistical bias, when left unmitigated, can skew results.  Specifically, we examine ImageNet-v2, a replication of the ImageNet dataset that induces a significant drop in model accuracy, presumed to be caused by a benign distribution shift between the datasets. We show, however, that by identifying and accounting for the aforementioned bias, we can explain the vast majority of this accuracy drop. We conclude with concrete recommendations for recognizing and avoiding bias in dataset replication.
Sub-linear Memory Sketches for Near Neighbor Search on Streaming Data with RACE
Authors: Benjamin Coleman, Anshumali Shrivastava, Richard Baraniuk
Date: 2020-01-01 00:00:00
Proceeding: ICML 2020 1
Tasks: compressed sensing, Density Estimation

We present the first sublinear memory sketch that can be queried to find the nearest neighbors in a dataset. Our online sketching algorithm compresses an N element dataset to a sketch of size O(N^b log^3 N) in O(N^(b+1) log^3 N) time, where b < 1. This sketch can correctly report the nearest neighbors of any query that satisfies a stability condition parameterized by b. We achieve sublinear memory performance on stable queries by combining recent advances in locality sensitive hash (LSH)-based estimators, online kernel density estimation, and compressed sensing. Our theoretical results shed new light on the memory-accuracy tradeoff for nearest neighbor search, and our sketch, which consists entirely of short integer arrays, has a variety of attractive features in practice. We provide rigorous theoretical guarantees and present a thorough evaluation of the memory-recall tradeoff of our method on a friend recommendation task in social media networks, including the Google plus graph. We find that RACE provides orders of magnitude better compression than the random projection based alternative while retaining the ability to report the nearest neighbors of practical queries. We expect that our theory will lead to new insight on geometric sketching problems while our methods will enable new possibilities in high-speed data mining and IoT settings.