Optimal Stochastic Nonconvex Optimization with Bandit Feedback
In this paper, we analyze the continuous armed bandit problems for nonconvex cost functions under certain smoothness and sublevel set assumptions. We first derive an upper bound on the expected cumulative regret of a simple bin splitting method. We then propose an adaptive bin splitting method, which can significantly improve the performance. Furthermore, a minimax lower bound is derived, which shows that our new adaptive method achieves locally minimax optimal expected cumulative regret.
Code (0)
등록된 구현이 없습니다.
Similar Papers 제목 키워드 기반
On Adaptivity in Non-stationary Stochastic Optimization With Bandit Feedback
In this paper we study the non-stationary stochastic optimization question with bandit feedback and dynamic regret measures. The seminal work of Besbes et al. (2015) shows that, when aggregated function changes is known …
Stochastic OptimizationAn Optimal Algorithm for Bandit and Zero-Order Convex Optimization with Two-Point Feedback
We consider the closely related problems of bandit convex optimization with two-point feedback, and zero-order stochastic convex optimization with two function evaluations per round. We provide a simple algorithm and ana…
Multi-Point Bandit Algorithms for Nonstationary Online Nonconvex Optimization
Bandit algorithms have been predominantly analyzed in the convex setting with function-value based stationary regret as the performance measure. In this paper, motivated by online reinforcement learning problems, we prop…
Reinforcement LearningDelay and Cooperation in Nonstochastic Linear Bandits
This paper offers a nearly optimal algorithm for online linear optimization with delayed bandit feedback. Online linear optimization with bandit feedback, or nonstochastic linear bandits, provides a generic framework for…
Decision MakingSequential Decision MakingA Nonstochastic Control Approach to Optimization
Selecting the best hyperparameters for a particular optimization instance, such as the learning rate and momentum, is an important but nonconvex problem. As a result, iterative optimization methods such as hypergradient …