pwc-archive/papers-with-abstracts huggingface dataset:
Linear Convergence of Gradient and Proximal-Gradient Methods Under the Polyak-Łojasiewicz Condition
Authors: Hamed Karimi, Julie Nutini, Mark Schmidt
Date: 2016-08-16 00:00:00

In 1963, Polyak proposed a simple condition that is sufficient to show a global linear convergence rate for gradient descent. This condition is a special case of the \L{}ojasiewicz inequality proposed in the same year, and it does not require strong convexity (or even convexity). In this work, we show that this much-older Polyak-\L{}ojasiewicz (PL) inequality is actually weaker than the main conditions that have been explored to show linear convergence rates without strong convexity over the last 25 years. We also use the PL inequality to give new analyses of randomized and greedy coordinate descent methods, sign-based gradient descent methods, and stochastic gradient methods in the classic setting (with decreasing or constant step-sizes) as well as the variance-reduced setting. We further propose a generalization that applies to proximal-gradient methods for non-smooth optimization, leading to simple proofs of linear convergence of these methods. Along the way, we give simple convergence results for a wide variety of problems in machine learning: least squares, logistic regression, boosting, resilient backpropagation, L1-regularization, support vector machines, stochastic dual coordinate ascent, and stochastic variance-reduced gradient methods.
Let's do it "again": A First Computational Approach to Detecting Adverbial Presupposition Triggers
Authors: Andre Cianflone, Yulan Feng, Jad Kabbara, Jackie Chi Kit Cheung
Date: 2018-06-11 00:00:00
Tasks: Language Modeling, Language Modelling, Text Generation

We introduce the task of predicting adverbial presupposition triggers such as
also and again. Solving such a task requires detecting recurring or similar
events in the discourse context, and has applications in natural language
generation tasks such as summarization and dialogue systems. We create two new
datasets for the task, derived from the Penn Treebank and the Annotated English
Gigaword corpora, as well as a novel attention mechanism tailored to this task.
Our attention mechanism augments a baseline recurrent neural network without
the need for additional trainable parameters, minimizing the added
computational cost of our mechanism. We demonstrate that our model
statistically outperforms a number of baselines, including an LSTM-based
language model.
Improving Whole Slide Segmentation Through Visual Context - A Systematic Study
Authors: Korsuk Sirinukunwattana, Nasullah Khalid Alham, Clare Verrill, Jens Rittscher
Date: 2018-06-11 00:00:00
Tasks: General Classification, image-classification, Image Classification, Segmentation

While challenging, the dense segmentation of histology images is a necessary
first step to assess changes in tissue architecture and cellular morphology.
Although specific convolutional neural network architectures have been applied
with great success to the problem, few effectively incorporate visual context
information from multiple scales. With this paper, we present a systematic
comparison of different architectures to assess how including multi-scale
information affects segmentation performance. A publicly available breast
cancer and a locally collected prostate cancer datasets are being utilised for
this study. The results support our hypothesis that visual context and scale
play a crucial role in histology image classification problems.
Can machine learning identify interesting mathematics? An exploration using empirically observed laws
Authors: Chai Wah Wu
Date: 2018-05-18 00:00:00
Tasks: BIG-bench Machine Learning

We explore the possibility of using machine learning to identify interesting
mathematical structures by using certain quantities that serve as fingerprints.
In particular, we extract features from integer sequences using two empirical
laws: Benford's law and Taylor's law and experiment with various classifiers to
identify whether a sequence is, for example, nice, important, multiplicative,
easy to compute or related to primes or palindromes.
Multi-step Reinforcement Learning: A Unifying Algorithm
Authors: Kristopher De Asis, J. Fernando Hernandez-Garcia, G. Zacharias Holland, Richard S. Sutton
Date: 2017-03-03 00:00:00
Tasks: Q-Learning, reinforcement-learning, Reinforcement Learning, Reinforcement Learning (RL)

