mtybilly/Instruct2DS huggingface dataset:
A Randomized Mirror Descent Algorithm for Large Scale Multiple Kernel Learning
Authors: Arash Afkanpour, András György, Csaba Szepesvari, Michael Bowling
Published in: Proceedings of the 30th International Conference on Machine Learning (Main Conference Track), 2013

Abstract: We consider the problem of simultaneously learning to linearly combine a very large number of kernels and learn a good predictor based on the learnt kernel. When the number of kernels d to be combined is very large, multiple kernel learning methods whose computational cost scales linearly in d are intractable. We propose a randomized version of the mirror descent algorithm to overcome this issue, under the objective of minimizing the group p-norm penalized empirical risk. The key to achieve the required exponential speed-up is the computationally efficient construction of low-variance estimates of the gradient. We propose importance sampling based estimates, and find that the ideal distribution samples a coordinate with a probability proportional to the magnitude of the corresponding gradient. We show that in the case of learning the coefficients of a polynomial kernel, the combinatorial structure of the base kernels to be combined allows sampling from this distribution in O(łog(d)) time, making the total computational cost of the method to achieve an epsilon-optimal solution to be O(łog(d)/epsilon^2), thereby allowing our method to operate for very large values of d. Experiments with simulated and real data confirm that the new algorithm is computationally more efficient than its state-of-the-art alternatives.
Learning Heteroscedastic Models by Convex Programming under Group Sparsity
Authors: Arnak Dalalyan, Mohamed Hebiri, Katia Meziani, Joseph Salmon
Published in: Proceedings of the 30th International Conference on Machine Learning (Main Conference Track), 2013

Abstract: Sparse estimation methods based on l1 relaxation,  such as the Lasso and the Dantzig  selector, require the knowledge of the variance  of the noise in order to properly tune the  regularization parameter. This constitutes a   major obstacle in applying these methods in  several frameworks, such as time series, random fields, inverse problems, for which noise  is rarely homoscedastic and the noise level is  hard to know in advance.  In this paper, we  propose a new approach to the joint estimation  of the conditional mean and the conditional  variance in a high-dimensional (auto-)  regression setting.   An attractive feature of the proposed estimator is   that it is efficiently computable even for very large   scale problems by solving a second-order cone program  (SOCP). We present theoretical analysis and  numerical results assessing the performance  of the proposed procedure.
Noisy and Missing Data Regression: Distribution-Oblivious Support Recovery
Authors: Yudong Chen, Constantine Caramanis
Published in: Proceedings of the 30th International Conference on Machine Learning (Main Conference Track), 2013

Abstract: Many models for sparse regression typically assume that the covariates are known completely, and without noise. Particularly in high-dimensional applications, this is often not the case. Worse yet, even estimating statistics of the noise (the noise covariance) can be a central challenge. In this paper we develop a simple variant of orthogonal matching pursuit (OMP) for precisely this setting. We show that without knowledge of the noise covariance, our algorithm recovers the support, and we provide matching lower bounds that show that our algorithm performs at the minimax optimal rate. While simple, this is the first algorithm that (provably) recovers support in a noise-distribution-oblivious manner. When knowledge of the noise-covariance is available, our algorithm matches the best-known \ell^2-recovery bounds available. We show that these too are min-max optimal. Along the way, we also obtain improved performance guarantees for OMP for the standard sparse regression problem with Gaussian noise.
Covariate Shift in Hilbert Space: A Solution via Sorrogate Kernels
Authors: Kai Zhang, Vincent Zheng, Qiaojun Wang, James Kwok, Qiang Yang, Ivan Marsic
Published in: Proceedings of the 30th International Conference on Machine Learning (Main Conference Track), 2013

Abstract: Covariate shift is a unconventional learning scenario in which training and testing data have different distributions. A general principle to solve the problem is to make the training data distribution similar to the test one, such that classifiers computed on the former generalizes well to the latter. Current approaches typically target on the sample distribution in the input space, however, for kernel-based learning methods, the algorithm performance depends directly on the geometry of the kernel-induced feature space. Motivated by this, we propose to match data distributions in the Hilbert space, which, given a pre-defined empirical kernel map, can be formulated as aligning kernel matrices across domains. In particular, to evaluate similarity of kernel matrices defined on arbitrarily different samples, the novel concept of surrogate kernel is introduced based on the Mercer's theorem. Our approach caters the model adaptation specifically to kernel-based learning mechanism, and demonstrates promising results on several real-world applications.
Dual Averaging and Proximal Gradient Descent for Online Alternating Direction Multiplier Method
Authors: Taiji Suzuki
Published in: Proceedings of the 30th International Conference on Machine Learning (Main Conference Track), 2013

