mtybilly/Instruct2DS huggingface dataset:
Buffer k-d Trees: Processing Massive Nearest Neighbor Queries on GPUs
Authors: Fabian Gieseke, Justin Heinermann, Cosmin Oancea, Christian Igel
Published in: Proceedings of the 31st International Conference on Machine Learning (Main Conference Track), 2014

Abstract: We present a new approach for combining k-d trees and graphics processing units for nearest neighbor search. It is well known that a direct combination of these tools leads to a non-satisfying performance due to conditional computations and suboptimal memory accesses. To alleviate these problems, we propose a variant of the classical k-d tree data structure, called buffer k-d tree, which can be used to reorganize the search. Our experiments show that we can take advantage of both the hierarchical subdivision induced by k-d trees and the huge computational resources provided by today’s many-core devices. We demonstrate the potential of our approach in astronomy, where hundreds of million nearest neighbor queries have to be processed.
Scaling Up Robust MDPs using Function Approximation
Authors: Aviv Tamar, Shie Mannor, Huan Xu
Published in: Proceedings of the 31st International Conference on Machine Learning (Main Conference Track), 2014

Abstract: We consider large-scale Markov decision processes (MDPs) with parameter uncertainty, under the robust MDP paradigm. Previous studies showed that robust MDPs, based on a minimax approach to handling uncertainty, can be solved using dynamic programming for small to medium sized problems. However, due to the "curse of dimensionality", MDPs that model real-life problems are typically prohibitively large for such approaches. In this work we employ a reinforcement learning approach to tackle this planning problem: we develop a robust approximate dynamic programming method based on a projected fixed point equation to approximately solve large scale robust MDPs. We show that the proposed method provably succeeds under certain technical conditions, and demonstrate its effectiveness through simulation of an option pricing problem. To the best of our knowledge, this is the first attempt to scale up the robust MDP paradigm.
Austerity in MCMC Land: Cutting the Metropolis-Hastings Budget
Authors: Anoop Korattikara, Yutian Chen, Max Welling
Published in: Proceedings of the 31st International Conference on Machine Learning (Main Conference Track), 2014

Abstract: Can we make Bayesian posterior MCMC sampling more efficient when faced with very large datasets? We argue that computing the likelihood for N datapoints in the Metropolis-Hastings (MH) test to reach a single binary decision is computationally inefficient. We introduce an approximate MH rule based on a sequential hypothesis test that allows us to accept or reject samples with high confidence using only a fraction of the data required for the exact MH rule. While this method introduces an asymptotic bias, we show that this bias can be controlled and is more than offset by a decrease in variance due to our ability to draw more samples per unit of time.
Marginal Structured SVM with Hidden Variables
Authors: Wei Ping, Qiang Liu, Alex Ihler
Published in: Proceedings of the 31st International Conference on Machine Learning (Main Conference Track), 2014

Abstract: In this work, we propose the marginal structured SVM (MSSVM) for structured prediction with hidden variables. MSSVM properly accounts for the uncertainty of hidden variables, and can significantly outperform the previously proposed latent structured SVM (LSSVM; Yu & Joachims (2009)) and other state-of-art methods, especially when that uncertainty is large. Our method also results in a smoother objective function, making gradient-based optimization of MSSVMs converge significantly faster than for LSSVMs. We also show that our method consistently outperforms hidden conditional random fields (HCRFs; Quattoni et al. (2007)) on both simulated and real-world datasets. Furthermore, we propose a unified framework that includes both our and several other existing methods as special cases, and provides insights into the comparison of different models in practice.
Understanding the Limiting Factors of Topic Modeling via Posterior Contraction Analysis
Authors: Jian Tang, Zhaoshi Meng, Xuanlong Nguyen, Qiaozhu Mei, Ming Zhang
Published in: Proceedings of the 31st International Conference on Machine Learning (Main Conference Track), 2014

Abstract: Topic models such as the latent Dirichlet allocation (LDA) have become a standard staple in the modeling toolbox of machine learning. They have been applied to a vast variety of data sets, contexts, and tasks to varying degrees of success. However, to date there is almost no formal theory explicating the LDA’s behavior, and despite its familiarity there is very little systematic analysis of and guidance on the properties of the data that affect the inferential performance of the model. This paper seeks to address this gap, by providing a systematic analysis of factors which characterize the LDA’s performance.  We present theorems elucidating the posterior contraction rates of the topics as the amount of data increases, and a thorough supporting empirical study using synthetic and real data sets, including news and web-based articles and tweet messages. Based on these results we provide practical guidance on how to identify suitable data sets for topic models, and how to specify particular model parameters.
Linear and Parallel Learning of Markov Random Fields
Authors: Yariv Mizrahi, Misha Denil, Nando De Freitas
Published in: Proceedings of the 31st International Conference on Machine Learning (Main Conference Track), 2014

