mtybilly/Instruct2DS huggingface dataset:
Towards End-To-End Speech Recognition with Recurrent Neural Networks
Authors: Alex Graves, Navdeep Jaitly
Published in: Proceedings of the 31st International Conference on Machine Learning (Main Conference Track), 2014

Abstract: This paper presents a speech recognition system that directly transcribes audio data with text, without requiring an intermediate phonetic representation. The system is based on a combination of the deep bidirectional LSTM recurrent neural network architecture and the Connectionist Temporal Classification objective function. A modification to the objective function is introduced that trains the network to minimise the expectation of an arbitrary transcription loss function. This allows a direct optimisation of the word error rate, even in the absence of a lexicon or language model. The system achieves a word error rate of 27.3% on the Wall Street Journal corpus with no prior linguistic information, 21.9% with only a lexicon of allowed words, and 8.2% with a trigram language model. Combining the network with a baseline system further reduces the error rate to 6.7%.
Multi-period Trading Prediction Markets with Connections to Machine Learning
Authors: Jinli Hu, Amos Storkey
Published in: Proceedings of the 31st International Conference on Machine Learning (Main Conference Track), 2014

Abstract: We present a new model for prediction markets, in which we use risk measures to model agents and introduce a market maker to describe the trading process. This specific choice of modelling approach enables us to show that the whole market approaches a global objective, despite the fact that the market is designed such that each agent only cares about its own goal. In addition, the market dynamic provides a sensible algorithm for optimising the global objective. An intimate connection between machine learning and our markets is thus established, such that we could 1) analyse a market by applying machine learning methods to the global objective; and 2) solve machine learning problems by setting up and running certain markets.
Efficient Gradient-Based Inference through Transformations between Bayes Nets and Neural Nets
Authors: Diederik Kingma, Max Welling
Published in: Proceedings of the 31st International Conference on Machine Learning (Main Conference Track), 2014

Abstract: Hierarchical Bayesian networks and neural networks with stochastic hidden units are commonly perceived as two separate types of models. We show that either of these types of models can often be transformed into an instance of the other, by switching between centered and differentiable non-centered parameterizations of the latent variables. The choice of parameterization greatly influences the efficiency of gradient-based posterior inference; we show that they are often complementary to eachother, we clarify when each parameterization is preferred and show how inference can be made robust. In the non-centered form, a simple Monte Carlo estimator of the marginal likelihood can be used for learning the parameters. Theoretical results are supported by experiments.
Neural Variational Inference and Learning in Belief Networks
Authors: Andriy Mnih, Karol Gregor
Published in: Proceedings of the 31st International Conference on Machine Learning (Main Conference Track), 2014

Abstract: Highly expressive directed latent variable models, such as sigmoid belief networks, are difficult to train on large datasets because exact inference in them is intractable and none of the approximate inference methods that have been applied to them scale well. We propose a fast non-iterative approximate inference method that uses a feedforward network to implement efficient exact sampling from the variational posterior. The model and this inference network are trained jointly by maximizing a variational lower bound on the log-likelihood. Although the naive estimator of the inference network gradient is too high-variance to be useful, we make it practical by applying several straightforward model-independent variance reduction techniques. Applying our approach to training sigmoid belief networks and deep autoregressive networks, we show that it outperforms the wake-sleep algorithm on MNIST and achieves state-of-the-art results on the Reuters RCV1 document dataset.
Scalable Bayesian Low-Rank Decomposition of Incomplete Multiway Tensors
Authors: Piyush Rai, Yingjian Wang, Shengbo Guo, Gary Chen, David Dunson, Lawrence Carin
Published in: Proceedings of the 31st International Conference on Machine Learning (Main Conference Track), 2014

Abstract: We present a scalable Bayesian framework for low-rank decomposition of multiway tensor data with missing observations. The key issue of pre-specifying the rank of the decomposition is sidestepped in a principled manner using a multiplicative gamma process prior. Both continuous and binary data can be analyzed under the framework, in a coherent way using fully conjugate Bayesian analysis. In particular, the analysis in the non-conjugate binary case is facilitated via the use of the Pólya-Gamma sampling strategy which elicits closed-form Gibbs sampling updates. The resulting samplers are efficient and enable us to apply our framework to large-scale problems, with time-complexity that is linear in the number of observed entries in the tensor. This is especially attractive in analyzing very large but sparsely observed tensors with very few known entries. Moreover, our method admits easy extension to the supervised setting where entities in one or more tensor modes have labels. Our method outperforms several state-of-the-art tensor decomposition methods on various synthetic and benchmark real-world datasets.
Beta Diffusion Trees
Authors: Creighton Heaukulani, David Knowles, Zoubin Ghahramani
Published in: Proceedings of the 31st International Conference on Machine Learning (Main Conference Track), 2014

