mtybilly/Instruct2DS huggingface dataset:
Computing Parametric Ranking Models via Rank-Breaking
Authors: Hossein Azari Soufiani, David Parkes, Lirong Xia
Published in: Proceedings of the 31st International Conference on Machine Learning (Main Conference Track), 2014

Abstract: Rank breaking is a methodology introduced by Azari Soufiani et al. (2013a) for applying a Generalized Method of Moments (GMM) algorithm to the estimation of parametric ranking models. Breaking takes full rankings and breaks, or splits them up, into counts for pairs of alternatives that occur in particular positions (e.g., first place and second place, second place and third place). GMMs are of interest because they can achieve significant speed-up relative to maximum likelihood approaches and comparable statistical efficiency. We characterize the breakings for which the estimator is consistent for random utility models (RUMs) including Plackett-Luce and Normal-RUM, develop a general sufficient condition for a full breaking to be the only consistent breaking, and provide a trichotomy theorem in regard to single-edge breakings. Experimental results are presented to show the computational efficiency along with statistical performance of the proposed method.
Rectangular Tiling Process
Authors: Masahiro Nakano, Katsuhiko Ishiguro, Akisato Kimura, Takeshi Yamada, Naonori Ueda
Published in: Proceedings of the 31st International Conference on Machine Learning (Main Conference Track), 2014

Abstract: This paper proposes a novel stochastic process that represents the arbitrary rectangular partitioning of an infinite-dimensional matrix as the conditional projective limit. Rectangular partitioning is used in relational data analysis, and is classified into three types: regular grid, hierarchical, and arbitrary. Conventionally, a variety of probabilistic models have been advanced for the first two, including the product of Chinese restaurant processes and the Mondrian process. However, existing models for arbitrary partitioning are too complicated to permit the analysis of the statistical behaviors of models, which places very severe capability limits on relational data analysis. In this paper, we propose a new probabilistic model of arbitrary partitioning called the rectangular tiling process (RTP). Our model has a sound mathematical base in projective systems and infinite extension of conditional probabilities, and is capable of representing partitions of infinite elements as found in ordinary Bayesian nonparametric models.
Tracking Adversarial Targets
Authors: Yasin Abbasi-Yadkori, Peter Bartlett, Varun Kanade
Published in: Proceedings of the 31st International Conference on Machine Learning (Main Conference Track), 2014

Abstract: We study linear control problems with quadratic losses and adversarially chosen tracking targets. We present an efficient algorithm for this problem and show that, under standard conditions on the linear system, its regret with respect to an optimal linear policy grows as O(łog^2 T), where T is the number of rounds of the game.  We also study a problem with adversarially chosen transition dynamics; we present an exponentially-weighted average algorithm for this problem, and we give regret bounds that grow as O(\sqrt T).
Two-Stage Metric Learning
Authors: Jun Wang, Ke Sun, Fei Sha, Stéphane Marchand-Maillet, Alexandros Kalousis
Published in: Proceedings of the 31st International Conference on Machine Learning (Main Conference Track), 2014

Abstract: In this paper, we present a novel two-stage metric learning algorithm. We first map each learning instance to a probability distribution by computing its similarities to a set of fixed anchor points. Then, we define the distance in the input data space as the Fisher information distance on the associated statistical manifold. This induces in the input data space a new family of distance metric which presents unique properties. Unlike kernelized metric learning, we do not require the similarity measure to be positive semi-definite. Moreover, it can also be interpreted as a local metric learning algorithm with well defined distance approximation. We evaluate its performance on a number of datasets. It outperforms significantly other metric learning methods and SVM.
Online Bayesian Passive-Aggressive Learning
Authors: Tianlin Shi, Jun Zhu
Published in: Proceedings of the 31st International Conference on Machine Learning (Main Conference Track), 2014

Abstract: Online Passive-Aggressive (PA) learning is an effective framework for performing max-margin online learning. But the deterministic formulation and estimated single large-margin model could limit its capability in discovering descriptive structures underlying complex data. This paper presents online Bayesian Passive-Aggressive (BayesPA) learning, which subsumes the online PA and extends naturally to incorporate latent variables and perform nonparametric Bayesian inference, thus providing great flexibility for explorative analysis. We apply BayesPA to topic modeling and derive efficient online learning algorithms for max-margin topic models. We further develop nonparametric methods to resolve the number of topics. Experimental results on real datasets show that our approaches significantly improve time efficiency while maintaining comparable results with the batch counterparts.
Stochastic Inference for Scalable Probabilistic Modeling of Binary Matrices
Authors: Jose Miguel Hernandez-Lobato, Neil Houlsby, Zoubin Ghahramani
Published in: Proceedings of the 31st International Conference on Machine Learning (Main Conference Track), 2014

