Dynamic Regret Bounds for Constrained Online Nonconvex Optimization Based on Polyak-Lojasiewicz Regions

We study constrained online nonconvex optimization where performance is measured by dynamic regret against the time-varying optimal decision. For losses that can be arbitrarily nonconvex yet admit slowly time-varying global solutions, we analyze regions around each time’s optimizer to define time-varying target sets that satisfy proximal Polyak–Łojasiewicz and other properties under projected gradient descent. We design two algorithms and prove dynamic regret bounds scaling with problem variation.