2024/06/18 by Haoyuan Cai, Cai, Haoyuan, Sulaiman A. Alghunaim +3 · 2 citations
Computer Science · #FOS: Computer and information sciences #FOS: Mathematics #Machine Learning (cs.LG) #Metaheuristic Optimization Algorithms Research #Optimization and Control (math.OC)
paper · pdf · doi:10.48550/arxiv.2406.13041
openalex publication_date 2024/06/18 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
Lower-bound analyses for nonconvex strongly-concave minimax optimization problems have shown that stochastic first-order algorithms require at least O(ε-4) sample complexity to find an ε-stationary point. Some works indicate that this complexity can be improved to O(ε-3) when the stochastic loss gradient is Lipschitz continuous. The question of achieving enhanced convergence rates under distinct conditions, remains open. In this work, we address this question for optimization problems that are nonconvex in the minimization variable and strongly concave or Polyak-Lojasiewicz (PL) in the maximization variable. We introduce novel bias-corrected momentum algorithms utilizing efficient Hessian-vector products. We establish convergence conditions and demonstrate a lower iteration complexity of O(ε-3) for the proposed algorithms. The effectiveness of the proposed method is validated through applications to robust logistic regression and robust adaptive cruise control.