Adaptive Restart under Unknown KL Geometry in Stochastic Weakly-Convex Optimization
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(log3 T) to O(log2 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.
Related
- Restart and Adaptive Acceleration in Stochastic Gradient Methods
- Localize, Restart, Accelerate: Stochastic Optimization under Generalized Smoothness
- Critical Growth for Stochastic Adaptive Stabilization with an Unknown Input Gain
- Riemannian Optimization on Unknown Manifolds via Stochastic Proximal Refinement
- An Adaptive Augmented Lagrangian Method for Deterministic and Stochastic Nonconvex Optimization
BibTeX
@misc{nguyen2026adaptive,
title = {{Adaptive Restart under Unknown KL Geometry in Stochastic Weakly-Convex Optimization}},
author = {Binh T. Nguyen and Khoa D. Nguyen and Bao Thai Huynh},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2610.30650},
eprint = {2610.30650},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2610.30650},
note = {CC BY-NC-ND 4.0},
}
RIS
TY - UNPB
TI - Adaptive Restart under Unknown KL Geometry in Stochastic Weakly-Convex Optimization
AU - Binh T. Nguyen
AU - Khoa D. Nguyen
AU - Bao Thai Huynh
PY - 2026
DA - 2026/10/22
PB - arXiv
DO - 10.48550/arxiv.2610.30650
UR - https://arxiv.org/abs/2610.30650
AB - 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.
ER -