pwc-archive/papers-with-abstracts huggingface dataset:
Protein Interface Prediction using Graph Convolutional Networks
Authors: Alex Fout, Jonathon Byrd, Basir Shariat, Asa Ben-Hur
Date: 2017-12-01 00:00:00
Proceeding: NeurIPS 2017 12
Tasks: Drug Discovery, Prediction, Protein Interface Prediction

We consider the prediction of interfaces between proteins, a challenging problem with important applications in drug discovery and design, and examine the performance of existing and newly proposed spatial graph convolution operators for this task. By performing convolution over a local neighborhood of a node of interest, we are able to stack multiple layers of convolution and learn effective latent representations that integrate information across the graph that represent the three dimensional structure of a protein of interest. An architecture that combines the learned features across pairs of proteins is then used to classify pairs of amino acid residues as part of an interface or not. In our experiments, several graph convolution operators yielded accuracy that is better than the state-of-the-art SVM method in this task.
Solid Harmonic Wavelet Scattering: Predicting Quantum Molecular Energy from Invariant Descriptors of 3D Electronic Densities
Authors: Michael Eickenberg, Georgios Exarchakis, Matthew Hirn, Stephane Mallat
Date: 2017-12-01 00:00:00
Proceeding: NeurIPS 2017 12
Tasks: General Classification, regression

We introduce a solid harmonic wavelet scattering representation, invariant  to rigid motion and stable to deformations, for regression and classification  of 2D and 3D signals. Solid harmonic wavelets are computed by multiplying solid  harmonic functions with Gaussian windows dilated at different scales. Invariant  scattering coefficients are obtained by cascading such wavelet transforms with  the complex modulus nonlinearity. We study an application of solid harmonic  scattering invariants to the estimation of quantum molecular energies, which  are also invariant to rigid motion and stable with respect to deformations. A multilinear regression  over scattering invariants provides close to state of the art results over  small and large databases of organic molecules.
Random Projection Filter Bank for Time Series Data
Authors: Amir-Massoud Farahmand, Sepideh Pourazarm, Daniel Nikovski
Date: 2017-12-01 00:00:00
Proceeding: NeurIPS 2017 12
Tasks: Time Series, Time Series Analysis, Time Series Prediction

We propose Random Projection Filter Bank (RPFB) as a generic and simple approach to extract features from time series data. RPFB is a set of randomly generated stable autoregressive filters that are convolved with the input time series to generate the features. These features can be used by any conventional machine learning algorithm for solving tasks such as time series prediction, classification with time series data, etc. Different filters in RPFB extract different aspects of the time series, and together they provide a reasonably good summary of the time series. RPFB is easy to implement, fast to compute, and parallelizable. We provide an error upper bound indicating that RPFB provides a reasonable approximation to a class of dynamical systems. The empirical results in a series of synthetic and real-world problems show that RPFB is an effective method to extract features from time series.
On Frank-Wolfe and Equilibrium Computation
Authors: Jacob D. Abernethy, Jun-Kun Wang
Date: 2017-12-01 00:00:00
Proceeding: NeurIPS 2017 12

We consider the Frank-Wolfe (FW) method for constrained convex optimization, and we show that this classical technique can be interpreted from a different perspective: FW emerges as the computation of an equilibrium (saddle point) of a special convex-concave zero sum game. This saddle-point trick relies on the existence of no-regret online learning to both generate a sequence of iterates but also to provide a proof of convergence through vanishing regret. We show that our stated equivalence has several nice properties, as it exhibits a modularity that gives rise to various old and new algorithms. We explore a few such resulting methods, and provide experimental results to demonstrate correctness and efficiency.
Approximation Algorithms for \ell_0-Low Rank Approximation
Authors: Karl Bringmann, Pavel Kolev, David Woodruff
Date: 2017-12-01 00:00:00
Proceeding: NeurIPS 2017 12

