pwc-archive/papers-with-abstracts huggingface dataset:
Importance Weighted Generative Networks
Authors: Maurice Diesendruck, Ethan R. Elenberg, Rajat Sen, Guy W. Cole, Sanjay Shakkottai, Sinead A. Williamson
Date: 2018-06-07 00:00:00
Tasks: Selection bias

Deep generative networks can simulate from a complex target distribution, by minimizing a loss with respect to samples from that distribution. However, often we do not have direct access to our target distribution - our data may be subject to sample selection bias, or may be from a different but related distribution. We present methods based on importance weighting that can estimate the loss with respect to a target distribution, even if we cannot access that distribution directly, in a variety of settings. These estimators, which differentially weight the contribution of data to the loss function, offer both theoretical guarantees and impressive empirical performance.
Exact Low Tubal Rank Tensor Recovery from Gaussian Measurements
Authors: Canyi Lu, Jiashi Feng, Zhouchen Lin, Shuicheng Yan
Date: 2018-06-07 00:00:00

The recent proposed Tensor Nuclear Norm (TNN) [Lu et al., 2016; 2018a] is an
interesting convex penalty induced by the tensor SVD [Kilmer and Martin, 2011].
It plays a similar role as the matrix nuclear norm which is the convex
surrogate of the matrix rank. Considering that the TNN based Tensor Robust PCA
[Lu et al., 2018a] is an elegant extension of Robust PCA with a similar tight
recovery bound, it is natural to solve other low rank tensor recovery problems
extended from the matrix cases. However, the extensions and proofs are
generally tedious. The general atomic norm provides a unified view of
low-complexity structures induced norms, e.g., the $\ell_1$-norm and nuclear
norm. The sharp estimates of the required number of generic measurements for
exact recovery based on the atomic norm are known in the literature. In this
work, with a careful choice of the atomic set, we prove that TNN is a special
atomic norm. Then by computing the Gaussian width of certain cone which is
necessary for the sharp estimate, we achieve a simple bound for guaranteed low
tubal rank tensor recovery from Gaussian measurements. Specifically, we show
that by solving a TNN minimization problem, the underlying tensor of size
$n_1\times n_2\times n_3$ with tubal rank $r$ can be exactly recovered when the
given number of Gaussian measurements is $O(r(n_1+n_2-r)n_3)$. It is order
optimal when comparing with the degrees of freedom $r(n_1+n_2-r)n_3$. Beyond
the Gaussian mapping, we also give the recovery guarantee of tensor completion
based on the uniform random mapping by TNN minimization. Numerical experiments
verify our theoretical results.
Stochastic Gradient/Mirror Descent: Minimax Optimality and Implicit Regularization
Authors: Navid Azizan, Babak Hassibi
Date: 2018-06-04 00:00:00
Proceeding: ICLR 2019 5

Stochastic descent methods (of the gradient and mirror varieties) have become
increasingly popular in optimization. In fact, it is now widely recognized that
the success of deep learning is not only due to the special deep architecture
of the models, but also due to the behavior of the stochastic descent methods
used, which play a key role in reaching "good" solutions that generalize well
to unseen data. In an attempt to shed some light on why this is the case, we
revisit some minimax properties of stochastic gradient descent (SGD) for the
square loss of linear models---originally developed in the 1990's---and extend
them to general stochastic mirror descent (SMD) algorithms for general loss
functions and nonlinear models. In particular, we show that there is a
fundamental identity which holds for SMD (and SGD) under very general
conditions, and which implies the minimax optimality of SMD (and SGD) for
sufficiently small step size, and for a general class of loss functions and
general nonlinear models. We further show that this identity can be used to
naturally establish other properties of SMD (and SGD), namely convergence and
implicit regularization for over-parameterized linear models (in what is now
being called the "interpolating regime"), some of which have been shown in
certain cases in prior literature. We also argue how this identity can be used
in the so-called "highly over-parameterized" nonlinear setting (where the
number of parameters far exceeds the number of data points) to provide insights
into why SMD (and SGD) may have similar convergence and implicit regularization
properties for deep learning.
Removing Algorithmic Discrimination (With Minimal Individual Error)
Authors: El Mahdi El Mhamdi, Rachid Guerraoui, Lê Nguyên Hoang, Alexandre Maurer
Date: 2018-06-07 00:00:00

