mtybilly/Instruct2DS huggingface dataset:
Gossip-based distributed stochastic bandit algorithms
Authors: Balazs Szorenyi, Robert Busa-Fekete, Istvan Hegedus, Robert Ormandi, Mark Jelasity, Balazs Kegl
Published in: Proceedings of the 30th International Conference on Machine Learning (Main Conference Track), 2013

Abstract: The multi-armed bandit problem has attracted remarkable attention in the machine learning community and many efficient algorithms have been proposed to handle the so-called exploitation-exploration dilemma in various bandit setups. At the same time, significantly less effort has been devoted to adapting bandit algorithms to particular architectures, such as sensor networks, multi-core machines, or peer-to-peer (P2P) environments, which could potentially speed up their convergence. Our goal is to adapt stochastic bandit algorithms to P2P networks.  In our setup, the same set of arms is available in each peer. In every iteration each peer can pull one arm independently of the other peers, and then some limited communication is possible with a few random other peers.  As our main result, we show that our adaptation achieves a linear speedup in terms of the number of peers participating in the network.  More precisely, we show that the probability of playing a suboptimal arm at a peer in iteration t = Ω( łog N ) is proportional to 1/(Nt) where N denotes the number of peers.  The theoretical results are supported by simulation experiments showing that our algorithm scales gracefully with the size of network.
Stochastic Simultaneous Optimistic Optimization
Authors: Michal Valko, Alexandra Carpentier, Rémi Munos
Published in: Proceedings of the 30th International Conference on Machine Learning (Main Conference Track), 2013

Abstract: We study the problem of global maximization of a function f given a finite number of evaluations perturbed by noise. We consider a very weak assumption on the function, namely that it is locally smooth (in some precise sense) with respect to some semi-metric, around one of its global maxima. Compared to previous works on bandits in general spaces (Kleinberg et al., 2008; Bubeck et al., 2011a) our algorithm does not require the knowledge of this semi-metric. Our algorithm, StoSOO, follows an optimistic strategy to iteratively construct upper confidence bounds over the hierarchical partitions of the function domain to decide which point to sample next. A finite-time analysis of StoSOO shows that it performs almost as well as the best specifically-tuned algorithms even though the local smoothness of the function is not known.
A Spectral Learning Approach to Range-Only SLAM
Authors: Byron Boots, Geoff Gordon
Published in: Proceedings of the 30th International Conference on Machine Learning (Main Conference Track), 2013

Abstract: We present a novel spectral learning algorithm for simultaneous localization and mapping (SLAM) from range data with known correspondences.  This algorithm is an instance of a general spectral system identification framework, from which it inherits several desirable properties, including statistical consistency and no local optima. Compared with popular batch optimization or multiple-hypothesis tracking (MHT) methods for range-only SLAM, our spectral approach offers guaranteed low computational requirements and good tracking performance. Compared with MHT and with popular extended Kalman filter (EKF) or extended information filter (EIF) approaches, our approach does not need to linearize a transition or measurement model. We provide a theoretical analysis of our method, including finite-sample error bounds.  Finally, we demonstrate on a real-world robotic SLAM problem that our algorithm is not only theoretically justified, but works well in practice: in a comparison of multiple methods, the lowest errors come from a combination of our algorithm with batch optimization, but our method alone produces nearly as good a result at far lower computational cost.
Near-Optimal Bounds for Cross-Validation via Loss Stability
Authors: Ravi Kumar, Daniel Lokshtanov, Sergei Vassilvitskii, Andrea Vattani
Published in: Proceedings of the 30th International Conference on Machine Learning (Main Conference Track), 2013

Abstract: Multi-fold cross-validation is an established practice to estimate the error rate   of a learning algorithm.  Quantifying the variance reduction gains due to cross-validation   has been challenging due to the inherent correlations introduced by the folds.    In this work we introduce a new and weak measure of stability called \emphloss stability  and relate the cross-validation performance to loss stability; we also establish that this   relationship is near-optimal.  Our work thus quantitatively improves the current  best bounds on cross-validation.
The Sample-Complexity of General Reinforcement Learning
Authors: Tor Lattimore, Marcus Hutter, Peter Sunehag
Published in: Proceedings of the 30th International Conference on Machine Learning (Main Conference Track), 2013

Abstract: We study the sample-complexity of reinforcement learning in a general setting without  assuming ergodicity or finiteness of the environment. Instead, we define a topology  on the space of environments and show that  if an environment class is compact with respect to this topology then finite sample-complexity bounds are possible and give an  algorithm achieving these bounds. We also  show the existence of environment classes  that are non-compact where finite sample-complexity bounds are not achievable. A  lower bound is presented that matches the  upper bound except for logarithmic factors.
Toward Optimal Stratification for Stratified Monte-Carlo Integration
Authors: Alexandra Carpentier, Rémi Munos
Published in: Proceedings of the 30th International Conference on Machine Learning (Main Conference Track), 2013

