Distance-based approaches to outlier detection are popular in data mining, as they do not require to model the underlying probability distribution, which is particularly challenging for high-dimensional data. We present an empirical comparison of various approaches to distance-based outlier detection across a large number of datasets. We report the surprising observation that a simple, sampling-based scheme outperforms state-of-the-art techniques in terms of both efficiency and effectiveness. To better understand this phenomenon, we provide a theoretical analysis why the sampling-based approach outperforms alternative methods based on k-nearest neighbor search.

In this paper, we study the problem of estimating the cluster tree of a density when the density is supported on or near a manifold.

We study the problem of estimating continuous quantities, such as prices, probabilities, and point spreads, using a crowdsourcing approach. A challenging aspect of combining the crowd's answers is that workers' reliabilities and biases are usually unknown and highly diverse. Control items with known answers can be used to evaluate workers' performance, and hence improve the combined results on the target items with unknown answers. This raises the problem of how many control items to use when the total number of items each workers can answer is limited: more control items evaluates the workers better, but leaves fewer resources for the target items that are of direct interest, and vice versa. We give theoretical results for this problem under different scenarios, and provide a simple rule of thumb for crowdsourcing practitioners. As a byproduct, we also provide theoretical analysis of the accuracy of different consensus methods.

We study in this paper flat and hierarchical classification strategies in the context of large-scale taxonomies. To this end, we first propose a multiclass, hierarchical data dependent bound on the generalization error of classifiers deployed in large-scale taxonomies. This bound provides an explanation to several empirical results reported in the literature, related to the performance of flat and hierarchical classifiers. We then introduce another type of bound targeting the approximation error of a family of classifiers, and derive from it features used in a meta-classifier to decide which nodes to prune (or flatten) in a large-scale taxonomy. We finally illustrate the theoretical developments through several experiments conducted on two widely used taxonomies.

Alternatively, if the algorithm performs well against any of the existing AC ones then it would be good to see its performance in various settings and detailed explanation of its properties. The latter would be useful in its own right whether or not it is related to summarizing posterior distribution's characteristics. A few specific comments: Line 19: It is correct to say that the MAP might not be good in situations where the posterior is diffuse, I guess you mean uniform-like? It might also be multimodal, skewed (mode and mean differ), high variance,for example, so the MAP is not necessarily a good choice although it depends on the (underlying) loss function. Line 52: Since a Dirichlet Process is a discrete random probability measure, when sampling from it it induces a random partition (the ties will belong to the same cluster).

Infinite mixture models are commonly used for clustering. One can sample from the posterior of mixture assignments by Monte Carlo methods or find its maximum a posteriori solution by optimization. However, in some problems the posterior is diffuse and it is hard to interpret the sampled partitionings. In this paper, we introduce novel statistics based on block sizes for representing sample sets of partitionings and feature allocations. We develop an element-based definition of entropy to quantify segmentation among their elements. Then we propose a simple algorithm called entropy agglomeration (EA) to summarize and visualize this information. Experiments on various infinite mixture posteriors as well as a feature allocation dataset demonstrate that the proposed statistics are useful in practice.

Convergence properties and relation to stochastic gradient descent have been discussed. Overall, this paper is not well written and should not be accepted in the current form. All theoretical analyses are based on the potential functions defined in line 109-111. There is no citation for this potential function and it is not explained why this function is defined in this form. Using the norm of the difference between v_n and the optimal first principal component is a more standard way to analyse the convergence rate.

Two classical such schemes are due to Krasulina (1969) and Oja (1983). We give finite-sample convergence rates for both.

We give differentially private algorithms for a large class of online learning algorithms, in both the full information and bandit settings. Our algorithms aim to minimize a convex loss function which is a sum of smaller convex loss terms, one for each data point. To design our algorithms, we modify the popular mirror descent approach, or rather a variant called follow the approximate leader. The technique leads to the first nonprivate algorithms for private online learning in the bandit setting. In the full information setting, our algorithms improve over the regret bounds of previous work (due to Dwork, Naor, Pitassi and Rothblum (2010) and Jain, Kothari and Thakurta (2012)). In many cases, our algorithms (in both settings) match the dependence on the input length, T, of the optimal nonprivate regret bounds up to logarithmic factors in T. Our algorithms require logarithmic space and update time.

This paper addresses the problem of identifying the type of each agents from his/her partial preference data, in order to use this information to better estimate the underlying preferences for each type. The authors propose a Generalized RUM to model the behavior of such clustered agents. A reversible jump MCMC technique is used to estimate the latent variables, including the types of the agents. A theoretical analysis of the identifiability of the model and uni-modality of the likelihood posterior are presented. Quality There are three contributions of this paper.