mtybilly/Instruct2DS huggingface dataset:
Dynamic Capacity Networks
Authors: Almahairi, Amjad and Ballas, Nicolas and Cooijmans, Tim and Zheng, Yin and Larochelle, Hugo and Courville, Aaron
Published in: Proceedings of The 33rd International Conference on Machine Learning (Main Conference Track), 2016

Abstract: We introduce the Dynamic Capacity Network (DCN), a neural network that can adaptively assign its capacity across different portions of the input data. This is achieved by combining modules of two types: low-capacity sub-networks and high-capacity sub-networks. The low-capacity sub-networks are applied across most of the input, but also provide a guide to select a few portions of the input on which to apply the high-capacity sub-networks. The selection is made using a novel gradient-based attention mechanism, that efficiently identifies input regions for which the DCN’s output is most sensitive and to which we should devote more capacity. We focus our empirical evaluation on the Cluttered MNIST and SVHN image datasets. Our findings indicate that DCNs are able to drastically reduce the number of computations, compared to traditional convolutional neural networks, while maintaining similar or even better performance.
Pricing a Low-regret Seller
Authors: Heidari, Hoda and Mahdian, Mohammad and Syed, Umar and Vassilvitskii, Sergei and Yazdanbod, Sadra
Published in: Proceedings of The 33rd International Conference on Machine Learning (Main Conference Track), 2016

Abstract: As the number of ad exchanges has grown, publishers have turned to low regret learning algorithms to decide which exchange offers the best price for their inventory. This in turn opens the following question for the exchange: how to set prices to attract as many sellers as possible and maximize revenue. In this work we formulate this precisely as a learning problem, and present algorithms showing that by simply knowing that the counterparty is using a low regret algorithm is enough for the exchange to have its own low regret learning algorithm to find the optimal price.
Estimation from Indirect Supervision with Linear Moments
Authors: Raghunathan, Aditi and Frostig, Roy and Duchi, John and Liang, Percy
Published in: Proceedings of The 33rd International Conference on Machine Learning (Main Conference Track), 2016

Abstract: In structured prediction problems where we have indirect supervision of the output, maximum marginal likelihood faces two computational obstacles: non-convexity of the objective and intractability of even a single gradient computation. In this paper, we bypass both obstacles for a class of what we call linear indirectly-supervised problems. Our approach is simple: we solve a linear system to estimate sufficient statistics of the model, which we then use to estimate parameters via convex optimization. We analyze the statistical properties of our approach and show empirically that it is effective in two settings: learning with local privacy constraints and learning from low-cost count-based annotations.
Speeding up k-means by approximating Euclidean distances via block vectors
Authors: Bottesch, Thomas and Bühler, Thomas and Kächele, Markus
Published in: Proceedings of The 33rd International Conference on Machine Learning (Main Conference Track), 2016

Abstract: This paper introduces a new method to approximate Euclidean distances between points using block vectors in combination with the Hölder inequality. By defining lower bounds based on the proposed approximation, cluster algorithms can be considerably accelerated without loss of quality. In extensive experiments, we show a considerable reduction in terms of computational time in comparison to standard methods and the recently proposed Yinyang k-means. Additionally we show that the memory consumption of the presented clustering algorithm does not depend on the number of clusters, which makes the approach suitable for large scale problems.
Learning and Inference via Maximum Inner Product Search
Authors: Mussmann, Stephen and Ermon, Stefano
Published in: Proceedings of The 33rd International Conference on Machine Learning (Main Conference Track), 2016

Abstract: A large class of commonly used probabilistic models known as log-linear models are defined up to a normalization constant.Typical learning algorithms for such models require solving a sequence of probabilistic inference queries. These inferences are typically intractable, and are a major bottleneck for learning models with large output spaces. In this paper, we provide a new approach for amortizing the cost of a sequence of related inference queries, such as the ones arising during learning. Our technique relies on a surprising connection with algorithms developed in the past two decades for similarity search in large data bases. Our approach achieves improved running times with provable approximation guarantees. We show that it performs well both on synthetic data and neural language models with large output spaces.
A Superlinearly-Convergent Proximal Newton-type Method for the Optimization of Finite Sums
Authors: Rodomanov, Anton and Kropotov, Dmitry
Published in: Proceedings of The 33rd International Conference on Machine Learning (Main Conference Track), 2016

Abstract: We consider the problem of minimizing the strongly convex sum of a finite number of convex functions. Standard algorithms for solving this problem in the class of incremental/stochastic methods have at most a linear convergence rate. We propose a new incremental method whose convergence rate is superlinear – the Newton-type incremental method (NIM). The idea of the method is to introduce a model of the objective with the same sum-of-functions structure and further update a single component of the model per iteration. We prove that NIM has a superlinear local convergence rate and linear global convergence rate. Experiments show that the method is very effective for problems with a large number of functions and a small number of variables.
A Kernel Test of Goodness of Fit
Authors: Chwialkowski, Kacper and Strathmann, Heiko and Gretton, Arthur
Published in: Proceedings of The 33rd International Conference on Machine Learning (Main Conference Track), 2016