Abstract: We introduce a new embarrassingly parallel parameter learning algorithm for Markov random fields which is efficient for a large class of practical models.  Our algorithm parallelizes naturally over cliques and, for graphs of bounded degree, its complexity is linear in the number of cliques. Unlike its competitors, our algorithm is fully parallel and for log-linear models it is also data efficient, requiring only the local sufficient statistics of the data to estimate parameters.
The Inverse Regression Topic Model
Authors: Maxim Rabinovich, David Blei
Published in: Proceedings of the 31st International Conference on Machine Learning (Main Conference Track), 2014

Abstract: i̧tettaddy13mnir proposed multinomial inverse regression (MNIR) as a new model of annotated text based on the influence of metadata and response variables on the distribution of words in a document. While effective, MNIR has no way to exploit structure in the corpus to improve its predictions or facilitate exploratory data analysis. On the other hand, traditional probabilistic topic models (like latent Dirichlet allocation) capture natural heterogeneity in a collection but do not account for external variables. In this paper, we introduce the inverse regression topic model (IRTM), a mixed-membership extension of MNIR that combines the strengths of both methodologies. We present two inference algorithms for the IRTM: an efficient batch estimation  algorithm and an online variant, which is suitable for large corpora.  We apply these methods to a corpus of 73K Congressional press releases  and another of 150K Yelp reviews, demonstrating that the IRTM  outperforms both MNIR and supervised topic models on the prediction task.  Further, we give examples showing that the IRTM enables systematic  discovery of in-topic lexical variation, which is not possible with previous supervised topic models.
Pitfalls in the use of Parallel Inference for the Dirichlet Process
Authors: Yarin Gal, Zoubin Ghahramani
Published in: Proceedings of the 31st International Conference on Machine Learning (Main Conference Track), 2014

Abstract: Recent work done by Lovell, Adams, and Mansingka (2012) and Williamson, Dubey, and Xing (2013) has suggested an alternative parametrisation for the Dirichlet process in order to derive non-approximate parallel MCMC inference for it - work which has been picked-up and implemented in several different fields. In this paper we show that the approach suggested is impractical due to an extremely unbalanced distribution of the data. We characterise the requirements of efficient parallel inference for the Dirichlet process and show that the proposed inference fails most of these requirements (while approximate approaches often satisfy most of them). We present both theoretical and experimental evidence, analysing the load balance for the inference and showing that it is independent of the size of the dataset and the number of nodes available in the parallel implementation. We end with suggestions of alternative paths of research for efficient non-approximate parallel inference for the Dirichlet process.
A Consistent Histogram Estimator for Exchangeable Graph Models
Authors: Stanley Chan, Edoardo Airoldi
Published in: Proceedings of the 31st International Conference on Machine Learning (Main Conference Track), 2014

Abstract: Exchangeable graph models (ExGM) subsume a number of popular network models. The mathematical object that characterizes an ExGM is  termed a graphon. Finding scalable estimators of graphons, provably consistent, remains an open issue. In this paper, we propose a histogram estimator of a graphon that is provably consistent and numerically efficient. The proposed estimator is based on a sorting-and-smoothing (SAS) algorithm, which first sorts the empirical degree of a graph, then smooths the sorted graph using total variation minimization. The consistency of the SAS algorithm is proved by leveraging  sparsity concepts from compressed sensing.
Optimal PAC Multiple Arm Identification with Applications to Crowdsourcing
Authors: Yuan Zhou, Xi Chen, Jian Li
Published in: Proceedings of the 31st International Conference on Machine Learning (Main Conference Track), 2014

Abstract: We study the problem of selecting K arms with the highest expected rewards in a stochastic N-armed bandit game.  Instead of using existing evaluation metrics  (e.g.,  misidentification probability or the metric in EXPLORE-K), we propose to use the aggregate regret, which is defined as the gap between the average reward of the optimal solution and that of our solution. Besides being a natural metric by itself, we argue that in many applications, such as our motivating example from crowdsourcing, the aggregate regret bound is more suitable. We propose a new PAC algorithm, which,  with  probability at least 1-δ, identifies a set of K arms with regret at most ε. We provide the sample complexity bound of our algorithm. To complement, we establish the  lower bound and show that the sample complexity of our algorithm matches the lower bound. Finally, we report experimental results on both synthetic and real data sets, which demonstrates the superior performance of the proposed algorithm.
Latent Variable Copula Inference for Bundle Pricing from Retail Transaction Data
Authors: Benjamin Letham, Wei Sun, Anshul Sheopuri
Published in: Proceedings of the 31st International Conference on Machine Learning (Main Conference Track), 2014

Abstract: Bundle discounts are used by retailers in many industries. Optimal bundle pricing requires learning the joint distribution of consumer valuations for the items in the bundle, that is, how much they are willing to pay for each of the items. We suppose that a retailer has sales transaction data, and the corresponding consumer valuations are latent variables. We develop a statistically consistent and computationally tractable inference procedure for fitting a copula model over correlated valuations, using only sales transaction data for the individual items. Simulations and data experiments demonstrate consistency, scalability, and the importance of incorporating correlations in the joint distribution.
Deep Generative Stochastic Networks Trainable by Backprop
Authors: Yoshua Bengio, Eric Laufer, Guillaume Alain, Jason Yosinski
Published in: Proceedings of the 31st International Conference on Machine Learning (Main Conference Track), 2014

