A New Complexity Result for Strongly Convex Optimization with Locally α-Hölder Continuous Gradients

2025/05/06 by Xiaojun Chen, C. T. Kelley, Chen, Xiaojun +2
Computer Science · Engineering · Mathematics · #Advanced Optimization Algorithms Research #FOS: Mathematics #Optimization and Control (math.OC) #Optimization and Variational Analysis #Sparse and Compressive Sensing Techniques

paper · pdf · doi:10.48550/arxiv.2505.03506

openalex publication_date 2025/05/06 · openalex created_date 2025/10/16 · openalex updated_date 2026/07/28

Abstract

In this paper, we present a new complexity result for the gradient descent method with an appropriately fixed stepsize for minimizing a strongly convex function with locally α-Hölder continuous gradients (0 < α≤ 1). The complexity bound for finding an approximate minimizer with a distance to the true minimizer less than ε is O(log (ε^-1) ε^{2 α- 2}), which extends the well-known complexity result for α= 1.

Citations

• Bundle-Level Type Methods Uniformly Optimal for Smooth and Nonsmooth Convex Optimization
• First-order methods of smooth convex optimization with inexact oracle

Related

• On the worst-case complexity of the gradient method with exact line search for smooth strongly convex functions
• An optimal gradient method for smooth strongly convex minimization
• Accelerated Gradient Algorithms with Adaptive Subspace Search for Instance-Faster Optimization
• Accelerated first-order methods for large-scale convex minimization
• Lower bounds for conditional gradient type methods for minimizing smooth strongly convex functions