pwc-archive/papers-with-abstracts huggingface dataset:
Compressive Sensing Using Iterative Hard Thresholding with Low Precision Data Representation: Theory and Applications
Authors: Nezihe Merve Gürel, Kaan Kara, Alen Stojanov, Tyler Smith, Thomas Lemmin, Dan Alistarh, Markus Püschel, Ce Zhang
Date: 2018-02-14 00:00:00
Tasks: Astronomy, Compressive Sensing, CPU, Quantization

Modern scientific instruments produce vast amounts of data, which can overwhelm the processing ability of computer systems. Lossy compression of data is an intriguing solution, but comes with its own drawbacks, such as potential signal loss, and the need for careful optimization of the compression ratio. In this work, we focus on a setting where this problem is especially acute: compressive sensing frameworks for interferometry and medical imaging. We ask the following question: can the precision of the data representation be lowered for all inputs, with recovery guarantees and practical performance? Our first contribution is a theoretical analysis of the normalized Iterative Hard Thresholding (IHT) algorithm when all input data, meaning both the measurement matrix and the observation vector are quantized aggressively. We present a variant of low precision normalized {IHT} that, under mild conditions, can still provide recovery guarantees. The second contribution is the application of our quantization framework to radio astronomy and magnetic resonance imaging. We show that lowering the precision of the data can significantly accelerate image recovery. We evaluate our approach on telescope data and samples of brain images using CPU and FPGA implementations achieving up to a 9x speed-up with negligible loss of recovery quality.
Disentangling by Factorising
Authors: Hyunjik Kim, andriy mnih
Date: 2018-02-16 00:00:00
Proceeding: ICML 2018 7
Tasks: Disentanglement

We define and address the problem of unsupervised learning of disentangled representations on data generated from independent factors of variation. We propose FactorVAE, a method that disentangles by encouraging the distribution of representations to be factorial and hence independent across the dimensions. We show that it improves upon $\beta$-VAE by providing a better trade-off between disentanglement and reconstruction quality. Moreover, we highlight the problems of a commonly used disentanglement metric and introduce a new metric that does not suffer from them.
Spatiotemporal Manifold Prediction Model for Anterior Vertebral Body Growth Modulation Surgery in Idiopathic Scoliosis
Authors: William Mandel, Olivier Turcot, Dejan Knez, Stefan Parent, Samuel Kadoury
Date: 2018-06-06 00:00:00

Anterior Vertebral Body Growth Modulation (AVBGM) is a minimally invasive
surgical technique that gradually corrects spine deformities while preserving
lumbar motion. However the selection of potential surgical patients is
currently based on clinical judgment and would be facilitated by the
identification of patients responding to AVBGM prior to surgery. We introduce a
statistical framework for predicting the surgical outcomes following AVBGM in
adolescents with idiopathic scoliosis. A discriminant manifold is first
constructed to maximize the separation between responsive and non-responsive
groups of patients treated with AVBGM for scoliosis. The model then uses
subject-specific correction trajectories based on articulated transformations
in order to map spine correction profiles to a group-average piecewise-geodesic
path. Spine correction trajectories are described in a piecewise-geodesic
fashion to account for varying times at follow-up exams, regressing the curve
via a quadratic optimization process. To predict the evolution of correction, a
baseline reconstruction is projected onto the manifold, from which a
spatiotemporal regression model is built from parallel transport curves
inferred from neighboring exemplars. The model was trained on 438
reconstructions and tested on 56 subjects using 3D spine reconstructions from
follow-up exams, with the probabilistic framework yielding accurate results
with differences of 2.1 +/- 0.6deg in main curve angulation, and generating
models similar to biomechanical simulations.
Finding the bandit in a graph: Sequential search-and-stop
Authors: Pierre Perrault, Vianney Perchet, Michal Valko
Date: 2018-06-06 00:00:00
Tasks: Multi-Armed Bandits

