pwc-archive/papers-with-abstracts huggingface dataset:
Fast Approximation and Estimation Bounds of Kernel Quadrature for Infinitely Wide Models
Authors: Sho Sonoda
Date: 2019-02-02 00:00:00
Tasks: Model Selection, Numerical Integration

An infinitely wide model is a weighted integration $\int \varphi(x,v) d \mu(v)$ of feature maps. This model excels at handling an infinite number of features, and thus it has been adopted to the theoretical study of deep learning. Kernel quadrature is a kernel-based numerical integration scheme developed for fast approximation of expectations $\int f(x) d p(x)$. In this study, regarding the weight $\mu$ as a signed (or complex/vector-valued) distribution of parameters, we develop the general kernel quadrature (GKQ) for parameter distributions. The proposed method can achieve a fast approximation rate $O(e^{-p})$ with parameter number $p$, which is faster than the traditional Barron's rate, and a fast estimation rate $\widetilde{O}(1/n)$ with sample size $n$. As a result, we have obtained a new norm-based complexity measure for infinitely wide models. Since the GKQ implicitly conducts the empirical risk minimization, we can understand that the complexity measure also reflects the generalization performance in the gradient learning setup.
Pairwise Teacher-Student Network for Semi-Supervised Hashing
Authors: Shifeng Zhang, Jianmin Li, Bo Zhang
Date: 2019-02-02 00:00:00
Tasks: Retrieval

Hashing method maps similar high-dimensional data to binary hashcodes with
smaller hamming distance, and it has received broad attention due to its low
storage cost and fast retrieval speed. Pairwise similarity is easily obtained
and widely used for retrieval, and most supervised hashing algorithms are
carefully designed for the pairwise supervisions. As labeling all data pairs is
difficult, semi-supervised hashing is proposed which aims at learning efficient
codes with limited labeled pairs and abundant unlabeled ones. Existing methods
build graphs to capture the structure of dataset, but they are not working well
for complex data as the graph is built based on the data representations and
determining the representations of complex data is difficult. In this paper, we
propose a novel teacher-student semi-supervised hashing framework in which the
student is trained with the pairwise information produced by the teacher
network. The network follows the smoothness assumption, which achieves
consistent distances for similar data pairs so that the retrieval results are
similar for neighborhood queries. Experiments on large-scale datasets show that
the proposed method reaches impressive gain over the supervised baselines and
is superior to state-of-the-art semi-supervised hashing methods.
CodedPrivateML: A Fast and Privacy-Preserving Framework for Distributed Machine Learning
Authors: Jinhyun So, Basak Guler, A. Salman Avestimehr
Date: 2019-02-02 00:00:00
Tasks: BIG-bench Machine Learning, Privacy Preserving, regression

How to train a machine learning model while keeping the data private and secure? We present CodedPrivateML, a fast and scalable approach to this critical problem. CodedPrivateML keeps both the data and the model information-theoretically private, while allowing efficient parallelization of training across distributed workers. We characterize CodedPrivateML's privacy threshold and prove its convergence for logistic (and linear) regression. Furthermore, via extensive experiments on Amazon EC2, we demonstrate that CodedPrivateML provides significant speedup over cryptographic approaches based on multi-party computing (MPC).
Particle Flow Bayes' Rule
Authors: Xinshi Chen, Hanjun Dai, Le Song
Date: 2019-02-02 00:00:00
Tasks: Bayesian Inference, Meta-Learning, Sequential Bayesian Inference

We present a particle flow realization of Bayes' rule, where an ODE-based neural operator is used to transport particles from a prior to its posterior after a new observation. We prove that such an ODE operator exists. Its neural parameterization can be trained in a meta-learning framework, allowing this operator to reason about the effect of an individual observation on the posterior, and thus generalize across different priors, observations and to sequential Bayesian inference. We demonstrated the generalization ability of our particle flow Bayes operator in several canonical and high dimensional examples.
A Spatial-Temporal Decomposition Based Deep Neural Network for Time Series Forecasting
Authors: Reza Asadi, Amelia Regan
Date: 2019-02-02 00:00:00
Tasks: Clustering, Denoising, Time Series, Time Series Analysis, Time Series Forecasting

