mtybilly/Instruct2DS huggingface dataset:
A non-IID Framework for Collaborative Filtering with Restricted Boltzmann Machines
Authors: Georgiev, Kostadin and Nakov, Preslav
Published in: Proceedings of the 30th International Conference on Machine Learning (Main Conference Track), 2013

Abstract: We propose a framework for collaborative filtering based on Restricted Boltzmann Machines (RBM), which extends previous RBM-based approaches in several important directions. First, while previous RBM research has focused on modeling the correlation between item ratings, we model both user-user and item-item correlations in a unified hybrid non-IID framework. We further use real values in the visible layer as opposed to multinomial variables, thus taking advantage of the natural order between user-item ratings. Finally, we explore the potential of combining the original training data with data generated by the RBM-based model itself in a bootstrapping fashion. The evaluation on two MovieLens datasets (with 100K and 1M user-item ratings, respectively), shows that our RBM model rivals the best previously-proposed approaches.
Intersecting singularities for multi-structured estimation
Authors: Richard, Emile and BACH, Francis and Vert, Jean-Philippe
Published in: Proceedings of the 30th International Conference on Machine Learning (Main Conference Track), 2013

Abstract: We address the problem of designing a convex nonsmooth regularizer encouraging multiple structural effects simultaneously. Focusing on the inference of sparse and low-rank matrices we suggest a new complexity index and a convex penalty approximating it. The new penalty term can be written as the trace norm of a linear function of the matrix. By analyzing theoretical properties of this family of regularizers  we come up with oracle inequalities and compressed sensing results ensuring the quality of our regularized estimator. We also provide algorithms and supporting numerical experiments.
Structure Discovery in Nonparametric Regression through Compositional Kernel Search
Authors: Duvenaud, David and Lloyd, James and Grosse, Roger and Tenenbaum, Joshua and Zoubin, Ghahramani
Published in: Proceedings of the 30th International Conference on Machine Learning (Main Conference Track), 2013

Abstract: Despite its importance, choosing the structural form of the kernel in nonparametric regression remains a black art. We define a space of kernel structures which are built compositionally by adding and multiplying a small number of base kernels. We present a method for searching over this space of structures which mirrors the scientific discovery process. The learned structures can often decompose functions into interpretable components and enable long-range extrapolation on time-series datasets. Our structure search method outperforms many widely used kernels and kernel combination methods on a variety of prediction tasks.
Copy or Coincidence? A Model for Detecting Social Influence and Duplication Events
Authors: Friedland, Lisa and Jensen, David and Lavine, Michael
Published in: Proceedings of the 30th International Conference on Machine Learning (Main Conference Track), 2013

Abstract: In this paper, we analyze the task of inferring rare links between pairs of entities that seem too similar to have occurred by chance. Variations of this task appear in such diverse areas as social network analysis, security, fraud detection, and entity resolution. To address the task in a general form, we propose a simple, flexible mixture model in which most entities are generated independently from a distribution but a small number of pairs are constrained to be similar. We predict the true pairs using a likelihood ratio that trades off the entities’ similarity with their rarity. This method always outperforms using only similarity; however, with certain parameter settings, similarity turns out to be surprisingly competitive. Using real data, we apply the model to detect twins given their birth weights and to re-identify cell phone users based on distinctive usage patterns.
Smooth Operators
Authors: Grunewalder, Steffen and Arthur, Gretton and Shawe-Taylor, John
Published in: Proceedings of the 30th International Conference on Machine Learning (Main Conference Track), 2013

Abstract: We develop a generic approach to form smooth versions of basic mathematical operations like multiplication, composition, change of measure, and conditional expectation, among others.   Operations which result in functions outside the reproducing kernel Hilbert space (such as the product of two RKHS functions) are approximated via a natural cost function, such that the solution is guaranteed to be in the targeted RKHS. This approximation problem is reduced to a regression problem using an adjoint trick, and solved in a vector-valued RKHS, consisting of continuous, linear, smooth operators which map from an input, real-valued RKHS to the desired target RKHS. Important constraints, such as an almost everywhere positive density, can be enforced or approximated naturally in this framework, using convex constraints on the operators. Finally, smooth operators can be composed to accomplish more complex machine learning tasks, such as the sum rule and kernelized approximate Bayesian inference, where state-of-the-art convergence rates are obtained.
The Cross-Entropy Method Optimizes for Quantiles
Authors: Goschin, Sergiu and Weinstein, Ari and Littman, Michael
Published in: Proceedings of the 30th International Conference on Machine Learning (Main Conference Track), 2013