We consider the problem where an agent wants to find a hidden object that is
randomly located in some vertex of a directed acyclic graph (DAG) according to
a fixed but possibly unknown distribution. The agent can only examine vertices
whose in-neighbors have already been examined. In this paper, we address a
learning setting where we allow the agent to stop before having found the
object and restart searching on a new independent instance of the same problem.
Our goal is to maximize the total number of hidden objects found given a time
budget. The agent can thus skip an instance after realizing that it would spend
too much time on it. Our contributions are both to the search theory and
multi-armed bandits. If the distribution is known, we provide a quasi-optimal
and efficient stationary strategy. If the distribution is unknown, we
additionally show how to sequentially approximate it and, at the same time, act
near-optimally in order to collect as many hidden objects as possible.
Deploying Deep Ranking Models for Search Verticals
Authors: Rohan Ramanath, Gungor Polatkan, Liqin Xu, Harold Lee, Bo Hu, Shan Zhou
Date: 2018-06-06 00:00:00
Tasks: BIG-bench Machine Learning, Semantic Similarity, Semantic Textual Similarity

In this paper, we present an architecture executing a complex machine
learning model such as a neural network capturing semantic similarity between a
query and a document; and deploy to a real-world production system serving
500M+users. We present the challenges that arise in a real-world system and how
we solve them. We demonstrate that our architecture provides competitive
modeling capability without any significant performance impact to the system in
terms of latency. Our modular solution and insights can be used by other
real-world search systems to realize and productionize recent gains in neural
networks.
Fast Information-theoretic Bayesian Optimisation
Authors: Binxin Ru, Mark McLeod, Diego Granziol, Michael A. Osborne
Date: 2017-11-02 00:00:00
Proceeding: ICML 2018 7
Tasks: Bayesian Optimisation

Information-theoretic Bayesian optimisation techniques have demonstrated
state-of-the-art performance in tackling important global optimisation
problems. However, current information-theoretic approaches require many
approximations in implementation, introduce often-prohibitive computational
overhead and limit the choice of kernels available to model the objective. We
develop a fast information-theoretic Bayesian Optimisation method, FITBO, that
avoids the need for sampling the global minimiser, thus significantly reducing
computational overhead. Moreover, in comparison with existing approaches, our
method faces fewer constraints on kernel choice and enjoys the merits of
dealing with the output space. We demonstrate empirically that FITBO inherits
the performance associated with information-theoretic Bayesian optimisation,
while being even faster than simpler Bayesian optimisation approaches, such as
Expected Improvement.
Deep Vessel Segmentation By Learning Graphical Connectivity
Authors: Seung Yeon Shin, Soochahn Lee, Il Dong Yun, Kyoung Mu Lee
Date: 2018-06-06 00:00:00
Tasks: Retinal Vessel Segmentation, Segmentation

We propose a novel deep-learning-based system for vessel segmentation.
Existing methods using CNNs have mostly relied on local appearances learned on
the regular image grid, without considering the graphical structure of vessel
shape. To address this, we incorporate a graph convolutional network into a
unified CNN architecture, where the final segmentation is inferred by combining
the different types of features. The proposed method can be applied to expand
any type of CNN-based vessel segmentation method to enhance the performance.
Experiments show that the proposed method outperforms the current
state-of-the-art methods on two retinal image datasets as well as a coronary
artery X-ray angiography dataset.
Celer: a Fast Solver for the Lasso with Dual Extrapolation
Authors: Mathurin Massias, Alexandre Gramfort, Joseph Salmon
Date: 2018-02-21 00:00:00
Proceeding: ICML 2018 7

Convex sparsity-inducing regularizations are ubiquitous in high-dimensional
machine learning, but solving the resulting optimization problems can be slow.
To accelerate solvers, state-of-the-art approaches consist in reducing the size
of the optimization problem at hand. In the context of regression, this can be
achieved either by discarding irrelevant features (screening techniques) or by
prioritizing features likely to be included in the support of the solution
(working set techniques). Duality comes into play at several steps in these
techniques. Here, we propose an extrapolation technique starting from a
sequence of iterates in the dual that leads to the construction of improved
dual points. This enables a tighter control of optimality as used in stopping
criterion, as well as better screening performance of Gap Safe rules. Finally,
we propose a working set strategy based on an aggressive use of Gap Safe
screening rules. Thanks to our new dual point construction, we show significant
computational speedups on multiple real-world problems.
Doubly Robust Bayesian Inference for Non-Stationary Streaming Data with $β$-Divergences
Authors: Jeremias Knoblauch, Jack Jewson, Theodoros Damoulas
Date: 2018-06-06 00:00:00
Proceeding: NeurIPS 2018
Tasks: Bayesian Inference, Change Point Detection

