mtybilly/Instruct2DS huggingface dataset:
Taming the Monster: A Fast and Simple Algorithm for Contextual Bandits
Authors: Agarwal, Alekh and Hsu, Daniel and Kale, Satyen and Langford, John and Li, Lihong and Schapire, Robert
Published in: Proceedings of the 31st International Conference on Machine Learning (Main Conference Track), 2014

Abstract: We present a new algorithm for the contextual bandit learning problem,  where the learner repeatedly takes one of K \emphactions in response to the  observed \emphcontext, and observes the \emphreward only for that  action. Our method assumes access to an oracle for solving fully  supervised cost-sensitive classification problems and achieves the  statistically optimal regret guarantee with only øtil(\sqrtKT)  oracle calls across all T rounds. By doing so, we obtain the most  practical contextual bandit learning algorithm amongst approaches that  work for general policy classes.  We conduct a  proof-of-concept experiment which demonstrates the excellent  computational and statistical performance of (an online variant of) our  algorithm relative to several strong baselines.
Structured Recurrent Temporal Restricted Boltzmann Machines
Authors: Mittelman, Roni and Kuipers, Benjamin and Savarese, Silvio and Lee, Honglak
Published in: Proceedings of the 31st International Conference on Machine Learning (Main Conference Track), 2014

Abstract: The Recurrent temporal restricted Boltzmann machine (RTRBM) is a probabilistic model for temporal data, that has been shown to effectively capture both short and long-term dependencies in time-series. The topology of the RTRBM graphical model, however, assumes full connectivity between all the pairs of visible and hidden units, therefore ignoring the dependency structure between the different observations. Learning this structure has the potential to not only improve the prediction performance, but it can also reveal important patterns in the data. For example, given an econometric dataset, we could identify interesting dependencies between different market sectors; given a meteorological dataset, we could identify regional weather patterns. In this work we propose a new class of RTRBM, which explicitly uses a dependency graph to model the structure in the problem and to define the energy function. We refer to the new model as the structured RTRBM (SRTRBM). Our technique is related to methods such as graphical lasso, which are used to learn the topology of Gaussian graphical models. We also develop a spike-and-slab version of the RTRBM, and combine it with our method to learn structure in datasets with real valued observations. Our experimental results using synthetic and real datasets, demonstrate that the SRTRBM can improve the prediction performance of the RTRBM, particularly when the number of visible units is large and the size of the training set is small. It also reveals the structure underlying our benchmark datasets.
Scalable and Robust Bayesian Inference via the Median Posterior
Authors: Minsker, Stanislav and Srivastava, Sanvesh and Lin, Lizhen and Dunson, David
Published in: Proceedings of the 31st International Conference on Machine Learning (Main Conference Track), 2014

Abstract: Many Bayesian learning methods for massive data benefit from working with small subsets of observations.  In particular, significant progress has been made in scalable Bayesian learning via stochastic approximation.  However, Bayesian learning methods in distributed computing environments are often problem- or distribution-specific and use ad hoc techniques.   We propose a novel general approach to Bayesian inference that is scalable and robust to corruption in the data.  Our technique is based on the idea of splitting the data into several non-overlapping subgroups, evaluating the posterior distribution given each independent subgroup, and then combining the results.  The main novelty is the proposed aggregation step which is based on finding the geometric median of posterior distributions.    We present both theoretical and numerical results illustrating the advantages of our approach.
Kernel Adaptive Metropolis-Hastings
Authors: Sejdinovic, Dino and Strathmann, Heiko and Garcia, Maria Lomeli and Andrieu, Christophe and Gretton, Arthur
Published in: Proceedings of the 31st International Conference on Machine Learning (Main Conference Track), 2014