Abstract: Cross-entropy optimization (CE) has proven to be a powerful tool for search in control environments. In the basic scheme, a distribution over proposed solutions is repeatedly adapted by evaluating a sample of solutions and refocusing the distribution on a percentage of those with the highest scores.  We show that, in the kind of noisy evaluation environments that are common in decision-making domains, this percentage-based refocusing does not optimize the expected utility of solutions, but instead a quantile metric. We provide a variant of CE (Proportional CE) that effectively optimizes the expected value. We show using variants of established noisy environments that Proportional CE can be used in place of CE and can improve solution quality.
Topic Discovery through Data Dependent and Random Projections
Authors: Ding, Weicong and Hossein Rohban, Mohammad and Ishwar, Prakash and Saligrama, Venkatesh
Published in: Proceedings of the 30th International Conference on Machine Learning (Main Conference Track), 2013

Abstract: We present algorithms for topic modeling based on the geometry of cross-document word-frequency patterns. This perspective gains significance under the so called separability condition. This is a condition on existence of novel-words that are unique to each topic. We present a suite of highly efficient algorithms with provable guarantees based on data-dependent and random projections to identify novel words and associated topics. Our key insight here is that the maximum and minimum values of cross-document frequency patterns projected along any direction are associated with novel words. While our sample complexity bounds for topic recovery are similar to the state-of-art, the computational complexity of our random projection scheme scales linearly with the number of documents and the number of words per document. We present several experiments on synthetic and realworld datasets to demonstrate qualitative and quantitative merits of our scheme.
Bayesian Learning of Recursively Factored Environments
Authors: Bellemare, Marc and Veness, Joel and Bowling, Michael
Published in: Proceedings of the 30th International Conference on Machine Learning (Main Conference Track), 2013

Abstract: Model-based reinforcement learning techniques have historically encountered a number of difficulties scaling up to large observation spaces. One promising approach has been to decompose the model learning task into a number of smaller, more manageable sub-problems by factoring the observation space. Typically, many different factorizations are possible, which can make it difficult to select an appropriate factorization without extensive testing. In this paper we introduce the class of recursively decomposable factorizations, and show how exact Bayesian inference can be used to efficiently guarantee predictive performance close to the best factorization in this class. We demonstrate the strength of this approach by presenting a collection of empirical results for 20 different Atari 2600 games.
Selective sampling algorithms for cost-sensitive multiclass prediction
Authors: Agarwal, Alekh
Published in: Proceedings of the 30th International Conference on Machine Learning (Main Conference Track), 2013

Abstract: In this paper, we study the problem of active learning for cost-sensitive multiclass classification. We propose selective  sampling algorithms, which process the data in a streaming fashion,  querying only a subset of the labels. For these algorithms, we analyze the regret and label complexity when the labels are generated according to a generalized linear model. We establish that the gains of active learning over passive learning can range from none to exponentially large, based on a natural notion of margin. We also  present a safety guarantee to guard against model mismatch. Numerical  simulations show that our algorithms indeed obtain a low regret with a  small number of queries.
The Bigraphical Lasso
Authors: Kalaitzis, Alfredo and Lafferty, John and Lawrence, Neil D. and Zhou, Shuheng
Published in: Proceedings of the 30th International Conference on Machine Learning (Main Conference Track), 2013

Abstract: The i.i.d. assumption in machine learning is endemic, but often flawed. Complex data sets exhibit partial correlations between both instances and features. A model specifying both types of correlation can have a number of parameters that scales quadratically with the number of features and data points. We introduce the bigraphical lasso, an estimator for precision matrices of matrix-normals based on the Cartesian product of graphs. A prominent product in spectral graph theory, this structure has appealing properties for regression, enhanced sparsity and interpretability. To deal with the parameter explosion we introduce L1 penalties and fit the model through a flip-flop algorithm that results in a linear number of lasso regressions.
Almost Optimal Exploration in Multi-Armed Bandits
Authors: Karnin, Zohar and Koren, Tomer and Somekh, Oren
Published in: Proceedings of the 30th International Conference on Machine Learning (Main Conference Track), 2013

Abstract: We study the problem of exploration in stochastic Multi-Armed Bandits. Even in the simplest setting of identifying the best arm, there remains a logarithmic multiplicative gap between the known lower and upper bounds for the number of arm pulls required for the task. This extra logarithmic factor is quite meaningful in nowadays large-scale applications. We present two novel, parameter-free algorithms for identifying the best arm, in two different settings: given a target confidence and given a target budget of arm pulls, for which we prove upper bounds whose gap from the lower bound is only doubly-logarithmic in the problem parameters. We corroborate our theoretical results with experiments demonstrating that our algorithm outperforms the state-of-the-art and scales better as the size of the problem increases.
Deep Canonical Correlation Analysis
Authors: Andrew, Galen and Arora, Raman and Bilmes, Jeff and Livescu, Karen
Published in: Proceedings of the 30th International Conference on Machine Learning (Main Conference Track), 2013

