First-Order Optimization under Uniform Nondegeneracy: Geometry, Computation, and Information
Abstract
Strongly convex minimization and its natural indefinite extension to strongly convex--strongly concave minimax problems combine quantitative control of curvature with a prescribed curvature orientation. We disentangle these two roles by retaining uniform nondegeneracy alone: curvature remains uniformly separated from zero but may have either sign, with no prescribed positive--negative splitting. Surprisingly, a large part of the familiar theory nevertheless re-emerges. We first derive an intrinsic formulation through first-order secant inequalities, making the gradient on ℝd a global bi-Lipschitz homeomorphism and yielding a unique stationary point. We then pair signed Moreau envelopes to construct a smooth scalar merit that recovers the missing descent geometry at both zeroth and first order, and the resulting paired proximal descent method achieves global linear convergence with dimension-free first-order oracle complexity. Meanwhile, we show that this tractability can break down on restricted domains: merely assuming the existence of a stationary point in the domain may lead to the curse of dimensionality, even with access to an infinite-order oracle. To overcome this information barrier, we introduce certified feasibility, an observable localization condition that enables feasible continuation. Together, these results establish a first-order optimization theory under uniform nondegeneracy that spans geometry, computation, and information.
Related
- Descent--Ascent Structure of Uniform Nondegeneracy
- Bayesian Optimization with Fisher Information Geometry: Gradient Bounds and Trust-Region Methods
- Information-Computation Inversion in Pseudo-Marginal MCMC
- Invariants of Nilpotent Lie Algebras via Geometry and Algebra with a Focus on Computation
- An information-geometric formulation of distributed computation
BibTeX
@misc{su2026firstorder,
title = {{First-Order Optimization under Uniform Nondegeneracy: Geometry, Computation, and Information}},
author = {Hua Su and Lei Zhang and Jin Zhao},
howpublished = {arXiv},
year = {2026},
month = sep,
doi = {10.48550/arxiv.2609.06946},
eprint = {2609.06946},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2609.06946},
}
RIS
TY - UNPB
TI - First-Order Optimization under Uniform Nondegeneracy: Geometry, Computation, and Information
AU - Hua Su
AU - Lei Zhang
AU - Jin Zhao
PY - 2026
DA - 2026/09/07
PB - arXiv
DO - 10.48550/arxiv.2609.06946
UR - https://arxiv.org/abs/2609.06946
AB - Strongly convex minimization and its natural indefinite extension to strongly convex--strongly concave minimax problems combine quantitative control of curvature with a prescribed curvature orientation. We disentangle these two roles by retaining uniform nondegeneracy alone: curvature remains uniformly separated from zero but may have either sign, with no prescribed positive--negative splitting. Surprisingly, a large part of the familiar theory nevertheless re-emerges. We first derive an intrinsic formulation through first-order secant inequalities, making the gradient on ℝ^d a global bi-Lipschitz homeomorphism and yielding a unique stationary point. We then pair signed Moreau envelopes to construct a smooth scalar merit that recovers the missing descent geometry at both zeroth and first order, and the resulting paired proximal descent method achieves global linear convergence with dimension-free first-order oracle complexity. Meanwhile, we show that this tractability can break down on restricted domains: merely assuming the existence of a stationary point in the domain may lead to the curse of dimensionality, even with access to an infinite-order oracle. To overcome this information barrier, we introduce certified feasibility, an observable localization condition that enables feasible continuation. Together, these results establish a first-order optimization theory under uniform nondegeneracy that spans geometry, computation, and information.
ER -