mtybilly/Instruct2DS huggingface dataset:
Constrained Policy Optimization
Authors: Joshua Achiam and David Held and Aviv Tamar and Pieter Abbeel
Published in: Proceedings of the 34th International Conference on Machine Learning (Main Conference Track), 2017

Abstract: For many applications of reinforcement learning it can be more convenient to specify both a reward function and constraints, rather than trying to design behavior through the reward function. For example, systems that physically interact with or around humans should satisfy safety constraints. Recent advances in policy search algorithms (Mnih et al., 2016, Schulman et al., 2015, Lillicrap et al., 2016, Levine et al., 2016) have enabled new capabilities in high-dimensional control, but do not consider the constrained setting. We propose Constrained Policy Optimization (CPO), the first general-purpose policy search algorithm for constrained reinforcement learning with guarantees for near-constraint satisfaction at each iteration. Our method allows us to train neural network policies for high-dimensional control while making guarantees about policy behavior all throughout training. Our guarantees are based on a new theoretical result, which is of independent interest: we prove a bound relating the expected returns of two policies to an average divergence between them. We demonstrate the effectiveness of our approach on simulated robot locomotion tasks where the agent must satisfy constraints motivated by safety.
The Price of Differential Privacy for Online Learning
Authors: Naman Agarwal and Karan Singh
Published in: Proceedings of the 34th International Conference on Machine Learning (Main Conference Track), 2017

Abstract: We design differentially private algorithms for the problem of online linear optimization in the full information and bandit settings with optimal $O(T^0.5)$ regret bounds. In the full-information setting, our results demonstrate that $ε$-differential privacy may be ensured for free – in particular, the regret bounds scale as $O(T^0.5+1/ε)$. For bandit linear optimization, and as a special case, for non-stochastic multi-armed bandits, the proposed algorithm achieves a regret of $O(T^0.5/ε)$, while the previously best known regret bound was $O(T^2/3/ε)$.
Local Bayesian Optimization of Motor Skills
Authors: Riad Akrour and Dmitry Sorokin and Jan Peters and Gerhard Neumann
Published in: Proceedings of the 34th International Conference on Machine Learning (Main Conference Track), 2017

Abstract: Bayesian optimization is renowned for its sample efficiency but its application to higher dimensional tasks is impeded by its focus on global optimization. To scale to higher dimensional problems, we leverage the sample efficiency of Bayesian optimization in a local context. The optimization of the acquisition function is restricted to the vicinity of a Gaussian search distribution which is moved towards high value areas of the objective. The proposed information-theoretic update of the search distribution results in a Bayesian interpretation of local stochastic search: the search distribution encodes prior knowledge on the optimum’s location and is weighted at each iteration by the likelihood of this location’s optimality. We demonstrate the effectiveness of our algorithm on several benchmark objective functions as well as a continuous robotic task in which an informative prior is obtained by imitation learning.
Connected Subgraph Detection with Mirror Descent on SDPs
Authors: Cem Aksoylar and Lorenzo Orecchia and Venkatesh Saligrama
Published in: Proceedings of the 34th International Conference on Machine Learning (Main Conference Track), 2017

Abstract: We propose a novel, computationally efficient mirror-descent based optimization framework for subgraph detection in graph-structured data. Our aim is to discover anomalous patterns present in a connected subgraph of a given graph. This problem arises in many applications such as detection of network intrusions, community detection, detection of anomalous events in surveillance videos or disease outbreaks. Since optimization over connected subgraphs is a combinatorial and computationally difficult problem, we propose a convex relaxation that offers a principled approach to incorporating connectivity and conductance constraints on candidate subgraphs. We develop a novel efficient algorithm to solve the relaxed problem, establish convergence guarantees and demonstrate its feasibility and performance with experiments on real and very large simulated networks.
Learning from Clinical Judgments: Semi-Markov-Modulated Marked Hawkes Processes for Risk Prognosis
Authors: Ahmed M. Alaa and Scott Hu and Mihaela van der Schaar
Published in: Proceedings of the 34th International Conference on Machine Learning (Main Conference Track), 2017

Abstract: Critically ill patients in regular wards are vulnerable to unanticipated adverse events which require prompt transfer to the intensive care unit (ICU). To allow for accurate prognosis of deteriorating patients, we develop a novel continuous-time probabilistic model for a monitored patient’s temporal sequence of physiological data. Our model captures “informatively sampled” patient episodes: the clinicians’ decisions on when to observe a hospitalized patient’s vital signs and lab tests over time are represented by a marked Hawkes process, with intensity parameters that are modulated by the patient’s latent clinical states, and with observable physiological data (mark process) modeled as a switching multi-task Gaussian process. In addition, our model captures “informatively censored” patient episodes by representing the patient’s latent clinical states as an absorbing semi-Markov jump process. The model parameters are learned from offline patient episodes in the electronic health records via an EM-based algorithm. Experiments conducted on a cohort of patients admitted to a major medical center over a 3-year period show that risk prognosis based on our model significantly outperforms the currently deployed medical risk scores and other baseline machine learning algorithms.
A Semismooth Newton Method for Fast, Generic Convex Programming
Authors: Alnur Ali and Eric Wong and J. Zico Kolter
Published in: Proceedings of the 34th International Conference on Machine Learning (Main Conference Track), 2017