Spatial time series forecasting problems arise in a broad range of
applications, such as environmental and transportation problems. These problems
are challenging because of the existence of specific spatial, short-term and
long-term patterns, and the curse of dimensionality. In this paper, we propose
a deep neural network framework for large-scale spatial time series forecasting
problems. We explicitly designed the neural network architecture for capturing
various types of patterns. In preprocessing, a time series decomposition method
is applied to separately feed short-term, long-term and spatial patterns into
different components of a neural network. A fuzzy clustering method finds
cluster of neighboring time series based on similarity of time series
residuals; as they can be meaningful short-term patterns for spatial time
series. In neural network architecture, each kernel of a multi-kernel
convolution layer is applied to a cluster of time series to extract short-term
features in neighboring areas. The output of convolution layer is concatenated
by trends and followed by convolution-LSTM layer to capture long-term patterns
in larger regional areas. To make a robust prediction when faced with missing
data, an unsupervised pretrained denoising autoencoder reconstructs the output
of the model in a fine-tuning step. The experimental results illustrate the
model outperforms baseline and state of the art models in a traffic flow
prediction dataset.
Uniform-in-Time Weak Error Analysis for Stochastic Gradient Descent Algorithms via Diffusion Approximation
Authors: Yuanyuan Feng, Tingran Gao, Lei LI, Jian-Guo Liu, Yulong Lu
Date: 2019-02-02 00:00:00
Tasks: Stochastic Optimization

Diffusion approximation provides weak approximation for stochastic gradient descent algorithms in a finite time horizon. In this paper, we introduce new tools motivated by the backward error analysis of numerical stochastic differential equations into the theoretical framework of diffusion approximation, extending the validity of the weak approximation from finite to infinite time horizon. The new techniques developed in this paper enable us to characterize the asymptotic behavior of constant-step-size SGD algorithms for strongly convex objective functions, a goal previously unreachable within the diffusion approximation framework. Our analysis builds upon a truncated formal power expansion of the solution of a stochastic modified equation arising from diffusion approximation, where the main technical ingredient is a uniform-in-time weak error bound controlling the long-term behavior of the expansion coefficient functions near the global minimum. We expect these new techniques to greatly expand the range of applicability of diffusion approximation to cover wider and deeper aspects of stochastic optimization algorithms in data science.
Efficient estimation of AUC in a sliding window
Authors: Nikolaj Tatti
Date: 2019-02-02 00:00:00

In many applications, monitoring area under the ROC curve (AUC) in a sliding
window over a data stream is a natural way of detecting changes in the system.
The drawback is that computing AUC in a sliding window is expensive, especially
if the window size is large and the data flow is significant.
  In this paper we propose a scheme for maintaining an approximate AUC in a
sliding window of length $k$. More specifically, we propose an algorithm that,
given $\epsilon$, estimates AUC within $\epsilon / 2$, and can maintain this
estimate in $O((\log k) / \epsilon)$ time, per update, as the window slides.
This provides a speed-up over the exact computation of AUC, which requires
$O(k)$ time, per update. The speed-up becomes more significant as the size of
the window increases. Our estimate is based on grouping the data points
together, and using these groups to calculate AUC. The grouping is designed
carefully such that ($i$) the groups are small enough, so that the error stays
small, ($ii$) the number of groups is small, so that enumerating them is not
expensive, and ($iii$) the definition is flexible enough so that we can
maintain the groups efficiently.
  Our experimental evaluation demonstrates that the average approximation error
in practice is much smaller than the approximation guarantee $\epsilon / 2$,
and that we can achieve significant speed-ups with only a modest sacrifice in
accuracy.
Non-asymptotic Analysis of Biased Stochastic Approximation Scheme
Authors: Belhal Karimi, Blazej Miasojedow, Eric Moulines, Hoi-To Wai
Date: 2019-02-02 00:00:00
Tasks: reinforcement-learning, Reinforcement Learning, Reinforcement Learning (RL)