Abstract: We define the beta diffusion tree, a random tree structure with a set of leaves that defines a collection of overlapping subsets of objects, known as a feature allocation. The generative process for the tree is defined in terms of particles (representing the objects) diffusing in some continuous space, analogously to the Dirichlet and Pitman-Yor diffusion trees (Neal, 2003b; Knowles & Ghahramani, 2011), both of which define tree structures over clusters of the particles. With the beta diffusion tree, however, multiple copies of a particle may exist and diffuse to multiple locations in the continuous space, resulting in (a random number of) possibly overlapping clusters of the objects. We demonstrate how to build a hierarchically-clustered factor analysis model with the beta diffusion tree and how to perform inference over the random tree structures with a Markov chain Monte Carlo algorithm. We conclude with several numerical experiments on missing data problems with data sets of gene expression arrays, international development statistics, and intranational socioeconomic measurements.
Learning Character-level Representations for Part-of-Speech Tagging
Authors: Cicero Dos Santos, Bianca Zadrozny
Published in: Proceedings of the 31st International Conference on Machine Learning (Main Conference Track), 2014

Abstract: Distributed word representations have recently been proven to be an invaluable resource for NLP. These representations are normally learned using neural networks and capture syntactic and semantic information about words. Information about word morphology and shape is normally ignored when learning word representations. However, for tasks like part-of-speech tagging, intra-word information is extremely useful, specially when dealing with morphologically rich languages. In this paper, we propose a deep neural network that learns character-level representation of words and associate them with usual word representations to perform POS tagging. Using the proposed approach, while avoiding the use of any handcrafted feature, we produce state-of-the-art POS taggers for two languages: English, with 97.32% accuracy on the Penn Treebank WSJ corpus; and Portuguese, with 97.47% accuracy on the Mac-Morpho corpus, where the latter represents an error reduction of 12.2% on the best previous known result.
Saddle Points and Accelerated Perceptron Algorithms
Authors: Adams Wei Yu, Fatma Kilinc-Karzan, Jaime Carbonell
Published in: Proceedings of the 31st International Conference on Machine Learning (Main Conference Track), 2014

Abstract: In this paper, we consider the problem of finding a linear (binary) classifier or providing a near-infeasibility certificate if there is none. We bring a new perspective to addressing these two problems simultaneously in a single efficient process, by investigating a related Bilinear Saddle Point Problem (BSPP). More specifically, we show that a BSPP-based approach provides either a linear classifier or an ε-infeasibility certificate. We show that the accelerated primal-dual algorithm, Mirror Prox, can be used for this purpose and achieves the best known convergence rate of O(\sqrtłog nøverρ(A)) (O(\sqrtłog nøverε)), which is \emphalmost independent of the problem size, n. Our framework also solves kernelized and conic versions of the problem, with the same rate of convergence. We support our theoretical findings with an empirical study on synthetic and real data, highlighting the efficiency and numerical stability of our algorithms, especially on  large-scale instances.
Robust Distance Metric Learning via Simultaneous L1-Norm Minimization and Maximization
Authors: Hua Wang, Feiping Nie, Heng Huang
Published in: Proceedings of the 31st International Conference on Machine Learning (Main Conference Track), 2014

Abstract: Traditional distance metric learning with side information usually formulates the objectives using the covariance matrices of the data point pairs in the two constraint sets of must-links and cannot-links. Because the covariance matrix computes the sum of the squared L2-norm distances, it is prone to both outlier samples and outlier features. To develop a robust distance metric learning method, in this paper we propose a new objective for distance metric learning using the L1-norm distances. However, the resulted objective is very challenging to solve, because it simultaneously minimizes and maximizes (minmax) a number of non-smooth L1-norm terms. As an important theoretical contribution of this paper, we systematically derive an efficient iterative algorithm to solve the general L1-norm minmax problem, which is rarely studied in literature. We have performed extensive empirical evaluations, where our new distance metric learning method outperforms related state-of-the-art methods in a variety of experimental settings to cluster both noiseless and noisy data.
Learning from Contagion (Without Timestamps)
Authors: Kareem Amin, Hoda Heidari, Michael Kearns
Published in: Proceedings of the 31st International Conference on Machine Learning (Main Conference Track), 2014

Abstract: We introduce and study new models for learning from contagion processes in a network. A learning algorithm is allowed to either choose or passively observe an initial set of seed infections. This seed set then induces a final set of infections resulting from the underlying stochastic contagion dynamics. Our models differ from prior work in that detailed vertex-by-vertex timestamps for the spread of the contagion are not observed. The goal of learning is to infer the unknown network structure. Our main theoretical results are efficient and provably correct algorithms for exactly learning trees. We provide empirical evidence that our algorithm performs well more generally on realistic sparse graphs.
Stochastic Variational Inference for Bayesian Time Series Models
Authors: Matthew Johnson, Alan Willsky
Published in: Proceedings of the 31st International Conference on Machine Learning (Main Conference Track), 2014

