pwc-archive/papers-with-abstracts huggingface dataset:
Horovod: fast and easy distributed deep learning in TensorFlow
Authors: Alexander Sergeev, Mike Del Balso
Date: 2018-02-15 00:00:00
Tasks: Deep Learning, GPU

Training modern deep learning models requires large amounts of computation,
often provided by GPUs. Scaling computation from one GPU to many can enable
much faster training and research progress but entails two complications.
First, the training library must support inter-GPU communication. Depending on
the particular methods employed, this communication may entail anywhere from
negligible to significant overhead. Second, the user must modify his or her
training code to take advantage of inter-GPU communication. Depending on the
training library's API, the modification required may be either significant or
minimal.
  Existing methods for enabling multi-GPU training under the TensorFlow library
entail non-negligible communication overhead and require users to heavily
modify their model-building code, leading many researchers to avoid the whole
mess and stick with slower single-GPU training. In this paper we introduce
Horovod, an open source library that improves on both obstructions to scaling:
it employs efficient inter-GPU communication via ring reduction and requires
only a few lines of modification to user code, enabling faster, easier
distributed training in TensorFlow. Horovod is available under the Apache 2.0
license at https://github.com/uber/horovod
Breaking the gridlock in Mixture-of-Experts: Consistent and Efficient Algorithms
Authors: Ashok Vardhan Makkuva, Sewoong Oh, Sreeram Kannan, Pramod Viswanath
Date: 2018-02-21 00:00:00
Tasks: Ensemble Learning, Mixture-of-Experts

Mixture-of-Experts (MoE) is a widely popular model for ensemble learning and is a basic building block of highly successful modern neural networks as well as a component in Gated Recurrent Units (GRU) and Attention networks. However, present algorithms for learning MoE including the EM algorithm, and gradient descent are known to get stuck in local optima. From a theoretical viewpoint, finding an efficient and provably consistent algorithm to learn the parameters remains a long standing open problem for more than two decades. In this paper, we introduce the first algorithm that learns the true parameters of a MoE model for a wide class of non-linearities with global consistency guarantees. While existing algorithms jointly or iteratively estimate the expert parameters and the gating paramters in the MoE, we propose a novel algorithm that breaks the deadlock and can directly estimate the expert parameters by sensing its echo in a carefully designed cross-moment tensor between the inputs and the output. Once the experts are known, the recovery of gating parameters still requires an EM algorithm; however, we show that the EM algorithm for this simplified problem, unlike the joint EM algorithm, converges to the true parameters. We empirically validate our algorithm on both the synthetic and real data sets in a variety of settings, and show superior performance to standard baselines.
Constant Regret, Generalized Mixability, and Mirror Descent
Authors: Zakaria Mhammedi, Robert C. Williamson
Date: 2018-02-20 00:00:00
Proceeding: NeurIPS 2018 12
Tasks: Open-Ended Question Answering

We consider the setting of prediction with expert advice; a learner makes
predictions by aggregating those of a group of experts. Under this setting, and
for the right choice of loss function and "mixing" algorithm, it is possible
for the learner to achieve a constant regret regardless of the number of
prediction rounds. For example, a constant regret can be achieved for
\emph{mixable} losses using the \emph{aggregating algorithm}. The
\emph{Generalized Aggregating Algorithm} (GAA) is a name for a family of
algorithms parameterized by convex functions on simplices (entropies), which
reduce to the aggregating algorithm when using the \emph{Shannon entropy}
$\operatorname{S}$. For a given entropy $\Phi$, losses for which a constant
regret is possible using the \textsc{GAA} are called $\Phi$-mixable. Which
losses are $\Phi$-mixable was previously left as an open question. We fully
characterize $\Phi$-mixability and answer other open questions posed by
\cite{Reid2015}. We show that the Shannon entropy $\operatorname{S}$ is
fundamental in nature when it comes to mixability; any $\Phi$-mixable loss is
necessarily $\operatorname{S}$-mixable, and the lowest worst-case regret of the
\textsc{GAA} is achieved using the Shannon entropy. Finally, by leveraging the
connection between the \emph{mirror descent algorithm} and the update step of
the GAA, we suggest a new \emph{adaptive} generalized aggregating algorithm and
analyze its performance in terms of the regret bound.
Angle constrained path to cluster multiple manifolds
Authors: Amir Babaeian
Date: 2018-02-21 00:00:00
Tasks: Dimensionality Reduction

