pwc-archive/papers-with-abstracts huggingface dataset:
On the Power of Truncated SVD for General High-rank Matrix Estimation Problems
Authors: Simon S. Du, Yining Wang, Aarti Singh
Date: 2017-02-22 00:00:00
Proceeding: NeurIPS 2017 12
Tasks: Matrix Completion

We show that given an estimate $\widehat{A}$ that is close to a general
high-rank positive semi-definite (PSD) matrix $A$ in spectral norm (i.e.,
$\|\widehat{A}-A\|_2 \leq \delta$), the simple truncated SVD of $\widehat{A}$
produces a multiplicative approximation of $A$ in Frobenius norm. This
observation leads to many interesting results on general high-rank matrix
estimation problems, which we briefly summarize below ($A$ is an $n\times n$
high-rank PSD matrix and $A_k$ is the best rank-$k$ approximation of $A$):
  (1) High-rank matrix completion: By observing
$\Omega(\frac{n\max\{\epsilon^{-4},k^2\}\mu_0^2\|A\|_F^2\log
n}{\sigma_{k+1}(A)^2})$ elements of $A$ where $\sigma_{k+1}\left(A\right)$ is
the $\left(k+1\right)$-th singular value of $A$ and $\mu_0$ is the incoherence,
the truncated SVD on a zero-filled matrix satisfies $\|\widehat{A}_k-A\|_F \leq
(1+O(\epsilon))\|A-A_k\|_F$ with high probability.
  (2)High-rank matrix de-noising: Let $\widehat{A}=A+E$ where $E$ is a Gaussian
random noise matrix with zero mean and $\nu^2/n$ variance on each entry. Then
the truncated SVD of $\widehat{A}$ satisfies $\|\widehat{A}_k-A\|_F \leq
(1+O(\sqrt{\nu/\sigma_{k+1}(A)}))\|A-A_k\|_F + O(\sqrt{k}\nu)$.
  (3) Low-rank Estimation of high-dimensional covariance: Given $N$
i.i.d.~samples $X_1,\cdots,X_N\sim\mathcal N_n(0,A)$, can we estimate $A$ with
a relative-error Frobenius norm bound? We show that if $N =
\Omega\left(n\max\{\epsilon^{-4},k^2\}\gamma_k(A)^2\log N\right)$ for
$\gamma_k(A)=\sigma_1(A)/\sigma_{k+1}(A)$, then $\|\widehat{A}_k-A\|_F \leq
(1+O(\epsilon))\|A-A_k\|_F$ with high probability, where
$\widehat{A}=\frac{1}{N}\sum_{i=1}^N{X_iX_i^\top}$ is the sample covariance.
Multilayer tensor factorization with applications to recommender systems
Authors: Xuan Bi, Annie Qu, Xiaotong Shen
Date: 2017-11-05 00:00:00
Tasks: Marketing, Recommendation Systems

Recommender systems have been widely adopted by electronic commerce and
entertainment industries for individualized prediction and recommendation,
which benefit consumers and improve business intelligence. In this article, we
propose an innovative method, namely the recommendation engine of multilayers
(REM), for tensor recommender systems. The proposed method utilizes the
structure of a tensor response to integrate information from multiple modes,
and creates an additional layer of nested latent factors to accommodate
between-subjects dependency. One major advantage is that the proposed method is
able to address the "cold-start" issue in the absence of information from new
customers, new products or new contexts. Specifically, it provides more
effective recommendations through sub-group information. To achieve scalable
computation, we develop a new algorithm for the proposed method, which
incorporates a maximum block improvement strategy into the cyclic
blockwise-coordinate-descent algorithm. In theory, we investigate both
algorithmic properties for global and local convergence, along with the
asymptotic consistency of estimated parameters. Finally, the proposed method is
applied in simulations and IRI marketing data with 116 million observations of
product sales. Numerical studies demonstrate that the proposed method
outperforms existing competitors in the literature.
Is Input Sparsity Time Possible for Kernel Low-Rank Approximation?
Authors: Cameron Musco, David P. Woodruff
Date: 2017-11-05 00:00:00
Proceeding: NeurIPS 2017 12