Abstract: Fully observed large binary matrices appear in a wide variety of contexts. To model them, probabilistic matrix factorization (PMF) methods are an attractive solution. However, current batch algorithms for PMF can be inefficient because they need to analyze the entire data matrix before producing any parameter updates. We derive an efficient stochastic inference algorithm for PMF models of fully observed binary matrices. Our method exhibits faster convergence rates than more expensive batch approaches and has better predictive performance than scalable alternatives.  The proposed method includes new data subsampling strategies which produce large gains over standard uniform subsampling. We also address the task  of automatically selecting the size of the minibatches of data used by our method. For this, we derive an algorithm that adjusts this hyper-parameter online.
Deterministic Policy Gradient Algorithms
Authors: David Silver, Guy Lever, Nicolas Heess, Thomas Degris, Daan Wierstra, Martin Riedmiller
Published in: Proceedings of the 31st International Conference on Machine Learning (Main Conference Track), 2014

Abstract: In this paper we consider deterministic policy gradient algorithms for reinforcement learning with continuous actions. The deterministic policy gradient has a particularly appealing form: it is the expected gradient of the action-value function. This simple form means that the deterministic policy gradient can be estimated much more efficiently than the usual stochastic policy gradient. To ensure adequate exploration, we introduce an off-policy actor-critic algorithm that learns a deterministic target policy from an exploratory behaviour policy. Deterministic policy gradient algorithms outperformed their stochastic counterparts in several benchmark problems, particularly in high-dimensional action spaces.
Elementary Estimators for High-Dimensional Linear Regression
Authors: Eunho Yang, Aurelie Lozano, Pradeep Ravikumar
Published in: Proceedings of the 31st International Conference on Machine Learning (Main Conference Track), 2014

Abstract: We consider the problem of structurally constrained high-dimensional linear regression. This has attracted considerable attention over the last decade, with state of the art statistical estimators based on solving regularized convex programs. While these typically non-smooth convex programs can be solved in polynomial time, scaling the state of the art optimization methods to very large-scale problems is an ongoing and rich area of research. In this paper, we attempt to address this scaling issue at the source, by asking whether one can build \emphsimpler possibly closed-form estimators, that yet come with statistical guarantees that are nonetheless comparable to regularized likelihood estimators! We answer this question in the affirmative, with variants of the classical ridge and OLS (ordinary least squares estimators) for linear regression. We analyze our estimators in the high-dimensional setting, and moreover provide empirical corroboration of its performance on simulated as well as real world microarray data.
Modeling Correlated Arrival Events with Latent Semi-Markov Processes
Authors: Wenzhao Lian, Vinayak Rao, Brian Eriksson, Lawrence Carin
Published in: Proceedings of the 31st International Conference on Machine Learning (Main Conference Track), 2014

Abstract: The analysis and characterization of correlated point process data has wide applications, ranging from biomedical research to network analysis. In this work, we model such data as generated by a latent collection of continuous-time binary semi-Markov processes, corresponding to external events appearing and disappearing. A continuous-time modeling framework is more appropriate for multichannel point process data than a binning approach requiring time discretization, and we show connections between our model and recent ideas from the discrete-time literature. We describe an efficient MCMC algorithm for posterior inference, and apply our ideas to both synthetic data and a real-world biometrics application.
Elementary Estimators for Sparse Covariance Matrices and other Structured Moments
Authors: Eunho Yang, Aurelie Lozano, Pradeep Ravikumar
Published in: Proceedings of the 31st International Conference on Machine Learning (Main Conference Track), 2014

Abstract: We consider the problem of estimating distributional parameters that are expected values of given feature functions. We are interested in recovery under high-dimensional regimes, where the number of variables p is potentially larger than the number of samples n, and where we need to impose structural constraints upon the parameters. In a natural distributional setting for this problem, the feature functions comprise the sufficient statistics of an exponential family, so that the problem would entail estimating structured moments of exponential family distributions. A special case of the above involves estimating the covariance matrix of a random vector, and where the natural distributional setting would correspond to the multivariate Gaussian distribution. Unlike the inverse covariance estimation case, we show that the regularized MLEs for covariance estimation, as well as natural Dantzig variants, are \emphnon-convex, even when the regularization functions themselves are convex; with the same holding for the general structured moment case. We propose a class of elementary convex estimators, that in many cases are available in \emphclosed-form, for estimating general structured moments. We then provide a unified statistical analysis of our class of estimators. Finally, we demonstrate the applicability of our class of estimators on real-world climatology and biology datasets.
Towards scaling up Markov chain Monte Carlo: an adaptive subsampling approach 
Authors: Rémi Bardenet, Arnaud Doucet, Chris Holmes
Published in: Proceedings of the 31st International Conference on Machine Learning (Main Conference Track), 2014

