mtybilly/Instruct2DS huggingface dataset:
Minibatch Gibbs Sampling on Large Graphical Models
Authors: De Sa, Chris and Chen, Vincent and Wong, Wing
Published in: Proceedings of the 35th International Conference on Machine Learning (Main Conference Track), 2018

Abstract: Gibbs sampling is the de facto Markov chain Monte Carlo method used for inference and learning on large scale graphical models. For complicated factor graphs with lots of factors, the performance of Gibbs sampling can be limited by the computational cost of executing a single update step of the Markov chain. This cost is proportional to the degree of the graph, the number of factors adjacent to each variable. In this paper, we show how this cost can be reduced by using minibatching: subsampling the factors to form an estimate of their sum. We introduce several minibatched variants of Gibbs, show that they can be made unbiased, prove bounds on their convergence rates, and show that under some conditions they can result in asymptotic single-update-run-time speedups over plain Gibbs sampling.
Stochastic Video Generation with a Learned Prior
Authors: Denton, Emily and Fergus, Rob
Published in: Proceedings of the 35th International Conference on Machine Learning (Main Conference Track), 2018

Abstract: Generating video frames that accurately predict future world states is challenging. Existing approaches either fail to capture the full distribution of outcomes, or yield blurry generations, or both. In this paper we introduce a video generation model with a learned prior over stochastic latent variables at each time step. Video frames are generated by drawing samples from this prior and combining them with a deterministic estimate of the future frame. The approach is simple and easily trained end-to-end on a variety of datasets. Sample generations are both varied and sharp, even many frames into the future, and compare favorably to those from existing approaches.
Decomposition of Uncertainty in Bayesian Deep Learning for Efficient and Risk-sensitive Learning
Authors: Depeweg, Stefan and Hernandez-Lobato, Jose-Miguel and Doshi-Velez, Finale and Udluft, Steffen
Published in: Proceedings of the 35th International Conference on Machine Learning (Main Conference Track), 2018

Abstract: Bayesian neural networks with latent variables are scalable and flexible probabilistic models: they account for uncertainty in the estimation of the network weights and, by making use of latent variables, can capture complex noise patterns in the data. Using these models we show how to perform and utilize a decomposition of uncertainty in aleatoric and epistemic components for decision making purposes. This allows us to successfully identify informative points for active learning of functions with heteroscedastic and bimodal noise. Using the decomposition we further define a novel risk-sensitive criterion for reinforcement learningto identify policies that balance expected cost, model-bias and noise aversion.
Accurate Inference for Adaptive Linear Models
Authors: Deshpande, Yash and Mackey, Lester and Syrgkanis, Vasilis and Taddy, Matt
Published in: Proceedings of the 35th International Conference on Machine Learning (Main Conference Track), 2018

Abstract: Estimators computed from adaptively collected data do not behave like their non-adaptive brethren.Rather, the sequential dependence of the collection policy can lead to severe distributional biases that persist even in the infinite data limit. We develop a general method – <em>$퐖$-decorrelation</em> – for transforming the bias of adaptive linear regression estimators into variance. The method uses only coarse-grained information about the data collection policy and does not need access to propensity scores or exact knowledge of the policy.We bound the finite-sample bias and variance of the $퐖$-estimator and develop asymptotically correct confidence intervals based on a novel martingale central limit theorem. We then demonstrate the empirical benefits of the generic $퐖$-decorrelation procedure in two different adaptive data settings: the multi-armed bandit and the autoregressive time series.
Variational Network Inference: Strong and Stable with Concrete Support
Authors: Dezfouli, Amir and Bonilla, Edwin and Nock, Richard
Published in: Proceedings of the 35th International Conference on Machine Learning (Main Conference Track), 2018

Abstract: Traditional methods for the discovery of latent network structures are limited in two ways: they either assume that all the signal comes from the network (i.e. there is no source of signal outside the network) or they place constraints on the network parameters to ensure model or algorithmic stability. We address these limitations by proposing a model that incorporates a Gaussian process prior on a network-independent component and formally proving that we get algorithmic stability for free while providing a novel perspective on model stability as well as robustness results and precise intervals for key inference parameters. We show that, on three applications, our approach outperforms previous methods consistently.
Modeling Sparse Deviations for Compressed Sensing using Generative Models
Authors: Dhar, Manik and Grover, Aditya and Ermon, Stefano
Published in: Proceedings of the 35th International Conference on Machine Learning (Main Conference Track), 2018

Abstract: In compressed sensing, a small number of linear measurements can be used to reconstruct an unknown signal. Existing approaches leverage assumptions on the structure of these signals, such as sparsity or the availability of a generative model. A domain-specific generative model can provide a stronger prior and thus allow for recovery with far fewer measurements. However, unlike sparsity-based approaches, existing methods based on generative models guarantee exact recovery only over their support, which is typically only a small subset of the space on which the signals are defined. We propose Sparse-Gen, a framework that allows for sparse deviations from the support set, thereby achieving the best of both worlds by using a domain specific prior and allowing reconstruction over the full space of signals. Theoretically, our framework provides a new class of signals that can be acquired using compressed sensing, reducing classic sparse vector recovery to a special case and avoiding the restrictive support due to a generative model prior. Empirically, we observe consistent improvements in reconstruction accuracy over competing approaches, especially in the more practical setting of transfer compressed sensing where a generative model for a data-rich, source domain aids sensing on a data-scarce, target domain.
Alternating Randomized Block Coordinate Descent
Authors: Diakonikolas, Jelena and Orecchia, Lorenzo
Published in: Proceedings of the 35th International Conference on Machine Learning (Main Conference Track), 2018