Abstract: Bayesian models provide powerful tools for analyzing complex time series data, but performing inference with large datasets is a challenge.  Stochastic variational inference (SVI) provides a new framework for approximating model posteriors with only a small number of passes through the data, enabling such models to be fit at scale.  However, its application to time series models has not been studied.    In this paper we develop SVI algorithms for several common Bayesian time series models, namely the hidden Markov model (HMM), hidden semi-Markov model (HSMM), and the nonparametric HDP-HMM and HDP-HSMM.  In addition, because HSMM inference can be expensive even in the minibatch setting of SVI, we develop fast approximate updates for HSMMs with durations distributions that are negative binomials or mixtures of negative binomials.
A Clockwork RNN
Authors: Jan Koutnik, Klaus Greff, Faustino Gomez, Juergen Schmidhuber
Published in: Proceedings of the 31st International Conference on Machine Learning (Main Conference Track), 2014

Abstract: Sequence prediction and classification are ubiquitous and challenging problems in machine learning that can require identifying complex dependencies between temporally distant inputs. Recurrent Neural Networks (RNNs) have the ability, in theory, to cope with these temporal dependencies by virtue of the short-term memory implemented by their recurrent (feedback) connections. However, in practice they are difficult to train successfully when long-term memory is  required.    This paper introduces a simple, yet powerful modification to the  simple RNN (SRN) architecture, the Clockwork RNN (CW-RNN), in which the hidden layer is partitioned into separate modules, each processing inputs at its own temporal granularity, making computations only at its prescribed clock rate.    Rather than making the standard RNN models more complex, CW-RNN  reduces the number of SRN parameters, improves the performance  significantly in the tasks tested, and speeds up the network evaluation.    The network is demonstrated in preliminary experiments involving three tasks: audio signal generation, TIMIT spoken word classification,  where it outperforms both SRN and LSTM networks, and online handwriting recognition, where it outperforms SRNs.
Estimating Latent-Variable Graphical Models using Moments and Likelihoods
Authors: Arun Tejasvi Chaganty, Percy Liang
Published in: Proceedings of the 31st International Conference on Machine Learning (Main Conference Track), 2014

Abstract: Recent work in method of moments provide consistent estimates for  latent-variable models, avoiding local optima issues, but these methods can  only be applied to certain types of graphical models. In this work, we show  that the method of moments in conjunction with a composite marginal likelihood  objective yields consistent parameter estimates for a much broader class of  directed and undirected graphical models, including loopy graphs with high  treewidth. Specifically, we use tensor factorization to reveal partial  information about the hidden variables, rendering the otherwise non-convex  negative log-likelihood convex. Our approach gracefully extends to models  outside our class by incorporating the partial information via posterior  regulraization.
Universal Matrix Completion
Authors: Srinadh Bhojanapalli, Prateek Jain
Published in: Proceedings of the 31st International Conference on Machine Learning (Main Conference Track), 2014

Abstract: The problem of low-rank matrix completion has recently generated a lot of interest leading to several results that offer exact solutions to the problem. However, in order to do so, these methods make assumptions that can be quite restrictive in practice. More specifically, the methods assume that: a) the observed indices are sampled uniformly at random, and b) for every new matrix, the observed indices are sampled \emphafresh. In this work, we address these issues by providing a universal recovery guarantee for matrix completion that works for a variety of sampling schemes. In particular, we show that if the set of sampled indices come from the edges of a bipartite graph with large spectral gap (i.e. gap between the first and the second singular value), then the nuclear norm minimization based method exactly recovers all low-rank matrices that satisfy certain incoherence properties.Moreover, we also show that under certain stricter incoherence conditions, O(nr^2) uniformly sampled entries are enough to recover any rank-r n\times n matrix, in contrast to the O(nrłog n) sample complexity required by other matrix completion algorithms as well as existing analyses of the nuclear norm method.
Finding Dense Subgraphs via Low-Rank Bilinear Optimization
Authors: Dimitris Papailiopoulos, Ioannis Mitliagkas, Alexandros Dimakis, Constantine Caramanis
Published in: Proceedings of the 31st International Conference on Machine Learning (Main Conference Track), 2014

Abstract: Given a graph, the Densest k-Subgraph (\DkS) problem asks for the subgraph on k vertices that contains the largest number of edges. In this work, we develop a novel algorithm for \DkS that searches a low-dimensional space for provably good solutions.  We obtain provable performance bounds that depend on the graph spectrum.  One of our results is that if there exists a k-subgraph that contains a constant fraction of all the edges, we can approximate \DkS within a factor arbitrarily close to two in polynomial time.     Our algorithm runs in nearly linear time, under spectral assumptions satisfied by   most graphs found in applications. Moreover, it is highly scalable and parallelizable.  We demonstrate this by implementing it in MapReduce and executing numerous experiments on  massive real-world graphs that have up to billions of edges.  We empirically show that our algorithm can find subgraphs of significantly higher density compared to the previous state of the art.
Compositional Morphology for Word Representations and Language Modelling
Authors: Jan Botha, Phil Blunsom
Published in: Proceedings of the 31st International Conference on Machine Learning (Main Conference Track), 2014

