mtybilly/Instruct2DS huggingface dataset:
Targeting EEG/LFP Synchrony with Neural Nets
Authors: Yitong Li, michael Murias, samantha Major, geraldine Dawson, Kafui Dzirasa, Lawrence Carin, David E Carlson
Published in: Advances in Neural Information Processing Systems 30  (NIPS 2017) (Main Conference Track), 2017

Abstract: We consider the analysis of Electroencephalography (EEG) and Local Field Potential (LFP) datasets, which are “big” in terms of the size of recorded data but rarely have sufficient labels required to train complex models (e.g., conventional deep learning methods).  Furthermore, in many scientific applications, the goal is to be able to understand the underlying features related to the classification, which prohibits the blind application of deep networks. This motivates the development of a new model based on {\em parameterized} convolutional filters guided by previous neuroscience research; the filters learn relevant frequency bands while targeting synchrony, which are frequency-specific power and phase correlations between electrodes. This results in a highly expressive convolutional neural network with only a few hundred parameters, applicable to smaller datasets.  The proposed approach is demonstrated to yield competitive (often state-of-the-art) predictive performance during our empirical tests while yielding interpretable features.  Furthermore, a Gaussian process adapter is developed to combine analysis over distinct electrode layouts, allowing the joint processing of multiple datasets to address overfitting and improve generalizability.  Finally, it is demonstrated that the proposed framework effectively tracks neural dynamics on children in a clinical trial on Autism Spectrum Disorder.
Learning from uncertain curves: The 2-Wasserstein metric for Gaussian processes
Authors: Anton Mallasto, Aasa Feragen
Published in: Advances in Neural Information Processing Systems 30  (NIPS 2017) (Main Conference Track), 2017

Abstract: We introduce a novel framework for statistical analysis of populations of non-degenerate Gaussian processes (GPs), which are natural representations of uncertain curves. This allows inherent variation or uncertainty in function-valued data to be properly incorporated in the population analysis. Using the 2-Wasserstein metric we geometrize the space of GPs with L2 mean and covariance functions over compact index spaces. We prove uniqueness of the barycenter of a population of GPs, as well as convergence of the metric and the barycenter of their finite-dimensional counterparts. This justifies practical computations. Finally, we demonstrate our framework through experimental validation on GP datasets representing brain connectivity and climate development. A Matlab library for relevant computations will be published at https://sites.google.com/view/antonmallasto/software.
Online Dynamic Programming
Authors: Holakou Rahmanian, Manfred K. Warmuth
Published in: Advances in Neural Information Processing Systems 30  (NIPS 2017) (Main Conference Track), 2017

Abstract: We consider the problem of repeatedly solving a variant of the same dynamic programming problem in successive trials. An instance of the type of problems we consider is to find a good binary search tree in a changing environment. At the beginning of each trial, the learner probabilistically chooses a tree with the n keys at the internal nodes and the n + 1 gaps between keys at the leaves. The learner is then told the frequencies of the keys and gaps and is charged by the average search cost for the chosen tree. The problem is online because the frequencies can change between trials. The goal is to develop algorithms with the property that their total average search cost (loss) in all trials is close to the total loss of the best tree chosen in hindsight for all trials. The challenge, of course, is that the algorithm has to deal with exponential number of trees. We develop a general methodology for tackling such problems for a wide class of dynamic programming algorithms. Our framework allows us to extend online learning algorithms like Hedge and Component Hedge to a significantly wider class of combinatorial objects than was possible before.
Neural Discrete Representation Learning
Authors: Aaron van den Oord, Oriol Vinyals, koray kavukcuoglu
Published in: Advances in Neural Information Processing Systems 30  (NIPS 2017) (Main Conference Track), 2017

Abstract: Learning useful representations without supervision remains a key challenge in machine learning. In this paper, we propose a simple yet powerful generative model that learns such discrete representations. Our model, the Vector Quantised-Variational AutoEncoder (VQ-VAE), differs from VAEs in two key ways: the encoder network outputs discrete, rather than continuous, codes; and the prior is learnt rather than static. In order to learn a discrete latent representation, we incorporate ideas from vector quantisation (VQ). Using the VQ method allows the model to circumvent issues of ``posterior collapse'' -— where the latents are ignored when they are paired with a powerful autoregressive decoder -— typically observed in the VAE framework. Pairing these representations with an autoregressive prior, the model can generate high quality images, videos, and speech as well as doing high quality speaker conversion and unsupervised learning of phonemes, providing further evidence of the utility of the learnt representations.
Probabilistic Rule Realization and Selection
Authors: Haizi Yu, Tianxi Li, Lav R. Varshney
Published in: Advances in Neural Information Processing Systems 30  (NIPS 2017) (Main Conference Track), 2017

