Functional Multi-armed Bandit and the Best Function Identification Problems

We consider the model selection problem, where we have a set of candidate parametric functions and need to identify the function with the smallest minimum and corresponding minimizer. This problem arises in the competitive training of neural networks, where a set of candidates is given, and the limited computational budgetpreventstheuseofabrute-forcesearch. Toaddressthisproblem, we propose generalizations of the classical multi-armed bandit (MAB)andbestarmidentification(BAI)setups, sinceusingclassical MAB and BAI setups leads to infeasible computational costs. We refer to the proposed setups as the functional multi-armed bandit problem (FMAB) and the best function identification (BFI) problems, respectively. For these problems, we establish lower regret bounds for different classes of candidate functions. To solve FMAB and BFI problems, we propose a novel reduction scheme to construct the F-LCB algorithm, which is a UCB-type algorithm based on basic algorithms for nonlinear optimization with known convergence rates. TheF-LCBalgorithmcombinesthearmselectionstepandthe update of the current optimum approximation. We provide regret upper bounds for F-LCB based on the known convergence rates of the underlying base algorithms. The regret upper bounds match with the derived lower bounds up to the logarithmic factor. Numerical experiments confirm that the proposed approach correctly identifies the optimal function and provides the minimizer for it in both smooth and non-smooth convex cases. Similarly, F-LCB converges faster than SuccessiveHalving and Hyperband algorithms for the model selection problem, where the candidate functions are neural networks and only a stochastic gradient estimate is available.

Authors

• Yuriy Dorn AI Center & IAI MSU, Lomonosov Moscow State University
• Aleksandr Katrutsa AI Center, Lomonosov Moscow State University
• Ilgam Latypov AI Center & IAI MSU, Lomonosov Moscow State University
• Anastasia Soboleva AI Center & IAI MSU, Lomonosov Moscow State University

Keywords

• Multi-armed bandits
• functional multi-armed bandits
• best function identification