Abstract: Block-coordinate descent algorithms and alternating minimization methods are fundamental optimization algorithms and an important primitive in large-scale optimization and machine learning. While various block-coordinate-descent-type methods have been studied extensively, only alternating minimization – which applies to the setting of only two blocks – is known to have convergence time that scales independently of the least smooth block. A natural question is then: is the setting of two blocks special? We show that the answer is “no” as long as the least smooth block can be optimized exactly – an assumption that is also needed in the setting of alternating minimization. We do so by introducing a novel algorithm AR-BCD, whose convergence time scales independently of the least smooth (possibly non-smooth) block. The basic algorithm generalizes both alternating minimization and randomized block coordinate (gradient) descent, and we also provide its accelerated version – AAR-BCD.
Learning to Act in Decentralized Partially Observable MDPs
Authors: Dibangoye, Jilles and Buffet, Olivier
Published in: Proceedings of the 35th International Conference on Machine Learning (Main Conference Track), 2018

Abstract: We address a long-standing open problem of reinforcement learning in decentralized partially observable Markov decision processes. Previous attempts focussed on different forms of generalized policy iteration, which at best led to local optima. In this paper, we restrict attention to plans, which are simpler to store and update than policies. We derive, under certain conditions, the first near-optimal cooperative multi-agent reinforcement learning algorithm. To achieve significant scalability gains, we replace the greedy maximization by mixed-integer linear programming. Experiments show our approach can learn to act near-optimally in many finite domains from the literature.
Leveraging Well-Conditioned Bases: Streaming and Distributed Summaries in Minkowski $p$-Norms
Authors: Dickens, Charlie and Cormode, Graham and Woodruff, David
Published in: Proceedings of the 35th International Conference on Machine Learning (Main Conference Track), 2018

Abstract: Work on approximate linear algebra has led to efficient distributed and streaming algorithms for problems such as approximate matrix multiplication, low rank approximation, and regression, primarily for the Euclidean norm $\ell_2$. We study other $\ell_p$ norms, which are more robust for $p < 2$, and can be used to find outliers for $p > 2$. Unlike previous algorithms for such norms, we give algorithms that are (1) deterministic, (2) work simultaneously for every $p ≥ 1$, including $p = ınfty$, and (3) can be implemented in both distributed and streaming environments. We study $\ell_p$-regression, entrywise $\ell_p$-low rank approximation, and versions of approximate matrix multiplication.
Noisin: Unbiased Regularization for Recurrent Neural Networks
Authors: Dieng, Adji Bousso and Ranganath, Rajesh and Altosaar, Jaan and Blei, David
Published in: Proceedings of the 35th International Conference on Machine Learning (Main Conference Track), 2018

Abstract: Recurrent neural networks (RNNs) are powerful models of sequential data. They have been successfully used in domains such as text and speech. However, RNNs are susceptible to overfitting; regularization is important. In this paper we develop Noisin, a new method for regularizing RNNs. Noisin injects random noise into the hidden states of the RNN and then maximizes the corresponding marginal likelihood of the data. We show how Noisin applies to any RNN and we study many different types of noise. Noisin is unbiased–it preserves the underlying RNN on average. We characterize how Noisin regularizes its RNN both theoretically and empirically. On language modeling benchmarks, Noisin improves over dropout by as much as 12.2% on the Penn Treebank and 9.4% on the Wikitext-2 dataset. We also compared the state-of-the-art language model of Yang et al. 2017, both with and without Noisin. On the Penn Treebank, the method with Noisin more quickly reaches state-of-the-art performance.
Discovering and Removing Exogenous State Variables and Rewards for Reinforcement Learning
Authors: Dietterich, Thomas and Trimponias, George and Chen, Zhitang
Published in: Proceedings of the 35th International Conference on Machine Learning (Main Conference Track), 2018

Abstract: Exogenous state variables and rewards can slow down reinforcement learning by injecting uncontrolled variation into the reward signal. We formalize exogenous state variables and rewards and identify conditions under which an MDP with exogenous state can be decomposed into an exogenous Markov Reward Process involving only the exogenous state+reward and an endogenous Markov Decision Process defined with respect to only the endogenous rewards. We also derive a variance-covariance condition under which Monte Carlo policy evaluation on the endogenous MDP is accelerated compared to using the full MDP. Similar speedups are likely to carry over to all RL algorithms. We develop two algorithms for discovering the exogenous variables and test them on several MDPs. Results show that the algorithms are practical and can significantly speed up reinforcement learning.
Coordinated Exploration in Concurrent Reinforcement Learning
Authors: Dimakopoulou, Maria and Van Roy, Benjamin
Published in: Proceedings of the 35th International Conference on Machine Learning (Main Conference Track), 2018