In this paper, we propose a method to cluster multiple intersected manifolds.
The algorithm chooses several landmark nodes randomly and then checks whether
there is an angle constrained path between each landmark node and every other
node in the neighborhood graph. When the points lie on different manifolds with
intersection they should not be connected using a smooth path, thus the angle
constraint is used to prevent connecting points from one cluster to another
one. The resulting algorithm is implemented as a simple variation of Dijkstras
algorithm used in Isomap. However, Isomap was specifically designed for
dimensionality reduction in the single-manifold setting, and in particular,
can-not handle intersections. Our method is simpler than the previous proposals
in the literature and performs comparably to the best methods, both on
simulated and some real datasets.
Optimizing Recurrent Neural Networks Architectures under Time Constraints
Authors: Junqi Jin, Ziang Yan, Kun fu, Nan Jiang, Chang-Shui Zhang
Date: 2016-08-29 00:00:00

Recurrent neural network (RNN)'s architecture is a key factor influencing its
performance. We propose algorithms to optimize hidden sizes under running time
constraint. We convert the discrete optimization into a subset selection
problem. By novel transformations, the objective function becomes submodular
and constraint becomes supermodular. A greedy algorithm with bounds is
suggested to solve the transformed problem. And we show how transformations
influence the bounds. To speed up optimization, surrogate functions are
proposed which balance exploration and exploitation. Experiments show that our
algorithms can find more accurate models or faster models than manually tuned
state-of-the-art and random search. We also compare popular RNN architectures
using our algorithms.
Neural Network Architecture Optimization through Submodularity and Supermodularity
Authors: Junqi Jin, Ziang Yan, Kun fu, Nan Jiang, Chang-Shui Zhang
Date: 2016-09-01 00:00:00

Deep learning models' architectures, including depth and width, are key
factors influencing models' performance, such as test accuracy and computation
time. This paper solves two problems: given computation time budget, choose an
architecture to maximize accuracy, and given accuracy requirement, choose an
architecture to minimize computation time. We convert this architecture
optimization into a subset selection problem. With accuracy's submodularity and
computation time's supermodularity, we propose efficient greedy optimization
algorithms. The experiments demonstrate our algorithm's ability to find more
accurate models or faster models. By analyzing architecture evolution with
growing time budget, we discuss relationships among accuracy, time and
architecture, and give suggestions on neural network architecture design.
Density-aware Single Image De-raining using a Multi-stream Dense Network
Authors: He Zhang, Vishal M. Patel
Date: 2018-02-21 00:00:00
Proceeding: CVPR 2018 6
Tasks: Density Estimation, Single Image Deraining

Single image rain streak removal is an extremely challenging problem due to
the presence of non-uniform rain densities in images. We present a novel
density-aware multi-stream densely connected convolutional neural network-based
algorithm, called DID-MDN, for joint rain density estimation and de-raining.
The proposed method enables the network itself to automatically determine the
rain-density information and then efficiently remove the corresponding
rain-streaks guided by the estimated rain-density label. To better characterize
rain-streaks with different scales and shapes, a multi-stream densely connected
de-raining network is proposed which efficiently leverages features from
different scales. Furthermore, a new dataset containing images with
rain-density labels is created and used to train the proposed density-aware
network. Extensive experiments on synthetic and real datasets demonstrate that
the proposed method achieves significant improvements over the recent
state-of-the-art methods. In addition, an ablation study is performed to
demonstrate the improvements obtained by different modules in the proposed
method. Code can be found at: https://github.com/hezhangsprinter
A note on patch-based low-rank minimization for fast image denoising
Authors: Haijuan Hu, Jacques Froment, Quansheng Liu
Date: 2015-06-28 00:00:00
Tasks: Denoising, Image Denoising, parameter estimation