Abstract: This paper presents a scalable method for integrating compositional morphological representations into a vector-based probabilistic language model. Our approach is evaluated in the context of log-bilinear language models, rendered suitably efficient for implementation inside a machine translation decoder by factoring the vocabulary. We perform both intrinsic and extrinsic evaluations, presenting results on a range of languages which demonstrate that our model learns morphological representations that both perform well on word similarity tasks and lead to substantial reductions in perplexity. When used for translation into morphologically rich languages with large vocabularies, our models obtain improvements of up to 1.2 BLEU points relative to a baseline system using back-off n-gram models.
Learning Polynomials with Neural Networks
Authors: Alexandr Andoni, Rina Panigrahy, Gregory Valiant, Li Zhang
Published in: Proceedings of the 31st International Conference on Machine Learning (Main Conference Track), 2014

Abstract: We study the effectiveness of learning low degree polynomials using   neural networks by the gradient descent method.  While neural   networks have been shown to have great expressive power, and gradient   descent has been widely used in practice for learning neural   networks, few theoretical guarantees are known for such methods.  In   particular, it is well known that gradient descent can get stuck at   local minima, even for simple classes of target functions.  In this   paper, we present several positive theoretical results to support the   effectiveness of neural networks.  We focus on two-layer neural   networks (i.e. one hidden layer) where the top layer node is a linear   function, similar to i̧tebarron93.  First we show that for a   randomly initialized neural network with sufficiently many hidden   units, the gradient descent method can learn any low degree   polynomial.  Secondly, we show that if we use complex-valued weights   (the target function can still be real), then under suitable   conditions, there are no “robust local minima”: the neural network   can always escape a local minimum by performing a random   perturbation. This property does not hold for real-valued weights.   Thirdly, we discuss whether sparse polynomials can be learned   with \emphsmall neural networks, where the size is dependent on the   sparsity of the target function.
Exponential Family Matrix Completion under Structural Constraints
Authors: Suriya Gunasekar, Pradeep Ravikumar, Joydeep Ghosh
Published in: Proceedings of the 31st International Conference on Machine Learning (Main Conference Track), 2014

Abstract: We consider the matrix completion problem of recovering a structured matrix from noisy and partial measurements. Recent works have proposed tractable estimators with strong statistical guarantees for the case where the underlying matrix is low–rank, and the measurements consist of a subset, either of the exact individual entries,  or of the entries perturbed by additive Gaussian noise, which is thus implicitly suited for thin–tailed continuous data. Arguably, common applications of matrix completion require estimators for (a) heterogeneous data–types, such as skewed–continuous, count, binary, etc., (b) for heterogeneous noise models (beyond Gaussian), which capture varied uncertainty in the measurements, and (c) heterogeneous structural constraints beyond low–rank, such as block–sparsity, or a superposition structure of low–rank plus elementwise sparseness, among others. In this paper, we provide a vastly unified framework for generalized matrix completion by considering a  matrix completion setting wherein the matrix entries are sampled from any member of the rich family of \textitexponential family distributions; and impose general structural constraints on the underlying matrix, as captured by a general regularizer \mathcalR(.). We propose a simple convex regularized M–estimator for the generalized framework, and provide a unified and novel statistical analysis for this general class of estimators. We finally corroborate our theoretical results on simulated datasets.
Sample-based approximate regularization
Authors: Philip Bachman, Amir-Massoud Farahmand, Doina Precup
Published in: Proceedings of the 31st International Conference on Machine Learning (Main Conference Track), 2014

Abstract: We introduce a method for regularizing linearly parameterized functions using general derivative-based penalties, which relies on sampling as well as finite-difference approximations of the relevant derivatives. We call this approach sample-based approximate regularization (SAR). We provide theoretical guarantees on the fidelity of such regularizers, compared to those they approximate, and prove that the approximations converge efficiently. We also examine the empirical performance of SAR on several datasets.
A Compilation Target for Probabilistic Programming Languages
Authors: Brooks Paige, Frank Wood
Published in: Proceedings of the 31st International Conference on Machine Learning (Main Conference Track), 2014

Abstract: Forward inference techniques such as sequential Monte Carlo and particle Markov chain Monte Carlo for probabilistic programming can be implemented in any programming language by creative use of standardized operating system functionality including processes, forking, mutexes, and shared memory.   Exploiting this we have defined, developed, and tested a probabilistic programming language intermediate representation language we call probabilistic C, which itself can be compiled to machine code by standard compilers and linked to operating system libraries yielding an efficient, scalable, portable probabilistic programming compilation target.  This opens up a new hardware and systems research path for optimizing probabilistic programming systems.
Adaptive Monte Carlo via Bandit Allocation
Authors: James Neufeld, Andras Gyorgy, Csaba Szepesvari, Dale Schuurmans
Published in: Proceedings of the 31st International Conference on Machine Learning (Main Conference Track), 2014