Abstract: Abstraction and realization are bilateral processes that are key in deriving intelligence and creativity. In many domains, the two processes are approached through \emph{rules}: high-level principles that reveal invariances within similar yet diverse examples. Under a probabilistic setting for discrete input spaces, we focus on the rule realization problem which generates input sample distributions that follow the given rules. More ambitiously, we go beyond a mechanical realization that takes whatever is given, but instead ask for proactively selecting reasonable rules to realize. This goal is demanding in practice, since the initial rule set may not always be consistent and thus intelligent compromises are needed. We formulate both rule realization and selection as two strongly connected components within a single and symmetric bi-convex problem, and derive an efficient algorithm that works at large scale. Taking music compositional rules as the main example throughout the paper, we demonstrate our model's efficiency in not only music realization (composition) but also music interpretation and understanding (analysis).
A Disentangled Recognition and Nonlinear Dynamics Model for Unsupervised Learning
Authors: Marco Fraccaro, Simon Kamronn, Ulrich Paquet, Ole Winther
Published in: Advances in Neural Information Processing Systems 30  (NIPS 2017) (Main Conference Track), 2017

Abstract: This paper takes a step towards temporal reasoning in a dynamically changing video, not in the pixel space that constitutes its frames, but in a latent space that describes the non-linear dynamics of the objects in its world. We introduce the Kalman variational auto-encoder, a framework for unsupervised learning of sequential data that disentangles two latent representations: an object's representation, coming from a recognition model, and a latent state describing its dynamics. As a result, the evolution of the world can be imagined and missing data imputed, both without the need to  generate high dimensional frames at each time step. The model is trained end-to-end on videos of a variety of simulated physical systems, and outperforms competing methods in generative and missing data imputation tasks.
Stabilizing Training of Generative Adversarial Networks through Regularization
Authors: Kevin Roth, Aurelien Lucchi, Sebastian Nowozin, Thomas Hofmann
Published in: Advances in Neural Information Processing Systems 30  (NIPS 2017) (Main Conference Track), 2017

Abstract: Deep generative models based on Generative Adversarial Networks (GANs) have demonstrated impressive sample quality but in order to work they require a careful choice of architecture, parameter initialization, and selection of hyper-parameters. This fragility is in part due to a dimensional mismatch or non-overlapping support between the model distribution and the data distribution, causing their density ratio and the associated f -divergence to be undefined. We overcome this fundamental limitation and propose a new regularization approach with low computational cost that yields a stable GAN training procedure. We demonstrate the effectiveness of this regularizer accross several architectures trained on common benchmark image generation tasks. Our regularization turns GAN models into reliable building blocks for deep learning.
Training Deep Networks without Learning Rates Through Coin Betting
Authors: Francesco Orabona, Tatiana Tommasi
Published in: Advances in Neural Information Processing Systems 30  (NIPS 2017) (Main Conference Track), 2017

Abstract: Deep learning methods achieve state-of-the-art performance in many application scenarios.  Yet, these methods require a significant amount of hyperparameters tuning in order to achieve  the best results. In particular, tuning the learning rates in the stochastic optimization  process is still one of the main bottlenecks. In this paper, we propose a new stochastic gradient descent procedure for deep networks that  does not require any learning rate setting. Contrary to previous methods, we do not adapt the  learning rates nor we make use of the assumed curvature of the objective function. Instead,  we reduce the optimization process to a game of betting on a coin and propose a learning rate free optimal algorithm for this scenario. Theoretical convergence is proven for convex and quasi-convex functions and empirical evidence shows  the advantage of our algorithm over popular stochastic gradient algorithms.
Dual-Agent GANs for Photorealistic and Identity Preserving Profile Face Synthesis
Authors: Jian Zhao, Lin Xiong, Panasonic Karlekar Jayashree, Jianshu Li, Fang Zhao, Zhecan Wang, Panasonic Sugiri Pranata, Panasonic Shengmei Shen, Shuicheng Yan, Jiashi Feng
Published in: Advances in Neural Information Processing Systems 30  (NIPS 2017) (Main Conference Track), 2017

Abstract: Synthesizing realistic profile faces is promising for more efficiently  training deep pose-invariant models for large-scale unconstrained face recognition, by populating samples with extreme poses and avoiding tedious annotations. However, learning from synthetic faces may not achieve the desired performance due to the discrepancy between distributions of the synthetic and real face images. To narrow this gap, we propose a Dual-Agent Generative Adversarial Network (DA-GAN) model, which can improve the realism of a face simulator's output using unlabeled real faces, while preserving the identity information during the realism refinement. The dual agents are specifically designed for distinguishing real v.s. fake and identities simultaneously. In particular, we employ an off-the-shelf 3D face model as a simulator to generate profile face images with varying poses. DA-GAN leverages a fully convolutional network as the generator to generate high-resolution images and an auto-encoder as the discriminator with the dual agents. Besides the novel architecture, we make several key modifications to the standard GAN to preserve pose and texture, preserve identity and stabilize training process: (i) a pose perception loss; (ii) an identity perception loss; (iii) an adversarial loss with a boundary equilibrium regularization term. Experimental results show that DA-GAN not only presents compelling perceptual results but also significantly outperforms state-of-the-arts on the large-scale and challenging NIST IJB-A unconstrained face recognition benchmark. In addition, the proposed DA-GAN is also promising as a new approach for solving generic transfer learning problems more effectively.
Thy Friend is My Friend: Iterative Collaborative Filtering for Sparse Matrix Estimation
Authors: Christian Borgs, Jennifer Chayes, Christina E. Lee, Devavrat Shah
Published in: Advances in Neural Information Processing Systems 30  (NIPS 2017) (Main Conference Track), 2017