Abstract: We propose a nonparametric statistical test for goodness-of-fit: given a set of samples, the test determines how likely it is that these were generated from a target density function. The measure of goodness-of-fit is a divergence constructed via Stein’s method using functions from a Reproducing Kernel Hilbert Space. Our test statistic is based on an empirical estimate of this divergence, taking the form of a V-statistic in terms of the log gradients of the target density and the kernel. We derive a statistical test, both for i.i.d. and non-i.i.d. samples, where we estimate the null distribution quantiles using a wild bootstrap procedure. We apply our test to quantifying convergence of approximate Markov Chain Monte Carlo methods, statistical model criticism, and evaluating quality of fit vs model complexity in nonparametric density estimation.
Interacting Particle Markov Chain Monte Carlo
Authors: Rainforth, Tom and Naesseth, Christian and Lindsten, Fredrik and Paige, Brooks and Vandemeent, Jan-Willem and Doucet, Arnaud and Wood, Frank
Published in: Proceedings of The 33rd International Conference on Machine Learning (Main Conference Track), 2016

Abstract: We introduce interacting particle Markov chain Monte Carlo (iPMCMC), a PMCMC method based on an interacting pool of standard and conditional sequential Monte Carlo samplers. Like related methods, iPMCMC is a Markov chain Monte Carlo sampler on an extended space. We present empirical results that show significant improvements in mixing rates relative to both non-interacting PMCMC samplers and a single PMCMC sampler with an equivalent memory and computational budget. An additional advantage of the iPMCMC method is that it is suitable for distributed and multi-core architectures.
Faster Eigenvector Computation via Shift-and-Invert Preconditioning
Authors: Garber, Dan and Hazan, Elad and Jin, Chi and Sham, and Musco, Cameron and Netrapalli, Praneeth and Sidford, Aaron
Published in: Proceedings of The 33rd International Conference on Machine Learning (Main Conference Track), 2016

Abstract: We give faster algorithms and improved sample complexities for the fundamental problem of estimating the top eigenvector. Given an explicit matrix $A ın ℝ^n \times d$, we show how to compute an $ε$-approximate top eigenvector of $A^TA$ in time $\tilde Ołeft( łeft[\textnnz(A) + \fracd \textsr(A)\textgap^2 i̊ght] · łog 1/ε\g̊ht)$. Here $\textnnz(A)$ is the number of nonzeros in $A$, $\textsr(A)$ is the stable rank, and gap is the relative eigengap. We also consider an online setting in which, given a stream of i.i.d. samples from a distribution D with covariance matrix $Σ$ and a vector $x_0$ which is an $O(\textgap)$ approximate top eigenvector for $Σ$, we show how to refine $x_0$ to an $ε$ approximation using  $O łeft( \frac\textvar(\mathcalD)\textgap-ε\rh̊t)$ samples from $\mathcalD$. Here $\textvar(\mathcalD)$ is a natural notion of variance. Combining our algorithm with previous work to initialize $x_0$, we obtain improved sample complexities and runtimes under a variety of assumptions on D. We achieve our results via a robust analysis of the classic shift-and-invert preconditioning method. This technique lets us reduce eigenvector computation to <i>approximately</i> solving a series of linear systems with fast stochastic gradient methods.
A Theory of Generative ConvNet
Authors: Xie, Jianwen and Lu, Yang and Zhu, Song-Chun and Wu, Yingnian
Published in: Proceedings of The 33rd International Conference on Machine Learning (Main Conference Track), 2016

Abstract: We show that a generative random field model, which we call generative ConvNet, can be derived from the commonly used discriminative ConvNet, by assuming a ConvNet for multi-category classification and assuming one of the category is a base category generated by a reference distribution. If we further assume that the non-linearity in the ConvNet is Rectified Linear Unit (ReLU) and the reference distribution is Gaussian white noise, then we obtain a generative ConvNet model that is unique among energy-based models: The model is piecewise Gaussian, and the means of the Gaussian pieces are defined by an auto-encoder, where the filters in the bottom-up encoding become the basis functions in the top-down decoding, and the binary activation variables detected by the filters in the bottom-up convolution process become the coefficients of the basis functions in the top-down deconvolution process. The Langevin dynamics for sampling the generative ConvNet is driven by the reconstruction error of this auto-encoder. The contrastive divergence learning of the generative ConvNet reconstructs the training images by the auto-encoder. The maximum likelihood learning algorithm can synthesize realistic natural image patterns.
Efficient Learning with a Family of Nonconvex Regularizers by Redistributing Nonconvexity
Authors: Yao, Quanming and Kwok, James
Published in: Proceedings of The 33rd International Conference on Machine Learning (Main Conference Track), 2016

