Uniformly Optimal and Parameter-Free First-Order Methods for Convex and Function-Constrained Optimization

This paper presents new first-order methods for achieving optimal oracle complexities in convex optimization with convex function constraints. Oracle complexities are measured by the number of function and gradient evaluations. To achieve this, we develop first-order methods that can utilize computational oracles for solving diagonal quadratic programs in subproblems. For problems where the optimal value $f^{*}$ is known, such as those in overparameterized models and feasibility problems, we propose an accelerated first-order method that incorporates a modified Polyak step size and Nesterov’s momentum. Notably, our method does not require knowledge of smoothness levels, Hölder continuity parameter of the gradient, or additional line search, yet achieves the optimal oracle complexity bound of $\mathcal{O}({\epsilon }^{-2/(1+3\rho )})$ under Hölder smoothness conditions. When $f^{*}$ is unknown, we reformulate the problem as finding the root of the optimal value function and develop inexact fixed-point iteration and secant method to compute $f^{*}$. These root-finding subproblems are solved inexactly using first-order methods to a specified relative accuracy. We employ the accelerated prox-level (APL) method, which is proven to be uniformly optimal for convex optimization with simple constraints. Our analysis demonstrates that APL-based root-finding also achieves the optimal oracle complexity of $\mathcal{O}({\epsilon }^{-2/(1+3\rho )})$ for convex function-constrained optimization, without requiring knowledge of any problem-specific structures. Through experiments on various tasks, we demonstrate the advantages of our methods over existing approaches in function-constrained optimization.

History: Accepted by Antonio Frangioni, Design & Analysis of Algorithms–Continuous.

Funding: Q. Deng was supported in part by the National Natural Science Foundation of China [Grants 12571325, 72394364/72394360] and the Natural Science Foundation of Shanghai [Grant 24ZR1421300].

Supplemental Material: The software that supports the findings of this study is available within the paper and its Supplemental Information (https://pubsonline.informs.org/doi/suppl/10.1287/ijoc.2025.1177) as well as from the IJOC GitHub software repository (https://github.com/INFORMSJoC/2025.1177). The complete IJOC Software and Data Repository is available at https://informsjoc.github.io/.