Abstract: We develop new stochastic optimization methods that are applicable to   a wide range of structured regularizations.  Basically our methods are combinations of   basic stochastic optimization techniques and Alternating Direction Multiplier Method (ADMM).  ADMM is a general framework for optimizing a composite function,  and has a wide range of applications.  We propose two types of online variants of ADMM,   which correspond to online proximal gradient descent and regularized dual averaging respectively.  The proposed algorithms are computationally efficient and easy to implement.  Our methods yield O(1/\sqrtT) convergence of the expected risk.  Moreover, the online proximal gradient descent type method yields   O(łog(T)/T) convergence for a strongly convex loss.  Numerical experiments show effectiveness of our methods in learning tasks with structured sparsity  such as overlapped group lasso.
A Local Algorithm for Finding Well-Connected Clusters
Authors: Zeyuan Allen Zhu, Silvio Lattanzi, Vahab Mirrokni
Published in: Proceedings of the 30th International Conference on Machine Learning (Main Conference Track), 2013

Abstract: Motivated by applications of large-scale graph clustering, we study random-walk-based LOCAL algorithms whose running times depend only on the size of the output cluster, rather than the entire graph. In particular, we develop a method with better theoretical guarantee compared to all previous work, both in terms of the clustering accuracy and the conductance of the output set. We also prove that our analysis is tight, and perform empirical evaluation to support our theory on both synthetic and real data.    More specifically, our method outperforms prior work when the cluster is WELL-CONNECTED. In fact, the better it is well-connected inside, the more significant improvement we can obtain. Our results shed light on why in practice some random-walk-based algorithms perform better than its previous theory, and help guide future research about local clustering.
A New Frontier of Kernel Design for Structured Data
Authors: Kilho Shin
Published in: Proceedings of the 30th International Conference on Machine Learning (Main Conference Track), 2013

Abstract: Many kernels for discretely structured data in the literature are designed within the framework of the convolution kernel and its generalization, the mapping kernel. The two most important advantages to use this framework is an easy-to-check criteria of positive definiteness and efficient computation based on the dynamic programming methodology of the resulting kernels.  On the other hand, the recent theory of partitionable kernels reveals that the known kernels only take advantage of a very small portion of the potential of the framework.  In fact, we have good opportunities to find novel and important kernels in the unexplored area.  In this paper, we shed light on a novel important class of kernels within the framework: We give a mathematical characterization of the class, show a parametric method to optimize kernels of the class to specific problems, based on this characterization, and present some experimental results, which show the new kernels are promising in both accuracy and efficiency.
Efficient Multi-label Classification with Many Labels
Authors: Wei Bi, James Kwok
Published in: Proceedings of the 30th International Conference on Machine Learning (Main Conference Track), 2013

Abstract: Multi-label classification deals with the problem where each instance can be associated with a set of class labels. However, in many real-world applications, the number of class labels can be in the hundreds or even thousands, and existing multi-label classification methods often become computationally inefficient. In recent years, a number of remedies have been proposed. However, they are either based on simple dimension reduction techniques or involve expensive optimization problems. In this paper, we address this problem by selecting a small subset of class labels that can approximately span the original label space. This is performed by randomized sampling where the sampling probability of each class label reflects its importance among all the labels. Theoretical analysis shows that this randomized sampling approach is highly efficient. Experiments on a number of real-world multi-label datasets with many labels demonstrate the appealing performance and efficiency of the proposed algorithm.
Learning with Marginalized Corrupted Features
Authors: Laurens Maaten, Minmin Chen, Stephen Tyree, Kilian Weinberger
Published in: Proceedings of the 30th International Conference on Machine Learning (Main Conference Track), 2013

Abstract: The goal of machine learning is to develop predictors that generalize well to test data. Ideally, this is achieved by training on very large (infinite) training data sets that capture all variations in the data distribution. In the case of finite training data, an effective solution is to extend the training set with artificially created examples – which, however, is also computationally costly. We propose to corrupt training examples with noise from known distributions within the exponential family and present a novel learning algorithm, called marginalized corrupted features (MCF), that trains robust predictors by minimizing the expected value of the loss function under the corrupting distribution – essentially learning with infinitely many (corrupted) training examples. We show empirically on a variety of data sets that MCF classifiers can be trained efficiently, may generalize substantially better to test data, and are more robust to feature deletion at test time.
Spectral Compressed Sensing via Structured Matrix Completion
Authors: Yuxin Chen, Yuejie Chi
Published in: Proceedings of the 30th International Conference on Machine Learning (Main Conference Track), 2013

