Preprint · 2022 · Open access
Solving Convex Smooth Function Constrained Optimization Is Almost As Easy As Unconstrained Optimization
arXiv (Cornell University) · Published 11 October 2022 · DOI 10.48550/arxiv.2210.05807
In brief
“Solving Convex Smooth Function Constrained Optimization Is Almost As Easy As Unconstrained Optimization” is a 2022 preprint by Zhe Zhang and Guanghui Lan, published in arXiv (Cornell University). OpenAlex counts 18 citations as of 16 November 2026. It is open access under a CC BY licence: the full text is free to read at arXiv (Cornell University).
- Citations
- 18
- Most cited in
- 2026 (8)
- References
- 1
- Authors
- 2
Abstract
While Nesterov's Accelerated Gradient Descent (AGD) efficiently solves constrained problems when the constraint set $X \subseteq \bbr^n$ is simple and easy to project onto, it remains an open question whether function-constrained problems $\min_{x \in X} \{F(x) : g(x) \leq 0\}$ can be solved as efficiently as unconstrained problems in terms of oracle complexity. We provide an affirmative answer by proposing the Accelerated Constrained Gradient Descent (ACGD) method, a single-loop algorithm that modifies AGD by replacing the descent step with a constrained descent step, adding only a few linear constraints to the prox mapping. ACGD achieves nearly the same oracle complexity as minimizing the optimal Lagrangian function (with the multiplier fixed at its optimal value). We establish matching lower bounds, demonstrating these complexity results are unimprovable. For large-scale problems with many constraints, we introduce ACGD-S, which replaces the computationally demanding constrained descent step with basic matrix-vector multiplications, maintaining optimal oracle and computation complexities. Together, these methods provide a nearly complete characterization of the hardness of smooth function-constrained optimization. Under the additional assumption that $X$ is bounded, we also propose adaptive versions that achieve an order-optimal oracle complexity without requiring knowledge of either the aggregate smoothness constant or the diameter of $X$; only the strong convexity modulus is required in the strongly convex case. We present encouraging numerical results demonstrating their efficiency.
Cite this paper
Formatted from the catalogue record. Check names, capitals and page numbers against the paper before you submit.
APA 7
Zhang, Z., & Lan, G. (2022). Solving Convex Smooth Function Constrained Optimization Is Almost As Easy As Unconstrained Optimization. arXiv (Cornell University). https://doi.org/10.48550/arxiv.2210.05807
MLA 9
Zhang, Zhe, and Guanghui Lan. “Solving Convex Smooth Function Constrained Optimization Is Almost As Easy As Unconstrained Optimization.” arXiv (Cornell University), 2022. https://doi.org/10.48550/arxiv.2210.05807.
Chicago
Zhang, Zhe and Guanghui Lan. 2022. “Solving Convex Smooth Function Constrained Optimization Is Almost As Easy As Unconstrained Optimization.” arXiv (Cornell University). https://doi.org/10.48550/arxiv.2210.05807.
Harvard
Zhang, Z. and Lan, G. (2022) ‘Solving Convex Smooth Function Constrained Optimization Is Almost As Easy As Unconstrained Optimization’, arXiv (Cornell University). doi:10.48550/arxiv.2210.05807.
IEEE
Z. Zhang and G. Lan, “Solving Convex Smooth Function Constrained Optimization Is Almost As Easy As Unconstrained Optimization,” arXiv (Cornell University), 2022, doi: 10.48550/arxiv.2210.05807.
BibTeX
@misc{zhang2022solving,
title = {{Solving Convex Smooth Function Constrained Optimization Is Almost As Easy As Unconstrained Optimization}},
author = {Zhang, Zhe and Lan, Guanghui},
howpublished = {arXiv (Cornell University)},
year = {2022},
doi = {10.48550/arxiv.2210.05807},
url = {https://doi.org/10.48550/arxiv.2210.05807}
}
Download for a reference manager: BibTeX (.bib) · RIS for Zotero, Mendeley and EndNote (.ris)
Citations by year
| Year | Citations | Share of the best year |
|---|---|---|
| 2023 | 1 | |
| 2024 | 4 | |
| 2025 | 5 | |
| 2026 | 8 |
Topic and keywords
Physical Sciences › Computer Science › Artificial Intelligence › Stochastic Gradient Optimization Techniques
- oracle complexity
- Lagrangian
- lower bounds
- adaptive algorithms
- strong convexity
Work with this paper
Most-cited papers in Computer Science
- ImageNet classification with deep convolutional neural networksAlex Krizhevsky, Ilya Sutskever, Geoffrey E. Hinton · Communications of the ACM · 2017 · 114,726 citations
- Long Short-Term MemorySepp Hochreiter, Jürgen Schmidhuber · Neural Computation · 1997 · 109,097 citations
- A Mathematical Theory of CommunicationClaude E. Shannon · Bell System Technical Journal · 1948 · 91,736 citations
- Deep learningYann LeCun, Yoshua Bengio, Geoffrey E. Hinton · Nature · 2015 · 90,226 citations
- Faster R-CNN: Towards Real-Time Object Detection with Region Proposal NetworksShaoqing Ren, Kaiming He, Ross Girshick and 1 more · IEEE Transactions on Pattern Analysis and Machine Intelligence · 2016 · 74,143 citations
Questions about this paper
How do I cite this paper in APA style?
Zhang, Z., & Lan, G. (2022). Solving Convex Smooth Function Constrained Optimization Is Almost As Easy As Unconstrained Optimization. arXiv (Cornell University). https://doi.org/10.48550/arxiv.2210.05807
How many times has this paper been cited?
18 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: read the free full text at arXiv (Cornell University).
Who wrote this paper?
Zhe Zhang, Guanghui Lan.
What is the DOI of this paper?
10.48550/arxiv.2210.05807. The permanent link is https://doi.org/10.48550/arxiv.2210.05807.
Bibliographic data from OpenAlex (CC0), last checked 16 November 2026. ResearchGuru does not host this paper; the links go to the publisher or the repository that does.