Journal article · 2026 · Open access

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

Qi Deng, Guanghui Lan, Zhenwei Lin

INFORMS journal on computing · Published 22 April 2026 · DOI 10.1287/ijoc.2025.1177

Open PDFView at the publisherCite this paper

In brief

“Uniformly Optimal and Parameter-Free First-Order Methods for Convex and Function-Constrained Optimization” is a 2026 journal article by Qi Deng and 2 co-authors, published in INFORMS journal on computing. OpenAlex counts 15 citations as of 16 November 2026. It is open access: the full text is free to read at arXiv (Cornell University).

Citations
15
Most cited in
2026 (10)
Field-weighted impact
13.97
References
37
Authors
3

Abstract

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 [Formula: see text] 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 [Formula: see text] under Hölder smoothness conditions. When [Formula: see text] 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 [Formula: see text]. 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 [Formula: see text] 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/ .

Cite this paper

Formatted from the catalogue record. Check names, capitals and page numbers against the paper before you submit.

APA 7

Deng, Q., Lan, G., & Lin, Z. (2026). Uniformly Optimal and Parameter-Free First-Order Methods for Convex and Function-Constrained Optimization. INFORMS journal on computing. https://doi.org/10.1287/ijoc.2025.1177

MLA 9

Deng, Qi, et al. “Uniformly Optimal and Parameter-Free First-Order Methods for Convex and Function-Constrained Optimization.” INFORMS journal on computing, 2026. https://doi.org/10.1287/ijoc.2025.1177.

Chicago

Deng, Qi, Guanghui Lan, and Zhenwei Lin. 2026. “Uniformly Optimal and Parameter-Free First-Order Methods for Convex and Function-Constrained Optimization.” INFORMS journal on computing. https://doi.org/10.1287/ijoc.2025.1177.

Harvard

Deng, Q., Lan, G. and Lin, Z. (2026) ‘Uniformly Optimal and Parameter-Free First-Order Methods for Convex and Function-Constrained Optimization’, INFORMS journal on computing. doi:10.1287/ijoc.2025.1177.

IEEE

Q. Deng, G. Lan, and Z. Lin, “Uniformly Optimal and Parameter-Free First-Order Methods for Convex and Function-Constrained Optimization,” INFORMS journal on computing, 2026, doi: 10.1287/ijoc.2025.1177.

BibTeX

@article{deng2026uniformly,
  title     = {{Uniformly Optimal and Parameter-Free First-Order Methods for Convex and Function-Constrained Optimization}},
  author    = {Deng, Qi and Lan, Guanghui and Lin, Zhenwei},
  journal   = {INFORMS journal on computing},
  year      = {2026},
  doi       = {10.1287/ijoc.2025.1177},
  url       = {https://doi.org/10.1287/ijoc.2025.1177}
}

Download for a reference manager: BibTeX (.bib) · RIS for Zotero, Mendeley and EndNote (.ris)

Citations by year

YearCitationsShare of the best year
202011
202544
20261010

Its field-weighted citation impact is 13.97: it has been cited 13.97 times as often as the average work of the same field, type and year (1.00 is the world average).

Topic and keywords

Physical Sciences › Computer Science › Artificial Intelligence › Stochastic Gradient Optimization Techniques

  • convex optimization
  • first-order methods
  • oracle complexity
  • parameter-free method
  • Nesterov momentum
  • Hölder smoothness
  • root finding
  • secant method

Work with this paper

Most-cited papers in Computer Science

All highly cited Computer Science papers

Questions about this paper

How do I cite this paper in APA style?

Deng, Q., Lan, G., & Lin, Z. (2026). Uniformly Optimal and Parameter-Free First-Order Methods for Convex and Function-Constrained Optimization. INFORMS journal on computing. https://doi.org/10.1287/ijoc.2025.1177

How many times has this paper been cited?

15 times, according to OpenAlex on 16 November 2026. Google Scholar and Scopus count different sets of sources, so their numbers differ.

Is this paper free to read?

Yes. It is open access at arXiv (Cornell University): sign in and open the PDF from this page.

Who wrote this paper?

Qi Deng, Guanghui Lan, Zhenwei Lin.

What is the DOI of this paper?

10.1287/ijoc.2025.1177, permanently at https://doi.org/10.1287/ijoc.2025.1177. Sign in and open it from this page.

Bibliographic data from OpenAlex (CC0), last checked 16 November 2026. ResearchGuru does not host this paper; once you are signed in, the links open it at the publisher or the repository that does.