Before revision:  In fact our algorithms succeed where convex surrogates failin the sense that we show strong lower bounds for the existing approaches .
After revision:  In fact our algorithms succeed where conventional methods fail. In particular we show strong lower bounds for the existing approaches .