Abstract: We introduce Newton-ADMM, a method for fast conic optimization. The basic idea is to view the residuals of consecutive iterates generated by the alternating direction method of multipliers (ADMM) as a set of fixed point equations, and then use a nonsmooth Newton method to find a solution; we apply the basic idea to the Splitting Cone Solver (SCS), a state-of-the-art method for solving generic conic optimization problems. We demonstrate theoretically, by extending the theory of semismooth operators, that Newton-ADMM converges rapidly (i.e., quadratically) to a solution; empirically, Newton-ADMM is significantly faster than SCS on a number of problems. The method also has essentially no tuning parameters, generates certificates of primal or dual infeasibility, when appropriate, and can be specialized to solve specific convex problems.
Learning Continuous Semantic Representations of Symbolic Expressions
Authors: Miltiadis Allamanis and Pankajan Chanthirasegaran and Pushmeet Kohli and Charles Sutton
Published in: Proceedings of the 34th International Conference on Machine Learning (Main Conference Track), 2017

Abstract: Combining abstract, symbolic reasoning with continuous neural reasoning is a grand challenge of representation learning. As a step in this direction, we propose a new architecture, called neural equivalence network, for the problem of learning continuous semantic representations of algebraic and logical expressions. These networks are trained to represent semantic equivalence, even of expressions that are syntactically very different. The challenge is that semantic representations must be computed in a syntax-directed manner, because semantics is compositional, but at the same time, small changes in syntax can lead to very large changes in semantics, which can be difficult for continuous neural architectures. We perform an exhaustive evaluation on the task of checking equivalence on a highly diverse class of symbolic algebraic and boolean expression types, showing that our model significantly outperforms existing architectures.
Doubly Accelerated Methods for Faster CCA and Generalized Eigendecomposition
Authors: Zeyuan Allen-Zhu and Yuanzhi Li
Published in: Proceedings of the 34th International Conference on Machine Learning (Main Conference Track), 2017

Abstract: We study k-GenEV, the problem of finding the top k generalized eigenvectors, and k-CCA, the problem of finding the top k vectors in canonical-correlation analysis. We propose algorithms LazyEV and LazyCCA to solve the two problems with running times linearly dependent on the input size and on k. Furthermore, our algorithms are <em>doubly-accelerated</em>: our running times depend only on the square root of the matrix condition number, and on the square root of the eigengap. This is the first such result for both k-GenEV or k-CCA. We also provide the first gap-free results, which provide running times that depend on $1/\sqrtɛ$ rather than the eigengap.
Faster Principal Component Regression and Stable Matrix Chebyshev Approximation
Authors: Zeyuan Allen-Zhu and Yuanzhi Li
Published in: Proceedings of the 34th International Conference on Machine Learning (Main Conference Track), 2017

Abstract: We solve principal component regression (PCR), up to a multiplicative accuracy $1+γ$, by reducing the problem to $\tildeO(γ^-1)$ black-box calls of ridge regression. Therefore, our algorithm does not require any explicit construction of the top principal components, and is suitable for large-scale PCR instances. In contrast, previous result requires $\tildeO(γ^-2)$ such black-box calls. We obtain this result by developing a general stable recurrence formula for matrix Chebyshev polynomials, and a degree-optimal polynomial approximation to the matrix sign function. Our techniques may be of independent interests, especially when designing iterative methods.
Follow the Compressed Leader: Faster Online Learning of Eigenvectors and Faster MMWU
Authors: Zeyuan Allen-Zhu and Yuanzhi Li
Published in: Proceedings of the 34th International Conference on Machine Learning (Main Conference Track), 2017

Abstract: The online problem of computing the top eigenvector is fundamental to machine learning. The famous matrix-multiplicative-weight-update (MMWU) framework solves this online problem and gives optimal regret. However, since MMWU runs very slow due to the computation of matrix exponentials, researchers proposed the follow-the-perturbed-leader (FTPL) framework which is faster, but a factor $\sqrtd$ worse than the optimal regret for dimension-$d$ matrices. We propose a <em>follow-the-compressed-leader</em> framework which, not only matches the optimal regret of MMWU (up to polylog factors), but runs no slower than FTPL. Our main idea is to “compress” the MMWU strategy to dimension 3 in the adversarial setting, or dimension 1 in the stochastic setting. This resolves an open question regarding how to obtain both (nearly) optimal and efficient algorithms for the online eigenvector problem.
Near-Optimal Design of Experiments via Regret Minimization
Authors: Zeyuan Allen-Zhu and Yuanzhi Li and Aarti Singh and Yining Wang
Published in: Proceedings of the 34th International Conference on Machine Learning (Main Conference Track), 2017