Unifying seemingly disparate algorithmic ideas to produce better performing
algorithms has been a longstanding goal in reinforcement learning. As a primary
example, TD($\lambda$) elegantly unifies one-step TD prediction with Monte
Carlo methods through the use of eligibility traces and the trace-decay
parameter $\lambda$. Currently, there are a multitude of algorithms that can be
used to perform TD control, including Sarsa, $Q$-learning, and Expected Sarsa.
These methods are often studied in the one-step case, but they can be extended
across multiple time steps to achieve better performance. Each of these
algorithms is seemingly distinct, and no one dominates the others for all
problems. In this paper, we study a new multi-step action-value algorithm
called $Q(\sigma)$ which unifies and generalizes these existing algorithms,
while subsuming them as special cases. A new parameter, $\sigma$, is introduced
to allow the degree of sampling performed by the algorithm at each step during
its backup to be continuously varied, with Sarsa existing at one extreme (full
sampling), and Expected Sarsa existing at the other (pure expectation).
$Q(\sigma)$ is generally applicable to both on- and off-policy learning, but in
this work we focus on experiments in the on-policy case. Our results show that
an intermediate value of $\sigma$, which results in a mixture of the existing
algorithms, performs better than either extreme. The mixture can also be varied
dynamically which can result in even greater performance.
Complexity Theory for Discrete Black-Box Optimization Heuristics
Authors: Carola Doerr
Date: 2018-01-06 00:00:00
Tasks: Evolutionary Algorithms

A predominant topic in the theory of evolutionary algorithms and, more
generally, theory of randomized black-box optimization techniques is running
time analysis. Running time analysis aims at understanding the performance of a
given heuristic on a given problem by bounding the number of function
evaluations that are needed by the heuristic to identify a solution of a
desired quality. As in general algorithms theory, this running time perspective
is most useful when it is complemented by a meaningful complexity theory that
studies the limits of algorithmic solutions.
  In the context of discrete black-box optimization, several black-box
complexity models have been developed to analyze the best possible performance
that a black-box optimization algorithm can achieve on a given problem. The
models differ in the classes of algorithms to which these lower bounds apply.
This way, black-box complexity contributes to a better understanding of how
certain algorithmic choices (such as the amount of memory used by a heuristic,
its selective pressure, or properties of the strategies that it uses to create
new solution candidates) influences performance.
  In this chapter we review the different black-box complexity models that have
been proposed in the literature, survey the bounds that have been obtained for
these models, and discuss how the interplay of running time analysis and
black-box complexity can inspire new algorithmic solutions to well-researched
problems in evolutionary computation. We also discuss in this chapter several
interesting open questions for future work.
Revisiting Adversarial Risk
Authors: Arun Sai Suggala, Adarsh Prasad, Vaishnavh Nagarajan, Pradeep Ravikumar
Date: 2018-06-07 00:00:00
Tasks: image-classification, Image Classification

Recent works on adversarial perturbations show that there is an inherent
trade-off between standard test accuracy and adversarial accuracy.
Specifically, they show that no classifier can simultaneously be robust to
adversarial perturbations and achieve high standard test accuracy. However,
this is contrary to the standard notion that on tasks such as image
classification, humans are robust classifiers with low error rate. In this
work, we show that the main reason behind this confusion is the inexact
definition of adversarial perturbation that is used in the literature. To fix
this issue, we propose a slight, yet important modification to the existing
definition of adversarial perturbation. Based on the modified definition, we
show that there is no trade-off between adversarial and standard accuracies;
there exist classifiers that are robust and achieve high standard accuracy. We
further study several properties of this new definition of adversarial risk and
its relation to the existing definition.
Theory of Parameter Control for Discrete Black-Box Optimization: Provable Performance Gains Through Dynamic Parameter Choices
Authors: Benjamin Doerr, Carola Doerr
Date: 2018-04-16 00:00:00
Tasks: Evolutionary Algorithms, General Classification