Abstract: A Kernel Adaptive Metropolis-Hastings algorithm is introduced, for the purpose of sampling from a target distribution with strongly nonlinear support. The algorithm embeds the trajectory of the Markov chain into a reproducing kernel Hilbert space (RKHS), such that the feature space covariance of the samples informs the choice of proposal. The procedure is computationally efficient and straightforward to implement, since the RKHS moves can be integrated out analytically: our proposal distribution in the original space is a normal distribution whose mean and covariance depend on where the current sample lies in the support of the target distribution, and adapts to its local covariance structure. Furthermore, the procedure requires neither gradients nor any other higher order information about the target, making it particularly attractive for contexts such as Pseudo-Marginal MCMC. Kernel Adaptive Metropolis-Hastings outperforms competing fixed and adaptive samplers on multivariate, highly nonlinear target distributions, arising in both real-world and synthetic examples.
Input Warping for Bayesian Optimization of Non-Stationary Functions
Authors: Snoek, Jasper and Swersky, Kevin and Zemel, Rich and Adams, Ryan
Published in: Proceedings of the 31st International Conference on Machine Learning (Main Conference Track), 2014

Abstract: Bayesian optimization has proven to be a highly effective methodology for the global optimization of unknown, expensive and multimodal functions.  The ability to accurately model distributions over functions is critical to the effectiveness of Bayesian optimization.  Although Gaussian processes provide a flexible prior over functions, there are various classes of functions that remain difficult to model.  One of the most frequently occurring of these is the class of non-stationary functions.  The optimization of the hyperparameters of machine learning algorithms is a problem domain in which parameters are often manually transformed a priori, for example by optimizing in "log-space", to mitigate the effects of spatially-varying length scale.  We develop a methodology for automatically learning a wide family of bijective transformations or warpings of the input space using the Beta cumulative distribution function.  We further extend the warping framework to multi-task Bayesian optimization so that multiple tasks can be warped into a jointly stationary space. On a set of challenging benchmark optimization tasks, we observe that the inclusion of warping greatly improves on the state-of-the-art, producing better results faster and more reliably.
Stochastic Gradient Hamiltonian Monte Carlo
Authors: Chen, Tianqi and Fox, Emily and Guestrin, Carlos
Published in: Proceedings of the 31st International Conference on Machine Learning (Main Conference Track), 2014

Abstract: Hamiltonian Monte Carlo (HMC) sampling methods provide a mechanism for defining distant proposals with high acceptance probabilities in a Metropolis-Hastings framework, enabling more efficient exploration of the state space than standard random-walk proposals.  The popularity of such methods has grown significantly in recent years.  However, a limitation of HMC methods is the required gradient computation for simulation of the Hamiltonian dynamical system-such computation is infeasible in problems involving a large sample size or streaming data. Instead, we must rely on a noisy gradient estimate computed from a subset of the data.  In this paper, we explore the properties of such a stochastic gradient HMC approach. Surprisingly, the natural implementation of the stochastic approximation can be arbitrarily bad.  To address this problem we introduce a variant that uses second-order Langevin dynamics with a friction term that counteracts the effects of the noisy gradient, maintaining the desired target distribution as the invariant distribution.  Results on simulated data validate our theory.  We also provide an application of our methods to a classification task using neural networks and to online Bayesian matrix factorization.
A Deep Semi-NMF Model for Learning Hidden Representations
Authors: Trigeorgis, George and Bousmalis, Konstantinos and Zafeiriou, Stefanos and Schuller, Bjoern
Published in: Proceedings of the 31st International Conference on Machine Learning (Main Conference Track), 2014

Abstract: Semi-NMF is a matrix factorization technique that learns a low-dimensional representation of a dataset that lends itself to a clustering interpretation. It is possible that the mapping between this new representation and our original features contains rather complex hierarchical information with implicit lower-level hidden attributes, that classical one level clustering methodologies can not interpret. In this work we propose a novel model, Deep Semi-NMF, that is able to learn such hidden representations that allow themselves to an interpretation of clustering  according to different, unknown attributes of a given dataset. We show that by doing so, our model is able to learn low-dimensional representations that are better suited for clustering, outperforming Semi-NMF, but also other NMF variants.
Asynchronous Distributed ADMM for Consensus Optimization
Authors: Zhang, Ruiliang and Kwok, James
Published in: Proceedings of the 31st International Conference on Machine Learning (Main Conference Track), 2014

