pwc-archive/papers-with-abstracts huggingface dataset:
Guaranteed Sufficient Decrease for Stochastic Variance Reduced Gradient Optimization
Authors: Fanhua Shang, Yuanyuan Liu, Kaiwen Zhou, James Cheng, Kelvin K. W. Ng, Yuichi Yoshida
Date: 2018-02-26 00:00:00
Tasks: Stochastic Optimization

In this paper, we propose a novel sufficient decrease technique for
stochastic variance reduced gradient descent methods such as SVRG and SAGA. In
order to make sufficient decrease for stochastic optimization, we design a new
sufficient decrease criterion, which yields sufficient decrease versions of
stochastic variance reduction algorithms such as SVRG-SD and SAGA-SD as a
byproduct. We introduce a coefficient to scale current iterate and to satisfy
the sufficient decrease property, which takes the decisions to shrink, expand
or even move in the opposite direction, and then give two specific update rules
of the coefficient for Lasso and ridge regression. Moreover, we analyze the
convergence properties of our algorithms for strongly convex problems, which
show that our algorithms attain linear convergence rates. We also provide the
convergence guarantees of our algorithms for non-strongly convex problems. Our
experimental results further verify that our algorithms achieve significantly
better performance than their counterparts.
Stochastic Zeroth-order Optimization in High Dimensions
Authors: Yining Wang, Simon Du, Sivaraman Balakrishnan, Aarti Singh
Date: 2017-10-29 00:00:00
Tasks: feature selection, Vocal Bursts Intensity Prediction

We consider the problem of optimizing a high-dimensional convex function
using stochastic zeroth-order queries. Under sparsity assumptions on the
gradients or function values, we present two algorithms: a successive
component/feature selection algorithm and a noisy mirror descent algorithm
using Lasso gradient estimates, and show that both algorithms have convergence
rates that de- pend only logarithmically on the ambient dimension of the
problem. Empirical results confirm our theoretical findings and show that the
algorithms we design outperform classical zeroth-order optimization methods in
the high-dimensional setting.
Multi-Evidence Filtering and Fusion for Multi-Label Classification, Object Detection and Semantic Segmentation Based on Weakly Supervised Learning
Authors: Weifeng Ge, Sibei Yang, Yizhou Yu
Date: 2018-02-26 00:00:00
Proceeding: CVPR 2018 6
Tasks: Clustering, General Classification, image-classification, Image Classification, Metric Learning, Multi-Label Classification, MUlTI-LABEL-ClASSIFICATION, Multi-Label Image Classification, Object, object-detection, Object Detection, Object Localization, Object Recognition, Segmentation, Semantic Segmentation, Weakly-supervised Learning, Weakly Supervised Object Detection, Weakly supervised Semantic Segmentation, Weakly-Supervised Semantic Segmentation

Supervised object detection and semantic segmentation require object or even
pixel level annotations. When there exist image level labels only, it is
challenging for weakly supervised algorithms to achieve accurate predictions.
The accuracy achieved by top weakly supervised algorithms is still
significantly lower than their fully supervised counterparts. In this paper, we
propose a novel weakly supervised curriculum learning pipeline for multi-label
object recognition, detection and semantic segmentation. In this pipeline, we
first obtain intermediate object localization and pixel labeling results for
the training images, and then use such results to train task-specific deep
networks in a fully supervised manner. The entire process consists of four
stages, including object localization in the training images, filtering and
fusing object instances, pixel labeling for the training images, and
task-specific network training. To obtain clean object instances in the
training images, we propose a novel algorithm for filtering, fusing and
classifying object instances collected from multiple solution mechanisms. In
this algorithm, we incorporate both metric learning and density-based
clustering to filter detected object instances. Experiments show that our
weakly supervised pipeline achieves state-of-the-art results in multi-label
image classification as well as weakly supervised object detection and very
competitive results in weakly supervised semantic segmentation on MS-COCO,
PASCAL VOC 2007 and PASCAL VOC 2012.
Deep Bayesian Bandits Showdown: An Empirical Comparison of Bayesian Deep Networks for Thompson Sampling
Authors: Carlos Riquelme, George Tucker, Jasper Snoek
Date: 2018-02-26 00:00:00
Proceeding: ICLR 2018 1
Tasks: Decision Making, Deep Reinforcement Learning, Multi-Armed Bandits, reinforcement-learning, Reinforcement Learning, Reinforcement Learning (RL), Sequential Decision Making, Thompson Sampling

