pwc-archive/papers-with-abstracts huggingface dataset:
Learning to Solve SMT Formulas
Authors: Mislav Balunovic, Pavol Bielik, Martin Vechev
Date: 2018-12-01 00:00:00
Proceeding: NeurIPS 2018 12

We present a new approach for learning to solve SMT formulas. We phrase the challenge of solving SMT formulas as a tree search problem where at each step a transformation is applied to the input formula until the formula is solved. Our approach works in two phases: first, given a dataset of unsolved formulas we learn a policy that for each formula selects a suitable transformation to apply at each step in order to solve the formula, and second, we synthesize a strategy in the form of a loop-free program with branches. This strategy is an interpretable representation of the policy decisions and is used to guide the SMT solver to decide formulas more efficiently, without requiring any modification to the solver itself and without needing to evaluate the learned policy at inference time. We show that our approach is effective in practice - it solves 17% more formulas over a range of benchmarks and achieves up to 100x runtime improvement over a state-of-the-art SMT solver.
Lifted Weighted Mini-Bucket
Authors: Nicholas Gallo, Alexander T. Ihler
Date: 2018-12-01 00:00:00
Proceeding: NeurIPS 2018 12

Many graphical models, such as Markov Logic Networks (MLNs) with evidence, possess highly symmetric substructures but no exact symmetries.  Unfortunately, there are few principled methods that exploit these symmetric substructures to perform efficient approximate inference.  In this paper, we present a lifted variant of the Weighted Mini-Bucket elimination algorithm which provides a principled way to (i) exploit the highly symmetric substructure of MLN models, and (ii) incorporate high-order inference terms which are necessary for high quality approximate inference.  Our method has significant control over the accuracy-time trade-off of the approximation, allowing us to generate any-time approximations.  Experimental results demonstrate the utility of this class of approximations, especially in models with strong repulsive potentials.
Convex Elicitation of Continuous Properties
Authors: Jessica Finocchiaro, Rafael Frongillo
Date: 2018-12-01 00:00:00
Proceeding: NeurIPS 2018 12

A property or statistic of a distribution is said to be elicitable if it can be expressed as the minimizer of some loss function in expectation. Recent work shows that continuous real-valued properties are elicitable if and only if they are identifiable, meaning the set of distributions with the same property value can be described by linear constraints. From a practical standpoint, one may ask for which such properties do there exist convex loss functions. In this paper, in a finite-outcome setting, we show that in fact every elicitable real-valued property can be elicited by a convex loss function. Our proof is constructive, and leads to convex loss functions for new properties.
Temporal alignment and latent Gaussian process factor inference in population spike trains
Authors: Lea Duncker, Maneesh Sahani
Date: 2018-12-01 00:00:00
Proceeding: NeurIPS 2018 12
Tasks: Gaussian Processes

We introduce a novel scalable approach to identifying common latent structure in neural population spike-trains, which allows for variability both in the trajectory and in the rate of progression of the underlying computation. Our approach is based on shared latent Gaussian processes (GPs) which are combined linearly, as in the Gaussian Process Factor Analysis (GPFA) algorithm. We extend GPFA to handle unbinned spike-train data by incorporating a continuous time point-process likelihood model, achieving scalability with a sparse variational approximation. Shared variability is separated into terms that express condition dependence, as well as trial-to-trial variation in trajectories. Finally, we introduce a nested GP formulation to capture variability in the rate of evolution along the trajectory. We show that the new method learns to recover latent trajectories in synthetic data, and can accurately identify the trial-to-trial timing of movement-related parameters from motor cortical data without any supervision.
Discretely Relaxing Continuous Variables for tractable Variational Inference
Authors: Trefor Evans, Prasanth Nair
Date: 2018-12-01 00:00:00
Proceeding: NeurIPS 2018 12
Tasks: Variational Inference

