Primal-dual subgradient methods for minimizing uniformly convex functions
arXiv:1401.1792
Abstract
We discuss non-Euclidean deterministic and stochastic algorithms for optimization problems with strongly and uniformly convex objectives. We provide accuracy bounds for the performance of these algorithms and design methods which are adaptive with respect to the parameters of strong or uniform convexity of the objective: in the case when the total number of iterations is fixed, their accuracy coincides, up to a logarithmic in factor with the accuracy of optimal algorithms.
Cited by in corpus (18)
- Competing with the Empirical Risk Minimizer in a Single Pass
- Optimal Algorithms for Distributed Optimization
- Scaling Limit: Exact and Tractable Analysis of Online Learning Algorithms with Applications to Regularized Regression and PCA
- A Generic Acceleration Framework for Stochastic Composite Optimization
- Stochastic Intermediate Gradient Method for Convex Problems with Inexact Stochastic Oracle
- Noise-adaptive Margin-based Active Learning and Lower Bounds under Tsybakov Noise Condition
- O(logT) Projections for Stochastic Optimization of Smooth and Strongly Convex Functions
- Local Minimax Complexity of Stochastic Convex Optimization
- Safe Grid Search with Optimal Complexity
- On Landscape of Lagrangian Functions and Stochastic Search for Constrained Nonconvex Optimization
- Local and Global Uniform Convexity Conditions
- An adaptive stochastic optimization algorithm for resource allocation
- Exploiting Smoothness in Statistical Learning, Sequential Prediction, and Stochastic Optimization
- Efficient numerical algorithms for regularized regression problem with applications to traffic matrix estimations
- Fast Gradient Methods for Uniformly Convex and Weakly Smooth Problems
- Adapting to Function Difficulty and Growth Conditions in Private Optimization
- Constant Time EXPected Similarity Estimation using Stochastic Optimization
- Multistep stochastic mirror descent for risk-averse convex stochastic programs based on extended polyhedral risk measures