Abstract: The sparse matrix estimation problem consists of estimating the distribution of an $n\times n$  matrix $Y$, from a sparsely observed single instance of this matrix where the entries of $Y$ are independent random variables. This captures a wide array of problems; special instances include matrix completion in the context of recommendation systems, graphon estimation, and community detection in (mixed membership) stochastic block models. Inspired by classical collaborative filtering for recommendation systems, we propose a novel iterative, collaborative filtering-style algorithm for matrix estimation in this generic setting. We show that the mean squared error (MSE) of our estimator converges to $0$ at the rate of $O(d^2 (pn)^{-2/5})$ as long as $\omega(d^5 n)$ random entries from a total of $n^2$ entries of $Y$ are observed (uniformly sampled), $\E[Y]$ has rank $d$, and the entries of $Y$ have bounded support. The maximum squared error across all entries converges to $0$ with high probability as long as we observe a little more, $\Omega(d^5 n \ln^5(n))$ entries. Our results are the best known sample complexity results in this generality.
Positive-Unlabeled Learning with Non-Negative Risk Estimator
Authors: Ryuichi Kiryo, Gang Niu, Marthinus C du Plessis, Masashi Sugiyama
Published in: Advances in Neural Information Processing Systems 30  (NIPS 2017) (Main Conference Track), 2017

Abstract: From only positive (P) and unlabeled (U) data, a binary classifier could be trained with PU learning, in which the state of the art is unbiased PU learning. However, if its model is very flexible, empirical risks on training data will go negative, and we will suffer from serious overfitting. In this paper, we propose a non-negative risk estimator for PU learning: when getting minimized, it is more robust against overfitting, and thus we are able to use very flexible models (such as deep neural networks) given limited P data. Moreover, we analyze the bias, consistency, and mean-squared-error reduction of the proposed risk estimator, and bound the estimation error of the resulting empirical risk minimizer. Experiments demonstrate that our risk estimator fixes the overfitting problem of its unbiased counterparts.
Gradient descent GAN optimization is locally stable
Authors: Vaishnavh Nagarajan, J. Zico Kolter
Published in: Advances in Neural Information Processing Systems 30  (NIPS 2017) (Main Conference Track), 2017

Abstract: Despite the growing prominence of generative adversarial   networks (GANs), optimization in GANs is still a poorly understood topic.  In this paper, we analyze   the ``gradient descent'' form of GAN optimization, i.e., the natural   setting where we simultaneously take small gradient steps in both generator   and discriminator parameters.  We show that even though GAN optimization   does \emph{not}    correspond to a convex-concave game (even for simple parameterizations), under   proper conditions, equilibrium points of this  optimization    procedure are still \emph{locally asymptotically stable} for the traditional   GAN formulation. On the other hand, we show that the recently proposed   Wasserstein GAN can have non-convergent limit cycles near equilibrium.   Motivated by this stability analysis, we    propose an additional regularization term for gradient descent GAN updates,   which \emph{is} able to guarantee local stability for both the WGAN and the   traditional GAN, and also shows practical promise in speeding up   convergence and addressing mode collapse.
Faster and Non-ergodic O(1/K) Stochastic Alternating Direction Method of Multipliers
Authors: Cong Fang, Feng Cheng, Zhouchen Lin
Published in: Advances in Neural Information Processing Systems 30  (NIPS 2017) (Main Conference Track), 2017

Abstract: We study stochastic convex optimization subjected to linear equality constraints. Traditional Stochastic Alternating Direction Method of Multipliers and its Nesterov's acceleration scheme can only achieve ergodic O(1/\sqrt{K}) convergence rates, where K is the number of iteration. By introducing Variance Reduction (VR) techniques, the convergence rates improve to ergodic O(1/K). In this paper, we propose a new stochastic ADMM which elaborately integrates Nesterov's extrapolation and VR techniques. With Nesterov’s extrapolation, our algorithm can achieve a non-ergodic O(1/K) convergence rate which is optimal for separable linearly constrained non-smooth convex problems, while the convergence rates of VR based ADMM methods are actually tight O(1/\sqrt{K}) in non-ergodic sense. To the best of our knowledge, this is the first work that achieves a truly accelerated, stochastic convergence rate for constrained convex problems. The experimental results demonstrate that our algorithm is significantly faster than the existing state-of-the-art stochastic ADMM methods.
Group Sparse Additive Machine
Authors: Hong Chen, Xiaoqian Wang, Cheng Deng, Heng Huang
Published in: Advances in Neural Information Processing Systems 30  (NIPS 2017) (Main Conference Track), 2017