We explore a new research direction in Bayesian variational inference with discrete latent variable priors where we exploit Kronecker matrix algebra for efficient and exact computations of the evidence lower bound (ELBO). The proposed "DIRECT" approach has several advantages over its predecessors; (i) it can exactly compute ELBO gradients (i.e. unbiased, zero-variance gradient estimates), eliminating the need for high-variance stochastic gradient estimators and enabling the use of quasi-Newton optimization methods; (ii) its training complexity is independent of the number of training points, permitting inference on large datasets; and (iii) its posterior samples consist of sparse and low-precision quantized integers which permit fast inference on hardware limited devices. In addition, our DIRECT models can exactly compute statistical moments of the parameterized predictive posterior without relying on Monte Carlo sampling. The DIRECT approach is not practical for all likelihoods, however, we identify a popular model structure which is practical, and demonstrate accurate inference using latent variables discretized as extremely low-precision 4-bit quantized integers. While the ELBO computations considered in the numerical studies require over 10^2352 log-likelihood evaluations, we train on datasets with over two-million points in just seconds.
Learning a Warping Distance from Unlabeled Time Series Using Sequence Autoencoders
Authors: Abubakar Abid, James Y. Zou
Date: 2018-12-01 00:00:00
Proceeding: NeurIPS 2018 12
Tasks: Dynamic Time Warping, Time Series, Time Series Analysis

Measuring similarities between unlabeled time series trajectories is an important problem in many domains such as medicine, economics, and vision. It is often unclear what is the appropriate metric to use because of the complex nature of noise in the trajectories (e.g. different sampling rates or outliers). Experts typically hand-craft or manually select a specific metric, such as Dynamic Time Warping (DTW), to apply on their data. In this paper, we propose an end-to-end framework, autowarp, that optimizes and learns a good metric given unlabeled trajectories. We define a flexible and differentiable family of warping metrics, which encompasses common metrics such as DTW, Edit Distance, Euclidean, etc. Autowarp then leverages the representation power of sequence autoencoders to optimize for a member of this warping family. The output is an metric which is easy to interpret and can be robustly learned from relatively few  trajectories. In systematic experiments across different domains, we show that autowarp often outperforms hand-crafted trajectory similarity metrics.
Regret Bounds for Online Portfolio Selection with a Cardinality Constraint
Authors: Shinji Ito, Daisuke Hatano, Sumita Hanna, Akihiro Yabe, Takuro Fukunaga, Naonori Kakimura, Ken-ichi Kawarabayashi
Date: 2018-12-01 00:00:00
Proceeding: NeurIPS 2018 12
Tasks: Computational Efficiency, Decision Making, Sequential Decision Making

Online portfolio selection is a sequential decision-making problem in which a learner repetitively selects a portfolio over a set of assets, aiming to maximize long-term return. In this paper, we study the problem with the cardinality constraint that the number of assets in a portfolio is restricted to be at most k, and consider two scenarios: (i) in the full-feedback setting, the learner can observe price relatives (rates of return to cost) for all assets, and (ii) in the bandit-feedback setting, the learner can observe price relatives only for invested assets. We propose efficient algorithms for these scenarios that achieve sublinear regrets. We also provide regret (statistical) lower bounds for both scenarios which nearly match the upper bounds when k is a constant. In addition, we give a computational lower bound which implies that no algorithm maintains both computational efficiency, as well as a small regret upper bound.
Sketching Method for Large Scale Combinatorial Inference
Authors: Wei Sun, Junwei Lu, Han Liu
Date: 2018-12-01 00:00:00
Proceeding: NeurIPS 2018 12
Tasks: regression

We present computationally efficient algorithms to test various combinatorial structures of large-scale graphical models. In order to test the hypotheses on their topological structures, we propose two adjacency matrix sketching frameworks: neighborhood sketching and subgraph sketching. The neighborhood sketching algorithm is proposed to test the connectivity of graphical models. This algorithm randomly subsamples vertices and conducts neighborhood regression and screening. The global sketching algorithm is proposed to test the topological properties requiring exponential computation complexity, especially testing the chromatic number and the maximum clique. This algorithm infers the corresponding property based on the sampled subgraph. Our algorithms are shown to substantially accelerate the computation of existing methods. We validate our theory and method through both synthetic simulations and a real application in neuroscience.
Connecting Optimization and Regularization Paths
Authors: Arun Suggala, Adarsh Prasad, Pradeep K. Ravikumar
Date: 2018-12-01 00:00:00
Proceeding: NeurIPS 2018 12