Patch-based low-rank minimization for image processing attracts much
attention in recent years. The minimization of the matrix rank coupled with the
Frobenius norm data fidelity can be solved by the hard thresholding filter with
principle component analysis (PCA) or singular value decomposition (SVD). Based
on this idea, we propose a patch-based low-rank minimization method for image
denoising. The main denoising process is stated in three equivalent way: PCA,
SVD and low-rank minimization. Compared to recent patch-based sparse
representation methods, experiments demonstrate that the proposed method is
rather rapid, and it is effective for a variety of natural grayscale images and
color images, especially for texture parts in images. Further improvements of
this method are also given. In addition, due to the simplicity of this method,
we could provide an explanation of the choice of the threshold parameter,
estimation of PSNR values, and give other insights into this method.
A Study into the similarity in generator and discriminator in GAN architecture
Authors: Arjun Karuvally
Date: 2018-02-21 00:00:00

One popular generative model that has high-quality results is the Generative
Adversarial Networks(GAN). This type of architecture consists of two separate
networks that play against each other. The generator creates an output from the
input noise that is given to it. The discriminator has the task of determining
if the input to it is real or fake. This takes place constantly eventually
leads to the generator modeling the target distribution. This paper includes a
study into the actual weights learned by the network and a study into the
similarity of the discriminator and generator networks. The paper also tries to
leverage the similarity between these networks and shows that indeed both the
networks may have a similar structure with experimental evidence with a novel
shared architecture.
Direct Learning to Rank and Rerank
Authors: Cynthia Rudin, Yining Wang
Date: 2018-02-21 00:00:00
Tasks: Learning-To-Rank, Reranking

Learning-to-rank techniques have proven to be extremely useful for
prioritization problems, where we rank items in order of their estimated
probabilities, and dedicate our limited resources to the top-ranked items. This
work exposes a serious problem with the state of learning-to-rank algorithms,
which is that they are based on convex proxies that lead to poor
approximations. We then discuss the possibility of "exact" reranking algorithms
based on mathematical programming. We prove that a relaxed version of the
"exact" problem has the same optimal solution, and provide an empirical
analysis.
Measuring Sample Quality with Diffusions
Authors: Jackson Gorham, Andrew B. Duncan, Sebastian J. Vollmer, Lester Mackey
Date: 2016-11-21 00:00:00
Tasks: Diversity

Stein's method for measuring convergence to a continuous target distribution
relies on an operator characterizing the target and Stein factor bounds on the
solutions of an associated differential equation. While such operators and
bounds are readily available for a diversity of univariate targets, few
multivariate targets have been analyzed. We introduce a new class of
characterizing operators based on Ito diffusions and develop explicit
multivariate Stein factor bounds for any target with a fast-coupling Ito
diffusion. As example applications, we develop computable and
convergence-determining diffusion Stein discrepancies for log-concave,
heavy-tailed, and multimodal targets and use these quality measures to select
the hyperparameters of biased Markov chain Monte Carlo (MCMC) samplers, compare
random and deterministic quadrature rules, and quantify bias-variance tradeoffs
in approximate MCMC. Our results establish a near-linear relationship between
diffusion Stein discrepancies and Wasserstein distances, improving upon past
work even for strongly log-concave targets. The exposed relationship between
Stein factors and Markov process coupling may be of independent interest.
Solving the Conjugacy Decision Problem via Machine Learning
Authors: Jonathan Gryak, Robert M. Haralick, Delaram Kahrobaei
Date: 2017-05-30 00:00:00
Tasks: BIG-bench Machine Learning

Machine learning and pattern recognition techniques have been successfully
applied to algorithmic problems in free groups. In this paper, we seek to
extend these techniques to finitely presented non-free groups, with a
particular emphasis on polycyclic and metabelian groups that are of interest to
non-commutative cryptography.
  As a prototypical example, we utilize supervised learning methods to
construct classifiers that can solve the conjugacy decision problem, i.e.,
determine whether or not a pair of elements from a specified group are
conjugate. The accuracies of classifiers created using decision trees, random
forests, and N-tuple neural network models are evaluated for several non-free
groups. The very high accuracy of these classifiers suggests an underlying
mathematical relationship with respect to conjugacy in the tested groups.
3LC: Lightweight and Effective Traffic Compression for Distributed Machine Learning
Authors: Hyeontaek Lim, David G. Andersen, Michael Kaminsky
Date: 2018-02-21 00:00:00
Tasks: BIG-bench Machine Learning, Data Compression, GPU, Quantization

