text:
= {JMLR.org},
volume = {15},
number = {1},
issn = {1532-4435},
abstract = {This work addresses multi-class segmentation of indoor scenes with RGB-D inputs. While this area of research has gained much attention recently, most works still rely on handcrafted features. In contrast, we apply a multiscale convolutional network to learn features directly from the images and the depth information. Using a frame by frame labeling, we obtain nearly state-of-the-art performance on the NYU-v2 depth data set with an accuracy of 64.5%. We then show that the labeling can be further improved by exploiting the temporal consistency in the video sequence of the scene. To that goal, we present a method producing temporally consistent superpixels from a streaming video. Among the different methods producing superpixel segmentations of an image, the graph-based approach of Felzenszwalb and Huttenlocher is broadly employed. One of its interesting properties is that the regions are computed in a greedy manner in quasi-linear time by using a minimum spanning tree. In a framework exploiting minimum spanning trees all along, we propose an efficient video segmentation approach that computes temporally consistent pixels in a causal manner, filling the need for causal and real-time applications. We illustrate the labeling of indoor scenes in video sequences that could be processed in real-time using appropriate hardware such as an FPGA.},
journal = {J. Mach. Learn. Res.},
month = jan,
pages = {3489–3511},
numpages = {23},
keywords = {convolutional networks, depth information, deep learning, superpixels, optimization}
}

@article{10.5555/2627435.2697076,
author = {Gillian, Nicholas and Paradiso, Joseph A.},
title = {The Gesture Recognition Toolkit},
year = {2014},
issue_date = {January 2014},
publisher = {JMLR.org},
volume = {15},
number = {1},
issn = {1532-4435},
abstract = {The Gesture Recognition Toolkit is a cross-platform open-source C++ library designed to make real-time machine learning and gesture recognition more accessible for non-specialists. Emphasis is placed on ease of use, with a consistent, minimalist design that promotes accessibility while supporting flexibility and customization for advanced users. The toolkit features a broad range of classification and regression algorithms and has extensive support for building real-time systems. This includes algorithms for signal processing, feature extraction and automatic gesture spotting.},
journal = {J. Mach. Learn. Res.},
month = jan,
pages = {3483–3487},
numpages = {5},
keywords = {open source, regression, machine learning, gesture spotting, classification, feature extraction, signal processing, gesture recognition, C++, clustering}
}