Low-rank approximation is a common tool used to accelerate kernel methods:
the $n \times n$ kernel matrix $K$ is approximated via a rank-$k$ matrix
$\tilde K$ which can be stored in much less space and processed more quickly.
In this work we study the limits of computationally efficient low-rank kernel
approximation. We show that for a broad class of kernels, including the popular
Gaussian and polynomial kernels, computing a relative error $k$-rank
approximation to $K$ is at least as difficult as multiplying the input data
matrix $A \in \mathbb{R}^{n \times d}$ by an arbitrary matrix $C \in
\mathbb{R}^{d \times k}$. Barring a breakthrough in fast matrix multiplication,
when $k$ is not too large, this requires $\Omega(nnz(A)k)$ time where $nnz(A)$
is the number of non-zeros in $A$. This lower bound matches, in many parameter
regimes, recent work on subquadratic time algorithms for low-rank approximation
of general kernels [MM16,MW17], demonstrating that these algorithms are
unlikely to be significantly improved, in particular to $O(nnz(A))$ input
sparsity runtimes. At the same time there is hope: we show for the first time
that $O(nnz(A))$ time approximation is possible for general radial basis
function kernels (e.g., the Gaussian kernel) for the closely related problem of
low-rank approximation of the kernelized dataset.
Simultaneous Joint and Object Trajectory Templates for Human Activity Recognition from 3-D Data
Authors: Saeed Ghodsi, Hoda Mohammadzade, Erfan Korki
Date: 2017-11-05 00:00:00
Tasks: Activity Recognition, Human Activity Recognition, Human-Object Interaction Detection

The availability of low-cost range sensors and the development of relatively
robust algorithms for the extraction of skeleton joint locations have inspired
many researchers to develop human activity recognition methods using the 3-D
data. In this paper, an effective method for the recognition of human
activities from the normalized joint trajectories is proposed. We represent the
actions as multidimensional signals and introduce a novel method for generating
action templates by averaging the samples in a "dynamic time" sense. Then in
order to deal with the variations in the speed and style of performing actions,
we warp the samples to the action templates by an efficient algorithm and
employ wavelet filters to extract meaningful spatiotemporal features. The
proposed method is also capable of modeling the human-object interactions, by
performing the template generation and temporal warping procedure via the joint
and object trajectories simultaneously. The experimental evaluation on several
challenging datasets demonstrates the effectiveness of our method compared to
the state-of-the-arts.
Testing and Learning on Distributions with Symmetric Noise Invariance
Authors: Ho Chung Leon Law, Christopher Yau, Dino Sejdinovic
Date: 2017-03-22 00:00:00
Proceeding: NeurIPS 2017 12
Tasks: Two-sample testing

Kernel embeddings of distributions and the Maximum Mean Discrepancy (MMD),
the resulting distance between distributions, are useful tools for fully
nonparametric two-sample testing and learning on distributions. However, it is
rarely that all possible differences between samples are of interest --
discovered differences can be due to different types of measurement noise, data
collection artefacts or other irrelevant sources of variability. We propose
distances between distributions which encode invariance to additive symmetric
noise, aimed at testing whether the assumed true underlying processes differ.
Moreover, we construct invariant features of distributions, leading to learning
algorithms robust to the impairment of the input distributions with symmetric
additive noise.
Ensemble Robustness and Generalization of Stochastic Deep Learning Algorithms
Authors: Tom Zahavy, Bingyi Kang, Alex Sivak, Jiashi Feng, Huan Xu, Shie Mannor
Date: 2016-02-07 00:00:00
Proceeding: ICLR 2018 1
Tasks: Deep Learning

The question why deep learning algorithms generalize so well has attracted
increasing research interest. However, most of the well-established approaches,
such as hypothesis capacity, stability or sparseness, have not provided
complete explanations (Zhang et al., 2016; Kawaguchi et al., 2017). In this
work, we focus on the robustness approach (Xu & Mannor, 2012), i.e., if the
error of a hypothesis will not change much due to perturbations of its training
examples, then it will also generalize well. As most deep learning algorithms
are stochastic (e.g., Stochastic Gradient Descent, Dropout, and
Bayes-by-backprop), we revisit the robustness arguments of Xu & Mannor, and
introduce a new approach, ensemble robustness, that concerns the robustness of
a population of hypotheses. Through the lens of ensemble robustness, we reveal
that a stochastic learning algorithm can generalize well as long as its
sensitiveness to adversarial perturbations is bounded in average over training
examples. Moreover, an algorithm may be sensitive to some adversarial examples
(Goodfellow et al., 2015) but still generalize well. To support our claims, we
provide extensive simulations for different deep learning algorithms and
different network architectures exhibiting a strong correlation between
ensemble robustness and the ability to generalize.
The Local Dimension of Deep Manifold
Authors: Mengxiao Zhang, Wangquan Wu, Yanren Zhang, Kun He, Tao Yu, Huan Long, John E. Hopcroft
Date: 2017-11-05 00:00:00