Recent advances in deep reinforcement learning have made significant strides
in performance on applications such as Go and Atari games. However, developing
practical methods to balance exploration and exploitation in complex domains
remains largely unsolved. Thompson Sampling and its extension to reinforcement
learning provide an elegant approach to exploration that only requires access
to posterior samples of the model. At the same time, advances in approximate
Bayesian methods have made posterior approximation for flexible neural network
models practical. Thus, it is attractive to consider approximate Bayesian
neural networks in a Thompson Sampling framework. To understand the impact of
using an approximate posterior on Thompson Sampling, we benchmark
well-established and recently developed methods for approximate posterior
sampling combined with Thompson Sampling over a series of contextual bandit
problems. We found that many approaches that have been successful in the
supervised learning setting underperformed in the sequential decision-making
scenario. In particular, we highlight the challenge of adapting slowly
converging uncertainty estimates to the online setting.
Unsupervised Grammar Induction with Depth-bounded PCFG
Authors: Lifeng Jin, Finale Doshi-Velez, Timothy Miller, William Schuler, Lane Schwartz
Date: 2018-02-23 00:00:00
Proceeding: TACL 2018 1

There has been recent interest in applying cognitively or empirically
motivated bounds on recursion depth to limit the search space of grammar
induction models (Ponvert et al., 2011; Noji and Johnson, 2016; Shain et al.,
2016). This work extends this depth-bounding approach to probabilistic
context-free grammar induction (DB-PCFG), which has a smaller parameter space
than hierarchical sequence models, and therefore more fully exploits the space
reductions of depth-bounding. Results for this model on grammar acquisition
from transcribed child-directed speech and newswire text exceed or are
competitive with those of other models when evaluated on parse accuracy.
Moreover, gram- mars acquired from this model demonstrate a consistent use of
category labels, something which has not been demonstrated by other acquisition
models.
Online Learning Rate Adaptation with Hypergradient Descent
Authors: Atilim Gunes Baydin, Robert Cornish, David Martinez Rubio, Mark Schmidt, Frank Wood
Date: 2017-03-14 00:00:00
Proceeding: ICLR 2018 1
Tasks: Hyperparameter Optimization, Stochastic Optimization

We introduce a general method for improving the convergence rate of
gradient-based optimizers that is easy to implement and works well in practice.
We demonstrate the effectiveness of the method in a range of optimization
problems by applying it to stochastic gradient descent, stochastic gradient
descent with Nesterov momentum, and Adam, showing that it significantly reduces
the need for the manual tuning of the initial learning rate for these commonly
used algorithms. Our method works by dynamically updating the learning rate
during optimization using the gradient with respect to the learning rate of the
update rule itself. Computing this "hypergradient" needs little additional
computation, requires only one extra copy of the original gradient to be stored
in memory, and relies upon nothing more than what is provided by reverse-mode
automatic differentiation.
Limits on representing Boolean functions by linear combinations of simple functions: thresholds, ReLUs, and low-degree polynomials
Authors: R. Ryan Williams
Date: 2018-02-26 00:00:00

We consider the problem of representing Boolean functions exactly by "sparse"
linear combinations (over $\mathbb{R}$) of functions from some "simple" class
${\cal C}$. In particular, given ${\cal C}$ we are interested in finding
low-complexity functions lacking sparse representations. When ${\cal C}$ is the
set of PARITY functions or the set of conjunctions, this sort of problem has a
well-understood answer, the problem becomes interesting when ${\cal C}$ is
"overcomplete" and the set of functions is not linearly independent. We focus
on the cases where ${\cal C}$ is the set of linear threshold functions, the set
of rectified linear units (ReLUs), and the set of low-degree polynomials over a
finite field, all of which are well-studied in different contexts.
  We provide generic tools for proving lower bounds on representations of this
kind. Applying these, we give several new lower bounds for "semi-explicit"
Boolean functions. For example, we show there are functions in nondeterministic
quasi-polynomial time that require super-polynomial size:
  $\bullet$ Depth-two neural networks with sign activation function, a special
case of depth-two threshold circuit lower bounds.
  $\bullet$ Depth-two neural networks with ReLU activation function.
  $\bullet$ $\mathbb{R}$-linear combinations of $O(1)$-degree