Abstract: We consider computationally tractable methods for the experimental design problem, where k out of n design points of dimension p are selected so that certain optimality criteria are approximately satisfied. Our algorithm finds a $(1+ε)$-approximate optimal design when k is a linear function of p; in contrast, existing results require k to be super-linear in p. Our algorithm also handles all popular optimality criteria, while existing ones only handle one or two such criteria. Numerical results on synthetic and real-world design problems verify the practical effectiveness of the proposed algorithm.
OptNet: Differentiable Optimization as a Layer in Neural Networks
Authors: Brandon Amos and J. Zico Kolter
Published in: Proceedings of the 34th International Conference on Machine Learning (Main Conference Track), 2017

Abstract: This paper presents OptNet, a network architecture that integrates optimization problems (here, specifically in the form of quadratic programs) as individual layers in larger end-to-end trainable deep networks. These layers encode constraints and complex dependencies between the hidden states that traditional convolutional and fully-connected layers often cannot capture. In this paper, we explore the foundations for such an architecture: we show how techniques from sensitivity analysis, bilevel optimization, and implicit differentiation can be used to exactly differentiate through these layers and with respect to layer parameters; we develop a highly efficient solver for these layers that exploits fast GPU-based batch solves within a primal-dual interior point method, and which provides backpropagation gradients with virtually no additional cost on top of the solve; and we highlight the application of these approaches in several problems. In one notable example, we show that the method is capable of learning to play mini-Sudoku (4x4) given just input and output games, with no a priori information about the rules of the game; this highlights the ability of our architecture to learn hard constraints better than other neural architectures.
Input Convex Neural Networks
Authors: Brandon Amos and Lei Xu and J. Zico Kolter
Published in: Proceedings of the 34th International Conference on Machine Learning (Main Conference Track), 2017

Abstract: This paper presents the input convex neural network architecture. These are scalar-valued (potentially deep) neural networks with constraints on the network parameters such that the output of the network is a convex function of (some of) the inputs. The networks allow for efficient inference via optimization over some inputs to the network given others, and can be applied to settings including structured prediction, data imputation, reinforcement learning, and others. In this paper we lay the basic groundwork for these models, proposing methods for inference, optimization and learning, and analyze their representational power. We show that many existing neural network architectures can be made input-convex with a minor modification, and develop specialized optimization algorithms tailored to this setting. Finally, we highlight the performance of the methods on multi-label prediction, image completion, and reinforcement learning problems, where we show improvement over the existing state of the art in many cases.
An Efficient, Sparsity-Preserving, Online Algorithm for Low-Rank Approximation
Authors: David Anderson and Ming Gu
Published in: Proceedings of the 34th International Conference on Machine Learning (Main Conference Track), 2017

Abstract: Low-rank matrix approximation is a fundamental tool in data analysis for processing large datasets, reducing noise, and finding important signals. In this work, we present a novel truncated LU factorization called Spectrum-Revealing LU (SRLU) for effective low-rank matrix approximation, and develop a fast algorithm to compute an SRLU factorization. We provide both matrix and singular value approximation error bounds for the SRLU approximation computed by our algorithm. Our analysis suggests that SRLU is competitive with the best low-rank matrix approximation methods, deterministic or randomized, in both computational complexity and approximation quality. Numeric experiments illustrate that SRLU preserves sparsity, highlights important data features and variables, can be efficiently updated, and calculates data approximations nearly as accurately as the best possible. To the best of our knowledge this is the first practical variant of the LU factorization for effective and efficient low-rank matrix approximation.
Modular Multitask Reinforcement Learning with Policy Sketches
Authors: Jacob Andreas and Dan Klein and Sergey Levine
Published in: Proceedings of the 34th International Conference on Machine Learning (Main Conference Track), 2017

Abstract: We describe a framework for multitask deep reinforcement learning guided by policy sketches. Sketches annotate tasks with sequences of named subtasks, providing information about high-level structural relationships among tasks but not how to implement them—specifically not providing the detailed guidance used by much previous work on learning policy abstractions for RL (e.g. intermediate rewards, subtask completion signals, or intrinsic motivations). To learn from sketches, we present a model that associates every subtask with a modular subpolicy, and jointly maximizes reward over full task-specific policies by tying parameters across shared subpolicies. Optimization is accomplished via a decoupled actor–critic training objective that facilitates learning common behaviors from multiple dissimilar reward functions. We evaluate the effectiveness of our approach in three environments featuring both discrete and continuous control, and with sparse rewards that can be obtained only after completing a number of high-level subgoals. Experiments show that using our approach to learn policies guided by sketches gives better performance than existing techniques for learning task-specific or shared policies, while naturally inducing a library of interpretable primitive behaviors that can be recombined to rapidly adapt to new tasks.
Averaged-DQN: Variance Reduction and Stabilization for Deep Reinforcement Learning
Authors: Oron Anschel and Nir Baram and Nahum Shimkin
Published in: Proceedings of the 34th International Conference on Machine Learning (Main Conference Track), 2017