Abstract: The paper studies the problem of recovering a spectrally sparse object from a small number of time domain samples. Specifically, the object of interest with ambient dimension n is assumed to be a mixture of r complex multi-dimensional sinusoids, while the underlying frequencies can assume any value in the unit disk. Conventional compressed sensing paradigms suffer from the \em basis mismatch issue when imposing a discrete dictionary on the Fourier representation. To address this problem,  we develop a novel nonparametric algorithm, called enhanced matrix completion (EMaC), based on structured matrix completion. The algorithm starts by converting the data into a low-rank enhanced form with multi-fold Hankel structure, then attempts recovery via nuclear norm minimization. Under mild incoherence conditions, EMaC allows perfect recovery as soon as the number of samples exceeds the order of \mathcalO(rłog^2 n). We also show that, in many instances, accurate completion of a low-rank multi-fold Hankel matrix is possible when the number of observed entries is proportional to the information theoretical limits (except for a logarithmic gap). The robustness of EMaC against bounded noise and its applicability to super resolution are further demonstrated by numerical experiments.
Approximation properties of DBNs with binary hidden units and real-valued visible units
Authors: Oswin Krause, Asja Fischer, Tobias Glasmachers, Christian Igel
Published in: Proceedings of the 30th International Conference on Machine Learning (Main Conference Track), 2013

Abstract: Deep belief networks (DBNs) can approximate any distribution over fixed-length binary vectors. However, DBNs are frequently applied to model real-valued data, and so far little is known about their representational power in this case.  We analyze the approximation properties of DBNs with two layers of binary hidden units and visible units with conditional distributions from the exponential family. It is shown that these DBNs can, under mild assumptions, model any additive mixture of distributions from the exponential family with independent variables. An arbitrarily good approximation in terms of Kullback-Leibler divergence of an m-dimensional mixture distribution with n components can be achieved by a DBN with m visible variables and n and n+1 hidden variables in the first and second hidden layer, respectively. Furthermore, relevant infinite mixtures can be approximated arbitrarily well by a DBN with a finite number of neurons. This includes the important special case of an infinite mixture of Gaussian distributions with fixed variance restricted to a compact domain, which in turn can approximate any strictly positive density over this domain.
Multi-Task Learning with Gaussian Matrix Generalized Inverse Gaussian Model
Authors: Ming Yang, Yingming Li, Zhongfei Zhang
Published in: Proceedings of the 30th International Conference on Machine Learning (Main Conference Track), 2013

Abstract: In this paper, we study the multi-task learning problem with a new perspective of considering the structure of the residue error matrix and the low-rank approximation to the task covariance matrix simultaneously. In particular, we first introduce the Matrix Generalized Inverse Gaussian (MGIG) prior and define a Gaussian Matrix Generalized Inverse Gaussian (GMGIG) model for low-rank approximation to the task covariance matrix. Through combining the GMGIG model with the residual error structure assumption, we propose the GMGIG regression model for multi-task learning. To make the computation tractable, we simultaneously use variational inference and sampling techniques. In particular, we propose two sampling strategies for computing the statistics of the MGIG distribution. Experiments show that this model is superior to the peer methods in regression and prediction.
Revisiting Frank-Wolfe: Projection-Free Sparse Convex Optimization
Authors: Martin Jaggi
Published in: Proceedings of the 30th International Conference on Machine Learning (Main Conference Track), 2013

Abstract: We provide stronger and more general primal-dual convergence results for Frank-Wolfe-type algorithms (a.k.a. conditional gradient) for constrained convex optimization, enabled by a simple framework of duality gap certificates. Our analysis also holds if the linear subproblems are only solved approximately (as well as if the gradients are inexact), and is proven to be worst-case optimal in the sparsity of the obtained solutions.    On the application side, this allows us to unify a large variety of existing sparse greedy methods, in particular for optimization over convex hulls of an atomic set, even if those sets can only be approximated, including sparse (or structured sparse) vectors or matrices, low-rank matrices, permutation matrices, or max-norm bounded matrices.    We present a new general framework for convex optimization over matrix factorizations, where every Frank-Wolfe iteration will consist of a low-rank update, and discuss the broad application areas of this approach.
Simple Sparsification Improves Sparse Denoising Autoencoders in Denoising Highly Corrupted Images
Authors: Kyunghyun Cho
Published in: Proceedings of the 30th International Conference on Machine Learning (Main Conference Track), 2013

Abstract: Recently Burger et al. (2012) and Xie et al. (2012) proposed to use a denoising autoencoder (DAE) for denoising noisy images. They showed that a plain, deep DAE can denoise noisy images as well as the conventional methods such as BM3D and KSVD. Both of them approached image denoising by denoising small, image patches of a larger image and combining them to form a clean image. In this setting, it is usual to use the encoder of the DAE to obtain the latent representation and subsequently apply the decoder to get the clean patch. We propose that a simple sparsification of the latent representation found by the encoder improves denoising performance, when the DAE was trained with sparsity regularization. The experiments confirm that the proposed sparsification indeed helps both denoising a small image patch and denoising a larger image consisting of those patches. Furthermore, it is found out that the proposed method improves even classification performance when test samples are corrupted with noise.
General Functional Matrix Factorization Using Gradient Boosting
Authors: Tianqi Chen, Hang Li, Qiang Yang, Yong Yu
Published in: Proceedings of the 30th International Conference on Machine Learning (Main Conference Track), 2013