Abstract: A family of learning algorithms generated from additive models have attracted much attention recently for their flexibility and interpretability in high dimensional data analysis. Among them, learning models with grouped variables have shown competitive performance for prediction and variable selection. However, the previous works mainly focus on the least squares regression problem, not the classification task. Thus, it is desired to design the new additive classification model with variable selection capability for many real-world applications which focus on high-dimensional data classification. To address this challenging problem, in this paper, we investigate the classification with group sparse additive models in reproducing kernel Hilbert spaces. A novel classification method, called as \emph{group sparse additive machine} (GroupSAM), is proposed to explore and utilize the structure information among the input variables. Generalization error bound is derived and proved by integrating the sample error analysis with empirical covering numbers and the hypothesis error estimate with the stepping stone technique. Our new bound shows that GroupSAM can achieve a satisfactory learning rate with polynomial decay. Experimental results on synthetic data and seven benchmark datasets consistently show the effectiveness of our new approach.
PixelGAN Autoencoders
Authors: Alireza Makhzani, Brendan J. Frey
Published in: Advances in Neural Information Processing Systems 30  (NIPS 2017) (Main Conference Track), 2017

Abstract: In this paper, we describe the "PixelGAN autoencoder", a generative autoencoder in which the generative path is a convolutional autoregressive neural network on pixels (PixelCNN) that is conditioned on a latent code, and the recognition path uses a generative adversarial network (GAN) to impose a prior distribution on the latent code. We show that different priors result in different decompositions of information between the latent code and the autoregressive decoder. For example, by imposing a Gaussian distribution as the prior, we can achieve a global vs. local decomposition, or by imposing a categorical distribution as the prior, we can disentangle the style and content information of images in an unsupervised fashion. We further show how the PixelGAN autoencoder with a categorical prior can be directly used in semi-supervised settings and achieve competitive semi-supervised classification results on the MNIST, SVHN and NORB datasets.
Excess Risk Bounds for the Bayes Risk using Variational Inference in Latent Gaussian Models
Authors: Rishit Sheth, Roni Khardon
Published in: Advances in Neural Information Processing Systems 30  (NIPS 2017) (Main Conference Track), 2017

Abstract: Bayesian models are established as one of the main successful paradigms for complex problems in machine learning. To handle intractable inference, research in this area has developed new approximation methods that are fast and effective. However, theoretical analysis of the performance of such approximations is not well developed. The paper furthers such analysis by providing bounds on the excess risk of variational inference algorithms and related regularized loss minimization algorithms for a large class of latent variable models with Gaussian latent variables. We strengthen previous results for variational algorithms by showing they are competitive with any point-estimate predictor. Unlike previous work, we also provide bounds on the risk of the \emph{Bayesian} predictor and not just the risk of the Gibbs predictor for the same approximate posterior. The bounds are applied in complex models including sparse Gaussian processes and correlated topic models. Theoretical results are complemented by identifying novel approximations to the Bayesian objective that attempt to minimize the risk directly. An empirical evaluation compares the variational and new algorithms shedding further light on their performance.
Online control of the false discovery rate with decaying memory
Authors: Aaditya Ramdas, Fanny Yang, Martin J. Wainwright, Michael I Jordan
Published in: Advances in Neural Information Processing Systems 30  (NIPS 2017) (Main Conference Track), 2017

Abstract: In the online multiple testing problem, p-values corresponding to different null hypotheses are presented one by one, and the decision of whether to reject a hypothesis must be made immediately, after which the next p-value is presented. Alpha-investing algorithms to control the false discovery rate were first formulated by Foster and Stine and have since been generalized and applied to various settings, varying from quality-preserving databases for science to multiple A/B tests for internet commerce. This paper improves the class of generalized alpha-investing algorithms (GAI) in four ways : (a) we show how to uniformly improve the power of the entire class of GAI procedures under independence by awarding more alpha-wealth for each rejection, giving a near win-win resolution to a dilemma raised by Javanmard and Montanari, (b) we demonstrate how to incorporate prior weights to indicate domain knowledge of which hypotheses are likely to be null or non-null, (c) we allow for differing penalties for false discoveries to indicate that some hypotheses may be more meaningful/important than others, (d) we define a new quantity called the \emph{decaying memory false discovery rate, or $\memfdr$} that may be more meaningful for applications with an explicit time component, using a discount factor to incrementally forget past decisions and alleviate some potential problems that we describe and name ``piggybacking'' and ``alpha-death''. Our GAI++ algorithms incorporate all four generalizations (a, b, c, d) simulatenously, and reduce to more powerful variants of earlier algorithms when the weights and decay are all set to unity.
Safe and Nested Subgame Solving for Imperfect-Information Games
Authors: Noam Brown, Tuomas Sandholm
Published in: Advances in Neural Information Processing Systems 30  (NIPS 2017) (Main Conference Track), 2017

