- 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 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
- Strong theoretical guarantees: the authors provide a clean theoretical analysis of the proposed method, obtaining a convergence guarantee under stated assumptions.
- 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.
- 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 , which is used to update the EXP3 probabilities, to perform the line search (Algorithm 4, line 8), and in the normalization . The authors explain in Section 5.1.3 why 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
- Could the authors elaborate on the choice of the fixed sample used in the experiments, and its influence on the method's convergence? (see Weaknesses)
- 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.
- 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.
- 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 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.
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 ξ′ 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 ξ′ 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ξ′, so fξ′ must be representative of f (Ass. 7). However, ξ′ 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 ξ′. The influence of ξ′ on the convergence is measured by κ and δ in Ass. 7: on nine tasks, κ remains bounded and δ=O(T) in Tab. 1. We did not study the sensitivity to the size of ξ′: the other parameter-free algorithms do not select the batch size either, and choosing it automatically, as well as ξ′, 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−5 to 2.5⋅10−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] 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, 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.