Abstract: Matrix factorization is among the most successful techniques for collaborative filtering. One challenge of collaborative filtering is how to utilize available auxiliary information to improve prediction accuracy. In this paper, we study the  problem of utilizing auxiliary information as features of   factorization and propose formalizing the problem as general functional matrix factorization, whose model includes conventional matrix factorization models as its special cases. Moreover, we propose a gradient boosting based algorithm to efficiently solve the optimization problem. Finally, we give two specific algorithms for efficient feature function construction for two specific tasks. Our method can construct more suitable feature functions by searching in an infinite functional space based on training data and thus can yield better prediction accuracy. The experimental results demonstrate that the proposed method outperforms the baseline methods on three real-world datasets.
On the Generalization Ability of Online Learning Algorithms for Pairwise Loss Functions
Authors: Purushottam Kar, Bharath Sriperumbudur, Prateek Jain, Harish Karnick
Published in: Proceedings of the 30th International Conference on Machine Learning (Main Conference Track), 2013

Abstract: In this paper, we study the generalization properties of online learning based stochastic methods for supervised learning problems where the loss function is dependent on more than one training sample (e.g., metric learning, ranking). We present a generic decoupling technique that enables us to provide Rademacher complexity-based generalization error bounds. Our bounds are in general tighter than those obtained by Wang et al. (COLT 2012) for the same problem. Using our decoupling technique, we are further able to obtain fast convergence rates for strongly con-vex pairwise loss functions. We are also able to analyze a class of memory efficient on-line learning algorithms for pairwise learning problems that use only a bounded subset of past training samples to update the hypothesis at each step. Finally, in order to complement our generalization bounds, we propose a novel memory efficient online learning algorithm for higher order learning problems with bounded regret guarantees.
Iterative Learning and Denoising in Convolutional Neural Associative Memories
Authors: Amin Karbasi, Amir Hesam Salavati, Amin Shokrollahi
Published in: Proceedings of the 30th International Conference on Machine Learning (Main Conference Track), 2013

Abstract: The task of a neural associative memory is to retrieve a set of previously memorized patterns from their noisy versions by using a network of neurons. Hence, an ideal network should be able to 1) gradually learn a set of patterns, 2) retrieve the correct pattern from noisy queries and 3) maximize the number of memorized patterns while maintaining the reliability in responding to queries. We show that by considering the inherent redundancy in the memorized patterns, one can obtain all the mentioned properties at once. This is in sharp contrast with the previous work that could only improve one or two aspects at the expense of the third. More specifically, we devise an iterative algorithm that learns the redundancy among the patterns. The resulting network has a  retrieval capacity that is exponential in the size of the network. Lastly, by considering the local structures of the network, the asymptotic error correction performance  can be made linear in the size of the network.
Non-Linear Stationary Subspace Analysis with Application to Video Classification
Authors: Mahsa Baktashmotlagh, Mehrtash Harandi, Abbas Bigdeli, Brian Lovell, Mathieu Salzmann
Published in: Proceedings of the 30th International Conference on Machine Learning (Main Conference Track), 2013

Abstract: Low-dimensional representations are key to the success of many video classification algorithms. However, the commonly-used dimensionality reduction techniques fail to account for the fact that only part of the signal is shared across all the videos in one class. As a consequence, the resulting representations contain instance-specific information, which introduces noise in the classification process. In this paper, we introduce Non-Linear Stationary Subspace Analysis: A method that overcomes this issue by explicitly separating the stationary parts of the video signal (i.e., the parts shared across all videos in one class), from its non-stationary parts (i.e., specific to individual videos). We demonstrate the effectiveness of our approach on action recognition, dynamic texture classification and scene recognition.
Scaling Multidimensional Gaussian Processes using Projected Additive Approximations
Authors: Elad Gilboa, Yunus Saatçi, John Cunningham, Elad Gilboa
Published in: Proceedings of the 30th International Conference on Machine Learning (Main Conference Track), 2013

Abstract: Exact Gaussian Process (GP) regression has O(N^3) runtime for data size N, making it intractable for large N. Advances in GP scaling have not been extended to the multidimensional input setting, despite the preponderance of multidimensional applications.   This paper introduces and tests a novel method of projected additive approximation to multidimensional GPs. We thoroughly illustrate the power of this method on several datasets, achieving close performance to the naive Full GP at orders of magnitude less cost.
Two-Sided Exponential Concentration Bounds for Bayes Error Rate and Shannon Entropy
Authors: Jean Honorio, Jaakkola Tommi
Published in: Proceedings of the 30th International Conference on Machine Learning (Main Conference Track), 2013

Abstract: We provide a method that approximates the Bayes error rate and the Shannon entropy with high probability. The Bayes error rate approximation makes possible to build a classifier that polynomially approaches Bayes error rate. The Shannon entropy approximation provides provable performance guarantees for learning trees and Bayesian networks from continuous variables. Our results rely on some reasonable regularity conditions of the unknown probability distributions, and apply to bounded as well as unbounded variables.
Active Learning for Multi-Objective Optimization
Authors: Marcela Zuluaga, Guillaume Sergent, Andreas Krause, Markus Püschel
Published in: Proceedings of the 30th International Conference on Machine Learning (Main Conference Track), 2013