Parameter control aims at realizing performance gains through a dynamic choice of the parameters which determine the behavior of the underlying optimization algorithm. In the context of evolutionary algorithms this research line has for a long time been dominated by empirical approaches. With the significant advances in running time analysis achieved in the last ten years, the parameter control question has become accessible to theoretical investigations. A number of running time results for a broad range of different parameter control mechanisms have been obtained in recent years. This book chapter surveys these works, and puts them into context, by proposing an updated classification scheme for parameter control.
Learning to Speed Up Structured Output Prediction
Authors: Xingyuan Pan, Vivek Srikumar
Date: 2018-06-11 00:00:00
Proceeding: ICML 2018 7
Tasks: Prediction, Relation Extraction

Predicting structured outputs can be computationally onerous due to the
combinatorially large output spaces. In this paper, we focus on reducing the
prediction time of a trained black-box structured classifier without losing
accuracy. To do so, we train a speedup classifier that learns to mimic a
black-box classifier under the learning-to-search approach. As the structured
classifier predicts more examples, the speedup classifier will operate as a
learned heuristic to guide search to favorable regions of the output space. We
present a mistake bound for the speedup classifier and identify inference
situations where it can independently make correct judgments without input
features. We evaluate our method on the task of entity and relation extraction
and show that the speedup classifier outperforms even greedy search in terms of
speed without loss of accuracy.
The Potential of the Return Distribution for Exploration in RL
Authors: Thomas M. Moerland, Joost Broekens, Catholijn M. Jonker
Date: 2018-06-11 00:00:00
Tasks: reinforcement-learning, Reinforcement Learning, Reinforcement Learning (RL)

This paper studies the potential of the return distribution for exploration
in deterministic reinforcement learning (RL) environments. We study network
losses and propagation mechanisms for Gaussian, Categorical and Gaussian
mixture distributions. Combined with exploration policies that leverage this
return distribution, we solve, for example, a randomized Chain task of length
100, which has not been reported before when learning with neural networks.
Multi-turn Dialogue Response Generation in an Adversarial Learning Framework
Authors: Oluwatobi Olabiyi, Alan Salimov, Anish Khazane, Erik T. Mueller
Date: 2018-05-30 00:00:00
Proceeding: WS 2019 8
Tasks: Decoder, Response Generation, Word Embeddings

We propose an adversarial learning approach for generating multi-turn dialogue responses. Our proposed framework, hredGAN, is based on conditional generative adversarial networks (GANs). The GAN's generator is a modified hierarchical recurrent encoder-decoder network (HRED) and the discriminator is a word-level bidirectional RNN that shares context and word embeddings with the generator. During inference, noise samples conditioned on the dialogue history are used to perturb the generator's latent space to generate several possible responses. The final response is the one ranked best by the discriminator. The hredGAN shows improved performance over existing methods: (1) it generalizes better than networks trained using only the log-likelihood criterion, and (2) it generates longer, more informative and more diverse responses with high utterance and topic relevance even with limited training data. This improvement is demonstrated on the Movie triples and Ubuntu dialogue datasets using both automatic and human evaluations.
Lecture Notes on Fair Division
Authors: Ulle Endriss
Date: 2018-06-11 00:00:00
Tasks: Fairness

Fair division is the problem of dividing one or several goods amongst two or
more agents in a way that satisfies a suitable fairness criterion. These Notes
provide a succinct introduction to the field. We cover three main topics.
First, we need to define what is to be understood by a "fair" allocation of
goods to individuals. We present an overview of the most important fairness
criteria (as well as the closely related criteria for economic efficiency)
developed in the literature, together with a short discussion of their
axiomatic foundations. Second, we give an introduction to cake-cutting
procedures as an example of methods for fairly dividing a single divisible
resource amongst a group of individuals. Third, we discuss the combinatorial
optimisation problem of fairly allocating a set of indivisible goods to a group
of agents, covering both centralised algorithms (similar to auctions) and a
distributed approach based on negotiation.
  While the classical literature on fair division has largely developed within