Abstract: Instability and variability of Deep Reinforcement Learning (DRL) algorithms tend to adversely affect their performance. Averaged-DQN is a simple extension to the DQN algorithm, based on averaging previously learned Q-values estimates, which leads to a more stable training procedure and improved performance by reducing approximation error variance in the target values. To understand the effect of the algorithm, we examine the source of value function estimation errors and provide an analytical comparison within a simplified model. We further present experiments on the Arcade Learning Environment benchmark that demonstrate significantly improved stability and performance due to the proposed extension.
A Simple Multi-Class Boosting Framework with Theoretical Guarantees and Empirical Proficiency
Authors: Ron Appel and Pietro Perona
Published in: Proceedings of the 34th International Conference on Machine Learning (Main Conference Track), 2017

Abstract: There is a need for simple yet accurate white-box learning systems that train quickly and with little data. To this end, we showcase REBEL, a multi-class boosting method, and present a novel family of weak learners called localized similarities. Our framework provably minimizes the training error of any dataset at an exponential rate. We carry out experiments on a variety of synthetic and real datasets, demonstrating a consistent tendency to avoid overfitting. We evaluate our method on MNIST and standard UCI datasets against other state-of-the-art methods, showing the empirical proficiency of our method.
Deep Voice: Real-time Neural Text-to-Speech
Authors: Sercan Ö. Arık and Mike Chrzanowski and Adam Coates and Gregory Diamos and Andrew Gibiansky and Yongguo Kang and Xian Li and John Miller and Andrew Ng and Jonathan Raiman and Shubho Sengupta and Mohammad Shoeybi
Published in: Proceedings of the 34th International Conference on Machine Learning (Main Conference Track), 2017

Abstract: We present Deep Voice, a production-quality text-to-speech system constructed entirely from deep neural networks. Deep Voice lays the groundwork for truly end-to-end neural speech synthesis. The system comprises five major building blocks: a segmentation model for locating phoneme boundaries, a grapheme-to-phoneme conversion model, a phoneme duration prediction model, a fundamental frequency prediction model, and an audio synthesis model. For the segmentation model, we propose a novel way of performing phoneme boundary detection with deep neural networks using connectionist temporal classification (CTC) loss. For the audio synthesis model, we implement a variant of WaveNet that requires fewer parameters and trains faster than the original. By using a neural network for each component, our system is simpler and more flexible than traditional text-to-speech systems, where each component requires laborious feature engineering and extensive domain expertise. Finally, we show that inference with our system can be performed faster than real time and describe optimized WaveNet inference kernels on both CPU and GPU that achieve up to 400x speedups over existing implementations.
Oracle Complexity of Second-Order Methods for Finite-Sum Problems
Authors: Yossi Arjevani and Ohad Shamir
Published in: Proceedings of the 34th International Conference on Machine Learning (Main Conference Track), 2017

Abstract: Finite-sum optimization problems are ubiquitous in machine learning, and are commonly solved using first-order methods which rely on gradient computations. Recently, there has been growing interest in <em>second-order</em> methods, which rely on both gradients and Hessians. In principle, second-order methods can require much fewer iterations than first-order methods, and hold the promise for more efficient algorithms. Although computing and manipulating Hessians is prohibitive for high-dimensional problems in general, the Hessians of individual functions in finite-sum problems can often be efficiently computed, e.g. because they possess a low-rank structure. Can second-order information indeed be used to solve such problems more efficiently? In this paper, we provide evidence that the answer – perhaps surprisingly – is negative, at least in terms of worst-case guarantees. However, we also discuss what additional assumptions and algorithmic approaches might potentially circumvent this negative result.
Wasserstein Generative Adversarial Networks
Authors: Martin Arjovsky and Soumith Chintala and Léon Bottou
Published in: Proceedings of the 34th International Conference on Machine Learning (Main Conference Track), 2017

Abstract: We introduce a new algorithm named WGAN, an alternative to traditional GAN training. In this new model, we show that we can improve the stability of learning, get rid of problems like mode collapse, and provide meaningful learning curves useful for debugging and hyperparameter searches. Furthermore, we show that the corresponding optimization problem is sound, and provide extensive theoretical work highlighting the deep connections to different distances between distributions.
Generalization and Equilibrium in Generative Adversarial Nets (GANs)
Authors: Sanjeev Arora and Rong Ge and Yingyu Liang and Tengyu Ma and Yi Zhang
Published in: Proceedings of the 34th International Conference on Machine Learning (Main Conference Track), 2017

Abstract: It is shown that training of generative adversarial network (GAN) may not have good generalization properties; e.g., training may appear successful but the trained distribution may be far from target distribution in standard metrics. However, generalization does occur for a weaker metric called neural net distance. It is also shown that an approximate pure equilibrium exists in the discriminator/generator game for a natural training objective (Wasserstein) when generator capacity and training set sizes are moderate. This existence of equilibrium inspires MIX+GAN protocol, which can be combined with any existing GAN training, and empirically shown to improve some of them.
A Closer Look at Memorization in Deep Networks
Authors: Devansh Arpit and Stanisław Jastrzębski and Nicolas Ballas and David Krueger and Emmanuel Bengio and Maxinder S. Kanwal and Tegan Maharaj and Asja Fischer and Aaron Courville and Yoshua Bengio and Simon Lacoste-Julien
Published in: Proceedings of the 34th International Conference on Machine Learning (Main Conference Track), 2017

