pwc-archive/papers-with-abstracts huggingface dataset:
Better accuracy with quantified privacy: representations learned via reconstructive adversarial network
Authors: Sicong Liu, Anshumali Shrivastava, Junzhao Du, Lin Zhong
Date: 2019-01-25 00:00:00
Proceeding: ICLR 2019 5
Tasks: BIG-bench Machine Learning, Decoder, General Classification

The remarkable success of machine learning, especially deep learning, has
produced a variety of cloud-based services for mobile users. Such services
require an end user to send data to the service provider, which presents a
serious challenge to end-user privacy. To address this concern, prior works
either add noise to the data or send features extracted from the raw data. They
struggle to balance between the utility and privacy because added noise reduces
utility and raw data can be reconstructed from extracted features. This work
represents a methodical departure from prior works: we balance between a
measure of privacy and another of utility by leveraging adversarial learning to
find a sweeter tradeoff. We design an encoder that optimizes against the
reconstruction error (a measure of privacy), adversarially by a Decoder, and
the inference accuracy (a measure of utility) by a Classifier. The result is
RAN, a novel deep model with a new training algorithm that automatically
extracts features for classification that are both private and useful. It turns
out that adversarially forcing the extracted features to only conveys the
intended information required by classification leads to an implicit
regularization leading to better classification accuracy than the original
model which completely ignores privacy. Thus, we achieve better privacy with
better utility, a surprising possibility in machine learning! We conducted
extensive experiments on five popular datasets over four training schemes, and
demonstrate the superiority of RAN compared with existing alternatives.
Evaluation Function Approximation for Scrabble
Authors: Rishabh Agarwal
Date: 2019-01-25 00:00:00
Tasks: Bayesian Optimization, Evolutionary Algorithms, Imitation Learning

The current state-of-the-art Scrabble agents are not learning-based but
depend on truncated Monte Carlo simulations and the quality of such agents is
contingent upon the time available for running the simulations. This thesis
takes steps towards building a learning-based Scrabble agent using self-play.
Specifically, we try to find a better function approximation for the static
evaluation function used in Scrabble which determines the move goodness at a
given board configuration. In this work, we experimented with evolutionary
algorithms and Bayesian Optimization to learn the weights for an approximate
feature-based evaluation function. However, these optimization methods were not
quite effective, which lead us to explore the given problem from an Imitation
Learning point of view. We also tried to imitate the ranking of moves produced
by the Quackle simulation agent using supervised learning with a neural network
function approximator which takes the raw representation of the Scrabble board
as the input instead of using only a fixed number of handcrafted features.
Towards Interpretable Deep Neural Networks by Leveraging Adversarial Examples
Authors: Yinpeng Dong, Fan Bao, Hang Su, Jun Zhu
Date: 2019-01-25 00:00:00

Sometimes it is not enough for a DNN to produce an outcome. For example, in
applications such as healthcare, users need to understand the rationale of the
decisions. Therefore, it is imperative to develop algorithms to learn models
with good interpretability (Doshi-Velez 2017). An important factor that leads
to the lack of interpretability of DNNs is the ambiguity of neurons, where a
neuron may fire for various unrelated concepts. This work aims to increase the
interpretability of DNNs on the whole image space by reducing the ambiguity of
neurons. In this paper, we make the following contributions:
  1) We propose a metric to evaluate the consistency level of neurons in a
network quantitatively.
  2) We find that the learned features of neurons are ambiguous by leveraging
adversarial examples.
  3) We propose to improve the consistency of neurons on adversarial example
subset by an adversarial training algorithm with a consistent loss.
Deep Multimodality Model for Multi-task Multi-view Learning
Authors: Lecheng Zheng, Yu Cheng, Jingrui He
Date: 2019-01-25 00:00:00
Tasks: General Classification, image-classification, Image Classification, MULTI-VIEW LEARNING

