Faking Interpolation Until You Make It
Authors: Alasdair Paren
Rudra P. K. Poudel
M. Pawan Kumar
Venue: Accepted by TMLR ()

Abstract: Deep over-parameterized neural networks exhibit the interpolation property on many data sets. Specifically, these models can achieve approximately zero loss on all training samples simultaneously. This property has been exploited to develop optimisation algorithms for this setting. These algorithms use the fact that the optimal loss value is known to employ a variation of a Polyak step size calculated on each stochastic batch of data. We introduce a novel extension of this idea to tasks where the interpolation property does not hold. As we no longer have access to the optimal loss values a priori, we instead estimate them for each sample online. To realise this, we introduce a simple but highly effective heuristic for approximating the optimal value based on previous loss evaluations.  We provide rigorous experimentation on a range of problems. From our empirical analysis we demonstrate the effectiveness of our approach, which outperforms other single hyperparameter optimisation methods.

Published in Transactions on Machine Learning Research (09/2022)
Faking Interpolation Until You Make It
Alasdair Paren
alasdair paree com
Deportment of Engineering Science University of Onford Oxford, UK
Rudra P. K. Poudel
rudru.pouddel@errttssoooe uk
Cambridge Research Laborutory, Toshiba Europe Ltd,
Cambridge, UK.
M. Pawan Kumar Department of Engineering Science University of Ouford Oxford, UK.
pawan@robots.oz.cco
Reviewed on OpenReview: https: // openreview. net/ forum? id- 0s LAMMF42P
Abstract
Deep over- peeeparraettrized neural networks exhibit the interpolation property on many data sets. Specifically, these models can achieve approximately zero loss on all training samples simultaneously. This property has been exploited develop optimisation algorithms for this setting. These algorithms variation of Polyak step size calculated a novel extension of this idea to tasks where the interpolation property does not hold. As we no longer have access to the optimal loss values a priori, we instead estimate them for each sample online. To realise this, we introduce a simple but highly effective heuristic for approximating the optimal value based on previous loss evaluations. We provide rigorous experimentation on range of problems. From our empirical analysis we demonstrate the effectiveness of approach, which outperforms here single hyperparameler optimisation methods.
the fact that the optimal loss value is known to employ each stochastic batch of data. We introduce
1 Introduction
Deep over-parameeterized neural networks exhibit the interpolation property on many data sets (?
et al. 2020). That is, these models are able to achieve close to zero loss on all samples simultaneously.
Initially, y, the interpolation property has been exploited to prove new convergence rates (Vaswani et al.
2019a b Ma et al.) 2018 Liu & Belkin 2019 and to develop novel optimisation algorithms for this setting.
Examples include Adaptive learning rates for Interpolation with Gradients (ALI-G; Berrada et al. (2020)
and Stochastic Polyak Step (SPS; Loizou al. (2021)). Both ALI-G and SPS the interpolation property
to ensure that the optimal loss value for each data point will be zero. With this knowledge it is possible to
employ stochastic variation of the Polyak step size (Polyak 1969). This automatically scales maximal step size hyperparameter down to appropriate value for each update, which removes the need for a painstakingly hand-designed learning rate schedule (Berrada el al. 2020 Loizou et al. 2021]. ALI-G and SPS have been shown to produce highly competitive results, matching the generalisation performance of SGD with a manually tuned learning rate many settings, and outperforming adaptive gradient methods by large margin. While these techniques work well, the interpolation property does not hold on many interesting large-scale learning tasks, or in situations where the model size is limited.

---

Published in Transactions on Machine Learning Research (09/2022)
In this work, we propose novel optimisation method for non-interpolating problems inspired by algorithms designed for interpolation. Our approach is based on the observation that any non-interpolating problem can be made to satisfy the interpolation property once point that minimises the training objective is known. One simply modifics cach loss to be the point-wise minimum of the loss function and its value at the optimal point. Moreover, one only requires the knowledge of this optimal loss value for every example and not the location in parameter space of the minimiser. Hence, one able to approximate the loss values at an optimal point with reasonable accuracy, one should be able to replicate the desirable characteristics of algorithms such as ALI-G and SPS. Specifically, we will be able to obtain algorithm with a single fixed hyperparameter that is easy to tune, and has strong generalisation performance. We present an optimisation method that approximates the optimal function values online using a heuristic in combination with a Polyak step size. We name our algorithm Adaplive ALI-G (ALIG+), as it makes use of ALI-G iteratively to update the parameters.
We conduct a thorough empirical evaluation of ALI-G+ on variety of tasks against strong basclines. We provide results for matrix factorisation, binary classification using RBF kernels, image classification on the SVHN, CLEAR, Tiny ImageNet and ImageNet datasets, and review classification and next character prodiction. These tasks are designed to provide a mix of non interpolating and interpolating problems, in all cases ALI-G+ outperforms all other single hyperparameter method often by significant margin. These results demonstrate that estimating the optimal loss value online is an effective alternative approach for selecting the step size.
2 Related Works
We discuss existing optimisation methods for supervised learning tasks that do not satisfy the interpolation property. The approaches can be broadly classified into three categories: SGD with manually tuned learning rate schedule, line search methods, and adaptive gradient methods.
SGD with a Learning Rate Schedule. SGD (Robbins & Monro 1951 has been used to produce state of the art performance for supervised learning tasks. However, the downside of SGD is that it requires the manual design and refinement of a learning rate schedule for best performance. Many forms of schedule have been proposed in the literature, including piecewise constant (Huang et al., 2017), geometrically decreasing (Szegedy el al. 2015 and warm starts with cosine annealing (Loshchilov & Hutter 2017). Consequently, practitioners who wish to use SGD in a novel setting need to select which type of schedule to use for their learning task. To that end, they first need to choose the parameterization of the schodule and then tune the corresponding hyprrparameters. For example, a piecewise linear scheme requires an initial learning rate value, decay factor and list or metric to determine at which points in training to decay the learning rate. This results in large search space which increases exponentially in combination with other problem dependent quantities such as regularisation amount or batch size. As SGD can be sensitive to these hyperparameters, and their optimal values often are highly interdependent, the resulting cross-val valdattion scheme necessary for best results can be prohibitively expensive.
Line Search Methods. Line search methods, such as those developed by Vaswani et al. (2019b) Mutschler & Zell ); Hao et al. (2021) offer an appealing alternative to SGD as they remove the need to find a learning rate schedule and instead run extra forward passes to select a step size. While not specifically designed for settings where interpolation does not hold, Vaswani et al. (2019b) present algorithms based around the Armijo and Goldstein line-search methods, classically used for deterministic gradient descent. They also introduce heuristics with the aim of minimising the number of extra forward passes required, which they claim reduces the average number required to one per batch. Mutschler & Zell (2020) and Hao et al. h instcad assume the loss function is approximately parabolic in the negative gradient direction, and thus use extra forward passes to construct a parabolic model of the loss that can then be minimised in closed form. Mutschler & Zell (2020) additionally provide empirical justification for the parabolic approximation. While lino-search mothods present strong performance they invariably introduce extra hyperparameters governing how points are selected in the line search or whether a target point is accepted. While these hyperparanters are held fixed over training and do not require schedule they must be tuned per experiment for best
2

---

Published in Transactions on Machine Learning Research (09/2022)
results. Furthermore, line search methods require approximately twice the computation per batch of typical first order methods resulting in far longer training time.
Adaptive Gradient Methods Adaptive gradient methods such as Adagrad (Duchi et al. 2011 Adam (Kingma& & Bay 2015) or more recently Adabound {Luo al. 2019) use heuristics based on previous gradient evaluations to scale a learning rate for each parameter independently. These algorithms are easy to use as they roquire single fixed learning rate hyperparameter that tends to provide decent results over wide range of values (Sivaprasad et al. 2020). However, once tuned, non-adaptive optinisation algorithms such as ALI- and SGD provide superior generalisation performance over adaptive gradient methods on range of supervised learning benchmarks (Berrada et al. 2020: Wilson et al. 2017).
3 Preliminaries
Loss Function. As standard for supervised learning, we consider tasks where the model is parameterized by w E Rd. We assume the objective function can be expressed an expectation over z E 2, where is random variable indexing the samples of the training set Z:
f(w) - (x))
(1)
Here & is the loss function associated with the sample z. We assume that each & admits a known lower bound B. For the large majority of loss functions used in machine learning, such as cross-entropy or hinge losses, the lower bound is = However, we do not assume this lower bound is reachod during training. In other words, the interpolation property does not hold.
Learning Task. We consider the task of finding a feasible vector w. E Ω that minimisos f:
w. E arg min f(w) + 1
(P)
WEn
where À controls the regularisation amount. We used weight decay for convenience as it allows for simple comparison with hthe algorithms. However, ALI-G+ can easily be used with other forms of regularisation. For unconstrained problems, like those considered in this paper, we set to f = Rd.
The ALI-G Algorithm. ALI-G+ inspired by the ALI-G algorithm (Berrada et al. 2020 hence we formally introduce this method here. ALI-G was designed for the optimisation of interpolating problems, that is, problems where f(w,)) B = 0. This condition also trivially implies that f=(w,, = 0, Vz E Z. In order for the interpolation assumption to hold for (P) when regularisation is used, ALI-G does not apply it in the conventional way, and hence À = 0. Instead, ALI-G makes use of a constraint based regularisation, where the feasible set is defined as Ω = { ww E Rd ||wl||2 r and r controls the regularisation level. In order to ensure that only feasible solutions are found the itcrate is projected back onto the set Q2 after cach parameter update. At time step sample 2,, or in practice a mini-batch, is sampled from Z and the loss and gradient is evaluated at the current interate w.- ALI- then selects w141 as the solution to following the proximal problem:
[1| ||w will + max (0, (wr) + g. (w - w/) 2n
arg min WEn
(2)
where g: Vunfz, (w:) and 1) is the step size hyperparameter. This proximal problem is identical to that solved in closed form by the SGD update, with a minor modification. The problem 2 additionally includes a point-wise maximum between the linear approximation of the loss and the known lower bound (fs(w.) ) = 0).
The dual of (2) is a maximisation over a concave function one dimension constrained to the interval [o. 1].
Hence, one can obtain the optimal point by projecting the unconstrained solution onto the feasible region. After some simplification this results in the following closed form solution:
w1+1 we 7a V (wr))
(3)
7 max min { { n lz (we) Ea (=(w.)
j. }
(4)
| w 2 112
3

---

Published in Transactions on Machine Learning Research (09/2022)
This update can be viewed stochastic analog of the Polyak step size (Polykk 1969) with the addition of maximal value From the interpolation assumption, we have (=w,, = 0, V2 E 2 and hence the numerator of the fraction in 4 can be simplified to l2 (wz). Additionally the maximum with zero is redundant as both numerator and denominator of the fraction will always be positive due to the non-negative nature of the loss function. We show both redundant pieces of notation here as it allows us to clearly specify our modified version in the next section. Additionally in practice ALI-G is often used with a Nesterov momentum term for best results. The ALI-G update computationally cheap with the project on to Zt and the evaluation of the norm of the gradients being the only extra computation required over SGD. Importantly, ALI-G removes the need for learning rate schedule and performs comparably on many benchmarks (Berrada et al. 2020).
4 Training in Non-Interpolating Settings
While the interpolation setting has received a lot of attention, many interesting problems do not satisfy this assumption. This could be for any of the following reasons: i) the model size could be limited due to hardware power constraints, such for embedded devices; it) the data set is very large, for example, the vast majority of models trained on the ImageNet data set (Deng et al. 2009) do not achieve zero training loss; iii) complexity of the loss function, such as in adversarial training; iv) label noise can make interpolation impossible by creating one to two mappings between inputs and labels. Thus, we think this setting is deserving of bespoke optimisation algorithms that are easy to use and produce strong generalisation performance.
Motivation. Our algorithm is motivated by trying to approximate (w.)) online, and as a result recover interpolation. Thus, we introduce scalar th to store estimate for each example in the training set. We refer to these scalars as approximate optimal values (AOVs) and the superscript k indicates how many times the approximation has been updated. Our algorithm alternates between two "steps" i) using the current approximation of the optimal loss & to inform the step size, (see Algorithm []; and ii) improving the approximations based on the best previous iterates, (see Algorithm 2). We describe these "steps" in detail in the following two sections.
Updating the Parameters. ALI-G+ uses the same stochastic version of the Polyak step size as ALI-G [Brradaa al.] 2020), however, we replace the optimal loss value f=(w.) 0 with its current approximation Hence, at time the ALI-G+ algorithm uses the following weight update:
Wi+1 = w: - ngg'.
(5)
7 max min { 17 | Ez,el1 112 }.0).
Lx (wi) 86c
(6)
We define gi é (2 ) + Aw;); where 17 and A are the hyperparameters controlling the maximum step size and weight decay amount, respectively. The loss, AOV and gradient values are average over the batch, see Appendix A for explicit step size formulae for mini-batches. As we do not require the interpolation assumption to hold, make use of weight decay which allows for easy comparison with other algorithms. It is worth noting here that the max with 0 is no longer redundant as there is no guarantce that (wx) (t) will be positive. Without this positivity constraint a negative step size could be used resulting in a gradient ascent step. Moreover le, (w:) is already lower than its AOV Th then we have already completed our goal for this sample in this "step". In the next "step" we can then update this AOV to a lower value, which we describe in the next section. The full procedure for updating the parameters given the AOVs outlined in Algorithm In Appendix B we detail some unsuccessful parameter update schemes.
do not need to use the constraint based regularisation of ALI-G, and can simply
4

