Recursive Exponential Weighting for Online Non-convex Optimization
This provides a theoretically optimal algorithm for online non-convex optimization, addressing a generalization of online convex optimization with potential applications in machine learning and decision-making under uncertainty.
The paper tackles the online non-convex optimization problem by introducing a recursive exponential weighting algorithm, achieving a regret of O(√T), which matches the known lower bound and improves upon the previous O(√T log T) result.
In this paper, we investigate the online non-convex optimization problem which generalizes the classic {online convex optimization problem by relaxing the convexity assumption on the cost function. For this type of problem, the classic exponential weighting online algorithm has recently been shown to attain a sub-linear regret of $O(\sqrt{T\log T})$. In this paper, we introduce a novel recursive structure to the online algorithm to define a recursive exponential weighting algorithm that attains a regret of $O(\sqrt{T})$, matching the well-known regret lower bound. To the best of our knowledge, this is the first online algorithm with provable $O(\sqrt{T})$ regret for the online non-convex optimization problem.