Based on our observation that there exists a dramatic drop for the singular
values of the fully connected layers or a single feature map of the
convolutional layer, and that the dimension of the concatenated feature vector
almost equals the summation of the dimension on each feature map, we propose a
singular value decomposition (SVD) based approach to estimate the dimension of
the deep manifolds for a typical convolutional neural network VGG19. We choose
three categories from the ImageNet, namely Persian Cat, Container Ship and
Volcano, and determine the local dimension of the deep manifolds of the deep
layers through the tangent space of a target image. Through several
augmentation methods, we found that the Gaussian noise method is closer to the
intrinsic dimension, as by adding random noise to an image we are moving in an
arbitrary dimension, and when the rank of the feature matrix of the augmented
images does not increase we are very close to the local dimension of the
manifold. We also estimate the dimension of the deep manifold based on the
tangent space for each of the maxpooling layers. Our results show that the
dimensions of different categories are close to each other and decline quickly
along the convolutional layers and fully connected layers. Furthermore, we show
that the dimensions decline quickly inside the Conv5 layer. Our work provides
new insights for the intrinsic structure of deep neural networks and helps
unveiling the inner organization of the black box of deep neural networks.
Double Q($σ$) and Q($σ, λ$): Unifying Reinforcement Learning Control Algorithms
Authors: Markus Dumke
Date: 2017-11-05 00:00:00
Tasks: Q-Learning, reinforcement-learning, Reinforcement Learning, Reinforcement Learning (RL)

Temporal-difference (TD) learning is an important field in reinforcement
learning. Sarsa and Q-Learning are among the most used TD algorithms. The
Q($\sigma$) algorithm (Sutton and Barto (2017)) unifies both. This paper
extends the Q($\sigma$) algorithm to an online multi-step algorithm Q($\sigma,
\lambda$) using eligibility traces and introduces Double Q($\sigma$) as the
extension of Q($\sigma$) to double learning. Experiments suggest that the new
Q($\sigma, \lambda$) algorithm can outperform the classical TD control methods
Sarsa($\lambda$), Q($\lambda$) and Q($\sigma$).
Properties of ABA+ for Non-Monotonic Reasoning
Authors: Kristijonas Cyras, Francesca Toni
Date: 2016-03-29 00:00:00

We investigate properties of ABA+, a formalism that extends the well studied
structured argumentation formalism Assumption-Based Argumentation (ABA) with a
preference handling mechanism. In particular, we establish desirable properties
that ABA+ semantics exhibit. These pave way to the satisfaction by ABA+ of some
(arguably) desirable principles of preference handling in argumentation and
nonmonotonic reasoning, as well as non-monotonic inference properties of ABA+
under various semantics.
Robust Speech Recognition Using Generative Adversarial Networks
Authors: Anuroop Sriram, Heewoo Jun, Yashesh Gaur, Sanjeev Satheesh
Date: 2017-11-05 00:00:00
Tasks: Generative Adversarial Network, Robust Speech Recognition, speech-recognition, Speech Recognition

This paper describes a general, scalable, end-to-end framework that uses the
generative adversarial network (GAN) objective to enable robust speech
recognition. Encoders trained with the proposed approach enjoy improved
invariance by learning to map noisy audio to the same embedding space as that
of clean audio. Unlike previous methods, the new framework does not rely on
domain expertise or simplifying assumptions as are often needed in signal
processing, and directly encourages robustness in a data-driven way. We show
the new approach improves simulated far-field speech recognition of vanilla
sequence-to-sequence models without specialized front-ends or preprocessing.
Stochastic Submodular Maximization: The Case of Coverage Functions
Authors: Mohammad Reza Karimi, Mario Lucic, Hamed Hassani, Andreas Krause
Date: 2017-11-05 00:00:00
Proceeding: NeurIPS 2017 12
Tasks: Clustering, Stochastic Optimization