Abstract: We consider a team of reinforcement learning agents that concurrently learn to operate in a common environment. We identify three properties - adaptivity, commitment, and diversity - which are necessary for efficient coordinated exploration and demonstrate that straightforward extensions to single-agent optimistic and posterior sampling approaches fail to satisfy them. As an alternative, we propose seed sampling, which extends posterior sampling in a manner that meets these requirements. Simulation results investigate how per-agent regret decreases as the number of agents grows, establishing substantial advantages of seed sampling over alternative exploration schemes.
Probabilistic Recurrent State-Space Models
Authors: Doerr, Andreas and Daniel, Christian and Schiegg, Martin and Duy, Nguyen-Tuong and Schaal, Stefan and Toussaint, Marc and Sebastian, Trimpe
Published in: Proceedings of the 35th International Conference on Machine Learning (Main Conference Track), 2018

Abstract: State-space models (SSMs) are a highly expressive model class for learning patterns in time series data and for system identification. Deterministic versions of SSMs (e.g., LSTMs) proved extremely successful in modeling complex time series data. Fully probabilistic SSMs, however, are often found hard to train, even for smaller problems. We propose a novel model formulation and a scalable training algorithm based on doubly stochastic variational inference and Gaussian processes. This combination allows efficient incorporation of latent state temporal correlations, which we found to be key to robust training. The effectiveness of the proposed PR-SSM is evaluated on a set of real-world benchmark datasets in comparison to state-of-the-art probabilistic model learning methods. Scalability and robustness are demonstrated on a high dimensional problem.
Randomized Block Cubic Newton Method
Authors: Doikov, Nikita and Richtarik, Peter and of Edinburgh, University
Published in: Proceedings of the 35th International Conference on Machine Learning (Main Conference Track), 2018

Abstract: We study the problem of minimizing the sum of three convex functions: a differentiable, twice-differentiable and a non-smooth term in a high dimensional setting. To this effect we propose and analyze a randomized block cubic Newton (RBCN) method, which in each iteration builds a model of the objective function formed as the sum of the natural models of its three components: a linear model with a quadratic regularizer for the differentiable term, a quadratic model with a cubic regularizer for the twice differentiable term, and perfect (proximal) model for the nonsmooth term. Our method in each iteration minimizes the model over a random subset of blocks of the search variable. RBCN is the first algorithm with these properties, generalizing several existing methods, matching the best known bounds in all special cases. We establish $a̧l O(1/ε)$, $\ļ O(1/\sqrtε)$ and $\c ̧O(łog (1/ε))$ rates under different assumptions on the component functions. Lastly, we show numerically that our method outperforms the state-of-the-art on a variety of machine learning problems, including cubically regularized least-squares, logistic regression with constraints, and Poisson regression.
Low-Rank Riemannian Optimization on Positive Semidefinite Stochastic Matrices with Applications to Graph Clustering
Authors: Douik, Ahmed and Hassibi, Babak
Published in: Proceedings of the 35th International Conference on Machine Learning (Main Conference Track), 2018

Abstract: This paper develops a Riemannian optimization framework for solving optimization problems on the set of symmetric positive semidefinite stochastic matrices. The paper first reformulates the problem by factorizing the optimization variable as $퐗=퐘퐘^T$ and deriving conditions on $p$, i.e., the number of columns of $퐘$, under which the factorization yields a satisfactory solution. The reparameterization of the problem allows its formulation as an optimization over either an embedded or quotient Riemannian manifold whose geometries are investigated. In particular, the paper explicitly derives the tangent space, Riemannian gradients and retraction operator that allow the design of efficient optimization methods on the proposed manifolds. The numerical results reveal that, when the optimal solution has a known low-rank, the resulting algorithms present a clear complexity advantage when compared with state-of-the-art Euclidean and Riemannian approaches for graph clustering applications.
Essentially No Barriers in Neural Network Energy Landscape
Authors: Draxler, Felix and Veschgini, Kambis and Salmhofer, Manfred and Hamprecht, Fred
Published in: Proceedings of the 35th International Conference on Machine Learning (Main Conference Track), 2018

Abstract: Training neural networks involves finding minima of a high-dimensional non-convex loss function. Relaxing from linear interpolations, we construct continuous paths between minima of recent neural network architectures on CIFAR10 and CIFAR100. Surprisingly, the paths are essentially flat in both the training and test landscapes. This implies that minima are perhaps best seen as points on a single connected manifold of low loss, rather than as the bottoms of distinct valleys.
Weakly Consistent Optimal Pricing Algorithms in Repeated Posted-Price Auctions with Strategic Buyer
Authors: Drutsa, Alexey
Published in: Proceedings of the 35th International Conference on Machine Learning (Main Conference Track), 2018