Abstract: We introduce a novel training principle for probabilistic models that is an alternative to maximum likelihood. The proposed Generative Stochastic Networks (GSN) framework is based on learning the transition operator of a Markov chain whose stationary distribution estimates the data distribution.  Because the transition distribution is a conditional distribution generally involving a small move, it has fewer dominant modes, being unimodal in the limit of small moves. Thus, it is easier to learn, more like learning to perform supervised function approximation, with gradients that can be obtained by backprop. The theorems provided here generalize recent work on the probabilistic interpretation of denoising autoencoders and provide an interesting justification for dependency networks and generalized pseudolikelihood (along with defining an appropriate joint distribution and sampling mechanism, even when the conditionals are not consistent). GSNs can be used with missing inputs and can be used to sample subsets of variables given the rest.  Successful experiments are conducted, validating these theoretical results, on two image datasets and with a particular architecture that mimics the Deep Boltzmann Machine Gibbs sampler but allows training to proceed with backprop, without the need for layerwise pretraining.
Towards Minimax Online Learning with Unknown Time Horizon
Authors: Haipeng Luo, Robert Schapire
Published in: Proceedings of the 31st International Conference on Machine Learning (Main Conference Track), 2014

Abstract: We consider online learning when the time horizon is unknown. We apply a minimax analysis, beginning with the fixed horizon case, and then moving on to two unknown-horizon settings, one that assumes the horizon is chosen randomly according to some distribution, and the other which allows the adversary full control over the horizon. For the random horizon setting with restricted losses, we derive a fully optimal minimax algorithm. And for the adversarial horizon setting, we prove a nontrivial lower bound which shows that the adversary obtains strictly more power than when the horizon is fixed and known. Based on the minimax solution of the random horizon setting, we then propose a new adaptive algorithm which “pretends” that the horizon is drawn from a distribution from a special family, but no matter how the actual horizon is chosen,  the worst-case regret is of the optimal rate. Furthermore, our algorithm can be combined and applied in many ways, for instance, to online convex optimization, follow the perturbed leader, exponential weights algorithm and first order bounds. Experiments show that our algorithm outperforms many other existing algorithms in an online linear optimization setting.
A Highly Scalable Parallel Algorithm for Isotropic Total Variation Models
Authors: Jie Wang, Qingyang Li, Sen Yang, Wei Fan, Peter Wonka, Jieping Ye
Published in: Proceedings of the 31st International Conference on Machine Learning (Main Conference Track), 2014

Abstract: Total variation (TV) models are among the most popular and successful tools in signal processing. However, due to the complex nature of the TV term, it is challenging to efficiently compute a solution for large-scale problems. State-of-the-art algorithms that are based on the alternating direction method of multipliers (ADMM)  often involve solving large-size linear systems. In this paper, we propose a highly scalable parallel algorithm for TV models that is based on a novel decomposition strategy of the problem domain. As a result, the TV models can be decoupled into a set of small and independent subproblems, which admit closed form solutions. This makes our approach particularly suitable for parallel implementation. Our algorithm is guaranteed to converge to its global minimum. With N variables and n_p processes, the time complexity is O(N/(εn_p)) to reach an epsilon-optimal solution. Extensive experiments demonstrate that our approach outperforms existing state-of-the-art algorithms, especially in dealing with high-resolution, mega-size images.
Factorized Point Process Intensities: A Spatial Analysis of Professional Basketball
Authors: Andrew Miller, Luke Bornn, Ryan Adams, Kirk Goldsberry
Published in: Proceedings of the 31st International Conference on Machine Learning (Main Conference Track), 2014

Abstract: We develop a machine learning approach to represent and analyze the underlying spatial structure that governs shot selection among professional basketball players in the NBA.  Typically, NBA players are discussed and compared in an heuristic, imprecise manner that relies on unmeasured intuitions about player behavior.  This makes it difficult to draw comparisons between players and make accurate player specific predictions.  Modeling shot attempt data as a point process, we create a low dimensional representation of offensive player types in the NBA.  Using non-negative matrix factorization (NMF), an unsupervised dimensionality reduction technique, we show that a low-rank spatial decomposition summarizes the shooting habits of NBA players.  The spatial representations discovered by the algorithm correspond to intuitive descriptions of NBA player types, and can be used to model other spatial effects, such as shooting accuracy.
Statistical-Computational Phase Transitions in Planted Models: The High-Dimensional Setting
Authors: Yudong Chen, Jiaming Xu
Published in: Proceedings of the 31st International Conference on Machine Learning (Main Conference Track), 2014