Many real-world problems exhibit the coexistence of multiple types of
heterogeneity, such as view heterogeneity (i.e., multi-view property) and task
heterogeneity (i.e., multi-task property). For example, in an image
classification problem containing multiple poses of the same object, each pose
can be considered as one view, and the detection of each type of object can be
treated as one task. Furthermore, in some problems, the data type of multiple
views might be different. In a web classification problem, for instance, we
might be provided an image and text mixed data set, where the web pages are
characterized by both images and texts. A common strategy to solve this kind of
problem is to leverage the consistency of views and the relatedness of tasks to
build the prediction model. In the context of deep neural network, multi-task
relatedness is usually realized by grouping tasks at each layer, while
multi-view consistency is usually enforced by finding the maximal correlation
coefficient between views. However, there is no existing deep learning
algorithm that jointly models task and view dual heterogeneity, particularly
for a data set with multiple modalities (text and image mixed data set or text
and video mixed data set, etc.). In this paper, we bridge this gap by proposing
a deep multi-task multi-view learning framework that learns a deep
representation for such dual-heterogeneity problems. Empirical studies on
multiple real-world data sets demonstrate the effectiveness of our proposed
Deep-MTMV algorithm.
Orthogonal Statistical Learning
Authors: Dylan J. Foster, Vasilis Syrgkanis
Date: 2019-01-25 00:00:00
Tasks: Domain Adaptation, parameter estimation

We provide non-asymptotic excess risk guarantees for statistical learning in a setting where the population risk with respect to which we evaluate the target parameter depends on an unknown nuisance parameter that must be estimated from data. We analyze a two-stage sample splitting meta-algorithm that takes as input arbitrary estimation algorithms for the target parameter and nuisance parameter. We show that if the population risk satisfies a condition called Neyman orthogonality, the impact of the nuisance estimation error on the excess risk bound achieved by the meta-algorithm is of second order. Our theorem is agnostic to the particular algorithms used for the target and nuisance and only makes an assumption on their individual performance. This enables the use of a plethora of existing results from machine learning to give new guarantees for learning with a nuisance component. Moreover, by focusing on excess risk rather than parameter estimation, we can provide rates under weaker assumptions than in previous works and accommodate settings in which the target parameter belongs to a complex nonparametric class. We provide conditions on the metric entropy of the nuisance and target classes such that oracle rates of the same order as if we knew the nuisance parameter are achieved.
Local Distance Constrained Bribery in Voting
Authors: Palash Dey
Date: 2019-01-25 00:00:00

Studying complexity of various bribery problems has been one of the main research focus in computational social choice. In all the models of bribery studied so far, the briber has to pay every voter some amount of money depending on what the briber wants the voter to report and the briber has some budget at her disposal. Although these models successfully capture many real world applications, in many other scenarios, the voters may be unwilling to deviate too much from their true preferences. In this paper, we study the computational complexity of the problem of finding a preference profile which is as close to the true preference profile as possible and still achieves the briber's goal subject to budget constraints. We call this problem Optimal Bribery. We consider three important measures of distances, namely, swap distance, footrule distance, and maximum displacement distance, and resolve the complexity of the optimal bribery problem for many common voting rules. We show that the problem is polynomial time solvable for the plurality and veto voting rules for all the three measures of distance. On the other hand, we prove that the problem is NP-complete for a class of scoring rules which includes the Borda voting rule, maximin, Copeland$^\alpha$ for any $\alpha\in[0,1]$, and Bucklin voting rules for all the three measures of distance even when the distance allowed per voter is $1$ for the swap and maximum displacement distances and $2$ for the footrule distance even without the budget constraints (which corresponds to having an infinite budget). For the $k$-approval voting rule for any constant $k>1$ and the simplified Bucklin voting rule, we show that the problem is NP-complete for the swap distance even when the distance allowed is $2$ and for the footrule distance even when the distance allowed is $4$ even without the budget constraints.
When Can Neural Networks Learn Connected Decision Regions?
Authors: Trung Le, Dinh Phung
Date: 2019-01-25 00:00:00