Abstract: We examine the role of memorization in deep learning, drawing connections to capacity, generalization, and adversarial robustness. While deep networks are capable of memorizing noise data, our results suggest that they tend to prioritize learning simple patterns first. In our experiments, we expose qualitative differences in gradient-based optimization of deep neural networks (DNNs) on noise vs.~real data. We also demonstrate that for appropriately tuned explicit regularization (e.g.,~dropout) we can degrade DNN training performance on noise datasets without compromising generalization on real data. Our analysis suggests that the notions of effective capacity which are dataset independent are unlikely to explain the generalization performance of deep networks when trained with gradient based methods because training data itself plays an important role in determining the degree of memorization.
An Alternative Softmax Operator for Reinforcement Learning
Authors: Kavosh Asadi and Michael L. Littman
Published in: Proceedings of the 34th International Conference on Machine Learning (Main Conference Track), 2017

Abstract: A softmax operator applied to a set of values acts somewhat like the maximization function and somewhat like an average. In sequential decision making, softmax is often used in settings where it is necessary to maximize utility but also to hedge against problems that arise from putting all of one’s weight behind a single maximum utility decision. The Boltzmann softmax operator is the most commonly used softmax operator in this setting, but we show that this operator is prone to misbehavior. In this work, we study a differentiable softmax operator that, among other properties, is a non-expansion ensuring a convergent behavior in learning and planning. We introduce a variant of SARSA algorithm that, by utilizing the new operator, computes a Boltzmann policy with a state-dependent temperature parameter. We show that the algorithm is convergent and that it performs favorably in practice.
Random Fourier Features for Kernel Ridge Regression: Approximation Bounds and Statistical Guarantees
Authors: Haim Avron and Michael Kapralov and Cameron Musco and Christopher Musco and Ameya Velingker and Amir Zandieh
Published in: Proceedings of the 34th International Conference on Machine Learning (Main Conference Track), 2017

Abstract: Random Fourier features is one of the most popular techniques for scaling up kernel methods, such as kernel ridge regression. However, despite impressive empirical results, the statistical properties of random Fourier features are still not well understood. In this paper we take steps toward filling this gap. Specifically, we approach random Fourier features from a spectral matrix approximation point of view, give tight bounds on the number of Fourier features required to achieve a spectral approximation, and show how spectral matrix approximation bounds imply statistical guarantees for kernel ridge regression.
Minimax Regret Bounds for Reinforcement Learning
Authors: Mohammad Gheshlaghi Azar and Ian Osband and Rémi Munos
Published in: Proceedings of the 34th International Conference on Machine Learning (Main Conference Track), 2017

Abstract: We consider the problem of provably optimal exploration in reinforcement learning for finite horizon MDPs. We show that an optimistic modification to value iteration achieves a regret bound of $\tilde O( \sqrtHSAT + H^2S^2A+H\sqrtT)$ where $H$ is the time horizon, $S$ the number of states, $A$ the number of actions and $T$ the number of time-steps. This result improves over the best previous known bound $\tilde O(HS \sqrtAT)$ achieved by the UCRL2 algorithm. The key significance of our new results is that when $T≥ H^3S^3A$ and $SA≥ H$, it leads to a regret of $\tildeO(\sqrtHSAT)$ that matches the established lower bound of $Ømega(\sqrtHSAT)$ up to a logarithmic factor. Our analysis contain two key insights. We use careful application of concentration inequalities to the optimal value function as a whole, rather than to the transitions probabilities (to improve scaling in $S$), and we define Bernstein-based “exploration bonuses” that use the empirical variance of the estimated values at the next states (to improve scaling in $H$).
Learning the Structure of Generative Models without Labeled Data
Authors: Stephen H. Bach and Bryan He and Alexander Ratner and Christopher Ré
Published in: Proceedings of the 34th International Conference on Machine Learning (Main Conference Track), 2017

Abstract: Curating labeled training data has become the primary bottleneck in machine learning. Recent frameworks address this bottleneck with generative models to synthesize labels at scale from weak supervision sources. The generative model’s dependency structure directly affects the quality of the estimated labels, but selecting a structure automatically without any labeled data is a distinct challenge. We propose a structure estimation method that maximizes the l1-regularized marginal pseudolikelihood of the observed data. Our analysis shows that the amount of unlabeled data required to identify the true structure scales sublinearly in the number of possible dependencies for a broad class of models. Simulations show that our method is 100x faster than a maximum likelihood approach and selects 1/4 as many extraneous dependencies. We also show that our method provides an average of 1.5 F1 points of improvement over existing, user-developed information extraction applications on real-world data such as PubMed journal abstracts.
Uniform Deviation Bounds for k-Means Clustering
Authors: Olivier Bachem and Mario Lucic and S. Hamed Hassani and Andreas Krause
Published in: Proceedings of the 34th International Conference on Machine Learning (Main Conference Track), 2017