Stochastic approximation (SA) is a key method used in statistical learning. Recently, its non-asymptotic convergence analysis has been considered in many papers. However, most of the prior analyses are made under restrictive assumptions such as unbiased gradient estimates and convex objective function, which significantly limit their applications to sophisticated tasks such as online and reinforcement learning. These restrictions are all essentially relaxed in this work. In particular, we analyze a general SA scheme to minimize a non-convex, smooth objective function. We consider update procedure whose drift term depends on a state-dependent Markov chain and the mean field is not necessarily of gradient type, covering approximate second-order method and allowing asymptotic bias for the one-step updates. We illustrate these settings with the online EM algorithm and the policy-gradient method for average reward maximization in reinforcement learning.
Nonparametric Curve Alignment
Authors: Marwan Mattar, Michael Ross, Erik Learned-Miller
Date: 2019-02-02 00:00:00
Tasks: Clustering

Congealing is a flexible nonparametric data-driven framework for the joint
alignment of data. It has been successfully applied to the joint alignment of
binary images of digits, binary images of object silhouettes, grayscale MRI
images, color images of cars and faces, and 3D brain volumes. This research
enhances congealing to practically and effectively apply it to curve data. We
develop a parameterized set of nonlinear transformations that allow us to apply
congealing to this type of data. We present positive results on aligning
synthetic and real curve data sets and conclude with a discussion on extending
this work to simultaneous alignment and clustering.
A Question Answering System Using Graph-Pattern Association Rules (QAGPAR) On YAGO Knowledge Base
Authors: Wahyudi, Masayu Leylia Khodra, Ary Setijadi Prihatmanto, Carmadi Machbub
Date: 2019-02-02 00:00:00
Tasks: General Classification, Question Answering

A question answering system (QA System) was developed that uses graph-pattern
association rules on the YAGO knowledge base. The answer as output of the
system is provided based on a user question as input. If the answer is missing
or unavailable in the database, then graph-pattern association rules are used
to get the answer. The architecture of this question answering system is as
follows: question classification, graph component generation, query generation,
and query processing. The question answering system uses association graph
patterns in a waterfall model. In this paper, the architecture of the system is
described, specifically discussing its reasoning and performance capabilities.
The results of this research is that rules with high confidence and correct
logic produce correct answers, and vice versa
Collaborative Quantization for Cross-Modal Similarity Search
Authors: Ting Zhang, Jingdong Wang
Date: 2019-02-02 00:00:00
Proceeding: CVPR 2016 6
Tasks: Quantization

Cross-modal similarity search is a problem about designing a search system
supporting querying across content modalities, e.g., using an image to search
for texts or using a text to search for images. This paper presents a compact
coding solution for efficient search, with a focus on the quantization approach
which has already shown the superior performance over the hashing solutions in
the single-modal similarity search. We propose a cross-modal quantization
approach, which is among the early attempts to introduce quantization into
cross-modal search. The major contribution lies in jointly learning the
quantizers for both modalities through aligning the quantized representations
for each pair of image and text belonging to a document. In addition, our
approach simultaneously learns the common space for both modalities in which
quantization is conducted to enable efficient and effective search using the
Euclidean distance computed in the common space with fast distance table
lookup. Experimental results compared with several competitive algorithms over
three benchmark datasets demonstrate that the proposed approach achieves the
state-of-the-art performance.
On Generalization Error Bounds of Noisy Gradient Methods for Non-Convex Learning
Authors: Jian Li, Xuanyuan Luo, Mingda Qiao
Date: 2019-02-02 00:00:00
Proceeding: ICLR 2020 1
Tasks: Generalization Bounds, Learning Theory