Abstract: In many fields one encounters the challenge of identifying, out of a pool of possible designs, those that simultaneously optimize multiple objectives. This means that usually there is not one optimal design but an entire set of Pareto-optimal ones with optimal tradeoffs in the objectives. In many applications, evaluating one design is expensive; thus, an exhaustive search for the Pareto-optimal set is unfeasible. To address this challenge, we propose the Pareto Active Learning (PAL) algorithm, which intelligently samples the design space to predict the Pareto-optimal set. Key features of PAL include (1) modeling the objectives as samples from a Gaussian process distribution to capture structure and accommodate noisy evaluation; (2) a method to carefully choose the next design to evaluate to maximize progress; and (3) the ability to control prediction accuracy and sampling cost. We provide theoretical bounds on PAL’s sampling cost required to achieve a desired accuracy. Further, we show an experimental evaluation on three real-world data sets. The results show PAL’s effectiveness; in particular it improves significantly over a state-of-the-art evolutionary algorithm, saving in many cases about 33%.
That was fast! Speeding up NN search of high dimensional distributions.
Authors: Emanuele Coviello, Adeel Mumtaz, Antoni Chan, Gert Lanckriet
Published in: Proceedings of the 30th International Conference on Machine Learning (Main Conference Track), 2013

Abstract: We present a data structure for fast nearest neighbor retrieval of generative models of documents based on KL divergence.  Our data structure, which shares some similarity with Bregman Ball Trees, consists of a hierarchical partition of a database,   and uses a novel branch and bound methodology for search.  The main technical contribution of the paper is a   novel and efficient algorithm  for deciding whether to explore nodes during backtracking, based on a variational approximation.  This reduces the number of computations per node, and overcomes the limitations of Bregman Ball Trees on high dimensional data.  In addition, our strategy is applicable also to probability distributions with hidden state variables, and is not limited to regular exponential family distributions.    Experiments demonstrate substantial speed-ups over both Bregman  Ball Trees and over brute force search, on both moderate and high dimensional histogram data.  In addition, experiments on linear dynamical systems demonstrate the flexibility of our approach to latent variable models.
A Generalized Kernel Approach to Structured Output Learning
Authors: Hachem Kadri, Mohammad Ghavamzadeh, Philippe Preux
Published in: Proceedings of the 30th International Conference on Machine Learning (Main Conference Track), 2013

Abstract: We study the problem of structured output learning from a regression perspective. We first provide a general formulation of the kernel dependency estimation (KDE) approach to this problem using operator-valued kernels. Our formulation overcomes the two main limitations of the original KDE approach, namely the decoupling between outputs  in the image space and the inability to use a joint feature space. We then propose a covariance-based operator-valued kernel that allows us to take into account the structure of the kernel feature space. This kernel operates on the output space and only encodes the interactions between the outputs without any reference to the input space. To address this issue, we introduce a variant of our KDE method based on the conditional covariance operator that in addition to the correlation between the outputs takes into account the effects of the input variables. Finally, we evaluate the performance of our KDE approach using both covariance and conditional covariance kernels on three structured output problems, and compare it to the state-of-the art kernel-based structured output regression methods.
Entropic Affinities: Properties and Efficient Numerical Computation
Authors: Max Vladymyrov, Miguel Carreira-Perpinan
Published in: Proceedings of the 30th International Conference on Machine Learning (Main Conference Track), 2013

Abstract: Gaussian affinities are commonly used in graph-based methods such as spectral clustering or nonlinear embedding. Hinton and Roweis (2003) introduced a way to set the scale individually for each point so that it has a distribution over neighbors with a desired perplexity, or effective number of neighbors. This gives very good affinities that adapt locally to the data but are harder to compute. We study the mathematical properties of these “entropic affinities” and show that they implicitly define a continuously differentiable function in the input space and give bounds for it. We then devise a fast algorithm to compute the widths and affinities, based on robustified, quickly convergent root-finding methods combined with a tree- or density-based initialization scheme that exploits the slowly-varying behavior of this function. This algorithm is nearly optimal and much more accurate and fast than the existing bisection-based approach, particularly with large datasets, as we show with image and text data.
Efficient Active Learning of Halfspaces: an Aggressive Approach
Authors: Alon Gonen, Sivan Sabato, Shai Shalev-Shwartz
Published in: Proceedings of the 30th International Conference on Machine Learning (Main Conference Track), 2013

