Optimal Gradient-based Algorithms for Non-concave Bandit Optimization
Dec 6, 2021
Speakers
Baihe Huang
Speaker · 0 followers
Kaixuan Huang
Speaker · 0 followers
Sham M. Kakade
Speaker · 0 followers
Jason D. Lee
Speaker · 0 followers
Runzhe Wang
Speaker · 0 followers
Jiaqi Yang
Speaker · 0 followers
About
Much work has considered multi-armed bandit problems under linear (or kernelized) assumptions on the underlying reward function. This work considers bandit problems where the unknown underlying reward function is structured polynomials, including a two-layer neural network with polynomial activations and a low-rank generalized linear bandit problem.For the low-rank generalized linear bandit problem, we provide a minimax optimal algorithm in the dimension, refuting the conjectures in Jun et al (2019) and Lu et al (2021). Our algorithm is a unified zeroth-order optimization paradigm that applies in general, which attains optimal rates in several structured polynomial settings (in the dimension). We instantiate with the generalized low-rank bandit on how our techniques can be extended to the RL in the generative setting, resulting in improved sample complexity over prior approaches.Finally, we show that the standard optimistic algorithms (e.g., UCB) are sub-optimal by dimension factors. With the neural net setting (with polynomial activation functions), where, in the noise-free setting, we provide a bandit algorithm that has sample complexity equal to the intrinsic algebraic dimension. Again, we show that optimistic approaches have worse sample complexity, polynomial in the extrinsic dimension (which could be exponentially worse in the polynomial degree).Much work has considered multi-armed bandit problems under linear (or kernelized) assumptions on the underlying reward function. This work considers bandit problems where the unknown underlying reward function is structured polynomials, including a two-layer neural network with polynomial activations and a low-rank generalized linear bandit problem.For the low-rank generalized linear bandit problem, we provide a minimax optimal algorithm in the dimension, refuting the conjectures in Jun et al (2…
Organizer
NeurIPS 2021
Account · 1.9k followers
About NeurIPS 2021
Neural Information Processing Systems (NeurIPS) is a multi-track machine learning and computational neuroscience conference that includes invited talks, demonstrations, symposia and oral and poster presentations of refereed papers. Following the conference, there are workshops which provide a less formal setting.
Like the format? Trust SlidesLive to capture your next event!
Professional recording and live streaming, delivered globally.
Sharing
Recommended Videos
Presentations on similar topic, category or speaker
From "what" to "why": Towards casual deep learning
Watch later
Total of 0 viewers voted for saving the presentation to eternal vault which is 0.0%
Learning Stochastic Majority Votes by Minimizing a PAC-Bayes Generalization Bound
Watch later
Total of 0 viewers voted for saving the presentation to eternal vault which is 0.0%
Differentiable Synthesis of Program Architectures
Watch later
Guofeng Cui, …
Total of 0 viewers voted for saving the presentation to eternal vault which is 0.0%
XCI-Sketch: Extraction of Color Information from Images for Generation of Colored Outlines and Sketches
Watch later
V Manushree, …
Total of 0 viewers voted for saving the presentation to eternal vault which is 0.0%
FjORD: Fair and Accurate Federated Learning under heterogeneous targets with Ordered Dropout
Watch later
Total of 0 viewers voted for saving the presentation to eternal vault which is 0.0%
NeurInt-Learning Interpolation by Neural ODEs
Watch later
Total of 0 viewers voted for saving the presentation to eternal vault which is 0.0%