Abstract: Uniform deviation bounds limit the difference between a model’s expected loss and its loss on an empirical sample <em>uniformly</em> for all models in a learning problem. In this paper, we provide a novel framework to obtain uniform deviation bounds for loss functions which are <em>unbounded</em>. As a result, we obtain competitive uniform deviation bounds for k-Means clustering under weak assumptions on the underlying distribution. If the fourth moment is bounded, we prove a rate of $O(m^-1/2)$ compared to the previously known $O(m^-1/4)$ rate. Furthermore, we show that the rate also depends on the kurtosis – the normalized fourth moment which measures the “tailedness” of a distribution. We also provide improved rates under progressively stronger assumptions, namely, bounded higher moments, subgaussianity and bounded support of the underlying distribution.
Distributed and Provably Good Seedings for k-Means in Constant Rounds
Authors: Olivier Bachem and Mario Lucic and Andreas Krause
Published in: Proceedings of the 34th International Conference on Machine Learning (Main Conference Track), 2017

Abstract: The k-Means++ algorithm is the state of the art algorithm to solve k-Means clustering problems as the computed clusterings are O(log k) competitive in expectation. However, its seeding step requires k inherently sequential passes through the full data set making it hard to scale to massive data sets. The standard remedy is to use the k-Means|| algorithm which reduces the number of sequential rounds and is thus suitable for a distributed setting. In this paper, we provide a novel analysis of the k-Means|| algorithm that bounds the expected solution quality for any number of rounds and oversampling factors greater than k, the two parameters one needs to choose in practice. In particular, we show that k-Means|| provides <em>provably good</em> clusterings even for a small, constant number of iterations. This theoretical finding explains the common observation that k-Means|| performs extremely well in practice even if the number of rounds is low. We further provide a hard instance that shows that an <em>additive</em> error term as encountered in our analysis is inevitable if less than k-1 rounds are employed.
Learning Algorithms for Active Learning
Authors: Philip Bachman and Alessandro Sordoni and Adam Trischler
Published in: Proceedings of the 34th International Conference on Machine Learning (Main Conference Track), 2017

Abstract: We introduce a model that learns active learning algorithms via metalearning. For a distribution of related tasks, our model jointly learns: a data representation, an item selection heuristic, and a prediction function. Our model uses the item selection heuristic to construct a labeled support set for training the prediction function. Using the Omniglot and MovieLens datasets, we test our model in synthetic and practical settings.
Improving Viterbi is Hard: Better Runtimes Imply Faster Clique Algorithms
Authors: Arturs Backurs and Christos Tzamos
Published in: Proceedings of the 34th International Conference on Machine Learning (Main Conference Track), 2017

Abstract: The classic algorithm of Viterbi computes the most likely path in a Hidden Markov Model (HMM) that results in a given sequence of observations. It runs in time $O(Tn^2)$ given a sequence of T observations from a HMM with n states. Despite significant interest in the problem and prolonged effort by different communities, no known algorithm achieves more than a polylogarithmic speedup. In this paper, we explain this difficulty by providing matching conditional lower bounds. Our lower bounds are based on assumptions that the best known algorithms for the All-Pairs Shortest Paths problem (APSP) and for the Max-Weight k-Clique problem in edge-weighted graphs are essentially tight. Finally, using a recent algorithm by Green Larsen and Williams for online Boolean matrix-vector multiplication, we get a $2^Ømega(\sqrtłog n)$ speedup for the Viterbi algorithm when there are few distinct transition probabilities in the HMM.
Differentially Private Clustering in High-Dimensional Euclidean Spaces
Authors: Maria-Florina Balcan and Travis Dick and Yingyu Liang and Wenlong Mou and Hongyang Zhang
Published in: Proceedings of the 34th International Conference on Machine Learning (Main Conference Track), 2017

Abstract: We study the problem of clustering sensitive data while preserving the privacy of individuals represented in the dataset, which has broad applications in practical machine learning and data analysis tasks. Although the problem has been widely studied in the context of low-dimensional, discrete spaces, much remains unknown concerning private clustering in high-dimensional Euclidean spaces $ℝ^d$. In this work, we give differentially private and efficient algorithms achieving strong guarantees for $k$-means and $k$-median clustering when $d=Ømega(\mathsfpolylog(n))$. Our algorithm achieves clustering loss at most $łog^3(n)\mathsfOPT+\mathsfpoly(łog n,d,k)$, advancing the state-of-the-art result of $\sqrtd\mathsfOPT+\mathsfpoly(łog n,d^d,k^d)$. We also study the case where the data points are $s$-sparse and show that the clustering loss can scale logarithmically with $d$, i.e., $łog^3(n)\mathsfOPT+\mathsfpoly(łog n,łog d,k,s)$. Experiments on both synthetic and real datasets verify the effectiveness of the proposed method.
The Shattered Gradients Problem: If resnets are the answer, then what is the question?
Authors: David Balduzzi and Marcus Frean and Lennox Leary and J. P. Lewis and Kurt Wan-Duo Ma and Brian McWilliams
Published in: Proceedings of the 34th International Conference on Machine Learning (Main Conference Track), 2017