Abstract: In imperfect-information games, the optimal strategy in a subgame may depend on the strategy in other, unreached subgames. Thus a subgame cannot be solved in isolation and must instead consider the strategy for the entire game as a whole, unlike perfect-information games. Nevertheless, it is possible to first approximate a solution for the whole game and then improve it in individual subgames. This is referred to as subgame solving. We introduce subgame-solving techniques that outperform prior methods both in theory and practice. We also show how to adapt them, and past subgame-solving techniques, to respond to opponent actions that are outside the original action abstraction; this significantly outperforms the prior state-of-the-art approach, action translation. Finally, we show that subgame solving can be repeated as the game progresses down the game tree, leading to far lower exploitability. These techniques were a key component of Libratus, the first AI to defeat top humans in heads-up no-limit Texas hold'em poker.
Dynamic Safe Interruptibility for Decentralized Multi-Agent Reinforcement Learning
Authors: El Mahdi El Mhamdi, Rachid Guerraoui, Hadrien Hendrikx, Alexandre Maurer
Published in: Advances in Neural Information Processing Systems 30  (NIPS 2017) (Main Conference Track), 2017

Abstract: In reinforcement learning, agents learn by performing actions and observing their outcomes. Sometimes, it is desirable for a human operator to interrupt an agent in order to prevent dangerous situations from happening. Yet, as part of their learning process, agents may link these interruptions, that impact their reward, to specific states and deliberately avoid them. The situation is particularly challenging in a multi-agent context because agents might not only learn from their own past interruptions, but also from those of other agents. Orseau and Armstrong defined safe interruptibility for one learner, but their work does not naturally extend to multi-agent systems. This paper introduces dynamic safe interruptibility, an alternative definition more suited to decentralized learning problems, and studies this notion in two learning frameworks: joint action learners and independent learners. We give realistic sufficient conditions on the learning algorithm to enable dynamic safe interruptibility in the case of joint action learners, yet show that these conditions are not sufficient for independent learners. We show however that if agents can detect interruptions, it is possible to prune the observations to ensure dynamic safe interruptibility even for independent learners.
Toward Multimodal Image-to-Image Translation
Authors: Jun-Yan Zhu, Richard Zhang, Deepak Pathak, Trevor Darrell, Alexei A Efros, Oliver Wang, Eli Shechtman
Published in: Advances in Neural Information Processing Systems 30  (NIPS 2017) (Main Conference Track), 2017

Abstract: Many image-to-image translation problems are ambiguous, as a single input image may correspond to multiple possible outputs. In this work, we aim to model a distribution of possible outputs in a conditional generative modeling setting. The ambiguity of the mapping is distilled in a low-dimensional latent vector, which can be randomly sampled at test time. A generator learns to map the given input, combined with this latent code, to the output. We explicitly encourage the connection between output and the latent code to be invertible. This helps prevent a many-to-one mapping from the latent code to the output during training, also known as the problem of mode collapse, and produces more diverse results. We explore several variants of this approach by employing different training objectives, network architectures, and methods of injecting the latent code. Our proposed method encourages bijective consistency between the latent encoding and output modes. We present a systematic comparison of our method and other variants on both perceptual realism and diversity.
The Marginal Value of Adaptive Gradient Methods in Machine Learning
Authors: Ashia C Wilson, Rebecca Roelofs, Mitchell Stern, Nati Srebro, Benjamin Recht
Published in: Advances in Neural Information Processing Systems 30  (NIPS 2017) (Main Conference Track), 2017

Abstract: Adaptive optimization methods, which perform local optimization with a metric constructed from the history of iterates, are becoming increasingly popular for training deep neural networks.  Examples include AdaGrad, RMSProp, and Adam. We show that for simple overparameterized problems, adaptive methods often find drastically different solutions than gradient descent (GD) or stochastic gradient descent (SGD).  We construct an illustrative binary classification problem where the data is linearly separable, GD and SGD achieve zero test error, and AdaGrad, Adam, and RMSProp attain test errors arbitrarily close to half.  We additionally study the empirical generalization capability of adaptive methods on several state-of-the-art deep learning models. We observe that the solutions found by adaptive methods generalize worse (often significantly worse) than SGD, even when these solutions have better training performance. These results suggest that practitioners should reconsider the use of adaptive methods to train neural networks.
Mean Field Residual Networks: On the Edge of Chaos
Authors: Ge Yang, Samuel Schoenholz
Published in: Advances in Neural Information Processing Systems 30  (NIPS 2017) (Main Conference Track), 2017