We address the problem of correcting group discriminations within a score
function, while minimizing the individual error. Each group is described by a
probability density function on the set of profiles. We first solve the problem
analytically in the case of two populations, with a uniform bonus-malus on the
zones where each population is a majority. We then address the general case of
n populations, where the entanglement of populations does not allow a similar
analytical solution. We show that an approximate solution with an arbitrarily
high level of precision can be computed with linear programming. Finally, we
address the inverse problem where the error should not go beyond a certain
value and we seek to minimize the discrimination.
Interpretability Beyond Feature Attribution: Quantitative Testing with Concept Activation Vectors (TCAV)
Authors: Been Kim, Martin Wattenberg, Justin Gilmer, Carrie Cai, James Wexler, Fernanda Viegas, Rory Sayres
Date: 2017-11-30 00:00:00
Proceeding: ICML 2018 7
Tasks: General Classification, image-classification, Image Classification

The interpretation of deep learning models is a challenge due to their size,
complexity, and often opaque internal state. In addition, many systems, such as
image classifiers, operate on low-level features rather than high-level
concepts. To address these challenges, we introduce Concept Activation Vectors
(CAVs), which provide an interpretation of a neural net's internal state in
terms of human-friendly concepts. The key idea is to view the high-dimensional
internal state of a neural net as an aid, not an obstacle. We show how to use
CAVs as part of a technique, Testing with CAVs (TCAV), that uses directional
derivatives to quantify the degree to which a user-defined concept is important
to a classification result--for example, how sensitive a prediction of "zebra"
is to the presence of stripes. Using the domain of image classification as a
testing ground, we describe how CAVs may be used to explore hypotheses and
generate insights for a standard image classification network as well as a
medical application.
Semi-Dynamic Load Balancing: Efficient Distributed Learning in Non-Dedicated Environments
Authors: Chen Chen, Qizhen Weng, Wei Wang, Baochun Li, Bo Li
Date: 2018-06-07 00:00:00
Tasks: CPU, GPU

Machine learning (ML) models are increasingly trained in clusters with non-dedicated workers possessing heterogeneous resources. In such scenarios, model training efficiency can be negatively affected by stragglers -- workers that run much slower than others. Efficient model training requires eliminating such stragglers, yet for modern ML workloads, existing load balancing strategies are inefficient and even infeasible. In this paper, we propose a novel strategy called semi-dynamic load balancing to eliminate stragglers of distributed ML workloads. The key insight is that ML workers shall be load-balanced at iteration boundaries, being non-intrusive to intra-iteration execution. We develop LB-BSP based on such an insight, which is an integrated worker coordination mechanism that adapts workers' load to their instantaneous processing capabilities by right-sizing the sample batches at the synchronization barriers. We have custom-designed the batch sizing algorithm respectively for CPU and GPU clusters based on their own characteristics. LB-BSP has been implemented as a Python module for ML frameworks like TensorFlow and PyTorch. Our EC2 deployment confirms that LB-BSP is practical, effective and light-weight, and is able to accelerating distributed training by up to $54\%$.
Large scale classification in deep neural network with Label Mapping
Authors: Qizhi Zhang, Kuang-Chih Lee, Hongying Bao, Yuan You, Wenjie Li, Dongbai Guo
Date: 2018-06-07 00:00:00
Tasks: BIG-bench Machine Learning, Classification, General Classification, Multi-class Classification