Abstract: The use of convex regularizers allow for easy optimization, though they often produce biased estimation and inferior prediction performance. Recently, nonconvex regularizers have attracted a lot of attention and outperformed convex ones. However, the resultant optimization problem is much harder. In this paper, for a large class of nonconvex regularizers, we propose to move the nonconvexity from the regularizer to the loss. The nonconvex regularizer is then transformed to a familiar convex regularizer, while the resultant loss function can still be guaranteed to be smooth. Learning with the convexified regularizer can be performed by existing efficient algorithms originally designed for convex regularizers (such as the standard proximal algorithm and Frank-Wolfe algorithm). Moreover, it can be shown that critical points of the transformed problem are also critical points of the original problem. Extensive experiments on a number of nonconvex regularization problems show that the proposed procedure is much faster than the state-of-the-art nonconvex solvers.
Computationally Efficient Nyström Approximation using Fast Transforms
Authors: Si, Si and Hsieh, Cho-Jui and Dhillon, Inderjit
Published in: Proceedings of The 33rd International Conference on Machine Learning (Main Conference Track), 2016

Abstract: Our goal is to improve the ıt training and ıt prediction time of Nyström method, which is a widely-used technique for generating low-rank kernel matrix approximations. When applying the Nyström approximation for large-scale applications, both training and prediction time is dominated by computing kernel values between a data point and all landmark points. With m landmark points, this computation requires Θ(md) time (flops), where d is the input dimension. In this paper, we propose the use of a family of fast transforms to generate structured landmark points for Nyström approximation. By exploiting fast transforms, e.g., Haar transform and Hadamard transform, our modified Nyström method requires only Θ(m) or Θ(młog d) time to compute the kernel values between a given data point and m landmark points. This improvement in time complexity can significantly speed up kernel approximation and benefit prediction speed in kernel machines. For instance, on the webspam data (more than 300,000 data points), our proposed algorithm enables kernel SVM prediction to deliver 98% accuracy and the resulting prediction time is 1000 times faster than LIBSVM and only 10 times slower than linear SVM prediction (which yields only 91% accuracy).
Gromov-Wasserstein Averaging of Kernel and Distance Matrices
Authors: Peyré, Gabriel and Cuturi, Marco and Solomon, Justin
Published in: Proceedings of The 33rd International Conference on Machine Learning (Main Conference Track), 2016

Abstract: This paper presents a new technique for computing the barycenter of a set of distance or kernel matrices. These matrices, which define the inter-relationships between points sampled from individual domains, are not required to have the same size or to be in row-by-row correspondence. We compare these matrices using the softassign criterion, which measures the minimum distortion induced by a probabilistic map from the rows of one similarity matrix to the rows of another; this criterion amounts to a regularized version of the Gromov-Wasserstein (GW) distance between metric-measure spaces. The barycenter is then defined as a Fréchet mean of the input matrices with respect to this criterion, minimizing a weighted sum of softassign values. We provide a fast iterative algorithm for the resulting nonconvex optimization problem, built upon state-of- the-art tools for regularized optimal transportation. We demonstrate its application to the computation of shape barycenters and to the prediction of energy levels from molecular configurations in quantum chemistry.
Robust Monte Carlo Sampling using Riemannian Nosé-Poincaré Hamiltonian Dynamics
Authors: Roychowdhury, Anirban and Kulis, Brian and Parthasarathy, Srinivasan
Published in: Proceedings of The 33rd International Conference on Machine Learning (Main Conference Track), 2016

Abstract: We present a Monte Carlo sampler using a modified Nosé-Poincaré Hamiltonian along with Riemannian preconditioning. Hamiltonian Monte Carlo samplers allow better exploration of the state space as opposed to random walk-based methods, but, from a molecular dynamics perspective, may not necessarily provide samples from the canonical ensemble. Nosé-Hoover samplers rectify that shortcoming, but the resultant dynamics are not Hamiltonian. Furthermore, usage of these algorithms on large real-life datasets necessitates the use of stochastic gradients, which acts as another potentially destabilizing source of noise. In this work, we propose dynamics based on a modified Nosé-Poincaré Hamiltonian augmented with Riemannian manifold corrections. The resultant symplectic sampling algorithm samples from the canonical ensemble while using structural cues from the Riemannian preconditioning matrices to efficiently traverse the parameter space. We also propose a stochastic variant using additional terms in the Hamiltonian to correct for the noise from the stochastic gradients. We show strong performance of our algorithms on synthetic datasets and high-dimensional Poisson factor analysis-based topic modeling scenarios.
The Segmented iHMM: A Simple, Efficient Hierarchical Infinite HMM
Authors: Saeedi, Ardavan and Hoffman, Matthew and Johnson, Matthew and Adams, Ryan
Published in: Proceedings of The 33rd International Conference on Machine Learning (Main Conference Track), 2016

Abstract: We propose the segmented iHMM (siHMM), a hierarchical infinite hidden Markov model (iHMM) that supports a simple, efficient inference scheme. The siHMM is well suited to segmentation problems, where the goal is to identify points at which a time series transitions from one relatively stable regime to a new regime. Conventional iHMMs often struggle with such problems, since they have no mechanism for distinguishing between high-and low-level dynamics. Hierarchical HMMs (HHMMs) can do better, but they require much more complex and expensive inference algorithms. The siHMM retains the simplicity and efficiency of the iHMM, but outperforms it on a variety of segmentation problems, achieving performance that matches or exceeds that of a more complicated HHMM.
Meta--Gradient Boosted Decision Tree Model for Weight and Target Learning
Authors: Ustinovskiy, Yury and Fedorova, Valentina and Gusev, Gleb and Serdyukov, Pavel
Published in: Proceedings of The 33rd International Conference on Machine Learning (Main Conference Track), 2016