Abstract: We introduce Deep Canonical Correlation Analysis (DCCA), a method to learn complex nonlinear transformations of two views of data such that the resulting representations are highly linearly correlated. Parameters of both transformations are jointly learned to maximize the (regularized) total correlation.   It can be viewed as a nonlinear extension of the linear method \emphcanonical correlation analysis (CCA).  It is an alternative to the nonparametric method \emphkernel canonical correlation analysis (KCCA) for learning correlated nonlinear transformations. Unlike KCCA, DCCA does not require an inner product, and has the advantages of a parametric method: training time scales well with data size and the training data need not be referenced when computing the representations of unseen instances.  In experiments on two real-world datasets, we find that DCCA learns representations with significantly higher correlation than those learned by CCA and KCCA. We also introduce a novel non-saturating sigmoid function based on the cube root that may be useful more generally in feedforward neural networks.
Consistency of Online Random Forests
Authors: Denil, Misha and Matheson, David and Freitas, Nando
Published in: Proceedings of the 30th International Conference on Machine Learning (Main Conference Track), 2013

Abstract: As a testament to their success, the theory of random forests has long been outpaced by their application in practice. In this paper, we take a step towards narrowing this gap by providing a consistency result for online random forests.
Sparse Gaussian Conditional Random Fields: Algorithms, Theory, and Application to Energy Forecasting
Authors: Wytock, Matt and Kolter, Zico
Published in: Proceedings of the 30th International Conference on Machine Learning (Main Conference Track), 2013

Abstract: This paper considers the sparse Gaussian conditional random field, a discriminative extension of sparse inverse covariance estimation, where we use convex methods to learn a high-dimensional conditional distribution of outputs given inputs. The model has been proposed by multiple researchers within the past year, yet previous papers have been substantially limited in their analysis of the method and in the ability to solve large-scale problems.  In this paper, we make three contributions: 1) we develop a second-order active-set method which is several orders of magnitude faster that previously proposed optimization approaches for this problem 2) we analyze the model from a theoretical standpoint, improving upon past bounds with convergence rates that depend logarithmically on the data dimension, and 3) we apply the method to large-scale energy forecasting problems, demonstrating state-of-the-art performance on two real-world tasks.
Fast Image Tagging
Authors: Chen, Minmin and Zheng, Alice and Weinberger, Kilian
Published in: Proceedings of the 30th International Conference on Machine Learning (Main Conference Track), 2013

Abstract: Automatic image annotation is a difficult and highly relevant machine learning task. Recent advances have significantly improved the state-of-the-art in retrieval accuracy with algorithms based on nearest neighbor classification in carefully learned metric spaces. But this comes at a price of increased computational complexity during training and testing. We propose FastTag, a novel algorithm that achieves comparable results with two simple linear mappings that are co-regularized in a joint convex loss function. The loss function can be efficiently optimized in closed form updates, which allows us to incorporate a large number of image descriptors cheaply. On several standard real-world benchmark data sets, we demonstrate that FastTag matches the current state-of-the-art in tagging quality, yet reduces the training and testing times by several orders of magnitude and has lower asymptotic complexity.
Expensive Function Optimization with Stochastic Binary Outcomes
Authors: Tesch, Matthew and Schneider, Jeff and Choset, Howie
Published in: Proceedings of the 30th International Conference on Machine Learning (Main Conference Track), 2013

Abstract: Real world systems often have parameterized controllers which can be tuned to improve performance. Bayesian optimization methods provide for efficient optimization of these controllers, so as to reduce the number of required experiments on the expensive physical system. In this paper we address Bayesian optimization in the setting where performance is only observed through a stochastic binary outcome – success or failure of the experiment. Unlike bandit problems, the goal is to maximize the system performance after this offline training phase rather than minimize regret during training.  In this work we define the stochastic binary optimization problem and propose an approach using an adaptation of Gaussian Processes for classification that presents a Bayesian optimization framework for this problem.  We propose an experiment selection metric for this setting based on expected improvement.  We demonstrate the algorithm’s performance on synthetic problems and on a real snake robot learning to move over an obstacle.
Multiple-source cross-validation
Authors: Geras, Krzysztof and Sutton, Charles
Published in: Proceedings of the 30th International Conference on Machine Learning (Main Conference Track), 2013

Abstract: Cross-validation is an essential tool in machine learning and statistics. The typical procedure, in which data points are randomly assigned to one of the test sets, makes an implicit assumption that the data are exchangeable. A common case in which this does not hold is when the data come from multiple sources, in the sense used in transfer learning. In this case it is common to arrange the cross-validation procedure in a way that takes the source structure into account. Although common in practice, this procedure does not appear to have been theoretically analysed. We present new estimators of the variance of the cross-validation, both in the multiple-source setting and in the standard iid setting. These new estimators allow for much more accurate confidence intervals and hypothesis tests to compare algorithms.
Learning Triggering Kernels for Multi-dimensional Hawkes Processes
Authors: Zhou, Ke and Zha, Hongyuan and Song, Le
Published in: Proceedings of the 30th International Conference on Machine Learning (Main Conference Track), 2013

