text:
learning, kernel methods, large-scale learning}
}

@article{10.5555/2503308.2503340,
author = {Wang, Yang and Tran, Duan and Liao, Zicheng and Forsyth, David},
title = {Discriminative Hierarchical Part-Based Models for Human Parsing and Action Recognition},
year = {2012},
issue_date = {January 2012},
publisher = {JMLR.org},
volume = {13},
number = {1},
issn = {1532-4435},
abstract = {We consider the problem of parsing human poses and recognizing their actions in static images with part-based models. Most previous work in part-based models only considers rigid parts (e.g., torso, head, half limbs) guided by human anatomy. We argue that this representation of parts is not necessarily appropriate. In this paper, we introduce hierarchical poselets--a new representation for modeling the pose configuration of human bodies. Hierarchical poselets can be rigid parts, but they can also be parts that cover large portions of human bodies (e.g., torso + left arm). In the extreme case, they can be the whole bodies. The hierarchical poselets are organized in a hierarchical way via a structured model. Human parsing can be achieved by inferring the optimal labeling of this hierarchical model. The pose information captured by this hierarchical model can also be used as a intermediate representation for other high-level tasks. We demonstrate it in action recognition from static images.},
journal = {J. Mach. Learn. Res.},
month = oct,
pages = {3075–3102},
numpages = {28},
keywords = {hierarchical poselets, action recognition, max-margin structured learning, human parsing, part-based models}
}