Abstract: We study randomly initialized residual networks using mean field theory and the theory of difference equations. Classical feedforward neural networks, such as those with tanh activations, exhibit exponential behavior on the average when propagating inputs forward or gradients backward. The exponential forward dynamics causes rapid collapsing of the input space geometry, while the exponential backward dynamics causes drastic vanishing or exploding gradients. We show, in contrast, that by adding skip connections, the network will, depending on the nonlinearity, adopt subexponential forward and backward dynamics, and in many cases in fact polynomial. The exponents of these polynomials are obtained through analytic methods and proved and verified empirically to be correct. In terms of the "edge of chaos" hypothesis, these subexponential and polynomial laws allow residual networks to "hover over the boundary between stability and chaos," thus preserving the geometry of the input space and the gradient information flow. In our experiments, for each activation function we study here, we initialize residual networks with different hyperparameters and train them on MNIST. Remarkably, our initialization time theory can accurately predict test time performance of these networks, by tracking either the expected amount of gradient explosion or the expected squared distance between the images of two input vectors. Importantly, we show, theoretically as well as empirically, that common initializations such as the Xavier or the He schemes are not optimal for residual networks, because the optimal initialization variances depend on the depth. Finally, we have made mathematical contributions by deriving several new identities for the kernels of powers of ReLU functions by relating them to the zeroth Bessel function of the second kind.
Non-convex Finite-Sum Optimization Via SCSG Methods
Authors: Lihua Lei, Cheng Ju, Jianbo Chen, Michael I Jordan
Published in: Advances in Neural Information Processing Systems 30  (NIPS 2017) (Main Conference Track), 2017

Abstract: We develop a class of algorithms, as variants of the stochastically controlled stochastic gradient (SCSG) methods , for the smooth nonconvex finite-sum optimization problem. Only assuming the smoothness of each component, the complexity of SCSG to reach a stationary point with $E \|\nabla f(x)\|^{2}\le \epsilon$ is $O(\min\{\epsilon^{-5/3}, \epsilon^{-1}n^{2/3}\})$, which strictly outperforms the stochastic gradient descent. Moreover, SCSG is never worse than the state-of-the-art methods based on variance reduction and it significantly outperforms them when the target accuracy is low. A similar acceleration is also achieved when the functions satisfy the Polyak-Lojasiewicz condition. Empirical experiments demonstrate that SCSG outperforms stochastic gradient methods on training multi-layers neural networks in terms of both training and validation loss.
First-Order Adaptive Sample Size Methods to Reduce Complexity of Empirical Risk Minimization
Authors: Aryan Mokhtari, Alejandro Ribeiro
Published in: Advances in Neural Information Processing Systems 30  (NIPS 2017) (Main Conference Track), 2017

Abstract: This paper studies empirical risk minimization (ERM) problems for large-scale datasets and incorporates the idea of adaptive sample size methods to improve the guaranteed convergence bounds for first-order stochastic and deterministic methods. In contrast to traditional methods that attempt to solve the ERM problem corresponding to the full dataset directly, adaptive sample size schemes start with a small number of samples and solve the corresponding ERM problem to its statistical accuracy. The sample size is then grown geometrically -- e.g., scaling by a factor of two -- and use the solution of the previous ERM as a warm start for the new ERM. Theoretical analyses show that the use of adaptive sample size methods reduces the overall computational cost of achieving the statistical accuracy of the whole dataset for a broad range of deterministic and stochastic first-order methods. The gains are specific to the choice of method. When particularized to, e.g., accelerated gradient descent and stochastic variance reduce gradient, the computational cost advantage is a logarithm of the number of training samples. Numerical experiments on various datasets confirm theoretical claims and showcase the gains of using the proposed adaptive sample size scheme.
Doubly Stochastic Variational Inference for Deep Gaussian Processes
Authors: Hugh Salimbeni, Marc Deisenroth
Published in: Advances in Neural Information Processing Systems 30  (NIPS 2017) (Main Conference Track), 2017

Abstract: Deep Gaussian processes (DGPs) are multi-layer generalizations of GPs, but inference in these models has proved challenging. Existing approaches to inference in DGP models assume approximate posteriors that force independence between the layers, and do not work well in practice. We present a doubly stochastic variational inference algorithm, which does not force independence between layers. With our method of inference we demonstrate that a DGP model can be used effectively on data ranging in size from hundreds to a billion points. We provide strong empirical evidence that our inference scheme for DGPs works well in practice in both classification and regression.
From Parity to Preference-based Notions of Fairness in Classification
Authors: Muhammad Bilal Zafar, Isabel Valera, Manuel Rodriguez, Krishna Gummadi, Adrian Weller
Published in: Advances in Neural Information Processing Systems 30  (NIPS 2017) (Main Conference Track), 2017

Abstract: The adoption of automated, data-driven decision making in an ever expanding range of applications has raised concerns about its potential unfairness towards certain social groups. In this context, a number of recent studies have focused on defining, detecting, and removing unfairness from data-driven decision systems. However, the existing notions of fairness, based on parity (equality) in treatment or outcomes for different social groups, tend to be quite stringent, limiting the overall decision making accuracy. In this paper, we draw inspiration from the fair-division and envy-freeness literature in economics and game theory and propose preference-based notions of fairness -- given the choice between various sets of decision treatments or outcomes, any group of users would collectively prefer its treatment or outcomes, regardless of the (dis)parity as compared to the other groups. Then, we introduce tractable proxies to design margin-based classifiers that satisfy these preference-based notions of fairness. Finally, we experiment with a variety of synthetic and real-world datasets and show that preference-based fairness allows for greater decision accuracy than parity-based fairness.
Nonparametric Online Regression while Learning the Metric
Authors: Ilja Kuzborskij, Nicolò Cesa-Bianchi
Published in: Advances in Neural Information Processing Systems 30  (NIPS 2017) (Main Conference Track), 2017