Previous work has questioned the conditions under which the decision regions
of a neural network are connected and further showed the implications of the
corresponding theory to the problem of adversarial manipulation of classifiers.
It has been proven that for a class of activation functions including leaky
ReLU, neural networks having a pyramidal structure, that is no layer has more
hidden units than the input dimension, produce necessarily connected decision
regions. In this paper, we advance this important result by further developing
the sufficient and necessary conditions under which the decision regions of a
neural network are connected. We then apply our framework to overcome the
limits of existing work and further study the capacity to learn connected
regions of neural networks for a much wider class of activation functions
including those widely used, namely ReLU, sigmoid, tanh, softlus, and
exponential linear function.
Almost Boltzmann Exploration
Authors: Harsh Gupta, Seo Taek Kong, R. Srikant, Weina Wang
Date: 2019-01-25 00:00:00
Tasks: Multi-Armed Bandits, Reinforcement Learning

Boltzmann exploration is widely used in reinforcement learning to provide a
trade-off between exploration and exploitation. Recently, in (Cesa-Bianchi et
al., 2017) it has been shown that pure Boltzmann exploration does not perform
well from a regret perspective, even in the simplest setting of stochastic
multi-armed bandit (MAB) problems. In this paper, we show that a simple
modification to Boltzmann exploration, motivated by a variation of the standard
doubling trick, achieves $O(K\log^{1+\alpha} T)$ regret for a stochastic MAB
problem with $K$ arms, where $\alpha>0$ is a parameter of the algorithm. This
improves on the result in (Cesa-Bianchi et al., 2017), where an algorithm
inspired by the Gumbel-softmax trick achieves $O(K\log^2 T)$ regret. We also
show that our algorithm achieves $O(\beta(G) \log^{1+\alpha} T)$ regret in
stochastic MAB problems with graph-structured feedback, without knowledge of
the graph structure, where $\beta(G)$ is the independence number of the
feedback graph. Additionally, we present extensive experimental results on real
datasets and applications for multi-armed bandits with both traditional bandit
feedback and graph-structured feedback. In all cases, our algorithm performs as
well or better than the state-of-the-art.
Surrogate Supervision for Medical Image Analysis: Effective Deep Learning From Limited Quantities of Labeled Data
Authors: Nima Tajbakhsh, Yufei Hu, Junli Cao, Xingjian Yan, Yi Xiao, Yong Lu, Jianming Liang, Demetri Terzopoulos, Xiaowei Ding
Date: 2019-01-25 00:00:00
Tasks: Colorization, Medical Image Analysis, Transfer Learning

We investigate the effectiveness of a simple solution to the common problem
of deep learning in medical image analysis with limited quantities of labeled
training data. The underlying idea is to assign artificial labels to abundantly
available unlabeled medical images and, through a process known as surrogate
supervision, pre-train a deep neural network model for the target medical image
analysis task lacking sufficient labeled training data. In particular, we
employ 3 surrogate supervision schemes, namely rotation, reconstruction, and
colorization, in 4 different medical imaging applications representing
classification and segmentation for both 2D and 3D medical images. 3 key
findings emerge from our research: 1) pre-training with surrogate supervision
is effective for small training sets; 2) deep models trained from initial
weights pre-trained through surrogate supervision outperform the same models
when trained from scratch, suggesting that pre-training with surrogate
supervision should be considered prior to training any deep 3D models; 3)
pre-training models in the medical domain with surrogate supervision is more
effective than transfer learning from an unrelated domain (e.g., natural
images), indicating the practical value of abundant unlabeled medical image
data.
Emergent Linguistic Phenomena in Multi-Agent Communication Games
Authors: Laura Graesser, Kyunghyun Cho, Douwe Kiela
Date: 2019-01-25 00:00:00
Proceeding: IJCNLP 2019 11
Tasks: Deep Reinforcement Learning, Reinforcement Learning, Reinforcement Learning (RL)

In this work, we propose a computational framework in which agents equipped with communication capabilities simultaneously play a series of referential games, where agents are trained using deep reinforcement learning. We demonstrate that the framework mirrors linguistic phenomena observed in natural language: i) the outcome of contact between communities is a function of inter- and intra-group connectivity; ii) linguistic contact either converges to the majority protocol, or in balanced cases leads to novel creole languages of lower complexity; and iii) a linguistic continuum emerges where neighboring languages are more mutually intelligible than farther removed languages. We conclude that intricate properties of language evolution need not depend on complex evolved linguistic capabilities, but can emerge from simple social exchanges between perceptually-enabled agents playing communication games.
Don't Jump Through Hoops and Remove Those Loops: SVRG and Katyusha are Better Without the Outer Loop
Authors: Dmitry Kovalev, Samuel Horvath, Peter Richtarik
Date: 2019-01-24 00:00:00
Tasks: BIG-bench Machine Learning