We study the implicit regularization properties of optimization techniques by explicitly connecting their optimization paths to the regularization paths of ``corresponding'' regularized problems. This surprising connection shows that iterates of optimization techniques such as gradient descent and mirror descent are \emph{pointwise} close to solutions of appropriately regularized objectives. While such a tight connection between optimization and regularization is of independent intellectual interest, it also has important implications for machine learning: we can port results from regularized estimators to optimization, and vice versa. We investigate one key consequence, that borrows from the well-studied analysis of regularized estimators, to then obtain tight excess risk bounds of the iterates generated by optimization techniques.
Fully Neural Network Based Speech Recognition on Mobile and Embedded Devices
Authors: Jinhwan Park, Yoonho Boo, Iksoo Choi, Sungho Shin, Wonyong Sung
Date: 2018-12-01 00:00:00
Proceeding: NeurIPS 2018 12
Tasks: Automatic Speech Recognition, Automatic Speech Recognition (ASR), GPU, speech-recognition, Speech Recognition

Real-time automatic speech recognition (ASR) on mobile and embedded devices has been of great interests for many years.  We present real-time speech recognition on smartphones or embedded systems by employing recurrent neural network (RNN) based acoustic models, RNN based language models, and beam-search decoding. The acoustic model is end-to-end trained with connectionist temporal classification (CTC) loss. The RNN implementation on embedded devices can suffer from excessive DRAM accesses because the parameter size of a neural network usually exceeds that of the cache memory and the parameters are used only once for each time step. To remedy this problem, we employ a multi-time step parallelization approach that computes multiple output samples at a time with the parameters fetched from the DRAM. Since the number of DRAM accesses can be reduced in proportion to the number of parallelization steps, we can achieve a high processing speed. However, conventional RNNs, such as long short-term memory (LSTM) or gated recurrent unit (GRU), do not permit multi-time step parallelization. We construct an acoustic model by combining simple recurrent units (SRUs) and depth-wise 1-dimensional convolution layers for multi-time step parallelization. Both the character and word piece models are developed for acoustic modeling, and the corresponding RNN based language models are used for beam search decoding. We achieve a competitive WER for WSJ corpus using the entire model size of around 15MB and achieve real-time speed using only a single core ARM without GPU or special hardware.
Robust Subspace Approximation in a Stream
Authors: Roie Levin, Anish Prasad Sevekari, David Woodruff
Date: 2018-12-01 00:00:00
Proceeding: NeurIPS 2018 12
Tasks: Dimensionality Reduction

We study robust subspace estimation in the streaming and distributed settings. Given a set of n data points {a_i}_{i=1}^n in R^d and an integer k, we wish to find a linear subspace S of dimension k for which sum_i M(dist(S, a_i)) is minimized, where dist(S,x) := min_{y in S} |x-y|_2, and M() is some loss function. When M is the identity function, S gives a subspace that is more robust to outliers than that provided by the truncated SVD. Though the problem is NP-hard, it is approximable within a (1+epsilon) factor in polynomial time when k and epsilon are constant.
	We give the first sublinear approximation algorithm for this problem in the turnstile streaming and arbitrary partition distributed models, achieving the same time guarantees as in the offline case. Our algorithm is the first based entirely on oblivious dimensionality reduction, and significantly simplifies prior methods for this problem, which held in neither the streaming nor distributed models.
Mean Field for the Stochastic Blockmodel: Optimization Landscape and Convergence Issues
Authors: Soumendu Sundar Mukherjee, Purnamrita Sarkar, Y. X. Rachel Wang, Bowei Yan
Date: 2018-12-01 00:00:00
Proceeding: NeurIPS 2018 12
Tasks: Bayesian Inference, Community Detection

Variational approximation has been widely used in large-scale Bayesian inference recently, the simplest kind of which involves imposing a mean field assumption to approximate complicated latent structures. Despite the computational scalability of mean field, theoretical studies of its loss function surface and the convergence behavior of iterative updates for optimizing the loss are far from complete. In this paper, we focus on the problem of community detection for a simple two-class Stochastic Blockmodel (SBM). Using batch co-ordinate ascent (BCAVI) for updates, we give a complete characterization of all the critical points and show different convergence behaviors with respect to initializations. When the parameters are known, we show a significant proportion of random initializations will converge to ground truth. On the other hand, when the parameters themselves need to be estimated, a random initialization will converge to an uninformative local optimum.
Analysis of Krylov Subspace Solutions of Regularized Non-Convex Quadratic Problems
Authors: Yair Carmon, John C. Duchi
Date: 2018-12-01 00:00:00
Proceeding: NeurIPS 2018 12

