pwc-archive/papers-with-abstracts huggingface dataset:
Bregman Divergence for Stochastic Variance Reduction: Saddle-Point and Adversarial Prediction
Authors: Zhan Shi, Xinhua Zhang, Yao-Liang Yu
Date: 2017-12-01 00:00:00
Proceeding: NeurIPS 2017 12
Tasks: Prediction

Adversarial machines, where a learner competes against an adversary, have regained much recent interest in machine learning. They are naturally in the form of saddle-point optimization, often with separable structure but sometimes also with unmanageably large dimension. In this work we show that adversarial prediction under multivariate losses can be solved much faster than they used to be. We first reduce the problem size exponentially by using appropriate sufficient statistics, and then we adapt the new stochastic variance-reduced algorithm of Balamurugan & Bach (2016) to allow any Bregman divergence. We prove that the same linear rate of convergence is retained and we show that for adversarial prediction using KL-divergence we can further achieve a speedup of #example times compared with the Euclidean alternative. We verify the theoretical findings through extensive experiments on two example applications: adversarial prediction and LPboosting.
Convolutional Phase Retrieval
Authors: Qing Qu, Yuqian Zhang, Yonina Eldar, John Wright
Date: 2017-12-01 00:00:00
Proceeding: NeurIPS 2017 12
Tasks: Retrieval

We study the convolutional phase retrieval problem, which asks us to recover an unknown signal ${\mathbf x} $ of length $n$ from $m$ measurements consisting of the magnitude of its cyclic convolution with a known kernel $\mathbf a$ of length $m$. This model is motivated by applications to channel estimation, optics, and underwater acoustic communication, where the signal of interest is acted on by a given channel/filter, and phase information is difficult or impossible to acquire. We show that when $\mathbf a$ is random and $m \geq \Omega(\frac{ \| \mathbf C_{\mathbf x}\|^2}{ \|\mathbf x\|^2 }  n \mathrm{poly} \log n)$, $\mathbf x$ can be efficiently recovered up to a global phase using a combination of spectral initialization and generalized gradient descent. The main challenge is coping with dependencies in the measurement operator; we overcome this challenge by using ideas from decoupling theory, suprema of chaos processes and the restricted isometry property of random circulant matrices, and recent analysis for alternating minimizing methods.
Estimating High-dimensional Non-Gaussian Multiple Index Models via Stein’s Lemma
Authors: Zhuoran Yang, Krishnakumar Balasubramanian, Princeton Zhaoran Wang, Han Liu
Date: 2017-12-01 00:00:00
Proceeding: NeurIPS 2017 12
Tasks: LEMMA, Vocal Bursts Intensity Prediction

We consider estimating the parametric components of semiparametric multi-index models in high dimensions. To bypass the requirements of Gaussianity or elliptical symmetry of covariates in existing methods, we propose to leverage a second-order Stein’s method with score function-based corrections. We prove that our estimator achieves a near-optimal statistical rate of convergence even when the score function or the response variable is heavy-tailed. To establish the key concentration results, we develop a data-driven truncation argument that may be of independent interest. We supplement our theoretical findings with simulations.
A Learning Error Analysis for Structured Prediction with Approximate Inference
Authors: Yuanbin Wu, Man Lan, Shiliang Sun, Qi Zhang, Xuanjing Huang
Date: 2017-12-01 00:00:00
Proceeding: NeurIPS 2017 12
Tasks: Dependency Parsing, General Classification, Structured Prediction, text-classification, Text Classification

In this work, we try to understand the differences between exact and approximate inference algorithms in structured prediction. We compare the estimation and approximation error of both underestimate and overestimate models. The result shows that, from the perspective of learning errors, performances of approximate inference could be as good as exact inference. The error analyses also suggest a new margin for existing learning algorithms. Empirical evaluations on text classification, sequential labelling and dependency parsing witness the success of approximate inference and the benefit of the proposed margin.
Efficient Second-Order Online Kernel Learning with Adaptive Embedding
Authors: Daniele Calandriello, Alessandro Lazaric, Michal Valko
Date: 2017-12-01 00:00:00
Proceeding: NeurIPS 2017 12
Tasks: Second-order methods

