License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.FSTTCS.2015.1
URN: urn:nbn:de:0030-drops-56647
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2015/5664/
Go to the corresponding LIPIcs Volume Portal

Charikar, Moses S.

Bypassing Worst Case Analysis: Tensor Decomposition and Clustering (Invited Talk)

pdf-format:
50.pdf (0.2 MB)

Abstract

Typical worst case analysis of algorithms has led to a rich theory, but suffers from many pitfalls.
This has inspired several approaches to bypass worst case analysis.
In this talk, I will describe two vignettes from recent work in this realm.

In the first part of the talk, I will discuss tensor decomposition -- a natural higher dimensional analog of matrix decomposition.
Low rank tensor decompositions have proved to be a powerful tool for learning generative models, and uniqueness results give them a significant advantage over matrix decomposition methods. Yet, they pose significant challenges for algorithm design as most problems about tensors
are NP-hard. I will discuss a smoothed analysis framework for analyzing algorithms for tensor decomposition which models realistic instances of learning problems and allows us to overcome many of the usual limitations of using tensor methods.

In the second part of the talk, I will explore the phenomenon of convex relaxations returning integer solutions. Clearly this is not true in the worst case. I will discuss instances of discrete optimization problems where, for a suitable distribution on inputs, LP and SDP relaxations produce integer solutions with high probability. This has been studied in the context of LP decoding, sparse recovery, stochastic block models and so on. I will mention some recent results for clustering problems: when points are drawn from a distribution over k sufficiently separated clusters, the well known k-median relaxation and a (not so well known) SDP relaxation for k-means exactly recover the clusters.

BibTeX - Entry

@InProceedings{charikar:LIPIcs:2015:5664,
  author =	{Moses S. Charikar},
  title =	{{Bypassing Worst Case Analysis: Tensor Decomposition and Clustering (Invited Talk)}},
  booktitle =	{35th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2015)},
  pages =	{1--1},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-97-2},
  ISSN =	{1868-8969},
  year =	{2015},
  volume =	{45},
  editor =	{Prahladh Harsha and G. Ramalingam},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2015/5664},
  URN =		{urn:nbn:de:0030-drops-56647},
  doi =		{10.4230/LIPIcs.FSTTCS.2015.1},
  annote =	{Keywords: tensor decomposition, smoothed analysis, convex relaxations, integrality}
}

Keywords: tensor decomposition, smoothed analysis, convex relaxations, integrality
Collection: 35th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2015)
Issue Date: 2015
Date of publication: 14.12.2015

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI