Local and Global Uniform Convexity Conditions
arXiv:2102.05134
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 \textit{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.
References in corpus (21)
- Local SGD Converges Fast and Communicates Little
- A Unified Analysis of Extra-gradient and Optimistic Gradient Methods for Saddle Point Problems: Proximal Point Approach
- Faster Rates for the Frank-Wolfe Method over Strongly-Convex Sets
- The Complexity of Large-scale Convex Programming under a Linear Optimization Oracle
- Adding vs. Averaging in Distributed Primal-Dual Optimization
- On the Universality of Online Mirror Descent
- Primal-dual subgradient methods for minimizing uniformly convex functions
- Algorithmic stability and hypothesis complexity
- Last-iterate convergence rates for min-max optimization
- Private Empirical Risk Minimization Beyond the Worst Case: The Effect of the Constraint Set Geometry
- Acceleration through Optimistic No-Regret Dynamics
- Differentially Private Accelerated Optimization Algorithms
- Following the Leader and Fast Rates in Linear Prediction: Curved Constraint Sets and Other Regularities
- Projection-Free Optimization on Uniformly Convex Sets
- Curvature of Feasible Sets in Offline and Online Optimization
- An Approximate Shapley-Folkman Theorem
- On the Effectiveness of Richardson Extrapolation in Machine Learning
- Affine Invariant Analysis of Frank-Wolfe on Strongly Convex Sets
- Differentially Private Empirical Risk Minimization with Sparsity-Inducing Norms
- Generalization Bounds in the Predict-then-Optimize Framework
- On the Rademacher Complexity of Linear Hypothesis Sets