Abstract: How does the activity of one person affect that of another person? Does the strength of influence remain periodic or decay exponentially over time? In this paper, we study these critical questions in social network analysis quantitatively under the framework of multi-dimensional Hawkes processes. In particular, we focus on the nonparametric learning of the  triggering kernels, and propose an algorithm \sf MMEL that combines the idea of decoupling the parameters through constructing a tight upper-bound of the objective function and application of Euler-Lagrange equations for optimization in infinite dimensional functional space.    We show that the proposed method performs significantly better than alternatives in experiments on both synthetic and real world datasets.
On the difficulty of training recurrent neural networks
Authors: Pascanu, Razvan and Mikolov, Tomas and Bengio, Yoshua
Published in: Proceedings of the 30th International Conference on Machine Learning (Main Conference Track), 2013

Abstract: There are two widely known issues with properly training recurrent neural networks, the vanishing and the exploding gradient problems detailed in Bengio et al. (1994). In this paper we attempt to improve the understanding of the underlying issues by exploring these problems from an analytical, a geometric and a dynamical systems perspective. Our analysis is used to justify a simple yet effective solution. We propose a gradient norm clipping strategy to deal with exploding gradients and a soft constraint for the vanishing gradients problem. We validate empirically our hypothesis and proposed solutions in the experimental section.
Maxout Networks
Authors: Goodfellow, Ian and Warde-Farley, David and Mirza, Mehdi and Courville, Aaron and Bengio, Yoshua
Published in: Proceedings of the 30th International Conference on Machine Learning (Main Conference Track), 2013

Abstract: We consider the problem of designing models to leverage a recently introduced approximate model averaging technique called dropout. We define a simple new model called maxout (so named because its output is the max of a set of inputs, and because it is a natural companion to dropout) designed to both facilitate optimization by dropout and improve the accuracy of dropout's fast approximate model averaging technique. We empirically verify that the model successfully accomplishes both of these tasks. We use maxout and dropout to demonstrate state of the art classification performance on four benchmark datasets: MNIST, CIFAR-10, CIFAR-100, and SVHN.
Predictable Dual-View Hashing
Authors: Rastegari, Mohammad and Choi, Jonghyun and Fakhraei, Shobeir and Hal, Daume and Davis, Larry
Published in: Proceedings of the 30th International Conference on Machine Learning (Main Conference Track), 2013

Abstract: We propose a Predictable Dual-View Hashing (PDH) algorithm which embeds proximity of data samples in the original spaces. We create a cross-view hamming space with the ability to compare information from previously incomparable domains with a notion of ‘predictability’.   By performing comparative experimental analysis on two large datasets, PASCAL-Sentence and SUN-Attribute, we demonstrate the superiority of our method to the state-of-the-art dual-view binary code learning algorithms.
Deep learning with COTS HPC systems
Authors: Coates, Adam and Huval, Brody and Wang, Tao and Wu, David and Catanzaro, Bryan and Andrew, Ng
Published in: Proceedings of the 30th International Conference on Machine Learning (Main Conference Track), 2013

Abstract: Scaling up deep learning algorithms has been shown to lead to increased performance in benchmark tasks and to enable discovery of complex high-level features.  Recent efforts to train extremely large networks (with over 1 billion parameters) have relied on cloud-like computing infrastructure and thousands of CPU cores.  In this paper, we present technical details and results from our own system based on Commodity Off-The-Shelf High Performance Computing (COTS HPC) technology: a cluster of GPU servers with Infiniband interconnects and MPI.  Our system is able to train 1 billion parameter networks on just 3 machines in a couple of days, and we show that it can scale to networks with over 11 billion parameters using just 16 machines.  As this infrastructure is much more easily marshaled by others, the approach enables much wider-spread research with extremely large neural networks.
Nonparametric Mixture of Gaussian Processes with Constraints
Authors: Ross, James and Dy, Jennifer
Published in: Proceedings of the 30th International Conference on Machine Learning (Main Conference Track), 2013

Abstract: Motivated by the need to identify new and clinically relevant categories of lung disease, we propose a novel clustering with constraints method using a Dirichlet process mixture of Gaussian processes in a variational Bayesian nonparametric framework. We claim that individuals should be grouped according to biological and/or genetic similarity regardless of their level of disease severity; therefore, we introduce a new way of looking at subtyping/clustering by recasting it in terms of discovering associations of individuals to disease trajectories (i.e., grouping individuals based on their similarity in response to environmental and/or disease causing variables). The nonparametric nature of our algorithm allows for learning the unknown number of meaningful trajectories. Additionally, we acknowledge the usefulness of expert guidance by providing for their input using must-link and cannot- link constraints. These constraints are encoded with Markov random fields. We also provide an efficient variational approach for performing inference on our model.
Scale Invariant Conditional Dependence Measures
Authors: J Reddi, Sashank and Poczos, Barnabas
Published in: Proceedings of the 30th International Conference on Machine Learning (Main Conference Track), 2013