Abstract: We consider the problem of adaptive stratified sampling for Monte Carlo integration of a function, given a finite number of function evaluations perturbed by noise. Here we address the problem of adapting simultaneously the number of samples into each stratum and the stratification itself. We show a tradeoff in the size of the partitioning. On the one hand it is important to refine the partition in areas where the observation noise or the function are heterogeneous in order to reduce this variability. But on the other hand, a too refined stratification makes it harder to assign the samples according to a near-optimal (oracle) allocation strategy. In this paper we provide an algorithm \em Monte-Carlo Upper-Lower Confidence Bound that selects online, among a large class of partitions, the partition that provides a near-optimal trade-off, and allocates the samples almost optimally on this partition.
Sparsity-Based Generalization Bounds for Predictive Sparse Coding
Authors: Nishant Mehta, Alexander Gray
Published in: Proceedings of the 30th International Conference on Machine Learning (Main Conference Track), 2013

Abstract: The goal of predictive sparse coding is to learn a representation of examples as sparse linear combinations of elements from a dictionary, such that a learned hypothesis linear in the new representation performs well on a predictive task. Predictive sparse coding has demonstrated impressive performance on a variety of supervised tasks, but its generalization properties have not been studied. We establish the first generalization error bounds for predictive sparse coding, in the overcomplete setting, where the number of features k exceeds the original dimensionality d. The learning bound decays as (sqrt(d k/m)) with respect to d, k, and the size m of the training sample. It depends intimately on stability properties of the learned sparse encoder, as measured on the training sample. Consequently, we also present a fundamental stability result for the LASSO, a result that characterizes the stability of the sparse codes with respect to dictionary perturbations.
Hierarchical Regularization Cascade for Joint Learning
Authors: Alon Zweig, Daphna Weinshall
Published in: Proceedings of the 30th International Conference on Machine Learning (Main Conference Track), 2013

Abstract: As the sheer volume of available benchmark datasets increases, the problem of joint learning of classifiers and knowledge-transfer between classifiers, becomes more and more relevant. We present a hierarchical approach which exploits information sharing among different classification tasks, in multi-task and multi-class settings. It engages a top-down iterative method, which begins by posing an optimization problem with an incentive for large scale sharing among all classes. This incentive to share is gradually decreased,until there is no sharing and all tasks are considered separately. The method therefore exploits different levels of sharing within a given group of related tasks, without having to make hard decisions about the grouping of tasks. In order to deal with large scale problems, with many tasks and many classes, we extend our batch approach to an online setting and provide regret analysis of the algorithm. We tested our approach extensively on synthetic and real datasets, showing significant improvement over baseline and state-of-the-art methods.
A General Iterative Shrinkage and Thresholding Algorithm for Non-convex Regularized Optimization Problems
Authors: Pinghua Gong, Changshui Zhang, Zhaosong Lu, Jianhua Huang, Jieping Ye
Published in: Proceedings of the 30th International Conference on Machine Learning (Main Conference Track), 2013

Abstract: Non-convex sparsity-inducing penalties have recently received considerable attentions in sparse learning. Recent theoretical investigations have demonstrated their superiority over the convex counterparts in several sparse learning settings. However, solving the non-convex optimization problems associated with non-convex penalties remains a big challenge. A commonly used approach is the Multi-Stage (MS) convex relaxation (or DC programming), which relaxes the original non-convex problem to a sequence of convex problems. This approach is usually not very practical for large-scale problems because its computational cost is a multiple of solving a single convex problem. In this paper, we propose a General Iterative Shrinkage and Thresholding (GIST) algorithm to solve the nonconvex optimization problem for a large class of non-convex penalties. The GIST algorithm iteratively solves a proximal operator problem, which in turn has a closed-form solution for many commonly used penalties. At each outer iteration of the algorithm, we use a line search initialized by the Barzilai-Borwein (BB) rule that allows finding an appropriate step size quickly. The paper also presents a detailed convergence analysis of the GIST algorithm. The efficiency of the proposed algorithm is demonstrated by extensive experiments on large-scale data sets.
Sparse Uncorrelated Linear Discriminant Analysis
Authors: Xiaowei Zhang, Delin Chu
Published in: Proceedings of the 30th International Conference on Machine Learning (Main Conference Track), 2013

Abstract: In this paper, we develop a novel approach for sparse uncorrelated linear discriminant analysis (ULDA). Our proposal is based on characterization of all solutions of the generalized ULDA. We incorporate sparsity into the ULDA transformation by seeking the solution with minimum \ell_1-norm from all minimum dimension solutions of the generalized ULDA. The problem is then formulated as a \ell_1-minimization problem and is solved by accelerated linearized Bregman method. Experiments on high-dimensional gene expression data demonstrate that our approach not only computes extremely sparse solutions but also performs well in classification. Experimental results also show that our approach can help for data visualization in low-dimensional space.
Multi-Class Classification with Maximum Margin Multiple Kernel
Authors: Corinna Cortes, Mehryar Mohri, Afshin Rostamizadeh
Published in: Proceedings of the 30th International Conference on Machine Learning (Main Conference Track), 2013

