A Practical and Provable Algorithm for Subspace Clustering

1. Introduction Traditional distance based clustering algorithms such as K-Means perform poorly on high dimensional data because of curse of dimensionality[1]. A common approach to cluster such data is to assume that even though their ambient dimensionality is high, their intrinsic dimensionality is much lower. As an example, consider the dataset of images of faces… Continue reading A Practical and Provable Algorithm for Subspace Clustering

Second Order Regret Bounds Parametrized By Variance Across Actions And Top Epsilon Percentile

Second order regret bounds parametrized by variance across actions and top percentile This blog will describe an open problem posted by Yoav Freund[1]. We’ll introduce the problem setting and an overview of regret bounds in section 1. In section 2, we’ll define variance across actions and how it comes into play. Then we’ll introduce percentile… Continue reading Second Order Regret Bounds Parametrized By Variance Across Actions And Top Epsilon Percentile

Efficiently Learning Ising Models on Arbitrary Graphs [STOC’15]

The paper [1] presented in this blog is from Professor Guy Bresler at Massachusetts Institute of Technology. It was originally presented at the 47th Annual Symposium on the Theory of Computing (STOC, 2015). The paper mainly talks about how to reconstruct a graph with an Ising model given i.i.d data samples. Without any restrictive constraints… Continue reading Efficiently Learning Ising Models on Arbitrary Graphs [STOC’15]