Fast Rates of ERM and Stochastic Approximation: Adaptive to Error Bound Conditions

Abstract

Error bound conditions (EBC) are properties that characterize the growth of an objective function when a point is moved away from the optimal set. They have recently received increasing attention in the field of optimization for developing optimization algorithms with fast convergence. However, the studies of EBC in statistical learning are hitherto still limited. The main contributions of this paper are two-fold. First, we develop fast and intermediate rates of empirical risk minimization (ERM) under EBC for risk minimization with Lipschitz continuous, and smooth convex random functions. Second, we establish fast and intermediate rates of an efficient stochastic approximation (SA) algorithm for risk minimization with Lipschitz continuous random functions, which requires only one pass of $n$ samples and adapts to EBC. For both approaches, the convergence rates span a full spectrum between $\tilde{O}(1/\sqrt{n})$ and $\tilde{O}(1/n)$ depending on the power constant in EBC, and could be even faster than $O(1/n)$ in special cases for ERM. Moreover, these convergence rates are automatically adaptive without using any knowledge of EBC. Overall, this work not only strengthens the understanding of ERM for statistical learning but also brings new fast stochastic algorithms for solving a broad range of statistical learning problems.

References in corpus (9)

• Making Gradient Descent Optimal for Strongly Convex Stochastic Optimization
• Stochastic Gradient Descent for Non-smooth Optimization: Convergence Results and Optimal Averaging Schemes
• 2004 IMS Medallion Lecture: Local Rademacher complexities and oracle inequalities in risk minimization
• Optimistic Rates for Learning with a Smooth Loss
• RSG: Beating Subgradient Method without Smoothness and Strong Convexity
• Combining Adversarial Guarantees and Stochastic Fast Rates in Online Learning
• Generalization of ERM in Stochastic Convex Optimization: The Dimension Strikes Back
• New Analysis of Linear Convergence of Gradient-type Methods via Unifying Error Bound Conditions
• Excess Risk Bounds for Exponentially Concave Losses