We review various characterizations of uniform convexity and smoothness on norm balls in finite-dimensional spaces and connect results 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 into a recent body of complexity results in learning theory, online learning, and offline optimization, which rely on the strong convexity of the feasible set. While these properties have a significant impact on complexity, the strong or uniform convexity of feasible sets is not exploited as thoroughly as their functional counterparts, and this work is an effort to correct this imbalance. We conclude with practical examples in optimization and machine learning where leveraging these conditions and localized assumptions leads to new complexity results.

错误:搜索内容不能为空,请输入英文关键词
错误:关键词超出字数限制,请精简
高级检索

Local and Global Uniform Convexity Conditions

  • Thomas Kerdreux,
  • Alexandre d’ Aspremont,
  • Sebastian Pokutta

摘要

We review various characterizations of uniform convexity and smoothness on norm balls in finite-dimensional spaces and connect results 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 into a recent body of complexity results in learning theory, online learning, and offline optimization, which rely on the strong convexity of the feasible set. While these properties have a significant impact on complexity, the strong or uniform convexity of feasible sets is not exploited as thoroughly as their functional counterparts, and this work is an effort to correct this imbalance. We conclude with practical examples in optimization and machine learning where leveraging these conditions and localized assumptions leads to new complexity results.