---

Published in Transactions on Machine Learning Research (09/2022)
(00)
(a) Increasing an AOV
(b) Deceasing an AOV
(c) Consecutive Decreases
Figure 1: The possible AOV updates of single sample. Thick black line represents AOV values. Blue line depicts &s (w), Thin black line represents previous AOV value, Panel (a) Shows the update if and AOV has not been reached. Panel (b) conversely shows the process for a AOV that has been reached for the first time, the AOV lowered half way to the provious value. (c) For samples that have reach their AOV for consecutive sections the same absolute decrease in value is applied.
Algorithm ALI-G with AOVs
Input: time horizon T, initial point wo, maximum step size n. AOVs et and A.
2: for t = O.... T do
3: Sample E Z, lz (wi), V (wes)
4: Set 7/t max min {n, tx, (.((w))-()
1i =11 }.0}
5: W++1 = w: Pe( (Voo Ez (we) + xwws)
Return w s arg (I.... {f(w)}
Updating the AOVs. To replicate the performance of algorithms for interpolation we want the approx- imation e to tend towards (=(w.) throughout training. Due to the stochastic and non-convex nature of training neural networks it is impossible to guarantee this behaviour. However, we present simple scheme for updating the AOVss that demonstrates strong empirical performance as shown in Section 5 This scheme is inspired by both the curriculum learning literature and the work of Hazan & Kakade (2022), which present a theory for a similar scheme for the convex and deterministic settings. The AOV update scheme is designed to be both reactive and optimistic. By reactive we mean that a spocific sample returns a constant loss its AOV will lend toward this value. By optimisticc we mean that the AOVs are updated to a lower value than the current best loss value for this sample, in the hope that a further decrease in loss is possible. In practice the loss values of specific samples can fluctuate throughout training especially when data augmentation is used. However, the step size is calculated on batch of data, and hence is relatively robust to this noise.
The AOV update scheme is as follows: we store the vectors Eh 1* - ((w) containing (C:, where w = arg mink (O.....?) [f(w))} in memory. The AOVs P pk- are initialised to our known lower bound on the loss B. The training duration is split into K equal sections each with length T. During each of these sections we keep the AOVs fixed and try to get a good estimate of (17) for each example. After each of the K sections we update all AOVs simultaneously. Each AOV is updated depending on whether it has been "reached", that is, if (w) < ēh) is true. In both cases we are optimistic that the loss can be decreased further from its currett value. Hence, if an AOV hasn't been reached it is updated by simply averaging lg (w) and é see Figure (a). This increases this AOV to halfway between the loss at the best point visited and its current value. However, if (f=(1)) < ( we instead try decreasing &h halfway to the last value that was reached - Figure [ (b). If the 2th AOV is reached again in successive sections we reduce &h each time by the same magnitude, see Figure I (c). Thus, even if an AOV incorrectly updated to a value higher than (w.) can casily be correctod by consecutive reductions. Lastly we ensure AOVs are never decreased below the lower bound B. Hence, for non-negative losses AOVs always positive.
E Z,
5

---

Published in Transactions on Machine Learning Research (09/2022)
This scheme can be thought of as defining curriculum for the non-interpolating setting. Rather than first focusing on easy examples, at the beginning all examples are treated equally. After time, examples that are identified as hard are given less importance, and the optimiser does not try to optimise these example further. As we know we cannot achieve zero loss on all sample simultancously makes sense to not focus over the hardest examples. In Appendix B we detail some unsuccessful AOV update schemes.
Algorithm 2 A Algorithm
1: Input: time horizon Tmaz; K = 5, wp and ? 2:
2. = B, 42 E & and X.
2: for epoch A = 1, .... K do
3: Run Algorithm with w Tmar, 1t, 1) and À to obtain w²
4: for E I do
then if (x)) S 2h
th-
6:
7+ f max
B}
2
A + pk+1 pk-
clsc
p++ f- 8t +6
ph
10:
11: Return K
Implementation Details. For the above scheme to work well, it is important that the AOVs are not updated too frequently, as this can lead to them trending towards (=(w) too fast. However, it is also important that the AOVs are updated a sufficient number of times so they can approximate (www), if (=(w).) is large. We find K = provides a good balance between these considerations and fix K to this value. However, ALI-G+ is relatively robust to the choice of K and produces good results for & E [3, 10]. In the Appendix D we provide additional results for K E 10, 10, 20). Furthermore, to save computation we i) avoid calculating f(w,) exactly and instead approximate this online during each epoch and ii) we use w in the place of W in line 3 of Algorithm 2 This results in ALI-G+ having a similar run time to SGD, where the only extra computation is the updating of the vectors ( f 1, ((w) and evaluating the norm of the gradients. As is common practice we report the results of the model with the best validation performance found during training.
Data Augmentation. Data augmentation can be thought of in two ways. First, it increases the size of the data set by adding new examples that are simply transformed versions of others. Second, it makes online alterations to the original number of examples. As ALI-G+ is designed for the optimisation of non- interpolating problems, which often have large data sets, choose to view data augmentation in the second way and save only single AOV for all possible augmentations. When viewing data augmentation in the first way, training regimes where the number of epochs is less than the number of possible transformations would only visit each example less than once on average. Hence, approximating the optimal value would be challenging. Moreover, for many common data augmentation transforms, such as random crops of images, we would expect the optimal loss value be highly correlated between the same example under different versions of the transformation. To support this claim we calculate the loss value of all possible crops for subset of 5000 images chosen from a selection of common data sets. We find empirically, at the start of training that the variance between loss values is on average 20 times lower for the different crops of the same image compared to randomly chosen images. Over training we observe this ratio drops to 5 times lower.
Justification. ALI-G+ shares many similaritics with the ALI-G Algorithm, morcover before the first AOV update these methods use identical descent directions and slep sizes. Thus it is likely one can const a worse case bounds for ALI-G+ similar to those proposed by Berrada et al.] (2020) for settings where & (w.) is bounded above. However the main goal of this paper is to demonstrate the strong empirical performance of ALI-G+ on a broad range of deep learning tasks, where ALI-G+ performs best out of all other single hyperparameter hethods considered.
6

---

Published in Transactions on Machine Learning Research (09/2022)
5
Experiments
In this section we test the hypothesis that Polyak like step size in combination with AOVs can produce high accuracy models in the non-interpolating setting. We investigate this through rigorous experiments comparing ALI-G+ against, a wide range of single hyperparameter optimisation algorithms on a variety of problems The problems include both non-interpolating and interpolating settings. We start with relatively simple problems such as matrix lactorisation and binary classification using RBF kernels. We then consider the training of deep neural networks on popular image classification benchmarks. Here we use small models for two reasons: i) to induce non-interpolation and ii) to be able investigate a wider range of data sets, hyperparameters and baselines. Ideally we would have included results for large models trained on even larger data sets, to ensure none interpolation. However, this was not within the limits of our computational resources. We have tried to perform as thorough a set of experiments as possible and our experimental setup is on par with, in fact often exceeds, prior work in this area of machine lcarning in terms of data sets and baselines considered (Vaswani et al. 2019b Loizou et al., 2021
We show that our approach scales large problems by providing results on the ImageNet data set. Fur- thermore, we do not just show results for computer vision data sets but also for two NLP tasks, highlighting the flexibility of our approach. We include wider section of tasks and optimiaiton baselines than many
casiler works Vaswani et al. (2019b) All experiments are conducted in PyTorch (Paszke et al. 2017 and are performed on a single GPU except for the ImageNet experiments that use two.
5.1 Simple Optimisation Benchmarks
Setting. We first demonstrate the performance of ALI-G+ on matrix factorisation and RBF Binary Clas- sification using the tasks detailed in ?. The matrix factorisation task can be expressed as:
min ExEx [ W2W Ax |x
W1
where X is a data set of 1000 examples drawn from N(: 0, I), A E R10x is randomly generated to have condition number 10 W1 E R 10 W1 E g A. The rank of the factorisation A is selected to be one of four different values resulting in two problems where interpolation holds and two where it does not. The binary classification with radial basis functions tasks use the mushrooms and ijenn dataset from the LIBSVM library of SVM problems (CCang & Lin 2011). The mushrooms dataset satisfies the interpolation assumption, whereas ijenn does not.
Method. We compare ALI-G+ against Parabolic Approximation Line Search (PAL) (Mutschler Zell 2020) and selection of the optimisation methods used in ?. We additionally reuse their code for the baselines. These optimisation algorithms contain collection of strong line search and adaptive gradient methods, all of which do not require learning rate schedule. Additionally, the majority have single step size hyperparameter which makes for fair comparison with ALI-G+
Results. The results of these experiments are shown in Figures 2 and 3 On the non-interpolating tasks (rank and rank 4 matrix factorisation and binary classification on the ijenn data set), ALI-G+ performs comparably to the best algorithms, specifically, PAL [Mutschler & Zell 2020) and SLS (?). On the interpo- lating tasks ALI-G+ fails to minimise the training loss to machine precision like PAL and SLS. However, it attains the same validation performance. which is impressive as ALI-G+ not designed for the interpolation setting. For these tasks using ALI-G would be a better option.
5.2 Image Classification Experiments
Setting. We run experiments on a broad range of image classification benchmarks. Specifically we use the SVHN (etzer et al. 201Th, CIFAR10, CIFAR100 (Krizhevsky) 2009) and Tiny ImageNet data sets. The SVHN and CIFAR data sets are comprised of 32x32 pixel RGB images. For the SVHN data set we use the
1 code available https:/ http:///ghhuuu.om// hal.l//ccooolaaaa--aaa Alasdair P/llg plus

---

Published in Transactions on Machine Learning Research (09/2022)
Rank Factorization
Rank 4 Factorization
Rank 10 Factorization
Thee Model
10-1
Dain Dog.
Taia Loss flog)
(log)
Tala Loss flog).
pal
10
10-1
adum
10-11
10-11
elig
10"1
10
20
40
20
40
20
40
40
Epodus
Epocis
Egocls
Epories
Figure 2: Training performance on the matrix factorisation problem of Vaswani et al. (209b)). In the settings where interpolation does not hold, namely the Rank 1 and Rank 4 problems, ALI-G+ quickly achieves the loss floor. For the Rank 10 and True model problems ALI-G+ does not minimise the loss to machine precision such as SLS (Vaswani et al. 2019b) and PAL (Mutschler & Zell, 2020). Due to the short number of epochs The AOV are updated away from their optimal value of zero before close zero loss is achieved. The update scheme also fails to decreased the AOVs back to this value. However, ALI-G+ still provides rapid optimisation to at worst 10-4
mushroomms
musirrooms
ijeun
ijeun
Viliiaiiinn aArcumyy
1.0
Valtiaiin adocuarr
Trai Less (log)
10
Thain Laxs (log)
10-1
sb
0.8
0.85
adam
10-5
0.6
10
0.80
coin
clig+
0.75
20
20
10
10
Epochs
Epochs
Epochs
Epachs
Figure 3: Training and validation performance on the mushrooms and ijenn data sets CChang & Lin 2011 On the mushroom data set, where interpolation holds, ALI-G+ fails to achieve the same training loss as the line search methods. However, in both non-interpolating and interpolating settings ALI-G+ obtains equally good validation performance the best baseline.
split proposed in Berrada al. (020)) resulting 598k training, 6k validation and 26k test samples. SVHN and CIFAR10 both have classes and CIFAR100 has 100. The Tiny ImageNet data set more challenging and contains 100K training examples of 64x64 pixels split over 200 classes. For the Tiny ImageNet data set report validation scores instead. All
the ground truth labels of the test set are not freely available images are normalised per channel and when data augmentation is used we apply standard random flips and crops. For the majority of data sets we present results with and without data augmentation. The exceptions being SVHN, which is not designed for data augmentation. For all data sets we make use of the cross entropy loss to train a small 8 layer ResNet (He et al. 2016) containing 90K parameters with 16 channels in the first layer. These tasks were chosen give examples of i) interpolation (SVHN); ii) near interpolation (CIFAR10) and iíi) non-interpolation resulting from limited model size (CIFARI00 and Tiny ImageNet).
Method. We compare ALI-G+ against PAL Mutschler & Zell 2020 ALI-G Berrada et al. 2020
AdamP (Heo et al. 2021), SPS [Lizzou et al. 2021], 1 the optimisation methods used in Vaswani et al. (011bb SGD with constant learning rate (SGDConst) and SGD with a step learning rate schedule (SGD (tGDstep)) Step)
SGD benefits from manually tuned learning rate schedule developed by He et al. (2016) while all other methods have at most single step size or maximum step size hyperparameter that is cross validated powers of ten. Hence, SGDstep requires far more tuning and does not provide fair comparison. However, it is included for completeness. For all optimisation ion a algorithms the problem regularisation hyperparameter is selected from E {1-3 3 1-111-000 .0.. ALI-G uses constraint based regularisation, (see section 3
: was se- lectod from r E (50, 100, 200, oo). All other hyperparameters are left their default values. SGD step we use the learning rate schedules detailed in He al. (2016). See Appendix E for more details of hyperparameters used. We reuse the schedule proposed for the CIFAR data sets for SVHN and Tiny ImageNet, redueing the
8

---

Published in Transactions on Machine Learning Research (09/2022)
learning rate by factor of 10 both half way and three quarters through training. A fixed batch size of 128 and an epoch budget of 200 are used for all experiments. As is common for deep learning experiments we accelerate SGD, ALIG and ALI-G+ with a Nesterov momentum of 0.9. SLSPolyak Adam and Adabound also include momentum like terms which we leave at their default scttings. We performed 3 runs for all experiments and report the average performance.
SVHN
Cifar10
Cifar100
Tiny ImageNel. ImageNet
Test Ace (%)
Val Ace (%)
Model
Small ResNet
ResNet18
Data Aug
No
No
Yes
No
Yes
No
Yes
Yes
Step
95.4
84.1
87.6
51.0
59.6
39.8
43.2
71.1
SGDt
94.2
80.6
87.0
49.0
57.3
36.6
41.3
57.5
ALIG
93.8
80.6
86.2
47.5
57.9
35.6
41.8
63.7
SPS
93.9
81.1
86.8
43.7
53.1
20.5
23.8
63.9
Adabound
93.1
75.6
85.2
44.0
55.4
34.2
40.1
62.9
Adam
94.0
79.7
86.0
48.1
56.2
35.9
41.3
62.6
AdamP
93.8
79.9
85.9
47.6
58.2
36.3
41.7
63.5
Coin
92.1
75.5
84.1
42.4
54.0
31.0
36.2
61.5
SLS Armijo
93.0
81.5
85.7
31.6
42.0
11.2
11.1
63.2
S SLSGoldsteia
92.3
78.3
86.4
45.5
57.2
33.0
40.4
62.6
SLSpolyak
93.5
79.8
85.9
43.6
54.0
31.3
38.3
62.7
PAL
94.2
81.5
86.7
39.8
57.0
35.3
40.8
63.6
ALIG+ (K=
95.5
85.0
87.2
56.1
59.4
39.8
42.6
67.8
Table 1: Accuracies of optimisation methods on a selection of standard image classification data sets. The model and dalasel combinations have been chosen include both interpolating and von-inlerpolaling lasks. The standard deviation of the accurocy was most 0.3 for ALI-G+ SGD is the only method to benefit from manually designed step size schedule. All other methods have at most fired step size hyperparameter. On these lasks ALI-G+ oulperforms all other single hyperparameter melhods, oflen by large margin.
Results. The accuracy of the best performing model for each optimisation method is shown in Table On the tasks considered, ALI-G+ does at least well all other line search and adaptive gradient methods. On many tasks it outperforms all other methods by significant margin. The main exception being on CIFAR10 with data augmentation where SGD produced similar test accuracy. The dominant performance of ALI- G+ shows the lack of strong algorithms for non-interpolating settings. The performance benefit of ALI-G+ is most notable when the interpolation property is far from satisfied or when data augmentation is used, For example, on the challenging Tiny Imagenet data set ALI-G+ produces validation accuracy 4% higher than the next best. Empirically significantly faster than Adam, and has curves for ALI-G+ are shown in Figure global step size in Appendix D
observe that ALI-G+ is almost twice fast the line search methods,
time within couple of percent of SGD. Typical training We present results for ALI-G+ with different values of K and a
5.3 Large Image Classification Experiments
Setting. The ImageNet data set (Deng et al. 2009) contains 1.2M large RGB images of various sizes split over 1000 classes. For our experiments we use the following data augmentation. All images are normalised per channel, randomly cropped to 224x224 pixels and horizontal flips are applied with probability 0.5. For validation a centre crop used and no flips are performed. For ImageNet the ground truth labels are not freely available we report validation scores instead. We train a ResNet18 containing 11.7M parameters He et al. 2016). Due to the large number of images and data augmentation the interpolation assumption

---

Published in Transactions on Machine Learning Research (09/2022)
x 10"
Log Step logi
10P
Less
Validation Accurcy
bgg.)
x 100
Moon AOV Value
Toin Apcatacy
80
2x'10
10--
40-
201
10"1
10f
80
120
100
200
0
40
80
120
1000
200
0
40
120
160
200
120 160
200
Eporis
Eponiss
Eporks
Epocus
Figure 4: The black solid lincs show curves produced by training small ResNet on CIFAR100 using the ALI G+ optimiser. Here 7 1.0, À 0.001 and no data augmentation was used. The AOVs are updated every 40 epochs. Until epoch 120 the mean loss is significantly higher than the mean AOV and thus the maximum step size 1j is used for the majority updates. The blue dotted curves show SGD with exactly the same hyperparameters as ALI-G+ except using a learning rate schedule this mimics ALIG+ but with the average step size used for all batches. The large difference in performance between these methods demonstrates the superiority of using step size tailored to each batch. Appendix C we provide additional training curves for ALI-G+ in variely of seltings.
does not hold. We opted to not larger model to computation requirements and to ensure interpolation was not approximately satisfied.
Method. Due to computational constraints for all methods we reuse the best hyperparamnters from Tiny ImageNet for Imagenet. However, the batch size increased to 256 and the epoch budget reduced to 90. For SGDatep use the learning rate schedule described in He et al. (2016). Note, different learning rate schedule is suggested in this setting, again highlighting the weakness of using SGDstep where a good learning rate schedule is not known in advance.
Results. The validation accuracy of each optimisation method is shown in the last column of Table On this task, ALI-G+ outperforms all line search and adaptive gradient methods by at least 3.5%. Additionally, ALI-G+ was significantly quicker to train than two of the next best performing methods. SLS Armijo and PAL took 20 and 12 hours longer to train than ALI-G+ respectively. These results show the advantage of ALI-G+ for training on large data sets over comparable techniques, especially line search methods.
Runtime and Memory Analyses. In Table 2 we include the run time for training a ResNet18 split across two NVIDIA TITAN XP GPUs on ImageNet. ALI-G+'s run time comparable to adaptive gradient methods and faster than line search approaches. During training ALI-G+ requires that an additional 3| floats are stored where |Z| is the size of the training set. This extra memory requirement may seem large, however, in many scenarios 3| is orders of magnitude times smaller than the number of parameters of the model d. For concrete example, when training the ResNet18 on ImageNet, 3/ 2| R 3.8M, however, ResNet18 requires 11.7M floats for the parameters alone, at least 11.7M for gradients and then roughly the same again for storing activations and their gradients. Thus, the extra memory requirement of ALI-G+ is negligible.
Adabound
ALI-G+
AL1-G
Adam
AdamP
SGD
SPS
Coin
SLS
PAL
Optimiser
Time (h)
32
34
33
33
35
35
34
53
47
35
Table 2: Wall clock time for training ResNet18 on ImageNet with various single hyperparameter methods.
Here A ALI-G+ + is as fast as adaplive gradient methods.
10

---

Published in Transactions on Machine Learning Research (09/2022)
5.4 NLP Experiments
Setting. For NLP Experiments we consider two tasks. The first is binary classification of reviews on the IMDB data set using a bi-directional LSTM. The second is the training of a Recurrent Neural Network (RNN) for character-level language modelling on the Tolstoi War and Peace data set which forms part of the DeepOBS benchmark {Schneider al. 2019). The bi-directional LSTM has layer and the RNN has 2 layers. Both models have 128 hidden units per layer. By selecting these models the interpolation property is satisfied on the IMDB data set but not on the Tolstoi data set.
Method. We compare ALI-G+ against the majority of the algorithms used in section 5.2 However, we use slightly modified cross validation scheme; each optimiser's 's step size maximum step size hyperparameter is again cross validated as powers of ten. Following (Sivaprasad et al., 2020) the weight decay amount À was selected from {0.01, 0.001} for the IMDB classification task, and was not applied to biases. For this task a batch size of 128 and an epoch budget of 100 was used. In contrast, no regularisation, batch size 50 and an epoch budget of 150 was used for Tolstoi character prediction.
Results. On the easy 1MDB review classification task large number of the optimisation methods achieved close to zero training loss and similar accuracics. The best performing of these were Adam and ALI-G+ which attained test accuracy of 87.9% and 88.0%, respectively. For the harder character prediction lask using the Tolstoi data set ALI-G+ was the best performing algorithm by over 1%. The full results are shown in Table 3 These results reinforce i) that + consistently achieves highly competitive results in a wide range of settings; and ii) in the non-interpolating setting ALI-G+ is particularly effective.
ALI-G+ (K=10)
ALI-G+ (K=5)
SLSGoldstein
Data Set
SGDoonst
Adabound
SLSArmijo
SLSPolyak
Model
Adam
Coin
PAL
IMDB
LSTM
87.5
82.7
87.9
87.6
73.4
78.6
67.1
85.1
88.0
87.7
Tolstoi
RNN
49.4
41.7
57.9
56.9
30.0
39.0
31.3
52.9
59.7
59.4
Table 3: Test accuracy of single hyperporometer optimisation methods on NLP data sets. For both data sets ALI-G+ is the best performing lask with Adam in a close second. However, on the relatively easy IMDB review classification task large reumber of the optimisation methods achieved close to zero training loss and similar test accuracy.
6 Discussion
We have introduced ALI-G+, an optimisation algorithm designed for sottings where interpolation does not hold. We have demonstrated the effectiveness of ALI-G+ on many standard data sets outperforming a wide range of modern neural network optimisation techniques both in run time and generalisation performance. We now briefly discuss four directions for future work. The first would be to characterise the conditions where ALI-G+ offers provable convergence. The second idca is a modification of ALI-G+ when data augmentation is used. Here, one could make use of a convenient distribution, to model the current spread of & (z()) given by the data augmentation. When updating the AOVs one could then use a lower confidence bound on this distribution. The Third direction for future work is the application of ALI-G+ to distillation where the teacher network could be used generate AOVs for the student. Finally, it maybe possible to combine ALI-G+ with the ideas presented in Paren et al. 2022 to increase it's robustness to its hyperparameters.
11