Abstract: Markov chain Monte Carlo (MCMC) methods are often deemed far too computationally intensive to be of any practical use for large datasets. This paper describes a methodology that aims to scale up the Metropolis-Hastings (MH) algorithm in this context. We propose an approximate implementation of the accept/reject step of MH that only requires evaluating the likelihood of a random subset of the data, yet is guaranteed to coincide with the accept/reject step based on the full dataset with a probability superior to a user-specified tolerance level. This adaptive subsampling technique is an alternative to the recent approach developed in (Korattikara et al, ICML’14), and it allows us to establish rigorously that the resulting approximate MH algorithm samples from a perturbed version of the target distribution of interest, whose total variation distance to this very target is controlled explicitly. We explore the benefits and limitations of this scheme on several examples.
Graph-based Semi-supervised Learning: Realizing Pointwise Smoothness Probabilistically
Authors: Yuan Fang, Kevin Chang, Hady Lauw
Published in: Proceedings of the 31st International Conference on Machine Learning (Main Conference Track), 2014

Abstract: As the central notion in semi-supervised learning, smoothness is often realized on a graph representation of the data. In this paper, we study two complementary dimensions of smoothness: its pointwise nature and probabilistic modeling. While no existing graph-based work exploits them in conjunction, we encompass both in a novel framework of Probabilistic Graph-based Pointwise Smoothness (PGP), building upon two foundational models of data closeness and label coupling. This new form of smoothness axiomatizes a set of probability constraints, which ultimately enables class prediction. Theoretically, we provide an error and robustness analysis of PGP. Empirically, we conduct extensive experiments to show the advantages of PGP.
Diagnosis determination: decision trees optimizing simultaneously worst and expected testing cost
Authors: Ferdinando Cicalese, Eduardo Laber, Aline Medeiros Saettler
Published in: Proceedings of the 31st International Conference on Machine Learning (Main Conference Track), 2014

Abstract: In several applications of automatic diagnosis  and active learning a central problem is the evaluation of a discrete function by adaptively querying the values of its variables until the values read uniquely determine the value of the function.   In general reading the value of a variable is done at the expense of some cost (computational or possibly a fee to pay the corresponding experiment). The goal is to design a strategy for evaluating the function incurring little cost (in the worst case or in expectation according to a prior distribution on the possible variables’ assignments).  We provide an algorithm that builds a strategy (decision tree) with both expected cost and worst cost which are at most an O(łog n) factor away  from, respectively, the minimum possible expected cost and the minimum possible worst cost.  Our algorithm provides the best possible approximation simultaneously with respect to both criteria. In fact,  there is no algorithm that can guarantee o(łog n) approximation, under the assumption  that a̧l P ≠\ļ NP.
Bayesian Max-margin Multi-Task Learning with Data Augmentation
Authors: Chengtao Li, Jun Zhu, Jianfei Chen
Published in: Proceedings of the 31st International Conference on Machine Learning (Main Conference Track), 2014

Abstract: Both max-margin and Bayesian methods have been extensively studied in multi-task learning, but have rarely been considered together. We present Bayesian max-margin multi-task learning, which conjoins the two schools of methods, thus allowing the discriminative max-margin methods to enjoy the great flexibility of Bayesian methods on incorporating rich prior information as well as performing nonparametric Bayesian feature learning with the latent dimensionality resolved from data. We develop Gibbs sampling algorithms by exploring data augmentation to deal with the non-smooth hinge loss. For nonparametric models, our algorithms do not need to make mean-field assumptions or truncated approximation. Empirical results demonstrate superior performance than competitors in both multi-task classification and regression.
Condensed Filter Tree for Cost-Sensitive Multi-Label Classification
Authors: Chun-Liang Li, Hsuan-Tien Lin
Published in: Proceedings of the 31st International Conference on Machine Learning (Main Conference Track), 2014

Abstract: Different real-world applications of multi-label classification often demand different evaluation criteria. We formalize this demand with a general setup, cost-sensitive multi-label classification (CSMLC), which takes  the evaluation criteria into account during learning. Nevertheless, most existing algorithms can only focus on optimizing a few specific evaluation criteria, and cannot systematically deal with different ones. In this paper, we propose a novel algorithm, called condensed filter tree (CFT), for optimizing any criteria in CSMLC. CFT is derived from reducing CSMLC to the famous filter tree algorithm for cost-sensitive multi-class classification via constructing the label powerset. We successfully cope with the difficulty of having exponentially many extended-classes within the powerset for representation, training and prediction by carefully designing the tree structure and focusing on the key nodes. Experimental results across many real-world datasets validate that CFT is competitive with special purpose algorithms on special criteria and reaches better performance on general criteria.
Sparse Reinforcement Learning via Convex Optimization
Authors: Zhiwei Qin, Weichang Li, Firdaus Janoos
Published in: Proceedings of the 31st International Conference on Machine Learning (Main Conference Track), 2014