The performance and efficiency of distributed machine learning (ML) depends
significantly on how long it takes for nodes to exchange state changes.
Overly-aggressive attempts to reduce communication often sacrifice final model
accuracy and necessitate additional ML techniques to compensate for this loss,
limiting their generality. Some attempts to reduce communication incur high
computation overhead, which makes their performance benefits visible only over
slow networks.
  We present 3LC, a lossy compression scheme for state change traffic that
strikes balance between multiple goals: traffic reduction, accuracy,
computation overhead, and generality. It combines three new
techniques---3-value quantization with sparsity multiplication, quartic
encoding, and zero-run encoding---to leverage strengths of quantization and
sparsification techniques and avoid their drawbacks. It achieves a data
compression ratio of up to 39--107X, almost the same test accuracy of trained
models, and high compression speed. Distributed ML frameworks can employ 3LC
without modifications to existing ML algorithms. Our experiments show that 3LC
reduces wall-clock training time of ResNet-110--based image classifiers for
CIFAR-10 on a 10-GPU cluster by up to 16--23X compared to TensorFlow's baseline
design.
Interpreting Neural Network Judgments via Minimal, Stable, and Symbolic Corrections
Authors: Xin Zhang, Armando Solar-Lezama, Rishabh Singh
Date: 2018-02-21 00:00:00
Proceeding: NeurIPS 2018 12

We present a new algorithm to generate minimal, stable, and symbolic
corrections to an input that will cause a neural network with ReLU activations
to change its output. We argue that such a correction is a useful way to
provide feedback to a user when the network's output is different from a
desired output. Our algorithm generates such a correction by solving a series
of linear constraint satisfaction problems. The technique is evaluated on three
neural network models: one predicting whether an applicant will pay a mortgage,
one predicting whether a first-order theorem can be proved efficiently by a
solver using certain heuristics, and the final one judging whether a drawing is
an accurate rendition of a canonical drawing of a cat.
Cell Detection in Microscopy Images with Deep Convolutional Neural Network and Compressed Sensing
Authors: Yao Xue, Nilanjan Ray
Date: 2017-08-10 00:00:00
Tasks: Cell Detection, compressed sensing

The ability to automatically detect certain types of cells or cellular
subunits in microscopy images is of significant interest to a wide range of
biomedical research and clinical practices. Cell detection methods have evolved
from employing hand-crafted features to deep learning-based techniques. The
essential idea of these methods is that their cell classifiers or detectors are
trained in the pixel space, where the locations of target cells are labeled. In
this paper, we seek a different route and propose a convolutional neural
network (CNN)-based cell detection method that uses encoding of the output
pixel space. For the cell detection problem, the output space is the sparsely
labeled pixel locations indicating cell centers. We employ random projections
to encode the output space to a compressed vector of fixed dimension. Then, CNN
regresses this compressed vector from the input pixels. Furthermore, it is
possible to stably recover sparse cell locations on the output pixel space from
the predicted compressed vector using $L_1$-norm optimization. In the past,
output space encoding using compressed sensing (CS) has been used in
conjunction with linear and non-linear predictors. To the best of our
knowledge, this is the first successful use of CNN with CS-based output space
encoding. We made substantial experiments on several benchmark datasets, where
the proposed CNN + CS framework (referred to as CNNCS) achieved the highest or
at least top-3 performance in terms of F1-score, compared with other
state-of-the-art methods.
Scalable Label Propagation for Multi-relational Learning on the Tensor Product of Graphs
Authors: Zhuliu Li, Raphael Petegrosso, Shaden Smith, David Sterling, George Karypis, Rui Kuang
Date: 2018-02-20 00:00:00
Tasks: Knowledge Graphs, Relational Reasoning