Generalization error (also known as the out-of-sample error) measures how well the hypothesis learned from training data generalizes to previously unseen data. Proving tight generalization error bounds is a central question in statistical learning theory. In this paper, we obtain generalization error bounds for learning general non-convex objectives, which has attracted significant attention in recent years. We develop a new framework, termed Bayes-Stability, for proving algorithm-dependent generalization error bounds. The new framework combines ideas from both the PAC-Bayesian theory and the notion of algorithmic stability. Applying the Bayes-Stability method, we obtain new data-dependent generalization bounds for stochastic gradient Langevin dynamics (SGLD) and several other noisy gradient methods (e.g., with momentum, mini-batch and acceleration, Entropy-SGD). Our result recovers (and is typically tighter than) a recent result in Mou et al. (2018) and improves upon the results in Pensia et al. (2018). Our experiments demonstrate that our data-dependent bounds can distinguish randomly labelled data from normal data, which provides an explanation to the intriguing phenomena observed in Zhang et al. (2017a). We also study the setting where the total loss is the sum of a bounded loss and an additional \ell_2 regularization term. We obtain new generalization bounds for the continuous Langevin dynamic in this setting by developing a new Log-Sobolev inequality for the parameter distribution at any time. Our new bounds are more desirable when the noisy level of the process is not small, and do not become vacuous even when T tends to infinity.
What is Local Optimality in Nonconvex-Nonconcave Minimax Optimization?
Authors: Chi Jin, Praneeth Netrapalli, Michael. I. Jordan
Date: 2019-02-02 00:00:00
Proceeding: ICML 2020 1
Tasks: BIG-bench Machine Learning, Multi-agent Reinforcement Learning, Reinforcement Learning

Minimax optimization has found extensive applications in modern machine learning, in settings such as generative adversarial networks (GANs), adversarial training and multi-agent reinforcement learning. As most of these applications involve continuous nonconvex-nonconcave formulations, a very basic question arises---"what is a proper definition of local optima?" Most previous work answers this question using classical notions of equilibria from simultaneous games, where the min-player and the max-player act simultaneously. In contrast, most applications in machine learning, including GANs and adversarial training, correspond to sequential games, where the order of which player acts first is crucial (since minimax is in general not equal to maximin due to the nonconvex-nonconcave nature of the problems). The main contribution of this paper is to propose a proper mathematical definition of local optimality for this sequential setting---local minimax, as well as to present its properties and existence results. Finally, we establish a strong connection to a basic local search algorithm---gradient descent ascent (GDA): under mild conditions, all stable limit points of GDA are exactly local minimax points up to some degenerate points.
Supervised Quantization for Similarity Search
Authors: Xiaojuan Wang, Ting Zhang, Guo-Jun Q, Jinhui Tang, Jingdong Wang
Date: 2019-02-02 00:00:00
Proceeding: CVPR 2016 6
Tasks: feature selection, General Classification, Quantization

In this paper, we address the problem of searching for semantically similar
images from a large database. We present a compact coding approach, supervised
quantization. Our approach simultaneously learns feature selection that
linearly transforms the database points into a low-dimensional discriminative
subspace, and quantizes the data points in the transformed space. The
optimization criterion is that the quantized points not only approximate the
transformed points accurately, but also are semantically separable: the points
belonging to a class lie in a cluster that is not overlapped with other
clusters corresponding to other classes, which is formulated as a
classification problem. The experiments on several standard datasets show the
superiority of our approach over the state-of-the art supervised hashing and
unsupervised quantization algorithms.
Confidence Trigger Detection: Accelerating Real-time Tracking-by-detection Systems
Authors: Zhicheng Ding, Zhixin Lai, Siyang Li, Panfeng Li, Qikai Yang, Edward Wong
Date: 2019-02-02 00:00:00
Tasks: Autonomous Driving, object-detection, Object Detection, Object Tracking

Real-time object tracking necessitates a delicate balance between speed and accuracy, a challenge exacerbated by the computational demands of deep learning methods. In this paper, we propose Confidence-Triggered Detection (CTD), an innovative approach that strategically bypasses object detection for frames closely resembling intermediate states, leveraging tracker confidence scores. CTD not only enhances tracking speed but also preserves accuracy, surpassing existing tracking algorithms. Through extensive evaluation across various tracker confidence thresholds, we identify an optimal trade-off between tracking speed and accuracy, providing crucial insights for parameter fine-tuning and enhancing CTD's practicality in real-world scenarios. Our experiments across diverse detection models underscore the robustness and versatility of the CTD framework, demonstrating its potential to enable real-time tracking in resource-constrained environments.
Understanding Composition of Word Embeddings via Tensor Decomposition
Authors: Abraham Frandsen, Rong Ge
Date: 2019-02-02 00:00:00
Proceeding: ICLR 2019 5
Tasks: Tensor Decomposition, Word Embeddings