Abstract: We propose two new algorithms for the sparse reinforcement learning problem based on different formulations.  The first algorithm is an off-line method based on the alternating direction method of multipliers for solving a constrained formulation that explicitly controls the projected Bellman residual.  The second algorithm is an online stochastic approximation algorithm that employs the regularized dual averaging technique, using the Lagrangian formulation.  The convergence of both algorithms are established. We demonstrate the performance of these algorithms through two classical examples.
On Measure Concentration of Random Maximum A-Posteriori Perturbations
Authors: Francesco Orabona, Tamir Hazan, Anand Sarwate, Tommi Jaakkola
Published in: Proceedings of the 31st International Conference on Machine Learning (Main Conference Track), 2014

Abstract: The maximum a-posteriori (MAP) perturbation framework has emerged as a useful approach for inference and learning in high dimensional complex models.  By maximizing a randomly perturbed potential function, MAP perturbations generate unbiased samples from the Gibbs distribution.  Unfortunately, the computational cost of generating so many high-dimensional random variables can be prohibitive.  More efficient algorithms use sequential sampling strategies based on the expected value of low dimensional MAP perturbations. This paper develops new measure concentration inequalities that bound the number of samples needed to estimate such expected values. Applying the general result to MAP perturbations can yield a more efficient algorithm to approximate sampling from the Gibbs distribution.  The measure concentration result is of general interest and may be applicable to other areas involving Monte Carlo estimation of expectations.
Gaussian Process Classification and Active Learning with Multiple Annotators
Authors: Filipe Rodrigues, Francisco Pereira, Bernardete Ribeiro
Published in: Proceedings of the 31st International Conference on Machine Learning (Main Conference Track), 2014

Abstract: Learning from multiple annotators took a valuable step towards modelling data that does not fit the usual single annotator setting. However, multiple annotators sometimes offer varying degrees of expertise. When disagreements arise, the establishment of the correct label through trivial solutions such as majority voting may not be adequate, since without considering heterogeneity in the annotators, we risk generating a flawed model.   In this paper, we extend GP classification in order to account for multiple annotators with different levels expertise. By explicitly handling uncertainty, Gaussian processes (GPs) provide a natural framework to build proper multiple-annotator models. We empirically show that our model significantly outperforms other commonly used approaches, such as majority voting, without a significant increase in the computational cost of approximate Bayesian inference. Furthermore, an active learning methodology is proposed, which is able to reduce annotation cost even further.
Bias in Natural Actor-Critic Algorithms
Authors: Philip Thomas
Published in: Proceedings of the 31st International Conference on Machine Learning (Main Conference Track), 2014

Abstract: We show that several popular discounted reward natural actor-critics, including the popular NAC-LSTD and eNAC algorithms, do not generate unbiased estimates of the natural policy gradient as claimed. We derive the first unbiased discounted reward natural actor-critics using batch and iterative approaches to gradient estimation. We argue that the bias makes the existing algorithms more appropriate for the average reward setting. We also show that, when Sarsa(lambda) is guaranteed to converge to an optimal policy, the objective function used by natural actor-critics is concave, so policy gradient methods are guaranteed to converge to globally optimal policies as well.
Structured Prediction of Network Response
Authors: Hongyu Su, Aristides Gionis, Juho Rousu
Published in: Proceedings of the 31st International Conference on Machine Learning (Main Conference Track), 2014

Abstract: We introduce the following network response problem: given a complex network and an action, predict the subnetwork that responds to action, that is, which nodes perform the action and which directed edges relay the action to the adjacent nodes.     We approach the problem through max-margin structured learning, in which a compatibility score is learned between the actions and their activated  subnetworks. Thus, unlike the most popular influence network approaches, our method, called SPIN,  is context-sensitive, namely, the presence, the direction and the dynamics of influences depend on the properties of the actions.     The inference problems of finding the highest scoring as well as the worst margin violating networks, are proven to be NP-hard. To solve the problems, we present an approximate inference method through a semi-definite programming relaxation (SDP), as well as a more scalable greedy heuristic algorithm.    In our experiments, we demonstrate that taking advantage of the context given by the actions and the network structure leads SPIN to a markedly better predictive performance over competing methods.
Dimension-free Concentration Bounds on Hankel Matrices for Spectral Learning
Authors: François Denis, Mattias Gybels, Amaury Habrard
Published in: Proceedings of the 31st International Conference on Machine Learning (Main Conference Track), 2014

Abstract: Learning probabilistic models over strings is an important issue for many applications. Spectral methods propose elegant solutions to the problem of inferring weighted automata from finite samples of variable-length strings drawn from an unknown target distribution. These methods rely on a singular value decomposition of a matrix H_S, called the Hankel matrix, that records the frequencies of (some of) the observed strings. The accuracy of the learned distribution depends both on the quantity of information embedded in H_S and on the distance between H_S and its mean H_r. Existing concentration bounds seem to indicate that the concentration over H_r gets looser with its size, suggesting to make a trade-off between the quantity of used information and the size of H_r. We propose new dimension-free concentration bounds for several variants of Hankel matrices. Experiments demonstrate that these bounds are tight and that they significantly improve existing bounds. These results suggest that the concentration rate of the Hankel matrix around its mean does not constitute an argument for limiting its size.
An Analysis of State-Relevance Weights and Sampling Distributions on L1-Regularized Approximate Linear Programming Approximation Accuracy
Authors: Gavin Taylor, Connor Geer, David Piekut
Published in: Proceedings of the 31st International Conference on Machine Learning (Main Conference Track), 2014