Abstract: We consider the problem of sequentially choosing between a set of unbiased Monte Carlo estimators to minimize the mean-squared-error (MSE) of a final combined estimate. By reducing this task to a stochastic multi-armed bandit problem, we show that well developed allocation strategies can be used to achieve an MSE that approaches that of the best estimator chosen in retrospect. We then extend these developments to a scenario where alternative estimators have different, possibly stochastic, costs. The outcome is a new set of adaptive Monte Carlo strategies that provide stronger guarantees than previous approaches while offering practical advantages.
Efficient Dimensionality Reduction for High-Dimensional Network Estimation
Authors: Safiye Celik, Benjamin Logsdon, Su-In Lee
Published in: Proceedings of the 31st International Conference on Machine Learning (Main Conference Track), 2014

Abstract: We propose module graphical lasso (MGL), an aggressive dimensionality reduction and network estimation technique for a high-dimensional Gaussian graphical model (GGM). MGL achieves scalability, interpretability and robustness by exploiting the modularity property of many real-world networks. Variables are organized into tightly coupled modules and a graph structure is estimated to determine the conditional independencies among modules. MGL iteratively learns the module assignment of variables, the latent variables, each corresponding to a module, and the parameters of the GGM of the latent variables. In synthetic data experiments, MGL outperforms the standard graphical lasso and three other methods that incorporate latent variables into GGMs. When applied to gene expression data from ovarian cancer, MGL outperforms standard clustering algorithms in identifying functionally coherent gene sets and predicting survival time of patients. The learned modules and their dependencies provide novel insights into cancer biology as well as identifying possible novel drug targets.
Deterministic Anytime Inference for Stochastic Continuous-Time Markov Processes
Authors: E. Busra Celikkaya, Christian Shelton
Published in: Proceedings of the 31st International Conference on Machine Learning (Main Conference Track), 2014

Abstract: We describe a deterministic anytime method for calculating  filtered and smoothed distributions in large variable-based continuous time  Markov processes.  Prior non-random algorithms do not converge to the true  distribution in the limit of infinite computation time.  Sampling  algorithms give different results each time run, which can lead to  instability when used inside expectation-maximization or other algorithms.  Our method combines the anytime convergent properties of sampling with the  non-random nature of variational approaches.  It is built upon a sum of  time-ordered products, an expansion of the matrix exponential.  We  demonstrate that our method performs as well as or better than the current  best sampling approaches on benchmark problems.
Doubly Stochastic Variational Bayes for non-Conjugate Inference
Authors: Michalis Titsias, Miguel Lázaro-Gredilla
Published in: Proceedings of the 31st International Conference on Machine Learning (Main Conference Track), 2014

Abstract: We propose a simple and effective variational inference algorithm based on stochastic optimisation   that can be widely applied for Bayesian non-conjugate inference in continuous parameter spaces. This algorithm is based on stochastic approximation and allows for efficient use of gradient information from the model joint density. We demonstrate these properties using illustrative examples as well as in challenging and diverse Bayesian inference   problems such as variable selection in logistic regression and fully   Bayesian inference over kernel hyperparameters in Gaussian process regression.
Efficient Learning of Mahalanobis Metrics for Ranking
Authors: Daryl Lim, Gert Lanckriet
Published in: Proceedings of the 31st International Conference on Machine Learning (Main Conference Track), 2014

Abstract: We develop an efficient algorithm to learn a Mahalanobis distance metric by directly optimizing a ranking loss.  Our approach focuses on optimizing the top of the induced rankings, which is desirable in tasks such as visualization and nearest-neighbor retrieval.  We further develop and justify a simple technique to reduce training time significantly with minimal impact on performance.   Our proposed method significantly outperforms alternative methods on several real-world tasks, and can scale to large and high-dimensional data.
GEV-Canonical Regression for Accurate Binary Class Probability Estimation when One Class is Rare
Authors: Arpit Agarwal, Harikrishna Narasimhan, Shivaram Kalyanakrishnan, Shivani Agarwal
Published in: Proceedings of the 31st International Conference on Machine Learning (Main Conference Track), 2014