Abstract: The planted models assume that a graph is generated from some unknown clusters by randomly placing edges between nodes according to their cluster memberships; the task is to recover the clusters given the graph. Special cases include planted clique, planted partition, planted densest subgraph and planted coloring. Of particular interest is the High-Dimensional setting where the number of clusters is allowed to grow with the number of nodes. We show that the space of model parameters can be partitioned into four disjoint regions corresponding to decreasing statistical and computational complexities: (1) the impossible regime, where all algorithms fail; (2) the hard regime, where the exponential-time Maximum Likelihood Estimator (MLE) succeeds, and no polynomial-time method is known; (3) the easy regime, where the polynomial-time convexified MLE succeeds; (4) the simple regime, where a simple counting/thresholding procedure succeeds. Moreover, each of these algorithms provably fails in the previous harder regimes. Our theorems establish the first minimax recovery results for the high-dimensional setting, and provide the best known guarantees for polynomial-time algorithms. Our results extend to the related problem of submatrix localization, a.k.a. bi-clustering. These results demonstrate the tradeoffs between statistical and computational considerations.
Margins, Kernels and Non-linear Smoothed Perceptrons
Authors: Aaditya Ramdas, Javier Peña
Published in: Proceedings of the 31st International Conference on Machine Learning (Main Conference Track), 2014

Abstract: We focus on the problem of finding a non-linear classification function that lies in a Reproducing Kernel Hilbert Space (RKHS) both from the primal point of view (finding a perfect separator when one exists) and the dual point of view (giving a certificate of non-existence), with special focus on generalizations of two classical schemes - the Perceptron (primal) and Von-Neumann (dual) algorithms.   We cast our problem as one of maximizing the regularized normalized hard-margin (ρ) in an RKHS and use the Representer Theorem to  rephrase it in terms of a Mahalanobis dot-product/semi-norm associated with the kernel’s (normalized and signed) Gram matrix. We derive an accelerated smoothed algorithm with a convergence rate of \tfrac\sqrt łog nρ given n separable points, which is strikingly similar to the classical kernelized Perceptron algorithm whose rate is \tfrac1ρ^2. When no such classifier exists, we prove a version of Gordan’s separation theorem for RKHSs, and give a reinterpretation of negative margins. This allows us to give guarantees for a primal-dual algorithm that halts in \min\tfrac\sqrt n|ρ|, \tfrac\sqrt nε iterations with a perfect separator in the RKHS if the primal is feasible or a dual ε-certificate of near-infeasibility.
Gaussian Process Optimization with Mutual Information
Authors: Emile Contal, Vianney Perchet, Nicolas Vayatis
Published in: Proceedings of the 31st International Conference on Machine Learning (Main Conference Track), 2014

Abstract: In this paper, we analyze a generic algorithm scheme for sequential global optimization using Gaussian processes. The upper bounds we derive on the cumulative regret for this generic algorithm improve by an exponential factor the previously known bounds for algorithms like GP-UCB. We also introduce the novel Gaussian Process Mutual Information algorithm (GP-MI), which significantly improves further these upper bounds for the cumulative regret. We confirm the efficiency of this algorithm on synthetic and real tasks against the natural competitor, GP-UCB, and also the Expected Improvement heuristic.
Robust RegBayes: Selectively Incorporating First-Order Logic Domain Knowledge into Bayesian Models
Authors: Shike Mei, Jun Zhu, Jerry Zhu
Published in: Proceedings of the 31st International Conference on Machine Learning (Main Conference Track), 2014

Abstract: Much research in Bayesian modeling has been done to elicit a prior distribution that incorporates domain knowledge. We present a novel and more direct approach by imposing First-Order Logic (FOL) rules on the posterior distribution. Our approach unifies FOL and Bayesian modeling under the regularized Bayesian framework. In addition, our approach automatically estimates the uncertainty of FOL rules when they are produced by humans, so that reliable rules are incorporated while unreliable ones are ignored. We apply our approach to latent topic modeling tasks and demonstrate that by combining FOL knowledge and Bayesian modeling, we both improve the task performance and discover more structured latent representations in unsupervised and supervised learning.
Aggregating  Ordinal Labels from Crowds by Minimax Conditional Entropy
Authors: Dengyong Zhou, Qiang Liu, John Platt, Christopher Meek
Published in: Proceedings of the 31st International Conference on Machine Learning (Main Conference Track), 2014

Abstract: We propose a method to aggregate noisy ordinal labels collected from a crowd of workers or annotators.  Eliciting ordinal labels is important in tasks such as judging web search quality and consumer satisfaction. Our method is  motivated by the observation that workers usually have difficulty distinguishing between two adjacent ordinal classes whereas distinguishing between two classes which are far away from each other is much easier. We develop the method  through  minimax conditional entropy subject to constraints which encode this observation. Empirical  evaluations on real datasets demonstrate significant improvements over existing methods.
Learning Theory and Algorithms for revenue optimization in second price auctions with reserve
Authors: Mehryar Mohri, Andres Munoz Medina
Published in: Proceedings of the 31st International Conference on Machine Learning (Main Conference Track), 2014

