Recursive Exponential Weighting for Online Non-convex Optimization
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.
Code (0)
등록된 구현이 없습니다.
Similar Papers 제목 키워드 기반
Recursive Decomposition for Nonconvex Optimization
Continuous optimization is an important problem in many areas of AI, including vision, robotics, probabilistic inference, and machine learning. Unfortunately, most real-world optimization problems are nonconvex, causing …
Combinatorial Optimizationgraph partitioningProblem DecompositionProtein FoldingNearly second-order asymptotic optimality of sequential change-point detection with one-sample updates
Sequential change-point detection when the distribution parameters are unknown is a fundamental problem in statistics and machine learning. When the post-change parameters are unknown, we consider a set of detection proc…
Change Point DetectionModel-free Online Learning for the Kalman Filter: Forgetting Factor and Logarithmic Regret
We consider the problem of online prediction for an unknown, non-explosive linear stochastic system. With a known system model, the optimal predictor is the celebrated Kalman filter. In the case of unknown systems, exist…
Inductive BiasregressionEfficient Smooth Non-Convex Stochastic Compositional Optimization via Stochastic Recursive Gradient Descent
Stochastic compositional optimization arises in many important machine learning tasks such as reinforcement learning and portfolio management. The objective function is the composition of two expectations of stochastic f…
ManagementReinforcement LearningStochastic OptimizationRecursive nonlinear-system identification using latent variables
In this paper we develop a method for learning nonlinear systems with multiple outputs and inputs. We begin by modelling the errors of a nominal predictor of the system using a latent variable framework. Then using the m…