Abstract: We study pool-based active learning of half-spaces. We revisit the aggressive approach for active learning in the realizable case, and show that it can be made efficient and  practical, while also having theoretical guarantees under reasonable assumptions. We further show, both theoretically and experimentally, that it can be preferable to mellow approaches.  Our efficient aggressive active learner of half-spaces has formal approximation guarantees that hold when the pool is separable with a margin. While our analysis is focused on the realizable setting, we show that a simple heuristic allows using the same algorithm successfully for pools with low error as well. We further compare the aggressive approach to the mellow approach, and prove that there are cases in which the aggressive approach results in significantly better label complexity compared to the mellow approach. We demonstrate experimentally that substantial improvements in label complexity can be achieved using the aggressive approach, for both realizable and low-error settings.
Local Deep Kernel Learning for Efficient Non-linear SVM Prediction
Authors: Cijo Jose, Prasoon Goyal, Parv Aggrwal, Manik Varma
Published in: Proceedings of the 30th International Conference on Machine Learning (Main Conference Track), 2013

Abstract: Our objective is to speed up non-linear SVM prediction while maintaining classification accuracy above an acceptable limit. We generalize Localized Multiple Kernel Learning so as to learn a primal feature space embedding which is high dimensional, sparse and computationally deep. Primal based classification decouples prediction costs from the number of support vectors and our tree-structured features efficiently encode non-linearities while speeding up prediction exponentially over the state-of-the-art. We develop routines for optimizing over the space of tree-structured features and efficiently scale to problems with over half a million training points. Experiments on benchmark data sets reveal that our formulation can reduce prediction costs by more than three orders of magnitude in some cases with a moderate sacrifice in classification accuracy as compared to RBF-SVMs. Furthermore, our formulation leads to much better classification accuracies over leading methods.
Enhanced statistical rankings  via  targeted data collection
Authors: Braxton Osting, Christoph Brune, Stanley Osher
Published in: Proceedings of the 30th International Conference on Machine Learning (Main Conference Track), 2013

Abstract: Given a graph where vertices represent alternatives and pairwise comparison data, y_ij, is given on the edges, the statistical ranking problem is to find a potential function, defined on the vertices, such that the gradient of the potential function agrees with pairwise comparisons. We study the dependence of the statistical ranking problem on the available pairwise data, i.e., pairs (i,j) for which the pairwise comparison data y_ij is known, and propose a framework to identify data which, when augmented with the current dataset, maximally increases the Fisher information of the ranking. Under certain assumptions, the data collection problem decouples, reducing to a problem of finding an edge set on the graph (with a fixed number of edges) such that the  second eigenvalue of the graph Laplacian is maximal. This reduction of the data collection problem to a spectral graph-theoretic question is one of the primary contributions of this work. As an application, we study the Yahoo! Movie user rating dataset and demonstrate that the addition of a small number of well-chosen pairwise comparisons can significantly increase the Fisher informativeness of the ranking.
Temporal Difference Methods for the Variance of the Reward To Go
Authors: Aviv Tamar, Dotan Di Castro, Shie Mannor
Published in: Proceedings of the 30th International Conference on Machine Learning (Main Conference Track), 2013

Abstract: In this paper we extend temporal difference policy evaluation algorithms to performance criteria that include the variance of the cumulative reward. Such criteria are useful for risk management, and are important in domains such as finance and process control. We propose variants of both TD(0) and LSTD(λ) with linear function approximation, prove their convergence, and demonstrate their utility in a 4-dimensional continuous state space problem.
Online Feature Selection for Model-based Reinforcement Learning
Authors: Trung Nguyen, Zhuoru Li, Tomi Silander, Tze Yun Leong
Published in: Proceedings of the 30th International Conference on Machine Learning (Main Conference Track), 2013

Abstract: We propose a new framework for learning the world dynamics of feature-rich environments in model-based reinforcement learning. The main idea is formalized as a new, factored state-transition representation that supports efficient online-learning of the relevant features. We construct the transition models through predicting how the actions change the world. We introduce an online sparse coding learning technique for feature selection in high-dimensional spaces. We derive theoretical guarantees for our framework and empirically demonstrate its practicality in both simulated and real robotics domains.
$∝$SVM for Learning with Label Proportions
Authors: Felix Yu, Dong Liu, Sanjiv Kumar, Jebara Tony, Shih-Fu Chang
Published in: Proceedings of the 30th International Conference on Machine Learning (Main Conference Track), 2013

Abstract: We study the problem of learning with label proportions in which the training data is provided in groups and only the proportion of each class in each group is known. We propose a new method called proportion-SVM, or ∝SVM, which explicitly models the latent unknown instance labels together with the known group label proportions in a large-margin framework. Unlike the existing works, our approach avoids making restrictive assumptions about the data. The ∝SVM model leads to a non-convex integer programming problem. In order to solve it efficiently, we propose two algorithms: one based on simple alternating optimization and the other based on a convex relaxation. Extensive experiments on standard datasets show that ∝SVM outperforms the state-of-the-art, especially for larger group sizes.
ELLA: An Efficient Lifelong Learning Algorithm
Authors: Paul Ruvolo, Eric Eaton
Published in: Proceedings of the 30th International Conference on Machine Learning (Main Conference Track), 2013