Abstract: Distributed optimization algorithms are highly attractive for solving big data problems. In particular, many machine learning problems can be formulated as the global consensus optimization problem, which can then be solved in a distributed manner by the alternating direction method of multipliers (ADMM) algorithm. However, this suffers from the straggler problem as its updates have to be synchronized. In this paper, we propose an asynchronous ADMM algorithm by using two conditions to control the asynchrony: partial barrier and bounded delay. The proposed algorithm has a simple structure and good convergence guarantees (its convergence rate can be reduced to that of its synchronous counterpart). Experiments on different distributed ADMM applications show that asynchrony reduces the time on network waiting, and achieves faster convergence than its synchronous counterpart in terms of the wall clock time.
Spectral Regularization for Max-Margin Sequence Tagging
Authors: Quattoni, Ariadna and Balle, Borja and Carreras, Xavier and Globerson, Amir
Published in: Proceedings of the 31st International Conference on Machine Learning (Main Conference Track), 2014

Abstract: We frame max-margin learning of latent variable structured prediction models as a convex optimization problem, making use of scoring functions computed by input-output observable operator models. This learning problem can be expressed as an optimization involving a low-rank Hankel matrix that represents the input-output operator model. The direct outcome of our work is a new spectral regularization method for max-margin structured prediction.  Our experiments confirm that our proposed regularization framework leads to an effective way of controlling the capacity of structured prediction models.
Learning by Stretching Deep Networks
Authors: Pandey, Gaurav and Dukkipati, Ambedkar
Published in: Proceedings of the 31st International Conference on Machine Learning (Main Conference Track), 2014

Abstract: In recent years, deep architectures have gained a lot of prominence for learning complex AI tasks  because of their capability to incorporate complex variations in data within the model. However, these models often need to be trained for a long time in order to obtain good results. In this paper, we propose a technique, called ‘stretching’, that allows the same models to perform considerably better with very little training.  We show that learning can be done tractably, even when the weight matrix is stretched to infinity, for some specific models. We also study tractable algorithms for implementing stretching in deep convolutional architectures in an iterative manner and derive bounds for its convergence. Our experimental results suggest that the proposed stretched deep convolutional networks are capable of achieving good performance for many object recognition tasks. More importantly, for a fixed network architecture, one can achieve much better accuracy using stretching rather than learning the weights using backpropagation.
Nonnegative Sparse PCA with Provable Guarantees
Authors: Asteris, Megasthenis and Papailiopoulos, Dimitris and Dimakis, Alexandros
Published in: Proceedings of the 31st International Conference on Machine Learning (Main Conference Track), 2014

Abstract: We introduce a novel algorithm to compute nonnegative sparse principal components of positive semidefinite (PSD) matrices. Our algorithm comes with approximation guarantees   contingent on the spectral profile of the input matrix A:  the sharper the eigenvalue decay, the better the approximation quality.    If the eigenvalues decay like any asymptotically vanishing function, we can approximate nonnegative sparse PCA within any accuracy εin time polynomial in the matrix size n and desired sparsity k, but not in 1/ε. Further, we obtain a data-dependent bound that is computed by executing an algorithm on a given data set. This bound is significantly tighter than a-priori bounds and can be used to show that for all tested datasets our algorithm is provably within 40%-90% from the unknown optimum.     Our algorithm is combinatorial and explores a subspace defined by the leading eigenvectors of A. We test our scheme on several data sets, showing that it matches or outperforms the previous state of the art.
Active Learning of Parameterized Skills
Authors: Silva, Bruno Da and Konidaris, George and Barto, Andrew
Published in: Proceedings of the 31st International Conference on Machine Learning (Main Conference Track), 2014

Abstract: We introduce a method for actively learning parameterized skills. Parameterized skills are flexible behaviors that can solve any task drawn from a distribution of parameterized reinforcement learning problems. Approaches to learning such skills have been proposed, but limited attention has been given to identifying which training tasks allow for rapid skill acquisition. We construct a non-parametric Bayesian model of skill performance and derive analytical expressions for a novel acquisition criterion capable of identifying tasks that maximize expected improvement in skill performance. We also introduce a spatiotemporal kernel tailored for non-stationary skill performance models. The proposed method is agnostic to policy and skill representation and scales independently of task dimensionality. We evaluate it on a non-linear simulated catapult control problem over arbitrarily mountainous terrains.
Learning Ordered Representations with Nested Dropout
Authors: Rippel, Oren and Gelbart, Michael and Adams, Ryan
Published in: Proceedings of the 31st International Conference on Machine Learning (Main Conference Track), 2014