---

Published in Transactions on Machine Learning Research (09/2022)
References
Leonard Berrada, Andrew Zisserman, and M Pawan Kumar. Training neural networks for and by interpo- lation. International Conference on Machine Learning, 2020.
Chil-Chung Chang and Chih-Jen Lin. Libsvi: A library for support vector machines. ACM Trans. Intell. Syst. Technol, 2011.
Jia Deng, Wei Dong, Richard Socher, Li-Jia Li, Kai Li, and Li Fei-Fei. Imagenet: A large-scale hierarchical image database, Conference on Computer Vision and Pattern Recognition, 2009.
John Duchi, Flad Hazan, and Yoram Singer. Adaptive subgradient methods for online learning and stochastic optimization. Journal of Machine Learning Research, 2011.
Zhiyong Hao, Yixuan Jiang, Huihua Yu, and Hsiao-Dong Chiang. Adaptive learning rate and momentum for training deep neural networks. European Conference on Machine Learning and Principles and Practice of Knowledge Discovery, 2021.
Elad Hazan and Sham M. Kakade. Revisiting the polyak step size. 2022.
Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Deep residual learning for image recognition.
Conference on Computer Vision and Pattern Recognition, 2016.
Byeongho Heo, Sanghyuk Chun, Seong Joon Oh, Dongyoon Han, Sangdoo Yun, Gyuwan Kim, Youngiung Uh, and Jung-Woo Woo Ha. Adamp: Slowing down the slowdown for momentum optimizers on scale-invariant weights. International Conference on Learning Represenlations, 2021.
Xiaowei Huang, Marta Kwiatkowska, Sen Wang, and Min Wu. Safety verification of deep neural networks. International Conference on Computer Aided Verification, 2017.
Diederik P. Kingma and Jimmy Ba. Adam: A method for stochastic optimization. International Conference on Learning Representations, 2015.
Alex Krizhevsky. Learning multiple layers of features from tiny images. Technical Report, 2009.
Chaoyue Liu and Mikhail Belkin. Accelerating sgd with momentum for pre-paraamterized learning. Inter- national Conference on Learning Representations, 2019.
Nicolas Loizou, Sharan Vaswani, Issam Laradji, and Simon Lacoste-Julien. Stochastic polyak step-size for sgd: An adaptive learning rate for fast, convergence. International Conference on Artificial Intelligence and Statistics, 2021.
Πyy Loshchilov and Frank Hutter. SGDR: Stochastic gradient descent with warm restarts. International Conference on Learning Representations, 2017.
Liangchen Luo, Yuanhao Xiong, Yan Liu, and Xu Sun. Adaptive gradient methods with dynamic bound of learning rate. Internotional Conference on Learning Representations, 2019.
Siyuan Ma, Raef Bassily, and Mikhail Belkin. The power of interpolation: Understanding the effectiveness of sgd in modern over-parametrized learning. International Conference on Machine Learning, 2018.
Maximus Mutschler and Andreas Zell. Parabolic approximation line search for dnns. Neural Information Processing Systems, 2020.
Yuval Netzer, Tao Wang, Adam Coates, Alessandro Bissacco, Bo Wu, and Andrew Y Ng. Reading digits in natural images with unsupervised feature learning. Neural Information Processing Systems, 2011.
Alasdair Paren, Leonard Berrada, Rudra PK Poudel, and M Pawan Kumar. A stochastic bundle method for interpolating networks. Journal of Machine Learning Research, 2022.
12