@article{10.5555/2503308.2503339,
author = {Lazaric, Alessandro and Ghavamzadeh, Mohammad and Munos, R\'{e}mi},
title = {Finite-Sample Analysis of Least-Squares Policy Iteration},
year = {2012},
issue_date = {January 2012},
publisher = {JMLR.org},
volume = {13},
number = {1},
issn = {1532-4435},
abstract = {In this paper, we report a performance bound for the widely used least-squares policy iteration (LSPI) algorithm. We first consider the problem of policy evaluation in reinforcement learning, that is, learning the value function of a fixed policy, using the least-squares temporal-difference (LSTD) learning method, and report finite-sample analysis for this algorithm. To do so, we first derive a bound on the performance of the LSTD solution evaluated at the states generated by the Markov chain and used by the algorithm to learn an estimate of the value function. This result is general in the sense that no assumption is made on the existence of a stationary distribution for the Markov chain. We then derive generalization bounds in the case when the Markov chain possesses a stationary distribution and is b-mixing. Finally, we analyze how the error at each policy evaluation step is propagated through the iterations of a policy iteration method, and derive a performance bound for the LSPI algorithm.},
journal = {J. Mach. Learn. Res.},
month = oct,
pages = {3041–3074},
numpages = {34},
keywords = {finite-sample analysis, least-squares temporal-difference, reinforcement learning, generalization bounds, least-squares policy iteration, Markov decision processes}
}

@article{10.5555/2503308.2503338,
author = {Sabato, Sivan and Tishby, Naftali},
title = {Multi-Instance Learning with Any Hypothesis Class},
year = {2012},
issue_date = {January 2012},
publisher = {JMLR.org},
volume = {13},
number = {1},
issn = {1532-4435},
abstract = {In the supervised learning setting termed Multiple-Instance Learning (MIL), the examples are bags of instances, and the bag label is a function of the labels of its instances. Typically, this function is the Boolean OR. The learner observes a sample of bags and the bag labels, but not the instance labels that determine the bag labels. The learner is then required to emit a classification rule for bags based on the sample. MIL has numerous applications, and many heuristic algorithms have been used successfully on this problem, each adapted to specific settings or applications. In this work we provide a unified theoretical analysis for MIL, which holds for any underlying hypothesis class, regardless of a specific application or problem domain. We show that the sample complexity of MIL is only poly-logarithmically dependent on the size of the bag, for any underlying hypothesis class. In addition, we introduce a new PAC-learning algorithm for MIL, which uses a regular supervised learning algorithm as an oracle. We prove that efficient PAC-learning for MIL can be generated from any efficient non-MIL supervised learning algorithm that handles one-sided error. The computational complexity of the resulting algorithm is only polynomially dependent on the bag size.},
journal = {J. Mach. Learn. Res.},
month = oct,
pages = {2999–3039},
numpages = {41},
keywords = {sample complexity, multiple-instance learning, supervised classification, PAC learning, learning theory}
}

@article{10.5555/2503308.2503337,
author = {Verstraeten, David and Schrauwen, Benjamin and Dieleman, Sander and Brakel, Philemon and Buteneers, Pieter and Pecevski, Dejan},
title = {Oger: Modular Learning Architectures for Large-Scale Sequential Processing},
year = {2012},
issue_date = {January 2012},
publisher = {JMLR.org},
volume = {13},
number = {1},
issn = {1532-4435},
abstract = {Oger (OrGanic Environment for Reservoir computing) is a Python toolbox for building, training and evaluating modular learning architectures on large data sets. It builds on MDP for its modularity, and adds processing of sequential data sets, gradient descent training, several crossvalidation schemes and parallel parameter optimization methods. Additionally, several learning algorithms are implemented, such as different reservoir implementations (both sigmoid and spiking), ridge regression, conditional restricted Boltzmann machine (CRBM) and others, including GPU accelerated versions. Oger is released under the GNU LGPL, and is available from http: //organic.elis.ugent.be/oger.},
journal = {J. Mach. Learn. Res.},
month = oct,
pages = {2995–2998},
numpages = {4},
keywords = {Python, modular architectures, sequential processing}
}

@article{10.5555/2503308.2503336,
author = {Su, Xiaogang and Kang, Joseph and Fan, Juanjuan and Levine, Richard A. and Yan, Xin},
title = {Facilitating Score and Causal Inference Trees for Large Observational Studies},
year = {2012},
issue_date = {January 2012},
publisher = {JMLR.org},
volume = {13},
number = {1},
issn = {1532-4435},
abstract = {Assessing treatment effects in observational studies is a multifaceted problem that not only involves heterogeneous mechanisms of how the treatment or cause is exposed to subjects, known as propensity, but also differential causal effects across sub-populations. We introduce a concept termed the facilitating score to account for both the confounding and interacting impacts of covariates on the treatment effect. Several approaches for estimating the facilitating score are discussed. In particular, we put forward a machine learning method, called causal inference tree (CIT), to provide a piecewise constant approximation of the facilitating score. With interpretable rules, CIT splits data in such a way that both the propensity and the treatment effect become more homogeneous within each resultant partition. Causal inference at different levels can be made on the basis of CIT. Together with an aggregated grouping procedure, CIT stratifies data into strata where causal effects can be conveniently assessed within each. Besides, a feasible way of predicting individual causal effects (ICE) is made available by aggregating ensemble CIT models. Both the stratified results and the estimated ICE provide an assessment of heterogeneity of causal effects and can be integrated for estimating the average causal effect (ACE). Mean square consistency of CIT is also established. We evaluate the performance of proposed methods with simulations and illustrate their use with the NSW data in Dehejia and Wahba (1999) where the objective is to assess the impact of a labor training program, the National SupportedWork (NSW) demonstration, on post-intervention earnings.},
journal = {J. Mach. Learn. Res.},
month = oct,
pages = {2955–2994},
numpages = {40},
keywords = {personalized medicine, causal inference, observational study, CART, recursive partitioning, confounding, interaction}
}

@article{10.5555/2503308.2503335,
author = {Ben-Tal, Aharon and Bhadra, Sahely and Bhattacharyya, Chiranjib and Nemirovski, Arkadi},
title = {Efficient Methods for Robust Classification under Uncertainty in Kernel Matrices},
year = {2012},
issue_date = {January 2012},
publisher = {JMLR.org},
volume = {13},
number = {1},
issn = {1532-4435},
abstract = {In this paper we study the problem of designing SVM classifiers when the kernel matrix, K, is affected by uncertainty. Specifically K is modeled as a positive affine combination of given positive semi definite kernels, with the coefficients ranging in a norm-bounded uncertainty set. We treat the problem using the Robust Optimization methodology. This reduces the uncertain SVM problem into a deterministic conic quadratic problem which can be solved in principle by a polynomial time Interior Point (IP) algorithm. However, for large-scale classification problems, IP methods become intractable and one has to resort to first-order gradient type methods. The strategy we use here is to reformulate the robust counterpart of the uncertain SVM problem as a saddle point problem and employ a special gradient scheme which works directly on the convex-concave saddle function. The algorithm is a simplified version of a general scheme due to Juditski and Nemirovski (2011). It achieves an O(1/T2) reduction of the initial error after T iterations. A comprehensive empirical study on both synthetic data and real-world protein structure data sets show that the proposed formulations achieve the desired robustness, and the saddle point based algorithm outperforms the IP method significantly.},
journal = {J. Mach. Learn. Res.},
month = oct,
pages = {2923–2954},
numpages = {32},
keywords = {robust optimization, kernel functions, uncertain classification}
}

@article{10.5555/2503308.2503334,
author = {Hazan, Elad and Kale, Satyen},
title = {Online Submodular Minimization},
year = {2012},
issue_date = {January 2012},
publisher = {JMLR.org},
volume = {13},
number = {1},
issn = {1532-4435},
abstract = {We consider an online decision problem over a discrete space in which the loss function is submodular. We give algorithms which are computationally efficient and are Hannan-consistent in both the full information and partial feedback settings.},
journal = {J. Mach. Learn. Res.},
month = oct,
pages = {2903–2922},
numpages = {20},
keywords = {submodular optimization, online learning, regret minimization}
}

@article{10.5555/2503308.2503333,
author = {Schnitzer, Dominik and Flexer, Arthur and Schedl, Markus and Widmer, Gerhard},
title = {Local and Global Scaling Reduce Hubs in Space},
year = {2012},
issue_date = {January 2012},
publisher = {JMLR.org},
volume = {13},
number = {1},
issn = {1532-4435},
abstract = { 'Hubness' has recently been identified as a general problem of high dimensional data spaces, manifesting itself in the emergence of objects, so-called hubs, which tend to be among the k nearest neighbors of a large number of data items. As a consequence many nearest neighbor relations in the distance space are asymmetric, that is, object y is amongst the nearest neighbors of x but not vice versa. The work presented here discusses two classes of methods that try to symmetrize nearest neighbor relations and investigates to what extent they can mitigate the negative effects of hubs. We evaluate local distance scaling and propose a global variant which has the advantage of being easy to approximate for large data sets and of having a probabilistic interpretation. Both local and global approaches are shown to be effective especially for high-dimensional data sets, which are affected by high hubness. Both methods lead to a strong decrease of hubness in these data sets, while at the same time improving properties like classification accuracy. We evaluate the methods on a large number of public machine learning data sets and synthetic data. Finally we present a real-world application where we are able to achieve significantly higher retrieval quality.},
journal = {J. Mach. Learn. Res.},
month = oct,
pages = {2871–2902},
numpages = {32},
keywords = {classification, local and global scaling, nearest neighbor relation, curse of dimensionality, hubness, shared near neighbors}
}

@article{10.5555/2503308.2503332,
author = {Hern\'{a}ndez-Orallo, Jos\'{e} and Flach, Peter and Ferri, C\`{e}sar},
title = {A Unified View of Performance Metrics: Translating Threshold Choice into Expected Classification Loss},
year = {2012},
issue_date = {January 2012},
publisher = {JMLR.org},
volume = {13},
number = {1},
issn = {1532-4435},
abstract = {Many performance metrics have been introduced in the literature for the evaluation of classification performance, each of them with different origins and areas of application. These metrics include accuracy, unweighted accuracy, the area under the ROC curve or the ROC convex hull, the mean absolute error and the Brier score or mean squared error (with its decomposition into refinement and calibration). One way of understanding the relations among these metrics is by means of variable operating conditions (in the form of misclassification costs and/or class distributions). Thus, a metric may correspond to some expected loss over different operating conditions. One dimension for the analysis has been the distribution for this range of operating conditions, leading to some important connections in the area of proper scoring rules. We demonstrate in this paper that there is an equally important dimension which has so far received much less attention in the analysis of performance metrics. This dimension is given by the decision rule, which is typically implemented as a threshold choice method when using scoring models. In this paper, we explore many old and new threshold choice methods: fixed, score-uniform, score-driven, rate-driven and optimal, among others. By calculating the expected loss obtained with these threshold choice methods for a uniform range of operating conditions we give clear interpretations of the 0-1 loss, the absolute error, the Brier score, the AUC and the refinement loss respectively. Our analysis provides a comprehensive view of performance metrics as well as a systematic approach to loss minimisation which can be summarised as follows: given a model, apply the threshold choice methods that correspond with the available information about the operating condition, and compare their expected losses. In order to assist in this procedure we also derive several connections between the aforementioned performance metrics, and we highlight the role of calibration in choosing the threshold choice method.},
journal = {J. Mach. Learn. Res.},
month = oct,
pages = {2813–2869},
numpages = {57},
keywords = {calibration loss, classification performance metrics, cost-sensitive evaluation, operating condition, Brier score, refinement loss, area under the ROC curve (AUC)}
}

@article{10.5555/2503308.2503331,
author = {Solnon, Matthieu and Arlot, Sylvain and Bach, Francis},
title = {Multi-Task Regression Using Minimal Penalties},
year = {2012},
issue_date = {January 2012},
publisher = {JMLR.org},
volume = {13},
number = {1},
issn = {1532-4435},
abstract = {In this paper we study the kernel multiple ridge regression framework, which we refer to as multitask regression, using penalization techniques. The theoretical analysis of this problem shows that the key element appearing for an optimal calibration is the covariance matrix of the noise between the different tasks. We present a new algorithm to estimate this covariance matrix, based on the concept of minimal penalty, which was previously used in the single-task regression framework to estimate the variance of the noise. We show, in a non-asymptotic setting and under mild assumptions on the target function, that this estimator converges towards the covariance matrix. Then plugging this estimator into the corresponding ideal penalty leads to an oracle inequality. We illustrate the behavior of our algorithm on synthetic examples.},
journal = {J. Mach. Learn. Res.},
month = sep,
pages = {2773–2812},
numpages = {40},
keywords = {oracle inequality, learning theory, multi-task}
}

@article{10.5555/2503308.2503330,
author = {Maillard, Odalric-Ambrym and Munos, R\'{e}mi},
title = {Linear Regression with Random Projections},
year = {2012},
issue_date = {January 2012},
publisher = {JMLR.org},
volume = {13},
number = {1},
issn = {1532-4435},
abstract = {We investigate a method for regression that makes use of a randomly generated subspace GP ⊂ F (of finite dimension P) of a given large (possibly infinite) dimensional function space F, for example, L2([0,1]d;R). GP is defined as the span of P random features that are linear combinations of a basis functions of F weighted by random Gaussian i.i.d. coefficients. We show practical motivation for the use of this approach, detail the link that this random projections method share with RKHS and Gaussian objects theory and prove, both in deterministic and random design, approximation error bounds when searching for the best regression function in GP rather than in F, and derive excess risk bounds for a specific regression algorithm (least squares regression in GP). This paper stresses the motivation to study such methods, thus the analysis developed is kept simple for explanations purpose and leaves room for future developments.},
journal = {J. Mach. Learn. Res.},
month = sep,
pages = {2735–2772},
numpages = {38},
keywords = {random matrices, regression, dimension reduction}
}

@article{10.5555/2503308.2503329,
author = {Zhang, Zhihua and Liu, Dehua and Dai, Guang and Jordan, Michael I.},
title = {Coherence Functions with Applications in Large-Margin Classification Methods},
year = {2012},
issue_date = {January 2012},
publisher = {JMLR.org},
volume = {13},
number = {1},
issn = {1532-4435},
abstract = {Support vector machines (SVMs) naturally embody sparseness due to their use of hinge loss functions. However, SVMs can not directly estimate conditional class probabilities. In this paper we propose and study a family of coherence functions, which are convex and differentiable, as surrogates of the hinge function. The coherence function is derived by using the maximum-entropy principle and is characterized by a temperature parameter. It bridges the hinge function and the logit function in logistic regression. The limit of the coherence function at zero temperature corresponds to the hinge function, and the limit of the minimizer of its expected error is the minimizer of the expected error of the hinge loss. We refer to the use of the coherence function in large-margin classification as "C-learning," and we present efficient coordinate descent algorithms for the training of regularized C-learning models.},
journal = {J. Mach. Learn. Res.},
month = sep,
pages = {2705–2734},
numpages = {30},
keywords = {c-learning, coherence functions, large-margin classifiers, hinge functions, logistic functions}
}

@article{10.5555/2503308.2503328,
author = {Lee, Joonseok and Sun, Mingxuan and Lebanon, Guy},
title = {PREA: Personalized Recommendation Algorithms Toolkit},
year = {2012},
issue_date = {January 2012},
publisher = {JMLR.org},
volume = {13},
number = {1},
issn = {1532-4435},
abstract = {Recommendation systems are important business applications with significant economic impact. In recent years, a large number of algorithms have been proposed for recommendation systems. In this paper, we describe an open-source toolkit implementing many recommendation algorithms as well as popular evaluation metrics. In contrast to other packages, our toolkit implements recent state-of-the-art algorithms as well as most classic algorithms.},
journal = {J. Mach. Learn. Res.},
month = sep,
pages = {2699–2703},
numpages = {5},
keywords = {recommender systems, evaluation metrics, collaborative filtering}
}

@article{10.5555/2503308.2503327,
author = {Dekel, Ofer and Gentile, Claudio and Sridharan, Karthik},
title = {Selective Sampling and Active Learning from Single and Multiple Teachers},
year = {2012},
issue_date = {January 2012},
publisher = {JMLR.org},
volume = {13},
number = {1},
issn = {1532-4435},
abstract = {We present a new online learning algorithm in the selective sampling framework, where labels must be actively queried before they are revealed. We prove bounds on the regret of our algorithm and on the number of labels it queries when faced with an adaptive adversarial strategy of generating the instances. Our bounds both generalize and strictly improve over previous bounds in similar settings. Additionally, our selective sampling algorithm can be converted into an efficient statistical active learning algorithm. We extend our algorithm and analysis to the multiple-teacher setting, where the algorithm can choose which subset of teachers to query for each label. Finally, we demonstrate the effectiveness of our techniques on a real-world Internet search problem.},
journal = {J. Mach. Learn. Res.},
month = sep,
pages = {2655–2697},
numpages = {43},
keywords = {crowdsourcing, regret, online learning, label-efficient}
}

@article{10.5555/2503308.2503326,
author = {Br\"{u}ckner, Michael and Kanzow, Christian and Scheffer, Tobias},
title = {Static Prediction Games for Adversarial Learning Problems},
year = {2012},
issue_date = {January 2012},
publisher = {JMLR.org},
volume = {13},
number = {1},
issn = {1532-4435},
abstract = {The standard assumption of identically distributed training and test data is violated when the test data are generated in response to the presence of a predictive model. This becomes apparent, for example, in the context of email spam filtering. Here, email service providers employ spam filters, and spam senders engineer campaign templates to achieve a high rate of successful deliveries despite the filters. We model the interaction between the learner and the data generator as a static game in which the cost functions of the learner and the data generator are not necessarily antagonistic. We identify conditions under which this prediction game has a unique Nash equilibrium and derive algorithms that find the equilibrial prediction model. We derive two instances, the Nash logistic regression and the Nash support vector machine, and empirically explore their properties in a case study on email spam filtering.},
journal = {J. Mach. Learn. Res.},
month = sep,
pages = {2617–2654},
numpages = {38},
keywords = {static prediction games, adversarial classification, Nash equilibrium}
}

@article{10.5555/2503308.2503325,
author = {Nayak, Sunita and Duncan, Kester and Sarkar, Sudeep and Loeding, Barbara},
title = {Finding Recurrent Patterns from Continuous Sign Language Sentences for Automated Extraction of Signs},
year = {2012},
issue_date = {January 2012},
publisher = {JMLR.org},
volume = {13},
number = {1},
issn = {1532-4435},
abstract = {We present a probabilistic framework to automatically learn models of recurring signs from multiple sign language video sequences containing the vocabulary of interest. We extract the parts of the signs that are present in most occurrences of the sign in context and are robust to the variations produced by adjacent signs. Each sentence video is first transformed into a multidimensional time series representation, capturing the motion and shape aspects of the sign. Skin color blobs are extracted from frames of color video sequences, and a probabilistic relational distribution is formed for each frame using the contour and edge pixels from the skin blobs. Each sentence is represented as a trajectory in a low dimensional space called the space of relational distributions. Given these time series trajectories, we extract signemes from multiple sentences concurrently using iterated conditional modes (ICM). We show results by learning single signs from a collection of sentences with one common pervading sign, multiple signs from a collection of sentences with more than one common sign, and single signs from a mixed collection of sentences. The extracted signemes demonstrate that our approach is robust to some extent to the variations produced within a sign due to different contexts. We also show results whereby these learned sign models are used for spotting signs in test sequences.},
journal = {J. Mach. Learn. Res.},
month = sep,
pages = {2589–2615},
numpages = {27},
keywords = {pattern extraction, iterated conditional modes, sign modeling, signeme extraction, sign language recognition}
}

@article{10.5555/2503308.2503324,
author = {Snoek, Jasper and Adams, Ryan P. and Larochelle, Hugo},
title = {Nonparametric Guidance of Autoencoder Representations Using Label Information},
year = {2012},
issue_date = {January 2012},
publisher = {JMLR.org},
volume = {13},
number = {1},
issn = {1532-4435},
abstract = {While unsupervised learning has long been useful for density modeling, exploratory data analysis and visualization, it has become increasingly important for discovering features that will later be used for discriminative tasks. Discriminative algorithms often work best with highly-informative features; remarkably, such features can often be learned without the labels. One particularly effective way to perform such unsupervised learning has been to use autoencoder neural networks, which find latent representations that are constrained but nevertheless informative for reconstruction. However, pure unsupervised learning with autoencoders can find representations that may or may not be useful for the ultimate discriminative task. It is a continuing challenge to guide the training of an autoencoder so that it finds features which will be useful for predicting labels. Similarly, we often have a priori information regarding what statistical variation will be irrelevant to the ultimate discriminative task, and we would like to be able to use this for guidance as well. Although a typical strategy would be to include a parametric discriminative model as part of the autoencoder training, here we propose a nonparametric approach that uses a Gaussian process to guide the representation. By using a nonparametric model, we can ensure that a useful discriminative function exists for a given set of features, without explicitly instantiating it. We demonstrate the superiority of this guidance mechanism on four data sets, including a real-world application to rehabilitation research. We also show how our proposed approach can learn to explicitly ignore statistically significant covariate information that is label-irrelevant, by evaluating on the small NORB image recognition problem in which pose and lighting labels are available.},
journal = {J. Mach. Learn. Res.},
month = sep,
pages = {2567–2588},
numpages = {22},
keywords = {gaussian process latent variable model, gaussian process, autoencoder, unsupervised learning, representation learning}
}

@article{10.5555/2503308.2503323,
author = {Kim, JooSeuk and Scott, Clayton D.},
title = {Robust Kernel Density Estimation},
year = {2012},
issue_date = {January 2012},
publisher = {JMLR.org},
volume = {13},
number = {1},
issn = {1532-4435},
abstract = {We propose a method for nonparametric density estimation that exhibits robustness to contamination of the training sample. This method achieves robustness by combining a traditional kernel density estimator (KDE) with ideas from classical M-estimation. We interpret the KDE based on a positive semi-definite kernel as a sample mean in the associated reproducing kernel Hilbert space. Since the sample mean is sensitive to outliers, we estimate it robustly via M-estimation, yielding a robust kernel density estimator (RKDE).An RKDE can be computed efficiently via a kernelized iteratively re-weighted least squares (IRWLS) algorithm. Necessary and sufficient conditions are given for kernelized IRWLS to converge to the global minimizer of the M-estimator objective function. The robustness of the RKDE is demonstrated with a representer theorem, the influence function, and experimental results for density estimation and anomaly detection.},
journal = {J. Mach. Learn. Res.},
month = sep,
pages = {2529–2565},
numpages = {37},
keywords = {outlier, reproducing kernel Hilbert space, influence function, kernel trick, M-estimation}
}

@article{10.5555/2503308.2503322,
author = {Mahdavi, Mehrdad and Jin, Rong and Yang, Tianbao},
title = {Trading Regret for Efficiency: Online Convex Optimization with Long Term Constraints},
year = {2012},
issue_date = {January 2012},
publisher = {JMLR.org},
volume = {13},
number = {1},
issn = {1532-4435},
abstract = {In this paper we propose efficient algorithms for solving constrained online convex optimization problems. Our motivation stems from the observation that most algorithms proposed for online convex optimization require a projection onto the convex set Κ from which the decisions are made. While the projection is straightforward for simple shapes (e.g., Euclidean ball), for arbitrary complex sets it is the main computational challenge and may be inefficient in practice. In this paper, we consider an alternative online convex optimization problem. Instead of requiring that decisions belong to Κ for all rounds, we only require that the constraints, which define the set Κ, be satisfied in the long run. By turning the problem into an online convex-concave optimization problem, we propose an efficient algorithm which achieves O(√T) regret bound and O(T3/4) bound on the violation of constraints. Then, we modify the algorithm in order to guarantee that the constraints are satisfied in the long run. This gain is achieved at the price of getting O(T3/4) regret bound. Our second algorithm is based on the mirror prox method (Nemirovski, 2005) to solve variational inequalities which achieves O(T2/3) bound for both regret and the violation of constraints when the domain Κ can be described by a finite number of linear constraints. Finally, we extend the results to the setting where we only have partial access to the convex set Κ and propose a multipoint bandit feedback algorithm with the same bounds in expectation as our first algorithm.},
journal = {J. Mach. Learn. Res.},
month = sep,
pages = {2503–2528},
numpages = {26},
keywords = {bandit feedback, convex-concave optimization, variational inequality, online convex optimization}
}

@article{10.5555/2503308.2503321,
author = {Kloft, Marius and Blanchard, Gilles},
title = {On the Convergence Rate of l<sub>p</sub>-Norm Multiple Kernel Learning},
year = {2012},
issue_date = {January 2012},
publisher = {JMLR.org},
volume = {13},
number = {1},
issn = {1532-4435},
abstract = {We derive an upper bound on the local Rademacher complexity of lp-norm multiple kernel learning, which yields a tighter excess risk bound than global approaches. Previous local approaches analyzed the case p = 1 only while our analysis covers all cases 1 ≤ p ≤ ∞, assuming the different feature mappings corresponding to the different kernels to be uncorrelated. We also show a lower bound that shows that the bound is tight, and derive consequences regarding excess loss, namely fast convergence rates of the order O(n-α/1+a), where α is the minimum eigenvalue decay rate of the individual kernels.},
journal = {J. Mach. Learn. Res.},
month = aug,
pages = {2465–2502},
numpages = {38},
keywords = {learning kernels, local Rademacher complexity, generalization bounds, multiple kernel learning}
}

@article{10.5555/2503308.2503320,
author = {Hauser, Alain and B\"{u}hlmann, Peter},
title = {Characterization and Greedy Learning of Interventional Markov Equivalence Classes of Directed Acyclic Graphs},
year = {2012},
issue_date = {January 2012},
publisher = {JMLR.org},
volume = {13},
number = {1},
issn = {1532-4435},
abstract = {The investigation of directed acyclic graphs (DAGs) encoding the same Markov property, that is the same conditional independence relations of multivariate observational distributions, has a long tradition; many algorithms exist for model selection and structure learning in Markov equivalence classes. In this paper, we extend the notion of Markov equivalence of DAGs to the case of interventional distributions arising from multiple intervention experiments. We show that under reasonable assumptions on the intervention experiments, interventionalMarkov equivalence defines a finer partitioning of DAGs than observational Markov equivalence and hence improves the identifiability of causal models. We give a graph theoretic criterion for two DAGs being Markov equivalent under interventions and show that each interventional Markov equivalence class can, analogously to the observational case, be uniquely represented by a chain graph called interventional essential graph (also known as CPDAG in the observational case). These are key insights for deriving a generalization of the Greedy Equivalence Search algorithm aimed at structure learning from interventional data. This new algorithm is evaluated in a simulation study.},
journal = {J. Mach. Learn. Res.},
month = aug,
pages = {2409–2464},
numpages = {56},
keywords = {interventions, causal inference, greedy equivalence search, Markov equivalence, graphical model}
}

@article{10.5555/2503308.2503319,
author = {Aho, Timo and \v{Z}enko, Bernard and D\v{z}eroski, Sa\c{s}o and Elomaa, Tapio},
title = {Multi-Target Regression with Rule Ensembles},
year = {2012},
issue_date = {January 2012},
publisher = {JMLR.org},
volume = {13},
number = {1},
issn = {1532-4435},
abstract = {Methods for learning decision rules are being successfully applied to many problem domains, in particular when understanding and interpretation of the learned model is necessary. In many real life problems, we would like to predict multiple related (nominal or numeric) target attributes simultaneously. While several methods for learning rules that predict multiple targets at once exist, they are all based on the covering algorithm, which does not work well for regression problems. A better solution for regression is the rule ensemble approach that transcribes an ensemble of decision trees into a large collection of rules. An optimization procedure is then used to select the best (and much smaller) subset of these rules and to determine their respective weights.We introduce the FIRE algorithm for solving multi-target regression problems, which employs the rule ensembles approach. We improve the accuracy of the algorithm by adding simple linear functions to the ensemble. We also extensively evaluate the algorithm with and without linear functions. The results show that the accuracy of multi-target regression rule ensembles is high. They are more accurate than, for instance, multi-target regression trees, but not quite as accurate as multi-target random forests. The rule ensembles are significantly more concise than random forests, and it is also possible to create compact rule sets that are smaller than a single regression tree but still comparable in accuracy.},
journal = {J. Mach. Learn. Res.},
month = aug,
pages = {2367–2407},
numpages = {41},
keywords = {multi-target prediction, rule learning, rule ensembles, regression}
}

@article{10.5555/2503308.2503318,
author = {Mahoney, Michael W. and Orecchia, Lorenzo and Vishnoi, Nisheeth K.},
title = {A Local Spectral Method for Graphs: With Applications to Improving Graph Partitions and Exploring Data Graphs Locally},
year = {2012},
issue_date = {January 2012},
publisher = {JMLR.org},
volume = {13},
number = {1},
issn = {1532-4435},
abstract = {The second eigenvalue of the Laplacian matrix and its associated eigenvector are fundamental features of an undirected graph, and as such they have found widespread use in scientific computing, machine learning, and data analysis. In many applications, however, graphs that arise have several local regions of interest, and the second eigenvector will typically fail to provide information fine-tuned to each local region. In this paper, we introduce a locally-biased analogue of the second eigenvector, and we demonstrate its usefulness at highlighting local properties of data graphs in a semi-supervised manner. To do so, we first view the second eigenvector as the solution to a constrained optimization problem, and we incorporate the local information as an additional constraint; we then characterize the optimal solution to this new problem and show that it can be interpreted as a generalization of a Personalized PageRank vector; and finally, as a consequence, we show that the solution can be computed in nearly-linear time. In addition, we show that this locally-biased vector can be used to compute an approximation to the best partition near an input seed set in a manner analogous to the way in which the second eigenvector of the Laplacian can be used to obtain an approximation to the best partition in the entire input graph. Such a primitive is useful for identifying and refining clusters locally, as it allows us to focus on a local region of interest in a semi-supervised manner. Finally, we provide a detailed empirical evaluation of our method by showing how it can applied to finding locally-biased sparse cuts around an input vertex seed set in social and information networks.},
journal = {J. Mach. Learn. Res.},
month = aug,
pages = {2339–2365},
numpages = {27},
keywords = {spectral graph partitioning, local spectral algorithms, personalized pagerank, Laplacian matrix, semi-supervised learning}
}

@article{10.5555/2503308.2503317,
author = {Anandkumar, Animashree and Tan, Vincent Y. F. and Huang, Furong and Willsky, Alan S.},
title = {High-Dimensional Gaussian Graphical Model Selection: Walk Summability and Local Separation Criterion},
year = {2012},
issue_date = {January 2012},
publisher = {JMLR.org},
volume = {13},
number = {1},
issn = {1532-4435},
abstract = {We consider the problem of high-dimensional Gaussian graphical model selection. We identify a set of graphs for which an efficient estimation algorithm exists, and this algorithm is based on thresholding of empirical conditional covariances. Under a set of transparent conditions, we establish structural consistency (or sparsistency) for the proposed algorithm, when the number of samples n = Ω(Jmin-2 log p), where p is the number of variables and Jmin is the minimum (absolute) edge potential of the graphical model. The sufficient conditions for sparsistency are based on the notion of walk-summability of the model and the presence of sparse local vertex separators in the underlying graph. We also derive novel non-asymptotic necessary conditions on the number of samples required for sparsistency.},
journal = {J. Mach. Learn. Res.},
month = aug,
pages = {2293–2337},
numpages = {45},
keywords = {high-dimensional learning, Gaussian graphical model selection, walk-summability, necessary conditions for model selection, local-separation property}
}

@article{10.5555/2503308.2503316,
author = {Brunner, Carl and Fischer, Andreas and Luig, Klaus and Thies, Thorsten},
title = {Pairwise Support Vector Machines and Their Application to Large Scale Problems},
year = {2012},
issue_date = {January 2012},
publisher = {JMLR.org},
volume = {13},
number = {1},
issn = {1532-4435},
abstract = {Pairwise classification is the task to predict whether the examples a,b of a pair (a,b) belong to the same class or to different classes. In particular, interclass generalization problems can be treated in this way. In pairwise classification, the order of the two input examples should not affect the classification result. To achieve this, particular kernels as well as the use of symmetric training sets in the framework of support vector machines were suggested. The paper discusses both approaches in a general way and establishes a strong connection between them. In addition, an efficient implementation is discussed which allows the training of several millions of pairs. The value of these contributions is confirmed by excellent results on the labeled faces in the wild benchmark.},
journal = {J. Mach. Learn. Res.},
month = aug,
pages = {2279–2292},
numpages = {14},
keywords = {large scale problems, interclass generalization, pairwise support vector machines, pairwise kernels}
}

@article{10.5555/2503308.2503315,
author = {Zhu, Jun and Ahmed, Amr and Xing, Eric P.},
title = {MedLDA: Maximum Margin Supervised Topic Models},
year = {2012},
issue_date = {January 2012},
publisher = {JMLR.org},
volume = {13},
number = {1},
issn = {1532-4435},
abstract = {A supervised topic model can use side information such as ratings or labels associated with documents or images to discover more predictive low dimensional topical representations of the data. However, existing supervised topic models predominantly employ likelihood-driven objective functions for learning and inference, leaving the popular and potentially powerful max-margin principle unexploited for seeking predictive representations of data and more discriminative topic bases for the corpus. In this paper, we propose the maximum entropy discrimination latent Dirichlet allocation (MedLDA) model, which integrates the mechanism behind the max-margin prediction models (e.g., SVMs) with the mechanism behind the hierarchical Bayesian topic models (e.g., LDA) under a unified constrained optimization framework, and yields latent topical representations that are more discriminative and more suitable for prediction tasks such as document classification or regression. The principle underlying the MedLDA formalism is quite general and can be applied for jointly max-margin and maximum likelihood learning of directed or undirected topic models when supervising side information is available. Efficient variational methods for posterior inference and parameter estimation are derived and extensive empirical studies on several real data sets are also provided. Our experimental results demonstrate qualitatively and quantitatively that MedLDA could: 1) discover sparse and highly discriminative topical representations; 2) achieve state of the art prediction performance; and 3) be more efficient than existing supervised topic models, especially for classification.},
journal = {J. Mach. Learn. Res.},
month = aug,
pages = {2237–2278},
numpages = {42},
keywords = {supervised topic models, support vector machines, latent Dirichlet allocation, maximum entropy discrimination, max-margin learning}
}

@article{10.5555/2503308.2503314,
author = {Zeng, Jia},
title = {A Topic Modeling Toolbox Using Belief Propagation},
year = {2012},
issue_date = {January 2012},
publisher = {JMLR.org},
volume = {13},
number = {1},
issn = {1532-4435},
abstract = {Latent Dirichlet allocation (LDA) is an important hierarchical Bayesian model for probabilistic topic modeling, which attracts worldwide interests and touches on many important applications in text mining, computer vision and computational biology. This paper introduces a topic modeling toolbox (TMBP) based on the belief propagation (BP) algorithms. TMBP toolbox is implemented by MEX C++/Matlab/Octave for either Windows 7 or Linux. Compared with existing topic modeling packages, the novelty of this toolbox lies in the BP algorithms for learning LDA-based topic models. The current version includes BP algorithms for latent Dirichlet allocation (LDA), authortopic models (ATM), relational topic models (RTM), and labeled LDA (LaLDA). This toolbox is an ongoing project and more BP-based algorithms for various topic models will be added in the near future. Interested users may also extend BP algorithms for learning more complicated topic models. The source codes are freely available under the GNU General Public Licence, Version 1.0 at https://mloss.org/software/view/399/.},
journal = {J. Mach. Learn. Res.},
month = jul,
pages = {2233–2236},
numpages = {4},
keywords = {belief propagation, variational Bayes, topic models, Gibbs sampling}
}

@article{10.5555/2503308.2503313,
author = {Cooper, Helen and Ong, Eng-Jon and Pugeault, Nicolas and Bowden, Richard},
title = {Sign Language Recognition Using Sub-Units},
year = {2012},
issue_date = {January 2012},
publisher = {JMLR.org},
volume = {13},
number = {1},
issn = {1532-4435},
abstract = {This paper discusses sign language recognition using linguistic sub-units. It presents three types of sub-units for consideration; those learnt from appearance data as well as those inferred from both 2D or 3D tracking data. These sub-units are then combined using a sign level classifier; here, two options are presented. The first uses Markov Models to encode the temporal changes between sub-units. The second makes use of Sequential Pattern Boosting to apply discriminative feature selection at the same time as encoding temporal information. This approach is more robust to noise and performs well in signer independent tests, improving results from the 54% achieved by the Markov Chains to 76%.},
journal = {J. Mach. Learn. Res.},
month = jul,
pages = {2205–2231},
numpages = {27},
keywords = {sub-units, data set, depth cameras, sign language recognition, sequential pattern boosting, signer independence}
}

@article{10.5555/2503308.2503312,
author = {Barbu, Adrian and Lay, Nathan},
title = {An Introduction to Artificial Prediction Markets for Classification},
year = {2012},
issue_date = {January 2012},
publisher = {JMLR.org},
volume = {13},
number = {1},
issn = {1532-4435},
abstract = {Prediction markets are used in real life to predict outcomes of interest such as presidential elections. This paper presents a mathematical theory of artificial prediction markets for supervised learning of conditional probability estimators. The artificial prediction market is a novel method for fusing the prediction information of features or trained classifiers, where the fusion result is the contract price on the possible outcomes. The market can be trained online by updating the participants' budgets using training examples. Inspired by the real prediction markets, the equations that govern the market are derived from simple and reasonable assumptions. Efficient numerical algorithms are presented for solving these equations. The obtained artificial prediction market is shown to be a maximum likelihood estimator. It generalizes linear aggregation, existent in boosting and random forest, as well as logistic regression and some kernel methods. Furthermore, the market mechanism allows the aggregation of specialized classifiers that participate only on specific instances. Experimental comparisons show that the artificial prediction markets often outperform random forest and implicit online learning on synthetic data and real UCI data sets. Moreover, an extensive evaluation for pelvic and abdominal lymph node detection in CT data shows that the prediction market improves adaboost's detection rate from 79.6% to 81.2% at 3 false positives/volume.},
journal = {J. Mach. Learn. Res.},
month = jul,
pages = {2177–2204},
numpages = {28},
keywords = {supervised learning, ensemble methods, implicit online learning, online learning, random forest}
}

@article{10.5555/2503308.2503311,
author = {Fortin, F\'{e}lix-Antoine and De Rainville, Fran\c{c}ois-Michel and Gardner, Marc-Andr\'{e} Gardner and Parizeau, Marc and Gagn\'{e}, Christian},
title = {DEAP: Evolutionary Algorithms Made Easy},
year = {2012},
issue_date = {January 2012},
publisher = {JMLR.org},
volume = {13},
number = {1},
issn = {1532-4435},
abstract = {DEAP is a novel evolutionary computation framework for rapid prototyping and testing of ideas. Its design departs from most other existing frameworks in that it seeks to make algorithms explicit and data structures transparent, as opposed to the more common black-box frameworks. Freely available with extensive documentation at http://deap.gel.ulaval.ca, DEAP is an open source project under an LGPL license.},
journal = {J. Mach. Learn. Res.},
month = jul,
pages = {2171–2175},
numpages = {5},
keywords = {software tools, distributed evolutionary algorithms}
}

@article{10.5555/2503308.2503310,
author = {Helmbold, David P. and Long, Philip M.},
title = {On the Necessity of Irrelevant Variables},
year = {2012},
issue_date = {January 2012},
publisher = {JMLR.org},
volume = {13},
number = {1},
issn = {1532-4435},
abstract = {This work explores the effects of relevant and irrelevant boolean variables on the accuracy of classifiers. The analysis uses the assumption that the variables are conditionally independent given the class, and focuses on a natural family of learning algorithms for such sources when the relevant variables have a small advantage over random guessing. The main result is that algorithms relying predominately on irrelevant variables have error probabilities that quickly go to 0 in situations where algorithms that limit the use of irrelevant variables have errors bounded below by a positive constant. We also show that accurate learning is possible even when there are so few examples that one cannot determine with high confidence whether or not any individual variable is relevant.},
journal = {J. Mach. Learn. Res.},
month = jul,
pages = {2145–2170},
numpages = {26},
keywords = {learning theory, feature selection, generalization}
}

@article{10.5555/2503308.2343712,
author = {Genovese, Christopher R. and Jin, Jiashun and Wasserman, Larry and Yao, Zhigang},
title = {A Comparison of the Lasso and Marginal Regression},
year = {2012},
issue_date = {January 2012},
publisher = {JMLR.org},
volume = {13},
number = {1},
issn = {1532-4435},
abstract = {The lasso is an important method for sparse, high-dimensional regression problems, with efficient algorithms available, a long history of practical success, and a large body of theoretical results supporting and explaining its performance. But even with the best available algorithms, finding the lasso solutions remains a computationally challenging task in cases where the number of covariates vastly exceeds the number of data points.Marginal regression, where each dependent variable is regressed separately on each covariate, offers a promising alternative in this case because the estimates can be computed roughly two orders faster than the lasso solutions. The question that remains is how the statistical performance of the method compares to that of the lasso in these cases.In this paper, we study the relative statistical performance of the lasso and marginal regression for sparse, high-dimensional regression problems. We consider the problem of learning which coefficients are non-zero. Our main results are as follows: (i) we compare the conditions under which the lasso and marginal regression guarantee exact recovery in the fixed design, noise free case; (ii) we establish conditions under which marginal regression provides exact recovery with high probability in the fixed design, noise free, random coefficients case; and (iii) we derive rates of convergence for both procedures, where performance is measured by the number of coefficients with incorrect sign, and characterize the regions in the parameter space recovery is and is not possible under this metric.In light of the computational advantages of marginal regression in very high dimensional problems, our theoretical and simulations results suggest that the procedure merits further study.},
journal = {J. Mach. Learn. Res.},
month = jun,
pages = {2107–2143},
numpages = {37},
keywords = {lasso, high-dimensional regression, regularization, phase diagram}
}

@article{10.5555/2503308.2343711,
author = {May, Benedict C. and Korda, Nathan and Lee, Anthony and Leslie, David S.},
title = {Optimistic Bayesian Sampling in Contextual-Bandit Problems},
year = {2012},
issue_date = {January 2012},
publisher = {JMLR.org},
volume = {13},
number = {1},
issn = {1532-4435},
abstract = {In sequential decision problems in an unknown environment, the decision maker often faces a dilemma over whether to explore to discover more about the environment, or to exploit current knowledge. We address the exploration-exploitation dilemma in a general setting encompassing both standard and contextualised bandit problems. The contextual bandit problem has recently resurfaced in attempts to maximise click-through rates in web based applications, a task with significant commercial interest.In this article we consider an approach of Thompson (1933) which makes use of samples from the posterior distributions for the instantaneous value of each action. We extend the approach by introducing a new algorithm, Optimistic Bayesian Sampling (OBS), in which the probability of playing an action increases with the uncertainty in the estimate of the action value. This results in better directed exploratory behaviour.We prove that, under unrestrictive assumptions, both approaches result in optimal behaviour with respect to the average reward criterion of Yang and Zhu (2002). We implement OBS and measure its performance in simulated Bernoulli bandit and linear regression domains, and also when tested with the task of personalised news article recommendation on a Yahoo! Front Page Today Module data set. We find that OBS performs competitively when compared to recently proposed benchmark algorithms and outperforms Thompson's method throughout.},
journal = {J. Mach. Learn. Res.},
month = jun,
pages = {2069–2106},
numpages = {38},
keywords = {exploration-exploitation, contextual bandits, sequential allocation, multi-armed bandits, Thompson sampling}
}

@article{10.5555/2503308.2343710,
author = {De Smedt, Tom and Daelemans, Walter},
title = {Pattern for Python},
year = {2012},
issue_date = {January 2012},
publisher = {JMLR.org},
volume = {13},
number = {1},
issn = {1532-4435},
abstract = {Pattern is a package for Python 2.4+ with functionality for web mining (Google + Twitter + Wikipedia, web spider, HTML DOM parser), natural language processing (tagger/chunker, n-gram search, sentiment analysis, WordNet), machine learning (vector space model, k-means clustering, Naive Bayes + k-NN + SVM classifiers) and network analysis (graph centrality and visualization). It is well documented and bundled with 30+ examples and 350+ unit tests. The source code is licensed under BSD and available from http://www.clips.ua.ac.be/pages/pattern.},
journal = {J. Mach. Learn. Res.},
month = jun,
pages = {2063–2067},
numpages = {5},
keywords = {machine learning, python, data mining, graph networks, natural language processing}
}

@article{10.5555/2503308.2343709,
author = {Zhang, Zhihua and Wang, Shusen and Liu, Dehua and Jordan, Michael I.},
title = {EP-GIG Priors and Applications in Bayesian Sparse Learning},
year = {2012},
issue_date = {January 2012},
publisher = {JMLR.org},
volume = {13},
number = {1},
issn = {1532-4435},
abstract = {In this paper we propose a novel framework for the construction of sparsity-inducing priors. In particular, we define such priors as a mixture of exponential power distributions with a generalized inverse Gaussian density (EP-GIG). EP-GIG is a variant of generalized hyperbolic distributions, and the special cases include Gaussian scale mixtures and Laplace scale mixtures. Furthermore, Laplace scale mixtures can subserve a Bayesian framework for sparse learning with nonconvex penalization. The densities of EP-GIG can be explicitly expressed. Moreover, the corresponding posterior distribution also follows a generalized inverse Gaussian distribution. We exploit these properties to develop EM algorithms for sparse empirical Bayesian learning. We also show that these algorithms bear an interesting resemblance to iteratively reweighted  l   2  or  l   1  methods. Finally, we present two extensions for grouped variable selection and logistic regression.},
journal = {J. Mach. Learn. Res.},
month = jun,
pages = {2031–2061},
numpages = {31},
keywords = {scale mixtures of exponential power distributions, generalized inverse Gaussian distributions, iteratively reweighted minimization methods, expectation-maximization algorithms, sparsity priors}
}

@article{10.5555/2503308.2343708,
author = {Yuan, Guo-Xun and Ho, Chia-Hua and Lin, Chih-Jen},
title = {An Improved GLMNET for L1-Regularized Logistic Regression},
year = {2012},
issue_date = {January 2012},
publisher = {JMLR.org},
volume = {13},
number = {1},
issn = {1532-4435},
abstract = {Recently, Yuan et al. (2010) conducted a comprehensive comparison on software for L1-regularized classification. They concluded that a carefully designed coordinate descent implementation CDN is the fastest among state-of-the-art solvers. In this paper, we point out that CDN is less competitive on loss functions that are expensive to compute. In particular, CDN for logistic regression is much slower than CDN for SVM because the logistic loss involves expensive exp/log operations.In optimization, Newton methods are known to have fewer iterations although each iteration costs more. Because solving the Newton sub-problem is independent of the loss calculation, this type of methods may surpass CDN under some circumstances. In L1-regularized classification, GLMNET by Friedman et al. is already a Newton-type method, but experiments in Yuan et al. (2010) indicated that the existing GLMNET implementation may face difficulties for some largescale problems. In this paper, we propose an improved GLMNET to address some theoretical and implementation issues. In particular, as a Newton-type method, GLMNET achieves fast local convergence, but may fail to quickly obtain a useful solution. By a careful design to adjust the effort for each iteration, our method is efficient for both loosely or strictly solving the optimization problem. Experiments demonstrate that our improved GLMNET ismore efficient than CDN for L1-regularized logistic regression.},
journal = {J. Mach. Learn. Res.},
month = jun,
pages = {1999–2030},
numpages = {32},
keywords = {linear classification, logistic regression, optimization methods, L1 regularization, support vector machines}
}

@article{10.5555/2503308.2343707,
author = {Xue, Lan and Qu, Annie},
title = {Variable Selection in High-Dimensional Varying-Coefficient Models with Global Optimality},
year = {2012},
issue_date = {January 2012},
publisher = {JMLR.org},
volume = {13},
number = {1},
issn = {1532-4435},
abstract = {The varying-coefficient model is flexible and powerful for modeling the dynamic changes of regression coefficients. It is important to identify significant covariates associated with response variables, especially for high-dimensional settings where the number of covariates can be larger than the sample size. We consider model selection in the high-dimensional setting and adopt difference convex programming to approximate the L0 penalty, and we investigate the global optimality properties of the varying-coefficient estimator. The challenge of the variable selection problem here is that the dimension of the nonparametric form for the varying-coefficient modeling could be infinite, in addition to dealing with the high-dimensional linear covariates. We show that the proposed varying-coefficient estimator is consistent, enjoys the oracle property and achieves an optimal convergence rate for the non-zero nonparametric components for high-dimensional data. Our simulations and numerical examples indicate that the difference convex algorithm is efficient using the coordinate decent algorithm, and is able to select the true model at a higher frequency than the least absolute shrinkage and selection operator (LASSO), the adaptive LASSO and the smoothly clipped absolute deviation (SCAD) approaches.},
journal = {J. Mach. Learn. Res.},
month = jun,
pages = {1973–1998},
numpages = {26},
keywords = {nonparametric function, coordinate decent algorithm, oracle property, difference convex programming, L0-regularization, model selection, truncated L1 penalty, large-p small-n}
}

@article{10.5555/2503308.2343706,
author = {Grau, Jan and Keilwagen, Jens and Gohr, Andr\'{e} and Haldemann, Berit and Posch, Stefan and Grosse, Ivo},
title = {Jstacs: A Java Framework for Statistical Analysis and Classification of Biological Sequences},
year = {2012},
issue_date = {January 2012},
publisher = {JMLR.org},
volume = {13},
number = {1},
issn = {1532-4435},
abstract = {Jstacs is an object-oriented Java library for analysing and classifying sequence data, which emerged from the need for a standardized implementation of statistical models, learning principles, classifiers, and performance measures. In Jstacs, these components can be used, combined, and extended easily, which allows for a direct comparison of different approaches and fosters the development of new components. Jstacs is especially tailored to biological sequence data, but is also applicable to general discrete and continuous data. Jstacs is freely available at http://www.jstacs.de under the GNU GPL license including an API documentation, a cookbook, and code examples.},
journal = {J. Mach. Learn. Res.},
month = jun,
pages = {1967–1971},
numpages = {5},
keywords = {classification, bioinformatics, machine learning, statistical models, Java}
}

@article{10.5555/2503308.2343705,
author = {Tamar, Aviv and Di Castro, Dotan and Meir, Ron},
title = {Integrating a Partial Model into Model Free Reinforcement Learning},
year = {2012},
issue_date = {January 2012},
publisher = {JMLR.org},
volume = {13},
number = {1},
issn = {1532-4435},
abstract = {In reinforcement learning an agent uses online feedback from the environment in order to adaptively select an effective policy. Model free approaches address this task by directly mapping environmental states to actions, while model based methods attempt to construct a model of the environment, followed by a selection of optimal actions based on that model. Given the complementary advantages of both approaches, we suggest a novel procedure which augments a model free algorithm with a partial model. The resulting hybrid algorithm switches between a model based and a model free mode, depending on the current state and the agent's knowledge. Our method relies on a novel definition for a partially known model, and an estimator that incorporates such knowledge in order to reduce uncertainty in stochastic approximation iterations. We prove that such an approach leads to improved policy evaluation whenever environmental knowledge is available, without compromising performance when such knowledge is absent. Numerical simulations demonstrate the effectiveness of the approach on policy gradient and Q-learning algorithms, and its usefulness in solving a call admission control problem.},
journal = {J. Mach. Learn. Res.},
month = jun,
pages = {1927–1966},
numpages = {40},
keywords = {hybrid model based model free algorithms, markov decision processes, reinforcement learning, stochastic approximation, temporal difference}
}

@article{10.5555/2503308.2343704,
author = {Crammer, Koby and Dredze, Mark and Pereira, Fernando},
title = {Confidence-Weighted Linear Classification for Text Categorization},
year = {2012},
issue_date = {January 2012},
publisher = {JMLR.org},
volume = {13},
number = {1},
issn = {1532-4435},
abstract = {Confidence-weighted online learning is a generalization of margin-based learning of linear classifiers in which the margin constraint is replaced by a probabilistic constraint based on a distribution over classifier weights that is updated online as examples are observed. The distribution captures a notion of confidence on classifier weights, and in some cases it can also be interpreted as replacing a single learning rate by adaptive per-weight rates. Confidence-weighted learning was motivated by the statistical properties of natural-language classification tasks, where most of the informative features are relatively rare. We investigate several versions of confidence-weighted learning that use a Gaussian distribution over weight vectors, updated at each observed example to achieve high probability of correct classification for the example. Empirical evaluation on a range of text-categorization tasks show that our algorithms improve over other state-of-the-art online and batch methods, learn faster in the online setting, and lead to better classifier combination for a type of distributed training commonly used in cloud computing.},
journal = {J. Mach. Learn. Res.},
month = jun,
pages = {1891–1926},
numpages = {36},
keywords = {online learning, confidence prediction, text categorization}
}

@article{10.5555/2503308.2343703,
author = {Kakade, Sham M. and Shalev-Shwartz, Shai and Tewari, Ambuj},
title = {Regularization Techniques for Learning with Matrices},
year = {2012},
issue_date = {January 2012},
publisher = {JMLR.org},
volume = {13},
number = {1},
issn = {1532-4435},
abstract = {There is growing body of learning problems for which it is natural to organize the parameters into a matrix. As a result, it becomes easy to impose sophisticated prior knowledge by appropriately regularizing the parameters under some matrix norm. This work describes and analyzes a systematic method for constructing such matrix-based regularization techniques. In particular, we focus on how the underlying statistical properties of a given problem can help us decide which regularization function is appropriate.Our methodology is based on a known duality phenomenon: a function is strongly convex with respect to some norm if and only if its conjugate function is strongly smooth with respect to the dual norm. This result has already been found to be a key component in deriving and analyzing several learning algorithms. We demonstrate the potential of this framework by deriving novel generalization and regret bounds for multi-task learning, multi-class learning, and multiple kernel learning.},
journal = {J. Mach. Learn. Res.},
month = jun,
pages = {1865–1890},
numpages = {26},
keywords = {multi-class learning, regret bounds, multi-task learning, regularization, generalization bounds, strong convexity, multiple kernel learning}
}

@article{10.5555/2503308.2343702,
author = {Huang, Jian and Zhang, Cun-Hui},
title = {Estimation and Selection via Absolute Penalized Convex Minimization and Its Multistage Adaptive Applications},
year = {2012},
issue_date = {January 2012},
publisher = {JMLR.org},
volume = {13},
number = {1},
issn = {1532-4435},
abstract = {The l1-penalized method, or the Lasso, has emerged as an important tool for the analysis of large data sets. Many important results have been obtained for the Lasso in linear regression which have led to a deeper understanding of high-dimensional statistical problems. In this article, we consider a class of weighted l1-penalized estimators for convex loss functions of a general form, including the generalized linear models. We study the estimation, prediction, selection and sparsity properties of the weighted l1-penalized estimator in sparse, high-dimensional settings where the number of predictors p can be much larger than the sample size n. Adaptive Lasso is considered as a special case. A multistage method is developed to approximate concave regularized estimation by applying an adaptive Lasso recursively. We provide prediction and estimation oracle inequalities for single- and multi-stage estimators, a general selection consistency theorem, and an upper bound for the dimension of the Lasso estimator. Important models including the linear regression, logistic regression and log-linear models are used throughout to illustrate the applications of the general results.},
journal = {J. Mach. Learn. Res.},
month = jun,
pages = {1839–1864},
numpages = {26},
keywords = {sparsity, penalized estimation, generalized linear models, variable selection, oracle inequality, selection consistency}
}

@article{10.5555/2503308.2343701,
author = {Hennig, Philipp and Schuler, Christian J.},
title = {Entropy Search for Information-Efficient Global Optimization},
year = {2012},
issue_date = {January 2012},
publisher = {JMLR.org},
volume = {13},
number = {1},
issn = {1532-4435},
abstract = {Contemporary global optimization algorithms are based on local measures of utility, rather than a probability measure over location and value of the optimum. They thus attempt to collect low function values, not to learn about the optimum. The reason for the absence of probabilistic global optimizers is that the corresponding inference problem is intractable in several ways. This paper develops desiderata for probabilistic optimization algorithms, then presents a concrete algorithm which addresses each of the computational intractabilities with a sequence of approximations and explicitly addresses the decision problem of maximizing information gain from each evaluation.},
journal = {J. Mach. Learn. Res.},
month = jun,
pages = {1809–1837},
numpages = {29},
keywords = {optimization, information, probability, Gaussian processes, expectation propagation}
}

@article{10.5555/2503308.2343700,
author = {Chai, Kian Ming A.},
title = {Variational Multinomial Logit Gaussian Process},
year = {2012},
issue_date = {January 2012},
publisher = {JMLR.org},
volume = {13},
number = {1},
issn = {1532-4435},
abstract = {Gaussian process prior with an appropriate likelihood function is a flexible non-parametric model for a variety of learning tasks. One important and standard task is multi-class classification, which is the categorization of an item into one of several fixed classes. A usual likelihood function for this is the multinomial logistic likelihood function. However, exact inference with this model has proved to be difficult because high-dimensional integrations are required. In this paper, we propose a variational approximation to this model, and we describe the optimization of the variational parameters. Experiments have shown our approximation to be tight. In addition, we provide data-independent bounds on the marginal likelihood of the model, one of which is shown to be much tighter than the existing variational mean-field bound in the experiments. We also derive a proper lower bound on the predictive likelihood that involves the Kullback-Leibler divergence between the approximating and the true posterior. We combine our approach with a recently proposed sparse approximation to give a variational sparse approximation to the Gaussian process multi-class model. We also derive criteria which can be used to select the inducing set, and we show the effectiveness of these criteria over random selection in an experiment.},
journal = {J. Mach. Learn. Res.},
month = jun,
pages = {1745–1808},
numpages = {64},
keywords = {Gaussian process, probabilistic classification, sparse approximation, variational approximation, multinomial logistic}
}

@article{10.5555/2503308.2343699,
author = {Lee, Sangkyun and Wright, Stephen J.},
title = {Manifold Identification in Dual Averaging for Regularized Stochastic Online Learning},
year = {2012},
issue_date = {January 2012},
publisher = {JMLR.org},
volume = {13},
number = {1},
issn = {1532-4435},
abstract = {Iterative methods that calculate their steps from approximate subgradient directions have proved to be useful for stochastic learning problems over large and streaming data sets. When the objective consists of a loss function plus a nonsmooth regularization term, the solution often lies on a low-dimensional manifold of parameter space along which the regularizer is smooth. (When an l1 regularizer is used to induce sparsity in the solution, for example, this manifold is defined by the set of nonzero components of the parameter vector.) This paper shows that a regularized dual averaging algorithm can identify this manifold, with high probability, before reaching the solution. This observation motivates an algorithmic strategy in which, once an iterate is suspected of lying on an optimal or near-optimal manifold, we switch to a "local phase" that searches in this manifold, thus converging rapidly to a near-optimal point. Computational results are presented to verify the identification property and to illustrate the effectiveness of this approach.},
journal = {J. Mach. Learn. Res.},
month = jun,
pages = {1705–1744},
numpages = {40},
keywords = {regularization, partly smooth manifold, manifold identification, dual averaging}
}

@article{10.5555/2188385.2343712,
author = {Genovese, Christopher R. and Jin, Jiashun and Wasserman, Larry and Yao, Zhigang},
title = {A Comparison of the Lasso and Marginal Regression},
year = {2012},
issue_date = {3/1/2012},
publisher = {JMLR.org},
volume = {13},
number = {null},
issn = {1532-4435},
abstract = {The lasso is an important method for sparse, high-dimensional regression problems, with efficient algorithms available, a long history of practical success, and a large body of theoretical results supporting and explaining its performance. But even with the best available algorithms, finding the lasso solutions remains a computationally challenging task in cases where the number of covariates vastly exceeds the number of data points.Marginal regression, where each dependent variable is regressed separately on each covariate, offers a promising alternative in this case because the estimates can be computed roughly two orders faster than the lasso solutions. The question that remains is how the statistical performance of the method compares to that of the lasso in these cases.In this paper, we study the relative statistical performance of the lasso and marginal regression for sparse, high-dimensional regression problems. We consider the problem of learning which coefficients are non-zero. Our main results are as follows: (i) we compare the conditions under which the lasso and marginal regression guarantee exact recovery in the fixed design, noise free case; (ii) we establish conditions under which marginal regression provides exact recovery with high probability in the fixed design, noise free, random coefficients case; and (iii) we derive rates of convergence for both procedures, where performance is measured by the number of coefficients with incorrect sign, and characterize the regions in the parameter space recovery is and is not possible under this metric.In light of the computational advantages of marginal regression in very high dimensional problems, our theoretical and simulations results suggest that the procedure merits further study.},
journal = {J. Mach. Learn. Res.},
month = jun,
pages = {2107–2143},
numpages = {37},
keywords = {regularization, phase diagram, lasso, high-dimensional regression}
}

@article{10.5555/2188385.2343711,
author = {May, Benedict C. and Korda, Nathan and Lee, Anthony and Leslie, David S.},
title = {Optimistic Bayesian Sampling in Contextual-Bandit Problems},
year = {2012},
issue_date = {3/1/2012},
publisher = {JMLR.org},
volume = {13},
number = {null},
issn = {1532-4435},
abstract = {In sequential decision problems in an unknown environment, the decision maker often faces a dilemma over whether to explore to discover more about the environment, or to exploit current knowledge. We address the exploration-exploitation dilemma in a general setting encompassing both standard and contextualised bandit problems. The contextual bandit problem has recently resurfaced in attempts to maximise click-through rates in web based applications, a task with significant commercial interest.In this article we consider an approach of Thompson (1933) which makes use of samples from the posterior distributions for the instantaneous value of each action. We extend the approach by introducing a new algorithm, Optimistic Bayesian Sampling (OBS), in which the probability of playing an action increases with the uncertainty in the estimate of the action value. This results in better directed exploratory behaviour.We prove that, under unrestrictive assumptions, both approaches result in optimal behaviour with respect to the average reward criterion of Yang and Zhu (2002). We implement OBS and measure its performance in simulated Bernoulli bandit and linear regression domains, and also when tested with the task of personalised news article recommendation on a Yahoo! Front Page Today Module data set. We find that OBS performs competitively when compared to recently proposed benchmark algorithms and outperforms Thompson's method throughout.},
journal = {J. Mach. Learn. Res.},
month = jun,
pages = {2069–2106},
numpages = {38},
keywords = {exploration-exploitation, multi-armed bandits, Thompson sampling, sequential allocation, contextual bandits}
}

@article{10.5555/2188385.2343710,
author = {De Smedt, Tom and Daelemans, Walter},
title = {Pattern for Python},
year = {2012},
issue_date = {3/1/2012},
publisher = {JMLR.org},
volume = {13},
number = {null},
issn = {1532-4435},
abstract = {Pattern is a package for Python 2.4+ with functionality for web mining (Google + Twitter + Wikipedia, web spider, HTML DOM parser), natural language processing (tagger/chunker, n-gram search, sentiment analysis, WordNet), machine learning (vector space model, k-means clustering, Naive Bayes + k-NN + SVM classifiers) and network analysis (graph centrality and visualization). It is well documented and bundled with 30+ examples and 350+ unit tests. The source code is licensed under BSD and available from http://www.clips.ua.ac.be/pages/pattern.},
journal = {J. Mach. Learn. Res.},
month = jun,
pages = {2063–2067},
numpages = {5},
keywords = {data mining, graph networks, python, machine learning, natural language processing}
}

@article{10.5555/2188385.2343709,
author = {Zhang, Zhihua and Wang, Shusen and Liu, Dehua and Jordan, Michael I.},
title = {EP-GIG Priors and Applications in Bayesian Sparse Learning},
year = {2012},
issue_date = {3/1/2012},
publisher = {JMLR.org},
volume = {13},
number = {null},
issn = {1532-4435},
abstract = {In this paper we propose a novel framework for the construction of sparsity-inducing priors. In particular, we define such priors as a mixture of exponential power distributions with a generalized inverse Gaussian density (EP-GIG). EP-GIG is a variant of generalized hyperbolic distributions, and the special cases include Gaussian scale mixtures and Laplace scale mixtures. Furthermore, Laplace scale mixtures can subserve a Bayesian framework for sparse learning with nonconvex penalization. The densities of EP-GIG can be explicitly expressed. Moreover, the corresponding posterior distribution also follows a generalized inverse Gaussian distribution. We exploit these properties to develop EM algorithms for sparse empirical Bayesian learning. We also show that these algorithms bear an interesting resemblance to iteratively reweighted  l   2  or  l   1  methods. Finally, we present two extensions for grouped variable selection and logistic regression.},
journal = {J. Mach. Learn. Res.},
month = jun,
pages = {2031–2061},
numpages = {31},
keywords = {scale mixtures of exponential power distributions, generalized inverse Gaussian distributions, sparsity priors, iteratively reweighted minimization methods, expectation-maximization algorithms}
}

@article{10.5555/2188385.2343708,
author = {Yuan, Guo-Xun and Ho, Chia-Hua and Lin, Chih-Jen},
title = {An Improved GLMNET for L1-Regularized Logistic Regression},
year = {2012},
issue_date = {3/1/2012},
publisher = {JMLR.org},
volume = {13},
number = {null},
issn = {1532-4435},
abstract = {Recently, Yuan et al. (2010) conducted a comprehensive comparison on software for L1-regularized classification. They concluded that a carefully designed coordinate descent implementation CDN is the fastest among state-of-the-art solvers. In this paper, we point out that CDN is less competitive on loss functions that are expensive to compute. In particular, CDN for logistic regression is much slower than CDN for SVM because the logistic loss involves expensive exp/log operations.In optimization, Newton methods are known to have fewer iterations although each iteration costs more. Because solving the Newton sub-problem is independent of the loss calculation, this type of methods may surpass CDN under some circumstances. In L1-regularized classification, GLMNET by Friedman et al. is already a Newton-type method, but experiments in Yuan et al. (2010) indicated that the existing GLMNET implementation may face difficulties for some largescale problems. In this paper, we propose an improved GLMNET to address some theoretical and implementation issues. In particular, as a Newton-type method, GLMNET achieves fast local convergence, but may fail to quickly obtain a useful solution. By a careful design to adjust the effort for each iteration, our method is efficient for both loosely or strictly solving the optimization problem. Experiments demonstrate that our improved GLMNET ismore efficient than CDN for L1-regularized logistic regression.},
journal = {J. Mach. Learn. Res.},
month = jun,
pages = {1999–2030},
numpages = {32},
keywords = {L1 regularization, linear classification, logistic regression, optimization methods, support vector machines}
}

@article{10.5555/2188385.2343707,
author = {Xue, Lan and Qu, Annie},
title = {Variable Selection in High-Dimensional Varying-Coefficient Models with Global Optimality},
year = {2012},
issue_date = {3/1/2012},
publisher = {JMLR.org},
volume = {13},
number = {null},
issn = {1532-4435},
abstract = {The varying-coefficient model is flexible and powerful for modeling the dynamic changes of regression coefficients. It is important to identify significant covariates associated with response variables, especially for high-dimensional settings where the number of covariates can be larger than the sample size. We consider model selection in the high-dimensional setting and adopt difference convex programming to approximate the L0 penalty, and we investigate the global optimality properties of the varying-coefficient estimator. The challenge of the variable selection problem here is that the dimension of the nonparametric form for the varying-coefficient modeling could be infinite, in addition to dealing with the high-dimensional linear covariates. We show that the proposed varying-coefficient estimator is consistent, enjoys the oracle property and achieves an optimal convergence rate for the non-zero nonparametric components for high-dimensional data. Our simulations and numerical examples indicate that the difference convex algorithm is efficient using the coordinate decent algorithm, and is able to select the true model at a higher frequency than the least absolute shrinkage and selection operator (LASSO), the adaptive LASSO and the smoothly clipped absolute deviation (SCAD) approaches.},
journal = {J. Mach. Learn. Res.},
month = jun,
pages = {1973–1998},
numpages = {26},
keywords = {nonparametric function, oracle property, large-p small-n, model selection, coordinate decent algorithm, difference convex programming, truncated L1 penalty, L0-regularization}
}

@article{10.5555/2188385.2343706,
author = {Grau, Jan and Keilwagen, Jens and Gohr, Andr\'{e} and Haldemann, Berit and Posch, Stefan and Grosse, Ivo},
title = {Jstacs: A Java Framework for Statistical Analysis and Classification of Biological Sequences},
year = {2012},
issue_date = {3/1/2012},
publisher = {JMLR.org},
volume = {13},
number = {null},
issn = {1532-4435},
abstract = {Jstacs is an object-oriented Java library for analysing and classifying sequence data, which emerged from the need for a standardized implementation of statistical models, learning principles, classifiers, and performance measures. In Jstacs, these components can be used, combined, and extended easily, which allows for a direct comparison of different approaches and fosters the development of new components. Jstacs is especially tailored to biological sequence data, but is also applicable to general discrete and continuous data. Jstacs is freely available at http://www.jstacs.de under the GNU GPL license including an API documentation, a cookbook, and code examples.},
journal = {J. Mach. Learn. Res.},
month = jun,
pages = {1967–1971},
numpages = {5},
keywords = {classification, machine learning, Java, statistical models, bioinformatics}
}

@article{10.5555/2188385.2343705,
author = {Tamar, Aviv and Di Castro, Dotan and Meir, Ron},
title = {Integrating a Partial Model into Model Free Reinforcement Learning},
year = {2012},
issue_date = {3/1/2012},
publisher = {JMLR.org},
volume = {13},
number = {null},
issn = {1532-4435},
abstract = {In reinforcement learning an agent uses online feedback from the environment in order to adaptively select an effective policy. Model free approaches address this task by directly mapping environmental states to actions, while model based methods attempt to construct a model of the environment, followed by a selection of optimal actions based on that model. Given the complementary advantages of both approaches, we suggest a novel procedure which augments a model free algorithm with a partial model. The resulting hybrid algorithm switches between a model based and a model free mode, depending on the current state and the agent's knowledge. Our method relies on a novel definition for a partially known model, and an estimator that incorporates such knowledge in order to reduce uncertainty in stochastic approximation iterations. We prove that such an approach leads to improved policy evaluation whenever environmental knowledge is available, without compromising performance when such knowledge is absent. Numerical simulations demonstrate the effectiveness of the approach on policy gradient and Q-learning algorithms, and its usefulness in solving a call admission control problem.},
journal = {J. Mach. Learn. Res.},
month = jun,
pages = {1927–1966},
numpages = {40},
keywords = {hybrid model based model free algorithms, temporal difference, stochastic approximation, reinforcement learning, markov decision processes}
}

@article{10.5555/2188385.2343704,
author = {Crammer, Koby and Dredze, Mark and Pereira, Fernando},
title = {Confidence-Weighted Linear Classification for Text Categorization},
year = {2012},
issue_date = {3/1/2012},
publisher = {JMLR.org},
volume = {13},
number = {null},
issn = {1532-4435},
abstract = {Confidence-weighted online learning is a generalization of margin-based learning of linear classifiers in which the margin constraint is replaced by a probabilistic constraint based on a distribution over classifier weights that is updated online as examples are observed. The distribution captures a notion of confidence on classifier weights, and in some cases it can also be interpreted as replacing a single learning rate by adaptive per-weight rates. Confidence-weighted learning was motivated by the statistical properties of natural-language classification tasks, where most of the informative features are relatively rare. We investigate several versions of confidence-weighted learning that use a Gaussian distribution over weight vectors, updated at each observed example to achieve high probability of correct classification for the example. Empirical evaluation on a range of text-categorization tasks show that our algorithms improve over other state-of-the-art online and batch methods, learn faster in the online setting, and lead to better classifier combination for a type of distributed training commonly used in cloud computing.},
journal = {J. Mach. Learn. Res.},
month = jun,
pages = {1891–1926},
numpages = {36},
keywords = {text categorization, confidence prediction, online learning}
}

@article{10.5555/2188385.2343703,
author = {Kakade, Sham M. and Shalev-Shwartz, Shai and Tewari, Ambuj},
title = {Regularization Techniques for Learning with Matrices},
year = {2012},
issue_date = {3/1/2012},
publisher = {JMLR.org},
volume = {13},
number = {null},
issn = {1532-4435},
abstract = {There is growing body of learning problems for which it is natural to organize the parameters into a matrix. As a result, it becomes easy to impose sophisticated prior knowledge by appropriately regularizing the parameters under some matrix norm. This work describes and analyzes a systematic method for constructing such matrix-based regularization techniques. In particular, we focus on how the underlying statistical properties of a given problem can help us decide which regularization function is appropriate.Our methodology is based on a known duality phenomenon: a function is strongly convex with respect to some norm if and only if its conjugate function is strongly smooth with respect to the dual norm. This result has already been found to be a key component in deriving and analyzing several learning algorithms. We demonstrate the potential of this framework by deriving novel generalization and regret bounds for multi-task learning, multi-class learning, and multiple kernel learning.},
journal = {J. Mach. Learn. Res.},
month = jun,
pages = {1865–1890},
numpages = {26},
keywords = {regret bounds, strong convexity, regularization, generalization bounds, multiple kernel learning, multi-task learning, multi-class learning}
}

@article{10.5555/2188385.2343702,
author = {Huang, Jian and Zhang, Cun-Hui},
title = {Estimation and Selection via Absolute Penalized Convex Minimization and Its Multistage Adaptive Applications},
year = {2012},
issue_date = {3/1/2012},
publisher = {JMLR.org},
volume = {13},
number = {null},
issn = {1532-4435},
abstract = {The l1-penalized method, or the Lasso, has emerged as an important tool for the analysis of large data sets. Many important results have been obtained for the Lasso in linear regression which have led to a deeper understanding of high-dimensional statistical problems. In this article, we consider a class of weighted l1-penalized estimators for convex loss functions of a general form, including the generalized linear models. We study the estimation, prediction, selection and sparsity properties of the weighted l1-penalized estimator in sparse, high-dimensional settings where the number of predictors p can be much larger than the sample size n. Adaptive Lasso is considered as a special case. A multistage method is developed to approximate concave regularized estimation by applying an adaptive Lasso recursively. We provide prediction and estimation oracle inequalities for single- and multi-stage estimators, a general selection consistency theorem, and an upper bound for the dimension of the Lasso estimator. Important models including the linear regression, logistic regression and log-linear models are used throughout to illustrate the applications of the general results.},
journal = {J. Mach. Learn. Res.},
month = jun,
pages = {1839–1864},
numpages = {26},
keywords = {selection consistency, sparsity, generalized linear models, oracle inequality, penalized estimation, variable selection}
}

@article{10.5555/2188385.2343701,
author = {Hennig, Philipp and Schuler, Christian J.},
title = {Entropy Search for Information-Efficient Global Optimization},
year = {2012},
issue_date = {3/1/2012},
publisher = {JMLR.org},
volume = {13},
number = {null},
issn = {1532-4435},
abstract = {Contemporary global optimization algorithms are based on local measures of utility, rather than a probability measure over location and value of the optimum. They thus attempt to collect low function values, not to learn about the optimum. The reason for the absence of probabilistic global optimizers is that the corresponding inference problem is intractable in several ways. This paper develops desiderata for probabilistic optimization algorithms, then presents a concrete algorithm which addresses each of the computational intractabilities with a sequence of approximations and explicitly addresses the decision problem of maximizing information gain from each evaluation.},
journal = {J. Mach. Learn. Res.},
month = jun,
pages = {1809–1837},
numpages = {29},
keywords = {expectation propagation, information, probability, Gaussian processes, optimization}
}

@article{10.5555/2188385.2343700,
author = {Chai, Kian Ming A.},
title = {Variational Multinomial Logit Gaussian Process},
year = {2012},
issue_date = {3/1/2012},
publisher = {JMLR.org},
volume = {13},
number = {null},
issn = {1532-4435},
abstract = {Gaussian process prior with an appropriate likelihood function is a flexible non-parametric model for a variety of learning tasks. One important and standard task is multi-class classification, which is the categorization of an item into one of several fixed classes. A usual likelihood function for this is the multinomial logistic likelihood function. However, exact inference with this model has proved to be difficult because high-dimensional integrations are required. In this paper, we propose a variational approximation to this model, and we describe the optimization of the variational parameters. Experiments have shown our approximation to be tight. In addition, we provide data-independent bounds on the marginal likelihood of the model, one of which is shown to be much tighter than the existing variational mean-field bound in the experiments. We also derive a proper lower bound on the predictive likelihood that involves the Kullback-Leibler divergence between the approximating and the true posterior. We combine our approach with a recently proposed sparse approximation to give a variational sparse approximation to the Gaussian process multi-class model. We also derive criteria which can be used to select the inducing set, and we show the effectiveness of these criteria over random selection in an experiment.},
journal = {J. Mach. Learn. Res.},
month = jun,
pages = {1745–1808},
numpages = {64},
keywords = {Gaussian process, variational approximation, probabilistic classification, multinomial logistic, sparse approximation}
}

@article{10.5555/2188385.2343699,
author = {Lee, Sangkyun and Wright, Stephen J.},
title = {Manifold Identification in Dual Averaging for Regularized Stochastic Online Learning},
year = {2012},
issue_date = {3/1/2012},
publisher = {JMLR.org},
volume = {13},
number = {null},
issn = {1532-4435},
abstract = {Iterative methods that calculate their steps from approximate subgradient directions have proved to be useful for stochastic learning problems over large and streaming data sets. When the objective consists of a loss function plus a nonsmooth regularization term, the solution often lies on a low-dimensional manifold of parameter space along which the regularizer is smooth. (When an l1 regularizer is used to induce sparsity in the solution, for example, this manifold is defined by the set of nonzero components of the parameter vector.) This paper shows that a regularized dual averaging algorithm can identify this manifold, with high probability, before reaching the solution. This observation motivates an algorithmic strategy in which, once an iterate is suspected of lying on an optimal or near-optimal manifold, we switch to a "local phase" that searches in this manifold, thus converging rapidly to a near-optimal point. Computational results are presented to verify the identification property and to illustrate the effectiveness of this approach.},
journal = {J. Mach. Learn. Res.},
month = jun,
pages = {1705–1744},
numpages = {40},
keywords = {regularization, partly smooth manifold, dual averaging, manifold identification}
}

@article{10.5555/2503308.2343698,
author = {Nickisch, Hannes},
title = {Glm-Ie: Generalised Linear Models Inference & Estimation Toolbox},
year = {2012},
issue_date = {January 2012},
publisher = {JMLR.org},
volume = {13},
number = {1},
issn = {1532-4435},
abstract = {The glm-ie toolbox contains functionality for estimation and inference in generalised linear models over continuous-valued variables. Besides a variety of penalised least squares solvers for estimation, it offers inference based on (convex) variational bounds, on expectation propagation and on factorial mean field. Scalable and efficient inference in fully-connected undirected graphical models or Markov random fields with Gaussian and non-Gaussian potentials is achieved by casting all the computations as matrix vector multiplications. We provide a wide choice of penalty functions for estimation, potential functions for inference and matrix classes with lazy evaluation for convenient modelling. We designed the glm-ie package to be simple, generic and easily expansible. Most of the code is written in Matlab including some MEX files to be fully compatible to both Matlab 7.x and GNU Octave 3.3.x. Large scale probabilistic classification as well as sparse linear modelling can be performed in a common algorithmical framework by the glm-ie toolkit.},
journal = {J. Mach. Learn. Res.},
month = may,
pages = {1699–1703},
numpages = {5},
keywords = {Bayesian inference, probabilistic regression and classification, lazy evaluation matrix class, sparse linear models, approximate inference, penalised least squares estimation, generalised linear models}
}

@article{10.5555/2503308.2343697,
author = {Negahban, Sahand and Wainwright, Martin J.},
title = {Restricted Strong Convexity and Weighted Matrix Completion: Optimal Bounds with Noise},
year = {2012},
issue_date = {January 2012},
publisher = {JMLR.org},
volume = {13},
number = {1},
issn = {1532-4435},
abstract = {We consider the matrix completion problem under a form of row/column weighted entrywise sampling, including the case of uniformentrywise sampling as a special case. We analyze the associated random observation operator, and prove that with high probability, it satisfies a form of restricted strong convexity with respect to weighted Frobenius norm. Using this property, we obtain as corollaries a number of error bounds on matrix completion in the weighted Frobenius norm under noisy sampling and for both exact and near low-rank matrices. Our results are based on measures of the 'spikiness' and 'low-rankness' of matrices that are less restrictive than the incoherence conditions imposed in previous work. Our technique involves an M-estimator that includes controls on both the rank and spikiness of the solution, and we establish non-asymptotic error bounds in weighted Frobenius norm for recovering matrices lying with lq-"balls" of bounded spikiness. Using information-theoretic methods, we show that no algorithm can achieve better estimates (up to a logarithmic factor) over these same sets, showing that our conditions on matrices and associated rates are essentially optimal.},
journal = {J. Mach. Learn. Res.},
month = may,
pages = {1665–1697},
numpages = {33},
keywords = {matrix completion, convex optimization, collaborative filtering}
}

@article{10.5555/2503308.2343696,
author = {Van Erven, Tim and Reid, Mark D. and Williamson, Robert C.},
title = {Mixability is Bayes Risk Curvature Relative to Log Loss},
year = {2012},
issue_date = {January 2012},
publisher = {JMLR.org},
volume = {13},
number = {1},
issn = {1532-4435},
abstract = {Mixability of a loss characterizes fast rates in the online learning setting of prediction with expert advice. The determination of the mixability constant for binary losses is straight forward but opaque. In the binary case we make this transparent and simpler by characterising mixability in terms of the second derivative of the Bayes risk of proper losses. We then extend this result to multiclass proper losses where there are few existing results. We show that mixability is governed by the maximum eigenvalue of the Hessian of the Bayes risk, relative to the Hessian of the Bayes risk for log loss. We conclude by comparing our result to other work that bounds prediction performance in terms of the geometry of the Bayes risk. Although all calculations are for proper losses, we also show how to carry the results across to improper losses.},
journal = {J. Mach. Learn. Res.},
month = may,
pages = {1639–1663},
numpages = {25},
keywords = {learning rates, mixability, prediction with expert advice, multiclass, proper loss}
}

@article{10.5555/2503308.2343695,
author = {Lawrence, Neil D.},
title = {A Unifying Probabilistic Perspective for Spectral Dimensionality Reduction: Insights and New Models},
year = {2012},
issue_date = {January 2012},
publisher = {JMLR.org},
volume = {13},
number = {1},
issn = {1532-4435},
abstract = {We introduce a new perspective on spectral dimensionality reduction which views these methods as Gaussian Markov random fields (GRFs). Our unifying perspective is based on the maximum entropy principle which is in turn inspired by maximum variance unfolding. The resulting model, which we call maximum entropy unfolding (MEU) is a nonlinear generalization of principal component analysis. We relate the model to Laplacian eigenmaps and isomap. We show that parameter fitting in the locally linear embedding (LLE) is approximate maximum likelihood MEU. We introduce a variant of LLE that performs maximum likelihood exactly: Acyclic LLE (ALLE). We show that MEU and ALLE are competitive with the leading spectral approaches on a robot navigation visualization and a human motion capture data set. Finally the maximum likelihood perspective allows us to introduce a new approach to dimensionality reduction based on L1 regularization of the Gaussian random field via the graphical lasso.},
journal = {J. Mach. Learn. Res.},
month = may,
pages = {1609–1638},
numpages = {30}
}

@article{10.5555/2503308.2343694,
author = {Martinez, Aleix and Du, Shichuan},
title = {A Model of the Perception of Facial Expressions of Emotion by Humans: Research Overview and Perspectives},
year = {2012},
issue_date = {January 2012},
publisher = {JMLR.org},
volume = {13},
number = {1},
issn = {1532-4435},
abstract = {In cognitive science and neuroscience, there have been two leading models describing how humans perceive and classify facial expressions of emotion--the continuous and the categorical model. The continuous model defines each facial expression of emotion as a feature vector in a face space. This model explains, for example, how expressions of emotion can be seen at different intensities. In contrast, the categorical model consists of C classifiers, each tuned to a specific emotion category. This model explains, among other findings, why the images in a morphing sequence between a happy and a surprise face are perceived as either happy or surprise but not something in between. While the continuous model has a more difficult time justifying this latter finding, the categorical model is not as good when it comes to explaining how expressions are recognized at different intensities or modes. Most importantly, both models have problems explaining how one can recognize combinations of emotion categories such as happily surprised versus angrily surprised versus surprise. To resolve these issues, in the past several years, we have worked on a revised model that justifies the results reported in the cognitive science and neuroscience literature. This model consists of C distinct continuous spaces. Multiple (compound) emotion categories can be recognized by linearly combining these C face spaces. The dimensions of these spaces are shown to be mostly configural. According to this model, the major task for the classification of facial expressions of emotion is precise, detailed detection of facial landmarks rather than recognition. We provide an overview of the literature justifying the model, show how the resulting model can be employed to build algorithms for the recognition of facial expression of emotion, and propose research directions in machine learning and computer vision researchers to keep pushing the state of the art in these areas. We also discuss how the model can aid in studies of human perception, social interactions and disorders.},
journal = {J. Mach. Learn. Res.},
month = may,
pages = {1589–1608},
numpages = {20},
keywords = {face detection, face perception, computational modeling, emotions, vision, categorical perception}
}

@article{10.5555/2503308.2343693,
author = {Hanneke, Steve},
title = {Activized Learning: Transforming Passive to Active with Improved Label Complexity},
year = {2012},
issue_date = {January 2012},
publisher = {JMLR.org},
volume = {13},
number = {1},
issn = {1532-4435},
abstract = {We study the theoretical advantages of active learning over passive learning. Specifically, we prove that, in noise-free classifier learning for VC classes, any passive learning algorithm can be transformed into an active learning algorithm with asymptotically strictly superior label complexity for all nontrivial target functions and distributions. We further provide a general characterization of the magnitudes of these improvements in terms of a novel generalization of the disagreement coefficient. We also extend these results to active learning in the presence of label noise, and find that even under broad classes of noise distributions, we can typically guarantee strict improvements over the known results for passive learning.},
journal = {J. Mach. Learn. Res.},
month = may,
pages = {1469–1587},
numpages = {119},
keywords = {sample complexity, selective sampling, PAC learning, active learning, sequential design, statistical learning theory}
}

@article{10.5555/2503308.2343692,
author = {Qin, Zhiwei and Goldfarb, Donald},
title = {Structured Sparsity via Alternating Direction Methods},
year = {2012},
issue_date = {January 2012},
publisher = {JMLR.org},
volume = {13},
number = {1},
issn = {1532-4435},
abstract = {We consider a class of sparse learning problems in high dimensional feature space regularized by a structured sparsity-inducing norm that incorporates prior knowledge of the group structure of the features. Such problems often pose a considerable challenge to optimization algorithms due to the non-smoothness and non-separability of the regularization term. In this paper, we focus on two commonly adopted sparsity-inducing regularization terms, the overlapping Group Lasso penalty l1/l2-norm and the l1/l∞-norm. We propose a unified framework based on the augmented Lagrangian method, under which problems with both types of regularization and their variants can be efficiently solved. As one of the core building-blocks of this framework, we develop new algorithms using a partial-linearization/splitting technique and prove that the accelerated versions of these algorithms require O(1/√ε) iterations to obtain an ε-optimal solution. We compare the performance of these algorithms against that of the alternating direction augmented Lagrangian and FISTA methods on a collection of data sets and apply them to two real-world problems to compare the relative merits of the two norms.},
journal = {J. Mach. Learn. Res.},
month = may,
pages = {1435–1468},
numpages = {34},
keywords = {overlapping group lasso, augmented Lagrangian, structured sparsity, alternating direction methods, variable splitting}
}

@article{10.5555/2503308.2343691,
author = {Song, Le and Smola, Alex and Gretton, Arthur and Bedo, Justin and Borgwardt, Karsten},
title = {Feature Selection via Dependence Maximization},
year = {2012},
issue_date = {January 2012},
publisher = {JMLR.org},
volume = {13},
number = {1},
issn = {1532-4435},
abstract = {We introduce a framework for feature selection based on dependence maximization between the selected features and the labels of an estimation problem, using the Hilbert-Schmidt Independence Criterion. The key idea is that good features should be highly dependent on the labels. Our approach leads to a greedy procedure for feature selection. We show that a number of existing feature selectors are special cases of this framework. Experiments on both artificial and real-world data show that our feature selector works well in practice.},
journal = {J. Mach. Learn. Res.},
month = may,
pages = {1393–1434},
numpages = {42},
keywords = {feature selection, kernel methods, Hilbert-Schmidt independence criterion, Hilbert space embedding of distribution, independence measure}
}

@article{10.5555/2503308.2343690,
author = {Rejchel, Wojciech},
title = {On Ranking and Generalization Bounds},
year = {2012},
issue_date = {January 2012},
publisher = {JMLR.org},
volume = {13},
number = {1},
issn = {1532-4435},
abstract = {The problem of ranking is to predict or to guess the ordering between objects on the basis of their observed features. In this paper we consider ranking estimators that minimize the empirical convex risk. We prove generalization bounds for the excess risk of such estimators with rates that are faster than 1/√n. We apply our results to commonly used ranking algorithms, for instance boosting or support vector machines. Moreover, we study the performance of considered estimators on real data sets.},
journal = {J. Mach. Learn. Res.},
month = may,
pages = {1373–1392},
numpages = {20},
keywords = {support vector machine, excess risk, empirical process, convex risk minimization, U-process}
}

@article{10.5555/2503308.2343689,
author = {Konidaris, George and Scheidwasser, Ilya and Barto, Andrew G.},
title = {Transfer in Reinforcement Learning via Shared Features},
year = {2012},
issue_date = {January 2012},
publisher = {JMLR.org},
volume = {13},
number = {1},
issn = {1532-4435},
abstract = {We present a framework for transfer in reinforcement learning based on the idea that related tasks share some common features, and that transfer can be achieved via those shared features. The framework attempts to capture the notion of tasks that are related but distinct, and provides some insight into when transfer can be usefully applied to a problem sequence and when it cannot. We apply the framework to the knowledge transfer problem, and show that an agent can learn a portable shaping function from experience in a sequence of tasks to significantly improve performance in a later related task, even given a very brief training period. We also apply the framework to skill transfer, to show that agents can learn portable skills across a sequence of tasks that significantly improve performance on later related tasks, approaching the performance of agents given perfectly learned problem-specific skills.},
journal = {J. Mach. Learn. Res.},
month = may,
pages = {1333–1371},
numpages = {39},
keywords = {transfer, skills, shaping, reinforcement learning}
}

@article{10.5555/2503308.2343688,
author = {Nelson, Blaine and Rubinstein, Benjamin I. P. and Huang, Ling and Joseph, Anthony D. and Lee, Steven J. and Rao, Satish and Tygar, J. D.},
title = {Query Strategies for Evading Convex-Inducing Classifiers},
year = {2012},
issue_date = {January 2012},
publisher = {JMLR.org},
volume = {13},
number = {1},
issn = {1532-4435},
abstract = {Classifiers are often used to detect miscreant activities. We study how an adversary can systematically query a classifier to elicit information that allows the attacker to evade detection while incurring a near-minimal cost of modifying their intended malfeasance. We generalize the theory of Lowd and Meek (2005) to the family of convex-inducing classifiers that partition their feature space into two sets, one of which is convex. We present query algorithms for this family that construct undetected instances of approximately minimal cost using only polynomially-many queries in the dimension of the space and in the level of approximation. Our results demonstrate that nearoptimal evasion can be accomplished for this family without reverse engineering the classifier's decision boundary. We also consider general lp costs and show that near-optimal evasion on the family of convex-inducing classifiers is generally efficient for both positive and negative convexity for all levels of approximation if p = 1.},
journal = {J. Mach. Learn. Res.},
month = may,
pages = {1293–1332},
numpages = {40},
keywords = {query algorithms, reverse engineering, evasion, adversarial learning}
}

@article{10.5555/2503308.2343687,
author = {Genovese, Christopher R. and Perone-Pacifico, Marco and Verdinelli, Isabella and Wasserman, Larry},
title = {Minimax Manifold Estimation},
year = {2012},
issue_date = {January 2012},
publisher = {JMLR.org},
volume = {13},
number = {1},
issn = {1532-4435},
abstract = {We find the minimax rate of convergence in Hausdorff distance for estimating a manifold M of dimension d embedded in RD given a noisy sample from the manifold. Under certain conditions, we show that the optimal rate of convergence is n-2/(2+d). Thus, the minimax rate depends only on the dimension of the manifold, not on the dimension of the space in which M is embedded.},
journal = {J. Mach. Learn. Res.},
month = may,
pages = {1263–1291},
numpages = {29},
keywords = {minimax estimation, manifold learning}
}

@article{10.5555/2188385.2343698,
author = {Nickisch, Hannes},
title = {Glm-Ie: Generalised Linear Models Inference & Estimation Toolbox},
year = {2012},
issue_date = {3/1/2012},
publisher = {JMLR.org},
volume = {13},
number = {null},
issn = {1532-4435},
abstract = {The glm-ie toolbox contains functionality for estimation and inference in generalised linear models over continuous-valued variables. Besides a variety of penalised least squares solvers for estimation, it offers inference based on (convex) variational bounds, on expectation propagation and on factorial mean field. Scalable and efficient inference in fully-connected undirected graphical models or Markov random fields with Gaussian and non-Gaussian potentials is achieved by casting all the computations as matrix vector multiplications. We provide a wide choice of penalty functions for estimation, potential functions for inference and matrix classes with lazy evaluation for convenient modelling. We designed the glm-ie package to be simple, generic and easily expansible. Most of the code is written in Matlab including some MEX files to be fully compatible to both Matlab 7.x and GNU Octave 3.3.x. Large scale probabilistic classification as well as sparse linear modelling can be performed in a common algorithmical framework by the glm-ie toolkit.},
journal = {J. Mach. Learn. Res.},
month = may,
pages = {1699–1703},
numpages = {5},
keywords = {penalised least squares estimation, approximate inference, sparse linear models, lazy evaluation matrix class, Bayesian inference, probabilistic regression and classification, generalised linear models}
}

@article{10.5555/2188385.2343697,
author = {Negahban, Sahand and Wainwright, Martin J.},
title = {Restricted Strong Convexity and Weighted Matrix Completion: Optimal Bounds with Noise},
year = {2012},
issue_date = {3/1/2012},
publisher = {JMLR.org},
volume = {13},
number = {null},
issn = {1532-4435},
abstract = {We consider the matrix completion problem under a form of row/column weighted entrywise sampling, including the case of uniformentrywise sampling as a special case. We analyze the associated random observation operator, and prove that with high probability, it satisfies a form of restricted strong convexity with respect to weighted Frobenius norm. Using this property, we obtain as corollaries a number of error bounds on matrix completion in the weighted Frobenius norm under noisy sampling and for both exact and near low-rank matrices. Our results are based on measures of the 'spikiness' and 'low-rankness' of matrices that are less restrictive than the incoherence conditions imposed in previous work. Our technique involves an M-estimator that includes controls on both the rank and spikiness of the solution, and we establish non-asymptotic error bounds in weighted Frobenius norm for recovering matrices lying with lq-"balls" of bounded spikiness. Using information-theoretic methods, we show that no algorithm can achieve better estimates (up to a logarithmic factor) over these same sets, showing that our conditions on matrices and associated rates are essentially optimal.},
journal = {J. Mach. Learn. Res.},
month = may,
pages = {1665–1697},
numpages = {33},
keywords = {matrix completion, convex optimization, collaborative filtering}
}

@article{10.5555/2188385.2343696,
author = {Van Erven, Tim and Reid, Mark D. and Williamson, Robert C.},
title = {Mixability is Bayes Risk Curvature Relative to Log Loss},
year = {2012},
issue_date = {3/1/2012},
publisher = {JMLR.org},
volume = {13},
number = {null},
issn = {1532-4435},
abstract = {Mixability of a loss characterizes fast rates in the online learning setting of prediction with expert advice. The determination of the mixability constant for binary losses is straight forward but opaque. In the binary case we make this transparent and simpler by characterising mixability in terms of the second derivative of the Bayes risk of proper losses. We then extend this result to multiclass proper losses where there are few existing results. We show that mixability is governed by the maximum eigenvalue of the Hessian of the Bayes risk, relative to the Hessian of the Bayes risk for log loss. We conclude by comparing our result to other work that bounds prediction performance in terms of the geometry of the Bayes risk. Although all calculations are for proper losses, we also show how to carry the results across to improper losses.},
journal = {J. Mach. Learn. Res.},
month = may,
pages = {1639–1663},
numpages = {25},
keywords = {prediction with expert advice, learning rates, proper loss, mixability, multiclass}
}

@article{10.5555/2188385.2343695,
author = {Lawrence, Neil D.},
title = {A Unifying Probabilistic Perspective for Spectral Dimensionality Reduction: Insights and New Models},
year = {2012},
issue_date = {3/1/2012},
publisher = {JMLR.org},
volume = {13},
number = {null},
issn = {1532-4435},
abstract = {We introduce a new perspective on spectral dimensionality reduction which views these methods as Gaussian Markov random fields (GRFs). Our unifying perspective is based on the maximum entropy principle which is in turn inspired by maximum variance unfolding. The resulting model, which we call maximum entropy unfolding (MEU) is a nonlinear generalization of principal component analysis. We relate the model to Laplacian eigenmaps and isomap. We show that parameter fitting in the locally linear embedding (LLE) is approximate maximum likelihood MEU. We introduce a variant of LLE that performs maximum likelihood exactly: Acyclic LLE (ALLE). We show that MEU and ALLE are competitive with the leading spectral approaches on a robot navigation visualization and a human motion capture data set. Finally the maximum likelihood perspective allows us to introduce a new approach to dimensionality reduction based on L1 regularization of the Gaussian random field via the graphical lasso.},
journal = {J. Mach. Learn. Res.},
month = may,
pages = {1609–1638},
numpages = {30}
}

@article{10.5555/2188385.2343694,
author = {Martinez, Aleix and Du, Shichuan},
title = {A Model of the Perception of Facial Expressions of Emotion by Humans: Research Overview and Perspectives},
year = {2012},
issue_date = {3/1/2012},
publisher = {JMLR.org},
volume = {13},
number = {null},
issn = {1532-4435},
abstract = {In cognitive science and neuroscience, there have been two leading models describing how humans perceive and classify facial expressions of emotion--the continuous and the categorical model. The continuous model defines each facial expression of emotion as a feature vector in a face space. This model explains, for example, how expressions of emotion can be seen at different intensities. In contrast, the categorical model consists of C classifiers, each tuned to a specific emotion category. This model explains, among other findings, why the images in a morphing sequence between a happy and a surprise face are perceived as either happy or surprise but not something in between. While the continuous model has a more difficult time justifying this latter finding, the categorical model is not as good when it comes to explaining how expressions are recognized at different intensities or modes. Most importantly, both models have problems explaining how one can recognize combinations of emotion categories such as happily surprised versus angrily surprised versus surprise. To resolve these issues, in the past several years, we have worked on a revised model that justifies the results reported in the cognitive science and neuroscience literature. This model consists of C distinct continuous spaces. Multiple (compound) emotion categories can be recognized by linearly combining these C face spaces. The dimensions of these spaces are shown to be mostly configural. According to this model, the major task for the classification of facial expressions of emotion is precise, detailed detection of facial landmarks rather than recognition. We provide an overview of the literature justifying the model, show how the resulting model can be employed to build algorithms for the recognition of facial expression of emotion, and propose research directions in machine learning and computer vision researchers to keep pushing the state of the art in these areas. We also discuss how the model can aid in studies of human perception, social interactions and disorders.},
journal = {J. Mach. Learn. Res.},
month = may,
pages = {1589–1608},
numpages = {20},
keywords = {face perception, vision, categorical perception, computational modeling, face detection, emotions}
}

@article{10.5555/2188385.2343693,
author = {Hanneke, Steve},
title = {Activized Learning: Transforming Passive to Active with Improved Label Complexity},
year = {2012},
issue_date = {3/1/2012},
publisher = {JMLR.org},
volume = {13},
number = {null},
issn = {1532-4435},
abstract = {We study the theoretical advantages of active learning over passive learning. Specifically, we prove that, in noise-free classifier learning for VC classes, any passive learning algorithm can be transformed into an active learning algorithm with asymptotically strictly superior label complexity for all nontrivial target functions and distributions. We further provide a general characterization of the magnitudes of these improvements in terms of a novel generalization of the disagreement coefficient. We also extend these results to active learning in the presence of label noise, and find that even under broad classes of noise distributions, we can typically guarantee strict improvements over the known results for passive learning.},
journal = {J. Mach. Learn. Res.},
month = may,
pages = {1469–1587},
numpages = {119},
keywords = {sequential design, sample complexity, PAC learning, statistical learning theory, selective sampling, active learning}
}

@article{10.5555/2188385.2343692,
author = {Qin, Zhiwei and Goldfarb, Donald},
title = {Structured Sparsity via Alternating Direction Methods},
year = {2012},
issue_date = {3/1/2012},
publisher = {JMLR.org},
volume = {13},
number = {null},
issn = {1532-4435},
abstract = {We consider a class of sparse learning problems in high dimensional feature space regularized by a structured sparsity-inducing norm that incorporates prior knowledge of the group structure of the features. Such problems often pose a considerable challenge to optimization algorithms due to the non-smoothness and non-separability of the regularization term. In this paper, we focus on two commonly adopted sparsity-inducing regularization terms, the overlapping Group Lasso penalty l1/l2-norm and the l1/l∞-norm. We propose a unified framework based on the augmented Lagrangian method, under which problems with both types of regularization and their variants can be efficiently solved. As one of the core building-blocks of this framework, we develop new algorithms using a partial-linearization/splitting technique and prove that the accelerated versions of these algorithms require O(1/√ε) iterations to obtain an ε-optimal solution. We compare the performance of these algorithms against that of the alternating direction augmented Lagrangian and FISTA methods on a collection of data sets and apply them to two real-world problems to compare the relative merits of the two norms.},
journal = {J. Mach. Learn. Res.},
month = may,
pages = {1435–1468},
numpages = {34},
keywords = {overlapping group lasso, alternating direction methods, structured sparsity, augmented Lagrangian, variable splitting}
}

@article{10.5555/2188385.2343691,
author = {Song, Le and Smola, Alex and Gretton, Arthur and Bedo, Justin and Borgwardt, Karsten},
title = {Feature Selection via Dependence Maximization},
year = {2012},
issue_date = {3/1/2012},
publisher = {JMLR.org},
volume = {13},
number = {null},
issn = {1532-4435},
abstract = {We introduce a framework for feature selection based on dependence maximization between the selected features and the labels of an estimation problem, using the Hilbert-Schmidt Independence Criterion. The key idea is that good features should be highly dependent on the labels. Our approach leads to a greedy procedure for feature selection. We show that a number of existing feature selectors are special cases of this framework. Experiments on both artificial and real-world data show that our feature selector works well in practice.},
journal = {J. Mach. Learn. Res.},
month = may,
pages = {1393–1434},
numpages = {42},
keywords = {Hilbert-Schmidt independence criterion, Hilbert space embedding of distribution, kernel methods, independence measure, feature selection}
}

@article{10.5555/2188385.2343690,
author = {Rejchel, Wojciech},
title = {On Ranking and Generalization Bounds},
year = {2012},
issue_date = {3/1/2012},
publisher = {JMLR.org},
volume = {13},
number = {null},
issn = {1532-4435},
abstract = {The problem of ranking is to predict or to guess the ordering between objects on the basis of their observed features. In this paper we consider ranking estimators that minimize the empirical convex risk. We prove generalization bounds for the excess risk of such estimators with rates that are faster than 1/√n. We apply our results to commonly used ranking algorithms, for instance boosting or support vector machines. Moreover, we study the performance of considered estimators on real data sets.},
journal = {J. Mach. Learn. Res.},
month = may,
pages = {1373–1392},
numpages = {20},
keywords = {empirical process, support vector machine, convex risk minimization, U-process, excess risk}
}

@article{10.5555/2188385.2343689,
author = {Konidaris, George and Scheidwasser, Ilya and Barto, Andrew G.},
title = {Transfer in Reinforcement Learning via Shared Features},
year = {2012},
issue_date = {3/1/2012},
publisher = {JMLR.org},
volume = {13},
number = {null},
issn = {1532-4435},
abstract = {We present a framework for transfer in reinforcement learning based on the idea that related tasks share some common features, and that transfer can be achieved via those shared features. The framework attempts to capture the notion of tasks that are related but distinct, and provides some insight into when transfer can be usefully applied to a problem sequence and when it cannot. We apply the framework to the knowledge transfer problem, and show that an agent can learn a portable shaping function from experience in a sequence of tasks to significantly improve performance in a later related task, even given a very brief training period. We also apply the framework to skill transfer, to show that agents can learn portable skills across a sequence of tasks that significantly improve performance on later related tasks, approaching the performance of agents given perfectly learned problem-specific skills.},
journal = {J. Mach. Learn. Res.},
month = may,
pages = {1333–1371},
numpages = {39},
keywords = {transfer, skills, shaping, reinforcement learning}
}

@article{10.5555/2188385.2343688,
author = {Nelson, Blaine and Rubinstein, Benjamin I. P. and Huang, Ling and Joseph, Anthony D. and Lee, Steven J. and Rao, Satish and Tygar, J. D.},
title = {Query Strategies for Evading Convex-Inducing Classifiers},
year = {2012},
issue_date = {3/1/2012},
publisher = {JMLR.org},
volume = {13},
number = {null},
issn = {1532-4435},
abstract = {Classifiers are often used to detect miscreant activities. We study how an adversary can systematically query a classifier to elicit information that allows the attacker to evade detection while incurring a near-minimal cost of modifying their intended malfeasance. We generalize the theory of Lowd and Meek (2005) to the family of convex-inducing classifiers that partition their feature space into two sets, one of which is convex. We present query algorithms for this family that construct undetected instances of approximately minimal cost using only polynomially-many queries in the dimension of the space and in the level of approximation. Our results demonstrate that nearoptimal evasion can be accomplished for this family without reverse engineering the classifier's decision boundary. We also consider general lp costs and show that near-optimal evasion on the family of convex-inducing classifiers is generally efficient for both positive and negative convexity for all levels of approximation if p = 1.},
journal = {J. Mach. Learn. Res.},
month = may,
pages = {1293–1332},
numpages = {40},
keywords = {adversarial learning, evasion, reverse engineering, query algorithms}
}

@article{10.5555/2188385.2343687,
author = {Genovese, Christopher R. and Perone-Pacifico, Marco and Verdinelli, Isabella and Wasserman, Larry},
title = {Minimax Manifold Estimation},
year = {2012},
issue_date = {3/1/2012},
publisher = {JMLR.org},
volume = {13},
number = {null},
issn = {1532-4435},
abstract = {We find the minimax rate of convergence in Hausdorff distance for estimating a manifold M of dimension d embedded in RD given a noisy sample from the manifold. Under certain conditions, we show that the optimal rate of convergence is n-2/(2+d). Thus, the minimax rate depends only on the dimension of the manifold, not on the dimension of the space in which M is embedded.},
journal = {J. Mach. Learn. Res.},
month = may,
pages = {1263–1291},
numpages = {29},
keywords = {minimax estimation, manifold learning}
}

@article{10.5555/2503308.2503309,
author = {Rinaldo, Alessandro and Singh, Aarti and Nugent, Rebecca and Wasserman, Larry},
title = {Stability of Density-Based Clustering},
year = {2012},
issue_date = {January 2012},
publisher = {JMLR.org},
volume = {13},
number = {1},
issn = {1532-4435},
abstract = {High density clusters can be characterized by the connected components of a level set L(λ) = {x : p(x) > λ} of the underlying probability density function p generating the data, at some appropriate level λ ≥ 0. The complete hierarchical clustering can be characterized by a cluster tree T = ∪λ L(λ). In this paper, we study the behavior of a density level set estimate L(λ) and cluster tree estimate T based on a kernel density estimator with kernel bandwidth h. We define two notions of instability to measure the variability of L(λ) and T as a function of h, and investigate the theoretical properties of these instability measures.},
journal = {J. Mach. Learn. Res.},
month = apr,
pages = {905–948},
numpages = {44},
keywords = {model selection, level sets, density estimation, clustering, stability}
}

@article{10.5555/2503308.2343686,
author = {Rubinstein, Benjamin I. P. and Rubinstein, J. Hyam},
title = {A Geometric Approach to Sample Compression},
year = {2012},
issue_date = {January 2012},
publisher = {JMLR.org},
volume = {13},
number = {1},
issn = {1532-4435},
abstract = {The Sample Compression Conjecture of Littlestone & Warmuth has remained unsolved for a quarter century. While maximum classes (concept classes meeting Sauer's Lemma with equality) can be compressed, the compression of general concept classes reduces to compressing maximal classes (classes that cannot be expanded without increasing VC dimension). Two promising ways forward are: embedding maximal classes into maximum classes with at most a polynomial

license: Unlicense

repository: goyalkaraniit/acm-cr

repo_name: goyalkaraniit/acm-cr