Alice: Adaptive Stochastic Gradient Descent Based on Adversarial Multi-armed Bandits

Gradient-based optimization algorithms are central to machine learning, and their performance critically depends on the choice of the learning rate. Modern methods adapt learning rates during training using gradient information. In this work, we explore an alternative research direction by viewing learning-rate adaptation through the adversarial bandit setting. We develop a theoretical framework that relates the convergence of adaptive gradient methods to the regret of an adversarial bandit problem. Then, we instantiate our framework using EXP3 within stochastic gradient descent and demonstrate its effectiveness through empirical evaluations.