Abstract: Recent interest in the use of L_1 regularization in the use of value function approximation includes Petrik et al.’s introduction of L_1-Regularized Approximate Linear Programming (RALP).  RALP is unique among L_1-regularized approaches in that it approximates the optimal value function using off-policy samples.  Additionally, it produces policies which outperform those of previous methods, such as LSPI.  RALP’s value function approximation quality is affected heavily by the choice of state-relevance weights in the objective function of the linear program, and by the distribution from which samples are drawn; however, there has been no discussion of these considerations in the previous literature.  In this paper, we discuss and explain the effects of choices in the state-relevance weights and sampling distribution on approximation quality, using both theoretical and experimental illustrations.  The results provide insight not only onto these effects, but also provide intuition into the types of MDPs which are especially well suited for approximation with RALP.
On Modelling Non-linear Topical Dependencies
Authors: Zhixing Li, Siqiang Wen, Juanzi Li, Peng Zhang, Jie Tang
Published in: Proceedings of the 31st International Conference on Machine Learning (Main Conference Track), 2014

Abstract: Probabilistic topic models such as Latent Dirichlet Allocation (LDA) discover latent topics from large corpora by exploiting words’ co-occurring relation. By observing the topical similarity between words, we find that some other relations, such as semantic or syntax relation between words, lead to strong dependence between their topics. In this paper, sentences are represented as dependency trees and a Global Topic Random Field (GTRF) is presented to model the non-linear dependencies between words. To infer our model, a new global factor is defined over all edges and the normalization factor of GRF is proven to be a constant. As a result, no independent assumption is needed when inferring our model. Based on it, we develop an efficient expectation-maximization (EM) procedure for parameter estimation. Experimental results on four data sets show that GTRF achieves much lower perplexity than LDA and linear dependency topic models and produces better topic coherence.
Optimization Equivalence of Divergences Improves Neighbor Embedding
Authors: Zhirong Yang, Jaakko Peltonen, Samuel Kaski
Published in: Proceedings of the 31st International Conference on Machine Learning (Main Conference Track), 2014

Abstract: Visualization methods that arrange data objects in 2D or 3D layouts have followed two main schools, methods oriented for graph layout and methods oriented for vectorial embedding. We show the two previously separate approaches are tied by an optimization equivalence, making it possible to relate methods from the two approaches and to build new methods that take the best of both worlds.  In detail, we prove a theorem of optimization equivalences between beta- and gamma-, as well as alpha- and Renyi-divergences through a connection scalar. Through the equivalences we represent several nonlinear dimensionality reduction and graph drawing methods in a generalized stochastic neighbor embedding setting, where information divergences are minimized between similarities in input and output spaces, and the optimal connection scalar provides a natural choice for the tradeoff between attractive and repulsive forces. We give two examples of developing new visualization methods through the equivalences: 1) We develop weighted symmetric stochastic neighbor embedding (ws-SNE) from Elastic Embedding and analyze its benefits, good performance for both vectorial and network data; in experiments ws-SNE has good performance across data sets of different types, whereas comparison methods fail for some of the data sets; 2) we develop a gamma-divergence version of a PolyLog layout method; the new method is scale invariant in the output space and makes it possible to efficiently use large-scale smoothed neighborhoods.
A Deep and Tractable Density Estimator
Authors: Benigno Uria, Iain Murray, Hugo Larochelle
Published in: Proceedings of the 31st International Conference on Machine Learning (Main Conference Track), 2014

Abstract: The Neural Autoregressive Distribution Estimator (NADE) and its real-valued version RNADE are competitive density models of multidimensional data across a variety of domains. These models use a fixed, arbitrary ordering of the data  dimensions. One can easily condition on variables at the beginning of the ordering, and marginalize out variables at the end of the ordering, however other inference tasks require approximate inference. In this work we introduce an efficient procedure to simultaneously train a NADE model for each possible ordering of the variables, by sharing parameters across all these models. We can thus use the most convenient model for each inference task at hand, and ensembles of such models with different orderings are immediately available. Moreover, unlike the original NADE, our training procedure scales to deep models. Empirically, ensembles of Deep NADE models obtain state of the art density estimation performance.
An Asynchronous Parallel Stochastic Coordinate Descent Algorithm
Authors: Ji Liu, Steve Wright, Christopher Re, Victor Bittorf, Srikrishna Sridhar
Published in: Proceedings of the 31st International Conference on Machine Learning (Main Conference Track), 2014