Abstract: The problem of learning multiple consecutive tasks, known as lifelong learning, is of great importance to the creation of intelligent, general-purpose, and flexible machines.  In this paper, we develop a method for online multi-task learning in the lifelong learning setting.  The proposed Efficient Lifelong Learning Algorithm (ELLA) maintains a sparsely shared basis for all task models, transfers knowledge from the basis to learn each new task, and refines the basis over time to maximize performance across all tasks. We show that ELLA has strong connections to both online dictionary learning for sparse coding and state-of-the-art batch multi-task learning methods, and provide robust theoretical performance guarantees.  We show empirically that ELLA yields nearly identical performance to batch multi-task learning while learning tasks sequentially in three orders of magnitude (over 1,000x) less time.
Parameter Learning and Convergent Inference for Dense Random Fields
Authors: Philipp Kraehenbuehl, Vladlen Koltun
Published in: Proceedings of the 30th International Conference on Machine Learning (Main Conference Track), 2013

Abstract: Dense random fields are models in which all pairs of variables are directly connected by pairwise potentials. It has recently been shown that mean field inference in dense random fields can be performed efficiently and that these models enable significant accuracy gains in computer vision applications. However, parameter estimation for dense random fields is still poorly understood. In this paper, we present an efficient algorithm for learning parameters in dense random fields. All parameters are estimated jointly, thus capturing dependencies between them. We show that gradients of a variety of loss functions over the mean field marginals can be computed efficiently. The resulting algorithm learns parameters that directly optimize the performance of mean field inference in the model.  As a supporting result, we present an efficient inference algorithm for dense random fields that is guaranteed to converge.
A Structural SVM Based Approach for Optimizing Partial AUC
Authors: Harikrishna Narasimhan, Shivani Agarwal
Published in: Proceedings of the 30th International Conference on Machine Learning (Main Conference Track), 2013

Abstract: The area under the ROC curve (AUC) is a widely used performance measure in machine learning. Increasingly, however, in several applications, ranging from ranking and biometric screening to medical diagnosis, performance is measured not in terms of the full area under the ROC curve, but instead, in terms of the partial area under the ROC curve between two specified false positive rates. In this paper, we develop a structural SVM framework for directly optimizing the partial AUC between any two false positive rates. Our approach makes use of a cutting plane solver along the lines of the structural SVM based approach for optimizing the full AUC developed by Joachims (2005). Unlike the full AUC, where the combinatorial optimization problem needed to find the most violated constraint in the cutting plane solver can be decomposed easily to yield an efficient algorithm, the corresponding optimization problem in the case of partial AUC is harder to decompose. One of our key technical contributions is an efficient algorithm for solving this combinatorial optimization problem that has the same computational complexity as Joachims’ algorithm for optimizing the usual AUC. This allows us to efficiently optimize the partial AUC in any desired false positive range. We demonstrate the approach on a variety of real-world tasks.
Loss-Proportional Subsampling for Subsequent ERM
Authors: Paul Mineiro, Nikos Karampatziakis
Published in: Proceedings of the 30th International Conference on Machine Learning (Main Conference Track), 2013

Abstract: We propose a sampling scheme suitable for reducing a data set prior to  selecting a hypothesis with minimum empirical risk.  The sampling only  considers a subset of the ultimate (unknown) hypothesis set, but can  nonetheless guarantee that the final excess risk will compare favorably  with utilizing the entire original data set. We demonstrate the practical  benefits of our approach on a large dataset which we subsample and  subsequently fit with boosted trees.
Convex Relaxations for Learning Bounded-Treewidth Decomposable Graphs
Authors: K. S. Sesh Kumar, Francis Bach
Published in: Proceedings of the 30th International Conference on Machine Learning (Main Conference Track), 2013

Abstract: We consider the problem of learning the structure of undirected graphical models with bounded treewidth, within the maximum likelihood framework. This is an NP-hard problem and most approaches consider local search techniques. In this paper, we pose it as a combinatorial optimization problem, which is then relaxed to a convex optimization problem that involves searching over the forest and hyperforest polytopes with special structures. A supergradient method is used to solve the dual problem, with a run-time complexity of O(k^3 n^k+2 łog n) for each iteration, where n is the number of variables and k is a bound on the treewidth. We compare our approach to state-of-the-art methods on synthetic datasets and classical benchmarks, showing the gains of the novel convex approach.
Scalable Simple Random Sampling and Stratified Sampling
Authors: Xiangrui Meng
Published in: Proceedings of the 30th International Conference on Machine Learning (Main Conference Track), 2013