Abstract: In this paper we develop new dependence and conditional dependence measures and provide their estimators. An attractive property of these measures and estimators is that they are invariant to any monotone increasing transformations of the random variables, which is important in many applications including feature selection. Under certain conditions we show the consistency of these estimators, derive upper bounds on their convergence rates, and show that the estimators do not suffer from the curse of dimensionality. However, when the conditions are less restrictive, we derive a lower bound which proves that in the worst case the convergence can be arbitrarily slow similarly to some other estimators. Numerical illustrations demonstrate the applicability of our method.
Learning Policies for Contextual Submodular Prediction
Authors: Ross, Stephane and Zhou, Jiaji and Yue, Yisong and Dey, Debadeepta and Bagnell, Drew
Published in: Proceedings of the 30th International Conference on Machine Learning (Main Conference Track), 2013

Abstract: Many prediction domains, such as ad placement, recommendation, trajectory prediction, and document summarization, require predicting a set or list of options. Such lists are often evaluated using submodular reward functions that measure both quality and diversity. We propose a simple, efficient, and provably near-optimal approach to optimizing such prediction problems based on no-regret learning. Our method leverages a surprising result from online submodular optimization: a single no-regret online learner can compete with an optimal sequence of predictions. Compared to previous work, which either learn a sequence of classifiers or rely on stronger assumptions such as realizability, we ensure both data-efficiency as well as performance guarantees in the fully agnostic setting. Experiments validate the efficiency and applicability of the approach on a wide range of problems including manipulator trajectory optimization, news recommendation and document summarization.
Manifold Preserving Hierarchical Topic Models for Quantization and Approximation
Authors: Kim, Minje and Smaragdis, Paris
Published in: Proceedings of the 30th International Conference on Machine Learning (Main Conference Track), 2013

Abstract: We present two complementary topic models to address the analysis of mixture data lying on manifolds. First, we propose a quantization method with an additional mid-layer latent variable, which selects only data points that best preserve the manifold structure of the input data. In order to address the case of modeling all the in-between parts of that manifold using this reduced representation of the input, we introduce a new model that provides a manifold-aware interpolation method. We demonstrate the advantages of these models with experiments on the hand-written digit recognition and the speech source separation tasks.
Safe Screening of Non-Support Vectors in Pathwise SVM Computation
Authors: Ogawa, Kohei and Suzuki, Yoshiki and Takeuchi, Ichiro
Published in: Proceedings of the 30th International Conference on Machine Learning (Main Conference Track), 2013

Abstract: In this paper, we claim that some of the non-support vectors (non-SVs) that have no influence on the classifier can be screened out prior to the training phase in pathwise SVM computation scenario, in which one is asked to train a sequence (or path) of SVM classifiers for different regularization parameters. Based on a recently proposed framework so-called safe screening rule, we derive a rule for screening out non-SVs in advance, and discuss how we can exploit the advantage of the rule in pathwise SVM computation scenario. Experiments indicate that our approach often substantially reduce the total pathwise computation cost.
Cost-sensitive Multiclass Classification Risk Bounds
Authors: Ávila Pires, Bernardo and Szepesvari, Csaba and Ghavamzadeh, Mohammad
Published in: Proceedings of the 30th International Conference on Machine Learning (Main Conference Track), 2013

Abstract: A commonly used approach to multiclass classification is to replace the 0-1 loss with a convex surrogate so as to make empirical risk minimization computationally tractable. Previous work has uncovered sufficient and necessary conditions for the consistency of the resulting procedures. In this paper, we strengthen these results by showing how the 0-1 excess loss of a predictor can be upper bounded as a function of the excess loss of the predictor measured using the convex surrogate. The bound is developed for the case of cost-sensitive multiclass classification and a convex surrogate loss that goes back to the work of  Lee, Lin and Wahba. The bounds are as easy to calculate as in binary classification. Furthermore, we also show that our analysis extends to the analysis of the recently introduced “Simplex Coding” scheme.
Semi-supervised Clustering by Input Pattern Assisted Pairwise Similarity Matrix Completion
Authors: Yi, Jinfeng and Zhang, Lijun and Jin, Rong and Qian, Qi and Jain, Anil
Published in: Proceedings of the 30th International Conference on Machine Learning (Main Conference Track), 2013

Abstract: Many semi-supervised clustering algorithms have been proposed to improve the clustering accuracy by effectively exploring the available side information that is usually in the form of pairwise constraints. Despite the progress, there are two main shortcomings of the existing semi-supervised clustering algorithms. First, they have to deal with non-convex optimization problems, leading to clustering results that are sensitive to the initialization. Second, none of these algorithms is equipped with theoretical guarantee regarding the clustering performance. We address these limitations by developing a framework for semi-supervised clustering based on ıt input pattern assisted matrix completion. The key idea is to cast clustering into a matrix completion problem, and solve it efficiently by exploiting the correlation between input patterns and cluster assignments. Our analysis shows that under appropriate conditions, only O(łog n) pairwise constraints are needed to accurately recover the true cluster partition. We verify the effectiveness of the proposed algorithm by comparing it to the state-of-the-art semi-supervised clustering algorithms on several benchmark datasets.
Learning the beta-Divergence in Tweedie Compound Poisson Matrix Factorization Models
Authors: Simsekli, Umut and Taylan Cemgil, Ali and Kenan Yilmaz, Yusuf
Published in: Proceedings of the 30th International Conference on Machine Learning (Main Conference Track), 2013