$\mathbb{F}_p$-polynomials, for every prime $p$ (related to problems regarding
Higher-Order "Uncertainty Principles"). We also obtain a function in $E^{NP}$
requiring $2^{\Omega(n)}$ linear combinations.
  $\bullet$ $\mathbb{R}$-linear combinations of $ACC \circ THR$ circuits of
polynomial size (further generalizing the recent lower bounds of Murray and the
author).
  (The above is a shortened abstract. For the full abstract, see the paper.)
Large-Scale Optimal Transport and Mapping Estimation
Authors: Vivien Seguy, Bharath Bhushan Damodaran, Rémi Flamary, Nicolas Courty, Antoine Rolet, Mathieu Blondel
Date: 2017-11-07 00:00:00
Tasks: Domain Adaptation

This paper presents a novel two-step approach for the fundamental problem of
learning an optimal map from one distribution to another. First, we learn an
optimal transport (OT) plan, which can be thought as a one-to-many map between
the two distributions. To that end, we propose a stochastic dual approach of
regularized OT, and show empirically that it scales better than a recent
related approach when the amount of samples is very large. Second, we estimate
a \textit{Monge map} as a deep neural network learned by approximating the
barycentric projection of the previously-obtained OT plan. This
parameterization allows generalization of the mapping outside the support of
the input measure. We prove two theoretical stability results of regularized OT
which show that our estimations converge to the OT plan and Monge map between
the underlying continuous measures. We showcase our proposed approach on two
applications: domain adaptation and generative modeling.
Prototyping Virtual Reality Serious Games for Building Earthquake Preparedness: The Auckland City Hospital Case Study
Authors: Ruggiero Lovreglio, Vicente Gonzalez, Zhenan Feng, Robert Amor, Michael Spearpoint, Jared Thomas, Margaret Trotter, Rafael Sacks
Date: 2018-02-26 00:00:00

Enhancing evacuee safety is a key factor in reducing the number of injuries
and deaths that result from earthquakes. One way this can be achieved is by
training occupants. Virtual Reality (VR) and Serious Games (SGs), represent
novel techniques that may overcome the limitations of traditional training
approaches. VR and SGs have been examined in the fire emergency context,
however, their application to earthquake preparedness has not yet been
extensively examined. We provide a theoretical discussion of the advantages and
limitations of using VR SGs to investigate how building occupants behave during
earthquake evacuations and to train building occupants to cope with such
emergencies. We explore key design components for developing a VR SG framework:
(a) what features constitute an earthquake event, (b) which building types can
be selected and represented within the VR environment, (c) how damage to the
building can be determined and represented, (d) how non-player characters (NPC)
can be designed, and (e) what level of interaction there can be between NPC and
the human participants. We illustrate the above by presenting the Auckland City
Hospital, New Zealand as a case study, and propose a possible VR SG training
tool to enhance earthquake preparedness in public buildings.
View Selection with Geometric Uncertainty Modeling
Authors: Cheng Peng, Volkan Isler
Date: 2017-03-31 00:00:00
Tasks: 3D Reconstruction, Simultaneous Localization and Mapping

Estimating positions of world points from features observed in images is a
key problem in 3D reconstruction, image mosaicking,simultaneous localization
and mapping and structure from motion. We consider a special instance in which
there is a dominant ground plane $\mathcal{G}$ viewed from a parallel viewing
plane $\mathcal{S}$ above it. Such instances commonly arise, for example, in
aerial photography. Consider a world point $g \in \mathcal{G}$ and its worst
case reconstruction uncertainty $\varepsilon(g,\mathcal{S})$ obtained by
merging \emph{all} possible views of $g$ chosen from $\mathcal{S}$. We first
show that one can pick two views $s_p$ and $s_q$ such that the uncertainty
$\varepsilon(g,\{s_p,s_q\})$ obtained using only these two views is almost as
good as (i.e. within a small constant factor of) $\varepsilon(g,\mathcal{S})$.
Next, we extend the result to the entire ground plane $\mathcal{G}$ and show
that one can pick a small subset of $\mathcal{S'} \subseteq \mathcal{S}$ (which
grows only linearly with the area of $\mathcal{G}$) and still obtain a constant
factor approximation, for every point $g \in \mathcal{G}$, to the minimum worst
case estimate obtained by merging all views in $\mathcal{S}$. Finally, we
present a multi-resolution view selection method which extends our techniques
to non-planar scenes. We show that the method can produce rich and accurate
dense reconstructions with a small number of views. Our results provide a view
selection mechanism with provable performance guarantees which can drastically
increase the speed of scene reconstruction algorithms. In addition to
theoretical results, we demonstrate their effectiveness in an application where
aerial imagery is used for monitoring farms and orchards.
Deep Complex Networks
Authors: Chiheb Trabelsi, Olexa Bilaniuk, Ying Zhang, Dmitriy Serdyuk, Sandeep Subramanian, João Felipe Santos, Soroush Mehri, Negar Rostamzadeh, Yoshua Bengio, Christopher J. Pal
Date: 2017-05-27 00:00:00
Proceeding: ICLR 2018 1
Tasks: Image Classification, Music Transcription, Retrieval