@article{10.5555/2627435.2697075,
author = {Lin, Xiaodong and Pham, Minh and Ruszczy\'{n}ski, Andrzej},
title = {Alternating Linearization for Structured Regularization Problems},
year = {2014},
issue_date = {January 2014},
publisher = {JMLR.org},
volume = {15},
number = {1},
issn = {1532-4435},
abstract = {We adapt the alternating linearization method for proximal decomposition to structured regularization problems, in particular, to the generalized lasso problems. The method is related to two well-known operator splitting methods, the Douglas-Rachford and the Peaceman-Rachford method, but it has descent properties with respect to the objective function. This is achieved by employing a special update test, which decides whether it is beneficial to make a Peaceman-Rachford step, any of the two possible Douglas-Rachford steps, or none. The convergence mechanism of the method is related to that of bundle methods of nonsmooth optimization. We also discuss implementation for very large problems, with the use of specialized algorithms and sparse data structures. Finally, we present numerical results for several synthetic and real-world examples, including a three-dimensional fused lasso problem, which illustrate the scalability, efficacy, and accuracy of the method.},
journal = {J. Mach. Learn. Res.},
month = jan,
pages = {3447–3481},
numpages = {35},
keywords = {operator splitting, nonsmooth optimization, fused lasso, lasso}
}

@article{10.5555/2627435.2697074,
author = {Lecci, Fabrizio and Rinaldo, Alessandro and Wasserman, Larry},
title = {Statistical Analysis of Metric Graph Reconstruction},
year = {2014},
issue_date = {January 2014},
publisher = {JMLR.org},
volume = {15},
number = {1},
issn = {1532-4435},
abstract = {A metric graph is a 1-dimensional stratified metric space consisting of vertices and edges or loops glued together. Metric graphs can be naturally used to represent and model data that take the form of noisy filamentary structures, such as street maps, neurons, networks of rivers and galaxies. We consider the statistical problem of reconstructing the topology of a metric graph embedded in RD from a random sample. We derive lower and upper bounds on the minimax risk for the noiseless case and tubular noise case. The upper bound is based on the reconstruction algorithm given in Aanjaneya et al. (2012).},
journal = {J. Mach. Learn. Res.},
month = jan,
pages = {3425–3446},
numpages = {22},
keywords = {reconstruction, metric graph, filament, minimax estimation, manifold learning}
}

@article{10.5555/2627435.2697073,
author = {Shamir, Ohad and Shalev-Shwartz, Shai},
title = {Matrix Completion with the Trace Norm: Learning, Bounding, and Transducing},
year = {2014},
issue_date = {January 2014},
publisher = {JMLR.org},
volume = {15},
number = {1},
issn = {1532-4435},
abstract = {Trace-norm regularization is a widely-used and successful approach for collaborative filtering and matrix completion. However, previous learning guarantees require strong assumptions, such as a uniform distribution over the matrix entries. In this paper, we bridge this gap by providing such guarantees, under much milder assumptions which correspond to matrix completion as performed in practice. In fact, we claim that previous difficulties partially stemmed from a mismatch between the standard learning-theoretic modeling of matrix completion, and its practical application. Our results also shed some light on the issue of matrix completion with bounded models, which enforce predictions to lie within a certain range. In particular, we provide experimental and theoretical evidence that such models lead to a modest yet significant improvement.},
journal = {J. Mach. Learn. Res.},
month = jan,
pages = {3401–3423},
numpages = {23},
keywords = {trace-norm regularization, collaborative filtering, sample complexity, transductive learning, matrix completion}
}

@article{10.5555/2627435.2697072,
author = {Fabisch, Alexander and Metzen, Jan Hendrik},
title = {Active Contextual Policy Search},
year = {2014},
issue_date = {January 2014},
publisher = {JMLR.org},
volume = {15},
number = {1},
issn = {1532-4435},
abstract = {We consider the problem of learning skills that are versatilely applicable. One popular approach for learning such skills is contextual policy search in which the individual tasks are represented as context vectors. We are interested in settings in which the agent is able to actively select the tasks that it examines during the learning process. We argue that there is a better way than selecting each task equally often because some tasks might be easier to learn at the beginning and the knowledge that the agent can extract from these tasks can be transferred to similar but more difficult tasks. The methods that we propose for addressing the task-selection problem model the learning process as a nonstationary multi-armed bandit problem with custom intrinsic reward heuristics so that the estimated learning progress will be maximized. This approach does neither make any assumptions about the underlying contextual policy search algorithm nor about the policy representation. We present empirical results on an artificial benchmark problem and a ball throwing problem with a simulated Mitsubishi PA-10 robot arm which show that active context selection can improve the learning of skills considerably.},
journal = {J. Mach. Learn. Res.},
month = jan,
pages = {3371–3399},
numpages = {29},
keywords = {policy search, reinforcement learning, movement primitives, multi-task learning, active learning}
}

@article{10.5555/2627435.2697071,
author = {Miller, Jeffrey W. and Harrison, Matthew T.},
title = {Inconsistency of Pitman-Yor Process Mixtures for the Number of Components},
year = {2014},
issue_date = {January 2014},
publisher = {JMLR.org},
volume = {15},
number = {1},
issn = {1532-4435},
abstract = {In many applications, a finite mixture is a natural model, but it can be difficult to choose an appropriate number of components. To circumvent this choice, investigators are increasingly turning to Dirichlet process mixtures (DPMs), and Pitman-Yor process mixtures (PYMs), more generally. While these models may be well-suited for Bayesian density estimation, many investigators are using them for inferences about the number of components, by considering the posterior on the number of components represented in the observed data. We show that this posterior is not consistent---that is, on data from a finite mixture, it does not concentrate at the true number of components. This result applies to a large class of nonparametric mixtures, including DPMs and PYMs, over a wide variety of families of component distributions, including essentially all discrete families, as well as continuous exponential families satisfying mild regularity conditions (such as multivariate Gaussians).},
journal = {J. Mach. Learn. Res.},
month = jan,
pages = {3333–3370},
numpages = {38},
keywords = {consistency, Bayesian nonparametrics, finite mixture, Dirichlet process mixture, number of components}
}

@article{10.5555/2627435.2697070,
author = {Tan, Kean Ming and London, Palma and Mohan, Karthik and Lee, Su-In and Fazel, Maryam and Witten, Daniela},
title = {Learning Graphical Models with Hubs},
year = {2014},
issue_date = {January 2014},
publisher = {JMLR.org},
volume = {15},
number = {1},
issn = {1532-4435},
abstract = {We consider the problem of learning a high-dimensional graphical model in which there are a few hub nodes that are densely-connected to many other nodes. Many authors have studied the use of an l1 penalty in order to learn a sparse graph in the high-dimensional setting. However, the l1 penalty implicitly assumes that each edge is equally likely and independent of all other edges. We propose a general framework to accommodate more realistic networks with hub nodes, using a convex formulation that involves a row-column overlap norm penalty. We apply this general framework to three widely-used probabilistic graphical models: the Gaussian graphical model, the covariance graph model, and the binary Ising model. An alternating direction method of multipliers algorithm is used to solve the corresponding convex optimization problems. On synthetic data, we demonstrate that our proposed framework outperforms competitors that do not explicitly model hub nodes. We illustrate our proposal on a webpage data set and a gene expression data set.},
journal = {J. Mach. Learn. Res.},
month = jan,
pages = {3297–3331},
numpages = {35},
keywords = {alternating direction method of multipliers, covariance graph, lasso, Gaussian graphical model, binary network, hub}
}

@article{10.5555/2627435.2697069,
author = {Mannor, Shie and Perchet, Vianney and Stoltz, Gilles},
title = {Set-Valued Approachability and Online Learning with Partial Monitoring},
year = {2014},
issue_date = {January 2014},
publisher = {JMLR.org},
volume = {15},
number = {1},
issn = {1532-4435},
abstract = {Approachability has become a standard tool in analyzing learning algorithms in the adversarial online learning setup. We develop a variant of approachability for games where there is ambiguity in the obtained reward: it belongs to a set rather than being a single vector. Using this variant we tackle the problem of approachability in games with partial monitoring and develop a simple and generally efficient strategy (i.e., with constant per-step complexity) for this setup. As an important example, we instantiate our general strategy to the case when external regret or internal regret is to be minimized under partial monitoring.},
journal = {J. Mach. Learn. Res.},
month = jan,
pages = {3247–3295},
numpages = {49},
keywords = {approachability, online learning, partial monitoring, regret}
}

@article{10.5555/2627435.2697068,
author = {Van Der Maaten, Laurens},
title = {Accelerating T-SNE Using Tree-Based Algorithms},
year = {2014},
issue_date = {January 2014},
publisher = {JMLR.org},
volume = {15},
number = {1},
issn = {1532-4435},
abstract = {The paper investigates the acceleration of t-SNE--an embedding technique that is commonly used for the visualization of high-dimensional data in scatter plots--using two tree-based algorithms. In particular, the paper develops variants of the Barnes-Hut algorithm and of the dual-tree algorithm that approximate the gradient used for learning t-SNE embeddings in O(N log N). Our experiments show that the resulting algorithms substantially accelerate t-SNE, and that they make it possible to learn embeddings of data sets with millions of objects. Somewhat counterintuitively, the Barnes-Hut variant of t-SNE appears to outperform the dual-tree variant.},
journal = {J. Mach. Learn. Res.},
month = jan,
pages = {3221–3245},
numpages = {25},
keywords = {dual-tree algorithm, space-partitioning trees, t-SNE, multidimensional scaling, embedding, Barnes-Hut algorithm}
}

@article{10.5555/2627435.2697067,
author = {Nguyen-Dinh, Long-Van and Calatroni, Alberto and Tr\"{o}ster, Gerhard},
title = {Robust Online Gesture Recognition with Crowdsourced Annotations},
year = {2014},
issue_date = {January 2014},
publisher = {JMLR.org},
volume = {15},
number = {1},
issn = {1532-4435},
abstract = {Crowdsourcing is a promising way to reduce the effort of collecting annotations for training gesture recognition systems. Crowdsourced annotations suffer from "noise" such as mislabeling, or inaccurate identification of start and end time of gesture instances. In this paper we present SegmentedLCSS and WarpingLCSS, two template-matching methods offering robustness when trained with noisy crowdsourced annotations to spot gestures from wearable motion sensors. The methods quantize signals into strings of characters and then apply variations of the longest common subsequence algorithm (LCSS) to spot gestures. We compare the noise robustness of our methods against baselines which use dynamic time warping (DTW) and support vector machines (SVM). The experiments are performed on data sets with various gesture classes (10-17 classes) recorded from accelerometers on arms, with both real and synthetic crowdsourced annotations. WarpingLCSS has similar or better performance than baselines in absence of noisy annotations. In presence of 60% mislabeled instances, WarpingLCSS outperformed SVM by 22% F1-score and outperformed DTW-based methods by 36% F1-score on average. SegmentedLCSS yields similar performance as WarpingLCSS, however it performs one order of magnitude slower. Additionally, we show to use our methods to filter out the noise in the crowdsourced annotation before training a traditional classifier. The filtering increases the performance of SVM by 20% F1-score and of DTW-based methods by 8% F1-score on average in the noisy real crowdsourced annotations.},
journal = {J. Mach. Learn. Res.},
month = jan,
pages = {3187–3220},
numpages = {34},
keywords = {accelerometer sensors, template matching methods, crowdsourced annotation, gesture spotting, longest common subsequence}
}

@article{10.5555/2627435.2697066,
author = {Couckuyt, Ivo and Dhaene, Tom and Demeester, Piet},
title = {OoDACE Toolbox: A Flexible Object-Oriented Kriging Implementation},
year = {2014},
issue_date = {January 2014},
publisher = {JMLR.org},
volume = {15},
number = {1},
issn = {1532-4435},
abstract = {When analyzing data from computationally expensive simulation codes, surrogate modeling methods are firmly established as facilitators for design space exploration, sensitivity analysis, visualization and optimization. Kriging is a popular surrogate modeling technique used for the Design and Analysis of Computer Experiments (DACE). Hence, the past decade Kriging has been the subject of extensive research and many extensions have been proposed, e.g., co-Kriging, stochastic Kriging, blind Kriging, etc. However, few Kriging implementations are publicly available and tailored towards scientists and engineers. Furthermore, no Kriging toolbox exists that unifies several Kriging flavors. This paper addresses this need by presenting an efficient object-oriented Kriging implementation and several Kriging extensions, providing a flexible and easily extendable framework to test and implement new Kriging flavors while reusing as much code as possible.},
journal = {J. Mach. Learn. Res.},
month = jan,
pages = {3183–3186},
numpages = {4},
keywords = {DACE, surrogate modeling, blind Kriging, Kriging, metamodeling, co-Kriging, Gaussian process}
}

@article{10.5555/2627435.2697065,
author = {Fern\'{a}ndez-Delgado, Manuel and Cernadas, Eva and Barro, Sen\'{e}n and Amorim, Dinani},
title = {Do We Need Hundreds of Classifiers to Solve Real World Classification Problems?},
year = {2014},
issue_date = {January 2014},
publisher = {JMLR.org},
volume = {15},
number = {1},
issn = {1532-4435},
abstract = {We evaluate 179 classifiers arising from 17 families (discriminant analysis, Bayesian, neural networks, support vector machines, decision trees, rule-based classifiers, boosting, bagging, stacking, random forests and other ensembles, generalized linear models, nearest-neighbors, partial least squares and principal component regression, logistic and multinomial regression, multiple adaptive regression splines and other methods), implemented in Weka, R (with and without the caret package), C and Matlab, including all the relevant classifiers available today. We use 121 data sets, which represent the whole UCI data base (excluding the large-scale problems) and other own real problems, in order to achieve significant conclusions about the classifier behavior, not dependent on the data set collection. The classifiers most likely to be the bests are the random forest (RF) versions, the best of which (implemented in R and accessed via caret) achieves 94.1% of the maximum accuracy overcoming 90% in the 84.3% of the data sets. However, the difference is not statistically significant with the second best, the SVM with Gaussian kernel implemented in C using LibSVM, which achieves 92.3% of the maximum accuracy. A few models are clearly better than the remaining ones: random forest, SVM with Gaussian and polynomial kernels, extreme learning machine with Gaussian kernel, C5.0 and avNNet (a committee of multi-layer perceptrons implemented in R with the caret package). The random forest is clearly the best family of classifiers (3 out of 5 bests classifiers are RF), followed by SVM (4 classifiers in the top-10), neural networks and boosting ensembles (5 and 3 members in the top-20, respectively).},
journal = {J. Mach. Learn. Res.},
month = jan,
pages = {3133–3181},
numpages = {49},
keywords = {Bayesian classifiers, classification, multiple adaptive regression splines, random forest, logistic and multinomial regression, ensembles, UCI data base, decision trees, nearest-neighbors, rule-based classifiers, neural networks, support vector machine, partial least squares and principal component regression, generalized linear models, discriminant analysis}
}

@article{10.5555/2627435.2697064,
author = {Doliwa, Thorsten and Fan, Gaojian and Simon, Hans Ulrich and Zilles, Sandra},
title = {Recursive Teaching Dimension, VC-Dimension and Sample Compression},
year = {2014},
issue_date = {January 2014},
publisher = {JMLR.org},
volume = {15},
number = {1},
issn = {1532-4435},
abstract = {This paper is concerned with various combinatorial parameters of classes that can be learned from a small set of examples. We show that the recursive teaching dimension, recently introduced by Zilles et al. (2008), is strongly connected to known complexity notions in machine learning, e.g., the self-directed learning complexity and the VC-dimension. To the best of our knowledge these are the first results unveiling such relations between teaching and query learning as well as between teaching and the VC-dimension. It will turn out that for many natural classes the RTD is upper-bounded by the VCD, e.g., classes of VC-dimension 1, intersection-closed classes and finite maximum classes. However, we will also show that there are certain (but rare) classes for which the recursive teaching dimension exceeds the VC-dimension. Moreover, for maximum classes, the combinatorial structure induced by the RTD, called teaching plan, is highly similar to the structure of sample compression schemes. Indeed one can transform any repetition-free teaching plan for a maximum class C into an unlabeled sample compression scheme for C and vice versa, while the latter is produced by (i) the corner-peeling algorithm of Rubinstein and Rubinstein (2012) and (ii) the tail matching algorithm of Kuzmin and Warmuth (2007).},
journal = {J. Mach. Learn. Res.},
month = jan,
pages = {3107–3131},
numpages = {25},
keywords = {upper bounds, recursive teaching, Vapnik-Chervonenkis dimension, compression schemes, tail matching algorithm, combinatorial parameters}
}

@article{10.5555/2627435.2697063,
author = {Loh, Po-Ling and B\"{u}hlmann, Peter},
title = {High-Dimensional Learning of Linear Causal Networks via Inverse Covariance Estimation},
year = {2014},
issue_date = {January 2014},
publisher = {JMLR.org},
volume = {15},
number = {1},
issn = {1532-4435},
abstract = {We establish a new framework for statistical estimation of directed acyclic graphs (DAGs) when data are generated from a linear, possibly non-Gaussian structural equation model. Our framework consists of two parts: (1) inferring the moralized graph from the support of the inverse covariance matrix; and (2) selecting the best-scoring graph amongst DAGs that are consistent with the moralized graph. We show that when the error variances are known or estimated to close enough precision, the true DAG is the unique minimizer of the score computed using the reweighted squared l2-loss. Our population-level results have implications for the identifiability of linear SEMs when the error covariances are specified up to a constant multiple. On the statistical side, we establish rigorous conditions for high-dimensional consistency of our two-part algorithm, defined in terms of a "gap" between the true DAG and the next best candidate. Finally, we demonstrate that dynamic programming may be used to select the optimal DAG in linear time when the treewidth of the moralized graph is bounded.},
journal = {J. Mach. Learn. Res.},
month = jan,
pages = {3065–3105},
numpages = {41},
keywords = {inverse covariance matrix estimation, linear structural equation models, causal inference, identifiability, dynamic programming}
}

@article{10.5555/2627435.2697062,
author = {Chin, Wei-Sheng and Zhuang, Yong and Juan, Yu-Chin and Wu, Felix and Tung, Hsiao-Yu and Yu, Tong and Wang, Jui-Pin and Chang, Cheng-Xia and Yang, Chun-Pai and Chang, Wei-Cheng and Huang, Kuan-Hao and Kuo, Tzu-Ming and Lin, Shan-Wei and Lin, Young-San and Lu, Yu-Chen and Su, Yu-Chuan and Wei, Cheng-Kuang and Yin, Tu-Chun and Li, Chun-Liang and Lin, Ting-Wei and Tsai, Cheng-Hao and Lin, Shou-De and Lin, Hsuan-Tien and Lin, Chih-Jen},
title = {Effective String Processing and Matching for Author Disambiguation},
year = {2014},
issue_date = {January 2014},
publisher = {JMLR.org},
volume = {15},
number = {1},
issn = {1532-4435},
abstract = {Track 2 of KDD Cup 2013 aims at determining duplicated authors in a data set from Microsoft Academic Search. This type of problems appears in many large-scale applications that compile information from different sources. This paper describes our solution developed at National Taiwan University to win the first prize of the competition. We propose an effective name matching framework and realize two implementations. An important strategy in our approach is to consider Chinese and non-Chinese names separately because of their different naming conventions. Post-processing including merging results of two predictions further boosts the performance. Our approach achieves F1-score 0.99202 on the private leader board, while 0.99195 on the public leader board.},
journal = {J. Mach. Learn. Res.},
month = jan,
pages = {3037–3064},
numpages = {28},
keywords = {deduplication, author disambiguation, name matching}
}

@article{10.5555/2627435.2697061,
author = {Wu, Jiaxiang and Cheng, Jian},
title = {Bayesian Co-Boosting for Multi-Modal Gesture Recognition},
year = {2014},
issue_date = {January 2014},
publisher = {JMLR.org},
volume = {15},
number = {1},
issn = {1532-4435},
abstract = {With the development of data acquisition equipment, more and more modalities become available for gesture recognition. However, there still exist two critical issues for multimodal gesture recognition: how to select discriminative features for recognition and how to fuse features from different modalities. In this paper, we propose a novel Bayesian Co-Boosting framework for multi-modal gesture recognition. Inspired by boosting learning and co-training method, our proposed framework combines multiple collaboratively trained weak classifiers to construct the final strong classifier for the recognition task. During each iteration round, we randomly sample a number of feature subsets and estimate weak classifier's parameters for each subset. The optimal weak classifier and its corresponding feature subset are retained for strong classifier construction. Furthermore, we define an upper bound of training error and derive the update rule of instance's weight, which guarantees the error upper bound to be minimized through iterations. For demonstration, we present an implementation of our framework using hidden Markov models as weak classifiers. We perform extensive experiments using the ChaLearn MMGR and ChAirGest data sets, in which our approach achieves 97.63% and 96.53% accuracy respectively on each publicly available data set.},
journal = {J. Mach. Learn. Res.},
month = jan,
pages = {3013–3036},
numpages = {24},
keywords = {gesture recognition, Bayesian co-boosting, hidden Markov model, multimodal fusion, feature selection}
}

@article{10.5555/2627435.2697060,
author = {Osting, Braxton and Brune, Christoph and Osher, Stanley J.},
title = {Optimal Data Collection for Informative Rankings Expose Well-Connected Graphs},
year = {2014},
issue_date = {January 2014},
publisher = {JMLR.org},
volume = {15},
number = {1},
issn = {1532-4435},
abstract = {Given a graph where vertices represent alternatives and arcs represent pairwise comparison data, the statistical ranking problem is to find a potential function, defined on the vertices, such that the gradient of the potential function agrees with the pairwise comparisons. Our goal in this paper is to develop a method for collecting data for which the least squares estimator for the ranking problem has maximal Fisher information. Our approach, based on experimental design, is to view data collection as a bi-level optimization problem where the inner problem is the ranking problem and the outer problem is to identify data which maximizes the informativeness of the ranking. Under certain assumptions, the data collection problem decouples, reducing to a problem of finding multigraphs with large algebraic connectivity. This reduction of the data collection problem to graph-theoretic questions is one of the primary contributions of this work. As an application, we study the Yahoo! Movie user rating data set and demonstrate that the addition of a small number of well-chosen pairwise comparisons can significantly increase the Fisher informativeness of the ranking. As another application, we study the 2011-12 NCAA football schedule and propose schedules with the same number of games which are significantly more informative. Using spectral clustering methods to identify highly-connected communities within the division, we argue that the NCAA could improve its notoriously poor rankings by simply scheduling more out-of-conference games.},
journal = {J. Mach. Learn. Res.},
month = jan,
pages = {2981–3012},
numpages = {32},
keywords = {active learning, scheduling, algebraic connectivity, optimal experimental design, ranking, graph synthesis}
}

@article{10.5555/2627435.2697059,
author = {Srivastava, Nitish and Salakhutdinov, Ruslan},
title = {Multimodal Learning with Deep Boltzmann Machines},
year = {2014},
issue_date = {January 2014},
publisher = {JMLR.org},
volume = {15},
number = {1},
issn = {1532-4435},
abstract = {Data often consists of multiple diverse modalities. For example, images are tagged with textual information and videos are accompanied by audio. Each modality is characterized by having distinct statistical properties. We propose a Deep Boltzmann Machine for learning a generative model of such multimodal data. We show that the model can be used to create fused representations by combining features across modalities. These learned representations are useful for classification and information retrieval. By sampling from the conditional distributions over each data modality, it is possible to create these representations even when some data modalities are missing. We conduct experiments on bimodal image-text and audio-video data. The fused representation achieves good classification results on the MIR-Flickr data set matching or outperforming other deep models as well as SVM based models that use Multiple Kernel Learning. We further demonstrate that this multimodal model helps classification and retrieval even when only unimodal data is available at test time.},
journal = {J. Mach. Learn. Res.},
month = jan,
pages = {2949–2980},
numpages = {32},
keywords = {multimodal learning, neural networks, unsupervised learning, Boltzmann machines, deep learning}
}

@article{10.5555/2627435.2697058,
author = {Hsieh, Cho-Jui and Sustik, M\'{a}ty\'{a}s A. and Dhillon, Inderjit S. and Ravikumar, Pradeep},
title = {QUIC: Quadratic Approximation for Sparse Inverse Covariance Estimation},
year = {2014},
issue_date = {January 2014},
publisher = {JMLR.org},
volume = {15},
number = {1},
issn = {1532-4435},
abstract = {The l1-regularized Gaussian maximum likelihood estimator (MLE) has been shown to have strong statistical guarantees in recovering a sparse inverse covariance matrix, or alternatively the underlying graph structure of a Gaussian Markov Random Field, from very limited samples. We propose a novel algorithm for solving the resulting optimization problem which is a regularized log-determinant program. In contrast to recent state-of-the-art methods that largely use first order gradient information, our algorithm is based on Newton's method and employs a quadratic approximation, but with some modifications that leverage the structure of the sparse Gaussian MLE problem. We show that our method is superlinearly convergent, and present experimental results using synthetic and real-world application data that demonstrate the considerable improvements in performance of our method when compared to previous methods.},
journal = {J. Mach. Learn. Res.},
month = jan,
pages = {2911–2947},
numpages = {37},
keywords = {Gaussian Markov random field, regularization, covariance, optimization, graphical model}
}

@article{10.5555/2627435.2697057,
author = {Javanmard, Adel and Montanari, Andrea},
title = {Confidence Intervals and Hypothesis Testing for High-Dimensional Regression},
year = {2014},
issue_date = {January 2014},
publisher = {JMLR.org},
volume = {15},
number = {1},
issn = {1532-4435},
abstract = {Fitting high-dimensional statistical models often requires the use of non-linear parameter estimation procedures. As a consequence, it is generally impossible to obtain an exact characterization of the probability distribution of the parameter estimates. This in turn implies that it is extremely challenging to quantify the uncertainty associated with a certain parameter estimate. Concretely, no commonly accepted procedure exists for computing classical measures of uncertainty and statistical significance as confidence intervals or p- values for these models.We consider here high-dimensional linear regression problem, and propose an efficient algorithm for constructing confidence intervals and p-values. The resulting confidence intervals have nearly optimal size. When testing for the null hypothesis that a certain parameter is vanishing, our method has nearly optimal power.Our approach is based on constructing a 'de-biased' version of regularized M-estimators. The new construction improves over recent work in the field in that it does not assume a special structure on the design matrix. We test our method on synthetic data and a high-throughput genomic data set about riboflavin production rate, made publicly available by B\"{u}hlmann et al. (2014).},
journal = {J. Mach. Learn. Res.},
month = jan,
pages = {2869–2909},
numpages = {41},
keywords = {hypothesis testing, confidence intervals, LASSO, high-dimensional models, bias of an estimator}
}

@article{10.5555/2627435.2697056,
author = {Archer, Evan and Park, Il Memming and Pillow, Jonathan W.},
title = {Bayesian Entropy Estimation for Countable Discrete Distributions},
year = {2014},
issue_date = {January 2014},
publisher = {JMLR.org},
volume = {15},
number = {1},
issn = {1532-4435},
abstract = {We consider the problem of estimating Shannon's entropy H from discrete data, in cases where the number of possible symbols is unknown or even countably infinite. The Pitman-Yor process, a generalization of Dirichlet process, provides a tractable prior distribution over the space of countably infinite discrete distributions, and has found major applications in Bayesian non-parametric statistics and machine learning. Here we show that it provides a natural family of priors for Bayesian entropy estimation, due to the fact that moments of the induced posterior distribution over H can be computed analytically. We derive formulas for the posterior mean (Bayes' least squares estimate) and variance under Dirichlet and Pitman-Yor process priors. Moreover, we show that a fixed Dirichlet or Pitman-Yor process prior implies a narrow prior distribution over H, meaning the prior strongly determines the entropy estimate in the under-sampled regime. We derive a family of continuous measures for mixing Pitman-Yor processes to produce an approximately flat prior over H. We show that the resulting "Pitman-Yor Mixture" (PYM) entropy estimator is consistent for a large class of distributions. Finally, we explore the theoretical properties of the resulting estimator, and show that it performs well both in simulation and in application to real data.},
journal = {J. Mach. Learn. Res.},
month = jan,
pages = {2833–2868},
numpages = {36},
keywords = {Bayesian estimation, entropy, information theory, Pitman-Yor process, Bayesian nonparametrics, Dirichlet process, neural coding}
}

@article{10.5555/2627435.2697055,
author = {Anandkumar, Animashree and Ge, Rong and Hsu, Daniel and Kakade, Sham M. and Telgarsky, Matus},
title = {Tensor Decompositions for Learning Latent Variable Models},
year = {2014},
issue_date = {January 2014},
publisher = {JMLR.org},
volume = {15},
number = {1},
issn = {1532-4435},
abstract = {This work considers a computationally and statistically efficient parameter estimation method for a wide class of latent variable models--including Gaussian mixture models, hidden Markov models, and latent Dirichlet allocation--which exploits a certain tensor structure in their low-order observable moments (typically, of second- and third-order). Specifically, parameter estimation is reduced to the problem of extracting a certain (orthogonal) decomposition of a symmetric tensor derived from the moments; this decomposition can be viewed as a natural generalization of the singular value decomposition for matrices. Although tensor decompositions are generally intractable to compute, the decomposition of these specially structured tensors can be efficiently obtained by a variety of approaches, including power iterations and maximization approaches (similar to the case of matrices). A detailed analysis of a robust tensor power method is provided, establishing an analogue of Wedin's perturbation theorem for the singular vectors of matrices. This implies a robust and computationally tractable estimation approach for several popular latent variable models.},
journal = {J. Mach. Learn. Res.},
month = jan,
pages = {2773–2832},
numpages = {60},
keywords = {power method, method of moments, tensor decompositions, topic models, mixture models, latent variable models}
}

@article{10.5555/2627435.2697054,
author = {Jin, Jiashun and Zhang, Cun-Hui and Zhang, Qi},
title = {Optimality of Graphlet Screening in High Dimensional Variable Selection},
year = {2014},
issue_date = {January 2014},
publisher = {JMLR.org},
volume = {15},
number = {1},
issn = {1532-4435},
abstract = {Consider a linear model Y = Xβ+ωz, where X has n rows and p columns and z - N(0, In). We assume both p and n are large, including the case of p ≫ n. The unknown signal vector β is assumed to be sparse in the sense that only a small fraction of its components is nonzero. The goal is to identify such nonzero coordinates (i.e., variable selection).We are primarily interested in the regime where signals are both rare and weak so that successful variable selection is challenging but is still possible. We assume the Gram matrix G = X′X is sparse in the sense that each row has relatively few large entries (diagonals of G are normalized to 1). The sparsity of G naturally induces the sparsity of the so-called Graph of Strong Dependence (GOSD). The key insight is that there is an interesting interplay between the signal sparsity and graph sparsity: in a broad context, the signals decompose into many small-size components of GOSD that are disconnected to each other.We propose Graphlet Screening for variable selection. This is a two-step Screen and Clean procedure, where in the first step, we screen subgraphs of GOSD with sequential χ2-tests, and in the second step, we clean with penalized MLE. The main methodological innovation is to use GOSD to guide both the screening and cleaning processes.For any variable selection procedure β, we measure its performance by the Hamming distance between the sign vectors of β and β, and assess the optimality by the minimax Hamming distance. Compared with more stringent criteria such as exact support recovery or oracle property, which demand strong signals, the Hamming distance criterion is more appropriate for weak signals since it naturally allows a small fraction of errors.We show that in a broad class of situations, Graphlet Screening achieves the optimal rate of convergence in terms of the Hamming distance. Unlike Graphlet Screening, well-known procedures such as the L0/L1-penalization methods do not utilize local graphic structure for variable selection, so they generally do not achieve the optimal rate of convergence, even in very simple settings and even if the tuning parameters are ideally set.The the presented algorithm is implemented as R-CRAN package ScreenClean and in matlab (available at http://www.stat.cmu.edu/~jiashun/Research/software/GS-matlab/).},
journal = {J. Mach. Learn. Res.},
month = jan,
pages = {2723–2772},
numpages = {50},
keywords = {graph of least favorables (GOLF), graph of strong dependence (GOSD), rare and weak signal model, sparsity, phase diagram, asymptotic minimaxity, graphlet screening (GS), Hamming distance, screen and clean}
}

@article{10.5555/2627435.2697053,
author = {Henniges, Marc and Turner, Richard E. and Sahani, Maneesh and Eggert, Julian and L\"{u}cke, J\"{o}g},
title = {Efficient Occlusive Components Analysis},
year = {2014},
issue_date = {January 2014},
publisher = {JMLR.org},
volume = {15},
number = {1},
issn = {1532-4435},
abstract = {We study unsupervised learning in a probabilistic generative model for occlusion. The model uses two types of latent variables: one indicates which objects are present in the image, and the other how they are ordered in depth. This depth order then determines how the positions and appearances of the objects present, specified in the model parameters, combine to form the image. We show that the object parameters can be learned from an unlabeled set of images in which objects occlude one another. Exact maximum-likelihood learning is intractable. Tractable approximations can be derived, however, by applying a truncated variational approach to Expectation Maximization (EM). In numerical experiments it is shown that these approximations recover the underlying set of object parameters including data noise and sparsity. Experiments on a novel version of the bars test using colored bars, and experiments on more realistic data, show that the algorithm performs well in extracting the generating components. The studied approach demonstrates that the multiple-causes generative approach can be generalized to extract occluding components, which links research on occlusion to the field of sparse coding approaches.},
journal = {J. Mach. Learn. Res.},
month = jan,
pages = {2689–2722},
numpages = {34},
keywords = {occlusion, expectation truncation, unsupervised learning, generative models, sparse coding}
}

@article{10.5555/2627435.2697052,
author = {Sheikh, Abdul-Saboor and Shelton, Jacquelyn A. and L\"{u}cke, J\"{o}rg},
title = {A Truncated EM Approach for Spike-and-Slab Sparse Coding},
year = {2014},
issue_date = {January 2014},
publisher = {JMLR.org},
volume = {15},
number = {1},
issn = {1532-4435},
abstract = {We study inference and learning based on a sparse coding model with 'spike-and-slab' prior. As in standard sparse coding, the model used assumes independent latent sources that linearly combine to generate data points. However, instead of using a standard sparse prior such as a Laplace distribution, we study the application of a more flexible 'spike-and-slab' distribution which models the absence or presence of a source's contribution independently of its strength if it contributes. We investigate two approaches to optimize the parameters of spike-and-slab sparse coding: a novel truncated EM approach and, for comparison, an approach based on standard factored variational distributions. The truncated approach can be regarded as a variational approach with truncated posteriors as variational distributions. In applications to source separation we find that both approaches improve the state-of-the-art in a number of standard benchmarks, which argues for the use of 'spike-and-slab' priors for the corresponding data domains. Furthermore, we find that the truncated EM approach improves on the standard factored approach in source separation tasks--which hints to biases introduced by assuming posterior independence in the factored variational approach. Likewise, on a standard benchmark for image denoising, we find that the truncated EM approach improves on the factored variational approach. While the performance of the factored approach saturates with increasing numbers of hidden dimensions, the performance of the truncated approach improves the state-of-the-art for higher noise levels.},
journal = {J. Mach. Learn. Res.},
month = jan,
pages = {2653–2687},
numpages = {35},
keywords = {sparse coding, variational Bayes, approximate EM, spike-and-slab distributions, source separation, denoising, unsupervised learning}
}

@article{10.5555/2627435.2697051,
author = {Shimizu, Shohei and Bollen, Kenneth},
title = {Bayesian Estimation of Causal Direction in Acyclic Structural Equation Models with Individual-Specific Confounder Variables and Non-Gaussian Distributions},
year = {2014},
issue_date = {January 2014},
publisher = {JMLR.org},
volume = {15},
number = {1},
issn = {1532-4435},
abstract = {Several existing methods have been shown to consistently estimate causal direction assuming linear or some form of nonlinear relationship and no latent confounders. However, the estimation results could be distorted if either assumption is violated. We develop an approach to determining the possible causal direction between two observed variables when latent confounding variables are present. We first propose a new linear non-Gaussian acyclic structural equation model with individual-specific effects that are sometimes the source of confounding. Thus, modeling individual-specific effects as latent variables allows latent confounding to be considered. We then propose an empirical Bayesian approach for estimating possible causal direction using the new model. We demonstrate the effectiveness of our method using artificial and real-world data.},
journal = {J. Mach. Learn. Res.},
month = jan,
pages = {2629–2652},
numpages = {24},
keywords = {Bayesian networks, non-Gaussianity, estimation of causal direction, structural equation models, latent confounding variables}
}

@article{10.5555/2627435.2670332,
author = {Dhurandhar, Amit and Petrik, Marek},
title = {Efficient and Accurate Methods for Updating Generalized Linear Models with Multiple Feature Additions},
year = {2014},
issue_date = {January 2014},
publisher = {JMLR.org},
volume = {15},
number = {1},
issn = {1532-4435},
abstract = {In this paper, we propose an approach for learning regression models efficiently in an environment where multiple features and data-points are added incrementally in a multistep process. At each step, any finite number of features maybe added and hence, the setting is not amenable to low rank updates. We show that our approach is not only efficient and optimal for ordinary least squares, weighted least squares, generalized least squares and ridge regression, but also more generally for generalized linear models and lasso regression that use iterated re-weighted least squares for maximum likelihood estimation. Our approach instantiated to linear settings has close relations to the partitioned matrix inversion mechanism based on Schur's complement. For arbitrary regression methods, even a relaxation of the approach is no worse than using the model from the previous step or using a model that learns on the additional features and optimizes the residual of the model at the previous step. Such problems are commonplace in complex manufacturing operations consisting of hundreds of steps, where multiple measurements are taken at each step to monitor the quality of the final product. Accurately predicting if the finished product will meet specifications at each or, at least, important intermediate steps can be extremely useful in enhancing productivity. We further validate our claims through experiments on synthetic and real industrial data sets.},
journal = {J. Mach. Learn. Res.},
month = jan,
pages = {2607–2627},
numpages = {21},
keywords = {logistic regressions, feature selection, manufacturing, linear regression, lasso, group lasso}
}

@article{10.5555/2627435.2670331,
author = {Saberian, Mohammad and Vasconcelos, Nuno},
title = {Boosting Algorithms for Detector Cascade Learning},
year = {2014},
issue_date = {January 2014},
publisher = {JMLR.org},
volume = {15},
number = {1},
issn = {1532-4435},
abstract = {The problem of learning classifier cascades is considered. A new cascade boosting algorithm, fast cascade boosting (FCBoost), is proposed. FCBoost is shown to have a number of interesting properties, namely that it 1) minimizes a Lagrangian risk that jointly accounts for classification accuracy and speed, 2) generalizes adaboost, 3) can be made cost-sensitive to support the design of high detection rate cascades, and 4) is compatible with many predictor structures suitable for sequential decision making. It is shown that a rich family of such structures can be derived recursively from cascade predictors of two stages, denoted cascade generators. Generators are then proposed for two new cascade families, last-stage and multiplicative cascades, that generalize the two most popular cascade architectures in the literature. The concept of neutral predictors is finally introduced, enabling FCBoost to automatically determine the cascade configuration, i.e., number of stages and number of weak learners per stage, for the learned cascades. Experiments on face and pedestrian detection show that the resulting cascades outperform current state-of-the-art methods in both detection accuracy and speed.},
journal = {J. Mach. Learn. Res.},
month = jan,
pages = {2569–2605},
numpages = {37},
keywords = {boosting, sequential decision-making, cost-sensitive learning, detector cascades, complexity-constrained learning, real-time object detection, ensemble methods}
}

@article{10.5555/2627435.2670330,
author = {Slivkins, Aleksandrs},
title = {Contextual Bandits with Similarity Information},
year = {2014},
issue_date = {January 2014},
publisher = {JMLR.org},
volume = {15},
number = {1},
issn = {1532-4435},
abstract = {In a multi-armed bandit (MAB) problem, an online algorithm makes a sequence of choices. In each round it chooses from a time-invariant set of alternatives and receives the payoff associated with this alternative. While the case of small strategy sets is by now well-understood, a lot of recent work has focused on MAB problems with exponentially or infinitely large strategy sets, where one needs to assume extra structure in order to make the problem tractable. In particular, recent literature considered information on similarity between arms.We consider similarity information in the setting of contextual bandits, a natural extension of the basic MAB problem where before each round an algorithm is given the context--a hint about the payoffs in this round. Contextual bandits are directly motivated by placing advertisements on web pages, one of the crucial problems in sponsored search. A particularly simple way to represent similarity information in the contextual bandit setting is via a similarity distance between the context-arm pairs which bounds from above the difference between the respective expected payoffs.Prior work on contextual bandits with similarity uses "uniform" partitions of the similarity space, so that each context-arm pair is approximated by the closest pair in the partition. Algorithms based on "uniform" partitions disregard the structure of the payoffs and the context arrivals, which is potentially wasteful. We present algorithms that are based on adaptive partitions, and take advantage of "benign" payoffs and context arrivals without sacrificing the worst-case performance. The central idea is to maintain a finer partition in high-payoff regions of the similarity space and in popular regions of the context space. Our results apply to several other settings, e.g., MAB with constrained temporal change (Slivkins and Upfal, 2008) and sleeping bandits (Kleinberg et al., 2008a).},
journal = {J. Mach. Learn. Res.},
month = jan,
pages = {2533–2568},
numpages = {36},
keywords = {metric space, regret, Lipschitz-continuity, contextual bandits, multi-armed bandits}
}

@article{10.5555/2627435.2670329,
author = {Kone\v{c}n\'{y}, Jakub and Hagara, Michal},
title = {One-Shot-Learning Gesture Recognition Using HOG-HOF Features},
year = {2014},
issue_date = {January 2014},
publisher = {JMLR.org},
volume = {15},
number = {1},
issn = {1532-4435},
abstract = {The purpose of this paper is to describe one-shot-learning gesture recognition systems developed on the ChaLearn Gesture Dataset (ChaLearn). We use RGB and depth images and combine appearance (Histograms of Oriented Gradients) and motion descriptors (Histogram of Optical Flow) for parallel temporal segmentation and recognition. The Quadratic-Chi distance family is used to measure differences between histograms to capture cross-bin relationships. We also propose a new algorithm for trimming videos--to remove all the unimportant frames from videos. We present two methods that use a combination of HOG-HOF descriptors together with variants of a Dynamic Time Warping technique. Both methods outperform other published methods and help narrow the gap between human performance and algorithms on this task. The code is publicly available in the MLOSS repository.},
journal = {J. Mach. Learn. Res.},
month = jan,
pages = {2513–2532},
numpages = {20},
keywords = {dynamic time warping, ChaLearn, histogram of oriented gradients, histogram of optical flow}
}

@article{10.5555/2627435.2670328,
author = {Hazan, Elad and Kale, Satyen},
title = {Beyond the Regret Minimization Barrier: Optimal Algorithms for Stochastic Strongly-Convex Optimization},
year = {2014},
issue_date = {January 2014},
publisher = {JMLR.org},
volume = {15},
number = {1},
issn = {1532-4435},
abstract = {We give novel algorithms for stochastic strongly-convex optimization in the gradient oracle model which return a O(1/T)-approximate solution after T iterations. The first algorithm is deterministic, and achieves this rate via gradient updates and historical averaging. The second algorithm is randomized, and is based on pure gradient steps with a random step size.his rate of convergence is optimal in the gradient oracle model. This improves upon the previously known best rate of O(log(T/T), which was obtained by applying an online strongly-convex optimization algorithm with regret O(log(T)) to the batch setting.We complement this result by proving that any algorithm has expected regret of Ω(log(T)) in the online stochastic strongly-convex optimization setting. This shows that any online-to-batch conversion is inherently suboptimal for stochastic strongly-convex optimization. This is the first formal evidence that online convex optimization is strictly more difficult than batch stochastic convex optimization.},
journal = {J. Mach. Learn. Res.},
month = jan,
pages = {2489–2512},
numpages = {24},
keywords = {online learning, stochastic gradient descent, regret minimization, convex optimization}
}

@article{10.5555/2627435.2670327,
author = {Gentile, Claudio and Orabona, Francesco},
title = {On Multilabel Classification and Ranking with Bandit Feedback},
year = {2014},
issue_date = {January 2014},
publisher = {JMLR.org},
volume = {15},
number = {1},
issn = {1532-4435},
abstract = {We present a novel multilabel/ranking algorithm working in partial information settings. The algorithm is based on 2nd-order descent methods, and relies on upper-confidence bounds to trade-off exploration and exploitation. We analyze this algorithm in a partial adversarial setting, where covariates can be adversarial, but multilabel probabilities are ruled by (generalized) linear models. We show O(T1/2 log T) regret bounds, which improve in several ways on the existing results. We test the effectiveness of our upper-confidence scheme by contrasting against full-information baselines on diverse real-world multilabel data sets, often obtaining comparable performance.},
journal = {J. Mach. Learn. Res.},
month = jan,
pages = {2451–2487},
numpages = {37},
keywords = {contextual bandits, regret bounds, structured prediction, generalized linear, online learning, ranking}
}

@article{10.5555/2627435.2670326,
author = {Cohen, Shay B. and Stratos, Karl and Collins, Michael and Foster, Dean P. and Ungar, Lyle},
title = {Spectral Learning of Latent-Variable PCFGs: Algorithms and Sample Complexity},
year = {2014},
issue_date = {January 2014},
publisher = {JMLR.org},
volume = {15},
number = {1},
issn = {1532-4435},
abstract = {We introduce a spectral learning algorithm for latent-variable PCFGs (Matsuzaki et al., 2005; Petrov et al., 2006). Under a separability (singular value) condition, we prove that the method provides statistically consistent parameter estimates. Our result rests on three theorems: the first gives a tensor form of the inside-outside algorithm for PCFGs; the second shows that the required tensors can be estimated directly from training examples where hidden-variable values are missing; the third gives a PAC-style convergence bound for the estimation method.},
journal = {J. Mach. Learn. Res.},
month = jan,
pages = {2399–2449},
numpages = {51},
keywords = {spectral learning algorithms, latent-variable PCFGs}
}

@article{10.5555/2627435.2670325,
author = {Reece, Steven and Ghosh, Siddhartha and Rogers, Alex and Roberts, Stephen and Jennings, Nicholas R.},
title = {Efficient State-Space Inference of Periodic Latent Force Models},
year = {2014},
issue_date = {January 2014},
publisher = {JMLR.org},
volume = {15},
number = {1},
issn = {1532-4435},
abstract = {Latent force models (LFM) are principled approaches to incorporating solutions to differential equations within non-parametric inference methods. Unfortunately, the development and application of LFMs can be inhibited by their computational cost, especially when closed-form solutions for the LFM are unavailable, as is the case in many real world problems where these latent forces exhibit periodic behaviour. Given this, we develop a new sparse representation of LFMs which considerably improves their computational efficiency, as well as broadening their applicability, in a principled way, to domains with periodic or near periodic latent forces. Our approach uses a linear basis model to approximate one generative model for each periodic force. We assume that the latent forces are generated from Gaussian process priors and develop a linear basis model which fully expresses these priors. We apply our approach to model the thermal dynamics of domestic buildings and show that it is effective at predicting day-ahead temperatures within the homes. We also apply our approach within queueing theory in which quasi-periodic arrival rates are modelled as latent forces. In both cases, we demonstrate that our approach can be implemented efficiently using state-space methods which encode the linear dynamic systems via LFMs. Further, we show that state estimates obtained using periodic latent force models can reduce the root mean squared error to 17% of that from non-periodic models and 27% of the nearest rival approach which is the resonator model (S\"{a}rkk\"{a} et al., 2012; Hartikainen et al., 2012).},
journal = {J. Mach. Learn. Res.},
month = jan,
pages = {2337–2397},
numpages = {61},
keywords = {Kalman filter, queueing theory, kernel principle component analysis, Gaussian processes, latent force models}
}

@article{10.5555/2627435.2670324,
author = {Tziortziotis, Nikolaos and Dimitrakakis, Christos and Blekas, Konstantinos},
title = {Cover Tree Bayesian Reinforcement Learning},
year = {2014},
issue_date = {January 2014},
publisher = {JMLR.org},
volume = {15},
number = {1},
issn = {1532-4435},
abstract = {This paper proposes an online tree-based Bayesian approach for reinforcement learning. For inference, we employ a generalised context tree model. This defines a distribution on multivariate Gaussian piecewise-linear models, which can be updated in closed form. The tree structure itself is constructed using the cover tree method, which remains efficient in high dimensional spaces. We combine the model with Thompson sampling and approximate dynamic programming to obtain effective exploration policies in unknown environments. The flexibility and computational simplicity of the model render it suitable for many reinforcement learning problems in continuous state spaces. We demonstrate this in an experimental comparison with a Gaussian process model, a linear model and simple least squares policy iteration.},
journal = {J. Mach. Learn. Res.},
month = jan,
pages = {2313–2335},
numpages = {23},
keywords = {reinforcement learning, non-parametric statistics, Bayesian inference}
}

@article{10.5555/2627435.2670323,
author = {Anandkumar, Animashree and Ge, Rong and Hsu, Daniel and Kakade, Sham M.},
title = {A Tensor Approach to Learning Mixed Membership Community Models},
year = {2014},
issue_date = {January 2014},
publisher = {JMLR.org},
volume = {15},
number = {1},
issn = {1532-4435},
abstract = {Community detection is the task of detecting hidden communities from observed interactions. Guaranteed community detection has so far been mostly limited to models with non-overlapping communities such as the stochastic block model. In this paper, we remove this restriction, and provide guaranteed community detection for a family of probabilistic network models with overlapping communities, termed as the mixed membership Dirichlet model, first introduced by Airoldi et al. (2008). This model allows for nodes to have fractional memberships in multiple communities and assumes that the community memberships are drawn from a Dirichlet distribution. Moreover, it contains the stochastic block model as a special case. We propose a unified approach to learning these models via a tensor spectral decomposition method. Our estimator is based on low-order moment tensor of the observed network, consisting of 3-star counts. Our learning method is fast and is based on simple linear algebraic operations, e.g., singular value decomposition and tensor power iterations. We provide guaranteed recovery of community memberships and model parameters and present a careful finite sample analysis of our learning method. As an important special case, our results match the best known scaling requirements for the (homogeneous) stochastic block model.},
journal = {J. Mach. Learn. Res.},
month = jan,
pages = {2239–2312},
numpages = {74},
keywords = {moment-based estimation, mixed membership models, tensor methods, spectral methods, community detection}
}

@article{10.5555/2627435.2670322,
author = {Chen, Yudong and Jalali, Ali and Sanghavi, Sujay and Xu, Huan},
title = {Clustering Partially Observed Graphs via Convex Optimization},
year = {2014},
issue_date = {January 2014},
publisher = {JMLR.org},
volume = {15},
number = {1},
issn = {1532-4435},
abstract = {This paper considers the problem of clustering a partially observed unweighted graph--i.e., one where for some node pairs we know there is an edge between them, for some others we know there is no edge, and for the remaining we do not know whether or not there is an edge. We want to organize the nodes into disjoint clusters so that there is relatively dense (observed) connectivity within clusters, and sparse across clusters.We take a novel yet natural approach to this problem, by focusing on finding the clustering that minimizes the number of "disagreements"--i.e., the sum of the number of (observed) missing edges within clusters, and (observed) present edges across clusters. Our algorithm uses convex optimization; its basis is a reduction of disagreement minimization to the problem of recovering an (unknown) low-rank matrix and an (unknown) sparse matrix from their partially observed sum. We evaluate the performance of our algorithm on the classical Planted Partition/Stochastic Block Model. Our main theorem provides sufficient conditions for the success of our algorithm as a function of the minimum cluster size, edge density and observation probability; in particular, the results characterize the tradeoff between the observation probability and the edge density gap. When there are a constant number of clusters of equal size, our results are optimal up to logarithmic factors.},
journal = {J. Mach. Learn. Res.},
month = jan,
pages = {2213–2238},
numpages = {26},
keywords = {convex optimization, graph clustering, sparse and low-rank decomposition}
}

@article{10.5555/2627435.2670321,
author = {Huang, Xiaolin and Shi, Lei and Suykens, Johan A. K.},
title = {Ramp Loss Linear Programming Support Vector Machine},
year = {2014},
issue_date = {January 2014},
publisher = {JMLR.org},
volume = {15},
number = {1},
issn = {1532-4435},
abstract = {The ramp loss is a robust but non-convex loss for classification. Compared with other non-convex losses, a local minimum of the ramp loss can be effectively found. The effectiveness of local search comes from the piecewise linearity of the ramp loss. Motivated by the fact that the l1-penalty is piecewise linear as well, the l1-penalty is applied for the ramp loss, resulting in a ramp loss linear programming support vector machine (ramp-LPSVM). The proposed ramp-LPSVM is a piecewise linear minimization problem and the related optimization techniques are applicable. Moreover, the l1-penalty can enhance the sparsity. In this paper, the corresponding misclassification error and convergence behavior are discussed. Generally, the ramp loss is a truncated hinge loss. Therefore ramp-LPSVM possesses some similar properties as hinge loss SVMs. A local minimization algorithm and a global search strategy are discussed. The good optimization capability of the proposed algorithms makes ramp-LPSVM perform well in numerical experiments: the result of ramp-LPSVM is more robust than that of hinge SVMs and is sparser than that of ramp-SVM, which consists of the || undefined || k-penalty and the ramp loss.},
journal = {J. Mach. Learn. Res.},
month = jan,
pages = {2185–2211},
numpages = {27},
keywords = {l1-regularization, generalization error analysis, ramp loss, global optimization, support vector machine}
}

@article{10.5555/2627435.2670320,
author = {Lindsten, Fredrik and Jordan, Michael I. and Sch\"{o}n, Thomas B.},
title = {Particle Gibbs with Ancestor Sampling},
year = {2014},
issue_date = {January 2014},
publisher = {JMLR.org},
volume = {15},
number = {1},
issn = {1532-4435},
abstract = {Particle Markov chain Monte Carlo (PMCMC) is a systematic way of combining the two main tools used for Monte Carlo statistical inference: sequential Monte Carlo (SMC) and Markov chain Monte Carlo (MCMC). We present a new PMCMC algorithm that we refer to as particle Gibbs with ancestor sampling (PGAS). PGAS provides the data analyst with an off-the-shelf class of Markov kernels that can be used to simulate, for instance, the typically high-dimensional and highly autocorrelated state trajectory in a state-space model. The ancestor sampling procedure enables fast mixing of the PGAS kernel even when using seemingly few particles in the underlying SMC sampler. This is important as it can significantly reduce the computational burden that is typically associated with using SMC. PGAS is conceptually similar to the existing PG with backward simulation (PGBS) procedure. Instead of using separate forward and backward sweeps as in PGBS, however, we achieve the same effect in a single forward sweep. This makes PGAS well suited for addressing inference problems not only in state-space models, but also in models with more complex dependencies, such as non-Markovian, Bayesian nonparametric, and general probabilistic graphical models.},
journal = {J. Mach. Learn. Res.},
month = jan,
pages = {2145–2184},
numpages = {40},
keywords = {Bayesian inference, state-space models, non-Markovian models, sequential Monte Carlo, particle Markov chain Monte Carlo}
}

@article{10.5555/2627435.2670319,
author = {Xu, Zhixiang and Kusner, Matt J. and Weinberger, Kilian Q. and Chen, Minmin and Chapelle, Olivier},
title = {Classifier Cascades and Trees for Minimizing Feature Evaluation Cost},
year = {2014},
issue_date = {January 2014},
publisher = {JMLR.org},
volume = {15},
number = {1},
issn = {1532-4435},
abstract = {Machine learning algorithms have successfully entered industry through many real-world applications (e.g., search engines and product recommendations). In these applications, the test-time CPU cost must be budgeted and accounted for. In this paper, we examine two main components of the test-time CPU cost, classifier evaluation cost and feature extraction cost, and show how to balance these costs with the classifier accuracy. Since the computation required for feature extraction dominates the test-time cost of a classifier in these settings, we develop two algorithms to efficiently balance the performance with the test-time cost. Our first contribution describes how to construct and optimize a tree of classifiers, through which test inputs traverse along individual paths. Each path extracts different features and is optimized for a specific sub-partition of the input space. Our second contribution is a natural reduction of the tree of classifiers into a cascade. The cascade is particularly useful for class-imbalanced data sets as the majority of instances can be early-exited out of the cascade when the algorithm is sufficiently confident in its prediction. Because both approaches only compute features for inputs that benefit from them the most, we find our trained classifiers lead to high accuracies at a small fraction of the computational cost.},
journal = {J. Mach. Learn. Res.},
month = jan,
pages = {2113–2144},
numpages = {32},
keywords = {feature cost sensitive learning, web-search ranking, tree of classifiers, budgeted learning, resource efficient machine learning}
}

@article{10.5555/2627435.2670318,
author = {Nishihara, Robert and Murray, Iain and Adams, Ryan P.},
title = {Parallel MCMC with Generalized Elliptical Slice Sampling},
year = {2014},
issue_date = {January 2014},
publisher = {JMLR.org},
volume = {15},
number = {1},
issn = {1532-4435},
abstract = {Probabilistic models are conceptually powerful tools for finding structure in data, but their practical effectiveness is often limited by our ability to perform inference in them. Exact inference is frequently intractable, so approximate inference is often performed using Markov chain Monte Carlo (MCMC). To achieve the best possible results from MCMC, we want to effciently simulate many steps of a rapidly mixing Markov chain which leaves the target distribution invariant. Of particular interest in this regard is how to take advantage of multi-core computing to speed up MCMC-based inference, both to improve mixing and to distribute the computational load. In this paper, we present a parallelizable Markov chain Monte Carlo algorithm for effciently sampling from continuous probability distributions that can take advantage of hundreds of cores. This method shares information between parallel Markov chains to build a scale-location mixture of Gaussians approximation to the density function of the target distribution. We combine this approximation with a recently developed method known as elliptical slice sampling to create a Markov chain with no step-size parameters that can mix rapidly without requiring gradient or curvature computations.},
journal = {J. Mach. Learn. Res.},
month = jan,
pages = {2087–2112},
numpages = {26},
keywords = {parallelism, Markov chain Monte Carlo, approximate inference, slice sampling, elliptical slice sampling}
}

@article{10.5555/2627435.2670317,
author = {Van Den Oord, A\"{a}ron and Schrauwen, Benjamin},
title = {The Student-t Mixture as a Natural Image Patch Prior with Application to Image Compression},
year = {2014},
issue_date = {January 2014},
publisher = {JMLR.org},
volume = {15},
number = {1},
issn = {1532-4435},
abstract = {Recent results have shown that Gaussian mixture models (GMMs) are remarkably good at density modeling of natural image patches, especially given their simplicity. In terms of log likelihood on real-valued data they are comparable with the best performing techniques published, easily outperforming more advanced ones, such as deep belief networks. They can be applied to various image processing tasks, such as image denoising, deblurring and inpainting, where they improve on other generic prior methods, such as sparse coding and field of experts. Based on this we propose the use of another, even richer mixture model based image prior: the Student-t mixture model (STM). We demonstrate that it convincingly surpasses GMMs in terms of log likelihood, achieving performance competitive with the state of the art in image patch modeling. We apply both the GMM and STM to the task of lossy and lossless image compression, and propose efficient coding schemes that can easily be extended to other unsupervised machine learning models. Finally, we show that the suggested techniques outperform JPEG, with results comparable to or better than JPEG 2000.},
journal = {J. Mach. Learn. Res.},
month = jan,
pages = {2061–2086},
numpages = {26},
keywords = {mixture models, image compression, density modeling, unsupervised learning, GMM}
}

@article{10.5555/2627435.2670316,
author = {M\"{u}ller, Andreas C. and Behnke, Sven},
title = {PyStruct: Learning Structured Prediction in Python},
year = {2014},
issue_date = {January 2014},
publisher = {JMLR.org},
volume = {15},
number = {1},
issn = {1532-4435},
abstract = {Structured prediction methods have become a central tool for many machine learning applications. While more and more algorithms are developed, only very few implementations are available.PyStruct aims at providing a general purpose implementation of standard structured prediction methods, both for practitioners and as a baseline for researchers. It is written in Python and adapts paradigms and types from the scientific Python community for seamless integration with other projects.},
journal = {J. Mach. Learn. Res.},
month = jan,
pages = {2055–2060},
numpages = {6},
keywords = {structural support vector machines, structured prediction, conditional random fields, Python}
}

@article{10.5555/2627435.2670315,
author = {Peters, Jonas and Mooij, Joris M. and Janzing, Dominik and Sch\"{o}lkopf, Bernhard},
title = {Causal Discovery with Continuous Additive Noise Models},
year = {2014},
issue_date = {January 2014},
publisher = {JMLR.org},
volume = {15},
number = {1},
issn = {1532-4435},
abstract = {We consider the problem of learning causal directed acyclic graphs from an observational joint distribution. One can use these graphs to predict the outcome of interventional experiments, from which data are often not available. We show that if the observational distribution follows a structural equation model with an additive noise structure, the directed acyclic graph becomes identifiable from the distribution under mild conditions. This constitutes an interesting alternative to traditional methods that assume faithfulness and identify only the Markov equivalence class of the graph, thus leaving some edges undirected. We provide practical algorithms for finitely many samples, RESIT (regression with subsequent independence test) and two methods based on an independence score. We prove that RESIT is correct in the population setting and provide an empirical evaluation.},
journal = {J. Mach. Learn. Res.},
month = jan,
pages = {2009–2053},
numpages = {45},
keywords = {Bayesian networks, causal inference, identifiability, causal minimality, structural equation models, additive noise}
}

@article{10.5555/2627435.2670314,
author = {Lan, Andrew S. and Waters, Andrew E. and Studer, Christoph and Baraniuk, Richard G.},
title = {Sparse Factor Analysis for Learning and Content Analytics},
year = {2014},
issue_date = {January 2014},
publisher = {JMLR.org},
volume = {15},
number = {1},
issn = {1532-4435},
abstract = {We develop a new model and algorithms for machine learning-based learning analytics, which estimate a learner's knowledge of the concepts underlying a domain, and content analytics, which estimate the relationships among a collection of questions and those concepts. Our model represents the probability that a learner provides the correct response to a question in terms of three factors: their understanding of a set of underlying concepts, the concepts involved in each question, and each question's intrinsic difficulty. We estimate these factors given the graded responses to a collection of questions. The underlying estimation problem is ill-posed in general, especially when only a subset of the questions are answered. The key observation that enables a well-posed solution is the fact that typical educational domains of interest involve only a small number of key concepts. Leveraging this observation, we develop both a bi-convex maximum-likelihood-based solution and a Bayesian solution to the resulting SPARse Factor Analysis (SPARFA) problem. We also incorporate user-defined tags on questions to facilitate the interpretability of the estimated factors. Experiments with synthetic and real-world data demonstrate the efficacy of our approach. Finally, we make a connection between SPARFA and noisy, binary-valued (1-bit) dictionary learning that is of independent interest.},
journal = {J. Mach. Learn. Res.},
month = jan,
pages = {1959–2008},
numpages = {50},
keywords = {Bayesian latent factor analysis, personalized learning, sparse probit regression, sparse logistic regression, factor analysis}
}

@article{10.5555/2627435.2670313,
author = {Srivastava, Nitish and Hinton, Geoffrey and Krizhevsky, Alex and Sutskever, Ilya and Salakhutdinov, Ruslan},
title = {Dropout: A Simple Way to Prevent Neural Networks from Overfitting},
year = {2014},
issue_date = {January 2014},
publisher = {JMLR.org},
volume = {15},
number = {1},
issn = {1532-4435},
abstract = {Deep neural nets with a large number of parameters are very powerful machine learning systems. However, overfitting is a serious problem in such networks. Large networks are also slow to use, making it difficult to deal with overfitting by combining the predictions of many different large neural nets at test time. Dropout is a technique for addressing this problem. The key idea is to randomly drop units (along with their connections) from the neural network during training. This prevents units from co-adapting too much. During training, dropout samples from an exponential number of different "thinned" networks. At test time, it is easy to approximate the effect of averaging the predictions of all these thinned networks by simply using a single unthinned network that has smaller weights. This significantly reduces overfitting and gives major improvements over other regularization methods. We show that dropout improves the performance of neural networks on supervised learning tasks in vision, speech recognition, document classification and computational biology, obtaining state-of-the-art results on many benchmark data sets.},
journal = {J. Mach. Learn. Res.},
month = jan,
pages = {1929–1958},
numpages = {30},
keywords = {deep learning, model combination, regularization, neural networks}
}

@article{10.5555/2627435.2670312,
author = {St\"{a}dler, Nicolas and Stekhoven, Daniel J. and B\"{u}hlmann, Peter},
title = {Pattern Alternating Maximization Algorithm for Missing Data in High-Dimensional Problems},
year = {2014},
issue_date = {January 2014},
publisher = {JMLR.org},
volume = {15},
number = {1},
issn = {1532-4435},
abstract = {We propose a novel and efficient algorithm for maximizing the observed log-likelihood of a multivariate normal data matrix with missing values. We show that our procedure, based on iteratively regressing the missing on the observed variables, generalizes the standard EM algorithm by alternating between different complete data spaces and performing the E-Step incrementally. In this non-standard setup we prove numerical convergence to a stationary point of the observed log-likelihood. For high-dimensional data, where the number of variables may greatly exceed sample size, we perform regularization using a Lasso-type penalty. This introduces sparsity in the regression coefficients used for imputation, permits fast computation and warrants competitive performance in terms of estimating the missing entries. We show on simulated and real data that the new method often improves upon other modern imputation techniques such as k-nearest neighbors imputation, nuclear norm minimization or a penalized likelihood approach with an l1-penalty on the concentration matrix.},
journal = {J. Mach. Learn. Res.},
month = jan,
pages = {1903–1928},
numpages = {26},
keywords = {observed likelihood, (partial) E- and M-Step, penalized variational free energy, Lasso, missing data}
}

@article{10.5555/2627435.2638593,
author = {Jyl\"{a}nki, Pasi and Nummenmaa, Aapo and Vehtari, Aki},
title = {Expectation Propagation for Neural Networks with Sparsity-Promoting Priors},
year = {2014},
issue_date = {January 2014},
publisher = {JMLR.org},
volume = {15},
number = {1},
issn = {1532-4435},
abstract = {We propose a novel approach for nonlinear regression using a two-layer neural network (NN) model structure with sparsity-favoring hierarchical priors on the network weights. We present an expectation propagation (EP) approach for approximate integration over the posterior distribution of the weights, the hierarchical scale parameters of the priors, and the residual scale. Using a factorized posterior approximation we derive a computationally effcient algorithm, whose complexity scales similarly to an ensemble of independent sparse linear models. The approach enables flexible definition of weight priors with different sparseness properties such as independent Laplace priors with a common scale parameter or Gaussian automatic relevance determination (ARD) priors with different relevance parameters for all inputs. The approach can be extended beyond standard activation functions and NN model structures to form flexible nonlinear predictors from multiple sparse linear models. The effects of the hierarchical priors and the predictive performance of the algorithm are assessed using both simulated and real-world data. Comparisons are made to two alternative models with ARD priors: a Gaussian process with a NN covariance function and marginal maximum a posteriori estimates of the relevance parameters, and a NN with Markov chain Monte Carlo integration over all the unknown model parameters.},
journal = {J. Mach. Learn. Res.},
month = jan,
pages = {1849–1901},
numpages = {53},
keywords = {linear model, automatic relevance determination, multilayer perceptron, sparse prior, expectation propagation, neural network}
}

@article{10.5555/2627435.2638592,
author = {Zhu, Jun and Chen, Ning and Xing, Eric P.},
title = {Bayesian Inference with Posterior Regularization and Applications to Infinite Latent SVMs},
year = {2014},
issue_date = {January 2014},
publisher = {JMLR.org},
volume = {15},
number = {1},
issn = {1532-4435},
abstract = {Existing Bayesian models, especially nonparametric Bayesian methods, rely on specially conceived priors to incorporate domain knowledge for discovering improved latent representations. While priors affect posterior distributions through Bayes' rule, imposing posterior regularization is arguably more direct and in some cases more natural and general. In this paper, we present regularized Bayesian inference (RegBayes), a novel computational framework that performs posterior inference with a regularization term on the desired post-data posterior distribution under an information theoretical formulation. RegBayes is more flexible than the procedure that elicits expert knowledge via priors, and it covers both directed Bayesian networks and undirected Markov networks. When the regularization is induced from a linear operator on the posterior distributions, such as the expectation operator, we present a general convex-analysis theorem to characterize the solution of RegBayes. Furthermore, we present two concrete examples of RegBayes, infinite latent support vector machines (iLSVM) and multi-task infinite latent support vector machines (MT-iLSVM), which explore the large-margin idea in combination with a nonparametric Bayesian model for discovering predictive latent features for classification and multi-task learning, respectively. We present efficient inference methods and report empirical studies on several benchmark data sets, which appear to demonstrate the merits inherited from both large-margin learning and Bayesian nonparametrics. Such results contribute to push forward the interface between these two important subfields, which have been largely treated as isolated in the community.},
journal = {J. Mach. Learn. Res.},
month = jan,
pages = {1799–1847},
numpages = {49},
keywords = {large-margin learning, multi-task learning, posterior regularization, classification, Bayesian nonparametrics, Bayesian inference}
}

@article{10.5555/2627435.2638591,
author = {Von Luxburg, Ulrike and Radl, Agnes and Hein, Matthias},
title = {Hitting and Commute Times in Large Random Neighborhood Graphs},
year = {2014},
issue_date = {January 2014},
publisher = {JMLR.org},
volume = {15},
number = {1},
issn = {1532-4435},
abstract = {In machine learning, a popular tool to analyze the structure of graphs is the hitting time and the commute distance (resistance distance). For two vertices u and v, the hitting time Huv is the expected time it takes a random walk to travel from u to v. The commute distance is its symmetrized version Cuv = Huv +Hvu. In our paper we study the behavior of hitting times and commute distances when the number n of vertices in the graph tends to infinity. We focus on random geometric graphs (ε-graphs, kNN graphs and Gaussian similarity graphs), but our results also extend to graphs with a given expected degree distribution or Erdos-R\'{e}nyi graphs with planted partitions. We prove that in these graph families, the suitably rescaled hitting time Huv converges to 1/dv and the rescaled commute time to 1/du+1=dv where du and dv denote the degrees of vertices u and v. In these cases, hitting and commute times do not provide information about the structure of the graph, and their use is discouraged in many machine learning applications.},
journal = {J. Mach. Learn. Res.},
month = jan,
pages = {1751–1798},
numpages = {48},
keywords = {spectral gap, random graph, k-nearest neighbor graph, commute distance, resistance}
}

@article{10.5555/2627435.2638590,
author = {Kolar, Mladen and Liu, Han and Xing, Eric P.},
title = {Graph Estimation from Multi-Attribute Data},
year = {2014},
issue_date = {January 2014},
publisher = {JMLR.org},
volume = {15},
number = {1},
issn = {1532-4435},
abstract = {Undirected graphical models are important in a number of modern applications that involve exploring or exploiting dependency structures underlying the data. For example, they are often used to explore complex systems where connections between entities are not well understood, such as in functional brain networks or genetic networks. Existing methods for estimating structure of undirected graphical models focus on scenarios where each node represents a scalar random variable, such as a binary neural activation state or a continuous mRNA abundance measurement, even though in many real world problems, nodes can represent multivariate variables with much richer meanings, such as whole images, text documents, or multi-view feature vectors. In this paper, we propose a new principled framework for estimating the structure of undirected graphical models from such multivariate (or multi-attribute) nodal data. The structure of a graph is inferred through estimation of non-zero partial canonical correlation between nodes. Under a Gaussian model, this strategy is equivalent to estimating conditional independencies between random vectors represented by the nodes and it generalizes the classical problem of covariance selection (Dempster, 1972). We relate the problem of estimating non-zero partial canonical correlations to maximizing a penalized Gaussian likelihood objective and develop a method that efficiently maximizes this objective. Extensive simulation studies demonstrate the effectiveness of the method under various conditions. We provide illustrative applications to uncovering gene regulatory networks from gene and protein profiles, and uncovering brain connectivity graph from positron emission tomography data. Finally, we provide sufficient conditions under which the true graphical structure can be recovered correctly.},
journal = {J. Mach. Learn. Res.},
month = jan,
pages = {1713–1750},
numpages = {38},
keywords = {network analysis, partial canonical correlation, graphical model selection, multi-attribute data}
}

@article{10.5555/2627435.2638589,
author = {Wang, Zhan and Paterlini, Sandra and Gao, Fuchang and Yang, Yuhong},
title = {Adaptive Minimax Regression Estimation over Sparse l<sub>q</sub>-Hulls},
year = {2014},
issue_date = {January 2014},
publisher = {JMLR.org},
volume = {15},
number = {1},
issn = {1532-4435},
abstract = {Given a dictionary of Mn predictors, in a random design regression setting with n observations, we construct estimators that target the best performance among all the linear combinations of the predictors under a sparse lq-norm (0 ≤ q ≤ 1) constraint on the linear coefficients. Besides identifying the optimal rates of convergence, our universal aggregation strategies by model mixing achieve the optimal rates simultaneously over the full range of 0 ≤ q ≤ 1 for any Mn and without knowledge of the lq-norm of the best linear coefficients to represent the regression function.To allow model misspecification, our upper bound results are obtained in a framework of aggregation of estimates. A striking feature is that no specific relationship among the predictors is needed to achieve the upper rates of convergence (hence permitting basically arbitrary correlations between the predictors). Therefore, whatever the true regression function (assumed to be uniformly bounded), our estimators automatically exploit any sparse representation of the regression function (if any), to the best extent possible within the lq-constrained linear combinations for any 0 ≤ q ≤ 1.A sparse approximation result in the lq-hulls turns out to be crucial to adaptively achieve minimax rate optimal aggregation. It precisely characterizes the number of terms needed to achieve a prescribed accuracy of approximation to the best linear combination in an lq-hull for 0 ≤ q ≤ 1. It offers the insight that the minimax rate of lq-aggregation is basically determined by an effective model size, which is a sparsity index that depends on q, Mn, n, and the lq-norm bound in an easily interpretable way based on a classical model selection theory that deals with a large number of models.},
journal = {J. Mach. Learn. Res.},
month = jan,
pages = {1675–1711},
numpages = {37},
keywords = {high-dimensional sparse learning, optimal aggregation, minimax rate of convergence, sparse lq-constraint, model selection}
}

@article{10.5555/2627435.2638588,
author = {Agarwal, Shivani},
title = {Surrogate Regret Bounds for Bipartite Ranking via Strongly Proper Losses},
year = {2014},
issue_date = {January 2014},
publisher = {JMLR.org},
volume = {15},
number = {1},
issn = {1532-4435},
abstract = {The problem of bipartite ranking, where instances are labeled positive or negative and the goal is to learn a scoring function that minimizes the probability of mis-ranking a pair of positive and negative instances (or equivalently, that maximizes the area under the ROC curve), has been widely studied in recent years. A dominant theoretical and algorithmic framework for the problem has been to reduce bipartite ranking to pairwise classification; in particular, it is well known that the bipartite ranking regret can be formulated as a pairwise classification regret, which in turn can be upper bounded using usual regret bounds for classification problems. Recently, Kotlowski et al. (2011) showed regret bounds for bipartite ranking in terms of the regret associated with balanced versions of the standard (non-pairwise) logistic and exponential losses. In this paper, we show that such (nonpairwise) surrogate regret bounds for bipartite ranking can be obtained in terms of a broad class of proper (composite) losses that we term as strongly proper. Our proof technique is much simpler than that of Kotlowski et al. (2011), and relies on properties of proper (composite) losses as elucidated recently by Reid and Williamson (2010, 2011) and others. Our result yields explicit surrogate bounds (with no hidden balancing terms) in terms of a variety of strongly proper losses, including for example logistic, exponential, squared and squared hinge losses as special cases. An important consequence is that standard algorithms minimizing a (non-pairwise) strongly proper loss, such as logistic regression and boosting algorithms (assuming a universal function class and appropriate regularization), are in fact consistent for bipartite ranking; moreover, our results allow us to quantify the bipartite ranking regret in terms of the corresponding surrogate regret. We also obtain tighter surrogate bounds under certain low-noise conditions via a recent result of Cl\'{e}men\c{c}on and Robbiano (2011).},
journal = {J. Mach. Learn. Res.},
month = jan,
pages = {1653–1674},
numpages = {22},
keywords = {regret bounds, strongly proper losses, bipartite ranking, statistical consistency, proper losses, area under ROC curve (AUC)}
}

@article{10.5555/2627435.2638587,
author = {Wager, Stefan and Hastie, Trevor and Efron, Bradley},
title = {Confidence Intervals for Random Forests: The Jackknife and the Infinitesimal Jackknife},
year = {2014},
issue_date = {January 2014},
publisher = {JMLR.org},
volume = {15},
number = {1},
issn = {1532-4435},
abstract = {We study the variability of predictions made by bagged learners and random forests, and show how to estimate standard errors for these methods. Our work builds on variance estimates for bagging proposed by Efron (1992, 2013) that are based on the jackknife and the infinitesimal jackknife (IJ). In practice, bagged predictors are computed using a finite number B of bootstrap replicates, and working with a large B can be computationally expensive. Direct applications of jackknife and IJ estimators to bagging require B = Θ(n1.5) bootstrap replicates to converge, where n is the size of the training set. We propose improved versions that only require B = Θ(n) replicates. Moreover, we show that the IJ estimator requires 1.7 times less bootstrap replicates than the jackknife to achieve a given accuracy. Finally, we study the sampling distributions of the jackknife and IJ variance estimates themselves. We illustrate our findings with multiple experiments and simulation studies.},
journal = {J. Mach. Learn. Res.},
month = jan,
pages = {1625–1651},
numpages = {27},
keywords = {variance estimation, Monte Carlo noise, bagging, jackknife methods}
}

@article{10.5555/2627435.2638586,
author = {Homan, Matthew D. and Gelman, Andrew},
title = {The No-U-Turn Sampler: Adaptively Setting Path Lengths in Hamiltonian Monte Carlo},
year = {2014},
issue_date = {January 2014},
publisher = {JMLR.org},
volume = {15},
number = {1},
issn = {1532-4435},
abstract = {Hamiltonian Monte Carlo (HMC) is a Markov chain Monte Carlo (MCMC) algorithm that avoids the random walk behavior and sensitivity to correlated parameters that plague many MCMC methods by taking a series of steps informed by first-order gradient information. These features allow it to converge to high-dimensional target distributions much more quickly than simpler methods such as random walk Metropolis or Gibbs sampling. However, HMC's performance is highly sensitive to two user-specified parameters: a step size ε and a desired number of steps L. In particular, if L is too small then the algorithm exhibits undesirable random walk behavior, while if L is too large the algorithm wastes computation. We introduce the No-U-Turn Sampler (NUTS), an extension to HMC that eliminates the need to set a number of steps L. NUTS uses a recursive algorithm to build a set of likely candidate points that spans a wide swath of the target distribution, stopping automatically when it starts to double back and retrace its steps. Empirically, NUTS performs at least as efficiently as (and sometimes more effciently than) a well tuned standard HMC method, without requiring user intervention or costly tuning runs. We also derive a method for adapting the step size parameter ε on the fly based on primal-dual averaging. NUTS can thus be used with no hand-tuning at all, making it suitable for applications such as BUGS-style automatic inference engines that require efficient "turnkey" samplers.},
journal = {J. Mach. Learn. Res.},
month = jan,
pages = {1593–1623},
numpages = {31},
keywords = {Bayesian inference, adaptive Monte Carlo, Markov chain Monte Carlo, dual averaging, Hamiltonian Monte Carlo}
}

@article{10.5555/2627435.2638585,
author = {Janzamin, Majid and Anandkumar, Animashree},
title = {High-Dimensional Covariance Decomposition into Sparse Markov and Independence Models},
year = {2014},
issue_date = {January 2014},
publisher = {JMLR.org},
volume = {15},
number = {1},
issn = {1532-4435},
abstract = {Fitting high-dimensional data involves a delicate tradeoff between faithful representation and the use of sparse models. Too often, sparsity assumptions on the fitted model are too restrictive to provide a faithful representation of the observed data. In this paper, we present a novel framework incorporating sparsity in different domains. We decompose the observed covariance matrix into a sparse Gaussian Markov model (with a sparse precision matrix) and a sparse independence model (with a sparse covariance matrix). Our framework incorporates sparse covariance and sparse precision estimation as special cases and thus introduces a richer class of high-dimensional models. We characterize sufficient conditions for identifiability of the two models, viz., Markov and independence models. We propose an efficient decomposition method based on a modification of the popular l1-penalized maximum-likelihood estimator (l1-MLE). We establish that our estimator is consistent in both the domains, i.e., it successfully recovers the supports of both Markov and independence models, when the number of samples n scales as n = Ω(d2 log p), where p is the number of variables and d is the maximum node degree in the Markov model. Our experiments validate these results and also demonstrate that our models have better inference accuracy under simple algorithms such as loopy belief propagation.},
journal = {J. Mach. Learn. Res.},
month = jan,
pages = {1549–1591},
numpages = {43},
keywords = {sparse covariance models, sparsistency, convex optimization, sparse graphical model selection, high-dimensional covariance estimation}
}

@article{10.5555/2627435.2638584,
author = {Wang, Po-Wei and Lin, Chih-Jen},
title = {Iteration Complexity of Feasible Descent Methods for Convex Optimization},
year = {2014},
issue_date = {January 2014},
publisher = {JMLR.org},
volume = {15},
number = {1},
issn = {1532-4435},
abstract = {In many machine learning problems such as the dual form of SVM, the objective function to be minimized is convex but not strongly convex. This fact causes difficulties in obtaining the complexity of some commonly used optimization algorithms. In this paper, we proved the global linear convergence on a wide range of algorithms when they are applied to some non-strongly convex problems. In particular, we are the first to prove O(log(1/ε)) time complexity of cyclic coordinate descent methods on dual problems of support vector classification and regression.},
journal = {J. Mach. Learn. Res.},
month = jan,
pages = {1523–1548},
numpages = {26},
keywords = {feasible descent methods, iteration complexity, convergence rate, convex optimization}
}

@article{10.5555/2627435.2638583,
author = {Durante, Daniele and Scarpa, Bruno and Dunson, David B.},
title = {Locally Adaptive Factor Processes for Multivariate Time Series},
year = {2014},
issue_date = {January 2014},
publisher = {JMLR.org},
volume = {15},
number = {1},
issn = {1532-4435},
abstract = {In modeling multivariate time series, it is important to allow time-varying smoothness in the mean and covariance process. In particular, there may be certain time intervals exhibiting rapid changes and others in which changes are slow. If such time-varying smoothness is not accounted for, one can obtain misleading inferences and predictions, with oversmoothing across erratic time intervals and under-smoothing across times exhibiting slow variation. This can lead to mis-calibration of predictive intervals, which can be substantially too narrow or wide depending on the time. We propose a locally adaptive factor process for characterizing multivariate mean-covariance changes in continuous time, allowing locally varying smoothness in both the mean and covariance matrix. This process is constructed utilizing latent dictionary functions evolving in time through nested Gaussian processes and linearly related to the observed data with a sparse mapping. Using a differential equation representation, we bypass usual computational bottlenecks in obtaining MCMC and online algorithms for approximate Bayesian inference. The performance is assessed in simulations and illustrated in a financial application.},
journal = {J. Mach. Learn. Res.},
month = jan,
pages = {1493–1522},
numpages = {30},
keywords = {multivariate time series, Bayesian nonparametrics, nested Gaussian process, stochastic volatility, locally varying smoothness}
}

@article{10.5555/2627435.2638582,
author = {Gupta, Maya R. and Bengio, Samy and Weston, Jason},
title = {Training Highly Multiclass Classifiers},
year = {2014},
issue_date = {January 2014},
publisher = {JMLR.org},
volume = {15},
number = {1},
issn = {1532-4435},
abstract = {Classification problems with thousands or more classes often have a large range of class-confusabilities, and we show that the more-confusable classes add more noise to the empirical loss that is minimized during training. We propose an online solution that reduces the effect of highly confusable classes in training the classifier parameters, and focuses the training on pairs of classes that are easier to differentiate at any given time in the training. We also show that the adagrad method, recently proposed for automatically decreasing step sizes for convex stochastic gradient descent, can also be profitably applied to the nonconvex joint training of supervised dimensionality reduction and linear classifiers as done in Wsabie. Experiments on ImageNet benchmark data sets and proprietary image recognition problems with 15,000 to 97,000 classes show substantial gains in classification accuracy compared to one-vs-all linear SVMs and Wsabie.},
journal = {J. Mach. Learn. Res.},
month = jan,
pages = {1461–1492},
numpages = {32},
keywords = {multiclass, online learning, large-scale, stochastic gradient, classification}
}

@article{10.5555/2627435.2638581,
author = {Boumal, Nicolas and Mishra, Bamdev and Absil, P.-A. and Sepulchre, Rodolphe},
title = {Manopt, a Matlab Toolbox for Optimization on Manifolds},
year = {2014},
issue_date = {January 2014},
publisher = {JMLR.org},
volume = {15},
number = {1},
issn = {1532-4435},
abstract = {Optimization on manifolds is a rapidly developing branch of nonlinear optimization. Its focus is on problems where the smooth geometry of the search space can be leveraged to design efficient numerical algorithms. In particular, optimization on manifolds is well-suited to deal with rank and orthogonality constraints. Such structured constraints appear pervasively in machine learning applications, including low-rank matrix completion, sensor network localization, camera network registration, independent component analysis, metric learning, dimensionality reduction and so on.The Manopt toolbox, available at www.manopt.org, is a user-friendly, documented piece of software dedicated to simplify experimenting with state of the art Riemannian optimization algorithms. By dealing internally with most of the differential geometry, the package aims particularly at lowering the entrance barrier.},
journal = {J. Mach. Learn. Res.},
month = jan,
pages = {1455–1459},
numpages = {5},
keywords = {non convex, nonlinear programming, Riemannian optimization, rank constraints, rotation matrices, optimization with symmetries, orthogonality constraints}
}

@article{10.5555/2627435.2638580,
author = {Dubout, Charles and Fleuret, Fran\c{c}ois},
title = {Adaptive Sampling for Large Scale Boosting},
year = {2014},
issue_date = {January 2014},
publisher = {JMLR.org},
volume = {15},
number = {1},
issn = {1532-4435},
abstract = {Classical boosting algorithms, such as AdaBoost, build a strong classifier without concern for the computational cost. Some applications, in particular in computer vision, may involve millions of training examples and very large feature spaces. In such contexts, the training time of off-the-shelf boosting algorithms may become prohibitive. Several methods exist to accelerate training, typically either by sampling the features or the examples used to train the weak learners. Even if some of these methods provide a guaranteed speed improvement, they offer no insurance of being more efficient than any other, given the same amount of time.The contributions of this paper are twofold: (1) a strategy to better deal with the increasingly common case where features come from multiple sources (for example, color, shape, texture, etc., in the case of images) and therefore can be partitioned into meaningful subsets; (2) new algorithms which balance at every boosting iteration the number of weak learners and the number of training examples to look at in order to maximize the expected loss reduction. Experiments in image classification and object recognition on four standard computer vision data sets show that the adaptive methods we propose outperform basic sampling and state-of-the-art bandit methods.},
journal = {J. Mach. Learn. Res.},
month = jan,
pages = {1431–1453},
numpages = {23},
keywords = {large scale learning, feature selection, boosting}
}

@article{10.5555/2627435.2638579,
author = {Tan, Mingkui and Tsang, Ivor W. and Wang, Li},
title = {Towards Ultrahigh Dimensional Feature Selection for Big Data},
year = {2014},
issue_date = {January 2014},
publisher = {JMLR.org},
volume = {15},
number = {1},
issn = {1532-4435},
abstract = {In this paper, we present a new adaptive feature scaling scheme for ultrahigh-dimensional feature selection on Big Data, and then reformulate it as a convex semi-infinite programming (SIP) problem. To address the SIP, we propose an efficient feature generating paradigm. Different from traditional gradient-based approaches that conduct optimization on all input features, the proposed paradigm iteratively activates a group of features, and solves a sequence of multiple kernel learning (MKL) subproblems. To further speed up the training, we propose to solve the MKL subproblems in their primal forms through a modified accelerated proximal gradient approach. Due to such optimization scheme, some efficient cache techniques are also developed. The feature generating paradigm is guaranteed to converge globally under mild conditions, and can achieve lower feature selection bias. Moreover, the proposed method can tackle two challenging tasks in feature selection: 1) group-based feature selection with complex structures, and 2) nonlinear feature selection with explicit feature mappings. Comprehensive experiments on a wide range of synthetic and real-world data sets of tens of million data points with O(1014) features demonstrate the competitive performance of the proposed method over state-of-the-art feature selection methods in terms of generalization performance and training effciency.},
journal = {J. Mach. Learn. Res.},
month = jan,
pages = {1371–1429},
numpages = {59},
keywords = {multiple kernel learning, nonlinear feature selection, feature generation, ultrahigh dimensionality, feature selection, big data}
}

@article{10.5555/2627435.2638578,
author = {Wand, Matt P.},
title = {Fully Simplified Multivariate Normal Updates in Non-Conjugate Variational Message Passing},
year = {2014},
issue_date = {January 2014},
publisher = {JMLR.org},
volume = {15},
number = {1},
issn = {1532-4435},
abstract = {Fully simplified expressions for Multivariate Normal updates in non-conjugate variational message passing approximate inference schemes are obtained. The simplicity of these expressions means that the updates can be achieved very effciently. Since the Multivariate Normal family is the most common for approximating the joint posterior density function of a continuous parameter vector, these fully simplified updates are of great practical benefit.},
journal = {J. Mach. Learn. Res.},
month = jan,
pages = {1351–1369},
numpages = {19},
keywords = {Bayesian computing, graphical models, variational approximation, matrix differential calculus, mean field variational bayes}
}

@article{10.5555/2627435.2638577,
author = {Doppa, Janardhan Rao and Fern, Alan and Tadepalli, Prasad},
title = {Structured Prediction via Output Space Search},
year = {2014},
issue_date = {January 2014},
publisher = {JMLR.org},
volume = {15},
number = {1},
issn = {1532-4435},
abstract = {We consider a framework for structured prediction based on search in the space of complete structured outputs. Given a structured input, an output is produced by running a time-bounded search procedure guided by a learned cost function, and then returning the least cost output uncovered during the search. This framework can be instantiated for a wide range of search spaces and search procedures, and easily incorporates arbitrary structured-prediction loss functions. In this paper, we make two main technical contributions. First, we describe a novel approach to automatically defining an effective search space over structured outputs, which is able to leverage the availability of powerful classification learning algorithms. In particular, we define the limited-discrepancy search space and relate the quality of that space to the quality of learned classifiers. We also define a sparse version of the search space to improve the effciency of our overall approach. Second, we give a generic cost function learning approach that is applicable to a wide range of search procedures. The key idea is to learn a cost function that attempts to mimic the behavior of conducting searches guided by the true loss function. Our experiments on six benchmark domains show that a small amount of search in limited discrepancy search space is often sufficient for significantly improving on state-of-the-art structured-prediction performance. We also demonstrate significant speed improvements for our approach using sparse search spaces with little or no loss in accuracy.},
journal = {J. Mach. Learn. Res.},
month = jan,
pages = {1317–1350},
numpages = {34},
keywords = {cost function, structured prediction, state space search, imitation learning}
}

@article{10.5555/2627435.2638576,
author = {De Rooij, Steven and Van Erven, Tim and Gr\"{u}nwald, Peter D. and Koolen, Wouter M.},
title = {Follow the Leader If You Can, Hedge If You Must},
year = {2014},
issue_date = {January 2014},
publisher = {JMLR.org},
volume = {15},
number = {1},
issn = {1532-4435},
abstract = {Follow-the-Leader (FTL) is an intuitive sequential prediction strategy that guarantees constant regret in the stochastic setting, but has poor performance for worst-case data. Other hedging strategies have better worst-case guarantees but may perform much worse than FTL if the data are not maximally adversarial. We introduce the FlipFlop algorithm, which is the first method that provably combines the best of both worlds. As a stepping stone for our analysis, we develop AdaHedge, which is a new way of dynamically tuning the learning rate in Hedge without using the doubling trick. AdaHedge refines a method by Cesa-Bianchi, Mansour, and Stoltz (2007), yielding improved worst-case guarantees. By interleaving AdaHedge and FTL, FlipFlop achieves regret within a constant factor of the FTL regret, without sacrificing AdaHedge's worst-case guarantees. AdaHedge and FlipFlop do not need to know the range of the losses in advance; moreover, unlike earlier methods, both have the intuitive property that the issued weights are invariant under rescaling and translation of the losses. The losses are also allowed to be negative, in which case they may be interpreted as gains.},
journal = {J. Mach. Learn. Res.},
month = jan,
pages = {1281–1316},
numpages = {36},
keywords = {learning rate, mixability, prediction with expert advice, online learning, hedge}
}

@article{10.5555/2627435.2638575,
author = {Gillis, Nicolas and Luce, Robert},
title = {Robust Near-Separable Nonnegative Matrix Factorization Using Linear Optimization},
year = {2014},
issue_date = {January 2014},
publisher = {JMLR.org},
volume = {15},
number = {1},
issn = {1532-4435},
abstract = {Nonnegative matrix factorization (NMF) has been shown recently to be tractable under the separability assumption, under which all the columns of the input data matrix belong to the convex cone generated by only a few of these columns. Bittorf, Recht, R\'{e} and Tropp ('Factoring nonnegative matrices with linear programs', NIPS 2012) proposed a linear programming (LP) model, referred to as Hottopixx, which is robust under any small perturbation of the input matrix. However, Hottopixx has two important drawbacks: (i) the input matrix has to be normalized, and (ii) the factorization rank has to be known in advance. In this paper, we generalize Hottopixx in order to resolve these two drawbacks, that is, we propose a new LP model which does not require normalization and detects the factorization rank automatically. Moreover, the new LP model is more flexible, significantly more tolerant to noise, and can easily be adapted to handle outliers and other noise models. Finally, we show on several synthetic data sets that it outperforms Hottopixx while competing favorably with two state-of-the-art methods.},
journal = {J. Mach. Learn. Res.},
month = jan,
pages = {1249–1280},
numpages = {32},
keywords = {convex optimization, separability, linear programming, robustness to noise, hyperspectral unmixing, pure-pixel assumption, nonnegative matrix factorization}
}

@article{10.5555/2627435.2638574,
author = {Ruiz, Francisco J. R. and Valera, Isabel and Blanco, Carlos and Perez-Cruz, Fernando},
title = {Bayesian Nonparametric Comorbidity Analysis of Psychiatric Disorders},
year = {2014},
issue_date = {January 2014},
publisher = {JMLR.org},
volume = {15},
number = {1},
issn = {1532-4435},
abstract = {The analysis of comorbidity is an open and complex research field in the branch of psychiatry, where clinical experience and several studies suggest that the relation among the psychiatric disorders may have etiological and treatment implications. In this paper, we are interested in applying latent feature modeling to find the latent structure behind the psychiatric disorders that can help to examine and explain the relationships among them. To this end, we use the large amount of information collected in the National Epidemiologic Survey on Alcohol and Related Conditions (NESARC) database and propose to model these data using a nonparametric latent model based on the Indian Buffet Process (IBP). Due to the discrete nature of the data, we first need to adapt the observation model for discrete random variables. We propose a generative model in which the observations are drawn from a multinomial-logit distribution given the IBP matrix. The implementation of an effcient Gibbs sampler is accomplished using the Laplace approximation, which allows integrating out the weighting factors of the multinomial-logit likelihood model. We also provide a variational inference algorithm for this model, which provides a complementary (and less expensive in terms of computational complexity) alternative to the Gibbs sampler allowing us to deal with a larger number of data. Finally, we use the model to analyze comorbidity among the psychiatric disorders diagnosed by experts from the NESARC database.},
journal = {J. Mach. Learn. Res.},
month = jan,
pages = {1215–1247},
numpages = {33},
keywords = {Laplace approximation, variational inference, categorical observations, Indian buffet process, Bayesian nonparametrics, multinomial-logit function}
}

@article{10.5555/2627435.2638573,
author = {Chiang, Kai-Yang and Hsieh, Cho-Jui and Natarajan, Nagarajan and Dhillon, Inderjit S. and Tewari, Ambuj},
title = {Prediction and Clustering in Signed Networks: A Local to Global Perspective},
year = {2014},
issue_date = {January 2014},
publisher = {JMLR.org},
volume = {15},
number = {1},
issn = {1532-4435},
abstract = {The study of social networks is a burgeoning research area. However, most existing work is on networks that simply encode whether relationships exist or not. In contrast, relationships in signed networks can be positive ("like", "trust") or negative ("dislike", "distrust"). The theory of social balance shows that signed networks tend to conform to some local patterns that, in turn, induce certain global characteristics. In this paper, we exploit both local as well as global aspects of social balance theory for two fundamental problems in the analysis of signed networks: sign prediction and clustering. Local patterns of social balance have been used in the past for sign prediction. We define more general measures of social imbalance (MOIs) based on l-cycles in the network and give a simple sign prediction rule. Interestingly, by examining measures of social imbalance, we show that the classic Katz measure, which is used widely in unsigned link prediction, also has a balance theoretic interpretation when applied to signed networks. Motivated by the global structure of balanced networks, we propose an effective low rank modeling approach for both sign prediction and clustering. We provide theoretical performance guarantees for our low-rank matrix completion approach via convex relaxations, scale it up to large problem sizes using a matrix factorization based algorithm, and provide extensive experimental validation including comparisons with local approaches. Our experimental results indicate that, by adopting a more global viewpoint of social balance, we get significant performance and computational gains in prediction and clustering tasks on signed networks. Our work therefore highlights the usefulness of the global aspect of balance theory for the analysis of signed networks.},
journal = {J. Mach. Learn. Res.},
month = jan,
pages = {1177–1213},
numpages = {37},
keywords = {signed networks, balance theory, matrix completion, graph clustering, low rank model, sign prediction}
}

@article{10.5555/2627435.2638572,
author = {Volkovs, Maksims N. and Zemel, Richard S.},
title = {New Learning Methods for Supervised and Unsupervised Preference Aggregation},
year = {2014},
issue_date = {January 2014},
publisher = {JMLR.org},
volume = {15},
number = {1},
issn = {1532-4435},
abstract = {In this paper we present a general treatment of the preference aggregation problem, in which multiple preferences over objects must be combined into a single consensus ranking. We consider two instances of this problem: unsupervised aggregation where no information about a target ranking is available, and supervised aggregation where ground truth preferences are provided. For each problem class we develop novel learning methods that are applicable to a wide range of preference types. Specifically, for unsupervised aggregation we introduce the Multinomial Preference model (MPM) which uses a multinomial generative process to model the observed preferences. For the supervised problem we develop a supervised extension for MPM and then propose two fully supervised models. The first model employs SVD factorization to derive effective item features, transforming the aggregation problems into a learning-to-rank one. The second model aims to eliminate the costly SVD factorization and instantiates a probabilistic CRF framework, deriving unary and pairwise potentials directly from the observed preferences. Using a probabilistic framework allows us to directly optimize the expectation of any target metric, such as NDCG or ERR. All the proposed models operate on pairwise preferences and can thus be applied to a wide range of preference types. We empirically validate the models on rank aggregation and collaborative filtering data sets and demonstrate superior empirical accuracy.},
journal = {J. Mach. Learn. Res.},
month = jan,
pages = {1135–1176},
numpages = {42},
keywords = {preference aggregation, collaborative filtering, meta-search, learning-to-rank}
}

@article{10.5555/2627435.2638571,
author = {Agarwal, Alekh and Chapelle, Olivier and Dud\'{\i}k, Miroslav and Langford, John},
title = {A Reliable Effective Terascale Linear Learning System},
year = {2014},
issue_date = {January 2014},
publisher = {JMLR.org},
volume = {15},
number = {1},
issn = {1532-4435},
abstract = {We present a system and a set of techniques for learning linear predictors with convex losses on terascale data sets, with trillions of features, billions of training examples and millions of parameters in an hour using a cluster of 1000 machines. Individually none of the component techniques are new, but the careful synthesis required to obtain an efficient implementation is. The result is, up to our knowledge, the most scalable and efficient linear learning system reported in the literature. We describe and thoroughly evaluate the components of the system, showing the importance of the various design choices.},
journal = {J. Mach. Learn. Res.},
month = jan,
pages = {1111–1133},
numpages = {23},
keywords = {distributed L-BFGS, Hadoop, distributed machine learning, AllReduce, repeated online averaging}
}

@article{10.5555/2627435.2638570,
author = {Zhu, Jun and Chen, Ning and Perkins, Hugh and Zhang, Bo},
title = {Gibbs Max-Margin Topic Models with Data Augmentation},
year = {2014},
issue_date = {January 2014},
publisher = {JMLR.org},
volume = {15},
number = {1},
issn = {1532-4435},
abstract = {Max-margin learning is a powerful approach to building classifiers and structured output predictors. Recent work on max-margin supervised topic models has successfully integrated it with Bayesian topic models to discover discriminative latent semantic structures and make accurate predictions for unseen testing data. However, the resulting learning problems are usually hard to solve because of the non-smoothness of the margin loss. Existing approaches to building max-margin supervised topic models rely on an iterative procedure to solve multiple latent SVM subproblems with additional mean-field assumptions on the desired posterior distributions. This paper presents an alternative approach by defining a new max-margin loss. Namely, we present Gibbs max-margin supervised topic models, a latent variable Gibbs classifier to discover hidden topic representations for various tasks, including classification, regression and multi-task learning. Gibbs max-margin supervised topic models minimize an expected margin loss, which is an upper bound of the existing margin loss derived from an expected prediction rule. By introducing augmented variables and integrating out the Dirichlet variables analytically by conjugacy, we develop simple Gibbs sampling algorithms with no restrictive assumptions and no need to solve SVM subproblems. Furthermore, each step of the "augment-and-collapse" Gibbs sampling algorithms has an analytical conditional distribution, from which samples can be easily drawn. Experimental results on several medium-sized and large-scale data sets demonstrate significant improvements on time effciency. The classification performance is also improved over competitors on binary, multi-class and multi-label classification tasks.},
journal = {J. Mach. Learn. Res.},
month = jan,
pages = {1073–1110},
numpages = {38},
keywords = {supervised topic models, Gibbs classifiers, support vector machines, regularized Bayesian inference, max-margin learning}
}

@article{10.5555/2627435.2638569,
author = {Wade, Sara and Dunson, David B. and Petrone, Sonia and Trippa, Lorenzo},
title = {Improving Prediction from Dirichlet Process Mixtures via Enrichment},
year = {2014},
issue_date = {January 2014},
publisher = {JMLR.org},
volume = {15},
number = {1},
issn = {1532-4435},
abstract = {Flexible covariate-dependent density estimation can be achieved by modelling the joint density of the response and covariates as a Dirichlet process mixture. An appealing aspect of this approach is that computations are relatively easy. In this paper, we examine the predictive performance of these models with an increasing number of covariates. Even for a moderate number of covariates, we find that the likelihood for x tends to dominate the posterior of the latent random partition, degrading the predictive performance of the model. To overcome this, we suggest using a different nonparametric prior, namely an enriched Dirichlet process. Our proposal maintains a simple allocation rule, so that computations remain relatively simple. Advantages are shown through both predictive equations and examples, including an application to diagnosis Alzheimer's disease.},
journal = {J. Mach. Learn. Res.},
month = jan,
pages = {1041–1071},
numpages = {31},
keywords = {random partition, predictive distribution, Bayesian nonparametrics, urn scheme, density regression}
}

@article{10.5555/2627435.2638568,
author = {Mizutani, Tomohiko},
title = {Ellipsoidal Rounding for Nonnegative Matrix Factorization under Noisy Separability},
year = {2014},
issue_date = {January 2014},
publisher = {JMLR.org},
volume = {15},
number = {1},
issn = {1532-4435},
abstract = {We present a numerical algorithm for nonnegative matrix factorization (NMF) problems under noisy separability. An NMF problem under separability can be stated as one of finding all vertices of the convex hull of data points. The research interest of this paper is to find the vectors as close to the vertices as possible in a situation in which noise is added to the data points. Our algorithm is designed to capture the shape of the convex hull of data points by using its enclosing ellipsoid. We show that the algorithm has correctness and robustness properties from theoretical and practical perspectives; correctness here means that if the data points do not contain any noise, the algorithm can find the vertices of their convex hull; robustness means that if the data points contain noise, the algorithm can find the near-vertices. Finally, we apply the algorithm to document clustering, and report the experimental results.},
journal = {J. Mach. Learn. Res.},
month = jan,
pages = {1011–1039},
numpages = {29},
keywords = {enclosing ellipsoid, document clustering, separability, robustness to noise, nonnegative matrix factorization}
}

@article{10.5555/2627435.2638567,
author = {Cuong, Nguyen Viet and Ye, Nan and Lee, Wee Sun and Chieu, Hai Leong},
title = {Conditional Random Field with High-Order Dependencies for Sequence Labeling and Segmentation},
year = {2014},
issue_date = {January 2014},
publisher = {JMLR.org},
volume = {15},
number = {1},
issn = {1532-4435},
abstract = {Dependencies among neighboring labels in a sequence are important sources of information for sequence labeling and segmentation. However, only first-order dependencies, which are dependencies between adjacent labels or segments, are commonly exploited in practice because of the high computational complexity of typical inference algorithms when longer distance dependencies are taken into account. In this paper, we give effcient inference algorithms to handle high-order dependencies between labels or segments in conditional random fields, under the assumption that the number of distinct label patterns used in the features is small. This leads to effcient learning algorithms for these conditional random fields. We show experimentally that exploiting high-order dependencies can lead to substantial performance improvements for some problems, and we discuss conditions under which high-order features can be effective.},
journal = {J. Mach. Learn. Res.},
month = jan,
pages = {981–1009},
numpages = {29},
keywords = {sequence labeling, segmentation, label sparsity, semi-Markov conditional random field, high-order feature, conditional random field}
}

@article{10.5555/2627435.2638566,
author = {Wierstra, Daan and Schaul, Tom and Glasmachers, Tobias and Sun, Yi and Peters, Jan and Schmidhuber, J\"{u}rgen},
title = {Natural Evolution Strategies},
year = {2014},
issue_date = {January 2014},
publisher = {JMLR.org},
volume = {15},
number = {1},
issn = {1532-4435},
abstract = {This paper presents Natural Evolution Strategies (NES), a recent family of black-box optimization algorithms that use the natural gradient to update a parameterized search distribution in the direction of higher expected fitness. We introduce a collection of techniques that address issues of convergence, robustness, sample complexity, computational complexity and sensitivity to hyperparameters. This paper explores a number of implementations of the NES family, such as general-purpose multi-variate normal distributions and separable distributions tailored towards search in high dimensional spaces. Experimental results show best published performance on various standard benchmarks, as well as competitive performance on others.},
journal = {J. Mach. Learn. Res.},
month = jan,
pages = {949–980},
numpages = {32},
keywords = {evolution strategies, black-box optimization, sampling, natural gradient, stochastic search}
}

@article{10.5555/2627435.2638565,
author = {Sprekeler, Henning and Zito, Tiziano and Wiskott, Laurenz},
title = {An Extension of Slow Feature Analysis for Nonlinear Blind Source Separation},
year = {2014},
issue_date = {January 2014},
publisher = {JMLR.org},
volume = {15},
number = {1},
issn = {1532-4435},
abstract = {We present and test an extension of slow feature analysis as a novel approach to nonlinear blind source separation. The algorithm relies on temporal correlations and iteratively reconstructs a set of statistically independent sources from arbitrary nonlinear instantaneous mixtures. Simulations show that it is able to invert a complicated nonlinear mixture of two audio signals with a high reliability. The algorithm is based on a mathematical analysis of slow feature analysis for the case of input data that are generated from statistically independent sources.},
journal = {J. Mach. Learn. Res.},
month = jan,
pages = {921–947},
numpages = {27},
keywords = {nonlinear blind source separation, slow feature analysis, slowness principle, statistical independence, independent component analysis}
}

@article{10.5555/2627435.2638564,
author = {Ailon, Nir and Begleiter, Ron and Ezra, Esther},
title = {Active Learning Using Smooth Relative Regret Approximations with Applications},
year = {2014},
issue_date = {January 2014},
publisher = {JMLR.org},
volume = {15},
number = {1},
issn = {1532-4435},
abstract = {The disagreement coeffcient of Hanneke has become a central data independent invariant in proving active learning rates. It has been shown in various ways that a concept class with low complexity together with a bound on the disagreement coeffcient at an optimal solution allows active learning rates that are superior to passive learning ones.We present a different tool for pool based active learning which follows from the existence of a certain uniform version of low disagreement coeffcient, but is not equivalent to it. In fact, we present two fundamental active learning problems of significant interest for which our approach allows nontrivial active learning bounds. However, any general purpose method relying on the disagreement coeffcient bounds only, fails to guarantee any useful bounds for these problems. The applications of interest are: Learning to rank from pairwise preferences, and clustering with side information (a.k.a. semi-supervised clustering).The tool we use is based on the learner's ability to compute an estimator of the difference between the loss of any hypothesis and some fixed "pivotal" hypothesis to within an absolute error of at most ε times the disagreement measure (l1 distance) between the two hypotheses. We prove that such an estimator implies the existence of a learning algorithm which, at each iteration, reduces its in-class excess risk to within a constant factor. Each iteration replaces the current pivotal hypothesis with the minimizer of the estimated loss difference function with respect to the previous pivotal hypothesis. The label complexity essentially becomes that of computing this estimator.},
journal = {J. Mach. Learn. Res.},
month = jan,
pages = {885–920},
numpages = {36},
keywords = {learning to rank from pairwise preferences, semi-supervised clustering, smooth relative regret approximation, active learning, clustering with side information, disagreement coeffcient}
}

@article{10.5555/2627435.2638563,
author = {Dann, Christoph and Neumann, Gerhard and Peters, Jan},
title = {Policy Evaluation with Temp

license_type: permissive

branch_name: refs/heads/main

extension: bib