Abstract: Labeled training data is an essential part of any supervised machine learning framework. In practice, there is a trade-off between the quality of a label and its cost. In this paper, we consider a problem of learning to rank on a large-scale dataset with low-quality relevance labels aiming at maximizing the quality of a trained ranker on a small validation dataset with high-quality ground truth relevance labels. Motivated by the classical Gauss-Markov theorem for the linear regression problem, we formulate the problems of (1) reweighting training instances and (2) remapping learning targets. We propose meta–gradient decision tree learning framework for optimizing weight and target functions by applying gradient-based hyperparameter optimization. Experiments on a large-scale real-world dataset demonstrate that we can significantly improve state-of-the-art machine-learning algorithms by incorporating our framework.
Discriminative Embeddings of Latent Variable Models for Structured Data
Authors: Dai, Hanjun and Dai, Bo and Song, Le
Published in: Proceedings of The 33rd International Conference on Machine Learning (Main Conference Track), 2016

Abstract: Kernel classifiers and regressors designed for structured data, such as sequences, trees and graphs, have significantly advanced a number of interdisciplinary areas such as computational biology and drug design. Typically, kernels are designed beforehand for a data type which either exploit statistics of the structures or make use of probabilistic generative models, and then a discriminative classifier is learned based on the kernels via convex optimization. However, such an elegant two-stage approach also limited kernel methods from scaling up to millions of data points, and exploiting discriminative information to learn feature representations. We propose, structure2vec, an effective and scalable approach for structured data representation based on the idea of embedding latent variable models into feature spaces, and learning such feature spaces using discriminative information. Interestingly, structure2vec extracts features by performing a sequence of function mappings in a way similar to graphical model inference procedures, such as mean field and belief propagation. In applications involving millions of data points, we showed that structure2vec runs 2 times faster, produces models which are 10,000 times smaller, while at the same time achieving the state-of-the-art predictive performance.
Robust Random Cut Forest Based Anomaly Detection on Streams
Authors: Guha, Sudipto and Mishra, Nina and Roy, Gourav and Schrijvers, Okke
Published in: Proceedings of The 33rd International Conference on Machine Learning (Main Conference Track), 2016

Abstract: In this paper we focus on the anomaly detection problem for dynamic data streams through the lens of random cut forests. We investigate a robust random cut data structure that can be used as a sketch or synopsis of the input stream. We provide a plausible definition of non-parametric anomalies based on the influence of an unseen point on the remainder of the data, i.e., the externality imposed by that point. We show how the sketch can be efficiently updated in a dynamic data stream. We demonstrate the viability of the algorithm on publicly available real data.
Training Neural Networks Without Gradients: A Scalable ADMM Approach
Authors: Taylor, Gavin and Burmeister, Ryan and Xu, Zheng and Singh, Bharat and Patel, Ankit and Goldstein, Tom
Published in: Proceedings of The 33rd International Conference on Machine Learning (Main Conference Track), 2016

Abstract: With the growing importance of large network models and enormous training datasets, GPUs have become increasingly necessary to train neural networks. This is largely because conventional optimization algorithms rely on stochastic gradient methods that don’t scale well to large numbers of cores in a cluster setting. Furthermore, the convergence of all gradient methods, including batch methods, suffers from common problems like saturation effects, poor conditioning, and saddle points. This paper explores an unconventional training method that uses alternating direction methods and Bregman iteration to train networks without gradient descent steps. The proposed method reduces the network training problem to a sequence of minimization sub-steps that can each be solved globally in closed form. The proposed method is advantageous because it avoids many of the caveats that make gradient methods slow on highly non-convex problems. In addition, the method exhibits strong scaling in the distributed setting, yielding linear speedups even when split over thousands of cores.
Clustering High Dimensional Categorical Data via Topographical Features
Authors: Chen, Chao and Quadrianto, Novi
Published in: Proceedings of The 33rd International Conference on Machine Learning (Main Conference Track), 2016

Abstract: Analysis of categorical data is a challenging task. In this paper, we propose to compute topographical features of high-dimensional categorical data. We propose an efficient algorithm to extract modes of the underlying distribution and their attractive basins. These topographical features provide a geometric view of the data and can be applied to visualization and clustering of real world challenging datasets. Experiments show that our principled method outperforms state-of-the-art clustering methods while also admits an embarrassingly parallel property.
Efficient Algorithms for Large-scale Generalized Eigenvector Computation and Canonical Correlation Analysis
Authors: Ge, Rong and Jin, Chi and Sham, and Netrapalli, Praneeth and Sidford, Aaron
Published in: Proceedings of The 33rd International Conference on Machine Learning (Main Conference Track), 2016