Abstract: In this study, we derive algorithms for estimating mixed β-divergences. Such cost functions are useful for Nonnegative Matrix and Tensor Factorization models with a compound Poisson observation model. Compound Poisson is a particular Tweedie model, an important special case of exponential dispersion models characterized by the fact that the variance is proportional to a power function of the mean. There are several well known matrix and tensor factorization algorithms that minimize the β-divergence; these estimate the mean parameter. The probabilistic interpretation gives us more flexibility and robustness by providing us additional tunable parameters such as power and dispersion. Estimation of the power parameter is useful for choosing a suitable divergence and estimation of dispersion is useful for data driven regularization and weighting in collective/coupled factorization of heterogeneous datasets. We present three inference algorithms for both estimating the factors and the additional parameters of the compound Poisson distribution. The methods are evaluated on two applications: modeling symbolic representations for polyphonic music and lyric prediction from audio features. Our conclusion is that the compound poisson based factorization models can be useful for sparse positive data.
Fast algorithms for sparse principal component analysis based on Rayleigh quotient iteration
Authors: Kuleshov, Volodymyr
Published in: Proceedings of the 30th International Conference on Machine Learning (Main Conference Track), 2013

Abstract: We introduce new algorithms for sparse principal component analysis (sPCA), a variation of PCA which aims to represent data in a sparse low-dimensional basis. Our algorithms possess a cubic rate of convergence and can compute principal components with k non-zero elements at a cost of O(nk + k^3) flops per iteration. We observe in numerical experiments that these components are of equal or greater quality than ones obtained from current state-of-the-art techniques, but require between one and two orders of magnitude fewer flops to be computed. Conceptually, our approach generalizes the Rayleigh quotient iteration algorithm for computing eigenvectors, and can be interpreted as a type of second-order optimization method. We demonstrate the applicability of our algorithms on several datasets, including the STL-10 machine vision dataset and gene expression data.
Nested Chinese Restaurant Franchise Process:  Applications to User Tracking and Document Modeling
Authors: Ahmed, Amr and Hong, Liangjie and Smola, Alexander
Published in: Proceedings of the 30th International Conference on Machine Learning (Main Conference Track), 2013

Abstract: Much natural data is hierarchical in nature. Moreover, this hierarchy  is often shared between different instances. We introduce the  nested Chinese Restaurant Franchise Process as a means to obtain both  hierarchical tree-structured representations for objects, akin to (but more general than) the nested Chinese Restaurant Process while sharing their structure akin  to the Hierarchical Dirichlet Process.     Moreover, by decoupling the \emphstructure generating part of the  process from the components responsible for the observations, we are  able to apply the same statistical approach to a variety of user  generated data. In particular, we model the joint distribution of  microblogs and locations for Twitter for users. This leads to a 40%  reduction in location uncertainty relative to the best previously  published results. Moreover, we model documents from the NIPS papers  dataset, obtaining excellent perplexity relative to (hierarchical)  Pachinko allocation and LDA.
Tree-Independent Dual-Tree Algorithms
Authors: Curtin, Ryan and March, William and Ram, Parikshit and Anderson, David and Gray, Alexander and Isbell, Charles
Published in: Proceedings of the 30th International Conference on Machine Learning (Main Conference Track), 2013

Abstract: Dual-tree algorithms are a widely used class of branch-and-bound algorithms.  Unfortunately, developing dual-tree algorithms for use with different trees and problems is often complex and burdensome.  We introduce a four-part logical split: the tree, the traversal, the point-to-point base case, and the pruning rule.  We provide a meta-algorithm which allows development of dual-tree algorithms in a tree-independent manner and easy extension to entirely new types of trees.  Representations are provided  for five common algorithms; for k-nearest neighbor search, this leads to a novel, tighter pruning bound. The meta-algorithm also allows  straightforward extensions to massively parallel settings.
Multilinear Multitask Learning
Authors: Romera-Paredes, Bernardino and Aung, Hane and Bianchi-Berthouze, Nadia and Pontil, Massimiliano
Published in: Proceedings of the 30th International Conference on Machine Learning (Main Conference Track), 2013