The stochastic variance-reduced gradient method (SVRG) and its accelerated variant (Katyusha) have attracted enormous attention in the machine learning community in the last few years due to their superior theoretical properties and empirical behaviour on training supervised machine learning models via the empirical risk minimization paradigm. A key structural element in both of these methods is the inclusion of an outer loop at the beginning of which a full pass over the training data is made in order to compute the exact gradient, which is then used to construct a variance-reduced estimator of the gradient. In this work we design {\em loopless variants} of both of these methods. In particular, we remove the outer loop and replace its function by a coin flip performed in each iteration designed to trigger, with a small probability, the computation of the gradient. We prove that the new methods enjoy the same superior theoretical convergence properties as the original methods. However, we demonstrate through numerical experiments that our methods have substantially superior practical behavior.
One-Class Convolutional Neural Network
Authors: Poojan Oza, Vishal M. Patel
Date: 2019-01-24 00:00:00
Tasks: Anomaly Detection, General Classification, Novelty Detection, One-Class Classification

We present a novel Convolutional Neural Network (CNN) based approach for one
class classification. The idea is to use a zero centered Gaussian noise in the
latent space as the pseudo-negative class and train the network using the
cross-entropy loss to learn a good representation as well as the decision
boundary for the given class. A key feature of the proposed approach is that
any pre-trained CNN can be used as the base network for one class
classification. The proposed One Class CNN (OC-CNN) is evaluated on the
UMDAA-02 Face, Abnormality-1001, FounderType-200 datasets. These datasets are
related to a variety of one class application problems such as user
authentication, abnormality detection and novelty detection. Extensive
experiments demonstrate that the proposed method achieves significant
improvements over the recent state-of-the-art methods. The source code is
available at : github.com/otkupjnoz/oc-cnn.
Multi-objective training of Generative Adversarial Networks with multiple discriminators
Authors: Isabela Albuquerque, João Monteiro, Thang Doan, Breandan Considine, Tiago Falk, Ioannis Mitliagkas
Date: 2019-01-24 00:00:00
Proceeding: ICLR 2019 5

Recent literature has demonstrated promising results for training Generative
Adversarial Networks by employing a set of discriminators, in contrast to the
traditional game involving one generator against a single adversary. Such
methods perform single-objective optimization on some simple consolidation of
the losses, e.g. an arithmetic average. In this work, we revisit the
multiple-discriminator setting by framing the simultaneous minimization of
losses provided by different models as a multi-objective optimization problem.
Specifically, we evaluate the performance of multiple gradient descent and the
hypervolume maximization algorithm on a number of different datasets. Moreover,
we argue that the previously proposed methods and hypervolume maximization can
all be seen as variations of multiple gradient descent in which the update
direction can be computed efficiently. Our results indicate that hypervolume
maximization presents a better compromise between sample quality and
computational cost than previous methods.
SAGA with Arbitrary Sampling
Authors: Xu Qian, Zheng Qu, Peter Richtárik
Date: 2019-01-24 00:00:00

We study the problem of minimizing the average of a very large number of
smooth functions, which is of key importance in training supervised learning
models. One of the most celebrated methods in this context is the SAGA
algorithm. Despite years of research on the topic, a general-purpose version of
SAGA---one that would include arbitrary importance sampling and minibatching
schemes---does not exist. We remedy this situation and propose a general and
flexible variant of SAGA following the {\em arbitrary sampling} paradigm. We
perform an iteration complexity analysis of the method, largely possible due to
the construction of new stochastic Lyapunov functions. We establish linear
convergence rates in the smooth and strongly convex regime, and under a
quadratic functional growth condition (i.e., in a regime not assuming strong
convexity). Our rates match those of the primal-dual method Quartz for which an
arbitrary sampling analysis is available, which makes a significant step
towards closing the gap in our understanding of complexity of primal and dual
methods for finite sum problems.
Guarantees for Spectral Clustering with Fairness Constraints
Authors: Matthäus Kleindessner, Samira Samadi, Pranjal Awasthi, Jamie Morgenstern
Date: 2019-01-24 00:00:00
Tasks: Clustering, Fairness, Stochastic Block Model