We present the very first robust Bayesian Online Changepoint Detection
algorithm through General Bayesian Inference (GBI) with $\beta$-divergences.
The resulting inference procedure is doubly robust for both the parameter and
the changepoint (CP) posterior, with linear time and constant space complexity.
We provide a construction for exponential models and demonstrate it on the
Bayesian Linear Regression model. In so doing, we make two additional
contributions: Firstly, we make GBI scalable using Structural Variational
approximations that are exact as $\beta \to 0$. Secondly, we give a principled
way of choosing the divergence parameter $\beta$ by minimizing expected
predictive loss on-line. Reducing False Discovery Rates of CPs from more than
90% to 0% on real world data, this offers the state of the art.
Adversarial Regression with Multiple Learners
Authors: Liang Tong, Sixie Yu, Scott Alfeld, Yevgeniy Vorobeychik
Date: 2018-06-06 00:00:00
Proceeding: ICML 2018 7
Tasks: regression

Despite the considerable success enjoyed by machine learning techniques in
practice, numerous studies demonstrated that many approaches are vulnerable to
attacks. An important class of such attacks involves adversaries changing
features at test time to cause incorrect predictions. Previous investigations
of this problem pit a single learner against an adversary. However, in many
situations an adversary's decision is aimed at a collection of learners, rather
than specifically targeted at each independently. We study the problem of
adversarial linear regression with multiple learners. We approximate the
resulting game by exhibiting an upper bound on learner loss functions, and show
that the resulting game has a unique symmetric equilibrium. We present an
algorithm for computing this equilibrium, and show through extensive
experiments that equilibrium models are significantly more robust than
conventional regularized linear regression.
Spatio-temporal Bayesian On-line Changepoint Detection with Model Selection
Authors: Jeremias Knoblauch, Theodoros Damoulas
Date: 2018-05-14 00:00:00
Proceeding: ICML 2018 7
Tasks: Change Point Detection, Model Selection

Bayesian On-line Changepoint Detection is extended to on-line model selection
and non-stationary spatio-temporal processes. We propose spatially structured
Vector Autoregressions (VARs) for modelling the process between changepoints
(CPs) and give an upper bound on the approximation error of such models. The
resulting algorithm performs prediction, model selection and CP detection
on-line. Its time complexity is linear and its space complexity constant, and
thus it is two orders of magnitudes faster than its closest competitor. In
addition, it outperforms the state of the art for multivariate data.
The Limitations of Cross-language Word Embeddings Evaluation
Authors: Amir Bakarov, Roman Suvorov, Ilya Sochenkov
Date: 2018-06-06 00:00:00
Proceeding: SEMEVAL 2018 6
Tasks: Embeddings Evaluation, Word Embeddings

The aim of this work is to explore the possible limitations of existing
methods of cross-language word embeddings evaluation, addressing the lack of
correlation between intrinsic and extrinsic cross-language evaluation methods.
To prove this hypothesis, we construct English-Russian datasets for extrinsic
and intrinsic evaluation tasks and compare performances of 5 different
cross-language models on them. The results say that the scores even on
different intrinsic benchmarks do not correlate to each other. We can conclude
that the use of human references as ground truth for cross-language word
embeddings is not proper unless one does not understand how do native speakers
process semantics in their cognition.
Causal Bandits with Propagating Inference
Authors: Akihiro Yabe, Daisuke Hatano, Hanna Sumita, Shinji Ito, Naonori Kakimura, Takuro Fukunaga, Ken-ichi Kawarabayashi
Date: 2018-06-06 00:00:00
Proceeding: ICML 2018 7