Abstract: Second-price auctions with reserve play a critical role for    modern search engine and popular online sites since the revenue of   these companies often directly depends on the outcome of such   auctions. The choice of the reserve price is the main mechanism   through which the auction revenue can be influenced in these   electronic markets. We cast the problem of selecting the reserve   price to optimize revenue as a learning problem and present a full   theoretical analysis dealing with the complex properties of the   corresponding loss function (it is non-convex and discontinuous). We further give novel algorithms for solving this problem and report the results of encouraging experiments   demonstrating their effectiveness.
Exchangeable Variable Models
Authors: Mathias Niepert, Pedro Domingos
Published in: Proceedings of the 31st International Conference on Machine Learning (Main Conference Track), 2014

Abstract: A sequence of random variables is exchangeable if its joint distribution is invariant under variable permutations. We introduce exchangeable variable models (EVMs) as a novel class of probabilistic models whose basic building blocks are partially exchangeable sequences, a generalization of exchangeable sequences. We prove that a family of tractable EVMs is optimal under zero-one loss for a large class of functions, including parity and threshold functions, and strictly subsumes existing tractable independence-based model families. Extensive experiments show that EVMs outperform state of the art classifiers such as SVMs and  probabilistic models which are solely based on independence assumptions.
Low-density Parity Constraints for Hashing-Based Discrete Integration
Authors: Stefano Ermon, Carla Gomes, Ashish Sabharwal, Bart Selman
Published in: Proceedings of the 31st International Conference on Machine Learning (Main Conference Track), 2014

Abstract: In recent years, a number of probabilistic inference and counting techniques have been proposed that exploit pairwise independent hash functions to infer properties of succinctly defined high-dimensional sets. While providing desirable statistical guarantees, typical constructions of such hash functions are themselves not amenable to efficient inference. Inspired by the success of LDPC codes, we propose the use of low-density parity constraints to make inference more tractable in practice. While not strongly universal, we show that such sparse constraints belong to a new class of hash functions that we call Average Universal. These weaker hash functions retain the desirable statistical guarantees needed by most such probabilistic inference methods. Thus, they continue to provide provable accuracy guarantees while at the same time making a number of algorithms significantly more scalable in practice. Using this technique, we provide new, tighter bounds for challenging discrete integration and model counting problems.
Clustering in the Presence of Background Noise
Authors: Shai Ben-David, Nika Haghtalab
Published in: Proceedings of the 31st International Conference on Machine Learning (Main Conference Track), 2014

Abstract: We address the problem of noise management in clustering algorithms. Namely, issues that arise when on top of some cluster structure the data also contains an unstructured set of points. We consider how clustering algorithms can be “robustified" so that they recover the cluster structure in spite of the unstructured part of the input. We introduce some quantitative measures of such robustness that take into account the strength of the embedded cluster structure as well was the mildness of the noise subset. We propose a simple and efficient method to turn any centroid-based clustering algorithm into a noise-robust one, and prove robustness guarantees for our method with respect to these measures. We also prove that more straightforward ways of “robustifying” clustering algorithms fail to achieve similar guarantees.
Prediction with Limited Advice and Multiarmed Bandits with Paid Observations
Authors: Yevgeny Seldin, Peter Bartlett, Koby Crammer, Yasin Abbasi-Yadkori
Published in: Proceedings of the 31st International Conference on Machine Learning (Main Conference Track), 2014

Abstract: We study two problems of online learning under restricted information access. In the first problem, \emphprediction with limited advice, we consider a game of prediction with expert advice, where on each round of the game we query the advice of a subset of M out of N experts. We present an algorithm that achieves O(\sqrt(N/M)Tłn N) regret on T rounds of this game. The second problem, the \emphmultiarmed bandit with paid  observations, is a variant of the adversarial N-armed bandit game, where on round t of the game we can observe the reward of any number of arms, but each observation has a cost c. We present an algorithm that achieves O((cNłn N)^1/3 T^2/3 + \sqrtT łn N) regret on T rounds of this game in the worst case. Furthermore, we present a number of refinements that treat arm- and time-dependent observation costs and achieve lower regret under benign conditions. We present lower bounds that show that, apart from the logarithmic factors, the worst-case regret bounds cannot be improved.
Bayesian Nonparametric Multilevel Clustering with Group-Level Contexts
Authors: Tien Vu Nguyen, Dinh Phung, Xuanlong Nguyen, Swetha Venkatesh, Hung Bui
Published in: Proceedings of the 31st International Conference on Machine Learning (Main Conference Track), 2014

Abstract: We present a Bayesian nonparametric framework for multilevel clustering which utilizes group-level context information to simultaneously discover low-dimensional structures of the group contents and partitions groups into clusters. Using the Dirichlet process as the building block, our model constructs a product base-measure with a nested structure to accommodate content and context observations at multiple levels. The proposed model possesses properties that link the nested Dirichlet processes (nDP) and the Dirichlet process mixture models (DPM) in an interesting way: integrating out all contents results in the DPM over contexts, whereas integrating out group-speciﬁc contexts results in the nDP mixture over content variables. We provide a Polya-urn view of the model and an efﬁcient collapsed Gibbs inference procedure. Extensive experiments on real-world datasets demonstrate the advantage of utilizing context information via our model in both text and image domains.
Safe Screening with Variational Inequalities and Its Application to Lasso
Authors: Jun Liu, Zheng Zhao, Jie Wang, Jieping Ye
Published in: Proceedings of the 31st International Conference on Machine Learning (Main Conference Track), 2014