In recent years, deep neural network is widely used in machine learning. The
multi-class classification problem is a class of important problem in machine
learning. However, in order to solve those types of multi-class classification
problems effectively, the required network size should have hyper-linear growth
with respect to the number of classes. Therefore, it is infeasible to solve the
multi-class classification problem using deep neural network when the number of
classes are huge. This paper presents a method, so called Label Mapping (LM),
to solve this problem by decomposing the original classification problem to
several smaller sub-problems which are solvable theoretically. Our method is an
ensemble method like error-correcting output codes (ECOC), but it allows base
learners to be multi-class classifiers with different number of class labels.
We propose two design principles for LM, one is to maximize the number of base
classifier which can separate two different classes, and the other is to keep
all base learners to be independent as possible in order to reduce the
redundant information. Based on these principles, two different LM algorithms
are derived using number theory and information theory. Since each base learner
can be trained independently, it is easy to scale our method into a large scale
training system. Experiments show that our proposed method outperforms the
standard one-hot encoding and ECOC significantly in terms of accuracy and model
complexity.
Selecting Representative Examples for Program Synthesis
Authors: Yewen Pu, Zachery Miranda, Armando Solar-Lezama, Leslie Pack Kaelbling
Date: 2017-11-09 00:00:00
Proceeding: ICML 2018 7
Tasks: Program Synthesis

Program synthesis is a class of regression problems where one seeks a
solution, in the form of a source-code program, mapping the inputs to their
corresponding outputs exactly. Due to its precise and combinatorial nature,
program synthesis is commonly formulated as a constraint satisfaction problem,
where input-output examples are encoded as constraints and solved with a
constraint solver. A key challenge of this formulation is scalability: while
constraint solvers work well with a few well-chosen examples, a large set of
examples can incur significant overhead in both time and memory. We describe a
method to discover a subset of examples that is both small and representative:
the subset is constructed iteratively, using a neural network to predict the
probability of unchosen examples conditioned on the chosen examples in the
subset, and greedily adding the least probable example. We empirically evaluate
the representativeness of the subsets constructed by our method, and
demonstrate such subsets can significantly improve synthesis time and
stability.
GP-RVM: Genetic Programing-based Symbolic Regression Using Relevance Vector Machine
Authors: Hossein Izadi Rad, Ji Feng, Hitoshi Iba
Date: 2018-06-07 00:00:00
Tasks: Evolutionary Algorithms, regression, Symbolic Regression

This paper proposes a hybrid basis function construction method (GP-RVM) for
Symbolic Regression problem, which combines an extended version of Genetic
Programming called Kaizen Programming and Relevance Vector Machine to evolve an
optimal set of basis functions. Different from traditional evolutionary
algorithms where a single individual is a complete solution, our method
proposes a solution based on linear combination of basis functions built from
individuals during the evolving process. RVM which is a sparse Bayesian kernel
method selects suitable functions to constitute the basis. RVM determines the
posterior weight of a function by evaluating its quality and sparsity. The
solution produced by GP-RVM is a sparse Bayesian linear model of the
coefficients of many non-linear functions. Our hybrid approach is focused on
nonlinear white-box models selecting the right combination of functions to
build robust predictions without prior knowledge about data. Experimental
results show that GP-RVM outperforms conventional methods, which suggest that
it is an efficient and accurate technique for solving SR. The computational
complexity of GP-RVM scales in $O( M^{3})$, where $M$ is the number of
functions in the basis set and is typically much smaller than the number $N$ of
training patterns.
Simplifying Reward Design through Divide-and-Conquer
Authors: Ellis Ratner, Dylan Hadfield-Menell, Anca D. Dragan
Date: 2018-06-07 00:00:00
Tasks: Motion Planning, Reinforcement Learning

Designing a good reward function is essential to robot planning and
reinforcement learning, but it can also be challenging and frustrating. The
reward needs to work across multiple different environments, and that often
requires many iterations of tuning. We introduce a novel divide-and-conquer
approach that enables the designer to specify a reward separately for each
environment. By treating these separate reward functions as observations about
the underlying true reward, we derive an approach to infer a common reward
across all environments. We conduct user studies in an abstract grid world
domain and in a motion planning domain for a 7-DOF manipulator that measure
user effort and solution quality. We show that our method is faster, easier to
use, and produces a higher quality solution than the typical method of
designing a reward jointly across all environments. We additionally conduct a
series of experiments that measure the sensitivity of these results to
different properties of the reward design task, such as the number of
environments, the number of feasible solutions per environment, and the
fraction of the total features that vary within each environment. We find that
independent reward design outperforms the standard, joint, reward design
process but works best when the design problem can be divided into simpler
subproblems.
Safe Element Screening for Submodular Function Minimization
Authors: Weizhong Zhang, Bin Hong, Lin Ma, Wei Liu, Tong Zhang
Date: 2018-05-22 00:00:00
Proceeding: ICML 2018 7
Tasks: Combinatorial Optimization, Sparse Learning

