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