Online kernel learning (OKL) is a flexible framework to approach prediction problems, since the large approximation space provided by reproducing kernel Hilbert spaces can contain an accurate function for the problem. Nonetheless, optimizing over this space is computationally expensive. Not only first order methods accumulate $\O(\sqrt{T})$ more loss than the optimal function, but the curse of kernelization results in a $\O(t)$ per step complexity. Second-order methods get closer to the optimum much faster, suffering only $\O(\log(T))$ regret, but second-order updates are even more expensive, with a $\O(t^2)$ per-step cost. Existing approximate OKL methods try to reduce this complexity either by limiting the Support Vectors (SV) introduced in the predictor, or by avoiding the kernelization process altogether using embedding. Nonetheless, as long as the size of the approximation space or the number of SV does not grow over time, an adversary can always exploit the approximation process. In this paper, we propose PROS-N-KONS, a method that combines Nystrom sketching to project the input point in a small, accurate embedded space, and performs efficient second-order updates in this space. The embedded space is continuously updated to guarantee that the embedding remains accurate, and we show that the per-step cost only grows with the effective dimension of the problem and not with $T$. Moreover, the second-order updated allows us to achieve the logarithmic regret. We empirically compare our algorithm on recent large-scales benchmarks and show it performs favorably.
Countering Feedback Delays in Multi-Agent Learning
Authors: Zhengyuan Zhou, Panayotis Mertikopoulos, Nicholas Bambos, Peter W. Glynn, Claire Tomlin
Date: 2017-12-01 00:00:00
Proceeding: NeurIPS 2017 12

We consider a model of game-theoretic learning based on online mirror descent (OMD) with asynchronous and delayed feedback information. Instead of focusing on specific games, we consider a broad class of continuous games defined by the general equilibrium stability notion, which we call λ-variational stability. Our first contribution is that, in this class of games, the actual sequence of play induced by OMD-based learning converges to Nash equilibria provided that the feedback delays faced by the players are synchronous and bounded. Subsequently, to tackle fully decentralized, asynchronous environments with (possibly) unbounded delays between actions and feedback, we propose a variant of OMD which we call delayed mirror descent (DMD), and which relies on the repeated leveraging of past information. With this modification, the algorithm converges to Nash equilibria with no feedback synchronicity assumptions and even when the delays grow superlinearly relative to the horizon of play.
Hierarchical Clustering Beyond the Worst-Case
Authors: Vincent Cohen-Addad, Varun Kanade, Frederik Mallmann-Trenn
Date: 2017-12-01 00:00:00
Proceeding: NeurIPS 2017 12
Tasks: Clustering, General Classification, Multi-class Classification

Hiererachical clustering, that is computing a recursive partitioning of a dataset to obtain clusters at increasingly finer granularity is a fundamental problem in data analysis. Although hierarchical clustering has mostly been studied through procedures such as linkage algorithms, or top-down heuristics, rather than as optimization problems, recently Dasgupta [1] proposed an objective function for hierarchical clustering and initiated a line of work developing algorithms that explicitly optimize an objective (see also [2, 3, 4]). In this paper, we consider a fairly general random graph model for hierarchical clustering, called the hierarchical stochastic blockmodel (HSBM), and show that in certain regimes the SVD approach of McSherry [5] combined with specific linkage methods results in a clustering that give an O(1)-approximation to Dasgupta’s cost function. We also show that an approach based on SDP relaxations for balanced cuts based on the work of Makarychev et al. [6], combined with the recursive sparsest cut algorithm of Dasgupta, yields an O(1) approximation in slightly larger regimes and also in the semi-random setting, where an adversary may remove edges from the random graph generated according to an HSBM. Finally, we report empirical evaluation on synthetic and real-world  data showing that our proposed SVD-based method does indeed achieve a better cost than other widely-used heurstics and also results in a better classification accuracy when the underlying problem was that of multi-class classification.
Invariance and Stability of Deep Convolutional Representations
Authors: Alberto Bietti, Julien Mairal
Date: 2017-12-01 00:00:00
Proceeding: NeurIPS 2017 12