We study the $\ell_0$-Low Rank Approximation Problem, where the goal is,    given an $m \times n$ matrix $A$, to output a rank-$k$ matrix $A'$ for which   $\|A'-A\|_0$ is minimized.    Here, for a matrix $B$, $\|B\|_0$ denotes the number of its non-zero entries.    This NP-hard variant of low rank approximation is natural for problems    with no underlying metric, and its goal is to minimize the number of disagreeing   data positions.      We provide approximation algorithms which significantly improve the running time    and approximation factor of previous work.    For $k > 1$, we show how to find, in poly$(mn)$ time for every $k$,    a rank $O(k \log(n/k))$ matrix $A'$ for which $\|A'-A\|_0 \leq O(k^2 \log(n/k)) \OPT$.    To the best of our knowledge, this is the first algorithm with provable guarantees    for the $\ell_0$-Low Rank Approximation Problem for $k > 1$,    even for bicriteria algorithms.       For the well-studied case when $k = 1$, we give a $(2+\epsilon)$-approximation    in {\it sublinear time}, which is impossible for other variants of low rank    approximation such as for the  Frobenius norm.    We strengthen this for the well-studied case of binary matrices to obtain    a $(1+O(\psi))$-approximation in sublinear time,    where $\psi = \OPT/\nnz{A}$.   For small $\psi$, our approximation factor is $1+o(1)$.
The power of absolute discounting: all-dimensional distribution estimation
Authors: Moein Falahatgar, Mesrob I. Ohannessian, Alon Orlitsky, Venkatadheeraj Pichapati
Date: 2017-12-01 00:00:00
Proceeding: NeurIPS 2017 12
Tasks: All, Language Modeling, Language Modelling

Categorical models are a natural fit for many problems. When learning the distribution of categories from samples, high-dimensionality may dilute the data. Minimax optimality is too pessimistic to remedy this issue. A serendipitously discovered estimator, absolute discounting, corrects empirical frequencies by subtracting a constant from observed categories, which it then redistributes among the unobserved. It outperforms classical estimators empirically, and has been used extensively in natural language modeling. In this paper, we rigorously explain the prowess of this estimator using less pessimistic notions. We show  that (1) absolute discounting recovers classical minimax KL-risk rates, (2) it is \emph{adaptive} to an effective dimension rather than the true dimension, (3) it is strongly related to the Good-Turing estimator and inherits its \emph{competitive} properties. We use power-law distributions as the cornerstone of these results. We validate the theory via synthetic data and an application to the Global Terrorism Database.
Subspace Clustering via Tangent Cones
Authors: Amin Jalali, Rebecca Willett
Date: 2017-12-01 00:00:00
Proceeding: NeurIPS 2017 12
Tasks: Clustering, Graph Clustering

Given samples lying on any of a number of subspaces, subspace clustering is the task of grouping the samples based on the their corresponding subspaces. Many subspace clustering methods operate by assigning a measure of affinity to each pair of points and feeding these affinities into a graph clustering algorithm. This paper proposes a new paradigm for subspace clustering that computes affinities based on the corresponding conic geometry. The proposed conic subspace clustering (CSC) approach considers the convex hull of a collection of normalized data points and the corresponding tangent cones. The union of subspaces underlying the data imposes a strong association between the tangent cone at a sample $x$ and the original subspace containing $x$. In addition to describing this novel geometric perspective, this paper provides a practical algorithm for subspace clustering that leverages this perspective, where a tangent cone membership test is used to estimate the affinities. This algorithm is accompanied with deterministic and stochastic guarantees on the properties of the learned affinity matrix, on the true and false positive rates and spread, which directly translate into the overall clustering accuracy.
Acceleration and Averaging in Stochastic Descent Dynamics
Authors: Walid Krichene, Peter L. Bartlett
Date: 2017-12-01 00:00:00
Proceeding: NeurIPS 2017 12

We formulate and study a general family of (continuous-time) stochastic dynamics  for accelerated first-order minimization of smooth convex functions. Building on an averaging formulation of accelerated mirror descent, we propose a stochastic variant in which the gradient is contaminated by noise, and study the resulting stochastic differential equation. We prove a bound on the rate of change of an energy function associated with the problem, then use it to derive estimates of convergence rates of the function values (almost surely and in expectation), both for persistent and asymptotically vanishing noise. We discuss the interaction between the parameters of the dynamics (learning rate and averaging rates) and the covariation of the noise process. In particular, we show how the asymptotic rate of covariation affects the choice of parameters and, ultimately, the convergence rate.
Cross-Spectral Factor Analysis
Authors: Neil Gallagher, Kyle R. Ulrich, Austin Talbot, Kafui Dzirasa, Lawrence Carin, David E. Carlson
Date: 2017-12-01 00:00:00
Proceeding: NeurIPS 2017 12