At present, the vast majority of building blocks, techniques, and
architectures for deep learning are based on real-valued operations and
representations. However, recent work on recurrent neural networks and older
fundamental theoretical analysis suggests that complex numbers could have a
richer representational capacity and could also facilitate noise-robust memory
retrieval mechanisms. Despite their attractive properties and potential for
opening up entirely new neural architectures, complex-valued deep neural
networks have been marginalized due to the absence of the building blocks
required to design such models. In this work, we provide the key atomic
components for complex-valued deep neural networks and apply them to
convolutional feed-forward networks and convolutional LSTMs. More precisely, we
rely on complex convolutions and present algorithms for complex
batch-normalization, complex weight initialization strategies for
complex-valued neural nets and we use them in experiments with end-to-end
training schemes. We demonstrate that such complex-valued models are
competitive with their real-valued counterparts. We test deep complex models on
several computer vision tasks, on music transcription using the MusicNet
dataset and on Speech Spectrum Prediction using the TIMIT dataset. We achieve
state-of-the-art performance on these audio-related tasks.
Generalizing Distance Covariance to Measure and Test Multivariate Mutual Dependence
Authors: Ze Jin, David S. Matteson
Date: 2017-09-08 00:00:00

We propose three measures of mutual dependence between multiple random
vectors. All the measures are zero if and only if the random vectors are
mutually independent. The first measure generalizes distance covariance from
pairwise dependence to mutual dependence, while the other two measures are sums
of squared distance covariance. All the measures share similar properties and
asymptotic distributions to distance covariance, and capture non-linear and
non-monotone mutual dependence between the random vectors. Inspired by complete
and incomplete V-statistics, we define the empirical measures and simplified
empirical measures as a trade-off between the complexity and power when testing
mutual independence. Implementation of the tests is demonstrated by both
simulation results and real data examples.
Dynamic Neural Program Embedding for Program Repair
Authors: Ke Wang, Rishabh Singh, Zhendong Su
Date: 2017-11-20 00:00:00
Tasks: Fault localization, Program Repair, Program Synthesis

Neural program embeddings have shown much promise recently for a variety of
program analysis tasks, including program synthesis, program repair, fault
localization, etc. However, most existing program embeddings are based on
syntactic features of programs, such as raw token sequences or abstract syntax
trees. Unlike images and text, a program has an unambiguous semantic meaning
that can be difficult to capture by only considering its syntax (i.e.
syntactically similar pro- grams can exhibit vastly different run-time
behavior), which makes syntax-based program embeddings fundamentally limited.
This paper proposes a novel semantic program embedding that is learned from
program execution traces. Our key insight is that program states expressed as
sequential tuples of live variable values not only captures program semantics
more precisely, but also offer a more natural fit for Recurrent Neural Networks
to model. We evaluate different syntactic and semantic program embeddings on
predicting the types of errors that students make in their submissions to an
introductory programming class and two exercises on the CodeHunt education
platform. Evaluation results show that our new semantic program embedding
significantly outperforms the syntactic program embeddings based on token
sequences and abstract syntax trees. In addition, we augment a search-based
program repair system with the predictions obtained from our se- mantic
embedding, and show that search efficiency is also significantly improved.
Can a Chatbot Determine My Diet?: Addressing Challenges of Chatbot Application for Meal Recommendation
Authors: Ahmed Fadhil
Date: 2018-02-25 00:00:00
Tasks: Chatbot, Nutrition