---

Published in Transactions on Machine Learning Research (09/2022)
Adam Paszke, Sam Gross, Soumith Chintala, Gregory Chanan, Edward Yang, Zachary DeVito, Zeming Lin, Alban Desmaison, Luca Antiga, and Adam Lerer. Automatic differentiation in pytorch. NIPS Autodiff' Workshop, 2017.
Boris Teodorovich Polyak. Minimization of unsmooth functionals. USSR Computational Mathematics and Mathematical Physics, 1969.
Herbert Robbins and Sutton Monro. A stochastic approximation method. The annals of mathematical statistics, 1951.
Frank Schneider, Lukas Balles, and Philipp Hemnig. DeepOBS: A deep learning optimizer benchmark suite. International Conference on Learning Representations, 2019.
Prabhu Teja Sivaprasad, Florian Mai, Thijs Vogels, Martin Jaggi, and Francois Fleuret. Optimizer bench- marking needs to account for hyperparameter tuning. International Conference on Machine Learning, 2020.
Christian Szegedy, Wei Liu, Yangqing Jia, Pierre Sermanet, Scott. Reed, Dragomir Anguelov, Dumitru Erhan, Vincent Vanhoucke, and Andrew Rabinovich. Going deeper with convolutions. Conference Computer Vision and Pattern Recognition, 2015.
Sharan Vaswani, Francis Bach, and Mark Schmidt. Fast and faster convergence of sgd for pee-pparaeterriee models and an accelerated rerceptron. International Conference Artificial Intelligence and Stalistics, 2019a.
Sharan Vaswani, Aaron Mishkin, Issam Laradji, Mark Schmidt, Gauthier Gidel, and Simon Lacoste-Julien. Painless stochastic gradient: Interpolation, line-search, and convergence rates. Neural Information Pro- cessing Systems, 2019b.
Ashia C Wilson, Rebecca Roclofs, Mitchell Stern, Nati Srebro, and Benjamin Rocht. The marginal value of adaptive gradient methods in machine learning. Neural Information Processing Systems, 2017.
A Mini Batch Step-Size
In this section we detail the step size formulae O6 when a applied a mini-batch. We define the set of indexes 2 of the example selected with in the batch time B., With this notation |B.| denotes the batch size. The loss values, AOV's and gradients are simply averaged over the batch.
# max min { E.E,, 1e. (w:) { 1..
}.0]
{", [E V Vwlzz
(8)
B Unsuccessful Approaches
In this appendix we briefly introduce so unsuccessful ideas for both the Algorithms g and
Parameter Updates A idea experiments with for Algorithms I was defining and augmented loss function f. as the point-wise maximum of the 2th loss function and its relevant AOV, specifically:
E. (w) A max (l, (w
(9)
This augmented loss function would then be used in the following parameter update:
wi+1 w. E.,E, /V W (wi)).
(10)
E,, 16,,, (w) - Pg] 2o max min n: [[ (w 1 j.0).
(11)
13

---

Published in Transactions on Machine Learning Research (09/2022)
where B, is the of indexes 2 of the example selected with in the batch at time This formulation excluded loss functions & that had reached their AOV both in the step size calculation and the descent direction. This had the effect to focus on examples that had not yet reached their AOV, while at first this might sound desirable, in the non-interpolation sctting it counter productive. In this setting it is given we can't achieve zero loss on all sample simultaneously, hence focusing on the hardest samples are detrimental when trying to minimise the mean loss.
AOV Updates The AOV increase in lines 9-10 in Algorithm 2 was inspired by Hazan & Kakade (2022)
and we did not try alternate schemes. For the AOV decrease 6-7 in Algorithm 2 we initially tried back tracking to the previous AOV that had been reached rather than half way. We found this worked slightly worse in practice as resulted in the AOVs oscillating more.
C Additional Plots
In this section provide a variety of training curves produced by ALI-G+ in a number of settings. We the SVHN data set where interpolation holds, see Figure 5. The next few plots detail runs of ALI-G+ on the slightly more challenging CIFAR100 data set. In Figure 6, in contrast to f we show the behaviour of ALI-G+ both without data augmentation. In Figure we show 5 is preferred. Finally, we show the behaviour when using ALI-G+ to train a ResNet18 (He et al. 2016 on the ImageNet data set.
start by showing ALI-G+ 's performance
training curves when = 10 to highlight why
Mean Log Sxpp Size kg
10"
Log Loss log(f)
109
Less
Mean AOV Value
10
Thin Accuzary
80
Valiaatoon Accurscy
80
10
60
60
40
80
121)
160
200
80
120 Epochs
160
2000
80
120
160
2000
41
800
123
160
200
Epochs
Epachs
Epoths
Figure 5: Curves produced by training a small ResNet on the SVHN data set Netzer et al. ALI-G+ optimiser. These results were produced with 7 = 1.0, 10-3 No data augmentation was used as is standard for SVHN. The AOVs were updated every 40 epochs. The maximum step size rj is selected for the first 80 epochs. At epoch 80 the AOVs are increased was followed by sharp decrease in loss value over the next 20 epochs. This, in turn, results in the mean step size dropping further and becoming zero for many batches. At epoch 120 the mean AOV value was significantly higher than the mean loss value f_(wū)) resulting in the majority of AOVs being decreased in value during the update. The updated AOV values resulted in the maximum step size being selected again for most batches. This causes the loss to increase sharply. Finally, at epoch 160 the AOVs are increased again resulting in similar behaviour to epoch
2011 with the
point where the mean step size decreases. This
14

---

Published in Transactions on Machine Learning Research (09/2022)
x 10"
Log, Stop Sioe log
10"
Loss
Valedesion Accaredy
Log log(f)
x 100"
Moon AOV Value
Thain Accuray
500
2x100 10'
10"1
-0-
80
30
10
10"3
20-
40
50
120
100
200
0
40
80
120
100
200
0
40
120
160
200
120
160
200
Eportas
Eponiss
Eporks
Epocus
Figure 6: Curves produced by training a small ResNet on CIFAR100 data set (Krizhevsky 2009 with data augmentation with the ALI-G+ optimiser. These results were produced with v 0.1, X 10-3 The AOVs are updated every 40 epochs. The maximum step size r is selected for the majority of batches during the first 120 epochs. For the remaining 140 epochs the step size was tailored to each batch.
x 10"
Mear. Log Step log(ov)
Loss log(f))
3''
Loss Mosn AOV Value
Train Accuracy
60
Vanidction Aocurazy
80
2 10P
800
30
108
20-
20
120
120 200
Epocis
Epochs
Epochs
Epochs
Figure 7: Curves produced by training small ResNet on CIFAR100 data set Krizhevsky 2009), again with data augmentation with the ALI-G+ optimiser, however, we set (K = 10). These results were produced with 7 = 1.0, A = 10-4. The AOVs are updated every 20 epochs. The maximum step size is selected for the majority of batches during the first 60 epochs. For the last 140 epochs the step size was tailored to each batch. However, the accuracy does not improve significantly during the last half of training. Due to the rapid AOV updates the mean AOV stabilises at suboptimally high value. This results in small step sizes being used average and thus little progross is made for the remaining of the training period. This results in K = 10 achieving slightly worse accuracy than when K = 5. Empirically we find k = 5 provides good results for all settings considered.
Log Shep log he)
10
1x100 10"
Lrzes
Validation: Accurrrr
Loss in
3 100
Meam
Value
10-1
Train Accuracy
60
60
My /4/er
50
2x
40
109
10
30
72
72
Epochs
Epochs
Rpoohs
Fpochs
Figure 8: Curves produced by training ResNet18 on the ImageNet data set Deng et al. 2009
with data
augmentation with the ALI-G+ optimiser. These results were produced with 1.0, A are updated every 18 epochs. The maximum step size rj is selected for the majority of batches during the first 36 Epochs. For the remaining 54 epochs ALI-G+ tailors the step size to each batch.
10
The AOVs
D Additional Results
In this appendix we provide results for modified versions of ALI-G+ applied many the image classifi- cation tasks detailed in Section 5.2 of the main paper. We state result for additional different values of
15