In this paper, we study deep signal representations that are near-invariant to groups of transformations and stable to the action of diffeomorphisms without losing signal information. This is achieved by generalizing the multilayer kernel introduced in the context of convolutional kernel networks and by studying the geometry of the corresponding reproducing kernel Hilbert space. We show that the signal representation is stable, and that models from this functional space, such as a large class of convolutional neural networks, may enjoy the same stability.
Robust and Efficient Transfer Learning with Hidden Parameter Markov Decision Processes
Authors: Taylor W. Killian, Samuel Daulton, George Konidaris, Finale Doshi-Velez
Date: 2017-12-01 00:00:00
Proceeding: NeurIPS 2017 12
Tasks: Transfer Learning

We introduce a new formulation of the Hidden Parameter Markov Decision Process (HiP-MDP), a framework for modeling families of related tasks using low-dimensional latent embeddings.  Our new framework correctly models the joint uncertainty in the latent parameters and the state space.  We also replace the original Gaussian Process-based model with a Bayesian Neural Network, enabling more scalable inference.  Thus, we expand the scope of the HiP-MDP to applications with higher dimensions and more complex dynamics.
Population Matching Discrepancy and Applications in Deep Learning
Authors: Jianfei Chen, Chongxuan Li, Yizhong Ru, Jun Zhu
Date: 2017-12-01 00:00:00
Proceeding: NeurIPS 2017 12
Tasks: Deep Learning, Domain Adaptation

A differentiable estimation of the distance between two distributions based on samples is important for many deep learning tasks. One such estimation  is maximum mean discrepancy (MMD). However, MMD suffers from its sensitive kernel bandwidth hyper-parameter, weak gradients, and large mini-batch size when used as a training objective. In this paper, we propose population matching discrepancy (PMD) for estimating the distribution distance based on samples, as well as an algorithm to learn the parameters of the distributions using PMD as an objective. PMD is defined as the minimum weight matching of sample populations from each distribution, and we prove that PMD is a strongly consistent estimator of the first Wasserstein metric. We apply PMD to two deep learning tasks, domain adaptation and generative modeling. Empirical results demonstrate that PMD overcomes the aforementioned drawbacks of MMD, and outperforms MMD on both tasks in terms of the performance as well as the convergence speed.
Generalizing GANs: A Turing Perspective
Authors: Roderich Gross, Yue Gu, Wei Li, Melvin Gauci
Date: 2017-12-01 00:00:00
Proceeding: NeurIPS 2017 12

Recently, a new class of machine learning algorithms has emerged, where models and discriminators are generated in a competitive setting. The most prominent example is Generative Adversarial Networks (GANs). In this paper we examine how these algorithms relate to the Turing test, and derive what - from a Turing perspective - can be considered their defining features. Based on these features, we outline directions for generalizing GANs - resulting in the family of algorithms referred to as Turing Learning. One such direction is to allow the discriminators to interact with the processes from which the data samples are obtained, making them "interrogators", as in the Turing test. We validate this idea using two case studies. In the first case study, a computer infers the behavior of an agent while controlling its environment. In the second case study, a robot infers its own sensor configuration while controlling its movements. The results confirm that by allowing discriminators to interrogate, the accuracy of models is improved.
Learning with Bandit Feedback in Potential Games
Authors: Amélie Heliou, Johanne Cohen, Panayotis Mertikopoulos
Date: 2017-12-01 00:00:00
Proceeding: NeurIPS 2017 12

This paper examines the equilibrium convergence properties of no-regret learning with exponential weights in potential games. To establish convergence with minimal information requirements on the players' side, we focus on two frameworks: the semi-bandit case (where players have access to a noisy estimate of their payoff vectors, including strategies they did not play), and the bandit case (where players are only able to observe their in-game, realized payoffs). In the semi-bandit case, we show that the induced sequence of play converges almost surely to a Nash equilibrium at a quasi-exponential rate. In the bandit case, the same result holds for approximate Nash equilibria if we introduce a constant exploration factor that guarantees that action choice probabilities never become arbitrarily small. In particular, if the algorithm is run with a suitably decreasing exploration factor, the sequence of play converges to a bona fide Nash equilibrium with probability 1.
Communication-Efficient Distributed Learning of Discrete Distributions
Authors: Ilias Diakonikolas, Elena Grigorescu, Jerry Li, Abhiram Natarajan, Krzysztof Onak, Ludwig Schmidt
Date: 2017-12-01 00:00:00
Proceeding: NeurIPS 2017 12
Tasks: Density Estimation