Abstract: We describe an asynchronous parallel stochastic coordinate descent algorithm for minimizing smooth unconstrained or separably constrained functions. The method achieves a linear convergence rate on functions that satisfy an essential strong convexity property and a sublinear rate (1/K) on general convex functions. Near-linear speedup on a multicore system can be expected if the number of processors is O(n^1/2) in unconstrained optimization and O(n^1/4) in the separable-constrained case, where n is the number of variables. We  describe results from implementation on 40-core processors.
(Near) Dimension Independent Risk Bounds for Differentially Private Learning
Authors: Prateek Jain, Abhradeep Guha Thakurta
Published in: Proceedings of the 31st International Conference on Machine Learning (Main Conference Track), 2014

Abstract: In this paper, we study the problem of differentially private risk minimization where the goal is to provide differentially private algorithms that have small excess risk. In particular we address the following open problem: \emphIs it possible to design computationally efficient differentially private risk minimizers with  excess risk bounds that do not explicitly depend on dimensionality (p) and do not require  structural assumptions like restricted strong convexity?  In this paper, we answer the question in the affirmative for a variant of the well-known  \emphoutput and \emphobjective perturbation algorithms [Chaudhuri et al., 2011]. In particular, we show that  in generalized linear model, variants of both output and objective perturbation algorithms have no \em explicit dependence on p. Our results assume that the underlying loss function is a 1-Lipschitz convex function and we show that the excess risk depends only on  L_2 norm of the true risk minimizer and that of training points.  Next, we present a novel privacy preserving algorithm for risk minimization over simplex in the generalized linear model, where the loss function is  a doubly differentiable convex function. Assuming that the training points have bounded L_∞-norm, our algorithm provides risk bound that has only \em logarithmic dependence on p. We also apply our technique to the online learning setting and obtain a regret bound with similar logarithmic dependence on p. In contrast, the existing differentially private online learning methods incur O(\sqrtp)  dependence.
Consistency of Causal Inference under the Additive Noise Model
Authors: Samory Kpotufe, Eleni Sgouritsa, Dominik Janzing, Bernhard Schölkopf
Published in: Proceedings of the 31st International Conference on Machine Learning (Main Conference Track), 2014

Abstract: We analyze a family of methods for statistical  causal inference from sample under the so-called  Additive Noise Model. While most work  on the subject has concentrated on establishing  the soundness of the Additive Noise Model, the  statistical consistency of the resulting inference  methods has received little attention. We derive  general conditions under which the given family  of inference methods consistently infers the  causal direction in a nonparametric setting.
Quasi-Monte Carlo Feature Maps for Shift-Invariant Kernels
Authors: Jiyan Yang, Vikas Sindhwani, Haim Avron, Michael Mahoney
Published in: Proceedings of the 31st International Conference on Machine Learning (Main Conference Track), 2014

Abstract: We consider the problem of improving the efficiency of randomized Fourier feature maps to accelerate training and testing speed of kernel methods on large datasets. These approximate feature maps arise as Monte Carlo approximations to integral representations of shift-invariant kernel functions (e.g., Gaussian kernel). In this paper, we propose to use Quasi-Monte Carlo (QMC) approximations instead  where the relevant integrands are evaluated on a low-discrepancy sequence of points as opposed to random point sets as in the Monte Carlo approach. We derive a new discrepancy measure called box discrepancy based on theoretical characterizations of the integration error with respect to a given sequence. We then propose to learn QMC sequences adapted to our setting based on explicit box discrepancy minimization. Our theoretical analyses are complemented with empirical results that demonstrate the effectiveness of classical and adaptive QMC techniques for this problem.
Globally Convergent Parallel MAP LP Relaxation Solver using the Frank-Wolfe Algorithm
Authors: Alexander Schwing, Tamir Hazan, Marc Pollefeys, Raquel Urtasun
Published in: Proceedings of the 31st International Conference on Machine Learning (Main Conference Track), 2014

Abstract: While MAP inference is typically intractable for many real-world applications, linear programming relaxations have been proven very effective. Dual block-coordinate descent methods are among the most efficient solvers, however, they are prone to get stuck in sub-optimal  points. Although subgradient approaches achieve global convergence, they are typically slower in practice. To improve convergence speed, algorithms which compute the steepest ε-descent direction by solving a quadratic program have been proposed. In this paper we suggest to decouple the quadratic program based on the Frank-Wolfe approach. This allows us to obtain an efficient and easy to parallelize algorithm while retaining the global convergence properties. Our method proves superior when compared to existing algorithms on a set of spin-glass models and protein design tasks.
Discriminative Features via Generalized Eigenvectors
Authors: Nikos Karampatziakis, Paul Mineiro
Published in: Proceedings of the 31st International Conference on Machine Learning (Main Conference Track), 2014