Abstract: We study revenue optimization learning algorithms for repeated posted-price auctions where a seller interacts with a single strategic buyer that holds a fixed private valuation for a good and seeks to maximize his cumulative discounted surplus. We propose a novel algorithm that never decreases offered prices and has a tight strategic regret bound of $Θ(łogłog T)$. This result closes the open research question on the existence of a no-regret horizon-independent weakly consistent pricing. We also show that the property of non-decreasing prices is nearly necessary for a weakly consistent algorithm to be a no-regret one.
On the Power of Over-parametrization in Neural Networks with Quadratic Activation
Authors: Du, Simon and Lee, Jason
Published in: Proceedings of the 35th International Conference on Machine Learning (Main Conference Track), 2018

Abstract: We provide new theoretical insights on why over-parametrization is effective in learning neural networks. For a $k$ hidden node shallow network with quadratic activation and $n$ training data points, we show as long as $ k \ge \sqrt2n$, over-parametrization enables local search algorithms to find a <em>globally</em> optimal solution for general smooth and convex loss functions. Further, despite that the number of parameters may exceed the sample size, using theory of Rademacher complexity, we show with weight decay, the solution also generalizes well if the data is sampled from a regular distribution such as Gaussian. To prove when $k\ge \sqrt2n$, the loss function has benign landscape properties, we adopt an idea from smoothed analysis, which may have other applications in studying loss surfaces of neural networks.
Gradient Descent Learns One-hidden-layer CNN: Don’t be Afraid of Spurious Local Minima
Authors: Du, Simon and Lee, Jason and Tian, Yuandong and Singh, Aarti and Poczos, Barnabas
Published in: Proceedings of the 35th International Conference on Machine Learning (Main Conference Track), 2018

Abstract: We consider the problem of learning an one-hidden-layer neural network with non-overlapping convolutional layer and ReLU activation function, i.e., $f(Z; w, a) = ∑_j a_jσ(w^⊤ Z_j)$, in which both the convolutional weights $w$ and the output weights $a$ are parameters to be learned. We prove that with Gaussian input $퐙$ there is a spurious local minimizer. Surprisingly, in the presence of the spurious local minimizer, starting from randomly initialized weights, gradient descent with weight normalization can still be proven to recover the true parameters with constant probability (which can be boosted to probability $1$ with multiple restarts). We also show that with constant probability, the same procedure could also converge to the spurious local minimum, showing that the local minimum plays a non-trivial role in the dynamics of gradient descent. Furthermore, a quantitative analysis shows that the gradient descent dynamics has two phases: it starts off slow, but converges much faster after several iterations.
Investigating Human Priors for Playing Video Games
Authors: Dubey, Rachit and Agrawal, Pulkit and Pathak, Deepak and Griffiths, Tom and Efros, Alexei
Published in: Proceedings of the 35th International Conference on Machine Learning (Main Conference Track), 2018

Abstract: What makes humans so good at solving seemingly complex video games? Unlike computers, humans bring in a great deal of prior knowledge about the world, enabling efficient decision making. This paper investigates the role of human priors for solving video games. Given a sample game, we conduct a series of ablation studies to quantify the importance of various priors on human performance. We do this by modifying the video game environment to systematically mask different types of visual information that could be used by humans as priors. We find that removal of some prior knowledge causes a drastic degradation in the speed with which human players solve the game, e.g. from 2 minutes to over 20 minutes. Furthermore, our results indicate that general priors, such as the importance of objects and visual consistency, are critical for efficient game-play. Videos and the game manipulations are available at https://rach0012.github.io/humanRL_website/
A Distributed Second-Order Algorithm You Can Trust
Authors: Duenner, Celestine and Lucchi, Aurelien and Gargiani, Matilde and Bian, An and Hofmann, Thomas and Jaggi, Martin
Published in: Proceedings of the 35th International Conference on Machine Learning (Main Conference Track), 2018

Abstract: Due to the rapid growth of data and computational resources, distributed optimization has become an active research area in recent years. While first-order methods seem to dominate the field, second-order methods are nevertheless attractive as they potentially require fewer communication rounds to converge. However, there are significant drawbacks that impede their wide adoption, such as the computation and the communication of a large Hessian matrix. In this paper we present a new algorithm for distributed training of generalized linear models that only requires the computation of diagonal blocks of the Hessian matrix on the individual workers. To deal with this approximate information we propose an adaptive approach that - akin to trust-region methods - dynamically adapts the auxiliary model to compensate for modeling errors. We provide theoretical rates of convergence for a wide class of problems including $L_1$-regularized objectives. We also demonstrate that our approach achieves state-of-the-art results on multiple large benchmark datasets.
Computational Optimal Transport: Complexity by Accelerated Gradient Descent Is Better Than by Sinkhorn’s Algorithm
Authors: Dvurechensky, Pavel and Gasnikov, Alexander and Kroshnin, Alexey
Published in: Proceedings of the 35th International Conference on Machine Learning (Main Conference Track), 2018

