TY - CHAP A1 - Kerdreux, Thomas A1 - d'Aspremont, Alexandre A1 - Pokutta, Sebastian T1 - Projection-Free Optimization on Uniformly Convex Sets T2 - To Appear in Proceedings of AISTATS Y1 - 2020 ER - TY - JOUR A1 - Kerdreux, Thomas A1 - d'Aspremont, Alexandre A1 - Pokutta, Sebastian T1 - Local and Global Uniform Convexity Conditions N2 - 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 analysing 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. Y1 - 2021 ER - TY - JOUR A1 - Kerdreux, Thomas A1 - Roux, Christophe A1 - d'Aspremont, Alexandre A1 - Pokutta, Sebastian T1 - Linear Bandits on Uniformly Convex Sets JF - Journal of Machine Learning Research N2 - Linear bandit algorithms yield O~(n√T) pseudo-regret bounds on compact convex action sets K⊂Rn and two types of structural assumptions lead to better pseudo-regret bounds. When K is the simplex or an ℓp ball with p∈]1,2], there exist bandits algorithms with O~(√n√T) pseudo-regret bounds. Here, we derive bandit algorithms for some strongly convex sets beyond ℓp balls that enjoy pseudo-regret bounds of O~(√n√T), which answers an open question from [BCB12, §5.5.]. Interestingly, when the action set is uniformly convex but not necessarily strongly convex, we obtain pseudo-regret bounds with a dimension dependency smaller than O(√n). However, this comes at the expense of asymptotic rates in T varying between O(√T) and O(T). Y1 - 2021 UR - https://www.jmlr.org/papers/v22/21-0277.html VL - 22 IS - 284 SP - 1 EP - 23 ER -