Word embedding is a powerful tool in natural language processing. In this
paper we consider the problem of word embedding composition \--- given vector
representations of two words, compute a vector for the entire phrase. We give a
generative model that can capture specific syntactic relations between words.
Under our model, we prove that the correlations between three words (measured
by their PMI) form a tensor that has an approximate low rank Tucker
decomposition. The result of the Tucker decomposition gives the word embeddings
as well as a core tensor, which can be used to produce better compositions of
the word embeddings. We also complement our theoretical results with
experiments that verify our assumptions, and demonstrate the effectiveness of
the new composition method.
On the Optimality of Perturbations in Stochastic and Adversarial Multi-armed Bandit Problems
Authors: Baekjin Kim, Ambuj Tewari
Date: 2019-02-02 00:00:00
Proceeding: NeurIPS 2019 12

We investigate the optimality of perturbation based algorithms in the stochastic and adversarial multi-armed bandit problems. For the stochastic case, we provide a unified regret analysis for both sub-Weibull and bounded perturbations when rewards are sub-Gaussian. Our bounds are instance optimal for sub-Weibull perturbations with parameter 2 that also have a matching lower tail bound, and all bounded support perturbations where there is sufficient probability mass at the extremes of the support. For the adversarial setting, we prove rigorous barriers against two natural solution approaches using tools from discrete choice theory and extreme value theory. Our results suggest that the optimal perturbation, if it exists, will be of Frechet-type.
Progressive Explanation Generation for Human-robot Teaming
Authors: Yu Zhang, Mehrdad Zakershahrak
Date: 2019-02-02 00:00:00
Tasks: Decision Making, Explanation Generation

Generating explanation to explain its behavior is an essential capability for
a robotic teammate. Explanations help human partners better understand the
situation and maintain trust of their teammates. Prior work on robot generating
explanations focuses on providing the reasoning behind its decision making.
These approaches, however, fail to heed the cognitive requirement of
understanding an explanation. In other words, while they provide the right
explanations from the explainer's perspective, the explainee part of the
equation is ignored. In this work, we address an important aspect along this
direction that contributes to a better understanding of a given explanation,
which we refer to as the progressiveness of explanations. A progressive
explanation improves understanding by limiting the cognitive effort required at
each step of making the explanation. As a result, such explanations are
expected to be smoother and hence easier to understand. A general formulation
of progressive explanation is presented. Algorithms are provided based on
several alternative quantifications of cognitive effort as an explanation is
being made, which are evaluated in a standard planning competition domain.
Efficient Learning of Discrete Graphical Models
Authors: Marc Vuffray, Sidhant Misra, Andrey Y. Lokhov
Date: 2019-02-02 00:00:00
Proceeding: NeurIPS 2020 12

Graphical models are useful tools for describing structured high-dimensional probability distributions. Development of efficient algorithms for learning graphical models with least amount of data remains an active research topic. Reconstruction of graphical models that describe the statistics of discrete variables is a particularly challenging problem, for which the maximum likelihood approach is intractable. In this work, we provide the first sample-efficient method based on the Interaction Screening framework that allows one to provably learn fully general discrete factor models with node-specific discrete alphabets and multi-body interactions, specified in an arbitrary basis. We identify a single condition related to model parametrization that leads to rigorous guarantees on the recovery of model structure and parameters in any error norm, and is readily verifiable for a large class of models. Importantly, our bounds make explicit distinction between parameters that are proper to the model and priors used as an input to the algorithm. Finally, we show that the Interaction Screening framework includes all models previously considered in the literature as special cases, and for which our analysis shows a systematic improvement in sample complexity.