Abstract: We analyze two algorithms for approximating the general optimal transport (OT) distance between two discrete distributions of size $n$, up to accuracy $ɛ$. For the first algorithm, which is based on the celebrated Sinkhorn’s algorithm, we prove the complexity bound $\widetildeOłeft(\fracn^2ɛ^2i̊ght)$ arithmetic operations ($\widetildeO$ hides polylogarithmic factors $(łn n)^c$, $c>0$). For the second one, which is based on our novel Adaptive Primal-Dual Accelerated Gradient Descent (APDAGD) algorithm, we prove the complexity bound $\widetildeOłeft(\minłeft\\fracn^9/4ɛ, \fracn^2ɛ^2 \g̊ht\\rh̊t)$ arithmetic operations. Both bounds have better dependence on $ɛ$ than the state-of-the-art result given by $\widetildeOłeft(\fracn^2ɛ^3\rit̊)$. Our second algorithm not only has better dependence on $ɛ$ in the complexity bound, but also is not specific to entropic regularization and can solve the OT problem with different regularizers.
Entropy-SGD optimizes the prior of a PAC-Bayes bound: Generalization properties of Entropy-SGD and data-dependent priors
Authors: Dziugaite, Gintare Karolina and Roy, Daniel
Published in: Proceedings of the 35th International Conference on Machine Learning (Main Conference Track), 2018

Abstract: We show that Entropy-SGD (Chaudhari et al., 2017), when viewed as a learning algorithm, optimizes a PAC-Bayes bound on the risk of a Gibbs (posterior) classifier, i.e., a randomized classifier obtained by a risk-sensitive perturbation of the weights of a learned classifier. Entropy-SGD works by optimizing the bound’s prior, violating the hypothesis of the PAC-Bayes theorem that the prior is chosen independently of the data. Indeed, available implementations of Entropy-SGD rapidly obtain zero training error on random labels and the same holds of the Gibbs posterior. In order to obtain a valid generalization bound, we rely on a result showing that data-dependent priors obtained by stochastic gradient Langevin dynamics (SGLD) yield valid PAC-Bayes bounds provided the target distribution of SGLD is eps-differentially private. We observe that test error on MNIST and CIFAR10 falls within the (empirically nonvacuous) risk bounds computed under the assumption that SGLD reaches stationarity. In particular, Entropy-SGLD can be configured to yield relatively tight generalization bounds and still fit real labels, although these same settings do not obtain state-of-the-art performance.
Beyond the One-Step Greedy Approach in Reinforcement Learning
Authors: Efroni, Yonathan and Dalal, Gal and Scherrer, Bruno and Mannor, Shie
Published in: Proceedings of the 35th International Conference on Machine Learning (Main Conference Track), 2018

Abstract: The famous Policy Iteration algorithm alternates between policy improvement and policy evaluation. Implementations of this algorithm with several variants of the latter evaluation stage, e.g, n-step and trace-based returns, have been analyzed in previous works. However, the case of multiple-step lookahead policy improvement, despite the recent increase in empirical evidence of its strength, has to our knowledge not been carefully analyzed yet. In this work, we introduce the first such analysis. Namely, we formulate variants of multiple-step policy improvement, derive new algorithms using these definitions and prove their convergence. Moreover, we show that recent prominent Reinforcement Learning algorithms are, in fact, instances of our framework. We thus shed light on their empirical success and give a recipe for deriving new algorithms for future study.
Parallel and Streaming Algorithms for K-Core Decomposition
Authors: Esfandiari, Hossein and Lattanzi, Silvio and Mirrokni, Vahab
Published in: Proceedings of the 35th International Conference on Machine Learning (Main Conference Track), 2018

Abstract: The k-core decomposition is a fundamental primitive in many machine learning and data mining applications. We present the first distributed and the first streaming algorithms to compute and maintain an approximate k-core decomposition with provable guarantees. Our algorithms achieve rigorous bounds on space complexity while bounding the number of passes or number of rounds of computation. We do so by presenting a new powerful sketching technique for k-core decomposition, and then by showing it can be computed efficiently in both streaming and MapReduce models. Finally, we confirm the effectiveness of our sketching technique empirically on a number of publicly available graphs.
IMPALA: Scalable Distributed Deep-RL with Importance Weighted Actor-Learner Architectures
Authors: Espeholt, Lasse and Soyer, Hubert and Munos, Remi and Simonyan, Karen and Mnih, Vlad and Ward, Tom and Doron, Yotam and Firoiu, Vlad and Harley, Tim and Dunning, Iain and Legg, Shane and Kavukcuoglu, Koray
Published in: Proceedings of the 35th International Conference on Machine Learning (Main Conference Track), 2018

Abstract: In this work we aim to solve a large collection of tasks using a single reinforcement learning agent with a single set of parameters. A key challenge is to handle the increased amount of data and extended training time. We have developed a new distributed agent IMPALA (Importance Weighted Actor-Learner Architecture) that not only uses resources more efficiently in single-machine training but also scales to thousands of machines without sacrificing data efficiency or resource utilisation. We achieve stable learning at high throughput by combining decoupled acting and learning with a novel off-policy correction method called V-trace. We demonstrate the effectiveness of IMPALA for multi-task reinforcement learning on DMLab-30 (a set of 30 tasks from the DeepMind Lab environment (Beattie et al., 2016)) and Atari57 (all available Atari games in Arcade Learning Environment (Bellemare et al., 2013a)). Our results show that IMPALA is able to achieve better performance than previous agents with less data, and crucially exhibits positive transfer between tasks as a result of its multi-task approach.
Scalable Gaussian Processes with Grid-Structured Eigenfunctions (GP-GRIEF)
Authors: Evans, Trefor and Nair, Prasanth
Published in: Proceedings of the 35th International Conference on Machine Learning (Main Conference Track), 2018