Abstract: In this paper, we present results on ordered representations of data in which different dimensions have different degrees of importance. To learn these representations we introduce nested dropout, a procedure for stochastically removing coherent nested sets of hidden units in a neural network. We first present a sequence of theoretical results in the simple case of a semi-linear autoencoder.  We rigorously show that the application of nested dropout enforces identifiability of the units, which leads to an exact equivalence with PCA.  We then extend the algorithm to deep models and demonstrate the relevance of ordered representations to a number of applications.  Specifically, we use the ordered property of the learned codes to construct hash-based data structures that permit very fast retrieval, achieving retrieval in time logarithmic in the database size and independent of the dimensionality of the representation. This allows the use of codes that are hundreds of times longer than currently feasible for retrieval.  We therefore avoid the diminished quality associated with short codes, while still performing retrieval that is competitive in speed with existing methods.  We also show that ordered representations are a promising way to learn adaptive compression for efficient online data reconstruction.
Learning the Irreducible Representations of Commutative Lie Groups
Authors: Cohen, Taco and Welling, Max
Published in: Proceedings of the 31st International Conference on Machine Learning (Main Conference Track), 2014

Abstract: We present a new probabilistic model of compact commutative Lie groups that produces invariant-equivariant and disentangled representations of data. To define the notion of disentangling, we borrow a fundamental principle from physics that is used to derive the elementary particles of a system from its symmetries. Our model employs a newfound Bayesian conjugacy relation that enables fully tractable probabilistic inference over compact commutative Lie groups – a class that includes the groups that describe the rotation and cyclic translation of images. We train the model on pairs of transformed image patches, and show that the learned invariant representation is highly effective for classification.
Towards End-To-End Speech Recognition with Recurrent Neural Networks
Authors: Graves, Alex and Jaitly, Navdeep
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: Hu, Jinli and Storkey, Amos
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: Kingma, Diederik and Welling, Max
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: Mnih, Andriy and Gregor, Karol
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: Rai, Piyush and Wang, Yingjian and Guo, Shengbo and Chen, Gary and Dunson, David and Carin, Lawrence
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: Heaukulani, Creighton and Knowles, David and Ghahramani, Zoubin
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: Santos, Cicero Dos and Zadrozny, Bianca
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: Yu, Adams Wei and Kilinc-Karzan, Fatma and Carbonell, Jaime
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: Wang, Hua and Nie, Feiping and Huang, Heng
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: Amin, Kareem and Heidari, Hoda and Kearns, Michael
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: Johnson, Matthew and Willsky, Alan
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: Koutnik, Jan and Greff, Klaus and Gomez, Faustino and Schmidhuber, Juergen
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: Chaganty, Arun Tejasvi and Liang, Percy
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: Bhojanapalli, Srinadh and Jain, Prateek
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: Papailiopoulos, Dimitris and Mitliagkas, Ioannis and Dimakis, Alexandros and Caramanis, Constantine
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: Botha, Jan and Blunsom, Phil
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: Andoni, Alexandr and Panigrahy, Rina and Valiant, Gregory and Zhang, Li
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: Gunasekar, Suriya and Ravikumar, Pradeep and Ghosh, Joydeep
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: Bachman, Philip and Farahmand, Amir-Massoud and Precup, Doina
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: Paige, Brooks and Wood, Frank
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: Neufeld, James and Gyorgy, Andras and Szepesvari, Csaba and Schuurmans, Dale
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: Celik, Safiye and Logsdon, Benjamin and Lee, Su-In
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: Celikkaya, E. Busra and Shelton, Christian
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: Titsias, Michalis and Lázaro-Gredilla, Miguel
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: Lim, Daryl and Lanckriet, Gert
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: Agarwal, Arpit and Narasimhan, Harikrishna and Kalyanakrishnan, Shivaram and Agarwal, Shivani
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.