Abstract: Representing examples in a way that is compatible with the underlying classifier can greatly enhance the performance of a learning system. In this paper we investigate scalable techniques for inducing discriminative features by taking advantage of simple second order structure in the data. We focus on multiclass classification and show that features extracted from the generalized eigenvectors of the class conditional second moments lead to classifiers with excellent empirical performance. Moreover, these features have attractive theoretical properties, such as inducing representations that are invariant to linear transformations of the input. We evaluate classifiers built from these features on three different tasks, obtaining state of the art results.
Linear Programming for Large-Scale Markov Decision Problems
Authors: Alan Malek, Yasin Abbasi-Yadkori, Peter Bartlett
Published in: Proceedings of the 31st International Conference on Machine Learning (Main Conference Track), 2014

Abstract: We consider the problem of controlling a Markov decision  process (MDP) with a large state space, so as to minimize average cost.  Since it is intractable to compete with the optimal policy for large  scale problems, we pursue the more modest goal of competing with a  low-dimensional family of policies. We use the dual linear programming  formulation of the MDP average cost problem, in which the variable is  a stationary distribution over state-action pairs, and we consider a  neighborhood of a low-dimensional subset of the set of stationary  distributions (defined in terms of state-action features) as  the comparison class.  We propose two techniques, one based on stochastic convex optimization,  and one based on constraint sampling. In both cases, we give bounds  that show that the performance of our algorithms approaches the best  achievable by any policy in the comparison class. Most importantly,  these results depend on the size of the comparison class, but not  on the size of the state space.  Preliminary experiments  show the effectiveness of the proposed algorithms in a queuing  application.
Forward-Backward Greedy Algorithms for General Convex Smooth Functions over A Cardinality Constraint
Authors: Ji Liu, Jieping Ye, Ryohei Fujimaki
Published in: Proceedings of the 31st International Conference on Machine Learning (Main Conference Track), 2014

Abstract: We consider forward-backward greedy algorithms for solving sparse feature selection problems with general convex smooth functions. A state-of-the-art greedy method, the Forward-Backward greedy algorithm (FoBa-obj) requires to solve a large number of optimization problems, thus it is not scalable for large-size problems. The FoBa-gdt algorithm, which uses the gradient information for feature selection at each forward iteration, significantly improves the efficiency of FoBa-obj. In this paper, we systematically analyze the theoretical properties of both algorithms. Our main contributions are: 1) We derive better theoretical bounds than existing analyses regarding FoBa-obj for general smooth convex functions; 2) We show that FoBa-gdt achieves the same theoretical performance as FoBa-obj under the same condition: restricted strong convexity condition. Our new bounds are consistent with the bounds of a special case (least squares) and fills a previously existing theoretical gap for general convex smooth functions; 3) We show that the restricted strong convexity condition is satisfied if the number of independent samples is more than \barkłog d where \bark is the sparsity number and d is the dimension of the variable; 4) We apply FoBa-gdt (with the conditional random field objective) to the sensor selection problem for human indoor activity recognition and our results show that FoBa-gdt outperforms other methods based on forward greedy selection and L1-regularization.
Linear Time Solver for Primal SVM
Authors: Feiping Nie, Yizhen Huang, Heng Huang
Published in: Proceedings of the 31st International Conference on Machine Learning (Main Conference Track), 2014

Abstract: Support Vector Machines (SVM) is among the most popular classification techniques in machine learning, hence designing fast primal SVM algorithms for large-scale datasets is a hot topic in recent years. This paper presents a new L2-norm regularized primal SVM solver using Augmented Lagrange Multipliers, with linear-time computational cost for Lp-norm loss functions. The most computationally intensive steps (that determine the algorithmic complexity) of the proposed algorithm is purely and simply matrix-by-vector multiplication, which can be easily parallelized on a multi-core server for parallel computing. We implement and integrate our algorithm into the interfaces and framework of the well-known LibLinear software toolbox. Experiments show that our algorithm is with stable performance and on average faster than the state-of-the-art solvers such as SVMperf , Pegasos and the LibLinear that integrates the TRON, PCD and DCD algorithms.
Online Learning in Markov Decision Processes with Changing Cost Sequences
Authors: Travis Dick, Andras Gyorgy, Csaba Szepesvari
Published in: Proceedings of the 31st International Conference on Machine Learning (Main Conference Track), 2014

Abstract: In this paper we consider online learning in finite Markov decision processes (MDPs) with changing cost sequences under full and bandit-information.  We propose to view this problem as an instance of online linear optimization.  We propose two methods for this problem: MD^2 (mirror descent with approximate projections) and the continuous exponential weights algorithm with Dikin walks.  We provide a rigorous complexity analysis of these techniques, while providing near-optimal regret-bounds (in particular, we take into account the computational costs of performing approximate projections in MD^2).  In the case of full-information feedback, our results complement existing ones. In the case of bandit-information feedback we consider the online stochastic shortest path problem, a special case of the above MDP problems, and manage to improve the existing results by removing the previous restrictive assumption that the state-visitation probabilities are uniformly bounded away from zero under all policies.
Memory (and Time) Efficient Sequential Monte Carlo
Authors: Seong-Hwan Jun, Alexandre Bouchard-Côté
Published in: Proceedings of the 31st International Conference on Machine Learning (Main Conference Track), 2014