Abstract: We introduce a kernel approximation strategy that enables computation of the Gaussian process log marginal likelihood and all hyperparameter derivatives in O(p) time. Our GRIEF kernel consists of p eigenfunctions found using a Nystrom approximation from a dense Cartesian product grid of inducing points. By exploiting algebraic properties of Kronecker and Khatri-Rao tensor products, computational complexity of the training procedure can be practically independent of the number of inducing points. This allows us to use arbitrarily many inducing points to achieve a globally accurate kernel approximation, even in high-dimensional problems. The fast likelihood evaluation enables type-I or II Bayesian inference on large-scale datasets. We benchmark our algorithms on real-world problems with up to two-million training points and 10^33 inducing points.
The Limits of Maxing, Ranking, and Preference Learning
Authors: Falahatgar, Moein and Jain, Ayush and Orlitsky, Alon and Pichapati, Venkatadheeraj and Ravindrakumar, Vaishakh
Published in: Proceedings of the 35th International Conference on Machine Learning (Main Conference Track), 2018

Abstract: We present a comprehensive understanding of three important problems in PAC preference learning: maximum selection (maxing), ranking, and estimating <em>all</em> pairwise preference probabilities, in the adaptive setting. With just Weak Stochastic Transitivity, we show that maxing requires $Ømega(n^2)$ comparisons and with slightly more restrictive Medium Stochastic Transitivity, we present a linear complexity maxing algorithm. With Strong Stochastic Transitivity and Stochastic Triangle Inequality, we derive a ranking algorithm with optimal $\mathcalO(nłog n)$ complexity and an optimal algorithm that estimates all pairwise preference probabilities.
BOHB: Robust and Efficient Hyperparameter Optimization at Scale
Authors: Falkner, Stefan and Klein, Aaron and Hutter, Frank
Published in: Proceedings of the 35th International Conference on Machine Learning (Main Conference Track), 2018

Abstract: Modern deep learning methods are very sensitive to many hyperparameters, and, due to the long training times of state-of-the-art models, vanilla Bayesian hyperparameter optimization is typically computationally infeasible. On the other hand, bandit-based configuration evaluation approaches based on random search lack guidance and do not converge to the best configurations as quickly. Here, we propose to combine the benefits of both Bayesian optimization and bandit-based methods, in order to achieve the best of both worlds: strong anytime performance and fast convergence to optimal configurations. We propose a new practical state-of-the-art hyperparameter optimization method, which consistently outperforms both Bayesian optimization and Hyperband on a wide range of problem types, including high-dimensional toy functions, support vector machines, feed-forward neural networks, Bayesian neural networks, deep reinforcement learning, and convolutional neural networks. Our method is robust and versatile, while at the same time being conceptually simple and easy to implement.
More Robust Doubly Robust Off-policy Evaluation
Authors: Farajtabar, Mehrdad and Chow, Yinlam and Ghavamzadeh, Mohammad
Published in: Proceedings of the 35th International Conference on Machine Learning (Main Conference Track), 2018

Abstract: We study the problem of off-policy evaluation (OPE) in reinforcement learning (RL), where the goal is to estimate the performance of a policy from the data generated by another policy(ies). In particular, we focus on the doubly robust (DR) estimators that consist of an importance sampling (IS) component and a performance model, and utilize the low (or zero) bias of IS and low variance of the model at the same time. Although the accuracy of the model has a huge impact on the overall performance of DR, most of the work on using the DR estimators in OPE has been focused on improving the IS part, and not much on how to learn the model. In this paper, we propose alternative DR estimators, called more robust doubly robust (MRDR), that learn the model parameter by minimizing the variance of the DR estimator. We first present a formulation for learning the DR model in RL. We then derive formulas for the variance of the DR estimator in both contextual bandits and RL, such that their gradients w.r.t. the model parameters can be estimated from the samples, and propose methods to efficiently minimize the variance. We prove that the MRDR estimators are strongly consistent and asymptotically optimal. Finally, we evaluate MRDR in bandits and RL benchmark problems, and compare its performance with the existing methods.
Efficient and Consistent Adversarial Bipartite Matching
Authors: Fathony, Rizal and Behpour, Sima and Zhang, Xinhua and Ziebart, Brian
Published in: Proceedings of the 35th International Conference on Machine Learning (Main Conference Track), 2018