Abstract: We consider the problem of binary class probability estimation (CPE) when one class is rare compared to the other. It is well known that standard algorithms such as logistic regression do not perform well on this task as they tend to under-estimate the probability of the rare class. Common fixes include under-sampling and weighting, together with various correction schemes. Recently, Wang & Dey (2010) suggested the use of a parametrized family of asymmetric link functions based on the generalized extreme value (GEV) distribution, which has been used for modeling rare events in statistics. The approach showed promising initial results, but combined with the logarithmic CPE loss implicitly used in their work, it results in a non-convex composite loss that is difficult to optimize. In this paper, we use tools from the theory of proper composite losses (Buja et al, 2005; Reid & Williamson, 2010) to construct a canonical underlying CPE loss corresponding to the GEV link, which yields a convex proper composite loss that we call the GEV-canonical loss; this loss is tailored for the task of CPE when one class is rare, and is easy to minimize using an IRLS-type algorithm similar to that used for logistic regression. Our experiments on both synthetic and real data demonstrate that the resulting algorithm – which we term GEV-canonical regression – outperforms common approaches such as under-sampling and weights correction for this problem.
A reversible infinite HMM using normalised random measures
Authors: David Knowles, Zoubin Ghahramani, Konstantina Palla
Published in: Proceedings of the 31st International Conference on Machine Learning (Main Conference Track), 2014

Abstract: We present a nonparametric prior over reversible Markov chains. We use completely random measures, specifically gamma processes, to construct a countably infinite graph with weighted edges.  By enforcing symmetry to make the edges undirected we define a prior over random walks on graphs that results in a reversible Markov chain. The resulting prior over infinite transition matrices is closely related to the hierarchical Dirichlet process but enforces reversibility. A reinforcement scheme has recently been proposed with similar properties, but the de Finetti measure is not well characterised. We take the alternative approach of explicitly constructing the mixing measure, which allows more straightforward and efficient inference at the cost of no longer having a closed form predictive distribution. We use our process to construct a reversible infinite HMM which we apply to two real datasets, one from epigenomics and one ion channel recording.
Structured Low-Rank Matrix Factorization: Optimality, Algorithm, and Applications to Image Processing
Authors: Benjamin Haeffele, Eric Young, Rene Vidal
Published in: Proceedings of the 31st International Conference on Machine Learning (Main Conference Track), 2014

Abstract: Recently, convex solutions to low-rank matrix factorization problems have received increasing attention in machine learning. However, in many applications the data can display other structures beyond simply being low-rank. For example, images and videos present complex spatio-temporal structures, which are largely ignored by current low-rank methods. In this paper we explore a matrix factorization technique suitable for large datasets that captures additional structure in the factors by using a projective tensor norm, which includes classical image regularizers such as total variation and the nuclear norm as particular cases. Although the resulting optimization problem is not convex, we show that under certain conditions on the factors, any local minimizer for the factors yields a global minimizer for their product. Examples in biomedical video segmentation and hyperspectral compressed recovery show the advantages of our approach on high-dimensional datasets.
Influence Function Learning in Information Diffusion Networks
Authors: Nan Du, Yingyu Liang, Maria Balcan, Le Song
Published in: Proceedings of the 31st International Conference on Machine Learning (Main Conference Track), 2014

Abstract: Can we learn the influence of a set of people in a social network from cascades of information diffusion? This question is often addressed by a two-stage approach: first learn a diffusion model, and then calculate the influence based on the learned model. Thus, the success of this approach relies heavily on the correctness of the diffusion model which is hard to verify for real world data. In this paper, we exploit the insight that the influence functions in many diffusion models are coverage functions, and propose a novel parameterization of such functions using a convex combination of random basis functions. Moreover, we propose an efficient maximum likelihood based algorithm to learn such functions directly from cascade data, and hence bypass the need to specify a particular diffusion model in advance. We provide both theoretical and empirical analysis for our approach, showing that the proposed approach can provably learn the influence function with low sample complexity, be robust to the unknown diffusion models, and significantly outperform existing approaches in both synthetic and real world data.
Selective Dyna-Style Planning Under Limited Model Capacity
Authors: Zaheer Abbas, Samuel Sokota, Erin Talvitie, Martha White
Published in: Proceedings of the 37th International Conference on Machine Learning (Main Conference Track), 2020

Abstract: In model-based reinforcement learning, planning with an imperfect model of the environment has the potential to harm learning progress. But even when a model is imperfect, it may still contain information that is useful for planning. In this paper, we investigate the idea of using an imperfect model selectively. The agent should plan in parts of the state space where the model would be helpful but refrain from using the model where it would be harmful. An effective selective planning mechanism requires estimating predictive uncertainty, which arises out of aleatoric uncertainty, parameter uncertainty, and model inadequacy, among other sources. Prior work has focused on parameter uncertainty for selective planning. In this work, we emphasize the importance of model inadequacy. We show that heteroscedastic regression can signal predictive uncertainty arising from model inadequacy that is complementary to that which is detected by methods designed for parameter uncertainty, indicating that considering both parameter uncertainty and model inadequacy may be a more promising direction for effective selective planning than either in isolation.
A distributional view on multi-objective policy optimization
Authors: Abbas Abdolmaleki, Sandy Huang, Leonard Hasenclever, Michael Neunert, Francis Song, Martina Zambelli, Murilo Martins, Nicolas Heess, Raia Hadsell, Martin Riedmiller
Published in: Proceedings of the 37th International Conference on Machine Learning (Main Conference Track), 2020

