Paperlane

no. 1 · Friday 23 October 2026

Adaptive Restart under Unknown KL Geometry in Stochastic Weakly-Convex Optimization

Binh T. Nguyen, Khoa D. Nguyen and Bao Thai Huynh

math.OC · 57 pp

Abstract

KL geometry accelerates restart schedules in stochastic weakly-convex optimization, but the schedule depends jointly on an unknown and potentially nonunique geometric description. We introduce CARP-KL, a certified portfolio that adapts over valid KL descriptions while using the same primitive stochastic-subgradient oracle for both optimization and candidate selection. Over declared polynomial parameter ranges, CARP-KL competes with every affordable valid description and preserves the known-description polynomial Moreau-stationarity rate up to logarithmic factors, without objective values, an exact proximal map, direct Moreau-gradient access, or a bounded-domain assumption. Controlled experiments quantify the finite-budget price of this universality. The portfolio repeatedly contains strong candidates, while certification consumes a substantial share of the oracle budget and finite-sample ranking limits their recovery. A common conservative gap bound further reduces the portfolio from $O(\log^3 T)$ to $O(\log^2 T)$ candidates with an explicit scale-mismatch penalty. The theory and diagnostics together establish certified unknown-geometry adaptation and pinpoint selection as the principal practical frontier of the current construction.

comments
57 pages
fields
Optimization and Control
pdf ↗ page arXiv:2610.30650 ↗