Abstract: This paper considers the problem of canonical-correlation analysis (CCA) and, more broadly, the generalized eigenvector problem for a pair of symmetric matrices. These are two fundamental problems in data analysis and scientific computing with numerous applications in machine learning and statistics. We provide simple iterative algorithms, with improved runtimes, for solving these problems that are globally linearly convergent with moderate dependencies on the condition numbers and eigenvalue gaps of the matrices involved. We obtain our results by reducing CCA to the top-k generalized eigenvector problem. We solve this problem through a general framework that simply requires black box access to an approximate linear system solver. Instantiating this framework with accelerated gradient descent we obtain a running time of ørder\fracz k \sqrtκρ łog(1/ε) łog łeft(kκ/ρi̊ght) where z is the total number of nonzero entries, κis the condition number and ρis the relative eigenvalue gap of the appropriate matrices. Our algorithm is linear in the input size and the number of components k up to a łog(k) factor. This is essential for handling large-scale matrices that appear in practice. To the best of our knowledge this is the first such algorithm with global linear convergence. We hope that our results prompt further research and ultimately improve the practical running time for performing these important data analysis procedures on large data sets.
Algorithms for Optimizing the Ratio of Submodular Functions
Authors: Bai, Wenruo and Iyer, Rishabh and Wei, Kai and Bilmes, Jeff
Published in: Proceedings of The 33rd International Conference on Machine Learning (Main Conference Track), 2016

Abstract: We investigate a new optimization problem involving minimizing the Ratio of Submodular (RS) functions. We argue that this problem occurs naturally in several real world applications. We then show the connection between this problem and several related problems, including minimizing the difference of submodular functions, and to submodular optimization subject to submodular constraints. We show RS that optimization can be solved within bounded approximation factors. We also provide a hardness bound and show that our tightest algorithm matches the lower bound up to a łog factor. Finally, we empirically demonstrate the performance and good scalability properties of our algorithms.
Model-Free Imitation Learning with Policy Optimization
Authors: Ho, Jonathan and Gupta, Jayesh and Ermon, Stefano
Published in: Proceedings of The 33rd International Conference on Machine Learning (Main Conference Track), 2016

Abstract: In imitation learning, an agent learns how to behave in an environment with an unknown cost function by mimicking expert demonstrations. Existing imitation learning algorithms typically involve solving a sequence of planning or reinforcement learning problems. Such algorithms are therefore not directly applicable to large, high-dimensional environments, and their performance can significantly degrade if the planning problems are not solved to optimality. Under the apprenticeship learning formalism, we develop alternative model-free algorithms for finding a parameterized stochastic policy that performs at least as well as an expert policy on an unknown cost function, based on sample trajectories from the expert. Our approach, based on policy gradients, scales to large continuous environments with guaranteed convergence to local minima.
ADIOS: Architectures Deep In Output Space
Authors: Cisse, Moustapha and Al-Shedivat, Maruan and Bengio, Samy
Published in: Proceedings of The 33rd International Conference on Machine Learning (Main Conference Track), 2016

Abstract: Multi-label classification is a generalization of binary classification where the task consists in predicting \emphsets of labels. With the availability of ever larger datasets, the multi-label setting has become a natural one in many applications, and the interest in solving multi-label problems has grown significantly. As expected, deep learning approaches are now yielding state-of-the-art performance for this class of problems. Unfortunately, they usually do not take into account the often unknown but nevertheless rich relationships between labels. In this paper, we propose to make use of this underlying structure by learning to partition the labels into a Markov Blanket Chain and then applying a novel deep architecture that exploits the partition. Experiments on several popular and large multi-label datasets demonstrate that our approach not only yields significant improvements, but also helps to overcome trade-offs specific to the multi-label classification setting.
Conditional Dependence via Shannon Capacity: Axioms, Estimators and Applications
Authors: Gao, Weihao and Kannan, Sreeram and Oh, Sewoong and Viswanath, Pramod
Published in: Proceedings of The 33rd International Conference on Machine Learning (Main Conference Track), 2016

Abstract: We consider axiomatically the problem of estimating the strength of a conditional dependence relationship P_Y|X from a random variables X to a random variable Y. This has applications in determining the strength of a known causal relationship, where the strength depends only on the conditional distribution of the effect given the cause (and not on the driving distribution of the cause). Shannon capacity, appropriately regularized, emerges as a natural measure under these axioms. We examine the problem of calculating Shannon capacity from the observed samples and propose a novel fixed-k nearest neighbor estimator, and demonstrate its consistency. Finally, we demonstrate an application to single-cell flow-cytometry, where the proposed estimators significantly reduce sample complexity.
Control of Memory, Active Perception, and Action in Minecraft
Authors: Oh, Junhyuk and Chockalingam, Valliappa and Satinder, and Lee, Honglak
Published in: Proceedings of The 33rd International Conference on Machine Learning (Main Conference Track), 2016