Bandit is a framework for designing sequential experiments. In each
experiment, a learner selects an arm $A \in \mathcal{A}$ and obtains an
observation corresponding to $A$. Theoretically, the tight regret lower-bound
for the general bandit is polynomial with respect to the number of arms
$|\mathcal{A}|$. This makes bandit incapable of handling an exponentially large
number of arms, hence the bandit problem with side-information is often
considered to overcome this lower bound. Recently, a bandit framework over a
causal graph was introduced, where the structure of the causal graph is
available as side-information. A causal graph is a fundamental model that is
frequently used with a variety of real problems. In this setting, the arms are
identified with interventions on a given causal graph, and the effect of an
intervention propagates throughout all over the causal graph. The task is to
find the best intervention that maximizes the expected value on a target node.
Existing algorithms for causal bandit overcame the
$\Omega(\sqrt{|\mathcal{A}|/T})$ simple-regret lower-bound; however, their
algorithms work only when the interventions $\mathcal{A}$ are localized around
a single node (i.e., an intervention propagates only to its neighbors).
  We propose a novel causal bandit algorithm for an arbitrary set of
interventions, which can propagate throughout the causal graph. We also show
that it achieves $O(\sqrt{ \gamma^*\log(|\mathcal{A}|T) / T})$ regret bound,
where $\gamma^*$ is determined by using a causal graph structure. In
particular, if the in-degree of the causal graph is bounded, then $\gamma^* =
O(N^2)$, where $N$ is the number $N$ of nodes.
TopRank: A practical algorithm for online stochastic ranking
Authors: Tor Lattimore, Branislav Kveton, Shuai Li, Csaba Szepesvari
Date: 2018-06-06 00:00:00
Proceeding: NeurIPS 2018 12
Tasks: Decision Making, Learning-To-Rank, Position, Sequential Decision Making

Online learning to rank is a sequential decision-making problem where in each
round the learning agent chooses a list of items and receives feedback in the
form of clicks from the user. Many sample-efficient algorithms have been
proposed for this problem that assume a specific click model connecting
rankings and user behavior. We propose a generalized click model that
encompasses many existing models, including the position-based and cascade
models. Our generalization motivates a novel online learning algorithm based on
topological sort, which we call TopRank. TopRank is (a) more natural than
existing algorithms, (b) has stronger regret guarantees than existing
algorithms with comparable generality, (c) has a more insightful proof that
leaves the door open to many generalizations, (d) outperforms existing
algorithms empirically.
Improving the Privacy and Accuracy of ADMM-Based Distributed Algorithms
Authors: Xueru Zhang, Mohammad Mahdi Khalili, Mingyan Liu
Date: 2018-06-06 00:00:00
Proceeding: ICML 2018 7

Alternating direction method of multiplier (ADMM) is a popular method used to
design distributed versions of a machine learning algorithm, whereby local
computations are performed on local data with the output exchanged among
neighbors in an iterative fashion. During this iterative process the leakage of
data privacy arises. A differentially private ADMM was proposed in prior work
(Zhang & Zhu, 2017) where only the privacy loss of a single node during one
iteration was bounded, a method that makes it difficult to balance the tradeoff
between the utility attained through distributed computation and privacy
guarantees when considering the total privacy loss of all nodes over the entire
iterative process. We propose a perturbation method for ADMM where the
perturbed term is correlated with the penalty parameters; this is shown to
improve the utility and privacy simultaneously. The method is based on a
modified ADMM where each node independently determines its own penalty
parameter in every iteration and decouples it from the dual updating step size.
The condition for convergence of the modified ADMM and the lower bound on the
convergence rate are also derived.
Constrained Counting and Sampling: Bridging the Gap between Theory and Practice
Authors: Kuldeep S. Meel
Date: 2018-06-06 00:00:00

