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 (23)
- Making Gradient Descent Optimal for Strongly Convex Stochastic Optimization
- 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
- Stochastic Block Mirror Descent Methods for Nonsmooth and Stochastic Optimization
- 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
- On Stochastic Subgradient Mirror-Descent Algorithm with Weighted Averaging
- An adaptive stochastic optimization algorithm for resource allocation
- Efficient numerical algorithms for regularized regression problem with applications to traffic matrix estimations
- Fast Gradient Methods for Uniformly Convex and Weakly Smooth Problems
- Exploiting Smoothness in Statistical Learning, Sequential Prediction, and Stochastic Optimization
- Information-theoretic lower bounds on the oracle complexity of stochastic convex optimization
- Adapting to Function Difficulty and Growth Conditions in Private Optimization
- Optimal rates for first-order stochastic convex optimization under Tsybakov noise condition
- Constant Time EXPected Similarity Estimation using Stochastic Optimization
- Multistep stochastic mirror descent for risk-averse convex stochastic programs based on extended polyhedral risk measures