Abstract: Many real world datasets occur or can be arranged into multi-modal structures.  With such datasets, the tasks to be learnt can be referenced by multiple indices.  Current multitask learning frameworks are not designed to account for the preservation of this information.  We propose the use of multilinear algebra as a natural way to model such a set of related tasks. We present two learning methods;   one is an adapted convex relaxation method used in the context of tensor completion.  The second method is based on the Tucker decomposition and on alternating minimization. Experiments on synthetic and real data indicate that the multilinear approaches provide a significant  improvement over other multitask learning methods. Overall our second  approach yields the best performance in all datasets.
Online Learning under Delayed Feedback
Authors: Joulani, Pooria and Gyorgy, Andras and Szepesvari, Csaba
Published in: Proceedings of the 30th International Conference on Machine Learning (Main Conference Track), 2013

Abstract: Online learning with delayed feedback has received increasing attention recently due to its several applications in distributed, web-based learning problems. In this paper we provide a systematic study of the topic, and analyze the effect of delay on the regret of online learning algorithms. Somewhat surprisingly, it turns out that delay increases the regret in a multiplicative way in adversarial problems, and in an additive way in stochastic problems. We give meta-algorithms that transform, in a black-box fashion, algorithms developed for the non-delayed case into ones that can handle the presence of delays in the feedback loop. Modifications of the well-known UCB algorithm are also developed for the bandit problem with delayed feedback, with the advantage over the meta-algorithms that they can be implemented with lower complexity.
Adaptive Hamiltonian and Riemann Manifold Monte Carlo
Authors: Wang, Ziyu and Mohamed, Shakir and Freitas, Nando
Published in: Proceedings of the 30th International Conference on Machine Learning (Main Conference Track), 2013

Abstract: In this paper we address the widely-experienced difficulty in tuning Hamiltonian-based Monte Carlo samplers. We develop an algorithm that allows for the adaptation of Hamiltonian and Riemann manifold Hamiltonian Monte Carlo samplers using Bayesian optimization that allows for infinite adaptation of the parameters of these samplers. We show that the resulting sampling algorithms are ergodic, and demonstrate on several models and data sets that the use of our adaptive algorithms makes it is easy to obtain more efficient samplers, in some precluding the need for more complex models. Hamiltonian-based Monte Carlo samplers are widely known to be an excellent choice of MCMC method, and we aim with this paper to remove a key obstacle towards the more widespread use of these samplers in practice.
Coco-Q: Learning in Stochastic Games with Side Payments
Authors: Sodomka, Eric and Hilliard, Elizabeth and Littman, Michael and Greenwald, Amy
Published in: Proceedings of the 30th International Conference on Machine Learning (Main Conference Track), 2013

Abstract: Coco (""cooperative/competitive"") values are a solution concept for two-player normal-form games with transferable utility, when binding agreements and side payments between players are possible. In this paper, we show that coco values can also be defined for stochastic games and can be learned using a simple variant of Q-learning that is provably convergent. We provide a set of examples showing how the strategies learned by the Coco-Q algorithm relate to those learned by existing multiagent Q-learning algorithms.
On A Nonlinear Generalization of Sparse Coding and Dictionary Learning
Authors: Ho, Jeffrey and Xie, Yuchen and Vemuri, Baba
Published in: Proceedings of the 30th International Conference on Machine Learning (Main Conference Track), 2013

Abstract: Existing dictionary learning algorithms are based on the  assumption that the data are vectors in an Euclidean vector  space, and the dictionary is learned from the training data using the vector space structure and its Euclidean metric. However, in many applications, features and data often originated from a Riemannian manifold that does not support a global linear (vector space) structure.  Furthermore, the extrinsic viewpoint of existing dictionary learning algorithms becomes inappropriate for modeling and incorporating the intrinsic geometry of the manifold that is potentially important and critical to the application. This paper proposes a novel framework for sparse coding and dictionary learning for data on a Riemannian manifold, and it shows that  the existing sparse coding and dictionary learning methods can be considered as special (Euclidean) cases of the more general framework proposed here. We show that both the dictionary and sparse coding can  be effectively computed for several important classes of Riemannian manifolds, and we validate the proposed method using two well-known classification problems in computer vision and medical imaging analysis.
Estimation of Causal Peer Influence Effects
Authors: Toulis, Panos and Kao, Edward
Published in: Proceedings of the 30th International Conference on Machine Learning (Main Conference Track), 2013

Abstract: The broad adoption of social media has generated interest in leveraging peer influence for inducing desired user behavior. Quantifying the causal effect of peer influence presents technical challenges, however, including how to deal with social interference, complex response functions and network uncertainty. In this paper, we extend potential outcomes to allow for interference, we introduce well-defined causal estimands of peer-influence, and we develop two estimation procedures: a frequentist procedure relying on a sequential randomization design that requires knowledge of the network but operates under complicated response functions, and a Bayesian procedure which accounts for network uncertainty but relies on a linear response assumption to increase estimation precision. Our results show the advantages and disadvantages of the proposed methods in a number of situations.
PAC-Bayesian Bounds on Rate-Efficient Classifiers
Authors: Abbas, Alhabib and Andreopoulos, Yiannis
Published in: Proceedings of the 39th International Conference on Machine Learning (Main Conference Track), 2022