Abstract: We study algorithms for online nonparametric regression that learn the directions along which the regression function is smoother. Our algorithm learns the Mahalanobis metric based on the gradient outer product matrix $\boldsymbol{G}$ of the regression function (automatically adapting to the effective rank of this matrix), while simultaneously bounding the regret ---on the same data sequence--- in terms of the spectrum of $\boldsymbol{G}$. As a preliminary step in our analysis, we extend a nonparametric online learning algorithm by Hazan and Megiddo enabling it to compete against functions whose Lipschitzness is measured with respect to an arbitrary Mahalanobis metric.
Stochastic Optimization with Variance Reduction for Infinite Datasets with Finite Sum Structure
Authors: Alberto Bietti, Julien Mairal
Published in: Advances in Neural Information Processing Systems 30  (NIPS 2017) (Main Conference Track), 2017

Abstract: Stochastic optimization algorithms with variance reduction have proven successful for minimizing large finite sums of functions. Unfortunately, these techniques are unable to deal with stochastic perturbations of input data, induced for example by data augmentation. In such cases, the objective is no longer a finite sum, and the main candidate for optimization is the stochastic gradient descent method (SGD). In this paper, we introduce a variance reduction approach for these settings when the objective is composite and strongly convex. The convergence rate outperforms SGD with a typically much smaller constant factor, which depends on the variance of gradient estimates only due to perturbations on a single example.
Working hard to know your neighbor's margins: Local descriptor learning loss
Authors: Anastasiia Mishchuk, Dmytro Mishkin, Filip Radenovic, Jiri Matas
Published in: Advances in Neural Information Processing Systems 30  (NIPS 2017) (Main Conference Track), 2017

Abstract: We introduce a loss for metric learning, which is inspired by the Lowe's matching criterion for SIFT. We show that the proposed loss, that maximizes the distance between the closest positive and closest negative example in the batch, is better than complex regularization methods; it works well for both shallow and deep convolution network architectures. Applying the novel loss to the L2Net CNN architecture results in a compact descriptor named HardNet. It has the same dimensionality as SIFT (128) and shows state-of-art performance in wide baseline stereo, patch verification and instance retrieval benchmarks.
Lookahead  Bayesian Optimization with Inequality Constraints
Authors: Remi Lam, Karen Willcox
Published in: Advances in Neural Information Processing Systems 30  (NIPS 2017) (Main Conference Track), 2017

Abstract: We consider the task of optimizing an objective function subject to inequality constraints when both the objective and the constraints are expensive to evaluate. Bayesian optimization (BO) is a popular way to tackle optimization problems with expensive objective function evaluations, but has mostly been applied to unconstrained problems. Several BO approaches have been proposed to address expensive constraints but are limited to greedy strategies maximizing immediate reward. To address this limitation, we propose a lookahead approach that selects the next evaluation in order to maximize the long-term feasible reduction of the objective function. We present numerical experiments demonstrating the performance improvements of such a lookahead approach compared to several greedy BO algorithms, including constrained expected improvement (EIC) and predictive entropy search with constraint (PESC).
Online Learning with Transductive Regret
Authors: Mehryar Mohri, Scott Yang
Published in: Advances in Neural Information Processing Systems 30  (NIPS 2017) (Main Conference Track), 2017

Abstract: We study online learning with the general notion of transductive regret, that is regret with modification rules applying to expert sequences (as opposed to single experts) that are representable by weighted finite-state transducers. We show how transductive regret generalizes existing notions of regret, including: (1) external regret; (2) internal regret; (3) swap regret; and (4) conditional swap regret. We present a general and efficient online learning algorithm for minimizing transductive regret. We further extend that to design efficient algorithms for the time-selection and sleeping expert settings. A by-product of our study is an algorithm for swap regret, which, under mild assumptions, is more efficient than existing ones, and a substantially more efficient algorithm for time selection swap regret.
Pixels to Graphs by Associative Embedding
Authors: Alejandro Newell, Jia Deng
Published in: Advances in Neural Information Processing Systems 30  (NIPS 2017) (Main Conference Track), 2017

Abstract: Graphs are a useful abstraction of image content. Not only can graphs represent details about individual objects in a scene but they can capture the interactions between pairs of objects. We present a method for training a convolutional neural network such that it takes in an input image and produces a full graph definition. This is done end-to-end in a single stage with the use of associative embeddings. The network learns to simultaneously identify all of the elements that make up a graph and piece them together. We benchmark on the Visual Genome dataset, and demonstrate state-of-the-art performance on the challenging task of scene graph generation.
Accelerated Stochastic Greedy Coordinate Descent by Soft Thresholding Projection onto Simplex
Authors: Chaobing Song, Shaobo Cui, Yong Jiang, Shu-Tao Xia
Published in: Advances in Neural Information Processing Systems 30  (NIPS 2017) (Main Conference Track), 2017