Abstract: Many real-world problems require trading off multiple competing objectives. However, these objectives are often in different units and/or scales, which can make it challenging for practitioners to express numerical preferences over objectives in their native units. In this paper we propose a novel algorithm for multi-objective reinforcement learning that enables setting desired preferences for objectives in a scale-invariant way. We propose to learn an action distribution for each objective, and we use supervised learning to fit a parametric policy to a combination of these distributions. We demonstrate the effectiveness of our approach on challenging high-dimensional real and simulated robotics tasks, and show that setting different preferences in our framework allows us to trace out the space of nondominated solutions.
Efficient Optimistic Exploration in Linear-Quadratic Regulators via Lagrangian Relaxation
Authors: Marc Abeille, Alessandro Lazaric
Published in: Proceedings of the 37th International Conference on Machine Learning (Main Conference Track), 2020

Abstract: We study the exploration-exploitation dilemma in the linear quadratic regulator (LQR) setting. Inspired by the extended value iteration algorithm used in optimistic algorithms for finite MDPs, we propose to relax the optimistic optimization of øfulq and cast it into a constrained \emphextended LQR problem, where an additional control variable implicitly selects the system dynamics within a confidence interval. We then move to the corresponding Lagrangian formulation for which we prove strong duality. As a result, we show that an $ε$-optimistic controller can be computed efficiently by solving at most $O\big(łog(1/ε)\big)$ Riccati equations. Finally, we prove that relaxing the original øfu problem does not impact the learning performance, thus recovering the $\wt O(\sqrtT)$ regret of øfulq. To the best of our knowledge, this is the first computationally efficient confidence-based algorithm for LQR with worst-case optimal regret guarantees.
Super-efficiency of automatic differentiation for functions defined as a minimum
Authors: Pierre Ablin, Gabriel Peyré, Thomas Moreau
Published in: Proceedings of the 37th International Conference on Machine Learning (Main Conference Track), 2020

Abstract: In min-min optimization or max-min optimization, one has to compute the gradient of a function defined as a minimum. In most cases, the minimum has no closed-form, and an approximation is obtained via an iterative algorithm. There are two usual ways of estimating the gradient of the function: using either an analytic formula obtained by assuming exactness of the approximation, or automatic differentiation through the algorithm. In this paper, we study the asymptotic error made by these estimators as a function of the optimization error. We find that the error of the automatic estimator is close to the square of the error of the analytic estimator, reflecting a super-efficiency phenomenon. The convergence of the automatic estimator greatly depends on the convergence of the Jacobian of the algorithm. We analyze it for gradient descent and stochastic gradient descent and derive convergence rates for the estimators in these cases. Our analysis is backed by numerical experiments on toy problems and on Wasserstein barycenter computation. Finally, we discuss the computational complexity of these estimators and give practical guidelines to chose between them.
A Geometric Approach to Archetypal Analysis via Sparse Projections
Authors: Vinayak Abrol, Pulkit Sharma
Published in: Proceedings of the 37th International Conference on Machine Learning (Main Conference Track), 2020

Abstract: Archetypal analysis (AA) aims to extract patterns using self-expressive decomposition of data as convex combinations of extremal points (on the convex hull) of the data. This work presents a computationally efficient greedy AA (GAA) algorithm. GAA leverages the underlying geometry of AA, is scalable to larger datasets, and has significantly faster convergence rate. To achieve this, archetypes are learned via sparse projection of data. In the transformed space, GAA employs an iterative subset selection approach to identify archetypes based on the sparsity of convex representations. The work further presents the use of GAA algorithm for extended AA models such as robust and kernel AA. Experimental results show that GAA is considerably faster while performing comparable to existing methods for tasks such as classification, data visualization/categorization.
Context Aware Local Differential Privacy
Authors: Jayadev Acharya, Kallista Bonawitz, Peter Kairouz, Daniel Ramage, Ziteng Sun
Published in: Proceedings of the 37th International Conference on Machine Learning (Main Conference Track), 2020

Abstract: Local differential privacy (LDP) is a strong notion of privacy that often leads to a significant drop in utility. The original definition of LDP assumes that all the elements in the data domain are equally sensitive. However, in many real-life applications, some elements are more sensitive than others. We propose a context-aware framework for LDP that allows the privacy level to vary across the data domain, enabling system designers to place privacy constraints where they matter without paying the cost where they do not. For binary data domains, we provide a universally optimal privatization scheme and highlight its connections to Warner’s randomized response and Mangat’s improved response. Motivated by geo-location and web search applications, for k-ary data domains, we consider two special cases of context-aware LDP: block-structured LDP and high-low LDP. We study minimax discrete distribution estimation under both cases and provide communication-efficient, sample-optimal schemes, and information-theoretic lower bounds. We show, using worst-case analyses and experiments on Gowalla’s 3.6 million check-ins to 43,750 locations, that context-aware LDP achieves a far better accuracy under the same number of samples.
Efficient Intervention Design for Causal Discovery with Latents
Authors: Raghavendra Addanki, Shiva Kasiviswanathan, Andrew Mcgregor, Cameron Musco
Published in: Proceedings of the 37th International Conference on Machine Learning (Main Conference Track), 2020