Economics, these Notes are specifically written for readers with a background
in Computer Science or similar, and who may be (or may wish to be) engaged in
research in Artificial Intelligence, Multiagent Systems, or Computational
Social Choice. References for further reading, as well as a small number of
exercises, are included.
  Notes prepared for a tutorial at the 11th European Agent Systems Summer
School (EASSS-2009), Torino, Italy, 31 August and 1 September 2009. Updated for
a tutorial at the COST-ADT Doctoral School on Computational Social Choice,
Estoril, Portugal, 9--14 April 2010.
Physical Representation-based Predicate Optimization for a Visual Analytics Database
Authors: Michael R. Anderson, Michael Cafarella, German Ros, Thomas F. Wenisch
Date: 2018-06-11 00:00:00
Tasks: GPU

Querying the content of images, video, and other non-textual data sources
requires expensive content extraction methods. Modern extraction techniques are
based on deep convolutional neural networks (CNNs) and can classify objects
within images with astounding accuracy. Unfortunately, these methods are slow:
processing a single image can take about 10 milliseconds on modern GPU-based
hardware. As massive video libraries become ubiquitous, running a content-based
query over millions of video frames is prohibitive.
  One promising approach to reduce the runtime cost of queries of visual
content is to use a hierarchical model, such as a cascade, where simple cases
are handled by an inexpensive classifier. Prior work has sought to design
cascades that optimize the computational cost of inference by, for example,
using smaller CNNs. However, we observe that there are critical factors besides
the inference time that dramatically impact the overall query time. Notably, by
treating the physical representation of the input image as part of our query
optimization---that is, by including image transforms, such as resolution
scaling or color-depth reduction, within the cascade---we can optimize data
handling costs and enable drastically more efficient classifier cascades.
  In this paper, we propose Tahoma, which generates and evaluates many
potential classifier cascades that jointly optimize the CNN architecture and
input data representation. Our experiments on a subset of ImageNet show that
Tahoma's input transformations speed up cascades by up to 35 times. We also
find up to a 98x speedup over the ResNet50 classifier with no loss in accuracy,
and a 280x speedup if some accuracy is sacrificed.
NeuroNet: Fast and Robust Reproduction of Multiple Brain Image Segmentation Pipelines
Authors: Martin Rajchl, Nick Pawlowski, Daniel Rueckert, Paul M. Matthews, Ben Glocker
Date: 2018-06-11 00:00:00
Tasks: Brain Image Segmentation, Brain Segmentation, Image Segmentation, Segmentation, Semantic Segmentation

NeuroNet is a deep convolutional neural network mimicking multiple popular
and state-of-the-art brain segmentation tools including FSL, SPM, and MALPEM.
The network is trained on 5,000 T1-weighted brain MRI scans from the UK Biobank
Imaging Study that have been automatically segmented into brain tissue and
cortical and sub-cortical structures using the standard neuroimaging pipelines.
Training a single model from these complementary and partially overlapping
label maps yields a new powerful "all-in-one", multi-output segmentation tool.
The processing time for a single subject is reduced by an order of magnitude
compared to running each individual software package. We demonstrate very good
reproducibility of the original outputs while increasing robustness to
variations in the input data. We believe NeuroNet could be an important tool in
large-scale population imaging studies and serve as a new standard in
neuroscience by reducing the risk of introducing bias when choosing a specific
software package.
Collaborative Human-AI (CHAI): Evidence-Based Interpretable Melanoma Classification in Dermoscopic Images
Authors: Noel C. F. Codella, Chung-Ching Lin, Allan Halpern, Michael Hind, Rogerio Feris, John R. Smith
Date: 2018-05-30 00:00:00
Tasks: Diagnostic, General Classification, Triplet