Given the widespread popularity of spectral clustering (SC) for partitioning graph data, we study a version of constrained SC in which we try to incorporate the fairness notion proposed by Chierichetti et al. (2017). According to this notion, a clustering is fair if every demographic group is approximately proportionally represented in each cluster. To this end, we develop variants of both normalized and unnormalized constrained SC and show that they help find fairer clusterings on both synthetic and real data. We also provide a rigorous theoretical analysis of our algorithms on a natural variant of the stochastic block model, where $h$ groups have strong inter-group connectivity, but also exhibit a "natural" clustering structure which is fair. We prove that our algorithms can recover this fair clustering with high probability.
Fairness risk measures
Authors: Robert C. Williamson, Aditya Krishna Menon
Date: 2019-01-24 00:00:00
Tasks: Fairness

Ensuring that classifiers are non-discriminatory or fair with respect to a
sensitive feature (e.g., race or gender) is a topical problem. Progress in this
task requires fixing a definition of fairness, and there have been several
proposals in this regard over the past few years. Several of these, however,
assume either binary sensitive features (thus precluding categorical or
real-valued sensitive groups), or result in non-convex objectives (thus
adversely affecting the optimisation landscape). In this paper, we propose a
new definition of fairness that generalises some existing proposals, while
allowing for generic sensitive features and resulting in a convex objective.
The key idea is to enforce that the expected losses (or risks) across each
subgroup induced by the sensitive feature are commensurate. We show how this
relates to the rich literature on risk measures from mathematical finance. As a
special case, this leads to a new convex fairness-aware objective based on
minimising the conditional value at risk (CVaR).
Is Pretraining Necessary for Hyperspectral Image Classification?
Authors: Hyungtae Lee, Sungmin Eum, Heesung Kwon
Date: 2019-01-24 00:00:00
Tasks: Classification, General Classification, Hyperspectral Image Classification, image-classification, Image Classification

We address two questions for training a convolutional neural network (CNN)
for hyperspectral image classification: i) is it possible to build a
pre-trained network? and ii) is the pre-training effective in furthering the
performance? To answer the first question, we have devised an approach that
pre-trains a network on multiple source datasets that differ in their
hyperspectral characteristics and fine-tunes on a target dataset. This approach
effectively resolves the architectural issue that arises when transferring
meaningful information between the source and the target networks. To answer
the second question, we carried out several ablation experiments. Based on the
experimental results, a network trained from scratch performs as good as a
network fine-tuned from a pre-trained network. However, we observed that
pre-training the network has its own advantage in achieving better performances
when deeper networks are required.
The Assistive Multi-Armed Bandit
Authors: Lawrence Chan, Dylan Hadfield-Menell, Siddhartha Srinivasa, Anca Dragan
Date: 2019-01-24 00:00:00
Tasks: Multi-Armed Bandits

Learning preferences implicit in the choices humans make is a well studied
problem in both economics and computer science. However, most work makes the
assumption that humans are acting (noisily) optimally with respect to their
preferences. Such approaches can fail when people are themselves learning about
what they want. In this work, we introduce the assistive multi-armed bandit,
where a robot assists a human playing a bandit task to maximize cumulative
reward. In this problem, the human does not know the reward function but can
learn it through the rewards received from arm pulls; the robot only observes
which arms the human pulls but not the reward associated with each pull. We
offer sufficient and necessary conditions for successfully assisting the human
in this framework. Surprisingly, better human performance in isolation does not
necessarily lead to better performance when assisted by the robot: a human
policy can do better by effectively communicating its observed rewards to the
robot. We conduct proof-of-concept experiments that support these results. We
see this work as contributing towards a theory behind algorithms for
human-robot interaction.