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 $\mathbb{R}^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.