Abstract: We consider recovering a causal graph in presence of latent variables, where we seek to minimize the cost of interventions used in the recovery process. We consider two intervention cost models: (1) a linear cost model where the cost of an intervention on a subset of variables has a linear form, and (2) an identity cost model where the cost of an intervention is the same, regardless of what variables it is on, i.e., the goal is just to minimize the number of interventions. Under the linear cost model, we give an algorithm to identify the ancestral relations of the underlying causal graph, achieving within a $2$-factor of the optimal intervention cost. This approximation factor can be improved to $1+\eps$ for any $\eps > 0$ under some mild restrictions. Under the identity cost model, we bound the number of interventions needed to recover the entire causal graph, including the latent variables, using a parameterization of the causal graph through a special type of colliders. In particular, we introduce the notion of $p$-colliders, that are colliders between pair of nodes arising from a specific type of conditioning in the causal graph, and provide an upper bound on the number of interventions as a function of the maximum number of $p$-colliders between any two nodes in the causal graph.
The Neural Tangent Kernel in High Dimensions: Triple Descent and a Multi-Scale Theory of Generalization
Authors: Ben Adlam, Jeffrey Pennington
Published in: Proceedings of the 37th International Conference on Machine Learning (Main Conference Track), 2020

Abstract: Modern deep learning models employ considerably more parameters than required to fit the training data. Whereas conventional statistical wisdom suggests such models should drastically overfit, in practice these models generalize remarkably well. An emerging paradigm for describing this unexpected behavior is in terms of a \emphdouble descent curve, in which increasing a model’s capacity causes its test error to first decrease, then increase to a maximum near the interpolation threshold, and then decrease again in the overparameterized regime. Recent efforts to explain this phenomenon theoretically have focused on simple settings, such as linear regression or kernel regression with unstructured random features, which we argue are too coarse to reveal important nuances of actual neural networks. We provide a precise high-dimensional asymptotic analysis of generalization under kernel regression with the Neural Tangent Kernel, which characterizes the behavior of wide neural networks optimized with gradient descent. Our results reveal that the test error has nonmonotonic behavior deep in the overparameterized regime and can even exhibit additional peaks and descents when the number of parameters scales quadratically with the dataset size.
Rank Aggregation from Pairwise Comparisons in the Presence of Adversarial Corruptions
Authors: Arpit Agarwal, Shivani Agarwal, Sanjeev Khanna, Prathamesh Patil
Published in: Proceedings of the 37th International Conference on Machine Learning (Main Conference Track), 2020

Abstract: Rank aggregation from pairwise preferences has widespread applications in recommendation systems and information retrieval. Given the enormous economic and societal impact of these applications, and the consequent incentives for malicious players to manipulate ranking outcomes in their favor, an important challenge is to make rank aggregation algorithms robust to adversarial manipulations in data. In this paper, we initiate the study of robustness in rank aggregation under the popular Bradley-Terry-Luce (BTL) model for pairwise comparisons. We consider a setting where pairwise comparisons are initially generated according to a BTL model, but a fraction of these comparisons are corrupted by an adversary prior to being reported to us. We consider a strong contamination model, where an adversary having complete knowledge of the initial truthful data and the underlying true BTL parameters, can subsequently corrupt the truthful data by inserting, deleting, or changing data points. The goal is to estimate the true score/weight of each item under the BTL model, even in the presence of these corruptions. We characterize the extent of adversarial corruption under which the true BTL parameters are uniquely identifiable. We also provide a novel pruning algorithm that provably cleans the data of adversarial corruption under reasonable conditions on data generation and corruption. We corroborate our theory with experiments on both synthetic as well as real data showing that previous algorithms are vulnerable to even small amounts of corruption, whereas our algorithm can clean a reasonably high amount of corruption.
Boosting for Control of Dynamical Systems
Authors: Naman Agarwal, Nataly Brukhim, Elad Hazan, Zhou Lu
Published in: Proceedings of the 37th International Conference on Machine Learning (Main Conference Track), 2020

Abstract: We study the question of how to aggregate controllers for dynamical systems in order to improve their performance. To this end, we propose a framework of boosting for online control. Our main result is an efficient boosting algorithm that combines weak controllers into a provably more accurate one. Empirical evaluation on a host of control settings supports our theoretical findings.