Automated dermoscopic image analysis has witnessed rapid growth in diagnostic
performance. Yet adoption faces resistance, in part, because no evidence is
provided to support decisions. In this work, an approach for evidence-based
classification is presented. A feature embedding is learned with CNNs,
triplet-loss, and global average pooling, and used to classify via kNN search.
Evidence is provided as both the discovered neighbors, as well as localized
image regions most relevant to measuring distance between query and neighbors.
To ensure that results are relevant in terms of both label accuracy and human
visual similarity for any skill level, a novel hierarchical triplet logic is
implemented to jointly learn an embedding according to disease labels and
non-expert similarity. Results are improved over baselines trained on disease
labels alone, as well as standard multiclass loss. Quantitative relevance of
results, according to non-expert similarity, as well as localized image
regions, are also significantly improved.
Multi-Agent Path Finding with Deadlines
Authors: Hang Ma, Glenn Wagner, Ariel Felner, Jiaoyang Li, T. K. Satish Kumar, Sven Koenig
Date: 2018-06-11 00:00:00
Tasks: Multi-Agent Path Finding

We formalize Multi-Agent Path Finding with Deadlines (MAPF-DL). The objective
is to maximize the number of agents that can reach their given goal vertices
from their given start vertices within the deadline, without colliding with
each other. We first show that MAPF-DL is NP-hard to solve optimally. We then
present two classes of optimal algorithms, one based on a reduction of MAPF-DL
to a flow problem and a subsequent compact integer linear programming
formulation of the resulting reduced abstracted multi-commodity flow network
and the other one based on novel combinatorial search algorithms. Our empirical
results demonstrate that these MAPF-DL solvers scale well and each one
dominates the other ones in different scenarios.
Universality of the stochastic block model
Authors: Jean-Gabriel Young, Guillaume St-Onge, Patrick Desrosiers, Louis J. Dubé
Date: 2018-06-11 00:00:00
Tasks: Community Detection, model, Stochastic Block Model

Mesoscopic pattern extraction (MPE) is the problem of finding a partition of
the nodes of a complex network that maximizes some objective function. Many
well-known network inference problems fall in this category, including, for
instance, community detection, core-periphery identification, and imperfect
graph coloring. In this paper, we show that the most popular algorithms
designed to solve MPE problems can in fact be understood as special cases of
the maximum likelihood formulation of the stochastic block model (SBM), or one
of its direct generalizations. These equivalence relations show that the SBM is
nearly universal with respect to MPE problems.
Matching with Text Data: An Experimental Evaluation of Methods for Matching Documents and of Measuring Match Quality
Authors: Reagan Mozer, Luke Miratrix, Aaron Russell Kaufman, L. Jason Anastasopoulos
Date: 2018-01-02 00:00:00
Tasks: Articles, Causal Inference, Text Matching

Matching for causal inference is a well-studied problem, but standard methods
fail when the units to match are text documents: the high-dimensional and rich
nature of the data renders exact matching infeasible, causes propensity scores
to produce incomparable matches, and makes assessing match quality difficult.
In this paper, we characterize a framework for matching text documents that
decomposes existing methods into: (1) the choice of text representation, and
(2) the choice of distance metric. We investigate how different choices within
this framework affect both the quantity and quality of matches identified
through a systematic multifactor evaluation experiment using human subjects.
Altogether we evaluate over 100 unique text matching methods along with 5
comparison methods taken from the literature. Our experimental results identify
methods that generate matches with higher subjective match quality than current
state-of-the-art techniques. We enhance the precision of these results by
developing a predictive model to estimate the match quality of pairs of text
documents as a function of our various distance scores. This model, which we
find successfully mimics human judgment, also allows for approximate and
unsupervised evaluation of new procedures. We then employ the identified best
method to illustrate the utility of text matching in two applications. First,
we engage with a substantive debate in the study of media bias by using text
matching to control for topic selection when comparing news articles from
thirteen news sources. We then show how conditioning on text data leads to more
precise causal inferences in an observational study examining the effects of a
medical intervention.