Cover Image

Solving Convex-Concave Problems with $\tilde{\mathcal{O}}(ε^{-4/7})$ Second-Order Oracle Complexity

Fuente: arXiv

Saved in:

Bibliographic Details
Main Authors:	Chen, Lesi, Liu, Chengchang, Luo, Luo, Zhang, Jingzhao
Format:	Preprint
Published:	2025
Subjects:	Optimization and Control Machine Learning
Online Access:	Acceder al recurso
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

Solving Convex-Concave Problems with $\tilde{\mathcal{O}}(ε^{-4/(3p+1)})$ $p$th-Order Oracle Complexity
by: Chen, Lesi, et al.
Published: (2026)

Second-Order Min-Max Optimization with Lazy Hessians
by: Chen, Lesi, et al.
Published: (2024)

Faster Newton Methods for Convex and Nonconvex Optimization in Gradient Complexity
by: Chen, Lesi, et al.
Published: (2025)

Functionally Constrained Algorithm Solves Convex Simple Bilevel Problems
by: Zhang, Huaqing, et al.
Published: (2024)

An Efficient Stochastic Algorithm for Decentralized Nonconvex-Strongly-Concave Minimax Optimization
by: Chen, Lesi, et al.
Published: (2022)

On the Condition Number Dependency in Bilevel Optimization
by: Chen, Lesi, et al.
Published: (2025)

On Finding Small Hyper-Gradients in Bilevel Optimization: Hardness Results and Improved Analysis
by: Chen, Lesi, et al.
Published: (2023)

Second-Order Bilevel Optimization with Accelerated Convergence Rates
by: Yang, Sheng, et al.
Published: (2026)

Faster Gradient Methods for Highly-Smooth Stochastic Bilevel Optimization
by: Chen, Lesi, et al.
Published: (2025)

On the Complexity of Decentralized Smooth Nonconvex Finite-Sum Optimization
by: Luo, Luo, et al.
Published: (2022)

A Parameter-Free First-Order Algorithm for Non-Convex Optimization with $\tilde{\mkern1mu O}(ε^{-5/3})$ Global Rate
by: Xiong, Sichao, et al.
Published: (2026)

Faster Stochastic Algorithms for Minimax Optimization under Polyak--Łojasiewicz Conditions
by: Chen, Lesi, et al.
Published: (2023)

Faster Gradient-Free Algorithms for Nonsmooth Nonconvex Stochastic Optimization
by: Chen, Lesi, et al.
Published: (2023)

Incremental Gauss--Newton Methods with Superlinear Convergence Rates
by: Zhou, Zhiling, et al.
Published: (2024)

Lower Complexity Bounds for Nonconvex-Strongly-Convex Bilevel Optimization with First-Order Oracles
by: Ji, Kaiyi
Published: (2025)

Beyond $\tilde{O}(\sqrt{T})$ Constraint Violation for Online Convex Optimization with Adversarial Constraints
by: Sinha, Abhishek, et al.
Published: (2025)

A Fully Parameter-Free Second-Order Algorithm for Convex-Concave Minimax Problems
by: Wang, Junlin, et al.
Published: (2024)

A Single-Loop Smoothed Gradient Descent-Ascent Algorithm for Nonconvex-Concave Min-Max Problems
by: Zhang, Jiawei, et al.
Published: (2020)

Near-Optimal Distributed Minimax Optimization under the Second-Order Similarity
by: Zhou, Qihao, et al.
Published: (2024)

A Modular Algorithm for Non-Stationary Online Convex-Concave Optimization
by: Meng, Qing-xin, et al.
Published: (2025)

Online Convex Optimization with a Separation Oracle
by: Mhammedi, Zakaria
Published: (2024)

Solving the Offline and Online Min-Max Problem of Non-smooth Submodular-Concave Functions: A Zeroth-Order Approach
by: Farzin, Amir Ali, et al.
Published: (2026)

Morphological Perceptron with Competitive Layer: Training Using Convex-Concave Procedure
by: Cunha, Iara, et al.
Published: (2025)

Gradient Norm Regularization Second-Order Algorithms for Solving Nonconvex-Strongly Concave Minimax Problems
by: Wang, Jun-Lin, et al.
Published: (2024)

Learning-Augmented Algorithms for Online Concave Packing and Convex Covering Problems
by: Grigorescu, Elena, et al.
Published: (2024)

Negative Momentum for Convex-Concave Optimization
by: Shugart, Henry, et al.
Published: (2026)

On Gradient Descent Ascent for Nonconvex-Concave Minimax Problems
by: Lin, Tianyi, et al.
Published: (2019)

More Optimal Fractional-Order Stochastic Gradient Descent for Non-Convex Optimization Problems
by: Partohaghighi, Mohammad, et al.
Published: (2025)

Effective Dimension Aware Fractional-Order Stochastic Gradient Descent for Convex Optimization Problems
by: Partohaghighi, Mohammad, et al.
Published: (2025)

Completely Parameter-Free Single-Loop Algorithms for Nonconvex-Concave Minimax Problems
by: Yang, Junnan, et al.
Published: (2024)

Solving 0-1 Integer Programs with Unknown Knapsack Constraints Using Membership Oracles
by: Messana, Rosario, et al.
Published: (2024)

Minimisation of Quasar-Convex Functions Using Random Zeroth-Order Oracles
by: Farzin, Amir Ali, et al.
Published: (2025)

Convex Relaxation for Solving Large-Margin Classifiers in Hyperbolic Space
by: Yang, Sheng, et al.
Published: (2024)

On Linear Convergence in Smooth Convex-Concave Bilinearly-Coupled Saddle-Point Optimization: Lower Bounds and Optimal Algorithms
by: Kovalev, Dmitry, et al.
Published: (2024)

Derivative-free Alternating Projection Algorithms for General Nonconvex-Concave Minimax Problems
by: Xu, Zi, et al.
Published: (2021)

Damped Proximal Augmented Lagrangian Method for weakly-Convex Problems with Convex Constraints
by: Dahal, Hari, et al.
Published: (2023)

On the Complexity of Finite-Sum Smooth Optimization under the Polyak-Łojasiewicz Condition
by: Bai, Yunyan, et al.
Published: (2024)

Universal Online Convex Optimization Meets Second-order Bounds
by: Zhang, Lijun, et al.
Published: (2021)

Minimisation of Polyak-Łojasewicz Functions Using Random Zeroth-Order Oracles
by: Farzin, Amir Ali, et al.
Published: (2024)

A General Tikhonov Regularized Second-Order Dynamical System for Convex-Concave Bilinear Saddle Point Problems
by: Zhang, Bohan, et al.
Published: (2026)