We provide convergence rates for Krylov subspace solutions to the trust-region and cubic-regularized (nonconvex) quadratic problems. Such solutions may be efficiently computed by the Lanczos method and have long been used in practice. We prove error bounds of the form $1/t^2$ and $e^{-4t/\sqrt{\kappa}}$, where $\kappa$ is a condition number for the problem, and $t$ is the Krylov subspace order (number of Lanczos iterations). We also provide lower bounds showing that our analysis is sharp.
Fast and Effective Robustness Certification
Authors: Gagandeep Singh, Timon Gehr, Matthew Mirman, Markus Püschel, Martin Vechev
Date: 2018-12-01 00:00:00
Proceeding: NeurIPS 2018 12

We present a new method and system, called DeepZ, for certifying neural network
robustness based on abstract interpretation. Compared to state-of-the-art automated
verifiers for neural networks, DeepZ: (i) handles ReLU, Tanh and Sigmoid activation functions, (ii) supports feedforward and convolutional architectures, (iii)
is significantly more scalable and precise, and (iv) and is sound with respect to
floating point arithmetic. These benefits are due to carefully designed approximations tailored to the setting of neural networks. As an example, DeepZ achieves a
verification accuracy of 97% on a large network with 88,500 hidden units under
$L_{\infty}$ attack with $\epsilon = 0.1$ with an average runtime of 133 seconds.
Support Recovery for Orthogonal Matching Pursuit: Upper and Lower bounds
Authors: Raghav Somani, Chirag Gupta, Prateek Jain, Praneeth Netrapalli
Date: 2018-12-01 00:00:00
Proceeding: NeurIPS 2018 12
Tasks: Generalization Bounds, regression

This paper studies the problem of sparse regression where the goal is to learn a sparse vector that best optimizes a given objective function. Under the assumption that the objective function satisfies restricted strong convexity (RSC), we analyze orthogonal matching pursuit (OMP), a greedy algorithm that is used heavily in applications, and obtain support recovery result as well as a tight generalization error bound for OMP. Furthermore, we obtain lower bounds for OMP, showing that both our results on support recovery and generalization error are tight up to logarithmic factors. To the best of our knowledge, these support recovery and generalization bounds are the first such matching upper and lower bounds (up to logarithmic factors) for {\em any} sparse regression algorithm under the RSC assumption.
Multi-value Rule Sets for Interpretable Classification with Feature-Efficient Representations
Authors: Tong Wang
Date: 2018-12-01 00:00:00
Proceeding: NeurIPS 2018 12
Tasks: Form, General Classification

We present the Multi-value Rule Set (MRS) for interpretable
classification with feature efficient presentations. Compared to
rule sets built from single-value rules, MRS adopts a more
generalized form of association rules that allows multiple values
in a condition. Rules of this form are more concise than classical
single-value rules in capturing and describing patterns in data.
Our formulation also pursues a higher efficiency of feature utilization,
which reduces possible cost in data collection and storage.
We propose a Bayesian framework for formulating an MRS model
and develop an efficient inference method for learning a maximum
a posteriori, incorporating theoretically grounded bounds to iteratively
reduce the search space and improve the search efficiency.
Experiments on synthetic and real-world data demonstrate that
MRS models have significantly smaller complexity and fewer features
than baseline models while being competitive in predictive
accuracy.
MixLasso: Generalized Mixed Regression via Convex Atomic-Norm Regularization
Authors: Ian En-Hsu Yen, Wei-Cheng Lee, Kai Zhong, Sung-En Chang, Pradeep K. Ravikumar, Shou-De Lin
Date: 2018-12-01 00:00:00
Proceeding: NeurIPS 2018 12
Tasks: regression