Abstract: Sparse learning techniques have been routinely used for feature selection as the resulting model usually has a small number of non-zero entries.  Safe screening, which eliminates the features that are guaranteed to have zero coefficients for a certain value of the regularization parameter, is a technique for improving the computational efficiency. Safe screening is gaining increasing attention since 1) solving sparse learning formulations usually has a high computational cost especially when the number of features is large and 2) one needs to try several regularization parameters to select a suitable model. In this paper, we propose an approach called “Sasvi" (Safe screening with variational inequalities). Sasvi makes use of the variational inequality that provides the sufficient and necessary optimality condition for the dual problem. Several existing approaches for Lasso screening can be casted as relaxed versions of the proposed Sasvi, thus Sasvi provides a stronger safe screening rule. We further study the monotone properties of Sasvi for Lasso, based on which a sure removal regularization parameter can be identified for each feature. Experimental results on both synthetic and real data sets are reported to demonstrate the effectiveness of the proposed Sasvi for Lasso screening.
Large-Margin Metric Learning for Constrained Partitioning Problems
Authors: Rémi Lajugie, Francis Bach, Sylvain Arlot
Published in: Proceedings of the 31st International Conference on Machine Learning (Main Conference Track), 2014

Abstract: We consider unsupervised partitioning problems based explicitly or implicitly on the minimization of Euclidean distortions, such as clustering, image or video segmentation, and other change-point detection problems. We emphasize on cases with specific structure, which include many practical situations ranging from mean-based change-point detection to image segmentation problems. We aim at learning a Mahalanobis metric for these unsupervised problems, leading to feature weighting and/or selection. This is done in a supervised way by assuming the availability of several (partially) labeled datasets that share the same metric. We cast the metric learning problem as a large-margin structured prediction problem, with proper definition of regularizers and losses, leading to a convex optimization problem which can be solved efficiently. Our experiments show how learning the metric can significantly improve performance on bioinformatics, video  or image segmentation problems.
Learning the Consistent Behavior of Common Users for Target Node Prediction across Social Networks
Authors: Shan-Hung Wu, Hao-Heng Chien, Kuan-Hua Lin, Philip Yu
Published in: Proceedings of the 31st International Conference on Machine Learning (Main Conference Track), 2014

Abstract: We study the target node prediction problem: given two social networks, identify those nodes/users from one network (called the source network) who are likely to join another (called the target network, with nodes called target nodes). Although this problem can be solved using existing techniques in the field of cross domain classification, we observe that in many real-world situations the cross-domain classifiers perform sub-optimally due to the heterogeneity between source and target networks that prevents the knowledge from being transferred. In this paper, we propose learning the consistent behavior of common users to help the knowledge transfer. We first present the Consistent Incidence Co-Factorization (CICF) for identifying the consistent users, i.e., common users that behave consistently across networks. Then we introduce the Domain-UnBiased (DUB) classifiers that transfer knowledge only through those consistent users. Extensive experiments are conducted and the results show that our proposal copes with heterogeneity and improves prediction accuracy.
Wasserstein Propagation for Semi-Supervised Learning
Authors: Justin Solomon, Raif Rustamov, Leonidas Guibas, Adrian Butscher
Published in: Proceedings of the 31st International Conference on Machine Learning (Main Conference Track), 2014

Abstract: Probability distributions and histograms are natural representations for product ratings, traffic measurements, and other data considered in many machine learning applications.  Thus, this paper introduces a technique for graph-based semi-supervised learning of histograms, derived from the theory of optimal transportation. Our method has several properties making it suitable for this application; in particular, its behavior can be characterized by the moments and shapes of the histograms at the labeled nodes. In addition, it can be used for histograms on non-standard domains like circles, revealing a strategy for manifold-valued semi-supervised learning. We also extend this technique to related problems such as smoothing distributions on graph nodes.
Signal recovery from Pooling Representations
Authors: Joan Bruna Estrach, Arthur Szlam, Yann LeCun
Published in: Proceedings of the 31st International Conference on Machine Learning (Main Conference Track), 2014

Abstract: Pooling operators construct non-linear representations  by cascading a redundant linear transform, followed by   a point-wise nonlinearity and a local aggregation, typically  implemented with a \ell_p norm.   Their efficiency in recognition architectures is based   on their ability to locally contract the input space,   but also on their capacity to retain as much stable information   as possible.  We address this latter question by computing the upper and   lower Lipschitz bounds of \ell_p pooling operators for p=1, 2, ∞as well as their half-rectified equivalents, which give  sufficient conditions for the design of invertible pooling layers.  Numerical experiments on MNIST and image patches confirm that  pooling layers can be inverted with phase recovery algorithms. Moreover,  the regularity of the inverse pooling, controlled by the lower Lipschitz constant,   is empirically verified with a nearest neighbor regression.
Max-Margin Infinite Hidden Markov Models
Authors: Aonan Zhang, Jun Zhu, Bo Zhang
Published in: Proceedings of the 31st International Conference on Machine Learning (Main Conference Track), 2014

