Tightness of Convex Relaxations to Sparsity and Rank

Wednesday, February 25, 2015 - 2:00pm - 2:50pm
Keller 3-180
Nathan (Nati) Srebro (Technion-Israel Institute of Technology)
I will first present the k-support norm, which is the tightest convex
relaxation of sparsity combined with an ell-2 penalty. In
particular, the k-support norm is strictly tighter then relaxing
sparsity to L1 as in the elastic net, and allows us to study the
looseness of the elastic net relaxation. I will also discuss
tightness of convex relaxations to the rank, establishing that the
max-norm is tighter then the trace-norm, though possibly not the
MSC Code: