Systems | Information | Learning | Optimization

A Well-Tempered Landscape for Non-convex Robust Subspace Recovery & Adaptive Sampling for Coarse Ranking

We present a mathematical analysis of a non-convex energy landscape for Robust Subspace Recovery. Under a deterministic condition, the only stationary point in a large neighborhood of an underlying subspace is the subspace itself. The same deterministic condition implies that a geodesic gradient descent method can exactly recover the underlying subspace with proper initialization. The condition is shown to hold with high probability for a certain statistical model of data.

Joint work with Teng Zhang and Gilad Lerman.

We consider the problem of sequential coarse ranking, where the goal is to sort items according to their means into clusters of pre-specified sizes, by adaptively sampling from their reward distributions. This setting is useful in many social science applications, where an approximate rank of every item is desired. In contrast, a complete ranking of the items requires a large number of samples if the means are close, while only finding the top few items as is done in recommender systems reveals no information about the ranks of other items. We propose a computationally efficient PAC algorithm LUCBRank to solve this problem, and derive an upper bound on its sample complexity. We also derive a nearly matching distribution-dependent lower bound. Experiments on synthetic as well as real-world data arising from assessing the safety scores of street view images show that LUCBRank performs better than state-of-the-art baseline methods, even when these methods have the advantage of knowing the underlying parametric model.

February 21 @ 12:30
12:30 pm (1h)

Discovery Building, Orchard View Room

Sumeet Katariya, Tyler Maunu