---

Published in Transactions on Machine Learning Research (09/2022)
K and for two version of ALI-G+ that use global step size instead of per sample step size. These steps sizes are detailed below. The global AOV f that aims to approximate f+ is updated using the equations in Algorithm 2 with the the point wises estimates la (w) replaced with their global versions f(w).
Global + variant 1 (GALIG1+)
B Σ (ree((((r)) -
N
max
min 1/s
1Eeel [ 22111 1 1.00.
(12)
Global ALI-G+ variant 2 (GALIG2+)
[ EeeBles, (wi) fk0 min 17, E2esl Vio 221 9.0).
7.0)
N - max
(13)
Results Table details the results of these experiments. ALI-G+ performs best for K E {5, 10), with the accuracy's falling away as K is increase or decreased outside this range. GALIGI+ performs similar to ALI-G+ which indicates that using single global AOV could be sufficient in these settings. This could be promising direction for future work that would reduce the memory foot print. GALIG2+ performs slightly worse than both ALI-G+ and GALIG1+. This suggests in practice mixing batch-wise and global estimates of the loss in the step size should be avoided, however further investigation is needed.
SVHN
Cifar10
Cifar100
Tiny ImageNet
ImageNet
Test Acc (%)
Val Acc (%)
Model
Small ResNet
ResNet18
Data Aug
No
No
Yes
No
Yes
No
Yes
Yes
ALIG (K
93.7
80.8
86.2
47.5
57.9
35.6
41.8
63.7
ALI-G+ (K =
95.4
84.8
86.5
54.6
57.4
36.1
41.4
ALI-++ (K =
95.5
85.0
87.2
56.1
59.4
39.8
42.6
67.8
ALI-G+ (K = 10)
95.0
85.0
86.8
56.6
58.0
39.9
42.3
67.1
ALI-G+ (K 20)
94.8
83.8
85.9
54.5
56.0
38.9
40.8
65.1
ALI-G+ (K 5)
95.5
85.0
87.2
56.1
59.4
39.8
42.6
GALIGI+ + (K 5)
95.5
84.4
87.3
56.2
59.4
40.4
42.6
GALIG2+ (K 5)
94.8
84.5
86.3
56.0
56.9
35.5
41.3
Table 4: Accuracies for ALI-G+ with K = 5, K = 10 and K = 20 on selection of standard image
classification data sets. ALI-G+ with K = 10 offers comparable results to K = 5, however, when K is increased to K 20 the performance becomes noticeably worse. We additionally show two results for ALI- G+ with a global step size.
16

---

Published in Transactions on Machine Learning Research (09/2022)
E
Hyperparameters
In this appendix we give great detail on the hyperparameters used in Section 5.2
Optimiser
Step-size
Regularisation
SGD Step
No {0.1, 0.01)
wd e {0, 10,11-5.00 1,-,,,,, 3
SGDeonst
1) {0.1, 0.01
wd {0, 1-
}
ALIG
Tmaz E 0.01,
ré (0,50, 100, 200,
SPS
Mmaa E 10,
l2 e (0,155,1--111111
Adabound
7) E (0.01,0.001)
e (0,100,1,,1-1111
Adam
7 0..01,
wd =0,
AdamP
7 E {0.01.0.001)
w (0,1-5,1-1.
Coin
N/A
6 (0,1--1111
SLS SLSArmip
Armijo
N/A
E (0,1 (0.155,1-11
S SLoGoddstein
Mmaz E {1,10)
82 E (0, (0.15,,1-11
S SLS Polyak
N/A
l2 E (0, (0,1-5,1-4
PAL
Mmaz E {1,
l E (0,1
ALI-G+
Tmaz 00.10
wd {0,1
Table Hyperparameters cross-validated the ezperiements in Section 5.2 perparometers were left at. the default values specified by the official authors implementation Coin, AdamP, ALIG, Adabound) or the PyTorch implentaiton (SGD, Adam).
All other hy-
17


Reviews:
[{"review_id": "jvxiIf5JBk", "reviewer": "Reviewer_qwHd", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "### Strengths\n+ General flow of the paper is good; sections like reintroducing ALI-G is appreciated  \n+ Empirical evaluation with multiple problem types stands out, and is comprehensive enough for this kind of study \n+ Well written in general without many minor errors\n+ Overall, for non-interpolating settings, results seem promising\n\n### Weaknesses\n- Are there other methods to estimate optimal loss?\n- Main comparison is with other single parameter methods; but adaptive multi-parameter methods are as easy to implement in practice and should be included, at least as a separate section/discussion. \n- Currently while updating AOVs, if the target loss value has not been reached within the K'th section of training, it is updated to a half-way point. This seems quite arbitrary; I agree that the general motivation is correct - that in either case (in Algo 2), you want loss to continuosly decrease, but why should l^{k+1} be the half-way point and not l^k + some other \\eps ? Can you discuss the reasoning behind this\n- How fast is \"too fast\" for trending towards optimal loss. How do you threshold/measure this? As an initial answer, running in the [5,10] range and additional K values work, but is this true for all problems - \"ALI-G+ is robust to the choice of K\"\n- Worst case bound using ALI-G is actually a good idea in this case. Does ALI-G+ perform better always? Can you comment in the justification section above Section 5\n- For Figure 1 - ALI-G+ underperforms compared to SLS and PAL for higher rank problems. \"However it still provides rapid optimization to at worst 10^-4\" seems like a digression to the main conclusion. Even iterations to reach 10^-4 is better in the case of PAL and SLS. Does K affect this? Can you do more updates initially? Of course, this might introduce another parameter\n- Again for Figure 2 - saying it approaches the same val loss seems like a way to explain out of \"ALI-G+ fails to achieve the same training loss as the line search methods\". Are you only testing for validation performance throughout or training performance as well?\n- \"Adam and Adabound also include momentum like terms which we leave at their default settings.\" - what are these settings and how may these affect your results?\n- Earlier the claim was that ALI-G+ is \"robust\" to choices of K. Seems like reducing K helps from the results as mentioned in the caption of Table 1. What if you reduce it further to (1,5] ? Abstract/intro can be changed to acknowledge this understanding", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "The overall motivation is to use a stochastic variation of Polyak step sizes introduced via the use of ALI-G algorithm without prior information on how the optimal loss looks, so that there is no need for designing the LR schedule. ALI-G+ uses ALI-G to iteratively update parameters.\n ", "claims_and_evidence_yn": "", "claims_explanation": "", "audience_yn": "", "audience_explanation": "", "requested_changes": "- Address questions mentioned above in the paper, or through discussion\n- Confirm if experiments are representative of results you want to show, particularly:\n\n1. poor training performance on some problems needs to be addressed without explaining around these deficiencies (like reaches 10-4 faster, or validation performance is as good)\n\n2. Some of the assumptions need to be explained (like K value, updating l to halfway point, using default settings for Adam etc., and not choosing other schedulers for SGD)", "broader_impact_concerns": "None", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "jgoWk6SELU", "reviewer": "Reviewer_XcC6", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n- Clear motivations and preliminaries.\n- Experiments are performed on various domains, and achieving good results. \n- The hyperparameter is very simple (just $K$, the number of updates to the lower bounds, and $\\eta$ maximum step size allowed). \n\nWeaknesses:\n- The hyperparameter $K$'s role is under-explored. The algorithm would become ALI-G when $K = 1$ (i.e., using the lower bound to run the entire algorithm), yet in most cases ALI-G+ with K=5 has the best performance. Why not consider $K = 2, 3, 4$?\n- The results are mostly demonstrated on very small networks. The deepest model in the image classification task is with ResNet18, and these are quite small compared to what are commonly used in practice; as a result, the accuracy numbers are pretty far from state-of-the-art, making it harder to gauge the usefulness of ALI-G+ with larger models. \n- There are superior baselines, such as SGD with cosine scheduling or K-FAC that are not compared against. The degree of freedom of cosine scheduling is actually smaller (as it only requires total number of iterations, whereas ALI-G+ needs an additional $K$ with the total number of iterations).\n- The method actually does not perform any preconditioning, which seems to be a bit weaker than methods that try to approximate Gauss-Newton.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "The paper introduces ALI-G+, which extends the ALI-G optimizer for cases where the optimal objective value is not assumed to be a certain value (like 0). The key idea is to use existing statistics to approximate the optimal objective value (Algorithm 2), and then apply the same algorithm as ALI-G. Experiment results are demonstrated on several settings such as matrix factorization, image and text classification, and language modeling. ", "claims_and_evidence_yn": "", "claims_explanation": "", "audience_yn": "", "audience_explanation": "", "requested_changes": "**Suggestion**: It would be nice to have a toy experiment that shows having an AOV that is higher (and possibly closer to the ground truth) than the guessed one is better. If our AOV is too small, the worst case scenario seems to be using the largest learning rate? \n\n**Critical**: This bring us to another concern, which is about the largest learning rate hyperparameter. I don't think the paper discusses the $\\eta$ hyperparameter of ALI-G+ in detail, other than in Figure 3. This seems quite important to all other optimization methods and is a \"make-or-break\" decision. In fact, Figure 3 seems incorrect, as y axis indicates the log of largest learning rate is $10^0$. Common SGD methods would start with a learning rate of $0.1$ -- why is this not always chosen in ALI-G+?\n\n**Critical**: The experiments are mostly done on very toy settings, and the performances are nowhere near state-of-the-art, or even some common models that can be used (like ResNet50). Even a few years ago, we have achieved over accuracy of 90% on CIFAR-10 and 80% on CIFAR100, and here the results are significantly worse. It is hard to identify whether the superior results in ALI-G+ translate to these settings, and it would be nice to have some supportive evidence. The only one closer to a large model is ResNet18 on ImageNet, where SGD step is already better by a large margin. \n\n**Suggestion**: Section 4 can be difficult to understand, and it would be nice to have a figure showing the intuition behind the heuristic. ", "broader_impact_concerns": "N/A", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "wPwBJvJl8R", "reviewer": "Reviewer_LejS", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "**Strengths**\n\n- The idea of using ALI-G and estimating the optimal loss values is novel.\n- Experiments are extensive. It includes many tasks, not just image classification. It also includes many relevant baselines.\n- The proposed method yields better performance in terms of generalization ability than many single-hyperparameter optimizers, which includes SGD with momentum, Adam, and SLS and PAL (well-performing line search methods).\n- Computational overhead of ALI-G+ is slight compared to SGD, and better than adaptive optimizers and line search methods.\n\n**Weaknesses**\n\n- The exact algorithm for approximating the optimal loss values is a bit ad hoc. There must have been other approximation schemes. Why was this specific method chosen?\n- The method introduces an additional hyperparameter $K$. Though the authors fixed this to be 5 for all the experiments, it still affects the performance of the method. Was there a reason why the number of times to update the loss values is chosen as a hyperparameter instead of the number of steps to use the fixed loss values for ($\\frac{T}{K}$ in this case)? It seems like the latter makes more sense, since the best value for $K$ must depend on the total number of steps $T$.\n- ALI-G performs worse than SGD with a tuned learning rate schedule. This means that practitioners who want to achieve the best results with ample budget to tune would still prefer to use an optimizer that can be used with a schedule (gives more flexibility).\n\n", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "- This paper proposes a novel optimization algorithm that modifies an optimizer designed to be used in the interpolation setting, such that it can be used in the non-interpolation setting. The resulting optimizer is called ALI-G+, as it builds upon ALI-G. In ALI-G’s update rule, there is a term that corresponds to the loss value of the optimal model, which can be set to the known lower bound in the interpolation setting. ALI-G+ uses the same update rule, but aims to estimate the loss value of the optimal model for each sample in the training set, since the loss doesn’t reach its lower bound in the non-interpolation setting.\n- The loss values are estimated to approximately track the loss value corresponding to the best model so far.\n- Experiments on a variety of different problems ranging from matrix factorisation to image classification, covering both the interpolation and non-interpolation setting, ALI-G+ is shown to consistently perform better than all considered single-hyperparameter optimizers. \n\n\n", "claims_and_evidence_yn": "", "claims_explanation": "", "audience_yn": "", "audience_explanation": "", "requested_changes": "**Major points**\n\nSection 4 is hard to parse. Important details are not mentioned or highlighted enough. More specifically:\n- Is there a different learning rate per sample in a minibatch? If so, the notations in Equation 6 makes this unclear since $\\ell_{z_t}$ is subscripted with $z_t$ while $\\tilde{l}^k_z$ is subscribed with $z$. If not, how exactly is the learning rate computed?\n- If weight decay is applied directly instead of projecting into a constrained set as in ALI-G, doesn’t this change the objective function, and therefore the derivation of the update rule (Equation 3 and 4)?\n- How exactly was $\\bar{\\mathbf{w}}$ determined in Algorithm 1? How was $\\mathbf{\\ell}(\\bar{\\mathbf{w}})$ computed? It seems expensive to compute the losses for all samples.\n- In Algorithm 2, why is the “has been reached” case (lines 6-7) different from the “hasn’t been reached” case (lines 9-10)? If we want to decrease the loss values, why are we averaging with the previous loss values? What if the previous loss value is higher? What exactly is the purpose of line 7 as opposed to line 10? Have the authors tried different variants of the update rule for Algorithm 2? It would be informative to include those results in the experiments.\n\nAuthors should include the exact ranges and increments of the tuned hyperparameters for the different optimizers in a table.\n\nIt doesn’t seem too much of an overhead to perform 3 runs for the baseline methods. I think it’s only fair to do this when it’s done for ALI-G+.\n\n\n**Minor points**\n\n- The experiments use unrealistically small models. For example, ResNet-18 seems too small to be used for ImageNet. It would be nice to see bigger models like ResNet-50 or Vision Transformers.\n- In the introduction: “One simply modifies each loss to be the point-wise maximum of the loss function and its value at the optimal point.” Did the authors mean point-wise minimum?\n- Page 2 when the authors cite Adam, the citation is wrong (should be Kingma & Ba instead of Kingma & Welling).\n- Page 3: “In order for the interpolation assumption to hold for (P)...” is this a typo? What is P?\n- Page 3: “hence the numerator of the fraction in (3)” -> should be (4)\n- Page 6: “update these methods use identical descent diration and …” typo in diration -> direction.\n- I feel like the whole Justification section in page 6 could be removed, since the authors did not construct a worse case bound.\n- In section 5.1, ALI-G isn’t included in one of the baselines. Why?\n- Figure 2: I think it makes sense to make the range of the y-axis smaller for the second and fourth plot.\n- Page 7: “For the Tiny ImageNet dataset the ground truth labels are not freely available” do the authors mean the test set is not available?\n- Page 8: “For SGD we use the learning rate schedules…” -> “For $\\text{SGD}_\\text{step}$.\n- Why was weight decay not used for the biases for the IMDB experiments, and why was regularization not used for the Tolstoi experiments?\n- Table 3 second column should be labeled Tolstoi instead of IMDB\n", "broader_impact_concerns": "There doesn’t seem to be any ethical concerns in this paper.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "rnIMb74pvu", "reviewer": "Reviewer_JZit", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n- Well-written\n- Preliminaries that introduces reader to context and prior work.\n- Good motivation: non-interpolating methods are often used in large-data settings\n- Interesting method: estimating pointwise losses online, and using them for optimization, is an idea that has not been explored thoroughly in prior work\n- Extensive experiments on a wide variety of settings (including both DNN and non-DNN)\n\nWeaknesses:\n- Some of the experiments (specifically the vision-tasks) appear to somewhat over-claim the performance of the new method. Specifically, in Table 1, ALI-G+ is claimed to be the best \"single hyperparameter\" method. However, this restriction to \"single hyperparameter\" methods is both artificial (since even ALI-G+ uses L2 regularization, some choice of batch-size, choice of epochs, etc), and not thoroughly explored. For example, SGD with cosine LR decay is \"single hyperparameter\" in the terminology of this paper, and is very competitive for CIFAR – but not included in Table 1.\n- Figure 3: Showing the blue dotted line as SGD with the \"average step-size of ALIG+\" seems a bit unfair. Since ALIG+ actually uses a *constant* stepsize until Epoch ~120, it would be more fair to compare against SGD with this constant stepsize.\n- The \"AOV update scheme\" is somewhat ad-hoc, and there is not much discussion into why this rule was chosen, and the effect of alternate update rules.\n- The experimental results show top-line accuracies, but there is little investigation/ablations into what factors in ALIG+ contribute to its performance. For example, how important is it that we keep track of pointwise losses, instead of a uniform lower-bound for all points?\n- There is no code provided (AFAIK). Including code in the final submission, especially for optimizer contribution, will make this submission both more reproducible and more impactful.\n", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This work proposes a variant of a certain adaptive step-size algorithm (ALI-G), which is applicable to non-interpolating settings. The ALI-G optimizer from prior work was a variant of Polyak step-size / Newton-Raphson, and thus only applied to settings where the optimal loss is 0 (or is known).\nThis paper extends the optimizer by introducing a heuristic estimation of the optimal-loss per-sample, which enables stochastic optimization for non-interpolating settings (e.g. with large data sizes or small model sizes). They conduct fairly extensive empirical studies showing that the new optimizer is competitive in modern settings.\n\nI recommend acceptance to TMLR.", "claims_and_evidence_yn": "", "claims_explanation": "", "audience_yn": "", "audience_explanation": "", "requested_changes": "Suggestions which do not affect the score:\n- I wonder if the learned pointwise losses are related to the \"difficulty\" of individual samples. I expect they will be; it could be interesting to engage with the \"example difficulty\" literature.\n- I suggest clarifying how ALI-G handles mini-batching. (eg: is there a \"batch AOV\" that's the average of the sample-AOVs?)\n- It would be informative to plot the \"effective step size\" \\gamma_t chosen by ALIG+, as a function of time T. This would clarify how ALIG+'s adaptive step size schedule differs from other standard choices (step-wise decay, cosine decay, etc).\n", "broader_impact_concerns": "N/A", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "lJndvSURRT", "reviewer": "Reviewer_DvfA", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths\n- There are a relatively large number of experiments on different problems and data modalities.\n- The proposed algorithm is efficient in terms of its time and memory overhead compared to standard SGD.\n\nWeaknesses\n- No convergence guarantees are provided. \n- It's unclear how well the baselines were tuned, since the authors provide their own results with previous methods rather than comparing against published results. \n- While ALIG+ does not seem worse than previous methods, there aren't many cases where it is obviously better.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "The paper’s main contribution is a new optimization algorithm called ALIG+. This method is a modification of the original ALI-G algorithm for interpolating problems. ALI-G requires that the optimal loss value is known a priori, whereas ALIG+ uses a heuristic to estimate the optimal loss value. While no convergence guarantees are provided, the authors do not claim this as a contribution. Instead, they focus on large scale empirical evaluation of the optimizer against previous methods on a variety of tasks. The authors claim that ALIG+ has similar walk-clock time to SGD and provides competitive generalization results.", "claims_and_evidence_yn": "", "claims_explanation": "", "audience_yn": "", "audience_explanation": "", "requested_changes": "- The discussion of SPS from Loizou et al., 2021 is confusing. It's not clear to me exactly where interpolation is required in that work. Indeed there is Assumption 2.1, but this is not interpolation. Can the authors comment on this?\n- The accuracies obtained on Table 1 are generally quite low. For example, less than 90% on CIFAR10 with data augmentation is very far from SoTA. I understand that the model size is limited to avoid interpolation, but is there any other reason for this?\n- This is particularly concerning since Loizou et al., 2021 report accuracies of >92% on CIFAR10 and >72% on CIFAR100 using SLS and SPS.\n- How is the bolding chosen in Table 1? Currently it's very misleading. The entire ALIG+ K=5 row is bold, but frequently it does not actually achieve the best accuracy on the task. The authors also admit a standard deviation of ~0.3, which would mean several of the confidence intervals would be overlapping.\n- I'm confused about the purpose of Fig. 3. Why is the correct comparison to use the same hyperparameters for SGD that were tuned for ALIG+?", "broader_impact_concerns": "N/A.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: The paper proposes a optimization technique extending ALI-G to non-overparametrized regime, named ALI-G+. This paper is well written and motivated, with results in this restricted setting promising enough to appeal to the audience of TMLR. With reviewers' feedback, the authors have clarified the submission and added new experiments to strengthen it. Therefore, along with the majority of the reviewers, I recommend this paper for acceptance.
Decision: Accept (poster)