In neuropsychiatric disorders such as schizophrenia or depression, there is often a disruption in the way that regions of the brain synchronize with one another. To facilitate understanding of network-level synchronization between brain regions, we introduce a novel model of multisite low-frequency neural recordings, such as local field potentials (LFPs) and electroencephalograms (EEGs). The proposed model, named Cross-Spectral Factor Analysis (CSFA), breaks the observed signal into factors defined by unique spatio-spectral properties. These properties are granted to the factors via a Gaussian process formulation in a multiple kernel learning framework. In this way, the LFP signals can be mapped to a lower dimensional space in a way that retains information of relevance to neuroscientists.  Critically, the factors are interpretable. The proposed approach empirically allows similar performance in classifying mouse genotype and behavioral context when compared to commonly used approaches that lack the interpretability of CSFA. We also introduce a semi-supervised approach, termed discriminative CSFA (dCSFA). CSFA and dCSFA provide useful tools for understanding neural dynamics, particularly by aiding in the design of causal follow-up experiments.
Affinity Clustering: Hierarchical Clustering at Scale
Authors: Mohammadhossein Bateni, Soheil Behnezhad, Mahsa Derakhshan, Mohammadtaghi Hajiaghayi, Raimondas Kiveris, Silvio Lattanzi, Vahab Mirrokni
Date: 2017-12-01 00:00:00
Proceeding: NeurIPS 2017 12
Tasks: Clustering, Graph Clustering

Graph clustering is a fundamental task in many data-mining and machine-learning pipelines. In particular, identifying a good hierarchical structure is at the same time a fundamental and challenging problem for several applications. The amount of data to analyze is increasing at an astonishing rate each day. Hence there is a need for new solutions to efficiently compute effective hierarchical clusterings on such huge data.  The main focus of this paper is on minimum spanning tree (MST) based clusterings. In particular, we propose affinity, a novel hierarchical clustering based on Boruvka's MST algorithm. We prove certain theoretical guarantees for affinity (as well as some other classic algorithms) and show that in practice it is superior to several other state-of-the-art clustering algorithms.   Furthermore, we present two MapReduce implementations for affinity. The first one works for the case where the input graph is dense and takes constant rounds. It is based on a Massively Parallel MST algorithm for dense graphs that improves upon the state-of-the-art algorithm of Lattanzi et al. (SPAA 2011). Our second algorithm has no assumption on the density of the input graph and finds the affinity clustering in $O(\log n)$ rounds using Distributed Hash Tables (DHTs). We show experimentally that our algorithms are scalable for huge data sets, e.g., for graphs with trillions of edges.
A Sharp Error Analysis for the Fused Lasso, with Application to Approximate Changepoint Screening
Authors: Kevin Lin, James L. Sharpnack, Alessandro Rinaldo, Ryan J. Tibshirani
Date: 2017-12-01 00:00:00
Proceeding: NeurIPS 2017 12

In the 1-dimensional multiple changepoint detection problem, we derive a new fast error rate for the fused lasso estimator, under the assumption that the mean vector has a sparse number of changepoints. This rate is seen to be suboptimal (compared to the minimax rate) by only a factor of $\log\log{n}$. Our proof technique is centered around a novel construction that we call a lower interpolant. We extend our results to misspecified models and exponential family distributions. We also describe the implications of our error analysis for the approximate screening of changepoints.
A Meta-Learning Perspective on Cold-Start Recommendations for Items
Authors: Manasi Vartak, Arvind Thiagarajan, Conrado Miranda, Jeshua Bratman, Hugo Larochelle
Date: 2017-12-01 00:00:00
Proceeding: NeurIPS 2017 12
Tasks: Meta-Learning, Product Recommendation