Poor nutrition can lead to reduced immunity, increased susceptibility to
disease, impaired physical and mental development, and reduced productivity. A
conversational agent can support people as a virtual coach, however building
such systems still have its associated challenges and limitations. This paper
describes the background and motivation for chatbot systems in the context of
healthy nutrition recommendation. We discuss current challenges associated with
chatbot application, we tackled technical, theoretical, behavioural, and social
aspects of the challenges. We then propose a pipeline to be used as guidelines
by developers to implement theoretically and technically robust chatbot
systems.
SAFFRON: an adaptive algorithm for online control of the false discovery rate
Authors: Aaditya Ramdas, Tijana Zrnic, Martin Wainwright, Michael Jordan
Date: 2018-02-25 00:00:00
Proceeding: ICML 2018 7

In the online false discovery rate (FDR) problem, one observes a possibly infinite sequence of $p$-values $P_1,P_2,\dots$, each testing a different null hypothesis, and an algorithm must pick a sequence of rejection thresholds $\alpha_1,\alpha_2,\dots$ in an online fashion, effectively rejecting the $k$-th null hypothesis whenever $P_k \leq \alpha_k$. Importantly, $\alpha_k$ must be a function of the past, and cannot depend on $P_k$ or any of the later unseen $p$-values, and must be chosen to guarantee that for any time $t$, the FDR up to time $t$ is less than some pre-determined quantity $\alpha \in (0,1)$. In this work, we present a powerful new framework for online FDR control that we refer to as SAFFRON. Like older alpha-investing (AI) algorithms, SAFFRON starts off with an error budget, called alpha-wealth, that it intelligently allocates to different tests over time, earning back some wealth on making a new discovery. However, unlike older methods, SAFFRON's threshold sequence is based on a novel estimate of the alpha fraction that it allocates to true null hypotheses. In the offline setting, algorithms that employ an estimate of the proportion of true nulls are called adaptive methods, and SAFFRON can be seen as an online analogue of the famous offline Storey-BH adaptive procedure. Just as Storey-BH is typically more powerful than the Benjamini-Hochberg (BH) procedure under independence, we demonstrate that SAFFRON is also more powerful than its non-adaptive counterparts, such as LORD and other generalized alpha-investing algorithms. Further, a monotone version of the original AI algorithm is recovered as a special case of SAFFRON, that is often more stable and powerful than the original. Lastly, the derivation of SAFFRON provides a novel template for deriving new online FDR rules.
Continuous Relaxation of MAP Inference: A Nonconvex Perspective
Authors: D. Khuê Lê-Huu, Nikos Paragios
Date: 2018-02-21 00:00:00
Proceeding: CVPR 2018 6

In this paper, we study a nonconvex continuous relaxation of MAP inference in
discrete Markov random fields (MRFs). We show that for arbitrary MRFs, this
relaxation is tight, and a discrete stationary point of it can be easily
reached by a simple block coordinate descent algorithm. In addition, we study
the resolution of this relaxation using popular gradient methods, and further
propose a more effective solution using a multilinear decomposition framework
based on the alternating direction method of multipliers (ADMM). Experiments on
many real-world problems demonstrate that the proposed ADMM significantly
outperforms other nonconvex relaxation based methods, and compares favorably
with state of the art MRF optimization algorithms in different settings.
Temporal Difference Models: Model-Free Deep RL for Model-Based Control
Authors: Vitchyr Pong, Shixiang Gu, Murtaza Dalal, Sergey Levine
Date: 2018-02-25 00:00:00
Proceeding: ICLR 2018 1
Tasks: continuous-control, Continuous Control, model, Q-Learning, Reinforcement Learning, Reinforcement Learning (RL)

Model-free reinforcement learning (RL) is a powerful, general tool for learning complex behaviors. However, its sample efficiency is often impractically large for solving challenging real-world problems, even with off-policy algorithms such as Q-learning. A limiting factor in classic model-free RL is that the learning signal consists only of scalar rewards, ignoring much of the rich information contained in state transition tuples. Model-based RL uses this information, by training a predictive model, but often does not achieve the same asymptotic performance as model-free RL due to model bias. We introduce temporal difference models (TDMs), a family of goal-conditioned value functions that can be trained with model-free learning and used for model-based control. TDMs combine the benefits of model-free and model-based RL: they leverage the rich information in state transitions to learn very efficiently, while still attaining asymptotic performance that exceeds that of direct model-based RL methods. Our experimental results show that, on a range of continuous control tasks, TDMs provide a substantial improvement in efficiency compared to state-of-the-art model-based and model-free methods.