Stochastic optimization of continuous objectives is at the heart of modern
machine learning. However, many important problems are of discrete nature and
often involve submodular objectives. We seek to unleash the power of stochastic
continuous optimization, namely stochastic gradient descent and its variants,
to such discrete problems. We first introduce the problem of stochastic
submodular optimization, where one needs to optimize a submodular objective
which is given as an expectation. Our model captures situations where the
discrete objective arises as an empirical risk (e.g., in the case of
exemplar-based clustering), or is given as an explicit stochastic model (e.g.,
in the case of influence maximization in social networks). By exploiting that
common extensions act linearly on the class of submodular functions, we employ
projected stochastic gradient ascent and its variants in the continuous domain,
and perform rounding to obtain discrete solutions. We focus on the rich and
widely used family of weighted coverage functions. We show that our approach
yields solutions that are guaranteed to match the optimal approximation
guarantees, while reducing the computational cost by several orders of
magnitude, as we demonstrate empirically.
Multi-label Dataless Text Classification with Topic Modeling
Authors: Daochen Zha, Chenliang Li
Date: 2017-11-05 00:00:00
Tasks: Classification, General Classification, GPU, Multi-Label Classification, MUlTI-LABEL-ClASSIFICATION, text-classification, Text Classification

Manually labeling documents is tedious and expensive, but it is essential for
training a traditional text classifier. In recent years, a few dataless text
classification techniques have been proposed to address this problem. However,
existing works mainly center on single-label classification problems, that is,
each document is restricted to belonging to a single category. In this paper,
we propose a novel Seed-guided Multi-label Topic Model, named SMTM. With a few
seed words relevant to each category, SMTM conducts multi-label classification
for a collection of documents without any labeled document. In SMTM, each
category is associated with a single category-topic which covers the meaning of
the category. To accommodate with multi-labeled documents, we explicitly model
the category sparsity in SMTM by using spike and slab prior and weak smoothing
prior. That is, without using any threshold tuning, SMTM automatically selects
the relevant categories for each document. To incorporate the supervision of
the seed words, we propose a seed-guided biased GPU (i.e., generalized Polya
urn) sampling procedure to guide the topic inference of SMTM. Experiments on
two public datasets show that SMTM achieves better classification accuracy than
state-of-the-art alternatives and even outperforms supervised solutions in some
scenarios.
Differential Evolution and Bayesian Optimisation for Hyper-Parameter Selection in Mixed-Signal Neuromorphic Circuits Applied to UAV Obstacle Avoidance
Authors: Llewyn Salt, David Howard, Giacomo Indiveri, Yulia Sandamirskaya
Date: 2017-04-17 00:00:00
Tasks: Bayesian Optimisation

The Lobula Giant Movement Detector (LGMD) is a an identified neuron of the
locust that detects looming objects and triggers its escape responses.
Understanding the neural principles and networks that lead to these fast and
robust responses can lead to the design of efficient facilitate obstacle
avoidance strategies in robotic applications. Here we present a neuromorphic
spiking neural network model of the LGMD driven by the output of a neuromorphic
Dynamic Vision Sensor (DVS), which has been optimised to produce robust and
reliable responses in the face of the constraints and variability of its mixed
signal analogue-digital circuits. As this LGMD model has many parameters, we
use the Differential Evolution (DE) algorithm to optimise its parameter space.
We also investigate the use of Self-Adaptive Differential Evolution (SADE)
which has been shown to ameliorate the difficulties of finding appropriate
input parameters for DE. We explore the use of two biological mechanisms:
synaptic plasticity and membrane adaptivity in the LGMD. We apply DE and SADE
to find parameters best suited for an obstacle avoidance system on an unmanned
aerial vehicle (UAV), and show how it outperforms state-of-the-art Bayesian
optimisation used for comparison.
Learning to Mix n-Step Returns: Generalizing lambda-Returns for Deep Reinforcement Learning
Authors: Sahil Sharma, Girish Raguvir J, Srivatsan Ramesh, Balaraman Ravindran
Date: 2017-05-21 00:00:00
Proceeding: ICLR 2018 1
Tasks: Benchmarking, Decision Making, Deep Reinforcement Learning, reinforcement-learning, Reinforcement Learning, Reinforcement Learning (RL), Sequential Decision Making