Abstract: Infinite hidden Markov models (iHMMs) are nonparametric Bayesian extensions of hidden Markov models (HMMs) with an infinite number of states. Though flexible in describing sequential data, the generative formulation of iHMMs could limit their discriminative ability in sequential prediction tasks. Our paper introduces max-margin infinite HMMs (M2iHMMs), new infinite HMMs that explore the max-margin principle for discriminative learning. By using the theory of Gibbs classifiers and data augmentation, we develop efficient beam sampling algorithms without making restricting mean-field assumptions or truncated approximation. For single variate classification, M2iHMMs reduce to a new formulation of DP mixtures of max-margin machines. Empirical results on synthetic and real data sets show that our methods obtain superior performance than other competitors in both single variate classification and sequential prediction tasks.
PAC-inspired Option Discovery in Lifelong Reinforcement Learning
Authors: Emma Brunskill, Lihong Li
Published in: Proceedings of the 31st International Conference on Machine Learning (Main Conference Track), 2014

Abstract: A key goal of AI is to create lifelong learning agents that can leverage prior experience to improve performance on later tasks. In reinforcement-learning problems, one way to summarize prior experience for future use is through options, which are temporally extended actions (subpolicies) for how to behave. Options can then be used to potentially accelerate learning in new reinforcement learning tasks. In this work, we provide the first formal analysis of the sample complexity, a measure of learning speed, of reinforcement learning with options.  This analysis helps shed light on some interesting  prior empirical results on when and how options may accelerate learning. We then quantify the benefit of options in reducing sample complexity of a lifelong learning agent. Finally, the new theoretical insights inspire a novel option-discovery algorithm that aims at minimizing overall sample complexity in lifelong reinforcement learning.
Efficient Approximation of Cross-Validation for Kernel Methods using Bouligand Influence Function
Authors: Yong Liu, Shali Jiang, Shizhong Liao
Published in: Proceedings of the 31st International Conference on Machine Learning (Main Conference Track), 2014

Abstract: Model selection is one of the key issues both in recent research and application of kernel methods. Cross-validation is a commonly employed and widely accepted model selection criterion. However, it requires multiple times of training the algorithm under consideration, which is computationally intensive. In this paper, we present a novel strategy for approximating the cross-validation based on the Bouligand influence function (BIF), which only requires the solution of the algorithm once. The BIF measures the impact of an infinitesimal small amount of contamination of the original distribution. We first establish the link between the concept of BIF and the concept of cross-validation. The BIF is related to the first order term of a Taylor expansion. Then, we calculate the BIF and higher order BIFs, and apply these theoretical results to approximate the cross-validation error in practice. Experimental results demonstrate that our approximate cross-validation criterion is sound and efficient.
Multi-label Classification via Feature-aware Implicit Label Space Encoding
Authors: Zijia Lin, Guiguang Ding, Mingqing Hu, Jianmin Wang
Published in: Proceedings of the 31st International Conference on Machine Learning (Main Conference Track), 2014

Abstract: To tackle a multi-label classification problem with many classes, recently label space dimension reduction (LSDR) is proposed. It encodes the original label space to a low-dimensional latent space and uses a decoding process for recovery. In this paper, we propose a novel method termed FaIE to perform LSDR via Feature-aware Implicit label space Encoding. Unlike most previous work, the proposed FaIE makes no assumptions about the encoding process and directly learns a code matrix, i.e. the encoding result of some implicit encoding function, and a linear decoding matrix. To learn both matrices, FaIE jointly maximizes the recoverability of the original label space from the latent space, and the predictability of the latent space from the feature space, thus making itself feature-aware. FaIE can also be specified to learn an explicit encoding function, and extended with kernel tricks to handle non-linear correlations between the feature space and the latent space. Extensive experiments conducted on benchmark datasets well demonstrate its effectiveness.
Generalized Exponential Concentration Inequality for Renyi Divergence Estimation
Authors: Shashank Singh, Barnabas Poczos
Published in: Proceedings of the 31st International Conference on Machine Learning (Main Conference Track), 2014

Abstract: Estimating divergences between probability distributions in a consistent way is of great importance in many machine learning tasks. Although this is a fundamental problem in nonparametric statistics, to the best of our knowledge there has been no finite sample exponential inequality convergence bound derived for any divergence estimators. The main contribution of our work is to provide such a bound for an estimator of Renyi divergence for a smooth Holder class of densities on the d-dimensional unit cube. We also illustrate our theoretical results with a numerical experiment.
Scalable Gaussian Process Structured Prediction for Grid Factor Graph Applications
Authors: Sebastien Bratieres, Novi Quadrianto, Sebastian Nowozin, Zoubin Ghahramani
Published in: Proceedings of the 31st International Conference on Machine Learning (Main Conference Track), 2014

