Workshop
Bounds on the weight margin
- Philipp Reichenbach (TU Berlin, Berlin, Germany)
Abstract
In his talk Peter Bürgisser introduced the "weight margin" of a representation. Moreover, he presented a second order algorithm for non-commutative optimization and the weight margin is the crucial complexity measure for this algorithm. Namely, the running time depends inversely on the weight margin.
In this talk we present bounds on the weight margin for concrete examples, including actions on quivers and on 3-order tensors. Thereby we will encounter inverse polynomial lower bounds for some examples as well as inverse (sub)exponential upper bounds for others. Thus, we exhibit situations in which the second order algorithm has polynomial respectively at best (sub)exponential running time.
This is joint work with Cole Franks.