Submodular functions are discrete analogs of convex functions, which have
applications in various fields, including machine learning and computer vision.
However, in large-scale applications, solving Submodular Function Minimization
(SFM) problems remains challenging. In this paper, we make the first attempt to
extend the emerging technique named screening in large-scale sparse learning to
SFM for accelerating its optimization process. We first conduct a careful
studying of the relationships between SFM and the corresponding convex proximal
problems, as well as the accurate primal optimum estimation of the proximal
problems. Relying on this study, we subsequently propose a novel safe screening
method to quickly identify the elements guaranteed to be included (we refer to
them as active) or excluded (inactive) in the final optimal solution of SFM
during the optimization process. By removing the inactive elements and fixing
the active ones, the problem size can be dramatically reduced, leading to great
savings in the computational cost without sacrificing any accuracy. To the best
of our knowledge, the proposed method is the first screening method in the
fields of SFM and even combinatorial optimization, thus pointing out a new
direction for accelerating SFM algorithms. Experiment results on both synthetic
and real datasets demonstrate the significant speedups gained by our approach.
Conditional probability calculation using restricted Boltzmann machine with application to system identification
Authors: Erick de la Rosa, Wen Yu
Date: 2018-06-07 00:00:00

There are many advantages to use probability method for nonlinear system
identification, such as the noises and outliers in the data set do not affect
the probability models significantly; the input features can be extracted in
probability forms. The biggest obstacle of the probability model is the
probability distributions are not easy to be obtained. In this paper, we form
the nonlinear system identification into solving the conditional probability.
Then we modify the restricted Boltzmann machine (RBM), such that the joint
probability, input distribution, and the conditional probability can be
calculated by the RBM training. Binary encoding and continue valued methods are
discussed. The universal approximation analysis for the conditional probability
based modelling is proposed. We use two benchmark nonlinear systems to compare
our probability modelling method with the other black-box modeling methods. The
results show that this novel method is much better when there are big noises
and the system dynamics are complex.
K-Beam Minimax: Efficient Optimization for Deep Adversarial Learning
Authors: Jihun Hamm, Yung-Kyun Noh
Date: 2018-05-29 00:00:00
Proceeding: ICML 2018 7
Tasks: Domain Adaptation

Minimax optimization plays a key role in adversarial training of machine
learning algorithms, such as learning generative models, domain adaptation,
privacy preservation, and robust learning. In this paper, we demonstrate the
failure of alternating gradient descent in minimax optimization problems due to
the discontinuity of solutions of the inner maximization. To address this, we
propose a new epsilon-subgradient descent algorithm that addresses this problem
by simultaneously tracking K candidate solutions. Practically, the algorithm
can find solutions that previous saddle-point algorithms cannot find, with only
a sublinear increase of complexity in K. We analyze the conditions under which
the algorithm converges to the true solution in detail. A significant
improvement in stability and convergence speed of the algorithm is observed in
simple representative problems, GAN training, and domain-adaptation problems.
Corpus-level Fine-grained Entity Typing
Authors: Yadollah Yaghoobzadeh, Heike Adel, Hinrich Schütze
Date: 2017-08-07 00:00:00
Tasks: Entity Typing, Knowledge Base Completion