Abstract: Many important structured prediction problems, including learning to rank items, correspondence-based natural language processing, and multi-object tracking, can be formulated as weighted bipartite matching optimizations. Existing structured prediction approaches have significant drawbacks when applied under the constraints of perfect bipartite matchings. Exponential family probabilistic models, such as the conditional random field (CRF), provide statistical consistency guarantees, but suffer computationally from the need to compute the normalization term of its distribution over matchings, which is a #P-hard matrix permanent computation. In contrast, the structured support vector machine (SSVM) provides computational efficiency, but lacks Fisher consistency, meaning that there are distributions of data for which it cannot learn the optimal matching even under ideal learning conditions (i.e., given the true distribution and selecting from all measurable potential functions). We propose adversarial bipartite matching to avoid both of these limitations. We develop this approach algorithmically, establish its computational efficiency and Fisher consistency properties, and apply it to matching problems that demonstrate its empirical benefits.
Global Convergence of Policy Gradient Methods for the Linear Quadratic Regulator
Authors: Fazel, Maryam and Ge, Rong and Kakade, Sham and Mesbahi, Mehran
Published in: Proceedings of the 35th International Conference on Machine Learning (Main Conference Track), 2018

Abstract: Direct policy gradient methods for reinforcement learning and continuous control problems are a popular approach for a variety of reasons: 1) they are easy to implement without explicit knowledge of the underlying model, 2) they are an “end-to-end” approach, directly optimizing the performance metric of interest, 3) they inherently allow for richly parameterized policies. A notable drawback is that even in the most basic continuous control problem (that of linear quadratic regulators), these methods must solve a non-convex optimization problem, where little is understood about their efficiency from both computational and statistical perspectives. In contrast, system identification and model based planning in optimal control theory have a much more solid theoretical footing, where much is known with regards to their computational and statistical properties. This work bridges this gap showing that (model free) policy gradient methods globally converge to the optimal solution and are efficient (polynomially so in relevant problem dependent quantities) with regards to their sample and computational complexities.
CRVI: Convex Relaxation for Variational Inference
Authors: Fazelnia, Ghazal and Paisley, John
Published in: Proceedings of the 35th International Conference on Machine Learning (Main Conference Track), 2018

Abstract: We present a new technique for solving non-convex variational inference optimization problems. Variational inference is a widely used method for posterior approximation in which the inference problem is transformed into an optimization problem. For most models, this optimization is highly non-convex and so hard to solve. In this paper, we introduce a new approach to solving the variational inference optimization based on convex relaxation and semidefinite programming. Our theoretical results guarantee very tight relaxation bounds that get nearer to the global optimal solution than traditional coordinate ascent. We evaluate the performance of our approach on regression and sparse coding.
Fourier Policy Gradients
Authors: Fellows, Matthew and Ciosek, Kamil and Whiteson, Shimon
Published in: Proceedings of the 35th International Conference on Machine Learning (Main Conference Track), 2018

Abstract: We propose a new way of deriving policy gradient updates for reinforcement learning. Our technique, based on Fourier analysis, recasts integrals that arise with expected policy gradients as convolutions and turns them into multiplications. The obtained analytical solutions allow us to capture the low variance benefits of EPG in a broad range of settings. For the critic, we treat trigonometric and radial basis functions, two function families with the universal approximation property. The choice of policy can be almost arbitrary, including mixtures or hybrid continuous-discrete probability distributions. Moreover, we derive a general family of sample-based estimators for stochastic policy gradients, which unifies existing results on sample-based approximation. We believe that this technique has the potential to shape the next generation of policy gradient approaches, powered by analytical results.
Nonparametric variable importance using an augmented neural network with multi-task learning
Authors: Feng, Jean and Williamson, Brian and Simon, Noah and Carone, Marco
Published in: Proceedings of the 35th International Conference on Machine Learning (Main Conference Track), 2018

Abstract: In predictive modeling applications, it is often of interest to determine the relative contribution of subsets of features in explaining the variability of an outcome. It is useful to consider this variable importance as a function of the unknown, underlying data-generating mechanism rather than the specific predictive algorithm used to fit the data. In this paper, we connect these ideas in nonparametric variable importance to machine learning, and provide a method for efficient estimation of variable importance when building a predictive model using a neural network. We show how a single augmented neural network with multi-task learning simultaneously estimates the importance of many feature subsets, improving on previous procedures for estimating importance. We demonstrate on simulated data that our method is both accurate and computationally efficient, and apply our method to both a study of heart disease and for predicting mortality in ICU patients.
Closed-form Marginal Likelihood in Gamma-Poisson Matrix Factorization
Authors: Filstroff, Louis and Lumbreras, Alberto and Févotte, Cédric
Published in: Proceedings of the 35th International Conference on Machine Learning (Main Conference Track), 2018

Abstract: We present novel understandings of the Gamma-Poisson (GaP) model, a probabilistic matrix factorization model for count data. We show that GaP can be rewritten free of the score/activation matrix. This gives us new insights about the estimation of the topic/dictionary matrix by maximum marginal likelihood estimation. In particular, this explains the robustness of this estimator to over-specified values of the factorization rank, especially its ability to automatically prune irrelevant dictionary columns, as empirically observed in previous work. The marginalization of the activation matrix leads in turn to a new Monte Carlo Expectation-Maximization algorithm with favorable properties.
Automatic Goal Generation for Reinforcement Learning Agents
Authors: Florensa, Carlos and Held, David and Geng, Xinyang and Abbeel, Pieter
Published in: Proceedings of the 35th International Conference on Machine Learning (Main Conference Track), 2018