Constrained counting and sampling are two fundamental problems in Computer
Science with numerous applications, including network reliability, privacy,
probabilistic reasoning, and constrained-random verification. In constrained
counting, the task is to compute the total weight, subject to a given weighting
function, of the set of solutions of the given constraints. In constrained
sampling, the task is to sample randomly, subject to a given weighting
function, from the set of solutions to a set of given constraints.
Consequently, constrained counting and sampling have been subject to intense
theoretical and empirical investigations over the years. Prior work, however,
offered either heuristic techniques with poor guarantees of accuracy or
approaches with proven guarantees but poor performance in practice.
  In this thesis, we introduce a novel hashing-based algorithmic framework for
constrained sampling and counting that combines the classical algorithmic
technique of universal hashing with the dramatic progress made in combinatorial
reasoning tools, in particular, SAT and SMT, over the past two decades. The
resulting frameworks for counting (ApproxMC2) and sampling (UniGen) can handle
formulas with up to million variables representing a significant boost up from
the prior state of the art tools' capability to handle few hundreds of
variables. If the initial set of constraints is expressed as Disjunctive Normal
Form (DNF), ApproxMC is the only known Fully Polynomial Randomized
Approximation Scheme (FPRAS) that does not involve Monte Carlo steps. By
exploiting the connection between definability of formulas and variance of the
distribution of solutions in a cell defined by 3-universal hash functions, we
introduced an algorithmic technique, MIS, that reduced the size of XOR
constraints employed in the underlying universal hash functions by as much as
two orders of magnitude.
Detecting Correlations with Little Memory and Communication
Authors: Yuval Dagan, Ohad Shamir
Date: 2018-03-04 00:00:00

We study the problem of identifying correlations in multivariate data, under
information constraints: Either on the amount of memory that can be used by the
algorithm, or the amount of communication when the data is distributed across
several machines. We prove a tight trade-off between the memory/communication
complexity and the sample complexity, implying (for example) that to detect
pairwise correlations with optimal sample complexity, the number of required
memory/communication bits is at least quadratic in the dimension. Our results
substantially improve those of Shamir [2014], which studied a similar question
in a much more restricted setting. To the best of our knowledge, these are the
first provable sample/memory/communication trade-offs for a practical
estimation problem, using standard distributions, and in the natural regime
where the memory/communication budget is larger than the size of a single data
point. To derive our theorems, we prove a new information-theoretic result,
which may be relevant for studying other information-constrained learning
problems.
A multi-scale pyramid of 3D fully convolutional networks for abdominal multi-organ segmentation
Authors: Holger R. Roth, Chen Shen, Hirohisa ODA, Takaaki Sugino, Masahiro Oda, Yuichiro Hayashi, Kazunari Misawa, Kensaku MORI
Date: 2018-06-06 00:00:00
Tasks: GPU, Organ Segmentation, Segmentation, Semantic Segmentation

Recent advances in deep learning, like 3D fully convolutional networks
(FCNs), have improved the state-of-the-art in dense semantic segmentation of
medical images. However, most network architectures require severely
downsampling or cropping the images to meet the memory limitations of today's
GPU cards while still considering enough context in the images for accurate
segmentation. In this work, we propose a novel approach that utilizes
auto-context to perform semantic segmentation at higher resolutions in a
multi-scale pyramid of stacked 3D FCNs. We train and validate our models on a
dataset of manually annotated abdominal organs and vessels from 377 clinical CT
images used in gastric surgery, and achieve promising results with close to 90%
Dice score on average. For additional evaluation, we perform separate testing
on datasets from different sources and achieve competitive results,
illustrating the robustness of the model and approach.
Size-Independent Sample Complexity of Neural Networks
Authors: Noah Golowich, Alexander Rakhlin, Ohad Shamir
Date: 2017-12-18 00:00:00

We study the sample complexity of learning neural networks, by providing new bounds on their Rademacher complexity assuming norm constraints on the parameter matrix of each layer. Compared to previous work, these complexity bounds have improved dependence on the network depth, and under some additional assumptions, are fully independent of the network size (both depth and width). These results are derived using some novel techniques, which may be of independent interest.