Abstract: In this paper, we introduce a new set of reinforcement learning (RL) tasks in Minecraft (a flexible 3D world). We then use these tasks to systematically compare and contrast existing deep reinforcement learning (DRL) architectures with our new memory-based DRL architectures. These tasks are designed to emphasize, in a controllable manner, issues that pose challenges for RL methods including partial observability (due to first-person visual observations), delayed rewards, high-dimensional visual observations, and the need to use active perception in a correct manner so as to perform well in the tasks. While these tasks are conceptually simple to describe, by virtue of having all of these challenges simultaneously they are difficult for current DRL architectures. Additionally, we evaluate the generalization performance of the architectures on environments not used during training. The experimental results show that our new architectures generalize to unseen environments better than existing DRL architectures.
The Label Complexity of Mixed-Initiative Classifier Training
Authors: Suh, Jina and Zhu, Xiaojin and Amershi, Saleema
Published in: Proceedings of The 33rd International Conference on Machine Learning (Main Conference Track), 2016

Abstract: Mixed-initiative classifier training, where the human teacher can choose which items to label or to label items chosen by the computer, has enjoyed empirical success but without a rigorous statistical learning theoretical justification. We analyze the label complexity of a simple mixed-initiative training mechanism using teach- ing dimension and active learning. We show that mixed-initiative training is advantageous com- pared to either computer-initiated (represented by active learning) or human-initiated classifier training. The advantage exists across all human teaching abilities, from optimal to completely unhelpful teachers. We further improve classifier training by educating the human teachers. This is done by showing, or explaining, optimal teaching sets to the human teachers. We conduct Mechanical Turk human experiments on two stylistic classifier training tasks to illustrate our approach.
Bayesian Poisson Tucker Decomposition for Learning the Structure of International Relations
Authors: Schein, Aaron and Zhou, Mingyuan and Blei, David and Wallach, Hanna
Published in: Proceedings of The 33rd International Conference on Machine Learning (Main Conference Track), 2016

Abstract: We introduce Bayesian Poisson Tucker decomposition (BPTD) for modeling country–country interaction event data. These data consist of interaction events of the form “country i took action a toward country j at time t.” BPTD discovers overlapping country–community memberships, including the number of latent communities. In addition, it discovers directed community–community interaction networks that are specific to “topics” of action types and temporal “regimes.” We show that BPTD yields an efficient MCMC inference algorithm and achieves better predictive performance than related models. We also demonstrate that it discovers interpretable latent structure that agrees with our knowledge of international relations.
Tensor Decomposition via Joint Matrix Schur Decomposition
Authors: Colombo, Nicolo and Vlassis, Nikos
Published in: Proceedings of The 33rd International Conference on Machine Learning (Main Conference Track), 2016

Abstract: We describe an approach to tensor decomposition that involves extracting a set of observable matrices from the tensor and applying an approximate joint Schur decomposition on those matrices, and we establish the corresponding first-order perturbation bounds. We develop a novel iterative Gauss-Newton algorithm for joint matrix Schur decomposition, which minimizes a nonconvex objective over the manifold of orthogonal matrices, and which is guaranteed to converge to a global optimum under certain conditions. We empirically demonstrate that our algorithm is faster and at least as accurate and robust than state-of-the-art algorithms for this problem.
Continuous Deep Q-Learning with Model-based Acceleration
Authors: Gu, Shixiang and Lillicrap, Timothy and Sutskever, Ilya and Levine, Sergey
Published in: Proceedings of The 33rd International Conference on Machine Learning (Main Conference Track), 2016

Abstract: Model-free reinforcement learning has been successfully applied to a range of challenging problems, and has recently been extended to handle large neural network policies and value functions. However, the sample complexity of model-free algorithms, particularly when using high-dimensional function approximators, tends to limit their applicability to physical systems. In this paper, we explore algorithms and representations to reduce the sample complexity of deep reinforcement learning for continuous control tasks. We propose two complementary techniques for improving the efficiency of such algorithms. First, we derive a continuous variant of the Q-learning algorithm, which we call normalized advantage functions (NAF), as an alternative to the more commonly used policy gradient and actor-critic methods. NAF representation allows us to apply Q-learning with experience replay to continuous tasks, and substantially improves performance on a set of simulated robotic control tasks. To further improve the efficiency of our approach, we explore the use of learned models for accelerating model-free reinforcement learning. We show that iteratively refitted local linear models are especially effective for this, and demonstrate substantially faster learning on domains where such models are applicable.
Domain Adaptation with Conditional Transferable Components
Authors: Gong, Mingming and Zhang, Kun and Liu, Tongliang and Tao, Dacheng and Glymour, Clark and Schölkopf, Bernhard
Published in: Proceedings of The 33rd International Conference on Machine Learning (Main Conference Track), 2016