This paper addresses the problem of corpus-level entity typing, i.e.,
inferring from a large corpus that an entity is a member of a class such as
"food" or "artist". The application of entity typing we are interested in is
knowledge base completion, specifically, to learn which classes an entity is a
member of. We propose FIGMENT to tackle this problem. FIGMENT is embedding-
based and combines (i) a global model that scores based on aggregated
contextual information of an entity and (ii) a context model that first scores
the individual occurrences of an entity and then aggregates the scores. Each of
the two proposed models has some specific properties. For the global model,
learning high quality entity representations is crucial because it is the only
source used for the predictions. Therefore, we introduce representations using
name and contexts of entities on the three levels of entity, word, and
character. We show each has complementary information and a multi-level
representation is the best. For the context model, we need to use distant
supervision since the context-level labels are not available for entities.
Distant supervised labels are noisy and this harms the performance of models.
Therefore, we introduce and apply new algorithms for noise mitigation using
multi-instance learning. We show the effectiveness of our models in a large
entity typing dataset, built from Freebase.
Stochastic Wasserstein Barycenters
Authors: Sebastian Claici, Edward Chien, Justin Solomon
Date: 2018-02-15 00:00:00
Proceeding: ICML 2018 7

We present a stochastic algorithm to compute the barycenter of a set of
probability distributions under the Wasserstein metric from optimal transport.
Unlike previous approaches, our method extends to continuous input
distributions and allows the support of the barycenter to be adjusted in each
iteration. We tackle the problem without regularization, allowing us to recover
a sharp output whose support is contained within the support of the true
barycenter. We give examples where our algorithm recovers a more meaningful
barycenter than previous work. Our method is versatile and can be extended to
applications such as generating super samples from a given distribution and
recovering blue noise approximations.
Estimating Train Delays in a Large Rail Network Using a Zero Shot Markov Model
Authors: Ramashish Gaurav, Biplav Srivastava
Date: 2018-06-07 00:00:00
Tasks: regression

India runs the fourth largest railway transport network size carrying over 8
billion passengers per year. However, the travel experience of passengers is
frequently marked by delays, i.e., late arrival of trains at stations, causing
inconvenience. In a first, we study the systemic delays in train arrivals using
n-order Markov frameworks and experiment with two regression based models.
Using train running-status data collected for two years, we report on an
efficient algorithm for estimating delays at railway stations with near
accurate results. This work can help railways to manage their resources, while
also helping passengers and businesses served by them to efficiently plan their
activities.
Stochastic Block Models are a Discrete Surface Tension
Authors: Zachary M. Boyd, Mason A. Porter, Andrea L. Bertozzi
Date: 2018-06-07 00:00:00
Tasks: Clustering, Video Semantic Segmentation

Networks, which represent agents and interactions between them, arise in
myriad applications throughout the sciences, engineering, and even the
humanities. To understand large-scale structure in a network, a common task is
to cluster a network's nodes into sets called "communities", such that there
are dense connections within communities but sparse connections between them. A
popular and statistically principled method to perform such clustering is to
use a family of generative models known as stochastic block models (SBMs). In
this paper, we show that maximum likelihood estimation in an SBM is a network
analog of a well-known continuum surface-tension problem that arises from an
application in metallurgy. To illustrate the utility of this relationship, we
implement network analogs of three surface-tension algorithms, with which we
successfully recover planted community structure in synthetic networks and
which yield fascinating insights on empirical networks that we construct from
hyperspectral videos.
Deep learning based inverse method for layout design
Authors: Yu-Jie Zhang, Wenjing Ye
Date: 2018-06-07 00:00:00
Tasks: Deep Learning, Layout Design

Layout design with complex constraints is a challenging problem to solve due
to the non-uniqueness of the solution and the difficulties in incorporating the
constraints into the conventional optimization-based methods. In this paper, we
propose a design method based on the recently developed machine learning
technique, Variational Autoencoder (VAE). We utilize the learning capability of
the VAE to learn the constraints and the generative capability of the VAE to
generate design candidates that automatically satisfy all the constraints. As
such, no constraints need to be imposed during the design stage. In addition,
we show that the VAE network is also capable of learning the underlying physics
of the design problem, leading to an efficient design tool that does not need
any physical simulation once the network is constructed. We demonstrated the
performance of the method on two cases: inverse design of surface diffusion
induced morphology change and mask design for optical microlithography.