pipette
ENEnglish

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

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

Preprint

En palabras de los autores

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 to 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.

Resultado principalLimitación que admiten los autores

Apareció: viernes, 23 de octubre. arXiv. Preprint, todavía sin revisión por pares.

Comentario de los autores: 57 pages