acceptodds
Under review as a conference paper at ICLR 2027

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

Abstract

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.

Primary area:
optimization
Keywords:
stochastic optimization, adversarial bandits, EXP3, adaptive learning rate

Reviews

Among:
Shape:
1234this paper, Top 49%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.33 over 3 reviews, above 51% of the others.
Reviewer_D6s4OpenReview ↗
Rating
4
Confidence
3
Informativeness
2
Presentation
3
Soundness
3
Read review
Paper summary

The paper presents ALICE - a modification of stochastic gradient descent with online step size selection based on regret minimization. At each iteration $ t $ an EXP3 algorithm is employed, extended to allow for a unbounded from above loss and side observations, to sample a candidate step size It\mathsf{I}_t from a predefined grid; then, the best step size is selected via line search over a user-defined set $ \Gamma_t (\mathsf{I}_t) $. The method then updates the EXP3 probabilities based on the losses of all step sizes in the set $ \Gamma_t (\mathsf{I}_t) $.

The authors prove the convergence of the method on a non-negative L-smooth non-convex objective with an unbiased gradient estimate, obtaining a guarantee that does not require tuning a single step size (although it is still up to the user to construct a suitable grid; the authors suggest two choices of geometric grids with the grid's lower and upper bound as hyperparameters). The authors validate the method on a set of experiments, reporting best test performance that matches or exceeds the baselines (SGD, Adam, AutoSGD, DoWG) in most settings.

Critical strengths
  1. Strong theoretical guarantees: the authors provide a clean theoretical analysis of the proposed method, obtaining a convergence guarantee under stated assumptions.
  2. The extension of the EXP3 algorithm to work with unbounded losses and side observations is valuable in itself, and is also supported with a derived regret bound.
  3. Strong empirical performance of the proposed method, matching or beating learning-rate-free baselines on a range of tasks.
Critical weaknesses

The method depends on a single fixed sample ξ′\xi', which is used to update the EXP3 probabilities, to perform the line search (Algorithm 4, line 8), and in the normalization bt\mathsf{b}_t. The authors explain in Section 5.1.3 why ξ′\xi' must be kept fixed for the analysis, but its choice is a hyperparameter in its own right; in my reading, the sensitivity of the method to it is not discussed. Other learning-rate selection methods do not require a fixed sample, such as LRRL (Donâncio et al., 2024) or AutoSGD (Surjanovic et al., 2025).

Questions for authors
  1. Could the authors elaborate on the choice of the fixed sample ξ′\xi' used in the experiments, and its influence on the method's convergence? (see Weaknesses)
  2. The method LRRL of Donâncio et al. (2024) seems to be the closest conceptual match to the proposed ALICE (although lacking theoretical guarantees); an experimental comparison between them would be interesting to see.
  3. Minor: the plots of Figure 1 contain a lot of information and are a bit hard to parse. Would it be possible to provide a table of best test risk per method per experiment, together with a wallclock time comparison accounting for time required for grid search for SGD and Adam? In my opinion, this would make the comparison easier.
  4. Minor: reporting best test risk mixes the optimization performance of the methods with the generalization ability of the models. In my view, it would be more informative to report the best train risk in the main body.
2 comments

Thank you for your positive evaluation and your remarks. Following your questions, we added the sampling of all the mini-batches, including the reference batch, in Sec. 7, and the total time of a grid search compared to a single run of Alice in Fig. 9. Regarding the influence of ξ′\xi' on the convergence, we also added intuition on Ass. 7 and the values of its constants in Tab. 1. All changes are in red.

Strengths. Thank you for highlighting the theoretical guarantees, the extension of EXP3 to unbounded losses with side observations, and the empirical performance.

Weakness and 1. Fixed sample. You are right that ξ′\xi' is a design choice: as you note, it must be fixed for the analysis (Sec. 5.1.3), and Alice favors the learning rates that are good for fξ′f_{\xi'}, so fξ′f_{\xi'} must be representative of ff (Ass. 7). However, ξ′\xi' does not add a hyperparameter to our experiments: it is a mini-batch of 256 samples, as the SGD mini-batches, drawn once at the start from the training set, with a different draw for each of the 3 seeds. Hence, the standard deviation in Fig. 1 already includes the variability due to ξ′\xi'. The influence of ξ′\xi' on the convergence is measured by κ\kappa and δ\delta in Ass. 7: on nine tasks, κ\kappa remains bounded and δ=O(T)\delta=\mathcal{O}(\sqrt{T}) in Tab. 1. We did not study the sensitivity to the size of ξ′\xi': the other parameter-free algorithms do not select the batch size either, and choosing it automatically, as well as ξ′\xi', is an interesting direction for future work. The methods that do not need a fixed sample have other drawbacks: AutoSGD and the parameter-free algorithms depend on an initial learning rate that can make the optimization diverge at the very beginning when it is badly chosen (Sec. 5.3), and AutoSGD, one of our baselines, runs three SGDs in parallel and is much slower than Alice (Fig. 8). We discuss LRRL in 2.

2. Comparison with LRRL. You are right that LRRL (Donâncio et al., 2024) is the closest conceptual match, and we discuss it in the related work. However, it is designed for deep reinforcement learning (its only other experiments, in its latest version, are on toy functions of two variables, such as Rosenbrock), with the return of the policy as feedback: applying it to supervised tasks requires re-adapting its feedback and its hyperparameters, which would give a method different from theirs. Moreover, it is not parameter-free: as its authors report, it needs a set of 3 to 5 learning rates within a factor 16 (e.g., from 1.6⋅10−51.6\cdot10^{-5} to 2.5⋅10−42.5\cdot10^{-4}) chosen carefully for each experiment, and a bandit step size that requires tuning. The safe variants of Alice use the same interval [10−6,102][10^{-6},10^{2}] for all tasks, with a guarantee linking the convergence of gradient descent to the bandit loss.

3. Table and wallclock time. Thank you for the suggestion, which led us to add Fig. 9: it reports the total wallclock time, including the grid searches of SGD, Adam, and DoWG, and shows that they take 3 to 8 times longer than a single run of the safe variants of Alice. Fig. 1 gives the best test risk of each algorithm for every γ0\gamma_0, which shows how much the baselines depend on tuning, whereas the safe variants of Alice need a single run.

4. Train risk. You are right that the best test risk mixes the optimization performance with the generalization of the models. We chose to also look at the test risk, as in, e.g., D-Adaptation (Defazio & Mishchenko, 2023) and DoWG (Khaled et al., 2023), to highlight the generalization of the models: in practice we minimize the training loss but evaluate on the test set, and Fig. 1 summarizes this information. The train risk and the train loss of the same models are all reported in Figs. 2 and 3.

Thank you again for your time. We added to Tab. 1 additional tasks that have finished running. We hope you had the chance to read our reply, and we would be happy to provide any additional information you may need.

Reviewer_jKwhOpenReview ↗
Rating
2
Confidence
3
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

The paper proposes Alice, a framework that uses adversarial bandits (EXP3) to adapt SGD learning rates. Learning rates are drawn from a geometric grid, and EXP3 selects among them using losses evaluated on a fixed reference function f_xi'. A "safe" variant adds gamma=0 to the candidate set when all rates would increase the reference loss above f_xi'(x_0). The main theoretical contribution is a convergence bound that relates the cumulative squared gradient norm to the regret of this bandit problem, followed by a regret analysis for nonnegative (unbounded) losses with side observations. Experiments compare several Alice variants against SGD, Adam, AutoSGD, and DoWG on regression, image classification, and text classification tasks.

Critical strengths

1.An explicit regret-to-optimization framework. Theorem 3 compares each adaptive iterate with a one-step ghost update and isolates a loss-gap term that is then controlled by bandit regret. Appendices C and D give the descent, telescoping, and EXP3 arguments leading to Corollary 1. This is a conceptually clean connection, and the proof strategy is not just "run a bandit on top of SGD."

2.A concrete safety mechanism with useful diagnostics. Appendix C.6 shows how the zero-step fallback keeps the reference-loss scale bounded. The supplementary experiments report learning-rate trajectories, distribution heatmaps, safe-step counts, and per-epoch timing. These support a bounded practical claim: the safe variants reduce sensitivity to the initial learning rate, and their overhead is below AutoSGD, though higher than SGD, Adam, and DoWG.

Critical weaknesses

1.The scope of the convergence claim is not fully established. Assumption 7 directly controls the cumulative discrepancy between the true objective and a fixed reference function along a reference-adaptive trajectory. Appendix C.4 invokes it at Eq. (13), but the paper does not give a concrete setting where the constants kappa and delta remain informative as the horizon T grows. The safe reference-loss bound in Proposition 1 does not imply this discrepancy control. More concretely, I am not sure Corollary 1(ii) actually yields a vanishing rate: with B_T bounded by Proposition 1, the term involving kappa, B_T, and the square root of T appears to be O(1) rather than O(1/sqrt(T)) or any vanishing rate. If I am misreading the bound, the authors should clarify; if not, part (ii) does not provide a convergence guarantee. The constants alpha, beta, kappa, delta also need discussion: the bounds are only meaningful if these are moderate, and the paper does not relate them to concrete stochastic optimization problems.

2.The evaluation still relies on test-based selection, and the timing evidence answers a narrower question than total tuning cost. Figure 3 explicitly selects gamma_0 using the lowest test risk, and Appendix E.2/Figure 3 follow the same protocol for baselines. Appendix E.1 merges training and validation data for the image tasks. Avoiding test-gradient updates does not remove this selection bias. Figure 8 does provide per-epoch timing (I acknowledge that), but it does not establish performance at a matched total budget with independent evaluation. The construction of the fixed reference batch is also unclear (size, sampling, relation to the gradient mini-batch), which limits assessment of the claimed robustness and cost tradeoff.

Questions for authors

1.Theory applicability. Which concrete stochastic optimization settings satisfy Assumptions 5 and 7 with constants that keep the bounds informative? Please make the dependence on the reference-batch size and reuse explicit, and clarify whether Corollary 1(ii) is intended to be a vanishing-rate bound. If so, where does the O(1) term I identified above go? Also, under persistent stochastic-gradient noise, which of the two bounds in Corollary 1 is the relevant one?

2.Empirical validity. If hyperparameters and checkpoints are selected using validation data, or if a prespecified terminal iterate is used, do the main robustness comparisons persist? Please clarify the fixed reference batch's size and source and its relation to the gradient batches, and relate the Figure 8 timings to the total budget needed for comparable independently evaluated performance.

5 comments

Thank you for your remarks. Following your questions, we added intuition on Ass. 5 and 7 and on Cor. 1, the values of their constants on the tasks in Tab. 1, the sampling of all the mini-batches, including the reference batch, in Sec. 7, and the total time of a grid search compared to a single run of Alice in Fig. 9. All changes are in red.

Strengths. Thank you for highlighting the regret-to-optimization framework (Th. 3) and the safe mechanism.

Weaknesses.

About the scope of the convergence claim. You are right that Ass. 7 is not implied by Prop. 1: it formalizes that fξ′f_{\xi'} must be representative of ff for Alice to update pt\mathsf p_t correctly (Sec. 4). Like the usual assumptions on SGD (e.g., smoothness or growth conditions; Ghadimi & Lan, 2013; Schmidt & Le Roux, 2013), it is assumed rather than proved: showing that the strong growth condition holds for a given model already needs a dedicated analysis (Vaswani et al., 2019). We go further by computing its constants and observing that they remain bounded when TT goes from 10k to 50k (Tab. 1).

About the evaluation. You are right that γ0\gamma_0 and the checkpoint are selected on the test risk, and that the image tasks merge the training and validation data. We explain in 2 why the selection does not invalidate the comparisons.

Questions.

1. Theory applicability. The constants κ\kappa and δ\delta measure how much choosing γt\gamma_t with fξ′f_{\xi'} makes the iterates depend on ξ′\xi' (Sec. 4). On nine tasks and for TT = 10k, 25k, and 50k (see, e.g., Tab. 1(a)), κ\kappa and α\alpha remain bounded and δ=O(T)\delta=\mathcal{O}(\sqrt{T}), while β\beta is zero or negligible for most tasks in (i) and at most O(T)\mathcal{O}(T) in (ii). The other tasks are running and we will add them. Since BT=O(1)\mathsf B_T=\mathcal{O}(1) for the safe variants (Prop. 1), if κ,α=O(1)\kappa,\alpha=\mathcal{O}(1) and δ=O(T)\delta=\mathcal{O}(\sqrt{T}), then under persistent noise along the trajectory, i.e., when β=O(T)\beta=\mathcal{O}(T), only Cor. 1 (ii) vanishes, in O(T−1/4)\mathcal{O}(T^{-1/4}), with no O(1)\mathcal{O}(1) term, since κBTTKln⁡K=O(T)\kappa\mathsf B_T\sqrt{TK\ln K}=\mathcal{O}(\sqrt{T}) is divided by TT. When the noise accumulated along the trajectory is small, i.e., when β=O(T)\beta=\mathcal{O}(\sqrt{T}), Cor. 1 (i) gives O(1/T)\mathcal{O}(1/\sqrt{T}).

2. Empirical validity.

Test-based selection. As in, e.g., COCOB (Orabona & Tommasi, 2017), D-Adaptation (Defazio & Mishchenko, 2023), and DoWG (Khaled et al., 2023), we evaluate the model learned on the training set with a test set. Our goal is not model selection but to check the generalization of the model obtained by minimizing the training loss, and Figs. 1 and 3 summarize this information. This can be quantified with confidence intervals. Let RD(x)=Ez∼Dℓ(x,z)R_{\mathcal{D}}(x)=\mathbb E_{z\sim\mathcal{D}}\ell(x,z) be the true risk of the parameters xx and RT(x)R_{\mathcal{T}}(x) its risk on the test set T\mathcal{T} of size nn (we take a bounded loss ℓ\ell; the unbounded case follows the same principle, e.g., with sub-Gaussian or sub-exponential losses). For NN candidates x1,…,xNx_1,\dots,x_N that do not depend on T\mathcal{T}, Hoeffding's inequality and a union bound give, with probability at least 1−η1-\eta, for all ii, ∣RD(xi)−RT(xi)∣≤ε|R_{\mathcal{D}}(x_i)-R_{\mathcal{T}}(x_i)|\le\varepsilon with ε=ln⁡(2N/η)/(2n)\varepsilon=\sqrt{\ln(2N/\eta)/(2n)}. With a standard train/validation/test split, x1=xx_1=x is chosen on the validation set, i.e., we have N=1N=1, so ε=ln⁡(2/η)/(2n)\varepsilon=\sqrt{\ln(2/\eta)/(2n)}. If xx is instead chosen among NN candidates with the test risk, the interval only grows logarithmically in NN (e.g., with n=10,000n=10{,}000 and η=0.05\eta=0.05, from ε≈0.014\varepsilon\approx0.014 for N=1N=1 to ε≈0.021\varepsilon\approx0.021 for N=200N=200). In Fig. 1, NN is the number of epochs, so all the algorithms have the same ε\varepsilon. In Fig. 3, γ0\gamma_0 is also selected, which multiplies NN by the number of values of γ0\gamma_0 for the baselines; the safe variants of Alice have no γ0\gamma_0, so their interval is slightly tighter, which is negligible for comparing the algorithms. Hence, the advantage of an algorithm over another reported on the test set exceeds the true one by at most the sum of their two intervals. A prespecified terminal iterate is simply the case N=1N=1, but it gives no control on the training, whose loss may increase again at some point. This is why Fig. 3 reports the train risk, the train loss, and the test risk along the iterations.

Reference batch and timings. Thank you for pointing out that the reference batch was unclear. All the mini-batches have 256 samples and are drawn from the training set: the SGD mini-batches are sampled without replacement at each epoch, whereas ξ′\xi' is drawn once at the start, independently of them, and reused at every iteration. The same batch size is used for all the algorithms and is not tuned, as the other parameter-free algorithms do not select it either; choosing it automatically, as well as ξ′\xi', is an interesting direction for future work. Thank you also for your remark on the timings, which led us to add Fig. 9: a grid search takes 3 to 8 times longer for SGD, Adam, and DoWG than a single run of the safe variants of Alice.

Thank you again for your review. We added to Tab. 1 additional tasks that have finished running. We would be glad to know whether our reply answers your questions, and we remain available to provide any additional information.

Reviewer_F3PGOpenReview ↗
Rating
1
Confidence
3
Informativeness
1
Presentation
2
Soundness
1
Read review
Paper summary

This work combines standard techniques from optimization and online learning to propose a meta-algorithm that adaptively tunes the learning rate using the adversarial bandit algorithm EXP3, treating each candidate learning rate as a separate arm.

Critical strengths

The reviewer does not find sufficient evidence from the paper to recommend it for acceptance.

Critical weaknesses

The paper does not clarify the positioning of the work within the existing literature or highlight its novelty. There are several papers that address parameter-free optimization algorithms, see [1--3].

The technical analysis raises some concerns. Assumption 7 appears to be rather artificial and potentially there to facilitate the convergence proof, rather than representing a standard growth condition; see, e.g., [4]. The authors should provide sufficient conditions under which this assumption is satisfied for Alice. Without such a justification, the convergence guarantee relies on a central assumption whose validity remains unverified.

[1] F. Orabona and T. Tommasi. “Training Deep Networks without Learning Rates Through Coin Betting”. In: Advances in Neural Information Processing Systems 30. 2017

[2] A. Cutkosky and K. A. Boahen. “Online Convex Optimization with Unconstrained Domains and Losses”. In: Advances in Neural Information Processing Systems 29. 2016, pp. 748–756

[3] A. Attia and T. Koren. 2024. How free is parameter-free stochastic optimization? In Proceedings of the 41st International Conference on Machine Learning (ICML'24), Vol. 235. JMLR.org, Article 80, 2009–2034.

[4] V., Sharan, F., Bach, and M. Schmidt. "Fast and faster convergence of sgd for over-parameterized models and an accelerated perceptron." The 22nd international conference on artificial intelligence and statistics. PMLR, 2019.

Questions for authors
  • Could the authors clarify the main novelty of the proposed approach compared with existing parameter-free optimization algorithms? What are the key theoretical or algorithmic advances over these works?

  • Could the authors explain the motivation behind Assumption 7 and provide sufficient, verifiable conditions under which it holds for Alice?Can the authors establish its validity rather than relying on it solely as a technical requirement for the convergence proof?

3 comments

Thank you for your remarks and for the references, which helped us improve the clarity of the paper. We moved to the main text the discussion on parameter-free algorithms that was in the appendix, and we extended it (Intro., Secs. 5.3 and 6.2). We also added intuition on Ass. 5 and 7 (Secs. 2 and 4), on Alice (Sec. 5.3), and on Cor. 1 (Sec. 6.2). All changes are in red and we summarize below the ones related to your two concerns.

1. Positioning. You are right that the positioning needed to be clearer. Parameter-free algorithms either perform a single run but depend on an initial hyperparameter (DoG, DoWG, D-Adaptation, AutoSGD, and [1] with α\alpha), or restart the optimization with different hyperparameters ([2, 3], Khaled & Jin, Carmon & Hinder, Streeter & McMahan). A badly chosen initial value can make the optimization diverge at the very beginning (e.g., a small α\alpha for [1]), and restarts are essentially a grid search where each run only uses a fraction of the iterations. Instead of a well-chosen initial value, the safe variants of Alice only need an interval of learning rates, [10−6,102][10^{-6},10^{2}] for all tasks, which can even contain values for which SGD diverges. Moreover, instead of restarts, the safe variants need a single run, while for SGD, Adam, and DoWG, a grid search over the learning rate takes 3 to 8 times longer (Fig. 9). Finally, Cor. 1 (i) gives a rate in O(1/T)\mathcal{O}(1/\sqrt{T}) when κ\kappa and α\alpha are O(1)\mathcal{O}(1) and δ\delta and β\beta are O(T)\mathcal{O}(\sqrt{T}) (Ass. 5 and 7). Its dependence on γmax⁡/γmin⁡\gamma_{\max}/\gamma_{\min} is only logarithmic, as in the guarantees of parameter-free algorithms. We obtain these guarantees by relating the convergence of SGD to the regret of an adversarial bandit (Th. 3), whose analysis we extend to unbounded losses (Sec. 5.2). The difference is that the guarantees of [1, 2] are stated for (quasi-)convex functions and the non-convex ones of [3] rely on several runs of SGD, whereas ours hold for non-convex smooth functions with a single run.

2. Assumption 7. You are right that it needed more motivation. Alice updates the distribution pt\mathsf{p}_t over the learning rates with the losses of fξ′f_{\xi'}. Hence, fξ′f_{\xi'} must be representative of ff for Alice to favor learning rates that are good for ff. Ass. 7 formalizes this: it relates the regret on fξ′f_{\xi'}, controlled by the bandit, to the regret on ff, with a multiplicative factor κ\kappa and an additive error δ\delta. It is a growth-condition-style assumption, like Ass. 5. Here, κ\kappa and δ\delta measure how much choosing γt\gamma_t with fξ′f_{\xi'} makes the iterates depend on ξ′\xi': they are κ=1\kappa=1 and δ=0\delta=0 without this dependence. Empirically (see, e.g., Tab. 1(a)), on nine tasks and for TT = 10k, 25k, and 50k, we observe κ=O(1)\kappa=\mathcal{O}(1) and δ=O(T)\delta=\mathcal{O}(\sqrt{T}), and the bounds are globally close to the measured values. The other tasks are currently running and we will add them. Finding the models for which Ass. 7 holds is a question in itself, as [4] needs a whole paper to show that the strong growth condition holds for over-parameterized models. We see it as an exciting direction for future work.

Thank you again for your review. We believe our reply and the revised paper address the points raised. We added to Tab. 1 additional tasks that have finished running. Please let us know if any additional information would be useful.

The reviewer thanks the authors for the additional clarifications. The reviewer still maintains his opinion on the novelty concerns.

Comments on the paper

1 comment

We thank the reviewers for their constructive remarks, which helped us improve the paper. We would like to highlight that Alice takes a different route from the existing parameter-free algorithms: it casts the choice of the learning rate as an adversarial bandit, and Th. 3 relates the convergence of SGD to its regret. This gives a parameter-free algorithm that needs a single run, has guarantees for non-convex smooth functions, and only requires a very large interval of learning rates. This new link also opens perspectives for the tuning of other hyperparameters, such as the mini-batch size or the momentum parameters, which we leave for future work.

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.