Reinforcement Learning (RL) can model complex behavior policies for
goal-directed sequential decision making tasks. A hallmark of RL algorithms is
Temporal Difference (TD) learning: value function for the current state is
moved towards a bootstrapped target that is estimated using next state's value
function. $\lambda$-returns generalize beyond 1-step returns and strike a
balance between Monte Carlo and TD learning methods. While lambda-returns have
been extensively studied in RL, they haven't been explored a lot in Deep RL.
This paper's first contribution is an exhaustive benchmarking of
lambda-returns. Although mathematically tractable, the use of exponentially
decaying weighting of n-step returns based targets in lambda-returns is a
rather ad-hoc design choice. Our second major contribution is that we propose a
generalization of lambda-returns called Confidence-based Autodidactic Returns
(CAR), wherein the RL agent learns the weighting of the n-step returns in an
end-to-end manner. This allows the agent to learn to decide how much it wants
to weigh the n-step returns based targets. In contrast, lambda-returns restrict
RL agents to use an exponentially decaying weighting scheme. Autodidactic
returns can be used for improving any RL algorithm which uses TD learning. We
empirically demonstrate that using sophisticated weighted mixtures of
multi-step returns (like CAR and lambda-returns) considerably outperforms the
use of n-step returns. We perform our experiments on the Asynchronous Advantage
Actor Critic (A3C) algorithm in the Atari 2600 domain.
Fast single image super-resolution based on sigmoid transformation
Authors: Longguang Wang, Zaiping Lin, Jinyan Gao, Xinpu Deng, Wei An
Date: 2017-08-23 00:00:00
Tasks: Image Super-Resolution, Super-Resolution

Single image super-resolution aims to generate a high-resolution image from a
single low-resolution image, which is of great significance in extensive
applications. As an ill-posed problem, numerous methods have been proposed to
reconstruct the missing image details based on exemplars or priors. In this
paper, we propose a fast and simple single image super-resolution strategy
utilizing patch-wise sigmoid transformation as an imposed sharpening
regularization term in the reconstruction, which realizes amazing
reconstruction performance. Extensive experiments compared with other
state-of-the-art approaches demonstrate the superior effectiveness and
efficiency of the proposed algorithm.
Fisher-Rao Metric, Geometry, and Complexity of Neural Networks
Authors: Tengyuan Liang, Tomaso Poggio, Alexander Rakhlin, James Stokes
Date: 2017-11-05 00:00:00
Tasks: LEMMA

We study the relationship between geometry and capacity measures for deep
neural networks from an invariance viewpoint. We introduce a new notion of
capacity --- the Fisher-Rao norm --- that possesses desirable invariance
properties and is motivated by Information Geometry. We discover an analytical
characterization of the new capacity measure, through which we establish
norm-comparison inequalities and further show that the new measure serves as an
umbrella for several existing norm-based complexity measures. We discuss upper
bounds on the generalization error induced by the proposed measure. Extensive
numerical experiments on CIFAR-10 support our theoretical findings. Our
theoretical analysis rests on a key structural lemma about partial derivatives
of multi-layer rectifier networks.
Linear Time Computation of Moments in Sum-Product Networks
Authors: Han Zhao, Geoff Gordon
Date: 2017-02-15 00:00:00
Proceeding: NeurIPS 2017 12

Bayesian online algorithms for Sum-Product Networks (SPNs) need to update
their posterior distribution after seeing one single additional instance. To do
so, they must compute moments of the model parameters under this distribution.
The best existing method for computing such moments scales quadratically in the
size of the SPN, although it scales linearly for trees. This unfortunate
scaling makes Bayesian online algorithms prohibitively expensive, except for
small or tree-structured SPNs. We propose an optimal linear-time algorithm that
works even when the SPN is a general directed acyclic graph (DAG), which
significantly broadens the applicability of Bayesian online algorithms for
SPNs. There are three key ingredients in the design and analysis of our
algorithm: 1). For each edge in the graph, we construct a linear time reduction
from the moment computation problem to a joint inference problem in SPNs. 2).
Using the property that each SPN computes a multilinear polynomial, we give an
efficient procedure for polynomial evaluation by differentiation without
expanding the network that may contain exponentially many monomials. 3). We
propose a dynamic programming method to further reduce the computation of the
moments of all the edges in the graph from quadratic to linear. We demonstrate
the usefulness of our linear time algorithm by applying it to develop a linear
time assume density filter (ADF) for SPNs.
ALICE: Towards Understanding Adversarial Learning for Joint Distribution Matching
Authors: Chunyuan Li, Hao liu, Changyou Chen, Yunchen Pu, Liqun Chen, Ricardo Henao, Lawrence Carin
Date: 2017-09-05 00:00:00
Proceeding: NeurIPS 2017 12

We investigate the non-identifiability issues associated with bidirectional
adversarial training for joint distribution matching. Within a framework of
conditional entropy, we propose both adversarial and non-adversarial approaches
to learn desirable matched joint distributions for unsupervised and supervised
tasks. We unify a broad family of adversarial models as joint distribution
matching problems. Our approach stabilizes learning of unsupervised
bidirectional adversarial learning methods. Further, we introduce an extension
for semi-supervised learning tasks. Theoretical results are validated in
synthetic data and real-world applications.