Abstract: We derive analytic bounds on the noise invariance of majority vote classifiers operating on compressed inputs. Specifically, starting from recent bounds on the true risk of majority vote classifiers, we extend the applicability of PAC-Bayesian theory to quantify the resilience of majority votes to input noise stemming from compression. The derived bounds are intuitive in binary classification settings, where they can be measured as expressions of voter differentials and voter pair agreement. By combining measures of input distortion with analytic guarantees on noise invariance, we prescribe rate-efficient machines to compress inputs without affecting subsequent classification. Our validation shows how bounding noise invariance can inform the compression stage for any majority vote classifier such that worst-case implications of bad input reconstructions are known, and inputs can be compressed to the minimum amount of information needed prior to inference.
Sharp-MAML: Sharpness-Aware Model-Agnostic Meta Learning
Authors: Abbas, Momin and Xiao, Quan and Chen, Lisha and Chen, Pin-Yu and Chen, Tianyi
Published in: Proceedings of the 39th International Conference on Machine Learning (Main Conference Track), 2022

Abstract: Model-agnostic meta learning (MAML) is currently one of the dominating approaches for few-shot meta-learning. Albeit its effectiveness, the optimization of MAML can be challenging due to the innate bilevel problem structure. Specifically, the loss landscape of MAML is much more complex with possibly  more saddle points and local minimizers than its empirical risk minimization counterpart. To address this challenge, we leverage the recently invented sharpness-aware minimization and develop a sharpness-aware MAML approach that we term Sharp-MAML. We empirically demonstrate that Sharp-MAML and its computation-efficient variant can outperform the plain-vanilla MAML baseline (e.g., +3% accuracy on Mini-Imagenet). We complement the empirical study with the convergence rate analysis and the generalization bound of Sharp-MAML. To the best of our knowledge, this is the first empirical and theoretical study on sharpness-aware minimization in the context of bilevel learning.
An Initial Alignment between Neural Network and Target is Needed for Gradient Descent to Learn
Authors: Abbe, Emmanuel and Cornacchia, Elisabetta and Hazla, Jan and Marquis, Christopher
Published in: Proceedings of the 39th International Conference on Machine Learning (Main Conference Track), 2022

Abstract: This paper introduces the notion of “Initial Alignment” (INAL) between a neural network at initialization and a target function. It is proved that if a network and a Boolean target function do not have a noticeable INAL, then noisy gradient descent with normalized i.i.d. initialization will not learn in polynomial time. Thus a certain amount of knowledge about the target (measured by the INAL) is needed in the architecture design. This also provides an answer to an open problem posed in (AS-NeurIPS’20). The results are based on deriving lower-bounds for descent algorithms on symmetric neural networks without explicit knowledge of the target function beyond its INAL.
Active Sampling for Min-Max Fairness
Authors: Abernethy, Jacob D and Awasthi, Pranjal and Kleindessner, Matthäus and Morgenstern, Jamie and Russell, Chris and Zhang, Jie
Published in: Proceedings of the 39th International Conference on Machine Learning (Main Conference Track), 2022

Abstract: We propose simple active sampling and reweighting strategies for optimizing min-max fairness that can be applied to any classification or regression model learned via loss minimization. The key intuition behind our approach is to use at each timestep a datapoint from the group that is worst off under the current model for updating the model. The ease of implementation and the generality of our robust formulation make it an attractive option for improving model performance on disadvantaged groups. For convex learning problems, such as linear or logistic regression, we provide a fine-grained analysis, proving the rate of convergence to a min-max fair solution.
Meaningfully debugging model mistakes using conceptual counterfactual explanations
Authors: Abid, Abubakar and Yuksekgonul, Mert and Zou, James
Published in: Proceedings of the 39th International Conference on Machine Learning (Main Conference Track), 2022

Abstract: Understanding and explaining the mistakes made by trained models is critical to many machine learning objectives, such as improving robustness, addressing concept drift, and mitigating biases. However, this is often an ad hoc process that involves manually looking at the model’s mistakes on many test samples and guessing at the underlying reasons for those incorrect predictions. In this paper, we propose a systematic approach, conceptual counterfactual explanations (CCE), that explains why a classifier makes a mistake on a particular test sample(s) in terms of human-understandable concepts (e.g. this zebra is misclassified as a dog because of faint stripes). We base CCE on two prior ideas: counterfactual explanations and concept activation vectors, and validate our approach on well-known pretrained models, showing that it explains the models’ mistakes meaningfully. In addition, for new models trained on data with spurious correlations, CCE accurately identifies the spurious correlation as the cause of model mistakes from a single misclassified test sample. On two challenging medical applications, CCE generated useful insights, confirmed by clinicians, into biases and mistakes the model makes in real-world settings. The code for CCE is publicly available and can easily be applied to explain mistakes in new models.