We initiate a systematic investigation of distribution learning (density estimation) when the data is distributed across multiple servers. The servers must communicate with a referee and the goal is to estimate the underlying distribution with as few bits of communication as possible. We focus on non-parametric density estimation of discrete distributions with respect to the l1 and l2 norms. We provide the first non-trivial upper and lower bounds on the communication complexity of this basic estimation task in various settings of interest. Specifically, our results include the following:   1. When the unknown discrete distribution is unstructured and each server has only one sample, we show that any blackboard protocol (i.e., any protocol in which servers interact arbitrarily using public messages) that learns the distribution must essentially communicate the entire sample.  2. For the case of structured distributions, such as k-histograms and monotone distributions, we design distributed learning algorithms that achieve significantly better communication guarantees than the naive ones, and obtain tight upper and lower bounds in several regimes. Our distributed learning algorithms run in near-linear time and are robust to model misspecification.  Our results provide insights on the interplay between structure and communication efficiency for a range of fundamental distribution estimation tasks.
When Worlds Collide: Integrating Different Counterfactual Assumptions in Fairness
Authors: Chris Russell, Matt J. Kusner, Joshua Loftus, Ricardo Silva
Date: 2017-12-01 00:00:00
Proceeding: NeurIPS 2017 12
Tasks: counterfactual, Counterfactual Inference, Fairness

Machine learning is now being used to make crucial decisions about people's lives. For nearly all of these decisions there is a risk that individuals of a certain race, gender, sexual orientation, or any other subpopulation are unfairly discriminated against. Our recent method has demonstrated how to use techniques from counterfactual inference to make predictions fair across different subpopulations. This method requires that one provides the causal model that generated the data at hand. In general, validating all causal implications of the model is not possible without further assumptions. Hence, it is desirable to integrate competing causal models to provide counterfactually fair decisions, regardless of which causal "world" is the correct one. In this paper, we show how it is possible to make predictions that are approximately fair with respect to multiple possible causal models at once, thus mitigating the problem of exact causal specification. We frame the goal of learning a fair classifier as an optimization problem with fairness constraints entailed by competing causal explanations. We show how this optimization problem can be efficiently solved using gradient-based methods. We demonstrate the flexibility of our model on two real-world fair classification problems. We show that our model can seamlessly balance fairness in multiple worlds with prediction accuracy.
Matrix Norm Estimation from a Few Entries
Authors: Ashish Khetan, Sewoong Oh
Date: 2017-12-01 00:00:00
Proceeding: NeurIPS 2017 12
Tasks: Collaborative Filtering, Matrix Completion

Singular values of a data in a matrix form provide insights on the structure of the data, the effective dimensionality, and the choice of hyper-parameters on higher-level data analysis tools. However, in many practical applications such as collaborative filtering and network analysis,  we only get a partial observation. Under such scenarios, we consider the fundamental problem of recovering various spectral properties of the underlying matrix from a sampling of its entries. We propose a framework of first estimating the Schatten $k$-norms of a matrix for several values of $k$, and using these as surrogates for estimating spectral properties of interest, such as   the spectrum itself or the rank.  This paper focuses on the technical challenges in accurately estimating the Schatten norms from a sampling of a matrix. We introduce  a novel unbiased estimator based on counting small structures in a graph and provide  guarantees that match its empirical performances.  Our theoretical analysis shows that Schatten norms can be recovered accurately from strictly smaller number of samples compared to what is needed to recover the underlying low-rank matrix. Numerical experiments suggest that we significantly improve upon a competing approach of using matrix completion methods.
Neural Networks for Efficient Bayesian Decoding of Natural Images from Retinal Neurons
Authors: Nikhil Parthasarathy, Eleanor Batty, William Falcon, Thomas Rutten, Mohit Rajpal, E.J. Chichilnisky, Liam Paninski
Date: 2017-12-01 00:00:00
Proceeding: NeurIPS 2017 12
Tasks: Bayesian Inference, Decoder

