Frank-Wolfe on Uniformly Convex Sets.

TITLE: Local and Global Uniform Convexity Conditions.

AUTHORS: Thomas Kerdreux, Alexandre d'Aspremont, Sebastian Pokutta.

ABSTRACT: We review various characterizations of uniform convexity and smoothness on norm balls in finite-dimensional spaces and connect results stemming from the geometry of Banach spaces with scaling inequalities used in analyzing the convergence of optimization methods. In particular, we establish local versions of these conditions to provide sharper insights on a recent body of complexity results in learning theory, online learning, or offline optimization, which rely on the strong convexity of the feasible set. While they have a significant impact on complexity, these strong convexity or uniform convexity properties of feasible sets are not exploited as thoroughly as their functional counterparts, and this work is an effort to correct this imbalance. We conclude with some practical examples in optimization and machine learning where leveraging these conditions and localized assumptions lead to new complexity results.

STATUS: Preprint.

ArXiv PREPRINT: 2102.05134