Abstract: Domain adaptation arises in supervised learning when the training (source domain) and test (target domain) data have different distributions. Let X and Y denote the features and target, respectively, previous work on domain adaptation considers the covariate shift situation where the distribution of the features P(X) changes across domains while the conditional distribution P(Y|X) stays the same. To reduce domain discrepancy, recent methods try to find invariant components \mathcalT(X) that have similar P(\mathcalT(X)) by explicitly minimizing a distribution discrepancy measure. However, it is not clear if P(Y|\mathcalT(X)) in different domains is also similar when P(Y|X) changes. Furthermore, transferable components do not necessarily have to be invariant. If the change in some components is identifiable, we can make use of such components for prediction in the target domain. In this paper, we focus on the case where P(X|Y) and P(Y) both change in a causal system in which Y is the cause for X. Under appropriate assumptions, we aim to extract conditional transferable components whose conditional distribution P(\mathcalT(X)|Y) is invariant after proper location-scale (LS) transformations, and identify how P(Y) changes between domains simultaneously. We provide theoretical analysis and empirical evaluation on both synthetic and real-world data to show the effectiveness of our method.
Fixed Point Quantization of Deep Convolutional Networks
Authors: Lin, Darryl and Talathi, Sachin and Annapureddy, Sreekanth
Published in: Proceedings of The 33rd International Conference on Machine Learning (Main Conference Track), 2016

Abstract: In recent years increasingly complex architectures for deep convolution networks (DCNs) have been proposed to boost the performance on image recognition tasks. However, the gains in performance have come at a cost of substantial increase in computation and model storage resources. Fixed point implementation of DCNs has the potential to alleviate some of these complexities and facilitate potential deployment on embedded hardware. In this paper, we propose a quantizer design for fixed point implementation of DCNs. We formulate and solve an optimization problem to identify optimal fixed point bit-width allocation across DCN layers. Our experiments show that in comparison to equal bit-width settings, the fixed point DCNs with optimized bit width allocation offer >20% reduction in the model size without any loss in accuracy on CIFAR-10 benchmark. We also demonstrate that fine-tuning can further enhance the accuracy of fixed point DCNs beyond that of the original floating point model. In doing so, we report a new state-of-the-art fixed point performance of 6.78% error-rate on CIFAR-10 benchmark.
Provable Algorithms for Inference in Topic Models
Authors: Arora, Sanjeev and Ge, Rong and Koehler, Frederic and Ma, Tengyu and Moitra, Ankur
Published in: Proceedings of The 33rd International Conference on Machine Learning (Main Conference Track), 2016

Abstract: Recently, there has been considerable progress on designing algorithms with provable guarantees —typically using linear algebraic methods—for parameter learning in latent variable models. Designing provable algorithms for inference has proved more difficult. Here we take a first step towards provable inference in topic models. We leverage a property of topic models that enables us to construct simple linear estimators for the unknown topic proportions that have small variance, and consequently can work with short documents. Our estimators also correspond to finding an estimate around which the posterior is well-concentrated. We show lower bounds that for shorter documents it can be information theoretically impossible to find the hidden topics. Finally, we give empirical results that demonstrate that our algorithm works on realistic topic models. It yields good solutions on synthetic data and runs in time comparable to a single iteration of Gibbs sampling.
Epigraph projections for fast general convex programming
Authors: Wang, Po-Wei and Wytock, Matt and Kolter, Zico
Published in: Proceedings of The 33rd International Conference on Machine Learning (Main Conference Track), 2016

Abstract: This paper develops an approach for efficiently solving general convex optimization problems specified as disciplined convex programs (DCP), a common general-purpose modeling framework. Specifically we develop an algorithm based upon fast epigraph projections, projections onto the epigraph of a convex function, an approach closely linked to proximal operator methods. We show that by using these operators, we can solve any disciplined convex program without transforming the problem to a standard cone form, as is done by current DCP libraries. We then develop a large library of efficient epigraph projection operators, mirroring and extending work on fast proximal algorithms, for many common convex functions. Finally, we evaluate the performance of the algorithm, and show it often achieves order of magnitude speedups over existing general-purpose optimization solvers.
Fast Algorithms for Segmented Regression
Authors: Acharya, Jayadev and Diakonikolas, Ilias and Li, Jerry and Schmidt, Ludwig
Published in: Proceedings of The 33rd International Conference on Machine Learning (Main Conference Track), 2016

Abstract: We study the fixed design segmented regression problem: Given noisy samples from a piecewise linear function f, we want to recover f up to a desired accuracy in mean-squared error. Previous rigorous approaches for this problem rely on dynamic programming (DP) and, while sample efficient, have running time quadratic in the sample size. As our main contribution, we provide new sample near-linear time algorithms for the problem that - while not being minimax optimal - achieve a significantly better sample-time tradeoff on large datasets compared to the DP approach. Our experimental evaluation shows that, compared with the DP approach, our algorithms provide a convergence rate that is only off by a factor of 2 to 4, while achieving speedups of three orders of magnitude.
Energetic Natural Gradient Descent
Authors: Thomas, Philip and Silva, Bruno Castro and Dann, Christoph and Brunskill, Emma
Published in: Proceedings of The 33rd International Conference on Machine Learning (Main Conference Track), 2016