Decoding sensory stimuli from neural signals can be used to reveal how we sense our physical environment, and is valuable for the design of brain-machine interfaces.  However, existing linear techniques for neural decoding may not fully reveal or exploit the fidelity of  the neural signal. Here we develop a new approximate Bayesian method for decoding natural images from the spiking activity of  populations of retinal ganglion cells (RGCs). We sidestep known computational challenges with Bayesian inference by exploiting artificial neural networks developed for computer vision, enabling fast nonlinear decoding that incorporates natural scene statistics implicitly.  We use a decoder architecture that first linearly reconstructs an image from RGC spikes, then applies a convolutional autoencoder to enhance the image. The resulting decoder, trained on natural images and simulated neural responses, significantly outperforms linear decoding, as well as simple point-wise nonlinear decoding. These results provide a tool for the assessment and optimization of retinal prosthesis technologies, and reveal that the retina may provide a more accurate representation of the visual scene than previously appreciated.
Semisupervised Clustering, AND-Queries and Locally Encodable Source Coding
Authors: Arya Mazumdar, Soumyabrata Pal
Date: 2017-12-01 00:00:00
Proceeding: NeurIPS 2017 12
Tasks: Clustering, Data Compression

Source coding is the canonical problem of data compression in information theory. In a  locally encodable source coding, each compressed bit depends on only few bits of the input. In this paper, we show that a recently popular model of semisupervised clustering is equivalent to locally encodable source coding. In this model, the task is to perform multiclass labeling of unlabeled elements. At the beginning, we can ask in parallel a set of simple queries to an oracle who provides (possibly erroneous) binary answers  to the queries. The queries cannot involve more than two (or a fixed constant number $\Delta$ of) elements. Now the labeling of all the elements (or clustering) must be performed based on the (noisy) query answers. The goal is to recover all the correct labelings while minimizing the number of such queries. The equivalence to locally encodable source codes leads us to find  lower bounds on the number of queries required in variety of scenarios. We are also able to show fundamental limitations of pairwise `same cluster' queries - and propose pairwise AND queries, that provably performs better in many situations.
Clustering Stable Instances of Euclidean k-means.
Authors: Aravindan Vijayaraghavan, Abhratanu Dutta, Alex Wang
Date: 2017-12-01 00:00:00
Proceeding: NeurIPS 2017 12
Tasks: Clustering

The Euclidean k-means problem is arguably the most widely-studied clustering problem in machine learning. While the k-means objective is NP-hard in the worst-case, practitioners have enjoyed remarkable success in applying heuristics like Lloyd's algorithm for this problem. To address this disconnect, we study the following question: what properties of real-world instances will enable us to design efficient algorithms and prove guarantees for finding the optimal clustering?   We consider a natural notion called additive perturbation stability that we believe captures many practical instances of Euclidean k-means clustering. Stable instances have unique optimal k-means solutions that does not change even when each point is perturbed a little (in Euclidean distance). This captures the property that k-means optimal solution should be tolerant to measurement errors and uncertainty in the points. We design efficient algorithms that provably recover the optimal clustering for instances that are additive perturbation stable. When the instance has some additional separation, we can design a simple, efficient algorithm with provable guarantees that is also robust to outliers. We also complement these results by studying the amount of stability in real datasets, and demonstrating that our algorithm performs well on these benchmark datasets.
On Blackbox Backpropagation and Jacobian Sensing
Authors: Krzysztof M. Choromanski, Vikas Sindhwani
Date: 2017-12-01 00:00:00
Proceeding: NeurIPS 2017 12
Tasks: compressed sensing

From a small number of calls to a given “blackbox" on random input perturbations, we show how to efficiently recover its unknown Jacobian, or estimate the left action of its Jacobian on a given vector. Our methods are based on a novel combination of compressed sensing and graph coloring techniques, and provably exploit structural prior knowledge about the Jacobian such as sparsity and symmetry while being noise robust. We demonstrate efficient backpropagation through noisy blackbox layers in a deep neural net, improved data-efficiency in the task of linearizing the dynamics of a rigid body system, and the generic ability to handle a rich class of input-output dependency structures in Jacobian estimation problems.