Abstract: We present a new algorithm for multi-class classification with multiple kernels. Our algorithm is based on a natural notion of the multi-class margin of a kernel. We show that larger values of this quantity guarantee the existence of an accurate multi-class predictor and also define a family of multiple kernel algorithms based on the maximization of the multi-class margin of a kernel (M^3K).  We present an extensive theoretical analysis in support of our algorithm, including novel multi-class Rademacher complexity margin bounds.  Finally, we also report the results of a series of experiments with several data sets, including comparisons where we improve upon the performance of state-of-the-art algorithms both in binary and multi-class classification with multiple kernels.
Thurstonian Boltzmann Machines: Learning from Multiple Inequalities
Authors: Truyen Tran, Dinh Phung, Svetha Venkatesh
Published in: Proceedings of the 30th International Conference on Machine Learning (Main Conference Track), 2013

Abstract: We introduce Thurstonian Boltzmann Machines (TBM), a unified architecture that can naturally incorporate a wide range of data inputs at the same time. Our motivation rests in the Thurstonian view that many discrete data types can be considered as being generated from a subset of underlying latent continuous variables, and in the observation that each realisation of a discrete type imposes certain inequalities on those variables. Thus learning and inference in TBM reduce to making sense of a set of inequalities. Our proposed TBM naturally supports the following types: Gaussian, intervals, censored, binary, categorical, muticategorical, ordinal, (in)-complete rank with and without ties. We demonstrate the versatility and capacity of the proposed model on three applications of very different natures; namely handwritten digit recognition, collaborative filtering and complex social survey analysis.
Block-Coordinate Frank-Wolfe Optimization for Structural SVMs
Authors: Simon Lacoste-Julien, Martin Jaggi, Mark Schmidt, Patrick Pletscher
Published in: Proceedings of the 30th International Conference on Machine Learning (Main Conference Track), 2013

Abstract: We propose a randomized block-coordinate variant of the classic Frank-Wolfe algorithm for convex optimization with block-separable constraints. Despite its lower iteration cost, we show that it achieves a similar convergence rate in duality gap as the full Frank-Wolfe algorithm. We also show that, when applied to the dual structural support vector machine (SVM) objective, this yields an online algorithm that has the same low iteration complexity as primal stochastic subgradient methods. However, unlike stochastic subgradient methods, the block-coordinate Frank-Wolfe algorithm allows us to compute the optimal step-size and yields a computable duality gap guarantee. Our experiments indicate that this simple algorithm outperforms competing structural SVM solvers.
Bayesian Games for Adversarial Regression Problems
Authors: Michael Großhans, Christoph Sawade, Michael Brückner, Tobias Scheffer
Published in: Proceedings of the 30th International Conference on Machine Learning (Main Conference Track), 2013

Abstract: We study regression problems in which an adversary can exercise some control over the data generation process. Learner and adversary have conflicting but not necessarily perfectly antagonistic objectives. We study the case in which the learner is not fully informed about the adversary’s objective; instead, any knowledge of the learner about parameters of the adversary’s goal may be reflected in a Bayesian prior. We model this problem as a Bayesian game, and characterize conditions under which a unique Bayesian equilibrium point exists. We experimentally compare the Bayesian equilibrium strategy to the Nash equilibrium strategy, the minimax strategy, and regular linear regression.
A Variational Approximation for Topic Modeling of Hierarchical Corpora
Authors: Do-kyum Kim, Geoffrey Voelker, Lawrence Saul
Published in: Proceedings of the 30th International Conference on Machine Learning (Main Conference Track), 2013

Abstract: We study the problem of topic modeling in corpora whose documents are organized in a multi-level hierarchy.  We explore a parametric approach to this problem, assuming that the number of topics is known or can be estimated by cross-validation.  The models we consider can be viewed as special (finite-dimensional) instances of hierarchical Dirichlet processes (HDPs).  For these models we show that there exists a simple variational approximation for probabilistic inference.  The approximation relies on a previously unexploited inequality that handles the conditional dependence between Dirichlet latent variables in adjacent levels of the model’s hierarchy.  We compare our approach to existing implementations of nonparametric HDPs.  On several benchmarks we find that our approach is faster than Gibbs sampling and able to learn more predictive models than existing variational methods.  Finally, we demonstrate the large-scale viability of our approach on two newly available corpora from researchers in computer security–one with 350,000 documents and over 6,000 internal subcategories, the other with a five-level deep hierarchy.
Fast Probabilistic Optimization from Noisy Gradients
Authors: Philipp Hennig
Published in: Proceedings of the 30th International Conference on Machine Learning (Main Conference Track), 2013