Abstract: A long-standing obstacle to progress in deep learning is the problem of vanishing and exploding gradients. Although, the problem has largely been overcome via carefully constructed initializations and batch normalization, architectures incorporating skip-connections such as highway and resnets perform much better than standard feedforward architectures despite well-chosen initialization and batch normalization. In this paper, we identify the shattered gradients problem. Specifically, we show that the correlation between gradients in standard feedforward networks decays exponentially with depth resulting in gradients that resemble white noise whereas, in contrast, the gradients in architectures with skip-connections are far more resistant to shattering, decaying sublinearly. Detailed empirical evidence is presented in support of the analysis, on both fully-connected networks and convnets. Finally, we present a new “looks linear” (LL) initialization that prevents shattering, with preliminary experiments showing the new initialization allows to train very deep networks without the addition of skip-connections.
Neural Taylor Approximations: Convergence and Exploration in Rectifier Networks
Authors: David Balduzzi and Brian McWilliams and Tony Butler-Yeoman
Published in: Proceedings of the 34th International Conference on Machine Learning (Main Conference Track), 2017

Abstract: Modern convolutional networks, incorporating rectifiers and max-pooling, are neither smooth nor convex; standard guarantees therefore do not apply. Nevertheless, methods from convex optimization such as gradient descent and Adam are widely used as building blocks for deep learning algorithms. This paper provides the first convergence guarantee applicable to modern convnets, which furthermore matches a lower bound for convex nonsmooth functions. The key technical tool is the neural Taylor approximation – a straightforward application of Taylor expansions to neural networks – and the associated Taylor loss. Experiments on a range of optimizers, layers, and tasks provide evidence that the analysis accurately captures the dynamics of neural optimization. The second half of the paper applies the Taylor approximation to isolate the main difficulty in training rectifier nets – that gradients are shattered – and investigates the hypothesis that, by exploring the space of activation configurations more thoroughly, adaptive optimizers such as RMSProp and Adam are able to converge to better solutions.
Spectral Learning from a Single Trajectory under Finite-State Policies
Authors: Borja Balle and Odalric-Ambrym Maillard
Published in: Proceedings of the 34th International Conference on Machine Learning (Main Conference Track), 2017

Abstract: We present spectral methods of moments for learning sequential models from a single trajectory, in stark contrast with the classical literature that assumes the availability of multiple i.i.d. trajectories. Our approach leverages an efficient SVD-based learning algorithm for weighted automata and provides the first rigorous analysis for learning many important models using dependent data. We state and analyze the algorithm under three increasingly difficult scenarios: probabilistic automata, stochastic weighted automata, and reactive predictive state representations controlled by a finite-state policy. Our proofs include novel tools for studying mixing properties of stochastic weighted automata.
Lost Relatives of the Gumbel Trick
Authors: Matej Balog and Nilesh Tripuraneni and Zoubin Ghahramani and Adrian Weller
Published in: Proceedings of the 34th International Conference on Machine Learning (Main Conference Track), 2017

Abstract: The Gumbel trick is a method to sample from a discrete probability distribution, or to estimate its normalizing partition function. The method relies on repeatedly applying a random perturbation to the distribution in a particular way, each time solving for the most likely configuration. We derive an entire family of related methods, of which the Gumbel trick is one member, and show that the new methods have superior properties in several settings with minimal additional computational cost. In particular, for the Gumbel trick to yield computational benefits for discrete graphical models, Gumbel perturbations on all configurations are typically replaced with so-called low-rank perturbations. We show how a subfamily of our new methods adapts to this setting, proving new upper and lower bounds on the log partition function and deriving a family of sequential samplers for the Gibbs distribution. Finally, we balance the discussion by showing how the simpler analytical form of the Gumbel trick enables additional theoretical results.
Dynamic Word Embeddings
Authors: Robert Bamler and Stephan Mandt
Published in: Proceedings of the 34th International Conference on Machine Learning (Main Conference Track), 2017

Abstract: We present a probabilistic language model for time-stamped text data which tracks the semantic evolution of individual words over time. The model represents words and contexts by latent trajectories in an embedding space. At each moment in time, the embedding vectors are inferred from a probabilistic version of word2vec [Mikolov et al., 2013]. These embedding vectors are connected in time through a latent diffusion process. We describe two scalable variational inference algorithms–skip-gram smoothing and skip-gram filtering–that allow us to train the model jointly over all times; thus learning on all data while simultaneously allowing word and context vectors to drift. Experimental results on three different corpora demonstrate that our dynamic model infers word embedding trajectories that are more interpretable and lead to higher predictive likelihoods than competing methods that are based on static models trained separately on time slices.
End-to-End Differentiable Adversarial Imitation Learning
Authors: Nir Baram and Oron Anschel and Itai Caspi and Shie Mannor
Published in: Proceedings of the 34th International Conference on Machine Learning (Main Conference Track), 2017