Abstract: In this paper we study the well-known greedy coordinate descent (GCD)  algorithm to solve $\ell_1$-regularized problems and improve GCD by the two popular strategies: Nesterov's acceleration and stochastic optimization. Firstly, we propose a new rule for greedy selection based on an $\ell_1$-norm square approximation  which is nontrivial to solve but convex; then an efficient algorithm called ``SOft ThreshOlding PrOjection (SOTOPO)'' is proposed to exactly solve the $\ell_1$-regularized $\ell_1$-norm square approximation problem, which is induced by the new rule.  Based on the new rule and the SOTOPO algorithm, the Nesterov's acceleration and stochastic optimization strategies are then successfully applied to the GCD algorithm. The resulted algorithm called accelerated stochastic greedy coordinate descent (ASGCD) has the optimal convergence rate $O(\sqrt{1/\epsilon})$;  meanwhile, it reduces the iteration complexity of greedy selection up to a factor of sample size. Both theoretically and empirically, we show that ASGCD has better performance for high-dimensional and dense problems with sparse solution.
Reinforcement Learning under Model Mismatch
Authors: Aurko Roy, Huan Xu, Sebastian Pokutta
Published in: Advances in Neural Information Processing Systems 30  (NIPS 2017) (Main Conference Track), 2017

Abstract: We study reinforcement learning under model misspecification,   where we do not have access to the true environment but only to a   reasonably close approximation to it. We address this problem by   extending the framework of robust MDPs to the model-free   Reinforcement Learning setting, where we do not have access to the   model parameters, but can only sample states from it.  We define   robust versions of Q-learning, Sarsa, and   TD-learning and prove convergence to an approximately optimal   robust policy and approximate value function respectively.  We scale   up the robust algorithms to large MDPs via function approximation   and prove convergence under two different settings. We prove   convergence of robust approximate policy iteration and robust   approximate value iteration for linear architectures (under mild   assumptions). We also define a   robust loss function, the mean squared robust projected     Bellman error and give stochastic gradient descent algorithms   that are guaranteed to converge to a local minimum.
Concrete Dropout
Authors: Yarin Gal, Jiri Hron, Alex Kendall
Published in: Advances in Neural Information Processing Systems 30  (NIPS 2017) (Main Conference Track), 2017

Abstract: Dropout is used as a practical tool to obtain uncertainty estimates in large vision models and reinforcement learning (RL) tasks. But to obtain well-calibrated uncertainty estimates, a grid-search over the dropout probabilities is necessary—a prohibitive operation with large models, and an impossible one with RL. We propose a new dropout variant which gives improved performance and better calibrated uncertainties. Relying on recent developments in Bayesian deep learning, we use a continuous relaxation of dropout’s discrete masks. Together with a principled optimisation objective, this allows for automatic tuning of the dropout probability in large models, and as a result faster experimentation cycles. In RL this allows the agent to adapt its uncertainty dynamically as more data is observed. We analyse the proposed variant extensively on a range of tasks, and give insights into common practice in the field where larger dropout probabilities are often used in deeper model layers.
Multiresolution Kernel Approximation for Gaussian Process Regression
Authors: Yi Ding, Risi Kondor, Jonathan Eskreis-Winkler
Published in: Advances in Neural Information Processing Systems 30  (NIPS 2017) (Main Conference Track), 2017

Abstract: Gaussian process regression generally does not scale to beyond a few thousands data points without applying some sort of kernel approximation method. Most approximations focus on the high eigenvalue part of the spectrum of the kernel matrix, $K$, which leads to bad performance when the length scale of the kernel is small. In this paper we introduce Multiresolution Kernel Approximation (MKA), the first true broad bandwidth kernel approximation algorithm.  Important points about MKA are that it is memory efficient, and it is a direct method,  which means that it also makes it easy to approximate $K^{-1}$ and $\mathop{\textrm{det}}(K)$.
Near Minimax Optimal Players for the Finite-Time 3-Expert Prediction Problem
Authors: Yasin Abbasi Yadkori, Peter L Bartlett, Victor Gabillon
Published in: Advances in Neural Information Processing Systems 30  (NIPS 2017) (Main Conference Track), 2017

Abstract: We study minimax strategies for the online prediction problem with expert advice. It has been conjectured that a simple adversary strategy, called COMB, is near optimal in this game for any number of experts. Our results and new insights make progress in this direction by showing that, up to a small additive term, COMB is minimax optimal in the finite-time three expert problem. In addition, we provide for this setting a new near minimax optimal COMB-based learner. Prior to this work, in this problem, learners obtaining the optimal multiplicative constant in their regret rate were known only when $K=2$ or $K\rightarrow\infty$. We characterize, when $K=3$, the regret of the game scaling as $\sqrt{8/(9\pi)T}\pm \log(T)^2$ which gives for the first time the optimal constant in the leading ($\sqrt{T}$) term of the regret.