Abstract: Stochastic gradient descent remains popular in large-scale machine learning, on account of its very low computational cost and robustness to noise. However, gradient descent is only linearly efficient and not transformation invariant. Scaling by a local measure can substantially improve its performance. One natural choice of such a scale is the Hessian of the objective function: Were it available, it would turn linearly efficient gradient descent into the quadratically efficient Newton-Raphson optimization. Existing covariant methods, though, are either super-linearly expensive or do not address noise. Generalising recent results, this paper constructs a nonparametric Bayesian quasi-Newton algorithm that learns gradient and Hessian from noisy evaluations of the gradient. Importantly, the resulting algorithm, like stochastic gradient descent, has cost linear in the number of input dimensions.
Optimistic Knowledge Gradient Policy for Optimal Budget Allocation in Crowdsourcing
Authors: Xi Chen, Qihang Lin, Dengyong Zhou
Published in: Proceedings of the 30th International Conference on Machine Learning (Main Conference Track), 2013

Abstract: In real crowdsourcing applications, each label from a crowd usually comes  with a certain cost. Given a pre- fixed amount of budget, since different tasks have different ambiguities and different workers have different expertises, we want to  find an optimal way to allocate the budget among instance-worker pairs such that the overall label quality can be maximized. To address this issue, we start from the simplest setting in which all workers are assumed to be perfect. We formulate the problem as a Bayesian Markov Decision Process (MDP). Using the dynamic programming (DP) algorithm, one can obtain the optimal allocation policy for a given budget. However,  DP is computationally intractable. To solve the computational challenge, we propose a novel approximate policy which is called optimistic knowledge gradient. It is practically efficient while theoretically its consistency can be guaranteed.  We then extend  the MDP framework to deal with inhomogeneous workers and tasks with contextual information available.  The experiments on both simulated and real data  demonstrate the superiority of our method.
Forecastable Component Analysis
Authors: Georg Goerg
Published in: Proceedings of the 30th International Conference on Machine Learning (Main Conference Track), 2013

Abstract: I introduce Forecastable Component Analysis (ForeCA), a novel dimension reduction technique for temporally dependent signals. Based on a new forecastability measure, ForeCA finds an optimal transformation to separate a multivariate time series into a forecastable and an orthogonal white noise space. I present a converging algorithm with a fast eigenvector solution. Applications to financial and macro-economic time series show that ForeCA can successfully discover informative structure, which can be used for forecasting as well as classification. The R package ForeCA accompanies this work and is publicly available on CRAN.
Stochastic Gradient Descent for Non-smooth Optimization: Convergence Results and Optimal Averaging Schemes
Authors: Ohad Shamir, Tong Zhang
Published in: Proceedings of the 30th International Conference on Machine Learning (Main Conference Track), 2013

Abstract: Stochastic Gradient Descent (SGD) is one of the simplest and most popular stochastic optimization methods. While it has already been theoretically studied for decades, the classical analysis usually required non-trivial smoothness assumptions, which do not apply to many modern applications of SGD with non-smooth objective functions such as support vector machines.  In this paper, we investigate the performance of SGD \emphwithout such smoothness assumptions, as well as a running average scheme to convert the SGD iterates to a solution with optimal optimization accuracy. In this framework, we prove that after T rounds, the suboptimality of the \emphlast SGD iterate scales as O(łog(T)/\sqrtT) for non-smooth convex objective functions, and O(łog(T)/T) in the non-smooth strongly convex case. To the best of our knowledge, these are the first bounds of this kind, and almost match the minimax-optimal rates obtainable by appropriate averaging schemes. We also propose a new and simple averaging scheme, which not only attains optimal rates, but can also be easily computed on-the-fly (in contrast, the suffix averaging scheme proposed in i̧tetRakhShaSri12arxiv is not as simple to implement). Finally, we provide some experimental illustrations.
Markov Network Estimation From Multi-attribute Data
Authors: Mladen Kolar, Han Liu, Eric Xing
Published in: Proceedings of the 30th International Conference on Machine Learning (Main Conference Track), 2013

Abstract: Many real world network problems often concern multivariate nodal attributes such as image, textual, and multi-view feature vectors on nodes, rather than simple univariate nodal attributes. The existing graph estimation methods built on Gaussian graphical models and covariance selection algorithms can not handle such data, neither can the theories developed around such methods be directly applied. In this paper, we propose a new principled framework for estimating multi-attribute graphs. Instead of estimating the partial correlation as in current literature, our method estimates the partial canonical correlations that naturally accommodate complex nodal features.  Computationally, we provide an efficient algorithm which utilizes the multi-attribute structure. Theoretically, we provide sufficient conditions which guarantee consistent graph recovery. Extensive simulation studies demonstrate performance of our method under various conditions.
Ellipsoidal Multiple Instance Learning
Authors: Gabriel Krummenacher, Cheng Soon Ong, Joachim Buhmann
Published in: Proceedings of the 30th International Conference on Machine Learning (Main Conference Track), 2013