Abstract: Reinforcement learning (RL) is a powerful technique to train an agent to perform a task; however, an agent that is trained using RL is only capable of achieving the single task that is specified via its reward function. Such an approach does not scale well to settings in which an agent needs to perform a diverse set of tasks, such as navigating to varying positions in a room or moving objects to varying locations. Instead, we propose a method that allows an agent to automatically discover the range of tasks that it is capable of performing in its environment. We use a generator network to propose tasks for the agent to try to accomplish, each task being specified as reaching a certain parametrized subset of the state-space. The generator network is optimized using adversarial training to produce tasks that are always at the appropriate level of difficulty for the agent, thus automatically producing a curriculum. We show that, by using this framework, an agent can efficiently and automatically learn to perform a wide set of tasks without requiring any prior knowledge of its environment, even when only sparse rewards are available. Videos and code available at https://sites.google.com/view/goalgeneration4rl.
DiCE: The Infinitely Differentiable Monte Carlo Estimator
Authors: Foerster, Jakob and Farquhar, Gregory and Al-Shedivat, Maruan and Rocktäschel, Tim and Xing, Eric and Whiteson, Shimon
Published in: Proceedings of the 35th International Conference on Machine Learning (Main Conference Track), 2018

Abstract: The score function estimator is widely used for estimating gradients of stochastic objectives in stochastic computation graphs (SCG), eg., in reinforcement learning and meta-learning. While deriving the first-order gradient estimators by differentiating a surrogate loss (SL) objective is computationally and conceptually simple, using the same approach for higher-order derivatives is more challenging. Firstly, analytically deriving and implementing such estimators is laborious and not compliant with automatic differentiation. Secondly, repeatedly applying SL to construct new objectives for each order derivative involves increasingly cumbersome graph manipulations. Lastly, to match the first-order gradient under differentiation, SL treats part of the cost as a fixed sample, which we show leads to missing and wrong terms for estimators of higher-order derivatives. To address all these shortcomings in a unified way, we introduce DiCE, which provides a single objective that can be differentiated repeatedly, generating correct estimators of derivatives of any order in SCGs. Unlike SL, DiCE relies on automatic differentiation for performing the requisite graph manipulations. We verify the correctness of DiCE both through a proof and numerical evaluation of the DiCE derivative estimates. We also use DiCE to propose and evaluate a novel approach for multi-agent learning. Our code is available at https://github.com/alshedivat/lola.
Practical Contextual Bandits with Regression Oracles
Authors: Foster, Dylan and Agarwal, Alekh and Dudik, Miroslav and Luo, Haipeng and Schapire, Robert
Published in: Proceedings of the 35th International Conference on Machine Learning (Main Conference Track), 2018

Abstract: A major challenge in contextual bandits is to design general-purpose algorithms that are both practically useful and theoretically well-founded. We present a new technique that has the empirical and computational advantages of realizability-based approaches combined with the flexibility of agnostic methods. Our algorithms leverage the availability of a regression oracle for the value-function class, a more realistic and reasonable oracle than the classification oracles over policies typically assumed by agnostic methods. Our approach generalizes both UCB and LinUCB to far more expressive possible model classes and achieves low regret under certain distributional assumptions. In an extensive empirical evaluation, we find that our approach typically matches or outperforms both realizability-based and agnostic baselines.
Generative Temporal Models with Spatial Memory for Partially Observed Environments
Authors: Fraccaro, Marco and Rezende, Danilo and Zwols, Yori and Pritzel, Alexander and Eslami, S. M. Ali and Viola, Fabio
Published in: Proceedings of the 35th International Conference on Machine Learning (Main Conference Track), 2018

Abstract: In model-based reinforcement learning, generative and temporal models of environments can be leveraged to boost agent performance, either by tuning the agent’s representations during training or via use as part of an explicit planning mechanism. However, their application in practice has been limited to simplistic environments, due to the difficulty of training such models in larger, potentially partially-observed and 3D environments. In this work we introduce a novel action-conditioned generative model of such challenging environments. The model features a non-parametric spatial memory system in which we store learned, disentangled representations of the environment. Low-dimensional spatial updates are computed using a state-space model that makes use of knowledge on the prior dynamics of the moving agent, and high-dimensional visual observations are modelled with a Variational Auto-Encoder. The result is a scalable architecture capable of performing coherent predictions over hundreds of time steps across a range of partially observed 2D and 3D environments.
ADMM and Accelerated ADMM as Continuous Dynamical Systems
Authors: Franca, Guilherme and Robinson, Daniel and Vidal, Rene
Published in: Proceedings of the 35th International Conference on Machine Learning (Main Conference Track), 2018

Abstract: Recently, there has been an increasing interest in using tools from dynamical systems to analyze the behavior of simple optimization algorithms such as gradient descent and accelerated variants. This paper strengthens such connections by deriving the differential equations that model the continuous limit of the sequence of iterates generated by the alternating direction method of multipliers, as well as an accelerated variant. We employ the direct method of Lyapunov to analyze the stability of critical points of the dynamical systems and to obtain associated convergence rates.