Abstract: Memory efficiency is an important issue in Sequential Monte Carlo (SMC) algorithms, arising for example in inference of high-dimensional latent variables via Rao-Blackwellized SMC algorithms, where the size of individual particles combined with the required number of particles can stress the main memory. Standard SMC methods have a memory requirement that scales linearly in the number of particles present at all stage of the algorithm.   Our contribution is a simple scheme that makes the memory cost of SMC methods depends on the number of distinct particles that survive resampling.   We show that this difference has a large empirical impact on the quality of the approximation in realistic scenarios, and also—since memory access is generally slow—on the running time.    The method is based on a two pass generation of the particles, which are represented implicitly in the first pass.   We parameterize the accuracy of our algorithm with a memory budget rather than with a fixed number of particles. Our algorithm adaptively selects an optimal number of particle to exploit this fixed memory budget. We show that this adaptation does not interfere with the usual consistency guarantees that come with SMC algorithms.
Unimodal Bandits: Regret Lower Bounds and Optimal Algorithms
Authors: Richard Combes, Alexandre Proutiere
Published in: Proceedings of the 31st International Conference on Machine Learning (Main Conference Track), 2014

Abstract: We consider stochastic multi-armed bandits where the expected reward is a unimodal function over partially ordered arms. This important class of problems has been recently investigated in (Cope 2009, Yu 2011). The set of arms is either discrete, in which case arms correspond to the vertices of a finite graph whose structure represents similarity in rewards, or continuous, in which case arms belong to a bounded interval. For discrete unimodal bandits, we derive asymptotic lower bounds for the regret achieved under any algorithm, and propose OSUB, an algorithm whose regret matches this lower bound. Our algorithm optimally exploits the unimodal structure of the problem, and surprisingly, its asymptotic regret does not depend on the number of arms. We also provide a regret upper bound for OSUB in non-stationary environments where the expected rewards smoothly evolve over time. The analytical results are supported by numerical experiments showing that OSUB performs significantly better than the state-of-the-art algorithms. For continuous sets of arms, we provide a brief discussion. We show that combining an appropriate discretization of the set of arms with the UCB algorithm yields an order-optimal regret, and in practice, outperforms recently proposed algorithms designed to exploit the unimodal structure.
Scaling SVM and Least Absolute Deviations via Exact Data Reduction
Authors: Jie Wang, Peter Wonka, Jieping Ye
Published in: Proceedings of the 31st International Conference on Machine Learning (Main Conference Track), 2014

Abstract: The support vector machine (SVM) is a widely used method for classification. Although many efforts have been devoted to develop efficient solvers, it remains challenging to apply SVM to large-scale problems. A nice property of SVM is that the non-support vectors have no effect on the resulting classifier. Motivated by this observation, we present fast and efficient screening rules to discard non-support vectors by analyzing the dual problem of SVM via variational inequalities (DVI). As a result, the number of data instances to be entered into the optimization can be substantially reduced. Some appealing features of our screening method are: (1) DVI is safe in the sense that the vectors discarded by DVI are guaranteed to be non-support vectors; (2) the data set needs to be scanned only once to run the screening, and its computational cost is negligible compared to that of solving the SVM problem; (3) DVI is independent of the solvers and can be integrated with any existing efficient solver. We also show that the DVI technique can be extended to detect non-support vectors in the least absolute deviations regression (LAD). To the best of our knowledge, there are currently no screening methods for LAD.  We have evaluated DVI on both synthetic and real data sets. Experiments indicate that DVI significantly outperforms the existing state-of-the-art screening rules for SVM, and it is very effective in discarding non-support vectors for LAD. The speedup gained by DVI rules can be up to two orders of magnitude.
Maximum Mean Discrepancy for Class Ratio Estimation: Convergence Bounds and Kernel Selection
Authors: Arun Iyer, Saketha Nath, Sunita Sarawagi
Published in: Proceedings of the 31st International Conference on Machine Learning (Main Conference Track), 2014

Abstract: In recent times, many real world applications have emerged that require estimates of class ratios in an unlabeled instance collection as opposed to labels of individual instances in the collection.  In this paper we investigate the use of maximum mean discrepancy (MMD) in a reproducing kernel Hilbert space (RKHS) for estimating such ratios. First, we theoretically analyze the MMD-based estimates. Our analysis establishes that, under some mild conditions, the estimate is statistically consistent. More importantly, it provides an upper bound on the error in the estimate in terms of intuitive geometric quantities like class separation and data spread. Next, we use the insights obtained from the theoretical analysis, to propose a novel convex formulation that automatically learns the kernel to be employed in the MMD-based estimation. We design an efficient cutting plane algorithm for solving this formulation.  Finally, we empirically compare our estimator with several existing methods, and show significantly improved performance under varying datasets, class ratios, and training sizes.