Matrix factorization (MF) is one of the most popular techniques for product recommendation, but is known to suffer from serious cold-start problems. Item cold-start problems are particularly acute in settings such as Tweet recommendation where new items arrive continuously. In this paper, we present a meta-learning strategy to address item cold-start when new items arrive continuously. We propose two deep neural network architectures that implement our meta-learning strategy. The first architecture learns a linear classifier whose weights are determined by the item history while the second architecture learns a neural network whose biases are instead adjusted. We evaluate our techniques on the real-world problem of Tweet recommendation. On production data at Twitter, we demonstrate that our proposed techniques significantly beat the MF baseline and also outperform production models for Tweet recommendation.
Efficient Approximation Algorithms for Strings Kernel Based Sequence Classification
Authors: Muhammad Farhan, Juvaria Tariq, Arif Zaman, Mudassir Shabbir, Imdad Ullah Khan
Date: 2017-12-01 00:00:00
Proceeding: NeurIPS 2017 12
Tasks: Classification, General Classification

Sequence classification algorithms, such as SVM, require a definition of distance (similarity) measure between two sequences. A commonly used notion of similarity is the number of matches between k-mers (k-length subsequences) in the two sequences. Extending this definition, by considering two k-mers to match if their distance is at most m, yields better classification performance. This, however, makes the problem computationally much more complex. Known algorithms to compute this similarity have computational complexity that render them applicable only for small values of k and m. In this work, we develop novel techniques to efficiently and accurately estimate the pairwise similarity score, which enables us to use much larger values of k and m, and get higher predictive accuracy. This opens up a broad avenue of applying this classification approach to audio, images, and text sequences. Our algorithm achieves excellent approximation performance with theoretical guarantees. In the process we solve an open combinatorial problem, which was posed as a major hindrance to the scalability of existing solutions. We give analytical bounds on quality and runtime of our algorithm and report its empirical performance on real world biological and music sequences datasets.
Convergence of Gradient EM on Multi-component Mixture of Gaussians
Authors: Bowei Yan, Mingzhang Yin, Purnamrita Sarkar
Date: 2017-12-01 00:00:00
Proceeding: NeurIPS 2017 12
Tasks: Learning Theory

In this paper, we study convergence properties of the gradient variant of Expectation-Maximization algorithm~\cite{lange1995gradient} for Gaussian Mixture Models for arbitrary number of clusters and mixing coefficients. We derive the convergence rate depending on the mixing coefficients, minimum and maximum pairwise distances between the true centers, dimensionality and number of components; and obtain a near-optimal local contraction radius. While there have been some recent notable works that derive local convergence rates for EM in the two symmetric mixture of Gaussians, in the more general case, the derivations need structurally different and non-trivial arguments. We use recent tools from learning theory and empirical processes to achieve our theoretical results.
Houdini: Fooling Deep Structured Visual and Speech Recognition Models with Adversarial Examples
Authors: Moustapha M. Cisse, Yossi Adi, Natalia Neverova, Joseph Keshet
Date: 2017-12-01 00:00:00
Proceeding: NeurIPS 2017 12
Tasks: General Classification, Pose Estimation, Semantic Segmentation, speech-recognition, Speech Recognition

Generating adversarial examples is a critical step for evaluating and improving the robustness of learning machines. So far, most existing methods only work for classification and are not designed to alter the true performance measure of the problem at hand. We introduce a novel flexible approach named Houdini for generating adversarial examples specifically tailored for the final performance measure of the task considered, be it combinatorial and non-decomposable. We successfully apply Houdini to a range of applications such as speech recognition, pose estimation and semantic segmentation. In all cases, the attacks based on Houdini achieve higher success rate than those based on the traditional surrogates used to train the models while using a less perceptible adversarial perturbation.
Efficient and Flexible Inference for Stochastic Systems
Authors: Stefan Bauer, Nico S. Gorbach, Djordje Miladinovic, Joachim M. Buhmann
Date: 2017-12-01 00:00:00
Proceeding: NeurIPS 2017 12

Many real world dynamical systems are described by stochastic differential equations. Thus parameter inference is a challenging and important problem in many disciplines. We provide a grid free and flexible algorithm offering parameter and state inference for stochastic systems and compare our approch based on variational approximations to state of the art methods showing significant advantages both in runtime and accuracy.
When Cyclic Coordinate Descent Outperforms Randomized Coordinate Descent
Authors: Mert Gurbuzbalaban, Asuman Ozdaglar, Pablo A. Parrilo, Nuri Vanli
Date: 2017-12-01 00:00:00
Proceeding: NeurIPS 2017 12