Abstract: Structured prediction is an important and well studied problem with many applications across machine learning. GPstruct is a recently proposed structured prediction model that offers appealing properties such as being kernelised, non-parametric, and supporting Bayesian inference (Bratières et al. 2013).   The model places a Gaussian process prior over energy functions which describe relationships between input variables and structured output variables.  However, the memory demand of GPstruct is quadratic in the number of latent variables and training runtime scales cubically.   This prevents GPstruct from being applied to problems involving grid factor graphs, which are prevalent in computer vision and spatial statistics applications.     Here we explore a scalable approach to learning GPstruct models based on ensemble learning, with weak learners (predictors) trained on subsets of the latent variables and bootstrap data, which can easily be distributed.  We show experiments with 4M latent variables on image segmentation.  Our method outperforms widely-used conditional random field models trained with pseudo-likelihood.   Moreover, in image segmentation problems it improves over recent state-of-the-art marginal optimisation methods in terms of predictive performance and uncertainty calibration. Finally, it generalises well on all training set sizes.
Boosting with Online Binary Learners for the Multiclass Bandit Problem
Authors: Shang-Tse Chen, Hsuan-Tien Lin, Chi-Jen Lu
Published in: Proceedings of the 31st International Conference on Machine Learning (Main Conference Track), 2014

Abstract: We consider the problem of online multiclass prediction in the bandit setting. Compared with the full-information setting, in which the learner can receive the true label as feedback after making each prediction, the bandit setting assumes that the learner can only know the correctness of the predicted label. Because the bandit setting is more restricted, it is difficult to design good bandit learners and currently there are not many bandit learners. In this paper, we propose an approach that systematically converts existing online binary classifiers to promising bandit learners with strong theoretical guarantee. The approach matches the idea of boosting, which has been shown to be powerful for batch learning as well as online learning. In particular, we establish the weak-learning condition on the online binary classifiers, and show that the condition allows automatically constructing a bandit learner with arbitrary strength by combining several of those classifiers. Experimental results on several real-world data sets demonstrate the effectiveness of the proposed approach.
Anomaly Ranking as Supervised Bipartite Ranking
Authors: Stephan Clémençon, Sylvain Robbiano
Published in: Proceedings of the 31st International Conference on Machine Learning (Main Conference Track), 2014

Abstract: The Mass Volume (MV) curve is a visual  tool to evaluate the performance of a scoring  function with regard to its capacity to rank  data in the same order as the underlying density function. Anomaly ranking refers to the  unsupervised learning task which consists in  building a scoring function, based on unlabeled data, with a MV curve as low as possible at any point. In this paper, it is proved  that, in the case where the data generating probability distribution has compact support, anomaly ranking is equivalent to (supervised) bipartite ranking, where the goal is  to discriminate between the underlying probability distribution and the uniform distribution with same support. In this situation, the  MV curve can be then seen as a simple transform of the corresponding ROC curve. Exploiting this view, we then show how to use  bipartite ranking algorithms, possibly combined with random sampling, to solve the  MV curve minimization problem. Numerical experiments based on a variety of bipartite ranking algorithms well-documented in  the literature are displayed in order to illustrate the relevance of our approach.
Optimal Budget Allocation: Theoretical Guarantee and Efficient Algorithm
Authors: Tasuku Soma, Naonori Kakimura, Kazuhiro Inaba, Ken-ichi Kawarabayashi
Published in: Proceedings of the 31st International Conference on Machine Learning (Main Conference Track), 2014

Abstract: We consider the budget allocation problem over bipartite influence model proposed by Alon et al. This problem can be viewed as the well-known influence maximization problem with budget constraints.     We first show that this problem and its much more general form  fall into a general setting; namely the monotone submodular function maximization over integer lattice subject to a knapsack constraint.  Our framework includes Alon et al.’s model, even with a competitor and with cost.  We then give a (1-1/e)-approximation algorithm for this more general problem. Furthermore, when influence probabilities are nonincreasing, we obtain a faster (1-1/e)-approximation algorithm, which runs essentially in linear time in the number of nodes. This allows us to implement our algorithm up to almost 10M edges (indeed, our experiments tell us that we can implement our algorithm up to 1 billion edges. It would approximately take us only 500 seconds.).
Hierarchical Quasi-Clustering Methods for Asymmetric Networks
Authors: Gunnar Carlsson, Facundo Mémoli, Alejandro Ribeiro, Santiago Segarra
Published in: Proceedings of the 31st International Conference on Machine Learning (Main Conference Track), 2014

Abstract: This paper introduces hierarchical quasi-clustering methods, a generalization of hierarchical clustering for asymmetric networks where the output structure preserves the asymmetry of the input data. We show that this output structure is equivalent to a finite quasi-ultrametric space and study admissibility with respect to two desirable properties. We prove that a modified version of single linkage is the only admissible quasi-clustering method. Moreover, we show stability of the proposed method and we establish invariance properties fulfilled by it. Algorithms are further developed and the value of quasi-clustering analysis is illustrated with a study of internal migration within United States.