Abstract: We propose a large margin method for asymmetric learning with ellipsoids, called eMIL, suited to multiple instance learning (MIL). We derive the distance between ellipsoids and the hyperplane, generalising the standard support vector machine. Negative bags in MIL contain only negative instances, and we treat them akin to uncertain observations in the robust optimisation framework. However, our method allows positive bags to cross the margin, since it is not known which instances within are positive.  We show that representing bags as ellipsoids under the introduced distance is the most robust solution when treating a bag as a random variable with finite mean and covariance. Two algorithms are derived to solve the resulting non-convex optimization problem: a concave-convex procedure and a quasi-Newton method. Our method achieves competitive results on benchmark datasets. We introduce a MIL dataset from a real world application of detecting wheel defects from multiple partial observations, and show that eMIL outperforms competing approaches.
Stochastic Alternating Direction Method of Multipliers
Authors: Hua Ouyang, Niao He, Long Tran, Alexander Gray
Published in: Proceedings of the 30th International Conference on Machine Learning (Main Conference Track), 2013

Abstract: The Alternating Direction Method of Multipliers (ADMM) has received lots of attention recently due to the tremendous demand from large-scale and data-distributed machine learning applications. In this paper, we present a stochastic setting for optimization problems with non-smooth composite objective functions. To solve this problem, we propose a stochastic ADMM algorithm. Our algorithm applies to a more general class of convex and nonsmooth objective functions, beyond the smooth and separable least squares loss used in lasso. We also demonstrate the rates of convergence for our algorithm under various structural assumptions of the stochastic function: O(1/\sqrtt) for convex functions and O(łog t/t) for strongly convex functions. Compared to previous literature, we establish the convergence rate of ADMM for convex problems in terms of both the objective value and the feasibility violation. A novel application named Graph-Guided SVM is proposed to demonstrate the usefulness of our algorithm.
MILEAGE: Multiple Instance LEArning with Global Embedding
Authors: Dan Zhang, Jingrui He, Luo Si, Richard Lawrence
Published in: Proceedings of the 30th International Conference on Machine Learning (Main Conference Track), 2013

Abstract: Multiple Instance Learning (MIL) methods generally represent each example as a collection of  instances such that the features for local objects can be better captured, whereas traditional learning methods typically extract a global feature vector for each example as an integral part. However, there is limited research work on which of the two learning scenarios performs better. This paper proposes a novel framework – \emphMultiple Instance LEArning with  Global Embedding (MILEAGE), in which  the global feature vectors for traditional learning methods are integrated into the MIL setting.  MILEAGE can leverage the benefits derived from both learning settings. Within the proposed framework, a large margin method is formulated. In particular,  the proposed method adaptively  tunes the weights on the two different kinds of feature  representations (i.e., global and multiple instance) for each example and trains the classifier simultaneously. An alternative algorithm is proposed to solve the resulting optimization problem, which extends the bundle method to the non-convex case. Some important properties of the proposed method, such as the convergence rate and the generalization error rate, are analyzed. A series of  experiments  have been conducted to demonstrate the advantages of the proposed method over several state-of-the-art multiple instance and traditional learning methods.
Local Low-Rank Matrix Approximation
Authors: Joonseok Lee, Seungyeon Kim, Guy Lebanon, Yoram Singer
Published in: Proceedings of the 30th International Conference on Machine Learning (Main Conference Track), 2013

Abstract: Matrix approximation is a common tool in recommendation systems, text mining, and computer vision. A prevalent assumption in constructing matrix approximations is that the partially observed matrix is of low-rank. We propose a new matrix approximation model where we assume instead that the matrix is locally of low-rank, leading to a representation of the observed matrix as a weighted sum of low-rank matrices. We analyze the accuracy of the proposed local low-rank modeling. Our experiments show improvements in prediction accuracy over classical approaches for recommendation tasks.
Noisy Sparse Subspace Clustering
Authors: Yu-Xiang Wang, Huan Xu
Published in: Proceedings of the 30th International Conference on Machine Learning (Main Conference Track), 2013

Abstract: This paper considers the problem of subspace clustering under noise. Specifically, we study the behavior of Sparse Subspace Clustering (SSC) when either adversarial or random noise is added to the unlabelled input data points, which are assumed to lie in a union of low-dimensional subspaces.  We show that a modified version of SSC is \emphprovably effective in correctly identifying the underlying subspaces, even with noisy data. This extends theoretical guarantee of this algorithm to the practical setting and provides justification to the success of SSC in a class of real applications.
Guaranteed Sparse Recovery under Linear Transformation
Authors: Ji Liu, Lei Yuan, Jieping Ye
Published in: Proceedings of the 30th International Conference on Machine Learning (Main Conference Track), 2013