Abstract: We propose a new class of algorithms for minimizing or maximizing functions of parametric probabilistic models. These new algorithms are natural gradient algorithms that leverage more information than prior methods by using a new metric tensor in place of the commonly used Fisher information matrix. This new metric tensor is derived by computing directions of steepest ascent where the distance between distributions is measured using an approximation of energy distance (as opposed to Kullback-Leibler divergence, which produces the Fisher information matrix), and so we refer to our new ascent direction as the energetic natural gradient.
Partition Functions from Rao-Blackwellized Tempered Sampling
Authors: Carlson, David and Stinson, Patrick and Pakman, Ari and Paninski, Liam
Published in: Proceedings of The 33rd International Conference on Machine Learning (Main Conference Track), 2016

Abstract: Partition functions of probability distributions are important quantities for model evaluation and comparisons. We present a new method to compute partition functions of complex and multimodal distributions. Such distributions are often sampled using simulated tempering, which augments the target space with an auxiliary inverse temperature variable. Our method exploits the multinomial probability law of the inverse temperatures, and provides estimates of the partition function in terms of a simple quotient of Rao-Blackwellized marginal inverse temperature probability estimates, which are updated while sampling. We show that the method has interesting connections with several alternative popular methods, and offers some significant advantages. In particular, we empirically find that the new method provides more accurate estimates than Annealed Importance Sampling when calculating partition functions of large Restricted Boltzmann Machines (RBM); moreover, the method is sufficiently accurate to track training and validation log-likelihoods during learning of RBMs, at minimal computational cost.
Learning Mixtures of Plackett-Luce Models
Authors: Zhao, Zhibing and Piech, Peter and Xia, Lirong
Published in: Proceedings of The 33rd International Conference on Machine Learning (Main Conference Track), 2016

Abstract: In this paper we address the identifiability and efficient learning problems of finite mixtures of Plackett-Luce models for rank data. We prove that for any k≥2, the mixture of k Plackett-Luce models for no more than 2k-1 alternatives is non-identifiable and this bound is tight for k=2. For generic identifiability, we prove that the mixture of k Plackett-Luce models over m alternatives is \em generically identifiable if k≤⌊\frac m-2 2⌋!. We also propose an efficient generalized method of moments (GMM) algorithm to learn the mixture of two Plackett-Luce models and show that the algorithm is consistent. Our experiments show that our GMM algorithm is significantly faster than the EMM algorithm by Gormley & Murphy (2008), while achieving competitive statistical efficiency.
Near Optimal Behavior via Approximate State Abstraction
Authors: Abel, David and Hershkowitz, David and Littman, Michael
Published in: Proceedings of The 33rd International Conference on Machine Learning (Main Conference Track), 2016

Abstract: The combinatorial explosion that plagues planning and reinforcement learning (RL) algorithms can be moderated using state abstraction. Prohibitively large task representations can be condensed such that essential information is preserved, and consequently, solutions are tractably computable. However, exact abstractions, which treat only fully-identical situations as equivalent, fail to present opportunities for abstraction in environments where no two situations are exactly alike. In this work, we investigate approximate state abstractions, which treat nearly-identical situations as equivalent. We present theoretical guarantees of the quality of behaviors derived from four types of approximate abstractions. Additionally, we empirically demonstrate that approximate abstractions lead to reduction in task complexity and bounded loss of optimality of behavior in a variety of environments.
Power of Ordered Hypothesis Testing
Authors: Lei, Lihua and Fithian, William
Published in: Proceedings of The 33rd International Conference on Machine Learning (Main Conference Track), 2016

Abstract: Ordered testing procedures are multiple testing procedures that exploit a pre-specified ordering of the null hypotheses, from most to least promising. We analyze and compare the power of several recent proposals using the asymptotic framework of Li & Barber (2015). While accumulation tests including ForwardStop can be quite powerful when the ordering is very informative, they are asymptotically powerless when the ordering is weaker. By contrast, Selective SeqStep, proposed by Barber & Candes (2015), is much less sensitive to the quality of the ordering. We compare the power of these procedures in different regimes, concluding that Selective SeqStep dominates accumulation tests if either the ordering is weak or non-null hypotheses are sparse or weak. Motivated by our asymptotic analysis, we derive an improved version of Selective SeqStep which we call Adaptive SeqStep, analogous to Storey’s improvement on the Benjamini-Hochberg procedure. We compare these methods using the GEO-Query data set analyzed by (Li & Barber, 2015) and find Adaptive SeqStep has favorable performance for both good and bad prior orderings.
PHOG: Probabilistic Model for Code
Authors: Bielik, Pavol and Raychev, Veselin and Vechev, Martin
Published in: Proceedings of The 33rd International Conference on Machine Learning (Main Conference Track), 2016

Abstract: We introduce a new generative model for code called probabilistic higher order grammar (PHOG). PHOG generalizes probabilistic context free grammars (PCFGs) by allowing conditioning of a production rule beyond the parent non-terminal, thus capturing rich contexts relevant to programs. Even though PHOG is more powerful than a PCFG, it can be learned from data just as efficiently. We trained a PHOG model on a large JavaScript code corpus and show that it is more precise than existing models, while similarly fast. As a result, PHOG can immediately benefit existing programming tools based on probabilistic models of code.