Abstract: Generative Adversarial Networks (GANs) have been successfully applied to the problem of <em>policy imitation</em> in a model-free setup. However, the computation graph of GANs, that include a stochastic policy as the generative model, is no longer differentiable end-to-end, which requires the use of high-variance gradient estimation. In this paper, we introduce the Model-based Generative Adversarial Imitation Learning (MGAIL) algorithm. We show how to use a forward model to make the computation fully differentiable, which enables training policies using the exact gradient of the discriminator. The resulting algorithm trains competent policies using relatively fewer expert samples and interactions with the environment. We test it on both discrete and continuous action domains and report results that surpass the state-of-the-art.
Emulating the Expert: Inverse Optimization through Online Learning
Authors: Andreas Bärmann and Sebastian Pokutta and Oskar Schneider
Published in: Proceedings of the 34th International Conference on Machine Learning (Main Conference Track), 2017

Abstract: In this paper, we demonstrate how to learn the objective function of a decision maker while only observing the problem input data and the decision maker’s corresponding decisions over multiple rounds. Our approach is based on online learning techniques and works for linear objectives over arbitrary sets for which we have a linear optimization oracle and as such generalizes previous work based on KKT-system decomposition and dualization approaches. The applicability of our framework for learning linear constraints is also discussed briefly. Our algorithm converges at a rate of O(1/sqrt(T)), and we demonstrate its effectiveness and applications in preliminary computational results.
Unimodal Probability Distributions for Deep Ordinal Classification
Authors: Christopher Beckham and Christopher Pal
Published in: Proceedings of the 34th International Conference on Machine Learning (Main Conference Track), 2017

Abstract: Probability distributions produced by the cross-entropy loss for ordinal classification problems can possess undesired properties. We propose a straightforward technique to constrain discrete ordinal probability distributions to be unimodal via the use of the Poisson and binomial probability distributions. We evaluate this approach in the context of deep learning on two large ordinal image datasets, obtaining promising results.
Globally Induced Forest: A Prepruning Compression Scheme
Authors: Jean-Michel Begon and Arnaud Joly and Pierre Geurts
Published in: Proceedings of the 34th International Conference on Machine Learning (Main Conference Track), 2017

Abstract: Tree-based ensemble models are heavy memory-wise. An undesired state of affairs considering nowadays datasets, memory-constrained environment and fitting/prediction times. In this paper, we propose the Globally Induced Forest (GIF) to remedy this problem. GIF is a fast prepruning approach to build lightweight ensembles by iteratively deepening the current forest. It mixes local and global optimizations to produce accurate predictions under memory constraints in reasonable time. We show that the proposed method is more than competitive with standard tree-based ensembles under corresponding constraints, and can sometimes even surpass much larger models.
End-to-End Learning for Structured Prediction Energy Networks
Authors: David Belanger and Bishan Yang and Andrew McCallum
Published in: Proceedings of the 34th International Conference on Machine Learning (Main Conference Track), 2017

Abstract: Structured Prediction Energy Networks (SPENs) are a simple, yet expressive family of structured prediction models (Belanger and McCallum, 2016). An energy function over candidate structured outputs is given by a deep network, and predictions are formed by gradient-based optimization. This paper presents end-to-end learning for SPENs, where the energy function is discriminatively trained by back-propagating through gradient-based prediction. In our experience, the approach is substantially more accurate than the structured SVM method of Belanger and McCallum (2016), as it allows us to use more sophisticated non-convex energies. We provide a collection of techniques for improving the speed, accuracy, and memory requirements of end-to-end SPENs, and demonstrate the power of our method on 7-Scenes image denoising and CoNLL-2005 semantic role labeling tasks. In both, inexact minimization of non-convex SPEN energies is superior to baseline methods that use simplistic energy functions that can be minimized exactly.
Learning to Discover Sparse Graphical Models
Authors: Eugene Belilovsky and Kyle Kastner and Gael Varoquaux and Matthew B. Blaschko
Published in: Proceedings of the 34th International Conference on Machine Learning (Main Conference Track), 2017

Abstract: We consider structure discovery of undirected graphical models from observational data. Inferring likely structures from few examples is a complex task often requiring the formulation of priors and sophisticated inference procedures. Popular methods rely on estimating a penalized maximum likelihood of the precision matrix. However, in these approaches structure recovery is an indirect consequence of the data-fit term, the penalty can be difficult to adapt for domain-specific knowledge, and the inference is computationally demanding. By contrast, it may be easier to generate training samples of data that arise from graphs with the desired structure properties. We propose here to leverage this latter source of information as training data to learn a function, parametrized by a neural network, that maps empirical covariance matrices to estimated graph structures. Learning this function brings two benefits: it implicitly models the desired structure or sparsity properties to form suitable priors, and it can be tailored to the specific problem of edge structure discovery, rather than maximizing data likelihood. Applying this framework, we find our learnable graph-discovery method trained on synthetic data generalizes well: identifying relevant edges in both synthetic and real data, completely unknown at training time. We find that on genetics, brain imaging, and simulation data we obtain performance generally superior to analytical methods.