The coordinate descent (CD) method is a classical optimization algorithm that has seen a revival of interest because of its competitive performance in machine learning applications. A number of recent papers provided convergence rate estimates for their deterministic (cyclic) and randomized variants that differ in the selection of update coordinates. These estimates suggest randomized coordinate descent (RCD) performs better than cyclic coordinate descent (CCD), although numerical experiments do not provide clear justification for this comparison. In this paper, we provide examples and more generally problem classes for which CCD (or CD with any deterministic order) is faster than RCD in terms of asymptotic worst-case convergence. Furthermore, we provide lower and upper bounds on the amount of improvement on the rate of CCD relative to RCD, which depends on the deterministic order used. We also provide a characterization of the best deterministic order (that leads to the maximum improvement in convergence rate) in terms of the combinatorial properties of the Hessian matrix of the objective function.
Active Learning from Peers
Authors: Keerthiram Murugesan, Jaime Carbonell
Date: 2017-12-01 00:00:00
Proceeding: NeurIPS 2017 12
Tasks: Active Learning

This paper addresses the challenge of learning from peers in an online multitask setting. Instead of always requesting a label from a human oracle, the proposed method first determines if the learner for each task can acquire that label with sufficient confidence from its peers either as a task-similarity weighted sum, or from the single most similar task.  If so, it saves the oracle query for later use in more difficult cases, and if not it queries the human oracle.  The paper develops the new algorithm to exhibit this behavior and proves a theoretical mistake bound for the method compared to the best linear predictor in hindsight. Experiments over three multitask learning benchmark datasets show clearly superior performance over baselines such as assuming task independence, learning only from the oracle and not learning from peer tasks.
Experimental Design for Learning Causal Graphs with Latent Variables
Authors: Murat Kocaoglu, Karthikeyan Shanmugam, Elias Bareinboim
Date: 2017-12-01 00:00:00
Proceeding: NeurIPS 2017 12
Tasks: Experimental Design

We consider the problem of learning causal structures with latent variables using interventions. Our objective is not only to learn the causal graph between the observed variables, but to locate unobserved variables that could confound the relationship between observables. Our approach is stage-wise: We first learn the observable graph, i.e., the induced graph between observable variables. Next we learn the existence and location of the latent variables given the observable graph. We propose an efficient randomized algorithm that can learn the observable graph using O(d\log^2 n) interventions where d is the degree of the graph. We further propose an efficient deterministic variant which uses O(log n + l) interventions, where l is the longest directed path in the graph. Next, we propose an algorithm that uses only O(d^2 log n) interventions that can learn the latents between both non-adjacent and adjacent variables. While a naive baseline approach would require O(n^2) interventions, our combined algorithm can learn the causal graph with latents using O(d log^2 n + d^2 log (n)) interventions.
Learning to Model the Tail
Authors: Yu-Xiong Wang, Deva Ramanan, Martial Hebert
Date: 2017-12-01 00:00:00
Proceeding: NeurIPS 2017 12
Tasks: image-classification, Image Classification, model, Transfer Learning

We describe an approach to learning from long-tailed, imbalanced datasets that are prevalent in real-world settings.  Here, the challenge is to learn accurate "few-shot'' models for classes in the tail of the class distribution, for which little data is available. We cast this problem as transfer learning, where knowledge from the data-rich classes in the head of the distribution is transferred to the data-poor classes in the tail. Our key insights are as follows. First, we propose to transfer meta-knowledge about learning-to-learn from the head classes. This knowledge is encoded with a meta-network that operates on the space of model parameters, that is trained to predict many-shot model parameters from few-shot model parameters.  Second, we transfer this meta-knowledge in a progressive manner, from classes in the head to the "body'', and from the "body'' to the tail. That is, we transfer knowledge in a gradual fashion, regularizing meta-networks for few-shot regression with those trained with more training data. This allows our final network to capture a notion of model dynamics, that predicts how model parameters are likely to change as more training data is gradually added. We demonstrate results on image classification datasets (SUN, Places, and ImageNet) tuned for the long-tailed setting, that significantly outperform common heuristics, such as data resampling or reweighting.