Accelerated Methods for α-Weakly-Quasi-Convex Problems

2017/10/02 by Sergey Guminov, Guminov, Sergey, Alexander Gasnikov +3 · 6 citations
Computer Science · Engineering · Mathematics · #Advanced Optimization Algorithms Research #FOS: Mathematics #Machine Learning and ELM #Optimization and Control (math.OC) #Optimization and Variational Analysis #Sparse and Compressive Sensing Techniques #Stochastic Gradient Optimization Techniques

paper · pdf · doi:10.48550/arxiv.1710.00797

openalex publication_date 2017/10/02 · openalex created_date 2022/10/03 · openalex updated_date 2026/07/28

Abstract

We provide a quick overview of the class of α-weakly-quasi-convex problems and its relationships with other problem classes. We show that the previously known Sequential Subspace Optimization method retains its optimal convergence rate when applied to minimization problems with smooth α-weakly-quasi-convex objectives. We also show that Nemirovski's conjugate gradients method of strongly convex minimization achieves its optimal convergence rate under weaker conditions of α-weak-quasi-convexity and quad\-ratic growth. Previously known results only capture the special case of 1-weak-quasi-convexity or give convergence rates with worse dependence on the parameter α.

Cited by

• Mirror Descent Methods for Quasar Convex Optimization Problems With Non-Smooth Inequality Constraints
• Continuized Nesterov Acceleration for Non-Convex Optimization
• Star Quasiconvexity: an Unified Approach for Linear Convergence of First-Order Methods Beyond Convexity
• Adaptive Conditional Gradient Descent
• Smooth Quasar-Convex Optimization with Constraints
• Extending Linear Convergence of the Proximal Point Algorithm: The Quasar-Convex Case

Related

• On Some Versions of Subspace Optimization Methods with Inexact Gradient Information
• A Note on Nesterov's Accelerated Method in Nonconvex Optimization: a Weak Estimate Sequence Approach
• Convergence Rates of Subgradient Methods for Quasi-convex Optimization Problems
• A Practical Approach to Quasi-convex Optimization
• Linear convergence of first order methods for non-strongly convex optimization