pipette
ENEnglish

On the Complexity of Finding Stationary Points in Stochastic -Smooth Nonconvex Optimization

Yanpeng Liang, Luo Luo

Preprint

En palabras de los autores

We study the stochastic first-order oracle (SFO) complexity of finding -stationary points of -smooth nonconvex functions. Under bounded-variance noise, existing analyses of normalized and clipped stochastic gradient descent (SGD) establish optimal dependence on and , but the jointly optimal dependence on , , and remains unclear. We resolve this question for an unbiased SFO whose gradient noise has a th central moment bounded by for some , where .Specifically, we establish an SFO lower bound of , where is the initial optimality gap.This bound identifies an unavoidable contribution proportional to . We also prove that mini-batch (smoothed) normalized SGD can attain a matching upper bound, thereby establishing the optimal SFO complexity.

Resultado principalEl resumen no menciona limitaciones.

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