We consider a generalization of mixed regression where the response is an additive combination of several mixture components. Standard mixed regression is a special case where each response is generated from exactly one component. Typical approaches to the mixture regression problem employ local search methods such as Expectation Maximization (EM) that are prone to spurious local optima. On the other hand, a number of recent theoretically-motivated \emph{Tensor-based methods} either have high sample complexity, or require the knowledge of the input distribution, which is not available in most of practical situations. In this work, we study a novel convex estimator \emph{MixLasso} for the estimation of generalized mixed regression, based on an atomic norm specifically constructed to regularize the number of mixture components. Our algorithm gives a risk bound that trades off between prediction accuracy and model sparsity without imposing stringent assumptions on the input/output distribution, and can be easily adapted to the case of non-linear functions. In our numerical experiments on mixtures of linear as well as nonlinear regressions, the proposed method yields high-quality solutions in a wider range of settings than existing approaches.
Topkapi: Parallel and Fast Sketches for Finding Top-K Frequent Elements
Authors: Ankush Mandal, He Jiang, Anshumali Shrivastava, Vivek Sarkar
Date: 2018-12-01 00:00:00
Proceeding: NeurIPS 2018 12

Identifying the top-K frequent items is one of the most common and important operations in large data processing systems. As a result, several solutions have been proposed to solve this problem approximately. In this paper, we identify that in modern distributed settings with both multi-node as well as multi-core parallelism, existing algorithms, although theoretically sound, are suboptimal from the performance perspective. In particular, for identifying top-K frequent items, Count-Min Sketch (CMS) has fantastic update time but lack the important property of reducibility which is needed for exploiting available massive data parallelism. On the other end, popular Frequent algorithm (FA) leads to reducible summaries but the update costs are significant. In this paper, we present Topkapi, a fast and parallel algorithm for finding top-K frequent items, which gives the best of both worlds, i.e., it is reducible as well as efficient update time similar to CMS. Topkapi possesses strong theoretical guarantees and leads to significant performance gains due to increased parallelism, relative to past work.
Contrastive Learning from Pairwise Measurements
Authors: Yi Chen, Zhuoran Yang, Yuchen Xie, Princeton Zhaoran Wang
Date: 2018-12-01 00:00:00
Proceeding: NeurIPS 2018 12
Tasks: Contrastive Learning, Data Augmentation

Learning from pairwise measurements naturally arises from many applications, such as rank aggregation, ordinal embedding, and crowdsourcing. However, most existing models and algorithms are susceptible to potential model misspecification. In this paper, we study a semiparametric model where the pairwise measurements follow a natural exponential family distribution with an unknown base measure. Such a semiparametric model includes various popular parametric models, such as the Bradley-Terry-Luce model and the paired cardinal model, as special cases. To estimate this semiparametric model without specifying the base measure, we propose a data augmentation technique to create virtual examples, which enables us to define a contrastive estimator. In particular, we prove that such a contrastive estimator is invariant to model misspecification within the natural exponential family, and moreover, attains the optimal statistical rate of convergence up to a logarithmic factor. We provide numerical experiments to corroborate our theory.
Point process latent variable models of larval zebrafish behavior
Authors: Anuj Sharma, Robert Johnson, Florian Engert, Scott Linderman
Date: 2018-12-01 00:00:00
Proceeding: NeurIPS 2018 12
Tasks: Variational Inference

A fundamental goal of systems neuroscience is to understand how neural activity gives rise to natural behavior.  In order to achieve this goal, we must first build comprehensive models that offer quantitative descriptions of behavior.  We develop a new class of probabilistic models to tackle this challenge in the study of larval zebrafish, an important model organism for neuroscience.  Larval zebrafish locomote via sequences of punctate swim bouts--brief flicks of the tail--which are naturally modeled as a marked point process.  However, these sequences of swim bouts belie a set of discrete and continuous internal states, latent variables that are not captured by standard point process models.  We incorporate these variables as latent marks of a point process and explore various models for their dynamics.  To infer the latent variables and fit the parameters of this model, we develop an amortized variational inference algorithm that targets the collapsed posterior distribution, analytically marginalizing out the discrete latent variables.  With a dataset of over 120,000 swim bouts, we show that our models reveal interpretable discrete classes of swim bouts and continuous internal states like hunger that modulate their dynamics.  These models are a major step toward understanding the natural behavioral program of the larval zebrafish and, ultimately, its neural underpinnings.