Multi-relational learning on knowledge graphs infers high-order relations among the entities across the graphs. This learning task can be solved by label propagation on the tensor product of the knowledge graphs to learn the high-order relations as a tensor. In this paper, we generalize a widely used label propagation model to the normalized tensor product graph, and propose an optimization formulation and a scalable Low-rank Tensor-based Label Propagation algorithm (LowrankTLP) to infer multi-relations for two learning tasks, hyperlink prediction and multiple graph alignment. The optimization formulation minimizes the upper bound of the noisy tensor estimation error for multiple graph alignment, by learning with a subset of the eigen-pairs in the spectrum of the normalized tensor product graph. We also provide a data-dependent transductive Rademacher bound for binary hyperlink prediction. We accelerate LowrankTLP with parallel tensor computation which enables label propagation on a tensor product of 100 graphs each of size 1000 in less than half hour in the simulation. LowrankTLP was also applied to predicting the author-paper-venue hyperlinks in publication records, alignment of segmented regions across up to 26 CT-scan images and alignment of protein-protein interaction networks across multiple species. The experiments demonstrate that LowrankTLP indeed well approximates the original label propagation with better scalability and accuracy.
Web-Scale Responsive Visual Search at Bing
Authors: Houdong Hu, Yan Wang, Linjun Yang, Pavel Komlev, Li Huang, Xi Chen, Jiapei Huang, Ye Wu, Meenaz Merchant, Arun Sacheti
Date: 2018-02-14 00:00:00
Tasks: Learning-To-Rank

In this paper, we introduce a web-scale general visual search system deployed
in Microsoft Bing. The system accommodates tens of billions of images in the
index, with thousands of features for each image, and can respond in less than
200 ms. In order to overcome the challenges in relevance, latency, and
scalability in such large scale of data, we employ a cascaded learning-to-rank
framework based on various latest deep learning visual features, and deploy in
a distributed heterogeneous computing platform. Quantitative and qualitative
experiments show that our system is able to support various applications on
Bing website and apps.
Sum-Product-Quotient Networks
Authors: Or Sharir, Amnon Shashua
Date: 2017-10-12 00:00:00

We present a novel tractable generative model that extends Sum-Product
Networks (SPNs) and significantly boosts their power. We call it
Sum-Product-Quotient Networks (SPQNs), whose core concept is to incorporate
conditional distributions into the model by direct computation using quotient
nodes, e.g. $P(A|B) = \frac{P(A,B)}{P(B)}$. We provide sufficient conditions
for the tractability of SPQNs that generalize and relax the decomposable and
complete tractability conditions of SPNs. These relaxed conditions give rise to
an exponential boost to the expressive efficiency of our model, i.e. we prove
that there are distributions which SPQNs can compute efficiently but require
SPNs to be of exponential size. Thus, we narrow the gap in expressivity between
tractable graphical models and other Neural Network-based generative models.
Combinatorial Semi-Bandits with Knapsacks
Authors: Karthik Abinav Sankararaman, Aleksandrs Slivkins
Date: 2017-05-23 00:00:00
Tasks: Multi-Armed Bandits

We unify two prominent lines of work on multi-armed bandits: bandits with
knapsacks (BwK) and combinatorial semi-bandits. The former concerns limited
"resources" consumed by the algorithm, e.g., limited supply in dynamic pricing.
The latter allows a huge number of actions but assumes combinatorial structure
and additional feedback to make the problem tractable. We define a common
generalization, support it with several motivating examples, and design an
algorithm for it. Our regret bounds are comparable with those for BwK and
combinatorial semi- bandits.
Information Theory: A Tutorial Introduction
Authors: James V Stone
Date: 2018-02-16 00:00:00

Shannon's mathematical theory of communication defines fundamental limits on how much information can be transmitted between the different components of any man-made or biological system. This paper is an informal but rigorous introduction to the main ideas implicit in Shannon's theory. An annotated reading list is provided for further reading.
On the scaling of polynomial features for representation matching
Authors: Siddhartha Brahma
Date: 2018-02-20 00:00:00
Tasks: General Classification, Natural Language Inference

In many neural models, new features as polynomial functions of existing ones
are used to augment representations. Using the natural language inference task
as an example, we investigate the use of scaled polynomials of degree 2 and
above as matching features. We find that scaling degree 2 features has the
highest impact on performance, reducing classification error by 5% in the best
models.