Abstract: Analyzing data sets of billions of records has now become a regular task in    many companies and institutions.    In the statistical analysis of those massive data sets, sampling generally    plays a very important role.    In this work, we describe a scalable simple random sampling algorithm, named    ScaSRS, which uses probabilistic thresholds to decide on the fly whether to    accept, reject, or wait-list an item independently of others.    We prove, with high probability, it succeeds and needs only O(\sqrtk)    storage, where k is the sample size.    ScaSRS extends naturally to a scalable stratified sampling algorithm, which is    favorable for heterogeneous data sets.    The proposed algorithms, when implemented in MapReduce, can effectively reduce    the size of intermediate output and greatly improve load balancing.    Empirical evaluation on large-scale data sets clearly demonstrates their    superiority.
Adaptive Task Assignment for Crowdsourced Classification
Authors: Chien-Ju Ho, Shahin Jabbari, Jennifer Wortman Vaughan
Published in: Proceedings of the 30th International Conference on Machine Learning (Main Conference Track), 2013

Abstract: Crowdsourcing markets have gained popularity as a tool for inexpensively collecting data from diverse populations of workers. Classification tasks, in which workers provide labels (such as “offensive” or “not offensive”) for instances (such as websites), are among the most common tasks posted, but due to a mix of human error and the overwhelming prevalence of spam, the labels collected are often noisy. This problem is typically addressed by collecting labels for each instance from multiple workers and combining them in a clever way. However, the question of how to choose which tasks to assign to each worker is often overlooked. We investigate the problem of task assignment and label inference for heterogeneous classification tasks. By applying online primal-dual techniques, we derive a provably near-optimal adaptive assignment algorithm. We show that adaptively assigning workers to tasks can lead to more accurate predictions at a lower cost when the available workers are diverse.
Riemannian Similarity Learning
Authors: Li Cheng
Published in: Proceedings of the 30th International Conference on Machine Learning (Main Conference Track), 2013

Abstract: We consider a similarity-score based paradigm to address scenarios where either the class labels are only partially revealed during learning, or the training and testing data are drawn from heterogeneous sources. The learning problem is subsequently formulated as optimization over a bilinear form of fixed rank. Our paradigm bears similarity to metric learning, where the major difference lies in its aim of learning a rectangular similarity matrix, instead of a proper metric. We tackle this problem in a Riemannian optimization framework. In particular, we consider its applications in pairwise-based action recognition, and cross-domain image-based object recognition. In both applications, the proposed algorithm produces competitive performance on respective benchmark datasets.
Optimal Regret Bounds for  Selecting the State Representation in Reinforcement Learning
Authors: Odalric-Ambrym Maillard, Phuong Nguyen, Ronald Ortner, Daniil Ryabko
Published in: Proceedings of the 30th International Conference on Machine Learning (Main Conference Track), 2013

Abstract: We consider an agent interacting with an environment in a single stream of actions, observations, and rewards, with no reset. This process is not assumed to be a Markov Decision Process (MDP). Rather, the agent has several representations (mapping histories of past interactions to a discrete state space) of the environment with unknown dynamics, only some of which result in an MDP. The goal is to minimize the average regret criterion against an agent who knows   an MDP representation giving the highest optimal reward, and acts optimally in it. Recent regret bounds for this setting are of order O(T^2/3) with an additive term constant yet exponential in some characteristics of the optimal MDP.  We propose an algorithm whose regret after T time steps is O(\sqrtT),  with all constants reasonably small.  This is optimal in T since O(\sqrtT) is the optimal regret in the setting of learning in a (single discrete) MDP.
On Compact Codes for Spatially Pooled Features
Authors: Yangqing Jia, Oriol Vinyals, Trevor Darrell
Published in: Proceedings of the 30th International Conference on Machine Learning (Main Conference Track), 2013

Abstract: Feature encoding with an overcomplete dictionary has demonstrated good performance in many applications, especially computer vision. In this paper we analyze the classification accuracy with respect to dictionary size by linking the encoding stage to kernel methods and \nystrom sampling, and obtain useful bounds on accuracy as a function of size. The \nystrom method also inspires us to revisit dictionary learning from local patches, and we propose to learn the dictionary in an end-to-end fashion taking into account pooling, a common computational layer in vision. We validate our contribution by showing how the derived bounds are able to explain the observed behavior of multiple datasets, and show that the pooling aware method efficiently reduces the dictionary size by a factor of two for a given accuracy.
Better Mixing via Deep Representations
Authors: Yoshua Bengio, Gregoire Mesnil, Yann Dauphin, Salah Rifai
Published in: Proceedings of the 30th International Conference on Machine Learning (Main Conference Track), 2013

Abstract: It has been hypothesized, and supported with experimental evidence, that deeper representations, when well trained, tend to do a better job at disentangling the underlying factors of variation.  We study the following related conjecture: better representations, in the sense of better disentangling, can be exploited to produce Markov chains that mix faster between modes. Consequently, mixing between modes would be more efficient at higher levels of representation.  To better understand this, we propose a secondary conjecture: the higher-level samples fill more uniformly the space they occupy and the high-density manifolds tend to unfold when represented at higher levels.  The paper discusses these hypotheses and tests them experimentally through visualization and measurements of mixing between modes and interpolating between samples.