Abstract: We consider the following signal recovery problem: given a  measurement matrix Φ∈\mathbbR^n\times p and a noisy  observation vector c∈\mathbbR^n constructed from c =  Φθ^* + εwhere ε∈\mathbbR^n is the  noise vector whose entries follow i.i.d. centered sub-Gaussian  distribution, how to recover the signal θ^* if Dθ^* is  sparse c̊a under a linear transformation D∈\mathbbR^m\times  p? One natural method using convex optimization is to solve the  following problem: $\min_θ 1øver 2\|Φθ- c\|^2 +  λ\|Dθ\|_1. This paper provides an upper bound of the  estimate error and shows the consistency property of this method by  assuming that the design matrix Φis a Gaussian random matrix.  Specifically, we show 1) in the noiseless case, if the condition  number of D is bounded and the measurement number n≥Ω(słog(p)) where s is the sparsity number, then the true  solution can be recovered with high probability; and 2) in the noisy  case, if the condition number of D is bounded and the measurement  increases faster than słog(p), that is, słog(p)=o(n), the  estimate error converges to zero with probability 1 when p and s  go to infinity. Our results are consistent with those for the  special case D=\boldI_p\times p (equivalently LASSO) and  improve the existing analysis. The condition number of D plays a  critical role in our analysis. We consider the condition numbers in  two cases including the fused LASSO and the random graph: the  condition number in the fused LASSO case is bounded by a constant,  while the condition number in the random graph case is bounded with  high probability if møver p (i.e., #\textedgeøver  #\textvertex$) is larger than a certain constant. Numerical  simulations are consistent with our theoretical results.
Generic Exploration and K-armed Voting Bandits
Authors: Tanguy Urvoy, Fabrice Clerot, Raphael Féraud, Sami Naamane
Published in: Proceedings of the 30th International Conference on Machine Learning (Main Conference Track), 2013

Abstract: We study a stochastic online learning scheme with partial feedback where the utility of decisions is only observable through an estimation of the environment parameters. We propose a generic pure-exploration algorithm, able to cope with various utility functions from multi-armed bandits settings to dueling bandits. The primary application of this setting is to offer a natural generalization of dueling bandits for situations where the environment parameters reflect the idiosyncratic preferences of a mixed crowd.
Parallel Markov Chain Monte Carlo for Nonparametric Mixture Models
Authors: Sinead Williamson, Avinava Dubey, Eric Xing
Published in: Proceedings of the 30th International Conference on Machine Learning (Main Conference Track), 2013

Abstract: Nonparametric mixture models based on the Dirichlet process are an elegant alternative to finite models when the number of underlying components is unknown, but inference in such models can be slow. Existing attempts to parallelize inference in such models have relied on introducing approximations, which can lead to inaccuracies in the posterior estimate. In this paper, we describe auxiliary variable representations for the Dirichlet process and the hierarchical Dirichlet process that allow us to perform MCMC using the correct equilibrium distribution, in a distributed manner. We show that our approach allows scalable inference without the deterioration in estimate quality that accompanies existing methods.
Learning invariant features by harnessing the aperture problem
Authors: Roland Memisevic, Georgios Exarchakis
Published in: Proceedings of the 30th International Conference on Machine Learning (Main Conference Track), 2013

Abstract: The energy model is a simple, biologically inspired approach to extracting relationships between images in tasks like stereopsis and motion analysis. We discuss how adding an extra pooling layer to the energy model makes it possible to learn encodings of transformations that are mostly invariant with respect to image content, and to learn encodings of images that are mostly invariant with respect to the observed transformations. We show how this makes it possible to learn 3D pose-invariant features of objects by watching videos of the objects. We test our approach on a dataset of videos derived from the NORB dataset.
A unifying framework for vector-valued manifold regularization and multi-view learning
Authors: Minh Hà Quang, Loris Bazzani, Vittorio Murino
Published in: Proceedings of the 30th International Conference on Machine Learning (Main Conference Track), 2013

Abstract: This paper presents a general vector-valued reproducing kernel Hilbert spaces (RKHS) formulation for the problem of learning an unknown functional dependency  between a structured input space and a structured output space, in the Semi-Supervised Learning setting. Our formulation includes as special cases Vector-valued Manifold Regularization and Multi-view Learning, thus provides in particular a unifying framework linking these two important learning approaches.  In the case of least square loss function, we provide a closed form solution with an efficient implementation. Numerical experiments on challenging multi-class categorization problems show that our multi-view learning formulation achieves results which are comparable with state of the art and are significantly better than single-view learning.
Risk Bounds and Learning Algorithms for the Regression Approach to Structured Output Prediction
Authors: Sébastien Giguère, François Laviolette, Mario Marchand, Khadidja Sylla
Published in: Proceedings of the 30th International Conference on Machine Learning (Main Conference Track), 2013

Abstract: We provide rigorous guarantees for the regression approach to structured output prediction. We show that the quadratic regression loss is a convex surrogate of the prediction loss when the output kernel satisfies some condition with respect to the prediction loss. We provide two upper bounds of the prediction risk that depend on the empirical quadratic risk of the predictor. The minimizer of the first bound is the predictor proposed by Cortes et al. (2007) while the minimizer of the second bound is a predictor that  has never been proposed so far. Both predictors are compared on practical tasks.
Efficient Ranking from Pairwise Comparisons
Authors: Fabian Wauthier, Michael Jordan, Nebojsa Jojic
Published in: Proceedings of the 30th International Conference on Machine Learning (Main Conference Track), 2013

Abstract: The ranking of n objects based on pairwise comparisons is a core machine learning problem, arising in recommender systems, ad placement, player ranking, biological applications and others. In many practical situations the true pairwise comparisons cannot be actively measured, but a subset of all n(n-1)/2 comparisons is passively and noisily observed. Optimization algorithms (e.g., the SVM) could be used to predict a ranking with fixed expected Kendall tau distance, while achieving an Ω(n) lower bound on the corresponding sample complexity. However, due to their centralized structure they are difficult to extend to online or distributed settings. In this paper we show that much simpler algorithms can match the same Ω(n) lower bound in expectation. Furthermore, if an average of O(nłog(n)) binary comparisons are measured, then one algorithm recovers the true ranking in a uniform sense, while the other predicts the ranking more accurately near the top than the bottom. We discuss extensions to online and distributed ranking, with benefits over traditional alternatives.
Learning Connections in Financial Time Series
Authors: Gartheeban Ganeshapillai, John Guttag, Andrew Lo
Published in: Proceedings of the 30th International Conference on Machine Learning (Main Conference Track), 2013

Abstract: To reduce risk, investors seek assets that have high expected return and are unlikely to move in tandem. Correlation measures are generally used to quantify the connections between equities. The 2008 financial crisis, and its aftermath, demonstrated the need for a better way to quantify these connections. We present a machine learning-based method to build a connectedness matrix to address the shortcomings of correlation in capturing events such as large losses. Our method uses an unconstrained optimization to learn this matrix, while ensuring that the resulting matrix is positive semi-definite. We show that this matrix can be used to build portfolios that not only “beat the market,”  but also outperform optimal (i.e., minimum variance) portfolios.
Making a Science of Model Search: Hyperparameter Optimization in Hundreds of Dimensions for Vision Architectures
Authors: James Bergstra, Daniel Yamins, David Cox
Published in: Proceedings of the 30th International Conference on Machine Learning (Main Conference Track), 2013

Abstract: Many computer vision algorithms depend on configuration settings that are typically hand-tuned in the course of evaluating the algorithm for a particular data set. While such parameter tuning is often presented as being incidental to the algorithm, correctly setting these parameter choices is frequently critical to realizing a method’s full potential. Compounding matters, these parameters often must be re-tuned when the algorithm is applied to a new problem domain, and the tuning process itself often depends on personal experience and intuition in ways that are hard to quantify or describe. Since the performance of a given technique depends on both the fundamental quality of the algorithm and the details of its tuning, it is sometimes difficult to know whether a given technique is genuinely better, or simply better tuned.     In this work, we propose a meta-modeling approach to support automated hyperparameter optimization, with the goal of providing practical tools that replace hand-tuning with a reproducible and unbiased optimization process. Our approach is to expose the underlying expression graph of how a performance metric (e.g. classification accuracy on validation examples) is computed from hyperparameters that govern not only how individual processing steps are applied, but even which processing steps are included.  A hyperparameter optimization algorithm transforms this graph into a program for optimizing that performance metric.  Our approach yields state of the art results on three disparate computer vision problems: a face-matching verification task (LFW), a face identification task (PubFig83) and an object recognition task (CIFAR-10), using a single broad class of feed-forward vision architectures.
Differentially Private Learning with Kernels
Authors: Prateek Jain, Abhradeep Thakurta
Published in: Proceedings of the 30th International Conference on Machine Learning (Main Conference Track), 2013

Abstract: In this paper, we consider the problem of differentially private learning where access to the training features is through a kernel function only. Existing work on this problem is restricted to translation invariant kernels only, where (approximate) training features are available explicitly.  In fact, for general class of kernel functions and in general setting of releasing different private predictor (\w^*), the problem is impossible to solve i̧teCMS11. In this work, we relax the problem setting into three different easier but practical settings. In our first problem setting, we consider an interactive model where the user sends its test set to a trusted learner who sends back differentially private predictions over the test points. This setting is prevalent in modern online systems like search engines, ad engines etc. In the second model, the learner sends back a differentially private version of the optimal parameter vector \w^* but requires access to a small subset of unlabeled test set beforehand. This also is a practical setting that involves two parties interacting through trusted third party. Our third model is similar to the traditional model, where learner is oblivious to the test set and needs to send a differentially private version of \w^*, but the kernels are restricted to efficiently computable functions over low-dimensional vector spaces. For each of the models, we derive differentially private learning algorithms with provable “utlity” or error bounds. Moreover, we  show that our methods can also be applied to the traditional setting of \ţe Rubinstein09, CMS11. Here, our sample complexity bounds have only O(d^1/3) dependence on the dimensionality d while existing methods require O(d^1/2) samples to achieve same generalization error.
Fast dropout training
Authors: Sida Wang, Christopher Manning
Published in: Proceedings of the 30th International Conference on Machine Learning (Main Conference Track), 2013

Abstract: Preventing feature co-adaptation by encouraging independent contributions from different features often improves classification and regression performance.  Dropout training (Hinton et al., 2012) does this by randomly dropping out (zeroing) hidden units and input features during training of neural networks. However, repeatedly sampling a random subset of input features makes training much slower. Based on an examination of the implied objective function of dropout training, we show how to do fast dropout training by sampling from or integrating a Gaussian approximation, instead of doing Monte Carlo optimization of this objective.  This approximation, justified by the central limit theorem and empirical evidence, gives an order of magnitude speedup and more stability.  We show how to do fast dropout training for classification, regression, and multilayer neural networks. Beyond dropout, our technique is extended to integrate out other types of noise and small image transformations.
Gibbs Max-Margin Topic Models with Fast Sampling Algorithms
Authors: Jun Zhu, Ning Chen, Hugh Perkins, Bo Zhang
Published in: Proceedings of the 30th International Conference on Machine Learning (Main Conference Track), 2013

Abstract: Existing max-margin supervised topic models rely on an iterative procedure to solve multiple latent SVM subproblems with additional mean-field assumptions on the desired posterior distributions. This paper presents Gibbs max-margin supervised topic models by minimizing an expected margin loss, an upper bound of the existing margin loss derived from an expected prediction rule. By introducing augmented variables, we develop simple and fast Gibbs sampling algorithms with no restricting assumptions and no need to solve SVM subproblems for both classification and regression. Empirical results demonstrate significant improvements on time efficiency. The classification performance is also significantly improved over competitors.
Thompson Sampling for Contextual Bandits with Linear Payoffs
Authors: Shipra Agrawal, Navin Goyal
Published in: Proceedings of the 30th International Conference on Machine Learning (Main Conference Track), 2013

Abstract: Thompson Sampling is one of the oldest heuristics for multi-armed bandit problems. It is a randomized algorithm based on Bayesian ideas, and has recently generated significant interest after several studies demonstrated it to have better empirical performance compared to the state of the art methods. However, many questions regarding its theoretical performance remained open. In this paper, we design and analyze Thompson Sampling algorithm for the stochastic contextual multi-armed bandit problem with linear payoff functions, when the contexts are provided by an adaptive adversary. This is among the most important and widely studied version of the contextual bandits problem. We prove a high probability regret bound of \tildeO(\fracd\sqrtε\sqrtT^1+ε) in time T for any ε∈(0,1), where d is the dimension of each context vector and εis a parameter used by the algorithm. Our results provide the first theoretical guarantees for the contextual version of Thompson Sampling, and are close to the lower bound of Ω(\sqrtdT) for this problem. This essentially solves the COLT open problem of Chapelle and Li [COLT 2012] regarding regret bounds for Thompson Sampling for contextual bandits problem with linear payoff functions.     Our version of Thompson sampling uses Gaussian prior and Gaussian likelihood function. Our novel martingale-based analysis techniques also allow easy extensions to the use of other distributions, satisfying certain general conditions.
Scalable Optimization of Neighbor Embedding for Visualization
Authors: Zhirong Yang, Jaakko Peltonen, Samuel Kaski
Published in: Proceedings of the 30th International Conference on Machine Learning (Main Conference Track), 2013

Abstract: Neighbor embedding (NE) methods have found their use in data visualization but are limited in big data analysis tasks due to their O(n^2) complexity for n data samples. We demonstrate that the obvious approach of subsampling produces inferior results and propose a generic approximated optimization technique that reduces the NE optimization cost to O(n log n). The technique is based on realizing that in visualization the embedding space is necessarily very low-dimensional (2D or 3D), and hence efficient approximations developed for n-body force calculations can be applied. In gradient-based NE algorithms the gradient for an individual point decomposes into “forces” exerted by the other points. The contributions of close-by points need to be computed individually but far-away points can be approximated by their “center of mass”, rapidly computable by applying a recursive decomposition of the visualization space into quadrants. The new algorithm brings a significant speed-up for medium-size data, and brings “big data” within reach of visualization.
Cost-Sensitive Tree of Classifiers
Authors: Zhixiang Xu, Matt Kusner, Kilian Weinberger, Minmin Chen
Published in: Proceedings of the 30th International Conference on Machine Learning (Main Conference Track), 2013

Abstract: Recently, machine learning algorithms have successfully entered large-scale real-world industrial applications (e.g. search engines and email spam filters). Here, the CPU cost during test-time must be budgeted and accounted for. In this paper, we address the challenge of balancing test-time cost and the classifier accuracy in a principled fashion. The test-time cost of a classifier is often dominated by the computation required for feature extraction-which can vary drastically across features. We incorporate this extraction time by constructing a tree of classifiers, through which test inputs traverse along individual paths. Each path extracts different features and is optimized for a specific sub-partition of the input space. By only computing features for inputs that benefit from them the most, our cost-sensitive tree of classifiers can match the high accuracies of the current state-of-the-art at a small fraction of the computational cost.