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 NPhard. 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 kmedian relaxation and a (not so well known) SDP relaxation for kmeans 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 = {11},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783939897972},
ISSN = {18688969},
year = {2015},
volume = {45},
editor = {Prahladh Harsha and G. Ramalingam},
publisher = {Schloss DagstuhlLeibnizZentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2015/5664},
URN = {urn:nbn:de:0030drops56647},
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 