Random Function Descent
Authors: Felix Benning
Leif Döring
Venue: NeurIPS 2024 poster (2024)
Keywords: optimization
hyperparameter tuning
Gaussian processes
random functions
random fields
average case analysis
bayesian optimization
Primary area: optimization
TL;DR: Grounding step size heuristics in average case analysis.

Abstract: Classical worst-case optimization theory neither explains the success of optimization in machine learning, nor does it help with step size selection. In this paper we demonstrate the viability and advantages of replacing the classical 'convex function' framework with a 'random function' framework. With complexity $\mathcal{O}(n^3d^3)$, where $n$ is the number of steps and $d$ the number of dimensions, Bayesian optimization with gradients has not been viable in large dimension so far. By bridging the gap between Bayesian optimization (i.e. random function optimization theory) and classical optimization we establish viability. Specifically, we use a 'stochastic Taylor approximation' to rediscover gradient descent, which is scalable in high dimension due to $\mathcal{O}(nd)$ complexity. This rediscovery yields a specific step size schedule we call Random Function Descent (RFD). The advantage of this random function framework is that RFD is scale invariant and that it provides a theoretical foundation for common step size heuristics such as gradient clipping and gradual learning rate warmup.

Random Function Descent
Felix Benning University of Mannheim felix. wwwningguni -manuuhmimmmmneinnn .m.
Leif Döring
University of Mannheim
leif www.iiignnnnin. -aatemmi--mmmmmeeeee -mannheim, de
Abstract
Classical worst-case optimization theory neither explains the success of optimiza- tion in machine learning, nor does it help with step size selection. In this paper we demonstrate the viability and advantages of replacing the classical 'convex function' framework with a 'random function' framework. With complexity O(ndd3) where is the number of steps and the number of dimensions, Bayesian optimization with gradients has not been viable in large dimension so far. By bridging the gap between Bayesian optimization (i.e. random function optimization theory) and classical optimization we establish viability. Specifically, we use a 'stochastic Taylor approximation' to rediscover gradient descent, which is scalable in high dimension due to (nd) complexity. This rediscovery yields specific step size schedule we call Random Function Descent (RFD). The advantage of this random function framework is that RFD is scale invariant and that it provides a theoretical foundation for common step size heuristics such as gradient clipping and gradual learning rate warmup.
Introduction
Cost function minimization is one of the most fundamental mathematical problems in machine learning. Gradient- praddeet-bbsed methods, popular for this task, require a step size, typically chosen using established heuristics. This article aims to deepen the theoretical understanding of these heuristics and proposes a new algorithm based on this insight.
Classical optimization theory uses T-smoothness, which limits the rate of change of the gradient by L, to provide some convergence guarantees for learning rates smaller than 1/L [c.g. 38J. As this theory is based conservative than necessary on average. Even if L was known, this learning rate would therefore be impractical. Since line search algorithms typically require access full cost function evaluations, the field of machine learning (ML) therefore relies heavily on step size heuristics [e.g. 48, 49, 42, 20]. To investigate these heuristics, introduce ideas based on 'random function' perspective.
upper bound (the worst case), the learning rate L/L is naturally much more
While automatic step size selection in the convex function framework is possible [11], convexity is generally only satisfied asymptotically and locally. So the understanding of the initial stages of optimization, which includes the warmup heuristic [20], greatly benefits from a framework which also admits non-convex functions. This objective is achieved by the 'random function' framework we investigate.
Many successful algorithms in computer science are significantly slower in the worst case than in the average case based on probabilistic framework (e.g. Quicksort [23] or the simplex algorithm [e.g. 6l). On random quadratic functions the average case behavior of first order optimizers is already being investigated by the ML community [e.g. 58, 43, 33, 12, 9, 40, 41]. Interested in the landscape of high dimensional random functions as a model for 'spin glasses', the physics community independently started studying the average case optimization well [e.g. 4, 15, 37, 51, 24], albeit not geared for ML algorithms.
38th Conference on Neural Information Processing Systems (NcurIPS 2024).

---

Average case analysis fundamentally requires a prior distribution over possible cost functions. The evaluations seen so far then result in posterior over the cost of other parameter inputs. Using this posterior for optimization is called "Bayesian optimization" (BO) [e.g. 32, 47, 16, 2], which is best known in the context of low dimensional optimization (e.g. hyperparameter tuning) in the MI. community. BO is treated like a zero order method for low dimensional problems due to the (n²) complexity for the covariance matrix inversion of the n evaluations seen so far, which increases to Onn' df) when gradient information is included [e.g. 35, 55J, where d is the input dimension of our cost function. This limits classic BO to relatively small dimensions even under sparsity considerations [e.g. 45, 39].
While the BO algorithms developed in the 'random function framework' might not have been viable in high dimension so far, due to their computational complexity, this framework is already used to explain the high relative frequency of saddle points in high dimension [10] and to explain the highly predictable progress optimizers make on high dimensional cost functions [5]-
In this work we bridge the gap between BO and (computationally viable) gradient based methods, derived from the first Taylor approximation, with the introduction of a stochastic Taylor approximation based on forgetful BO posterior. The optimization method "Random Function Descent" (RFD), resulting from the minimization of this stochastic Taylor approximation, coincides with a specific form of gradient descent which establishes its viability in high dimension. The advantages of its BO heritage are scale invariance and an explicit step size schedule, which illuminates the inner workings of step size heuristics such as gradient clipping [42] and gradual learning rate warmup [20].
Our contributions and outline The main goal of this paper is to demonstrate the viability and advantages of replacing the classical "convex function" framework with a "random function" frame- work. Theorem 4.2 is the main theoretical result establishing viability (computatability and scalable complexity) for given covariance model. Section is concerned with practical estimation of the covariance model and viability is demonstrated with practical example in the MNIST case study (Section 7). The advantages of this approach are scale invariance (Advantage 2.3) and an explicit step size schedule, which does not require expensive tuning and explains existing MI. heuristics such as warmup (cf. Section 5.2). This explanation of the initial stage of optimization could never be delivered by the convex framework, because the convexity assumption is not fulfilled initially so can at best explain asymptotic behavior.
Sec. We motivate a stochastic Taylor approximation and RFD and prove its ecale-invariance
Sec. 3 We briefly motivate and discuss the common distributional assumptions in BO.
Sec. 4 We establish the connection between RFD and gradient descent.
Sec. 5 We investigate the step size schedule suggested by RFD. In particular we
0. calculate explicit formulas for the step size schedules resulting from common covariance models (Table 1, Sec. C),
1. analyze the general asymptotic behavior (Sec. 5.1).
2. discuss how RFD explains gradient clipping and learning rate warmup (Sec. 5.2),
Sec. 6 We develop non- con--aemmttric variance estimation method, which is robust with respect the choice of covariance kernel. Finally, we present an extension of RFD to mini-batch losses.
Sec. We conduct a case study on the MNIST dataset.
Sec. We discuss extensions (see also Sec. B) and limitations.
2 The random function descent algorithm
The classic derivation of gradient descent [e.g. 38, p. 291, adds an L-smoothness based trust bound to the first Taylor approximation, ([J(0) J(w). V [ww],, of the cost function J around w resulting in the gradient step
w 1 [ = AigminnT((0 J(w), VJ(w)] + -110- w|l?
Our unusual notation for the Taylor approximation T[J J(w), VJ(w)) meant to highlight the connection to the stochastic Taylor approximation define below.

---

Definition 2.1 (Stochastic Taylor approximation). We define the first order stochastic Taylor approxi- mation of random (cost) function around w by the conditional expectation
(0) [ww), VJ(w)).
This is the best 2 approximation [30, Cor. 8.17] of (()) provided first order knowledge of J at w.
We call this the 'stochastic Taylor approxima- tion' because this approximation only makes use of derivatives in a single point. While the standard Taylor approximation is a polynomial approximation, the "stochastic Taylor approx- imation" is the best approximation sense and already mean-reverting by itself, i.e. naturally incorporates covariance-based trust (cf. Figure 1). While L-smoothness-badt
7136)
F201)
an L
trust guarantees that the gradient still points the di- rection we are going (for learning rates smaller 1/L,, covariance based trust tells us whether the derivative is still negative imizing the stochastic Taylor approximation is therefore optimized for the average case. Since convergence proof's for gradient descent typi- cally rely on an improvement guarantee, prov- ing convergence is significantly harder in the average case and we answer this question only partially in Corollary 5.3.
average. Min-
Figure The stochastic Taylor approximation naturally contains a trust bound in contrast to the classical one. Here J is a Gaussian random func- tion (with covariance as in Equation (11), with length scale 2 and variance a² 1). The rib- bon represents two conditional standard deviations around the conditional expectation.
Definition 2.2 (Random Function Descent
RFD). Select uo+1 as the minimizer of the first order stochastic Taylor approximation
Wn+1 == argmin (w)) J (ww), V.(w))].
Properties of RFD Before we make RFD more explicit in Section 4, we discuss some properties which are easier to see in the abstract form.
First, observe that RFD is greedy and forgetful in the same way gradient descent is greedy and forgetful when derived as the minimizer of the regularized first Taylor approximation, or the Newton method the minimizer of the second Taylor approximation. This is because the Taylor approximation only uses derivatives from the last point wn, (forgetful), and we minimize this approximation (greedy). Since momentum methods retain some information about past gradients, they are not forgetful. We therefore expect a similar improvement could be made for RFD in the future.
Second, it is well known that classical gradient descent with exogenous step sizes (and most other first order methods) lack the scale invariance property of the Newton method [c.g. 21, 13]. Scale invariance means that scaling the input parameters or the cost itself (e.g. by switching from the mean squared error to the sum squared error) does not change the points selected by the optimization method.
Advantage 2.3 (Scale invariance). RFD is invariant to additive shifts and positive scaling of the cost RFD is also invariant with respect to transformations of the parameter input of J by differentiable bijections whose Jacobian is invertible everywhere (e.g. invertible linear maps).
While invariance to bijections of inputs is much stronger than the affine invariance offered by the Newton method, non-linear bijections will typically break the 'isotropy' assumption of the following
"stochastic process" [e.g. 53], "random field" [e.g. 1] and "random function" [e.g. 36] are all synonyms. However the latter seems most descriptive of random variables in the set of functions. "Gaussian processes" are naturally Gaussian stochastic processes, i.e. Gaussian random functions. To better distinguish random functions from deterministic functions, use bold letters denote random functions (as the usual convention of capitalizing random variables often clashes with other conventions functions). 'we ignore throughout the main body that argmin could be valuvd and that the w, would be random variables (cf. Section D.I.1 for formal approach).
'Remark on terminology:
3

---

section which makes RFD explicit. This invariance should therefore be viewed as an opportunity look for the bijection of imputs which ensures isotropy (e.g. a whitening transformation). The discussion of geometric anisotropy in Section E.1 is conducive to build an understanding of this.
3 A distribution over cost functions
is impossible to make average case analysis explicit without a distribution over functions, so we use the canonical distributional assumption of Bayesian optimization [c.g. 16, 44]. 'isotropic Gaussian random functions'. This assumption was also used in the high dimensional setting by Dauphin et al. [10] to argue that saddle points are much more common than minima in high dimension, which is often cited to explain why second order methods are uncommon in machine learning.
To motivate isotropy, note that in average weighs all problem instances equally (e.g. all possible permutations in sorting). Isotropy is such a uniformity assumption, which essentially requires "IP(J J) P(J J x)", for all isometries In other words, the probability that our cost function is equal to J is equal to the probability that it is equal shifted and turned version of J, given by J
analysis the uniform distribution is popular, since
Since the probability of any single realization of a cost function zero, the equation we put in quotes is mathematically unsound. The formal definition follows below.
Definition 3.1 (Isotropy). A random function J is called isotropic if its distribution stays the same under isometric transformations of its input, i.e. for any isometry ø we have
Fy PJo2
If J is Gaussian, isotropy is well known [e.g. 44, 1] to be equivalent to the condition that there exists Ju E and function C R + such that for all w, ú Rd the expectation and covariance are
E [w) = p,
Cov(J(w), = C |1 [1=-01")
For these isotropic Gaussian random functions we use the notation J ~ (H,
We discuss generalizations to isotropy in Section F and E.1, but for ease of exposition we retain the (stationary) isotropy assumption throughout the main body. Note that the Gaussian assumption can be statistically tested in practice (cf. Figure 4), but it is also straightforward reproduce our results with the "best linear unbiased estimator" (BLUE) (Section E.3) in place of the conditional expectation remove the Gaussian assumption. We finally want to highlight that, in contrast to the uniformity assumption on finite sets, 'isotropic Gaussian random functions' leave us with family of plausible distributions. is therefore necessary to estimate μ and C, which the topic of Section
Relation to gradient descent
While were able to define RFD abstractly without any assumptions the distribution Py of the random cost J, an explicit calculation requires distributional assumptions and we have motivated isotropic Gaussian random functions in Section 3 for this purpose. The assumption of isotropy allows for an explicit version of the stochastic Taylor approximation which then immediately leads to an explicit version of RFD.
Lemma 4.1 (Explicit first order stochastic Taylor approximation). For J NN(,, C), the first order stochastic Taylor approximation is given by
C( d 2
(J(w) - ()) C'
C'( [la C'(0) (d, VI(w))
[[ d) J(w).. VJ(w))
C(O)
The explicit version of RFD follows by fixing the step size ||d]] and optimizing over the direction first.
Theorem 4.2 (Explicit RFD). Let J ~ NN1,, C), then RFD coincides with gradient descent
(an.)
Wa+1 Wn. The (w.

---

Table 1: RFD step size (cf. Figure 2 and Eq. (11), (13), (14) for the formal definitions of the models). In particular, is the length scale in all covariance models.
Model
RFD step size 1f" for (w) S μ
A-RFD
General case (with θ p ((a)
[J((r)
J ((w) P
Matérn
3/2
R 0.588
3
5/2
(1-() ++(+2))
with <
/B.
R3 0.72s
V5
2(++()
350
Squared- exponential
8
VJ(w)]
5²0
+ [[]] 1-
Rational quadratic
8
$ / Root
Root (11+ # ワ (1+ 3)n² + v nつ
$V I+3
2²
where the RFD step sizes are given by
C(
C² (J(w)) - n1) "'O) ('() [ww)ll C(O)
Un = argmin
yER
While the descent direction is universal property for all isotropic Gaussian random functions, follows from (1) that the step sizes depend much more on the specific covariance structure. In particular depends on the decay rate of the covariance acting as the trust bound.
Remark 4.3 (Scalable complexity). While Bayesian optimization typically has computational com- plexity On dd in number of steps n and dimensions [55, 45], RFD under the isotropy assumption has the same computational complexity gradient descent (i.e. ((nd)).
Remark 4.4 (Step until the given information is longer informative). While L-smoothness-bun based trust prescribes step sizes that guarantee the slope to point downwards over the entire step, RFD prescribes steps which exactly large enough that the gradient is no longer correlated to the previously observed evaluation. This is because the first order condition demands
[w) J (w,),, [J(w,,) = E (w) (w,). VJ(w))). (([(w,), VJ(w))) is sufficiently
And for measurable functions Φ Rd+1 + R such that integrable, & is then uncorrelated from (.J(w) by the first order condition
(ov( )) = E2 (w) (ww), (J(w)) - = 0.
5 The RFD step size schedule
While classical theory leads to 'learning rates', RFD suggests 'step sizes' applied normalized gradients representing the actual length of the step size. In the following we thus make the distinction
Wn+1 W/
Ni VJ
wn
na
VJ(wa)
'learning rate'
'step size'
To get a better feel for the step sizes suggested by RFD, enlightening to divide (1) by μ J(wn) which results in minimization problem
C(3)
C²
1 = y (9) :- argmin (1) for
(e(n) ==
O
(2)
C(0)
C'
which is only parametrized by the "gradient cost quotient"
[w,)]l
/ (w,,)
i.e. T/ - (O..). This minimization problem can be solved explicitly for the most common [44,
ch. 4] differentiable isotropic covariance models, see Table 1, Figure 2 and Appendix C for details.
5

---

Figure 2 can be interpreted as follows: At the start of optimization, the cost should be roughly equal to the average cost f z J (w), so the gradi- ent cost quotient è is infinite and the step sizes are therefore given by 1/ (oo) (also listed in its own column in Table 1). As we start minimizing, the difference μt (w) becomes positive. To- wards the end of minimization this difference no longer changes the cost no longer decreases. Lee towards the end the gradient cost quotient θ roughly linear in the gradient J ||. The derivative d ze 77 (0) of 17" (+) at zero then effec- tively results in a constant asymptotic learning rate.
1.00
0.75
0.50
0125
Rutional Quadratic (-11)
Mateen 3/2
Squarel Expcoestal
J J(w)
Figure 2: RFD step sizes as function of θ
[
u-J[w) assuming scale s = 1 (cf. Table 1). A-
5.1 Asymptotic learning rate
RFD (Definition 5.1) is plotted as dashed lines. A-RFD of the rational quadratic coincides with A-RFD of the squared exponential covariance.
To explain the claim above, note that the gradi-
ent cost quotient @ converges to zero towards the end of optimization, because the gradient norm converges to zero. A first order Taylor expansion of 11'' would therefore imply
d 7 (+) n (0) 25 (0)O
de (0) [(w]
V
asymptotic learning rate
assuming (0) = 0 and differentiability of 17",, which is reasonable educated guess based on the the examples in Figure 2. But since the RFD step sizes 17" are abstractly defined as an argmin, is necessary to formalize this intuition for general covariance models. First, we define asymptotic step sizes as an object towards which we can prove convergence. Then we prove convergence, proving they are well defined. In addition, we obtain more explicit formula for the asymptotic learning rate. Definition 5.1 (A-RFD). We define the step sizes of "asymptotic RFD" (A-RFD) to be the minimizer of the second order Taylor approximation T2ge of ge around zero
C(O) ii))) == argmin Tzge (n) (o
C(O)
[VJ(w)]]
7
asymptotic learning rate
In the following we prove that these are truly asymptotically equal to the step sizes 17" of RFD.
Proposition 5.2 (A-RFD is well defined). Let J ~ (p, C`) and assume there exists 1jo >> 0 such that
the correlation for larger distances 1) 2 77 are bounded smaller than 1, i.e. C(a² /2) < p E (0, 1). Then the step sizes of RFD are asymptotically equal to the step sizes A-FDD, i.e.
C(O)
(())) ~ 17" (9) as θ - 0.
Note that the assumption is essentially always satisfied, since the
inequality implies
C( @[Iw-aül' ol Cov(J(w), J (w)) I VVrr[J (w) Var (J ()) C(O),
where equality requires the random variables to almost surely equal [30]. If the random function is not periodic or constant, this will generally be strict. In the proof, this requirement is only needed to ensure that 17" is not very large. The smallest local minimum of qe always close to r even without this assumption (which ensures it is a global minimum).
Figure illustrates that 1f - 0 should imply θ + 0, resulting in a weak convergence guarantee. Corollary 5.3. Assume d1 - 0 implies θ - O, the cost J is bounded, has continuous gradients and RFD converges to some point Wos. Then wao is critical point and the RFD step sizes 17" are asymptotically equal to f
For the squared exponential covariance model we formally prove that 17" is strictly monotonously increasing in θ and thus 17" + O implies O - O (Prop. C.3). The 'bounded' and "continuous gradients' assumptions are almost surely satisfied for all sufficiently smooth covariance functions [cf. 1]. where three times differentiable is more than enough smoothness.

---

5.2 RED step sizes explain common step size heuristics
Asymptotically, RFD suggests constant learning rates, similar to the classical L-smooth setting. We thus define these asymptotic learning rates (as the limit of the learning rates h, of iteration n)) to be
C(O)
1100 (W n))
(3)
where (W is the cost reach in the limit. If we used these asymptotic learning rates from the start, step sizes would become too large for large gradients, as RFD step sizes exhibit plateau (ef. Figure 2). To emulate the behavior of RFD with piecewise linear function, we could introduce cutoff whenever our step size exceeds the initial step size v)" (oo), i.e.
17 VJ (C,,,
1 w/ min ho
(w,,)
(gradient clipping)
At this point we have rediscovered 'gradient clipping' [42]. Since the rational quadratic covariance has the same asymptotic learning rate h for every B, its parameter controls the step size bound v7" (oo) of gradient clipping (cf. Table 1, Figure 2).
Pascanu al. [42] motivated gradient clipping with the geometric interpretation of movement towards a 'wall' placed behind the minimum. This suggests that clipping should happen towards the end of training. This stands contrast
more recent step size heuristic, "(linear) warmup" [20], which suggests smaller learning rates at the start (i.e. ho = [wre)) and gradual ramp-up to the
(0())
asymptotic learning rate hoo In other words, gradients are not clipped due to some wall next to the minimum, but because the step sizes would be too large the start otherwise. Goyal et [20]
further observe that 'constant warmup' (i.e. step change of learning rates akin to gradient clipping) performs worse than gradual warmup. Since RFD step sizes suggest this gradual increase, we argue that they may have discovered RFD step sizes empirically (also ef. Figure 3).
6 Mini-batch loss and covariance estimation
Since we do not have access to evaluations of the cost J in practice, we need to prove some results about stochastic losses & before we can apply RFD practice. For this, assume that we have independent identically distributed (iid) data X, independent of the true relationship f drawn from Ir resulting in labels Y; f(X,) + St, where we have added independent iid noise Si, resulting in loss and cost
(w) == (w,, (X,, Y:)) and (ww) = [((;(w) [f].
In this setting we confirm (cf. Lemma D.9), that the stochastic approximation errors
e (w) = (w) J (w)
are independent conditional on the true relationship f. In particular they (and all their derivatives) are uncorrelated and also uncorrelated from J. follows that mini-batei losses
1 b b
(ow)) ((w) J (ww + ((()
(4)
have variance
Var(Co(w) = Var(J (w) + Var(ei (w)) isotropy
C(O) + +
(5)
where we assume J ~ NN,, C') and e; NO, C.) in the last equation for simplicity. But this step did not yet require the distributional Gaussian assumption beyond the mean and variance.
6.1 Variance estimation
Recall that the asymptotic learning rate Aow in Equation (3) only depends C(0) and C²(0). So we estimate these values, we are certain to get the right RFD step sizes asymptotically without knowing the entire covariance kerne C..
7

---

Equation (5) reveals that for Zo := (Lo(w) - -12 2 we have
[ 90 + 8, i..
Z. = 3o 8.81 noise
with bias 3o (()) and slope 31 C. So a linear regression samples ( Zoe )agn allows for the estimation of Bu and 31. Using the Gaussian assumption from (5), the variance of Zp is the (centered) fourth moment of Cs. which given by
of := Var(Zi) = E[Z - E|2 2 Var(Cu(w)) = 2(6 + }31)².
In particular the variance of Z depends the batch size b. The linear regression is therefore heteroskedastic. Weighted least squares (WLS) [e.g. 28, Theorem 4.2] is designed to handle this case, but for its application the variance of Z₁ is needed. Since Bo, 81 are the parameters estimate, we find ourselves in the paradoxical situation that we need / to obtain 3. Our solution to this problem start with guess of 3n, 31. apply WLS to obtain better estimate and repeat this bootstrapping procedure until convergence. Since all Zn have the same underlying cost J, we sample the parameters randomly reduce their covariance (details in Sec. B).
wish to
The same procedure can be applied to obtain (0)) where the counterpart of Equation (5) is given by
(ar(O)C((w)) Var(0,J(w)) + Var(Ore((w)) isotropy
(C" (O))
Remark 6.1. Under the isotropy assumption the partial derivatives are iid, so the expectation of [V)] 2 = Ei (0;C((w)) is this variance scaled by d. In particular the variance needs to scale with 1 to keep the gradient norms (and thus the Lipschitz constant of J) stable. This observation closely related "isoperimetry" [e.g. 7], for details see [5]. Removing the isotropy assumption and estimating the variance component-we wise is most likely how "adaptive" step sizes [e.g. 14, 29], like the ones used by Adam, work (cf. Sec. F.
Batch size distribution Before we can apply linear regression to the samples ( Zon Jks it is necessary to choose the batch sizes by. As this choice is left to us, we calculate the variance of our estimator 3o of fo explicitly (Lemma B.2), in order to minimize this variance subject to sample budget a over the selection of batch sizes
T
min Var(Bo) s.t. b.....
by
S a.
(6)
samples used
Since this optimization problem is very difficult to solve, we rephrase it in terms of the empirical distribution of batch sizes Vn = 1 n Ex= db Optimizing over distributions is still difficult, but we explain in Section B.1 how to heuristically arrive at the parametrization
v(b) x exp(AI ,/4 A2b),
E N
where the parameters \1, A2 2 0 can then be used to optimize (6). Due to our usage of of this has to be bootstrapped.
Covariance estimation While the variance estimates above ensure correct asymptotic learning rates, we motivated in Section 5.2 that asymptotic learning rates alone would result in too large step sizes at the beginning. We therefore use the estimates of C(0) and (0(0) to fit covariance model, effectively acting as gradient clipper while retaining the asymptotic guarantees. Note that covariance models with less than two parameters are generally fully determined by these values.
6.2 Stochastic RFD (S-RFD)
It is reasonable ask whether there is 'stochastic gradient descent'- counterpart to the 'gradient descent'- RFD. The answer is yes, and we already have all the required machinery.
Extension 6.2 (S-RFD). For loss N C) and stochastic errors c; idd N( C.) we have
vex(w) argmin [[J(w d) [s(w), VLo(w)] = (7) [V]]
8

---

with the same step size function 1f" as for RFD, but modified è
(0) C(O) (0)
| (w)) (w)l J Ls (w)
θ (0) C((0 C(()
C(O)
Note, that our con-parametric covariance estimation already provides us with estimates of C. (0) and (0), so no further adaptions are needed. The resulting asymptotic learning rate given by
C(O) + (0)
hoc (C" (C()) n)
(7)
7 MNIST case study
For our case study we use the negative log likelihood loss to train a neural network [3, M7] on the MNIST dataset [34]. We choose this model as one of the simplest state-of-the-ar models the time of selection, consisting only of convolutional layers with ReLU activation interspersed by batch normalization layers and single dense layers at the end with softmax activation. Assuming isotropy. we estimate C(O) and (0) as described in Section 6.1 and deduce the parameters o² and of the respective covariance model (more details Section B). We then use the step sizes listed in Table for the "squared exponential' and 'rational quadratic' covariance in our RFD algorithm.
In Figure 3, RFD benchmarked against step size tuned Adam [29] and stochastic gradient descent (SGD). Even with early stopping, their tuning would typically require more than 1 epoch worth of samples, contrast to RFD (Section 1.1.1). We highlight that A-RFD performs significantly worse than either of the RFD versions which effectively implement some form of learning rate warmup. This is despite the RFD learning rates converging to the asymptotic one within one epoch (ca. 30 out of 60 steps per epoch). The step sizes on the other hand are (up to noise) monotonously decreasing. This stands in contrast to the "wall next to the minimum" motivation of gradient clipping.
Code availability: Our implementation of RFD can be found at https://gi com/ FelixBenning/pyrte and the package can also be installed from PyPI via 'pip install pyrfd'.
8 Limitations and extensions
To cover the vast amount of ground that lays between the 'formulation of general average case optimization problem' and the 'prototype of a working optimizer with theoretical backing',
1. we used the common [16, 52, 55, 10] isotropic and Gaussian distributional assumption for J,
2. we used very simple covariance models for the actual implementation,
3. used WLS in our variance estimation procedure despite the violation of independence.
Since RFD is defined as the minimizer of average instead of an upper bound making it more risk affine it naturally loses the improvement guarantee driving classical convergence proofs. therefore impossible extend classical optimization proofs and new mathematical theory must be developed. This risk-affinity can also be observed in its comparatively large step sizes (cf. Fig. 3 and Sec. A). On CIFAR-100 [31], the step sizes were too large and it is an open question whether assumptions were violated or whether RFD is simply too risk-affine. But since the variance of random functions vanishes asymptotic with high dimension [5] we highly suspect the former (cf. Remark E.5).
Future work will therefore have to target these assumptions. Some of the assumptions were already simplifications for the sake of exposition, and deferred their relaxation the appendix. The Gaussian assumption can be relaxed with a generalization to the 'BLUE' (Sec. E.3), isotropy can be generalized 'geometric anisotropies' (Sec. 1. and the risk-affinity of RFD can be reduced with confidence intervals (Sec. E.2). Since simple random linear models already violate stationary isotropy (Sec. F.I), we believe that stationarity is the most important assumption attack in future work.
9 Conclusion
In this paper we have demonstrated the viability (computability and scalable complexity) and ad advantages (scale invariance, explainable step size schedule which does not require expensive

---

Validation loss
Thning
REDISE)
SGD
S-RFDISE)
Adam
(FD(NQ(beaa=))
RFD
SGD(I==1)
Flial. validacion
10-1
Las
10-1
Adan(I:-1o2]
0
16
20
26
30
10
10
10
10
100
Epoch
Learning
Learning
Step
16
RED/SE
S-RFD(SE)
KFDCRQUltt-1)
12
A RED
10'
SGD(e=1
Adam([==1o-2)
8-
REDISE)
4-
S-RFD(SE)
10-1
RFD(RQ(Leto-I)
0-
10
Step
Step
Figure 3: Training on the MNIST dataset (batch size 1024). Ribbons describe the range between the 10% and 90% quantile 20 repeated experiments while lines represent their mean. SE stands for the squared exponential (11) and RQ for the rational quadratic (13) covariance. The validation loss uses the test data set, which provides a small advantage to Adam and SGD, as we also use for tuning.
tuning) of replacing the classical "convex function" framework with the "random function" framework. Along the way we bridged the gap between Bayesian optimization (not scalable far) and classical optimization methods (scalable). This theoretical framework not only sheds light on existing step size heuristics, but can also be used to develop future heuristics.
We envision the following improvements to RFD in the future:
The reliability of RFD can be improved by generalizing the distributional assumptions to interested in the generalization non-stationary isotropy because we suspect that regularization such as weight and batch normalization [46, 25] used patch violations of stationarity (cf. Section F).
real world scenarios. In particular
2. The performance of RFD also be improved. Since RFD is forgetful while momentum methods retains some information it is likely fruitfuul to relax the full forgetfulness. Further- more, suspect that adaptive learning rates [e.g. 14, 29], such those used by Adam, can be incorporated with geometric anisotropies (cf. Sec. E. Performance could also be further improved by estimating the covariance (locally) online instead of globally at the start. Finally, the implementation itself can be made more performant.
Acknowledgement
We extend our sincere gratitude our colleagues the University of Mannheim, with special thanks to Rainer Gemulla and Julie Naegelen for insightful discussions and invaluable feedback. The Experiments in this work were partially carried out on the compute cluster of the state of Baden- - Würtemberg (bwHPC).
10

---

References
[1] Robert J. Adler and Jonathan E. Taylor. Random Fields and Geometry. Springer Monographs in Mathematics. New York, NY: Springer New York, 2007. ISBN: 978-0-387-48 12-8. DOI:
10. 0000/99780-387-4B8-
[2] Apoorv Agnihotri and Nipun Batra. "Exploring Bayesian Optimization", In: Distill 5.5 (2020- 05-05), c26. ISSN: 2476-0757. DOI: 10. 23915/distill. 00026.
[3] Sanghyeon An et al. An Ensemble of Simple Convolutional Neural Network Models for MNIST Digil Recognition. 2020-10-04 DOI: 10. 48550/ arXiv. 2008 10400. Pre-published.
[4] Antonio Auffngger and Qiang Zeng. "Complexity of Gaussian Random Fields with Isotropic Increments" In: Communications Mathematical Physics 402.1 (2023-08-01), pp. 951-993.
ISSN: 1432-0916. DOI: 10. 10000000000000000 020-000-22----9---00 04739-0.
[5] Felix Benning and Leif Döring. Gradient Span Algorithms Make Predictable Progress in Hlgh Dimension. 3024-10-13, DOI: 48.48550/ ariiv. 2410 09973. Pre-published.
[6] Karl Heinz Borgwardt. The Simplex Method: A Probabilistic Analysis. Softcover reprint of the original 1st ed. 1987 edition. Berlin Heidelberg: Springer, 1986-11-01 282 pp. ISBN:
978-3-540-17096-9)
[7] Sebastien Bubeck and Mark Sellke. "A Universal Law Robustness via Isoperime- try". In: Advances in Neural Information Processing Systems. Vol. 34. Virtual Event: Curran Associates, Inc., 2021, pp. 28811-28822 arXiv: 2105 12806 [cs, stat]. URL: https
proceedings neurips cc / paper 2021 / hash / Abstract html (visited on 2023-09-22).
[8] Youngmin Cho and Lawrence Saul. "Kernel Methods for Deep Learning". In: Ad- vances in Neural Information Processing Systems. Vol. 22. Curran Associates, Inc., 2009. URL: https
proceedings neurips cc paper / 2009 hash / hww.ca/9eaeeab777977777720000000 Abstracttttttttttt...mcca html (visited on 2023-04-03).
[9] Leonardo Cunha al. "Only Tails Matter: Average-Case Universality and Robustness in the Convex Regime". In: Proceedings of the 39th International Conference on Machine Learning.
International Conference on Machine Leanning PMLR, 2022-06-28, pp. 4474 4491. URL: https://procesdee .mr...ssmm.r................mr.. wrw.pprssssveeeee voses//v122/ w1llvv16////0 www.aaa/aaaaaa..aaaaa/aaaaaaaa html (visited on 2023-11-09),
[10] Yann N Dauphin et al. "Identifying and Attacking the Saddle Point Problem in High- Dimensional Non-Convex Optimization". In: Advances in Neural Information Processing Sys- tems. Vol. 27. Montréal, Canada: Curran Associates, Inc., 2014. URL: https: http:tpeepp///coeeieeieeese/// neurips-. cc paper 2014/ hwwhh/aaaa//a///a 11226660bddc3000033320000000 -tt.:eeeeceoobb--baaaaacc Abstract html (visited on 2022-06- 10).
[11] Aaron Defazio and Konstantin Mishchenko. "LLearning-Rat-Fiie Learning by D-Adaptation".
In: Proceedings of the 40th International Conference on Machine Learning. International
Conference Machine Learning. PMLR, 2023-07-03, pp. 7449-7479. arXiv: 2301. 2301.07733
[cs.LG] URL: htttps:/pproceeding/ mlr. http:///iwn.......eess//2/22222/
html (visited on
2024-03-31).
[12] Percy Deift and Thomas Trogdon. "The Conjugate Gradient Algorithm on Well-Conditioned Wishart Matrices Is Almost Deterministic.. In: Quarterly of Applied Mathematics 79.1 (2021- DOI: 10. 1090 / qam/ 1574. arXiv: 1901.
03), pp. 125-161. ISSN: 0033-569X, 1552-4485. 09007 [cs, math].
[13] P. Deufthard and G. Heindl. "Affine Invariant Convergence Theorems for Newton's 's Method and Extensions to Related Methods". In: SIAM Journal on Numerical Analysis 16.1 (1979-02),
pp. 1-10. ISSN: 0036- 1026.1429, DOI: 10. 1 137 /0716001
[14] John Duchi, Elad Hazan, and Yoram Singer. "Adaptive Subgradient Methods for Online Learning and Stochastic Optimization", " In: The Journal of Machine Learning Research 12 (2011-07-01), pp. 2121-2159. ISSN: 1532-4435.
[15] Ahmed El Alaoui, Andrea Montanari. and Mark Sellke. "Optimization of Mean-Field Spin Glasses", In: The Annals of Probability 49.6 (2021-11), pp. 2922-2960, DOr: 10. 001214//1- AOP1519.
[16] Peter I. Frazier. "Bayesian Optimization". In: Recent Advances in Optimization and Modeling of Contemporary Problems. INFORMS TutORials in Operations Research. Phoenix, Arizona, USA: INFORMS, 2018-10, pp. 255-278. ISBN: 978-0-99061.3--2. DOI: 10. 1287 eduu.
2018. 0188.
arXiv: 1807. 02811 [cs, math, stat].

---

[17] Fuchang Gao and Lixing Han. "Implementing the Nelder-Meat Simplex Algorithm with Adap- tive Parameters". In: Computational Optimization and Applications 51.1 (2012-01-01). pp. 259-277. ISSN: 1573-2894. DOt: 10. 1007 s00009900009900---00 010-9999-10--99----3-
[18] Xavier Glorot and Yoshua Bengio. "Understanding the Difficulty of Training Deep Feed- forward Neural Networks". In: Proceedings of the Thirteenth International Conference on Artificial Intelligence and Statistics. Proceedings of the Thirteenth International Conference on Artificial Intelligence and Statistics. Sardinia, Italy: JMLR Workshop and Conference Proceedings, 2010-03-31, pp. 249-256. URL: https : / proceeding mlr gress/v9. glorot10a.hn html (visited on 2023-04-11).
[19] Ian Goodfellow, Yoshua Bengio, and Aaron Courville. Deep Learning. MIT Press, 2016-1 11-10. 801 pp. ISBN: 978-0-262-337777
Google Books: omivDQAAQBAJ.
[20] Priya Goyal et al. Accurate, Large Minibatch SGD: Training ImageNet in 1 Hour. arXiv, 2018- 04-30. arXiv: 1706.02677
[cs]. URL: pestt://arriee org/ abs/1706. 02677 (visited on
2024-04-02).
[21] Anders Hansson. Optimization for Learning and Control. Hoboken, New Jersey: John Wiley & Sons, Inc.. 2023. ISBN: 978 1-119-80914--2
[22] Geoffrey Hinton. "Neural Networks for Machine Learning". Massive Open Online Course (Coursera). 2012. URL: https:
www.sst..ooooooooooooo edu/ /wtpt//occoosseraaaaaaa lectuurrs
html (visited on 2021-11-16).
[23] C. A. R. Hoare. "Quicksort". In: The Computer Journal 5.1 (1962-01-01), pp. 10-16. ISSN: 0010-4620. DOT: 10. 00093/cmmjn//// 1.100..
[24] Brice Huang and Mark Sellke. "Tight Lipschitz Hardness for Optimizing Mean Field Spin Glasses". In: 2022 IEFE 63rd Annual Symposium on Foundaations of Computer Science (FOCS). 2022 IEEE 63rd Annual Symposium on Foundations of Computer Science (FOCS). 2022-10, 10,
pp. 312-322. DOT: 10. 11110//FFOS545577. 222CS5445..2022.... 00037..
[25] Sergey Ioffe and Christian Szegedy. "Batch Normalization: Accelerating Deep Network Training by Reducing Internal Covariate Shift". In: Proceedings of the 32nd International Conference on Machine Learning. International Conference Machine Learning. PMLR, 2015-06-01, pp. 448-456. arXiv: 1502. 03167 [cs]. URL: https: http///prceeennsse///e/ mlr.
Fress/v37/ioffeds html (visited on 2021-10-06).
[26] E. T. Jaynes. "Information Theory and Statistical Mechanies". In: Physical Review 106.4
(1957-05-15), pp. 620-630. DOI: 10. 1103/Phpppee 100/PhysRev... 106. 620.
[27] Richard Arnold Johnson and Dean W. Wichern. Applied Multivariate Statistical Analysis.
6th ed. Upper Saddle River, N.J: Pearson College Div, 2007. 767 pp. ISBN: 978-0-13-187715-
3.
[28]
Steven M. Kay. Fundamentals of Statistical Signal Processing:
Estimation Theory. USA:
Prentice-Hall Hall, Inc., 1993-02. 595 pp. ISBN: 978-0-13-34571111
[29] Diederik P. Kingma and Jimmy Ba. "Adam: A Method for Stochastic Optimization". In: Proceedings of the 3rd International Conference on Learning Representations, ICLR. San
Diego, 2015. arXiv: 1412.6980.
[30] Achim Klenke. Probability Theory: A Comprehensive Course. Universitext. London: Springer, 2014. ISBN: 978-1-4471-5366 978-1-4471-53614 DOI: 10.
[31] Alex Krizhevsky. Learning Multiple Layers of Features from Tiny Images. 2009, URL: https: / www. cs toronto..... edu /ttp://////ri/// (at00krii/leeaniii /larriingnnn-g features- 2009 TR. pdf (visited on 2024-05-21).
[32] H. J. Kushner. "A New Method of Locating the Maximum Point of an Arbitrary Multipeak Curve in the Presence of Noise". In: Journal of Basic Engineering 86.1 (1964-03-01), pp. 97-
106. ISSN: 0021-9223. DOI: 10. 11../11/1111 3.53312..
[33] Jonathan Lacotte and Mert Pilanci. "Optimal Randomized First-Order Methods for Least- Squares Problems". In: Proceedings of the 37th International Conference on Machine Learning. International Conference on Machine Learning. PMLR, 2020- 11-21, pp. 5587-5597. URL.: .ww.............mmm............. www.:mmes.....et.mmm.mm.e.mmee.e prres//v19//acotteee
html (visited on 0023-11-09), [34] Yann LeCun, Corinna Cortes, and Christopher J.C. Burges. THE MNIST DATABASE of Handwritten Digits. 2010. URL: http : yann. lecun com/ exdb / mnist/ (visited on 2024-01-24).
https::/prooet
12

---

[35] Daniel James Lizotte. "Practical Bayesian Optimization". PhD thesis. Alberta, Canada: Uni- versity of Alberta, 2008. 168 pp.
[36] G. Matheron. "The Intrinsic Random Functions and Their Applications". In: Advances in Applied Probability 5.3 (1973-12), pp. 439-468. ISSN: 0001-8678, 1475-6064. DOI: 10. 2307/ 1425829.
[37] Andrea Montanari. "Optimization of the Sherrington-Kirkpatii HamaraaapptiiiiHaliiiiinnna Hamiltonian". In: SIAM Jour- nal on Computing (2021-01-07), FOCS19-L ISSN: 0097-5397. DoI: 10. 1137/20M13201
[38] Yurii Evgen' ević Nesterov. Lectures on Convex Optimization. Second edition. Springer Opti- mization and Its Applications; Volume 137, Cham: Springer, 2018. ISBN: 978-3-319-91578-4
DOI: 10.
[39] Misha Padidar et al. "Scaling Gaussian Processes with Derivative Information Using Variational Inference", . In: Advances in Neural Information Processing Systems. Vol. 34. Curran Associates,
Inc., 2021, pp. 6442-6453. URL:
neuripa cc paper / 2021/
hash/ 322b://tbc4ee114eeeeeecec
htt.:6aag9--Abtractt...o html (visited on 2023-05-17).
[40] Courtney Paquette et al. "Halting Time Predictable for Large Models: A Universality
Property and Average-Case Analysis" In: Foundations of Computational Mathematics 23.2 022
(2022-02), pp. 597-673. ISSN: 1615-3383, DOI: 10. 1w0000001100000220065666 y. arXiv:
2006. 042999 [math, stat].
[41] Elliot Paquette and Thomas Trogdon. "Universality for the Conjugate Gradient and MINRES
Al Algorithms on Sample Covariance Matrices". In: Communications on Pure and Applied
Mathematics 76.5 (2022-09-01), pp. 1085-1136. ISSN: 1097-0312. DOE: 10. 1002 / cpa. 22081.
[42] Razvan Pascanu, Tomas Mikolov, and Yoshua Bengio. "On the Difficulty of Training Recurrent Neural Networks". In: Proceedings of the 30th International Conference on Machine Learning. International Conference on Machine Learning. Atlanta: PMLR, 2013-05-26, pp. 1310-1318. URL:: httph::t/pppptt //poceedi//o mlr www.ppres/vie vv28/ http//asccann1 3.hmll (visited on 2024-04-02).
[43] Fabian Pedregosa and Damien Scieur. "Acceleration through Spectral Density Estimation". In: Proceedings of the 37th International Conference on Machine Learning. International Conference on Machine Learning. Virtual Event (formerly Vienna): PMLR, 2020-1 11211, pp. 7553-7562. URI.: https::/pproceeeeeeee (visited on 2023-11-09).
mlr, press/v119 petess/v119/pediiee
httpa///v111///eeoesaaaa/ pedregosa20a.... html
[44] Carl Edward Rasmussen and Christopher K.I. Williams. Gaussian Processes for Machine Learning. 2nd ed. Adaptive Computation and Machine Learning 3. Cambridge, Massachusetts: MIT Press, 2006. 248 pp. ISBN: 2-222-8823--2 URL: http:// http://gaussianproeeee gaussianprocess. org/ pdf (visited on 2023-04-06).
spml/chapters//1
[45] Filip de Roos, Alexandra Gessner, and Philipp Hennig. "High-Dimennsinal Gaussian Process Inference with Derivatives". In: Proceedings of the 38th International Conference on Machine Learning. International Conference on Machine Learning. PMLR, 2021-07-01, pp. 2535- 2545. URL: https: /tt::/prroee proceedings. mlr. press /v13///3/////// http/dderooo00000 roos21a html (visited on 2023-05-15).
[46] Tim Salimans and Durk P Kingma. "Weight Normalization: A Simple Reparameter- ization to Accelerate Training of Deep Neural Networks". In: Advances in Neural Information Processing Systems. Vol. 29. Barcelona, Spain: Curran Associates, Inc.,
2016. URL: https : proceedings neurips cc paper / 2016 hash / Abstract html (visited on 2023-10-16).
[47] Bobak Shahriari et al. "Taking the Human Out of the Loop: A Review of Bayesian Optimiza- tion". In: Proceedings of the IEEE 104.1 (2016-01), pp. 148-175.
ISSN: 1558-2256. DOI:
10. N0.1109/JPROC 2015 2494218.
[48] Leslie N. Smith. A Disciplined Approach to Neural Network Hyper-Parametee Part Learning Rate, Batch Size, Momenium, and Weight Decay. 2018-04-24. DOT: 10. 48550/ / arXiv 100..09820.........0000000000..1 arXiv: 1803. 1803.09820 [cs, stat]. Pre-published.
[49] Leslie N. Smith. "Cyclical Learning Rates for Training Neural Networks". In: 2017 IEEE Winter Conference Applications of Computer Vision (WACV). 2017 IEEE Winter Conference on Applications of Computer Vision (WACV). 2017-03, pp. 464-472, DOI: 10. 1109/ 1109/WAOOC /WCCV.
2017.58.
13

---

[50] Michael L. Stein. Interpolation of Spatial Data. Springer Series in Statistics. New York, NY: Springer. 1999. ISBN: -78-1-4612-7166- 978- 978---64111-44424444 DOI: 10. 10.1007/998-1-46122 1494-6.
[51] Eliran Subag. "Following the Ground States of Full-RSB Spherical Spin Glasses". In: Commu- nications on Pure and Applied Mathematics 74.5 (2021), pp. 1021-1044. ISSN: 1097-0312.
DOI: 10. 1002/000///// 2tp.//pa.... 21922.
[52] Ziyu Wang al. "Bayesian Optimization in a Billion Dimensions via Random Embeddings", In: Journal of Artificial Intelligence Research 55 (2016-02-19), pp. 361-387. ISSN: 1076-9757.
DOI: 10. 1..1111/....
jair jair/jair
.806.
[53] C.K.I. Williams and D. Barber. "Bayesian Classification with Gaussian Processes". In: IEEE Transactions on Pattern Analysis and Machine Intelligence 20.12 (1998-12) 12), pp. 1342-1351.
ISSN: 1939-3539. DOr: 10. 1199/34.738077 735807.
[54] Christopher K. I. Williams. "Computation with Infinite Neural Networks", In: Neural
Compulation 10.5 (1998-07-01), pp. 1203-1216. ISSN: 0899-7667. DOI: 10 1162 /
089976698300017411.
[55] Jian Wu et al. "Bayesian Optimization with Gradients". In: Advances in Neural Information Processing Systems. Vol. 30. Curran Associates, Inc., 2017. URL: https: p/poceed///ooceiiggg..
neurips- cc paper / 2017 / /0ta0//0f....e111100000000011110 Abstract....... html (visited on 2022-06-02).
[56] Han Xiao, Kashif Rasul, and Roland Vollgraf. Fashion-MNIST:: A Novel Image Dataset for Benchmarking Machine Learning Algorithms. 2017-09-15. DOr: 10. 48550/arXiv, 1708 07747. arxiv: 07747 [cs, stat]. Pre-published.
[57] Matthew D. Zeiler. "ADADELTA: An Adaptive Learning Rate Method". 2012-122-0 arXiv:
1212.5701 [cs].
[58] Guodong Zhang et al. "Which Algorithmic Choices Matter at Which Batch Sizes? Insights From Noisy Quadratic Model". In: Advances in Neural Information Pro- cessing Systems. Vol. 32. Curran Associates, Inc., 2019. arXiv: 1907 04164 [cs, stat]. URL: https
proceedings neurips cc paper 2019 / hash / #0eacd9983911633327e0 118 9ea8b6214 Abstract html (visited on 2023-11-09).
14

---

Ls(w)) batchwise
3.5
b 100
3.0
2.73
Ordend Valtass
1000
2.5
2.0
10
10
-3
-2
(Galu) AA
0.6
batclorie meon squaress Var(Ca(so))
b- 1000
Ordeand Valtes
0.2
0.0
0.00
0.06
0.08
0.10
2000
(V FF
bc: 10
batchwise meen
20000
15000
Orekeve Valuue
1000
10000
10000
3000
0-
Thomestcaa quoutiles
x10
Visualization of the variance estimation (Section 6.1) with 95%-confidence intervals based on the assumed distribution. Quantile-quantia (QQ) plots of the losses (against a normal distribution), squared losses (against x1) distribution) and squared gradient norms (against x² (dd)diistribution) are displayed on the right for selection of batch sizes.
Figure 4:
Appendix: Random Function Descent
A Experiments
A.1 Covariance estimation
In Figure 4 we visualize weighted least squares (WLS) regression of the covariance estimation from Section 6. Note, that sampled much more samples per batch size for these plots than RFD would typically require by itself in order to be able to plot batch-wise means and batch-wise QQ-plots. The batch size distribution we described in Section B. would avoid sampling the same batch size multiple times to ensure better stability of the regression and generally requires much fewer samples than were used for this visualization (cf. A.1.1)
can observe from the QQ-plots on the right, that the Gaussian assumption is essentially justified for the losses, resulting in (1) distribution for the squared losses and (d) distribution for the gradient norms squared. The confidence interval estimate for the squared norms appears be much too small (it is plotted, but too small to be visible). Perhaps this signifies violation of the isotropy
15

---

15.0
12.5
10.0
7.5
5.0
0.0
10.0
12.5
15.0
17.5
20.0
22.5
25.0
100000
200000
300000
400000
500000
Asymptatic learning rate
Sample cost.
Figure repeated covariance estimations of model M7 [3] applied to the MNIST dataset. On the left are the resulting asymptotic learning rates (assuming final loss of zero) and on the right are the samples used until the stopping criterion interrupted sampling.
assumption as the variance of
[V Σ (0,Co(w))
does not appear be the variance independent (d) Gaussian random variables, and the indepen- dence only follows from the isotropy assumption.
A.1.1 Sampling efficiency and stability
To evaluate the sampling efficiency and stability of variance estimation process, we repeated the covariance estimation the model model M7 [3] applied to the MNIST dataset 20 times (Figure 5). We used tolerance of tol 0.3 stopping criterion for the estimated relative standard deviation (10).
At this tolerance, the asymptotic learning rate already seems relatively stable (in the same order of magnitude) and the sample cost quite cheap. The majority of runs (16/20 runs or 80%) required less than 60 000 samples (I epoch). There was one large outlier which used 500 589 samples. A closer inspection revealed, that after the initial sample to estimate the optimal batch size distribution, it sampled almost exclusively at batch sizes 20 (which was the minimal cutoff to avoid instabilities caused by batch normalization) and batch sizes between 1700 and 1900. It therefore seems like the initial batch of samples caused very unfavorable batch size distribution which then required lot of samples to recover from. Our selection of an initial sample size of 6000 might therefore have been small.
more extensive empirical study is needed to tune this estimation process, but the process promises to be very sample efficient. Classical step size tuning would train models for short duration in order to evaluate the performance a particular learning rate [e.g. 48], but a single epoch worth of samples very hard to beat.
Our implementation of this process on the other hand very inefficient as of writing. Piping data of differing batch sizes into model is not standard use case. We implement this by repeatedly initializing data loaders, which is anything but performance friendly.
A.2 Other models and datasets
To estimate the effect of the batch size on RFD, we trained the same model (M7 [3]) on MNIST with batch size 128 (Figure 6). We smaller batch size (cf. Equation 7) but the performance is barely different. Overall, RFD seems to be slightly too risk-affine, selecting larger step sizes than the tuned SGD models.
that the asymptotic learning rate of S-RFD is reduced at
We also trained a different model (M5 [3]) on the Fashion MNIST dataset [56] with batch size 128 (Figure 7). Since the validation loss increases after epoch 5, carly stopping would have been
16

---

Validation loss
Timing
RFD(SE)
SGD Adam
S-RFD(SB)
xx 10
SGD(I=0J))
Fizal validation loss
Adum/Ir=1es 1e-3)
Los
10
10
15
20
25
30
10
10r
Epoch
Louning
Learning rate
Step size
15.0
10a
Louringg rate
10.0
Slepslen xiee
10-2
5.0
S-RFD(SE)
RFD(SK)
SGD((1-01)
S-RFD(SE)
10
Adam([c-1e-3
0.0
20
60
100
2000
J000
6000
9000
10000
12000
14000
Step
Step
Figure 6: Training model M7 [3] with batch size 128 on MNIST [34].
appropriate. We therefore include Adam with learning rate 10-3 despite Adam with learning rate 10-4 technically performing better the end of training. can generally see, that RFD comes very close to tuned performance at the time early stopping would have been appropriate. Again, learning rates seem to be slightly too large -risk-affine) in comparison to tuned SGD.
Variance estimation in detail
Recall that we interested in the regression
1
Zo(w) = (Co(w) - -1)² 3o + a
where the variance of Z is given by
of - 2(30 + t.
under the Gaussian assumption on Lb-
More specifically we for minibatch sizes (bx) and parameter vectors (wH)esn we want to sample mini batch losses
by
(()) = Co2 (wx) = ((w) +
(wk)
==1
As the εR, are all conditionally independent and therefore uncorrelated, we have
(ov( (()) = Cov(J(wx)) J(w)) C( [1
Since the covariance kernel C is typically monotonously falling in the distance of parameters ||l - wy/l we want to select them spaced out possible to minimize the covariance of (k)
(which is the next best thing to iid samples). Randomly selecting w; with Glorot initialization [18] will ensure a good spread.
Note that Glorot initialization places all parameters approximately on the same sphere. This is because Glorot initialization initializes all parameters independently, therefore their norm is the
17

---

Validation loss
Tuning
xx 10
RFD(SE; S-RPD(SE;
SGD
Adam
(GD(1r=0.))
Adun(Ir=Ted To-3)
Piaul valtlation
Los
4x 10-1
Adun(Ir=1e-)
10010
10
15
20
10
10
10
108
10a
Egoch
Learning
Learning rate
Step size
10"
Leoraagg
d-
10
RED(SE)
S-RED(SE)
SGD(I-001)
RFD(SE)
10-2
Adaemile 1e33
S-EE
20
60
4000
6000
10000
12000
14000
Step
Step
Figure 7:
Model M5 [3] trained on Fashion MNIST [56] with batch size 128.
sum of independent squares, which converges by the law of large numbers due to the normalization Glorot uses. Since stationary isotropy and statttottonry isotropy coincides on the sphere, this an important effect to consider (cf. Section F).
What is left, is the selection of the batch sizes by-
B.1 Batch size distribution
Since we plan use the data set (2) ((())) for weighted least squares (WLS) regression and do not have a selection process for the batch sizes by yet, it might be appropriate select the batch sizes by in such a way, that the variance our estimator Bo of 8g is minimized. Here we choose Var(3)) and not Var(3)) as our optimization target, since 30 = C(00 used to the covariance model, while B1 (0) is only required for S-RFD. Without deeper analysis Bu therefore seems to be more important.
Optimization over n parameters by is quite difficult, but we can simplify this optimization problem by considering the empirical batch size distribution
Vn
Using random variable distributed according to Un. the total number of sample losses can then be expressed as
bc [ = samples used.
Under an (unrealistic) independence assumption, the variance Var($n) also has simple represen- tation in terms of 2% (Lemma B.2). We now want to minimize this variance subject to compute
18

---

constraint a limiting the number of sample losses we can use resulting in the optimization problem
1 n
Var(B9)
nE S
(8)
B
'variance of Ze
inverse 'sprend' i
where we recall that oz is the variance of Z.. So the inverse of the expectation its inverse is roughly the average variance of 7... The second half the fraction of weighted second moment divided by the weighted variance. Unless the mean is at zero, the former will be larger. In particular we want a spread of data otherwise the variance would be zero. This in some conflict with the variance of B..
But first, let us get rid of n. Note that we would always increase until our compute budget is used up, since this always reduces variance. So we approximately have nE B = a. Thus
E
B
Var
Bo Bo 41
Since a is now just resulting in constant factor, it can assumed to be without loss generality, Over batch size distributions y therefore want to solve the minimization problem
B E
min
B
moments
Example B.1 (If we did not require spread). If we were not concerned with the variance of batch sizes, we could select a constant = b. Then is straightforward minimize the moments factor manually
Eb b E
min
boj 2b(30 b 8,)
resulting in & In other words: If we did not have to be concerned with the spread of B there is one optimal selection to minimize the first factor. But in reality we have to trade-off this target with the spread of B.
3,
To ensure good spread of data, we use the maximum entropy distribution for B, with the moment constraints
a
2
average sample usage
E
ZB variance
which capture the first factor. Maximizing entropy under moment constraints known [26] to result in the Boltzmann (a.k.a. Gibbs) distribution
(bb) = PBB = x exp A1 ( -2b).
where A1 A2 depend on the momentum constraints. We can now forget the origin of this distribution and 'ι, A2 parameters for the distribution in Equation (9) get close its minimum. In practice we use a zero order black box optimizer (Nelder-Mead [17]). One could calculate the expectations (9) under this distribution explicitly and take manual derivatives with respect to A to investigate this further, but we wanted to avoid getting too distracted by this tangent.
We also the estimated relative standard deviation
V Var(3))
rel std
(10)
B
as a stopping criterion for sampling. Without extensive testing we found tolerance of rel rel_std < tol 0.3 to be reasonable, cf. Section A.I.I.
19

---

Lemma B.2 (Variance of Bu in terms of the empirical batch size distribution). Assuming independence of the samples ), Zoe )as the variance of Bo is given by
(ar
1
R
E
E
E
Boge/1/o 1)9
where B is distributed according to the empirical batch size distribution Vy = n/4 Ek=1 6oL-
Proof. With the notation o o to describe the variance of 2n, it follows from [ef. 28, Thm. 4.2] that the variance of the estimator of 3 using n samples is given by
Var(B) = -11"))
1 Ex of (2x (ox - EEx
Σ Torbey
- oē Σx oz
1
)2
oZbr
obbb
where
of
b1
C =
H =
b
In particular we have
Σx ..
Var(Bo) (Ex क.
)
(Ex
नम..
1 and Av कें we can reorder the divisor. For this note that since the With the help of 0 = E; #/2 A sum to 1 we have
Σ da 60
Σ A
2
Σ
>3 bj
1
+
Σ
Xo No)))
'))
bk
b9
bb
j
An
2
Σ
A bk
+
Σ )
A:
k
h:
1
2
A
Ak by:
b
Where the above is essentially the well known statement [E[(Y - = 1a0j-E]j E|y]² for an appropriate selection of Y. This implies that our divisor given by weighted variance
0
A bk Σッ Σ
Σ
20
where it is only necessary to plug in the definition of to see the right term is exactly our divisor. Expanding both the enumerator as well as the divisor by 4. we obtain
# 1
1
Var(3o)
0
0
+
by
))
Since 0 nE[1/o?] for B ~ 1 Ei
8b and
d
the above can thus be written as
n
na
1/
Var(3))
B
E
E
E
Bo 1/00
which proves claim.
20

---

C Covariance models
In this section we calculate the step sizes of the covariance models listed in Table and plotted in Figure 2. Additionally we calculate the asymptotic learning rate of A-RFD and prove an Assumption of Corollary 5.3 for the squared exponential covariance (Prop. C.3).
C.1 Squared exponential
The squared exponential covariance function is given by
7 y1l 0² exp(
(11)
Note that o² will play no role in the step sizes of RFD due to its scale invariance (cf. Advantage 2.3). Theorem C.I. Let J N(u, C) where the squared exponential covariance function (11), then we have
(ww)
argmin B[J - d) J(w), vJ(w)]
[w] d
with RFD step size
VJ [W)Ill
Jim] 2 [w)) M-J(w)
Proof.
The covariance function C' is of the form
C(h) o²e 2
By Equation (2)
C 1)* argmin C1O)
C' O.
where è
[w=] [w)
We calculate
C
C² (²(
C(0)
1
(0(
θ
2.2 (1+ 79).
This results in the first order condition
L
22 277
(1 ())
2,
22
θ
22
(1 + 1 -²))
Since the exponential never be zero, we have to solve quadratic equation. Its solution results in
7 (0)
(12)
35
25
At this point we could stop, but the result is numerically unstable as it suffers from catastrophic cancellation. To solve this issue we set x 20 and reorder
8
+
x x
1 V x2 + (V2² 52 x))
+
2
+
V
+ + + E
Re-substituting x
1 a-J(w) [[
we finally get
28
2 VJ
((w(ww) 2
(w)
(ar
+ [w)) + p-J(w)
2
Proposition C.2 (A-RFD for the Squared Exponential Covariance). J is isotropic with squared exponential covariance (11), then the step size of A-RFD given by
2
i
VJ(w)l,
1 J(w)
21

---

Proof. By Definition 5.1 of A-RFD and θ [J
we have
1- (w)
(()) n)(@) (0)
θ x² exp [
[J] Jr ((w
z exp(0)
Proposition C.3. J isotropic with squared exponential covariance (11), then the RFD step sizes strictly monotonously increasing in e
Proof. Since we know that - 0 implies vy" ~ n - strict monotonicity of in sufficient to show that 17" 0 also implies @ 0. So take the derivative of (12) resulting in
do " (2+)
d
20
which is greater zero for all θ > O.
C.2 Rational quadratic
The rational quadratic covariance function is given by
((
= 0² (1 (1+
a yll
-8/2
8 0.
(13)
Bg
It can be viewed scale mixture of the squared exponential and converges to the squared exponential in the limit | + oo [44, p. 87].
Theorem C.4 (Rational Quadratic). For J (N,, where C is the rational quadratic covariance
2 0 that the RFD step size is given by we have for j (1r)
[V[(w)
a/3 Root (-1+
(1+ (1
de 26
The unique root of the polynomial in can be found either directly with formula for polynomials of third degree (e.g. using Cardano's 's method) or by bisection as is contained in [0, 1/ /1 +1+117 3).
Proof. By Theorem 4.2 we have
1j" argmin c(4)
C(
C(0)
for =())= +
2x Dz2
-B/2, We therefore need to minimize
f(
17
= = (1+
3/2
1+
n72
-1/2-1
O.
B3
352
3z2
Substitute in ń = .3a- then the first order condition is
_ ('( f = di (1 (++1?) 172) 8/2 + v Bsn (1 + +1))) -3/2-1 θ
-
Dividing both sides by VBs0 we get
f(( VBst
0 = (1 + - -
+ (1 + (i2) - 1 + 172 - C + 1)27
vpso
= (1+ + アー -
3îj
(1 + ; - 11 (1 B)]
vpsa
=-1+
46 7 +1+
Since θ 2 0 and B > 0 all coefficients of the polynomial are positive except for the shift. The polynomial thus starts out at zero and only increases from there. Therefore there exists unique positive critical point which is a minimum.
At the point 7 v1 the quadratic term is already larger than I the polynomial is positive and we have passed the root. The minimum is therefore contained in the interval [0, vT /
After finding the minimum in î return to 17 by multiplication with /Bs.
22

---

Proposition C.5 (A-RFD for the Rational Quadratic Covariance). If J is isotropic with rational quadratic covariance (13), then the step size of A-RFD is given by
2²
i
[J[()]]-
J (w)
Proof. C(x) = o² +
2it 18 )-8/2 implies by Definition 5.1 of A-RFD and è [V]
n(()) Co(0) -= 01+ V+(
- 8² (z)]l
((r
C.3 Matérn
Definition C.6. The Matérn model parametrized by s 0,0 0,0² 2 is given by
c( 0² =222~ 2-1-"
C( (i--vll
r(v) (vamla-vi) Kr ( (
(
(14)
where K2 is the modified Bessel function.
For p 2 with p No, it can be simplified [ef. 44, sec. 4.2.1] to
/2v
v
w/1) %
C( u--yle 0²e
12p R)1 KJRR
2v/2u |
(2p) k=
The Matérn model encompasses Rasmussen and Williams [44]
the nugget effect for 0 (independent randomness)
the exponential model for
Penstein-Uhlenbee process)
the squared exponential model for v + oo with the same scale and variance o².
The random functions induced by the Matérn model a.s. [r] -timmees differentiable Rasmussen and Williams [44], i.e. the smoothness of the model increases with increasing v. While the exponential covariance model with 1/ results in random function which is not yet differentiable, larger result in increasing differentiability. As differentiability starts with v 2 and we have a more explicit formula for v = + 1/2 the cases v/ = and / = are of particular interest.
"[F]or 2 7/2, in the absence of explicit prior knowledge about the existence of higher order derivatives, it probably very hard from finite noisy training examples distinguish between values of 7/2 (or even distinguish between finite values of i and v + co, the smooth squared exponential, in this case)" [44, p. 85).
Theorem C.7. Assuming J ~ N(,,, C) is random function where C is the Matérn covariance such that ppp with p {1, 2). Then the RFD step is given for θ [[J[W]]]
0 by p-0
p
5
1¹"
v3
v3
1
+
s
*p= =2=2
(1 (1-5) + /4 + C)+
x== V5
17'
V5 2(1 + <)
3s0
Proof. We define C(n) = C(2)) which implies
c'(n)= = C² (1)
23

---

or conversely
c(3)) C(())
(15)
By Theorem 4.2, we need to calculate
0 C(0)
C' (O)
1 argmin
11
O.
(16)
Discarding a w.l.o.g. due to scale invariance (Advantage 2.3), we have in the case =
C(n) (1 5 exp (- v3
v3
(-yan)
The derivative then given by
('(1) - -3 1f nexp( eexp(->211 x)
which implies using (15)
(²(2) = - (v3) 2
exp(-va5
(17)
We therefore need to minimize (16) which is given by
argmin - (1 + - n) exp( () 17 expp
1/ n)
argmin - + (33 + +0)n) exp exp(-
1))
7
The first order condition is
3 9 (I + (v33 + + ?ي + t))
which (divided by O and noting that the exponential can never be zero) is equivalent to
1 v3 (33 00
+ 1)
reordering for 7) implies
v3 (1+ v3
also not difficult to see that this is the point where the derivative switches from negative to positive (i.e. minimum).
Let us now consider the case p = 2, i.e.
C(1) (1 v3
1 1)
n²=" exp (- n)
which results in
("))) = 35
(n +
l
1 exp( (-(5 x5,
$
i.e. by (15)
c²(x5) = 35
5 (I +
L n) exp( (-ffa))
(18)
We therefore need to minimize (16) which is given by
(-(1+ 2i + "² 7 + ش n)
exp( (xp(->
(1+
ب.ب ))²)
5
The first order condition results in
0 - v/5
V5
O)7 +
5 3.
+
x)))n²² - (3/ + 2 33 + 8
=)0111)
8
15
v5
+ y5 ))
= +
33d
352
Dividing everything by O and using : 3.63 get
v
-1 (s- 1)( 1 n) + (S + (1)
Taking a closer look at the sign changes of the derivative it becomes obvious, that the positive root is the minimum, i.e.
V5 77
(1 <) + +1 4(1+5) (1()) / 4+ (1+
2(1+()
2(1 +(
24

---

Proposition C.8 (A-RFD for the Matérn Covariance). If is isotropic with Matérn covariance (14)
such that = p 2. then the step size of A-FD for p {1,2} is given by
p
5² VJ μ (x)
p =p=2 2
3s VJ 1
(z)
Proof. Noting θ
[[V](x)]| (a))
have by Definition 5.1 of A-RFD for p
C(O) (17) s²
n = -C'(0) 3 O
and in the case p = 2
C(O)
+ (18) 38
O.
C*(() 5
D Proofs
In this section we prove all the claims made in the main body.
D.1
Section 2: Random function descent
D.1.1 Formal RFD
As we mentioned footnote at definition RFD, the fact that the parameters become random variables they are selected by random gradients poses some mathematical challenges which would have been distracting to address in the main body. In following paragraphs leading up to Definition D.I introduce and discuss the probability theory required to provide mathematically sound definition.
For fixed cost distribution PJ and any weight vectors w and v the conditional distribution
E E[J (w) J (w), [J)))
is by its axiomatic definition (Jww, VJ ( measurable random variable. By the factorization
lemma [30, Cor. 1.9.7], there therefore exists a measurable function (j.g) + PP (j. g) such that the following equation holds almost surely
Pw (J))( VJ(w)) ( J(w), (u)))..
(19)
Since is possible calculate fw,ü explicitly in the Gaussian case (cf. G.1), the function
R R Rdd R
Tr, (w. j.g) argmin Pw, (j.g),
which implements some tie-breaker rules for set valued argmin is measurable when J is Gaussian and its covariance function is sufficiently smooth. To prove measurability in the general case is difficult problem of its own, which we do not attempt to solve here, since we would not utilize the conditional expectation outside of the Gaussian case anyway (cf. Section E.3). For deterministic w, we therefore have
Dr, (w, J(w), VJ(w)) argmin Pu (Jw), VJ(w))
MigminnEJir i (w), VJ(w).
25

---

So if the parameter vectors Wn were deterministic, our formal definition of RFD and our initial definition would coincide. But for random weights W (19) stops hold general', i..
Pw,a (J(W), VJ(W)) + ( J(W).
VJ(W)).
this equation does need hold, we similarly have in general
Fr (W,J (W), VJ(W)) Af argmin E ( J(W), VJ(W)].
So the following definition is not just restatement of the original definition of RFD. Definition D.1 (Formal RFD). For Gaussian random cost function J, define the RFD algorithm with starting point Wo = wp E g by
W == Op (W J(W,), VJ(W.))
This is what effectively do in Theorem 4.2 under the additional isotropy assumption, where calculate the argmin under the assumption that w is deterministic (i.e. we determine Pr,), before we plug-in the random variables Wa obtain W., Wn+1. Similarly this is how the step size prescriptions of RFD actually work. We first assume deterministic weights and later plug the random variables into our formulas. For this reason, we avoided large letters indicating random variables for parameters w in the main body.
D.1.2 Scale invariance
Advantage 2.3 (Scale invariance). RFD invariant to additive shifts and positive scaling of the cost
J. RFD is also invariant with respect transformations of the parameter input of J by differentiable bijections whose Jacobian is invertible everywhere (e.g. invertible linear maps).
Before we get to the proof, let quickly formulate the statement in mathematical terms. Let Wne be the parameters selected optimizing J starting in wi and w. the parameters selected by the same optimizer optimizing J starting in tōp-
we apply affine linear scaling to cost such that (ww = aJ (w) + and start optimization in the same point, i.e. wh Wy. then we expect scale invariant optimizer to select
aJ(w)
WR
If we scale inputs on the other hand (or more generally map them with bijection Φ), then expect for J : J & and starting point whp x (wo). that this relationship is retained by scale invariant optimizer, i.e.
W x (ww))
Why do we use different starting point? As an illustrating example, assume that maps miles into kilometers. Then J accepts miles, while J accepts kilometers. Then we have map the initial starting point of J measured in kilometers into miles wp. o is precisely this transformation from kilometers into miles. A scale invariant optimizer should retain this relation, i.c. no matter if the input is measured in miles or kilometers the same points are selected.
Proof. The following proof will be split into three parts. The first two parts of the proof will address a more general audience and ignore the mathematical subtleties we discussed in Section D. the third part we explain to the interested probabilists how to resolve these issues.
1. Invariance with regard to affine linear scaling
Let (ww == (w) + b where a > 0 and b E R and assume vp Wg- With the induction start given, we only require the induction step to prove w. Wn.
'Eg. consider the random variable
(argmin 1u(0)so + (argmax 1u
In this case, J(W) is much more informative of ( than J (w) some deterministic
26

---

For the induction step, we assume this equation holds up to n. Since Φ(z) = a.r + b is a measurable bijection, the sigma algebra" generated by
(Jww), (w,)) = (ø J (wn), (w,))
is therefore equal to the sigma algebra generated by (J (w,,, (I(W))) This implies
Wn+1
argmin E B (w) (w.)) (..))
w
induction
argmin E (w) (w.). (ww)))
sigma argmin E (w)
(w,), [J(w,)]
(20)
linearity
argmin (w)) J (wx). VJ(w.,)] +
monotonicity
argmin B (t) J (w,). VJ(w.)]
def.
Wn++11
Where we have used the linearity of the conditional expectation and the strict monotonicity of ((x) b.
2. Invariance with regard to certain input bijections
Let ø be a differentiable bijection whose jacobian is invertible everywhere and assume J := J ø. Since Φ is a bijection, ((M) is the domain of J whenever M is the domain of
For starting point Wh ((M) the claim
assume th -- (ww) M and are again going to prove
Wr (w,).
by induction. Assume that we have this claim up to n. Then we have by induction
j (w.) ( (ww)
(21)
and
vi(w.) = Va, (J e (( = d' ( (VJ)(
VJW,)
Since (b(w)) is invertible by assumption, the sigma algebras generated by (iūn) vJ(w)) and Iw,). (mw,) are identical. But this results in the induction step
Wn+1 argmin [ (w) [ww), vū,))
WEM
sigma alg.
argmin E [[[ (w)
(w,), [[(w,)]
WEM
def.
argmin EJJ 6(w) J (w.). (www))
(22)
wEM
= = aargmin [[[ J(wn), VJ(w)))
BEO(M)
where we simply optimize over ((w) instead and correct the argmin the end.
3. Addressing the subtleties
In equation (20) we have really proven for deterministic w
hr, (w, (w), vī(w)) 4e, (w.J(w). VJ(w)).
But this implies with the induction assumption W,, W.,
W Wa+1 = Dr, (W., (W.), vj(W.)) ind. d (W,, J(W),, VJ(W.)) = W,+ 'if you unfamiliar with sigma algebras read them "information".
27

---

Similarly we have proven in (22) that
4r, ( (o (J - (w, vJ(w))).
By the induction assumption W x (W',, this implies
W n+1 De, (Wi, J (w,) ,) vJ(W)))
ind. Qp, ( (W,, J( vi(6-((W,))
= = (0, JW, JWW,) vJ(W))
= = (W+i)
D.2
Section 4: Relation to gradient descent
Lemma 4.1 (Explicit first order stochastic Taylor approximation). For N(u, C) the first order stochastic Taylor approximation is given by
E[J(w d) J(w), VJ(w)) =u+ + C² dil
C(0) (J(w) - p) C² Id C" d, VJW)).
Proof. (J(w), VJ(w)) J - d)) is a Gaussian vector which the conditional distribution is well known. It only necessary calculate the covariance matrix. The key ingredient here is to observe that Jww,, J,J (wr,..., OaJ( 3aJ(w) are independent, trivializing matrix inversion.
More formally, by Lemma G.2 we have
(
)) ((O)
Cov
CC'
and
Cov [[( Cov(J(w-
(J((m)) ))
J(w)
C c(Laal
-d),
C² ||dli d
By Theorem G.I we therefore know that
C |idll
C(O)
J ((w) vJ(w))
B w d) J(w), VJ(w) +
c
li jd
-C' (O)
which immediately yields the claim.
Theorem 4.2 (Explicit RFD). Let J N(,, C), then RFD coincides with gradient descent
(w..)
Wn+1 = Wp 7n [VJ
where the RFD step sizes are given by
C(
(²
1 = argmin
(J(wn) 11) C(O)
J(w))l
C*(0)
VER
Proof. The explicit version of RED follows essentially by fixing the step size 7) = |d]] and optimizing the direction first. With Lemma 4.1 we have
EinE d) (ww), VJ(w]
min min #
2 (J(w) 11)
(d. VJ(w))
720 d: dil=
C(0)
c(3))
c((+²)
max (d, VJ vJ(w))
2 0 C²(0)
min
(J(w) 4) C²(0)
d:jdd|=nn
20
((0)
min (d, vJ(w))
< 0.
d:||d|=n
C((0)
28

---

By Lemma G.3 and Corollary G.4 the maximizing minimizing step direction is then given by
VJ
d(n) - -n V (w))
Where it is typically to be expected, that we have a positive sign. Since that depends on the covariance though, avoid this problem with the following argument: Since only appears as 17² in the remaining equation, we can optimize over 1 E IR the outer minimization instead of over 7) 2 0 to move the sign into the step size 77 and set without loss of generality
(w)
d(n)
[V[(w)]
Since (d(n), VJ(w)) 7| (w))l the remaining outer minimization problem over the step size is then given by
-w) C² C a6) 4) 7ER ((0)
min
(O)
Its minimizer by definition the RFD step size given in the Theorem.
D.3 Section RFD-step sizes
Proposition D.2 (Tayloring the step size optimization problem). The second order Taylor approxi- mation of the step size optimization problem
C( C² C(O)
ge(
7
around zero is given by
T1) -1 1 + 2 (0) 2C(())
minimized by Trgmi C(O) O.
-C)
Furthermore, the Taylor residual is bounded by
(a(n) T29(n)] S 1 co +
with co = max maxxssupeennul(((()) (C" + (ooo < co.
Proof. Using the Taylor approximation with the mean value reminder for C, we get
c(3)) C(0) + c((()) (2²)²
2!
(² C(0)
for some 0,,02 E [0, ] This implies
C" ("(())) 17 C(O) 23 (²
C²((1)
((1) (-(1+
C' C(U)
1 1
By the following error the optimistically defined (1) is really the second Taylor approximation (which can be confirmed manually, but deduce it by arguing that its residual is in O17²)). More specifically,
(q(n) T2q(n) S </3'
sup
velo.
22 (C)(
sup
eejo
(C)
Lem. D.8 S
1y 17 + +)
2C(0)
2 (0)
is easy to see for (w:) < that T29(1) is convex parabola due to C² < 0. We thus have
== argmin Tege (n) -c"
C(0) O.
29

---

Theorem D.3 (Details of Proposition 5.2). Let ~ Nip, C) and assume there exists 1l > 0 such that the correlation for larger distances 2 To are bounded smaller than 1, i.e. C(a²² (2) Then there exists K, Oo > 0 such that for all θ < O
< E (0, 1).
C(0)
1 1 1-K - (0) f((@)
1 11 KO.
particular we have of (0) () as θ - 0 or equivalently as v - 0.
Proof. This follows immediately from Lemma D.4, Lemma D.5 and Lemma D.6.
Corollary 5.3. Assume "i 0 implies θ + O, the cost J is bounded, has continuous gradients and RFD converges to some point Woo. Then Wao is critical point and the RFD step sizes rý" are asymptotically equal to ft.
Proof. Assuming RFD converges, its step sizes v)" converge zero. But this implies @ - 0 by assumption, i.e.
θ VJ (w))
0
1 J (w)
Since (w) is bounded, this implies V [w)l + 0 and by continuity the of the gradient, it is zero in its limit. Thus converge to stationary point. The asymptotic equality follows by Lemma D.4 and Lemma D.5, as we know 17" converges so we do not require the assumptions of Lemma D.6.
D.3.1 Locating the Minimizer
In the following we want to rule out locations for the RFD step size 1j" by proving ge > (e for a wide range of n, For this endeavour the relative position of the step size 1) relative to r is useful re-parametrization
= (7A An-
C(O) θ we obtain Due to n (0)
(1) -1 1/0 522 -C((U) C(0)
-1 A(} 1)r0
On the other hand we have for the bound
gee (n) - (1)) $ 23//8 co (> > + 1 1)@
C(U)
Since f (1) we thus obtain
qe ge (n)
T2ge (1) (1) T2ge (17) T2go (1) Ige (f) T2ge (
i10
i10
(A(2 1) -- b)) - [x0(2
[[]" (1
\
C(0)
+1) +
(() + 11]
C(0)
- 2²
= =1 - X)² - ci {x
| + +1) +
C [ + +1)]
(23)
This equation will be the basis of number of lemmas ruling out various step sizes as minimizers.
Lemma D.4 (Ruling out small step sizes). If the step size is (much) smaller than the asymptotic step size ij = i(),, then can not be a minimizer. More specifically
?
E 1 (0,1-c99) = g0(n) > (
C(0) where 01 : (0) V co
1) x0.
30

---

Proof. Here we consider the case S n. i.e. A [0. By (23) we have
2e (1)
ge (i)
(1 2)² c/ 1 ( C(o)
aaccr(0 + +1) +
+1)
iif)
2 21 -)2 2nj²cn
[C] +1)
((0)
for which
(1 (1= 4f c0
[[- 1)
C
is sufficient or equivalently
A <<L 1 12-22// c0
[[0| (0(200))
C10)
+1) = 1- 2
C(O)
co
C(O)
+1
=001
So for X E [0, 1 θc1) we have ()(1) > ge (f)
Lemma D.5 (Ruling out medium sized step sizes as minimizer). For 02 = 201 and θ S Og == we have
beg
! う/ (1+ m
qe > ge ge(
Proof. Here we consider the case 2 1, i.e. > nj. Again starting with (23) we get
((1)
q(1)
2 a)² 8/²cu 1
(2 +1) + 4|C + 1
CiO)
C(O)
n10
2 2 - 1)² 2/'1/00 0 (000 +1)
C(O)
~ 0,
for which
C10) À 1 22 co [0)
+1) o2
or equivalently
- 1 c1 0
sufficient, Note that this is concave parabola in A. So it is positive between its zeros which are characterized by
e - X 11
They are thus given by
1 VI 1c
112
20,0
So whenever À E A2) we have that ge > 10 (1). In particular for 4c S or equivalently
+ < 4et
we have
1
20 c26
To get a bound on A note that the original equation was essentially
2 1+ Oxx
with equality for À A₁ if θ is reduced, the inequality remains, which implies that X is decreasing with O. So assuming the inequality is satisfied for particular À e.g. À = v2 which requires
V 2 1 0
/2-1
2c,
then know that \ 22 for all smaller O This implies for O < On 5c
<
22-1 20g
\₂ 1 1 + < 1 + 20 θ.
31

---

Lemma D.6 (Ruling out large step sizes as minimizer). If there exists step size no > 0 such that the correlation is bounded by some p 1, i.e.
C( C(O)
p (0,1);
for larger step sizes 2 17, then there exist O, > 0 such that for all è < Oo
" E (1 + c20, = ((n) > (()).
f
where 02 is the constant from Lemma D.5.
Proof. The upper bound _ in Lemma D.5 is only due the loss of precision of the Taylor og approximation. To remove it, we take closer look at the actual go itself. We have the following bound for our asymptotic minimum
qel (7) S 4
T240 (f) (g) T2)
n co
C(a) (0)
+1)
+
2
+
c/'c3
Which means we have for
9e (n)
ge (1)
(1
C( C²(4))
"
1/00 C3
θ
C(0) 6 C"(0)
Lemma D.7
(1 C(0) 0 --0((0) 1/03
C(5)
Vo(
2
(1 M)
/C
1/33
V-)((0)
0,
c( where we use the assumption that there exists E (0, 1) such that p 2 c( for all 1 2 no and the fact that we only need consider 77 rg To into some maximal 9g. Note that ; θ vanishes as θ + 0, so eventually the term (1 - M) M) g dominates. Selecting On small small enough thus sufficient cover everything that is not already covered by Lemma D.5.
1 (due Lemma D.5) which allows translation of
D.3.2 Technical bounds
Lemma D.7 (Bound on the first derivative of the covariance).
CC' (5 ml S (-C
sup
n20
Proof. Since we have
(ov( C' C' ( y, 2)
we have for a standardized vector |||||| and - y mp by Cauchy-Schwarz
C.. C² (2) = (ov J()) S VVr(DD,J (x)) Var(J(v)) (-C(()))())
As the bound is independent of 7y this yields the claim.
Lemma D.8 (Bound the second derivative of the covariance).
sup [C)( S max sup 8E(0.1]
[C"(0),,
020
32

---

Proof. Note that
(ov(D, (w)) -C" (ا )o y/ u) y, w) C²( C((lا=م) (v, w)
Selecting orthonormal vectors (e.g. t= eI, e2) and x y = m7(1 + w) for some 0 results in || yll² 2n/² and thus by the Cauchy-Schward inequality
CS.. 1-""(""" (z) S (Var(D.((t) Var(D.. (0))
This implies the claim.
D.4
Section 6: Stochastic loss
Lemma D.9. The stochastic approximation errors
<((w) :- f:(w) [ww
are identically distributed, centered random functions, which are independent conditional on In particular,
(lei(w)), = [le,(()), [
Proof. The e are independent random functions conditional on f, since for any E N, any bounded measurable functions and
h( ..... (w,,) (((,)) F)
(i(e((w).......eel E (1r) (s(w)) le, Xi, [r]
-m[n(cs(wn) (((((t)).....(((..)) If (g) (ww)) [f]
where (*) uses the fact that ej does not depend on the independent X,, s.. Since almost by definition
EEle f] E[((- X,, Yi) f] J(-) O,
the stochastic approximation errors are thus uncorrelated
E[GG,] = E Elcc; f]]
E Bic
f]E(e, f|] 0.
Extension 6.2 (S-RFD). For loss J ~ N(H, O) and stochastic errors e No C.) we have
arginin E[J d) (s(w), VLI(w)] 17" (0) (w) with the same step size function 1f" as for RFD, but modified +
(v]]
(0) C(O) (O) [VV C'(0) +C
θ
C(0) - La (w)
Proof. Since e are conditionally independent between each other and J, as entire functions, the same holds true for Ve,. As all the mixed covariances disappear we have
cor(( Co(ze) Cov ((el(e)) = Cor (()(a)
(E((w)))
+
Cov
12
C(00)
Cc(0)
Lo'(o)
+
82
(O)
1=1
(C(0) + (CC((0)
+ - - +
33

---

by Lemma G.2. If you want to break the first step we recommend considering individual entries of the covariance matrix to convince yourself that all the mixed covariances disappear. Together with the fact
Cov (Jo(J(w d),
(r(w) (VLo(w))
6 Cov J(w d), (
= =Cov (J(w d).
(()
Σ
<:(w)
Vei(w)
62
C c(la C" d
The rest is analogous to Lemma 4.1 and Theorem 4.2, so we only sketch the remaining steps.
Applying Theorem G.1 as in Lemma 4.1 obtain stochastic version of the stochastic Taylor approximation ("stochastic" Taylor approximation" " perhaps?)
(lla 2
C" (rddd
[[J(w- d) (.(w), VLo(w)] F C(O) + (CC(0) (Co(w) - C²(0) + C,
(d, Lo(w)).
Minimizing this subject to a constant step size as in Theorem 4.2 results in
C²( |d
17' = argmin
C(0) C. (Ca(w) 11)
" C'(0) + + (C [(((w)
NER
C |dl
C(
C(O)
||(,(w)]|
argmin
C(O) -1 C'(0) + (O C(O) + (0) (sww)'
nER
where we divided the term by ((0)+ (x²e follows by definition of 17" (9) and our redefinition of e.
C(O)
2 0 to obtain the last equation. The claim
E Extensions
In this section we present few possible extensions to Theorem 4.2, which are composable, ie. it is possible combine these extensions without any major problems (including S-RFD, i.c Extension 6.2).
E.1 Geometric anisotropy/Adappivve step sizes
In this section, we discuss the generalization of isotropy to "geometric anisotropies" [50, p. 17], which provide good insights into the inner workings of adaptive learning rates (c.g. AdaGrad [14] and Adam [29]).
Definition E.1 (Geometric Anisotropy). We say random function J exhibits "geometric anisotropy", if there exists an invertible matrix such that J(z) = =(Ar) for some isotropic random function g.
This implies that the expectation of J is still constant (x)) Elg((x)) = 14) and the covariance function of J is given
(ov( = Cov(g(An) = C( || w0ll c( ||
y 2 ATA
(24)
2
where : l/s is the norm induced by (z.0)x := (x, Ey) for some strictly positive definite matrix Σ= A Here (24) characterizes the set random functions with a geometric anisotropy in the
Gaussian case, because for an J with such a covariance we can always obtain an isotropic g by g(x) == J()- This the whitening transformation we suggest looking for order to ensure isotropy in the context of scale invariance (Section 2).
34

---

An important observation is, that Theorem F.2 implies that J is still stationary, so the distribution of J is still invariant to translations. If stationarity problem, this is therefore not the solution. But geometric anisotropies are a beautiful model to explain preconditioning and adaptive step sizes, For this, we first determine the RFD steps.
Extension E.2 (RFD steps under geometric anisotropy). Let be a Gaussian random function which exhibits a "geometric anisotropy" A and based on an isotropic random function g N Nu, C). Then the RFD steps are given by
(w) argmin [[J - -d) [(w), vJ(w)]
with
Σ VJ /
||ا
"/ argmin (n) where θ
Proofsketch. There are two ways to see this. Either we apply scale invariance (Advantage 2.3) directly to translate the steps on g into steps on J. Alternatively one can manually retrace the steps of the proof. Details in Subsection E.1.1
The step direction therefore
Σ VJ))(()
and Σー1 acts as a preconditioner. So how would one obtain Σ? As it turns out the following holds true (by Lemma G.2)
[V -
VVE[Vg(()VV((()) A (T(C'(0))) -C'(
In their proposal of the first "adaptive" method, AdaGrad, Duchi et al. [14] suggest to use the matrix
G =
which is basically already looking like an estimation method of E. They then restrict themselves to diag(G.) due to the computational costs of full matrix inversion. This results in entry-wise ("adaptive") learning rates. Later adaptive methods like RMSProp [22], AdaDelta [57] and in particular Adam [29] replace this sum with exponential mean estimate, i.e. in the case of Adam the decay rate B2 is used to get an exponential moving average
12= B2u + (1 - .32) diag VJ (w, VVJ()))))) = 320 (1 32) (VJ(w.))
They then take the expectation
Elve] B [ 32)
8/ - VJ (Wx)2
BB
32)
3 - [w))]] (1 V (x.)²
xcdiag(E)
So 8 -v//// 111(11 83) in the Adam optimizer essentially an estimator for diag(E) It is noteworthy, that Kingma and Ba [29] already used the expectation symbol. This is despite the fact, that they did not yet model the optimization objective J as a random function.
We can not yet explain why they then the square root of their estimate (i) -1/2 instead of diag(E)-1 itself. This might have something to do with the fact that the estimation of G, happens online and the J(w)) estimator has different properties than the estimator itself. Finally, the fact that only the diagonal is used might also be the reason, if the preconditioner diag(E)-114 ourselves to diagonal matrices.
therefore highly correlated. Another reason might be that the inverse of an
11)2 -1/2 is simply better when we restrict
35

---

E.1.1 Proof of Extension E.2
Since the application of scale invariance provides no intuition, we provide proof which retraces some of the steps of the original proof.
Recall, that for an isotropic random function we have the stochastic Taylor approximation
El d) g()), Vg(+)) = na + C( ((laale)
C(0) (g(w)) - -4) C²(
(d. Vg(u:)
C²())
This implies for random function with geometric anisotropy J(w) = g(Aw) that J d) J(w,, vJ(w)] Elg(A(w- - d)) g(Aw), vg(Aw))
C( ||AdI
(g(Aw) - 11) C' ||Ad]]
(Ad, Vg(Aw))
C(0)
C'(0)
C( [
C" ||dI| C"())
pt +
2 C(O)
(J(w) 11)
2
(d, A Vg(Aw)
=V](w)
with :
= A. As in the original proof, we now optimize over the direction first, while keeping the step size constant, although now fix the step size with regard to the norm || means that we still do the optimization in the isotropic space). Note that
||x (which basically
max vI()))
s.t.
||d||
equivalent to
max E E
VJ(x)a s.t.
||||s "
which is solved by
V-'VJ(')
The remainder of the proof is exactly the same in the original.
E.2 Conservative RFD
In the first paragraph of Section we motivated the relation between RFD and classical optimization with the observation, that gradient descent is the minimizer of regularized first order Taylor
approximation
(w) argmin [[J(w d) J(w), VJ(w)] + - ||w||
This regularized Taylor approximation in fact an upper bound on our function under the L- smoothness assumption [38], i.e.
J (w d)) d) T[J(w d) (ww), VJ(w) + ||d]
improvement on of this upper bound compared to (ax) therefore guarantees an improvement of the loss. This guarantee was lost with the conditional expectation (on purpose, as we wanted to consider the average case). Losing this guarantee also makes convergence proofs more difficult as they typically make use of this improvement. In view of the confidence intervals of Figure 1, it is natural to ask for a similar upper bound in the random setting, where this can only be the top of an confidence interval. This is provided in the following theorem
Lemma E.3 (An y-upper bound). We have
IP J[w d) < E[J(W d) J(w), VJ(w)] + (((l))))) 27
for (T(1) = --'())0())) with
C(5)2 -10)
O' C²(11)2
o² (- C(0)
C(()
C'(0)
where de is the cumulative distribution function (cdf) of the standard normal distribution.
36

---

Proof. Note that the conditional variance is with the usual argument about the covariance matrices (cf. the proof of Thoerem 4.2) using Lemma G.2 and an application of Theorem G.1 given by
C )
C² )
(1101))) = Var[J(w d) [(w), ( = C(0)
2 (0)
|||
C(0)
Since the conditional distribution is normal (by Theorem G.1), we have
Ji d) -[ - d) J J(w), VJ(w)] ~ (),
o a([w|??
But this implies the claim
P J(w d) S [[ d) J(w), VJ(w)] + (((())))))
P J(w d) - E d) J(w). VJ(w)] < Φ - (7))
o <<|
=b( y
To avoid the Gaussian assumption, could apply the Markov inequality instead, or another applicable concentration inequality.
Using this upper bound, we obtain natural conservative extension of RFD
Extension E.4 (y-conservative RFD), Let J ~ (p, C) and p=, 4 (n))) where a is the conditional standard deviation as defined in Lemma E.3. Then the conservative RFD step direction given by
VJ(w) VJ [w]
argmin E[ - d) J(w), VJ(w)] + +
and the 7-conservative RFD step size is given by
C ((0) (J(w) - (0)
C²( C*(0)
17" argmin
[VJ(w)] (T())
Proof. The proof is the same as in Theorem 4.2 with Lemma 4.1 replaced by Lemma E.3.
Taking multiple steps should generally have averaging effect,
expect faster convergence for almost risk neutral minimization the conditional expectation (i.e. 7 R f)) Here y is a natural parameter to vary conservatism. In a software implementation it might be good idea to call this parameter 'conservatism' and rescale it to be in [0, 1] instead of 2 1]. But formulas look cleaner with 7.
In Bayesian optimization it is much more common to reverse this approach and minimize lower confidence bound ("conservatism' < 0 or 7 < 2)) in order to encourage exploration. But since RFD forgetful, this is not good idea for RFD.
Remark E.5 (Conservative RFD coincides asymptotically with RFD in high dimension). While conservative RFD might seem like good approach fix the instability of RFD under the isotropy assumption on some optimization problems, the variance generally vanishes in high dimension [see 5] and conservative RFD coincides asymptotically with RFD. We therefore believe that the underlying issue is not an overly risk-affine algorithm but rather that distributional assumptions, in particular the stationarity assumption, are violated when instabilities occur (cf. Section F).
Nevertheless, conservative RFD might be good approach for lower dimensional, risk-sensitive applications.
E.3 Beyond the Gaussian assumption
In this section we sketch how the extension beyond the Gaussian case using the "best linear unbiased estimator" BLUE [c.g. 27, ch. 7] works.
37

---

For this we recapitulate what BLUE is. A linear estimator Y of Y using Xi.... Xn is of the form
y E sp (X,,..., Xn) + R.
The set of unbiased linear estimators is defined as
LUE LUE X Xn] = (Ý E span(X Xn) R: B[y] = B[
(25)
(Y + B[y] E (X B[X []X ...................... Xn B[.
And the BLUE is the best linear unbiased estimator, i.e.
BLUE|Y [I...... Xn] = argmin B[|l 11
(26)
YELUE
Other risk functions to minimize possible, but this is the usual Lemma E.6. Xf .y...., Yn are multivariate normal distributed, then we have ......,,
BLUE|Y XI,..., [.....,,.] = =E(y [X,,...,X,, Xn.
EIIYY - 81111)
=
argmin
(e. meas.)
Proof. We observe that the conditional expectation of Gaussian random variables linear (Theo- rem G.I). So linear function its L risk must be larger or equal to that of the BLUE. And as an L projection [30, Cor. 8. 17] the conditional expectation was already optimal.
If now replace the conditional expectation with the BLUE, then all our theory remains the same because the result Theorem G.I remains the BLUE for general distributions [27]. Instead of minimizing
min E[J(w[[WW d) (ww, VJ(w]]
we can therefore always minimize
min BLUE - d) ((w), VJ(w)]
without the Gaussian assumption and all our results can be translated to this case. The reader only needs replace all mentions of Theorem G.1 with the BLUE equivalent and replace all "idependence" claims with "uncorrelated".
F
Input invariance
In this section we generalize the notion of isotropy to non-stationary isotropy and discuss why we believe this generalization necessary. Recall that motivated isotropy as invariant distribution with regard to isometric transformations of the input. particular its distribution stays invariant with regard translations (also known stationarity), which we do not believe plausible for cost functions, because the cost at zero (0) behaves fundamentally different from the cost of any other parameter vector.
In the following we will therefore generalize this notion to general input invariant distributions. And will discuss their applicability to machine learning after characterize the named categories. Definition F.1 (Input Invariance), A random function f is d-input invariant, if
Pr Prog
VΦ E tb.
For certain sets of we give these h-input invariant distributions names
*The input to random function is somewhat ambiguous since it is a random variable, i.e. function from the probability space Ω into function space, its first input should be w E Ω. Formally, the definition should therefore be: For all measurable sets of functions A
Pr() = Pe(A) Ve E
where d. f f denotes the pullback. But this less helpful for intuitive understanding.
38

---

If ④ is the set of isometries, we call f (stationary) isotropic.
If + is the set of translations, call f stationary.
If 4 is the set of linear isometries, we call non-stationary isotropic.
We further say a random function f is n-weakly Ø-input invariant, if for all & E Φ, all & v n and all
32
[[f()(z1)) ..... f()(==))) B[f(21) f(xx)]-
Since second moments fully determine Gaussian distributions, 2- 2-weakly input invariance is special, because it is equivalent to full input invariance the Gaussian case. So an omitted n equals "Weakly isometry invariant" naturally becomes "weakly isotropic", etc.
While stationary and stationary isotropic random functions are well known [e.g. 44, 1]. we are not aware of research non-stationary isotropy although we doubt the concept is new. It turns out that the different notions of input isometry have simple characterizations in terms of the covariance functions. We present these in Theorem F.2 of which the stationary isotropic and stationary case already well known.
Theorem F.2 (Characterization of Weak Input Invariances), Let f: Rd - be a random function,, then f is
1. weakly stationary, if and only if there exists μs E R and function C Rd TR such that for all
[+(x)= = p.
Cx(x,))= C((x -
2. weakly non-stationary isotropic, if and only if there exist functions : R20 + IR and
K D + with D {A E IR2 x IR |Aal S 2//1222 S TRS. such that for all x. y
(r(x) ( (1=)
Cr(o, 9) x(=1all
|||| 2 (x.v)) 1112
3. weakly stationary isotropic, if and only if there exists E R and a function C: R220 + I such that for all x.
pr(x) pb
CF(,,)) C( a yll
Proof. The proof essentially follow corollary from a characterization of isometries (Proposi- tion F.4). For details see Subsec F.2.
Non-stationary isotropy is therefore a generalization of stationary isotropy. allows the zero parameter vector have special meaning because the distribution only invariant linear isometries (i.e. rotations and reflections) which keep the zero in place.
It is important to highlight, that geometric anisotropy (Section E.1) retains stationarity, while breaking non-stationary isotropy. A similar geometric generalization could also be applied to non- stationary isotropy.
Another important observation is the fact, that non-stationary isotropy coincides with stationary isotropy on the sphere. Lee when ||~||| and ||y/| are constant, the function
xc( ||]|| |M ||=-012
only depends on || | v/l and the mean is also constant. In other words, we have stationary isotropy on the sphere.
Isotropy might therefore 'get by" as assumption in machine learning, parameters typi- cally initialized on the sphere. This is because Glorot intialization [18] samples parameter entries independently, their squared norm
||0| 2
(1)
1=1
39

---

is sum of independent random variables which are normalized such that a law of large numbers applies. Up small variance their lengths are therefore all the same, and are placed on a sphere at this radius.
If we leave this sphere, this equivalence stops being true. Weight normalization [46], batch normal- ization [25], weight decay [e.g. 19] or equivalently L regularization, etc. might all contribute to keep this assumption intact.
But in the following section we will see, that even simple linear regressions considered by researches investigating the average case behavior quadratic functions [e.g. 58, 43, 33, 12, 9, 40, 41], require non-stationary isotropy. Moreover the covariance kernels suggested by investigations into random
neuronal networks [e.g. 54, 8] are also non non-stationary isotropic but not stationary isotropic.
E1 Random linear regression
In this section, we determine the distribution of the cost function induced by a simple linear regression. For this we define the mean squared sample loss
(uw)) (Y fm (x))²
where the random data X is mapped by the true relationship to labels Y = f(X) and
fw (x) (x, w)
a linear model. If the true relationship is also a random linear function f(x) = (0, with random signal 0 (N, TI) independent of input X ~ NO I), then the cost function is given by
J ((w) [w) f] [ w. X)² []]
(0 w) T X [ w)
0 w|l
Lemma F3. The expectation and covariance of J are given by [[J(w)] const. + ||w|| [Jv(J(w), [w)) = const. + 4(w, ni)
In particular, the cost J is non-stationary isotropic, but not stationary isotropic.
Proof. Its expectation is given by
E [w)(
B[1 w| ||] E B[[[0|1]]
2 2 w)
||l||
const. + ||
In particular it is not constant, but dependent on ||w|| which means that we do not have stationary isotropy. But there is still hope for non-stationary isotropy, and this is essentially true can be seen by calculating
(W)) E
(J (w) E[J ([) B(J(,)))
E
[1101 |lllaa 2(0, w) - - x))
2ar(110]|2 - E|(01(2)
2 - 00 w\]
2 0| (), [6)
+ 4w "
- + 4 4ww, w)
const. + 4ww ii)
because the terms in the middle are zero, e.g.
[ 1 E| (1)) wi)l [1110|220) w)
0| (E w)
where the entries of |[]00|[00 are zero, because of independence and first moments being zero and third moments being zero.
40

---

F.2 Proof of Theorem F.2
Proposition F.4 (Characterizing isometries). Let X vectorspace and F4, yi E for 1,...,.. then the following pairs of statements are equivalent
1. (a) I; -, = V/ yj for all i,
(b) there exists translation & with 6(2,) ys for all i.
In the remainder we further assume be Hilleertspace,
2. (a) | = llaall and || - =xil = ly - yı for all i.j
(b) there exists linear isometry & with ((x+)) = y1 for all
3. (a) ||=, - zyll 11 - yyll for all j.j
(b) there exists an (affine) isometry & with ((x;) = ys for all i.
Proof. (Ia) + (lb): we define
<(x) == (yo zo);
which implies
6(x,) 2; Fo + yo (ys yo) + yo y/-
(1b) = (la): Let ((x) = x + for some Then immediately have
y1 - 6(x,) o(xx) r; (zz + c) Zj.
(2a) > (2b): By the polarization formula, for all j
(x,, xz) ||:; || + 1 | x3l1?
(Ue. 82)-
2
We apply the Gram-Schmidt orthonormalization procedure to both and y such that
Uk.. = span(puuu (u....., uk_))
for orthonormal u; where we skip Im it is already Ukm-> (resulting in km = km-11) and similarly
V = (up. )n.) = span(yi......ull
Since this procedure only uses scalar products, we inductively get
(Ix, Uz} (yk: 03) Vk,j
We now extend u, and e to orthonormal basis of X' and define the linear mapping by its behavior the basis elements Φ uy ve. Mapping orthonormal basis to orthonormal basis is an isometry and we have
d(xx) o
Σ (ox (ekkuy)u)) uy) j=1
(oks uz) (1)))
(yk uy)2z >(2x.
1=1
yk-
(2b) + (2a): Isometries preserve distances by definition. This implies || - xzyl = 1lus Vl And linear functions map 0 to 0, so we have
||
|| Ol1 [1)()))) <(0)]l ||yall-
(3a)= + (3b): We define
ã, I, 200
and similarly for y. In particular, 2o = Do = 0. Since ā; and ÿ satisfy the requirements of 2, there exists a linear isometry 3 with o = ÿ.. Then the isometry
Φ: H 2 .00) + yo
does the job.
41

---

(3b) = (3a): This is precisely the distance preserving property of Isometries.
Theorem E22 (Characterization of Weak Input Invariances). Let f: R² + IR be a random random,functio, then f is
1. weakly stationary, if and only if there exists μ E B and function C: Rd B. such that for all y
pr(z) p.
Cr(x,)) y) C(x 102-v11 y)-
2. weakly non-stationary isotropic, if and only if there exist functions μ R220 IR and
K D R with D = (A R 20 x R: \Asl S 2//1222 C R such that for all x,y
[r(x) 1 (
Cr(a, y) - x( ||]|" I|ll??
2 2 (x,y))
3. weakly stationary isotropic, if and only if there exists μ and a function C: R2o IR such that for all x,y
[F(x) =
C+(xg)= C( (===ll"))
Proof. Starting from the mean and covariance function it is easy to check 2-weak non-stationary isotropy. So we only need to check the other direction.
The proof is essentially an application of Prop. F.4. For brevity (and since the other two results are well known), will only prove the weakly non-stationary isotropic case (the other two cases be proven with minor adjustments to the proof).
Without loss of generality, we will find the slightly different representation
[[f](=)] = ((|==]] and
(x, y) x|||=]] lllll. (z.8)),
where the domain of i is given by D fA E R R |Asl - A2 The representation of the theorem is then equivalent by change
m(A) == ( and <(A1, A2. X2) = R 1 As)
First we want to find p. Let be some vector (w.l.o.g. || = 1). Then we define
u(r) = (rv))
Now we need to show that this definition of is an appropriate mean function. For this choose any x E X. Then for = ||>||| there exists by Prop. F.4 (2.) a non-stationary isometry é such that x(x) = rv (we use = 1). With 1-weak non-stationary isotropy of fa this implies
[ffa())] (ro)) u(r) =(|[=]])-
Next we need to define <(r2. ry. Tzy) For this, choose two orthonormal vectors v, w. For every (Tai Tay) E D we define
x (r) T2U
y (r) Tay Fz
Ye W.
Where E D ensures |ral ToTy and thus r
2 0. Then we have
| (r)ll = Tzx
(b0(r)) = ry,
and (x (r), Tay
(27)
and define
(( Ng Tay) == Cr, (a (a" (r)).
Again, we need show that this kernel does the job. For this, choose any x, y E X. For
r :: (1|=II, Ilv/l. (z, v)),
which is in D by the Cauchy-Schwand incquality, the induced x (r) and y (r) satisfy by (27)
|| (r)ll ||=||, Iy (r) |bvll and [xx((r) y" (r)ll || yl|-
By Prop. F4 (2.) there therefore exists an isometry e such that ((x) = x= (r) and p(y) = y (r). By
2-weak input isotropy of fa we conclude
(x,
isotmpp
(x. (r), def ([1x||, (z.
42

---

G
Technical
G.1
Conditional Gaussian distribution
For the following well known result we found tidy proof giving insight into the reason it is true, so we wrote it down for your convenience but do even expect this particular proof to be new.
Theorem G.1 (Conditional Gaussian distribution). Let X NN, 2) be maltivariate Gaussian vector where the covariance matrix is a block matrix of the form
M1
and
Σ11
Σ12
[2
Σ21
Σ2
then assuming Σn1 is invertible, the conditional distribution of X2 given X1 is
X2 X1 ~ ~N(221 Eạp1)
with conditional mean and variance
Paji
P2 + Eg1 Eji (X1 11)
Σzn = Ez2 En1 E12
Proof. Let X == X be the centered version of X. There exists some lower triangular matrix L (even if Σ is only positive semidefinite only not uniquely) such that Σ LL" (i.e. the Cholesky Decomposition). We can then write without loss of generality
Li
Y Y/
X X-
LY
X2
L
L22
with independent standard normal Y, i.e. Y AO 1).. Since En is invertible, so L1 and therefore the map from Y1 to X1. Conditioning on X1 is therefore equivalent to conditioning on Yı. But we have
X2 = P2 X2
P22 + L21Y2 conditional expectation
L22Y2
conditional distribution
So it follows that with
X₂ X1 ~ ((222 E211)
P2l1 P12 L21Vi
Σ211 == L22
What is left to do, is find representation for the Lij using the block matrices of Σ. For this note
Lu Li
Ln L2gLh L21
Σ LII
This implies
L21Yi = (L21 (4T) = En 41)
so we have the desired conditional expectation, and finally
LagLirg En2
L21
Len (L
Li
(L
Lu)
=mi
=x
=
G.2
Covariance derívatives
By Swapping integration and differentiation we have for centered random function
Cov(O,, [(x), f(v)) = [(x)(()) 0, E({())((v))
= -r,,
43

---

So the covariance of a derivative of f with is equal to partial derivative of the covariance function [more details in 1]. Similarly other covariances can be calculated, e.g.
Cov(O,,f(x)) O f()) d2, Oy Cr (z. 8).
For this reason the derivatives of the covariance function interesting they represent the covariance of derivatives.
Applying this observation to isotropic covariance functions
(ov(f(z), (z)) C (1<1==11) 1
we obtain.
Lemma G.2 (Covariance of derivatives). Lerf (N, C) and = I y. then
Cov
f(y)
aff(v)
f(x)
C( d
C² |d]l (d,
0.f(z)
C²(
[
(d, es)
- -[cm(La)) Lall" (d. (d) es) + C ld
c
[e
G.3
Constrained linear optimization
Let U be vectorspace. We define the projection of vector onto U by
(w(w): argmin ||v w|l
vet
Lemma G.3 (Constrained maximiziation of scalar products). For a linear subspace U C Rd we
have
max (u, w) (w)]l
(28)
VEU
||||==
argmax(u, w) (w(w)
(29)
(w)
NEU'
||||=>
Before we get to the proof let us note that this immediately results in the following corollary about minimization. Corollary G.4 (Constrained minimization of scalar products).
min (v, w) Po
(30)
|
(w
argmin(v, w)
(31)
eEU
|
Proof of Corollary G.4. The trick is to move one outside from w = -((rr)
min (v, w) = max (v. -w) = Pu
PEU |
"eU
where we have used in the last equation that the projection is linear (we can move the minus sign out) and the norm removes the inner minus sign. The argmin argument is similar.
Proof of Lemma G.3. Step 1: We claim that
(o(w) PP
=
results in the value (0", = Al)P((w)l
44

---

For this we consider
(w(w) = argmin vEU
||0 w|
(32)
=||v||a-2(v
argmin
||]l 2(v, w)
vEU
=:f(v)
we know that + f(t(w))) is minimized at = 1 by the definition of (w)). The first order condition implies
- dt
Pt ((P6(w)),))
and thus
1= (Pu (w), w²
(w))?
Multiplying both sides by (w))l finishes this step
Al)Po Po(w) (P w
(>
(33)
Step By (33), we know that we can achieve the value we claim be the maximum (and know the location s² to do so). So if we prove that we can not exceed this value, then it is maximum and wt the argmax. This would finish the proof. What remains to be shown is therefore
(v, w) s (())
Yo E U
||a|| X.
Let E U with ||a|| A. Then for any μ R we can plug μv into f from (32) to get
²x² 2p/u, w) f(v))
(32)
2 ((Pww) [P 2(Pyw, w)
- -P w)
where the last equation follows from (33) with x = |P Reordering we get for y
(Pow, w) + 4 x² N 2p(v, w)
We now select μ Po 0 and divide both sides by l get
(o(ww)
2(v, w) s
w
+AlIPo(w)]| 2AIlPowl
Polll
Dividing both sides by 2 yields the claim.
45

---

NeurIPS Paper Checklist
Claims
Question: Do the main claims made in the abstract and introduction accurately reflect paper's contributions and scope?
Answer: [Yes]
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made the paper and important assumptions and limitations. A No or
NA answer to this question will not be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings.
It is fine to include aspirational goals as motivation as long it is clear that these goals are not attained by the paper.
2. Limitations
Question:
Does the paper discuss the limitations the work performed by the authors?
Answer: [Yes]
Section recapitulates all the assumptions made and highlights possible generalizations.
Justification:
Guidelines:
The answer NA means that the paper has limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create separate "Limitations" section in their paper.
The paper should point out any strong assumptions and how robust the results to violations of these assumptions (e.g.. independence assumptions, noiseless settings, model well-specification, asymptotic approximations only holding locally). The authors should reflect on how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, e.g., if the approach was only tested few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect on the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution is low or images are taken in low lighting. Or speech-to-text system might not be used reliably to provide closed captions for online lectures because it fails handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and faireess.
While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, worse outcome might be that reviewers discover limitations that aren't 't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions favor of transparency play an impor- tant role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.
3. Theory Assumptions and Proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and a complete (and correct) proof?
Answer: [Yes]
46

---

Justification: Section D provides all proofs of statements made in the main body and follows an identical structure for easier cross reference.
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated or referenced the statement of any theorems.
The proofs can either appear in the main paper or the supplemental material, but if they appear in the supplemental material, the authors are encouraged to provide short proof sketch provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental Result Reproducibility
Does the paper fully disclose all the information needed to reproduce the main ex- perimental results of the paper to the extent that it affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided or not)?
Question:
Answer: [Yes]
Justification: While we not have the necessary space to discuss all implementation details, we believe that we have discussed all relevant insights necessary to reproduce our results.
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, a No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is novel architecture, describing the architecture fully might suffice, or if the contribution a specific model and empirical evaluation, it may be necessary either make it possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data is often one good way accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access to a hosted model (e.g., in the case of large language model), releasing of a model checkpoint, or other means that appropriate to the research performed.
While NeurlPS does not require releasing code, the conference does require all submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) the contribution is primarily a new algorithm, the paper should make clear how reproduce that algorithm. (b) If the contribution is primarily new model architecture, the paper should describe the architecture clearly and fully.
(c) the contribution is a new model (e.g., a large language model), then there should either be way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case authors are welcome deseribe the particular way they provide for reproducibility. In the case of closed-source models, it may be that access to the model is limited in some way (e.g., to registered users), but it should possible for other researchers to have some path to reproducing or verifying the results.
5. Open access to data and code
47

---

Question: Does the paper provide open access to the data and code, with sufficient instruc- tions faithfully reproduce the main experimental results, as described in supplemental material?
Answer: [Yes]
Justification: The code of our algorithm is fairly well commented and passes pylint and flake8 linting. The code to perform the benchmarks is less polished and we have not seeded the covariance estimation sampling process, but, since obtained similar results over multiple runs (Section A.1.1), we are confident that our results are reproducible.
Guidelines:
The answer NA means that paper does not include experiments requiring code. Please see the NeurlPS code and data submission guidelines (https://nips. cc/
stssuumiissoooooccooo.oooooooici for more details.
While we encourage the release of code and data, we understand that this might not be possible, "No" is acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for a new open-source benchmark).
The instructions should contain the exact command and environment needed to reproduce the results. See the NeurIPS code and data submission guidelines (https: wttppcccccppccccccccccccccccccct guides/ /CodeSubmii ssionPolicy) for more details.
The authors should provide instructions data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible supplemental material (appended the paper) is recommended, but including URLs to data and code is permitted.
6. Experimental Setting/Details
Question: Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [Ye]]
Justification: Training on the MNIST data set is fairly standard, so we feel like our brief outline is sufficient.
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented the core the paper to level of detail that is necessary to appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, as supplemental material.
7. Experiment Statistical Significance
Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Question:
Answer: [Yes]
Justification: Quantiles are plotted in Figure and the figures of Section and we provided histogram of asymptotic learning rates resulting from multiple covariance estimation runs (Section A.I.
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by emror bars, confi- dence intervals, or statistical significance tests, least for the experiments that support the main claims of the paper.
48

---

The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall run with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)
The assumptions made should be given (e.g., Normally distributed errors).
It should be clear whether the error bar is the standard deviation or the standard error of the mean.
OK to report 1-sigma error bars, but one should state The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that out of range (e.g. negative error rates).
If error bars are reported in tables or plots, The authors should explain in the text how they were calculated and reference the corresponding figures tables in the text.
8. Experiments Compute Resources
For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time of execution) needed reproduce the experiments?
Question:
Answer: [No]
Justification: We have not kept careful track of resources used, as MNIST fairly small dataset for machine learning standards. We believe the compute was comparatively negligible, although the use of multiple GPUs was helpful in repeating experiments in parallel.
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental runs as well as estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported the paper (e.g., preliminary or failed experiments that didn't make it into the paper).
9. Code Of Ethics
Question: Does the research conducted the paper conform, in every respect, with the NeurlPS Code of Ethics https: : //te:///neuuee /tt.//nuuip..p/ cc htcp/pblicc/thiccuiiieeeeeeeeddd
Answer: [Yes]
Justification:
See broader impacts.
Guidelines:
The answer NA means that the authors have not reviewed the NeurlPS Code of Ethics.
If the authors answer No, they should explain the special cireumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g., if there is a special consid- eration due to laws or regulations their jurisdiction).
10. Broader Impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [NA]
Justification: Since we focus optimization theory work has no societal impact beyond the advancement of the field of Machine Learning, which may have many societal consequences, but none we feel necessary to address.
49

---

Guidelines:
The answer NA means that there no societal impact of the work performed.
If the authors answer NA or No. they should explain why their work has no societal impact why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considcrations.
The conference expects that many papers will be foundational research and tied to particular applications, let alone deployments. However, if there is a direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used as intended and functioning conrectly, harms that could arise when the technology is being used as intended but gives incorrect results, and harms following from (intentional unintentional) misuse of the technology.
If there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms to monitor how system learns from feedback over time, improving the efficiency and accessibility of ML).
11. Safeguards
Does the paper deseribe safeguards that have been put in place for responsible release of data models that have high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Guidelines:
The answer NA means that the paper poses such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards is challenging, and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
12. Licenses for existing assets
Question: Are the creators or original owners of assets (e.g., code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected?
Answer: [Yes]
Justification:
We cite datasets and models used.
Guidelines:
The answer NA means that the paper does not use existing assets.
The authors should cite the original paper that produced the code package or dataset.
The authors should state which version of the asset used and, possible, include a URL
The name of the license (e.g., CC-BY 4.0) should be included for each asset.
For scraped data from a particular source (e.g., website), the copyright and terms of service of that source should be provided.
50

---

If assets are released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, paperswi thcode. cww datasets has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
For existing datasets that are re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided. If this information is not available online, the authors are encouraged to reach out to the asset's s creators.
13. New Assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [NA]
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details the dataset/code/model as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent was obtained from people whose asset is used.
At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
14. Crowdsourcing and Research with Human Subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well as details about compensation (if any)?
Answer: [NA]
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Including this information in the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as possible should be included the main paper.
According the NeurIPS Code of Ethics, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional Review Board (IRB) Approvals or Equivalent for Research with Human Subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or equivalent approval/review based the requirements of your country institution) were obtained?
Answer: [NA]
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Depending the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors to adhere to the NeurlPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review.
51


Reviews:
[{"review_id": "bUABArmE2c", "reviewer": "Reviewer_XTWd", "summary": "### Summary\n\nThe paper \"Random Function Descent\" explores the limitations of classical worst-case optimization theory in explaining the success of optimization in machine learning and selecting appropriate step sizes. It establishes a connection between Bayesian Optimization and classical optimization through a \"stochastic Taylor approximation,\" rediscovering gradient descent. This rediscovery introduces a new step size schedule called Random Function Descent (RFD), which is scale-invariant. The analysis provides a theoretical foundation for common step size heuristics such as gradient clipping and gradual learning rate warmup. The paper also proposes a statistical procedure for estimating the RFD step size schedule and validates this theory with a case study on the MNIST dataset.\n\nIn the introduction, the paper emphasizes the importance of cost function minimization in machine learning, typically performed using gradient-based methods that require step sizes chosen by established heuristics. The paper aims to enhance the theoretical understanding of these heuristics and proposes RFD as a new algorithm based on this deeper insight. The authors highlight that classical optimization theory, which relies on \\(L\\)-smoothness, provides conservative learning rates unsuitable for average cases, necessitating the reliance on step size heuristics in machine learning.\n\nThe authors bridge the gap between Bayesian Optimization (BO) and gradient-based methods by introducing a stochastic Taylor approximation based on a forgetful BO posterior. This results in the RFD optimization method, which combines the properties of gradient descent with scale invariance and a complete step size schedule derived from BO. The contributions include proving the scale invariance of RFD, discussing common distributional assumptions in BO, establishing the connection between RFD and gradient descent, and investigating the step size schedule suggested by RFD.\n\nThe paper further develops a non-parametric variance estimation method robust to covariance kernel choices and extends RFD to mini-batch losses. The case study on the MNIST dataset demonstrates the practical application and effectiveness of the proposed RFD algorithm compared to traditional methods like Adam and stochastic gradient descent (SGD). The discussion includes limitations and potential extensions of the proposed method, emphasizing the need for new mathematical theory to address the risk-affine nature of RFD and its larger step sizes.", "questions": "My main issue with this paper is understanding its final message. It feels more like a collection of relevant results rather than a cohesive argument, and I would appreciate a comment on this. If you provided two paragraphs explaining what you proved, why it is important, and what you aim to prove in the future, I still could not grasp the overall vision of the paper.", "limitations": "n/a", "rating": 5, "confidence": 4, "soundness": 4, "presentation": 3, "contribution": 2, "strengths": "### Strengths\n\n1. **Innovative Approach**: The paper introduces a novel connection between Bayesian Optimization and gradient descent through the stochastic Taylor approximation, leading to the development of Random Function Descent (RFD). This approach provides a new perspective on step size selection and optimization in machine learning.\n   \n2. **Theoretical Foundation**: The analysis of RFD step sizes offers a solid theoretical foundation for commonly used heuristics such as gradient clipping and learning rate warmup. This bridges the gap between empirical practices and theoretical understanding.\n   \n3. **Scale Invariance**: RFD's scale invariance is a significant advantage, making it robust to different scales of input parameters and cost functions. This property is stronger than the affine invariance offered by the Newton method.\n   \n4. **Practical Validation**: The statistical procedure for estimating the RFD step size schedule and its validation on the MNIST dataset demonstrate the practical applicability and effectiveness of the proposed method. The case study shows that RFD can outperform traditional optimization methods like Adam and SGD.\n   \n5. **Comprehensive Analysis**: The paper provides a thorough investigation of the step size schedule suggested by RFD, including explicit formulas, asymptotic behavior, and explanations for gradient clipping and learning rate warmup. This comprehensive analysis enhances the understanding of RFD's behavior and potential benefits.", "weaknesses": "### Weaknesses\n\n1. **Complexity and Accessibility**: The theoretical development and mathematical derivations in the paper are complex, which might limit the accessibility and understanding for practitioners who are not well-versed in advanced optimization theory and Bayesian methods.\n   \n2. **Assumptions and Simplifications**: The paper relies on certain assumptions, such as isotropic Gaussian random functions, which might not hold in all practical scenarios. The need for these assumptions could limit the generalizability of the proposed method.\n   \n3. **Risk-Affine Nature**: RFD's risk-affine nature, resulting in comparatively larger step sizes, might lead to instability in certain cases. The paper acknowledges this limitation and suggests that further work is needed to address this issue and develop new mathematical theories for convergence guarantees.\n   \n4. **Empirical Validation Scope**: While the MNIST case study is a valuable demonstration, the empirical validation is limited to a single dataset and a specific neural network architecture. Additional experiments on diverse datasets and models would strengthen the evidence for RFD's effectiveness.\n   \n5. **Variance Estimation Procedure**: The non-parametric variance estimation method, while robust, involves a bootstrapping procedure that could be computationally intensive. This might pose challenges for large-scale applications and require further optimization for practical use.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for taking the time to review our work, we are glad you find it\ninnovative!\n\n## Question (final message and vision)\n\nMost optimisers in ML have their root in convex function optimisation, a property that is far from being satisfied in reality. Modifications and tricks work well but not much can be explained by the convex root of the optimisers. We suggest a new point of view, replacing convex functions by random functions with a very natural statistical way of optimising. \n\nThe main achievement of this paper is to demonstrate the **viability** (abstract theory gives something reasonable that can be implemented) and\n**advantages** of replacing the \"convex function\" framework\nwith the \"random function\" framework. Theorem 4.2 is the main result\nestablishing **viability** assuming a given covariance model. Section 6\nis concerned with obtaining this covariance model and viability is\ndemonstrated with a practical example in the MNIST case study (Section 7).\nWe showcase the **advantages** of this approach with scale invariance\n(Theorem 2.3) and an explanation for step size heuristics such\nas warmup (cf. section 5.2). This explanation of the initial stage of\noptimization could never be delivered by the convex framework, because the\nconvexity assumption is not fulfilled initially so it can at best explain\nasymptotic behavior.\n\nWe envision the following improvements to RFD in the future: \n1. The *reliability* of RFD can be improved by generalizing\nthe distributional assumptions to cover more real world scenarios. In particular\nwe are interested in the generalization to linear isotropy because\nwe suspect that regularization such as weight and batch normalization [43, 23]\nare used to patch violations of isotropy (cf. Section F).\n2. The *performance* of RFD can also be improved. Since RFD\nis forgetful while momentum methods retains some information it is likely\nfruitful to relax the full\nforgetfulness. Furthermore, we suspect that adaptive learning rates [e.g. 12,\n27], such as those used by Adam, can be incorporated with geometric anisotropies\n(cf.  Sec. E.1). Performance could also be further improved by estimating\nthe covariance (locally) online instead of globally at the start. Finally, the\nimplementation itself can be made more performant.\n\nIn the main rebuttal we outline how we will add these clarifications to the paper with very little changes.\n\n## Addressing criticism\n\n### 1. Complexity and Accessibility, 2. Assumptions and Simplifications\n\nWriting this paper was a big challenge - we spent a lot (!) of time\ntrying to bridge the two points you address. Our approach is mathematically\ncomplex and hard to access because it requires merging a number of ideas from\ndifferent domains. That is why we used rather strong assumptions and\nsimplifications in the main body and addressed extensions only in the appendix\n(cf. Section E, e.g. a generalization to geometric anisotropies in E.1). We are\nalso working on a number of different generalizations we did not want to be part\nof this article yet, which, as you quite rightly say, is already complex. The\ncurrent version is the best compromise we could come up with.\n\nWhile we cannot reduce the Maths, we can encourage you again to check out the\ngeneral rebuttal on how we use your valuable feedback to make the article even more accessible.\n\n### 3. Risk-Affine Nature\n\nTrue! And we already suggest a way to modify the risk aversion: Confidence intervals\n(cf.  Section E.2).\n\n### 4. Empirical Validation Scope\n\nWe totally agree, in the end of the day every new algorithm must be validated on\npractical examples. When writing this article we already started working with\nempirical researchers on a systematic empirical study. As you mentioned above,\nour article is already complicated so we decided to focus on one standard\nnon-trivial example for this article to support the theory. We believe the choice was right when\naccompanied with the upcoming article. The catch so far is, sometimes RFD works\nperfectly, beating Adam with tuned parameters, sometimes it does not. This is\nnot very surprising as the algorithm relies on structural assumptions which are\nnot always satisfied (cf. Section F.1). In general Batch Normalization seems to\nbe quite important for RFD (with the isotropy assumption) to work.\n\n### 5. Cost of Variance Estimation Procedure\n\nIn our MNIST case study the cost of the bootstrapping procedure is already\ncompletely overshadowed by the sampling cost (i.e. evaluating the loss and\ngradient for various batch sizes and parameters).\n\nLet us demonstrate this irrelevance by some back of the envelope calculations:\nIf we had sampled MNIST purely with batch size 30, then one epoch would be 2000\nsamples and the size of the generalized linear regression matrix $X$ is\ntherefore roughly $2000\\times 2$ (in reality we have less samples because we\nalso sample at larger batch sizes). More generally we have a regression matrix\nof size $n \\times 2$. The generalized linear regression then calculates\n$$\n\t(X^T C^{-1} X)^{-1}X^T C^{-1}Y\n$$\nwhere $C$ is a diagonal matrix and $X^T C^{-1}X$ a $2\\times 2$ matrix. The cost\nis therefore of the order $O(n)$. The bootstrapping procedure typically finished\nin 10-20 iterations. So overall we have perhaps 20 times a problem of\ncomputational complexity $O(n)$ where $n$ (in our case less than $2000$) is\ngenerally vastly smaller than the parameter dimension (in our case $\\sim 2$\nmillion). Evaluating a single gradient is probably more expensive.\n\nOverall we highly doubt this will ever have significant computational overhead. In fact we would\nactually expect the number of samples $n$ needed to remain relatively constant\nindependent of the parameter dimension (because we are simply estimating a\ncovariance with random variables here). So if we had to guess, we would guess\nthat the bootstrapping cost is less and less relevant the larger the model.\n\nThank you again for your constructive criticism!", "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": "", "extra_scores": {}}, {"review_id": "oX7e8t4Ify", "reviewer": "Reviewer_1by3", "summary": "Many machine learning model have parameters that are optimized by some form of gradient descent. Given a parameters $\\omega$ in a space $\\Omega$ and a loss function $\\textbf{J}: \\Omega \\to \\mathbb{R}$, typical gradient descent proceeds by picking a starting point $\\omega_0$ and iteratively taking steps in the direction of steepest descent\n\n$$\n\\omega_{n+1} = \\omega_n - h \\nabla J(\\omega_n) = \\omega_n - \\eta \\frac{\\nabla J(\\omega_n)}{||\\nabla J(\\omega_n)||}\n$$\nwhere $h$ is the learning rate, or similarly $\\eta = $ is the step size. The learning rate/step size is an exogenous pre-determined user hyper parameter.\n\nThis paper proposes a method to automatically determine the steps size parameter. (I may have misunderstood and I welcome any correction by the authors) this method, called Random Function Descent (RFD), take a point $\\omega$, computes the function value and gradient $J(\\omega)$, $\\nabla J(\\omega)$, which is then used to fit a Gaussian process model. The GP model has a constant prior mean mean and a stationary, isotropic kernel, and by fitting one data point and it's gradient vector, the constant prior mean is updated to a still mostly constant surface however with a single local deformation at $\\omega$ resulting in a peak in the uphill direction from $\\omega$ and a trough on the direct opposite downhill side, . the RFD method jumps straight to the bottom of the trough, mathematically\n$$\n\\omega_{n+1} = \\text{arg min}_{\\omega'} \\mathbb{E}[J(\\omega') | J(\\omega), \\nabla J(\\omega') ]\n$$\nwhere the expectation is the posterior mean of the GP having been fit to the one data point. As the GP kernel is isotropic, there is no prior bias in any direction and the direction of the trough is exactly the direction of the gradient, consistent with normal gradient descent.\n\nThe paper considers many of the technical and theoretical hurdles and provides solutions in each case. Finally experiments with MNIST are provided. \n\nI somewhat struggled with the paper and have set my confidence score to low accordingly.", "questions": "- is it possible to extend to use individual rescaling for each parameter whilst keeping the isometric assumption? Sacrificing the isotropy assumption would require fitting a GP model to 1 + d values which has O(d**3) complexity hence would be impossible for network models. Preserving isotropy avoids this issue.", "limitations": "- the assumption of isometric in parameter space", "rating": 6, "confidence": 2, "soundness": 3, "presentation": 2, "contribution": 2, "strengths": "- tuning the baselines in the numerical experiments", "weaknesses": "Unfortunately for me, I struggled to understand much of the paper, I believe this could be partially be due to writing style, I have tried to keep my technical and writing comments separate\n\nI apologize if my understanding is incorrect, and look forward to the authors response to correct any such errors.\n\n- all the parameter updates are using euclidean distance in parameter space. In contrast, Natural gradient descent makes parameter updates that have equal distance in output distribution space. In practice, I believe an approximation is implemented by using inverse squared gradients for each parameter similar to ADAM/RMSprop that use root mean squared gradients. Obviously, \n\n- the numerical experiments seem a little lacking, RFD doesn't appear to show a significant improvement on Figures 3, 6, 7. MNIST and FashinMNIST are very small and perhaps too easy, any optimizer will \"max out\" any model pretty quickly I assume.\n\n\nThe below points are my personal subjective comments on the writing.\n- I am a little reluctant to agree that this paper has much to do with Bayesian optimisation as suggested by the abstract and introduction. RFD fits a GP model to a single data point and  only uses the posterior mean, it is the same as kernel ridge regression.\n- I felt the terminology of \"stochastic Taylor Expansion\" was rather unhelpful and somewhat counterproductive. In my mind, zeroth/first/second order Taylor expansion refer to constant/linear/quadratic local polynomial approximations to a function, however the given function approximations are non-linear (lemma 4.12) this description unfortunately rather mis-directed my thoughts.\n- L69: as above, \"it naturally incorporates covariance based trust\" assumes a lot of context that has not been introduced in the paper at this point, upon first reading I was rather lost, upon second reading it makes sense but felt out of place.\n- (there are many topics and details covered the main paper, would it be possible to focus on a few big ideas?)\n- Table 1, Figure 2, what is the scale \"s\", I assume the length scale in the covariance $C()$ function?  This appears not to be introduced in the paper.\n- L62, should the final term of the equation be $\\frac{L}{2}||\\omega - \\Theta||^2$?", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for taking your the time to review our paper. We understand that it is\na difficult paper to read due to its unconventional approach which takes some\ntime to get used to. We took your thoughts into account and will improve the paper (see general rebuttal), the paper is essentially a theory paper that should also be accessible/convince practitioners.\n\n## Question (Isotropy and rescaling individual parameters)\n\nThe anisotropy you have in mind is probably a \"geometric anisotropy\" which we\ncover in its entirety in Appendix E.1.\nThis geometric anisotropy still assumes that the covariance is of the form\n$$\n\tCov(\\mathbf{J}(w_1), \\mathbf{J}(w_2))\n\t= C\\Bigl(\\frac{\\langle w_1 - w_2, \\Sigma (w_1-w_2)\\rangle}2\\Bigr)\n\t= C\\Bigl(\\frac{\\\\|w_1 - w_2\\\\|_\\Sigma^2}2\\Bigr)\n$$\nand results in an update proportional to $\\Sigma^{-1}\\nabla\\mathbf{J}(w)$.\nIf you want to rescale individual parameters only, then you implicitly assume\nthe geometric anisotropy $\\Sigma$ to be diagonal. The $O(d^3)$ cost on\nthe other hand comes from the inversion of a dense matrix $\\Sigma$.\n\nBut note that the covariance is still stationary, i.e. of the form $f(w_1 -\nw_2)$ for some $f$. We believe that the necessary generalization beyond isotropy\nneeds to remove this stationarity because it is already violated for a\nsimple linear model (cf. appendix F.1). We suggest a generalization to linear\nisotropy (cf. appendix F) instead. So when we speak of removing the isotropy\nassumption in the conclusion we are generally talking about generalizations in\nthis direction beyond geometric anisotropies.\n\n## Addressing points in weaknesses\n\n### Euclidean distance and natural gradient descent\n\nThe isotropy assumption on the covariance implies\n$$\nCov(\\mathbf{J}(w_1), \\mathbf{J}(w_2))\n=C\\Bigl(\\frac{\\\\|w_1-w_2\\\\|^2}2\\Bigr)\n$$\nfor some covariance kernel $C$, where we took the norm to be the euclidean norm.\nHow RFD would look like if this norm is replaced by a distributional distance is\nup to future research. Perhaps the RFD updates would then look like Natural\ngradient descent with a specific step size.  But we did not investigate this\navenue so far. We are also unfamiliar with the relation of natural gradient\ndescent with Adam/RMSProp.\n\n### Numerical experiments\n\nThe aim of the project was never to outperform existing *tuned* optimizers. Given\nthat RFD is simply a form of gradient descent this would have been a tall order.\nThe aim was to understand the link between optimization theory and optimization\npractice in ML and (ideally) to perform the *tuning* statistically (i.e.\nremoving the need for expensive step size tuning). But we did not only find a\ntuned step size, we found an entire step size schedule! And SGD with a tuned\nstep size schedule can be more performant than SGD with a constant step size,\nthis is why RFD slightly outperforms SGD in the MNIST case study, but we would\nnever expect it to outperform SGD by much given that it is still gradient\ndescent after all.\n\nIf you compared RFD to the *untuned* optimizer the advantage is much more visible\nand in the end the performance advantage of RFD lies in the fact that tuning\nis much less expensive.\n\n### RFD relation to Bayesian optimization \n\nGiven that\n$$\n\\alpha(\\theta)\n= \\mathbb{E}[\\mathbf{J}(\\theta) \\mid \\mathbf{J}(w_n), \\nabla\\mathbf{J}(w_n)]\n$$\nconstitutes an acquisition function i.e. $w_{n+1} =\n\\arg\\min_{\\theta}\\alpha(\\theta)$ of which there are many in Bayesian\noptimization (e.g. expected improvement, probability of improvement, etc.) we\nbelieve that RFD could reasonably be interpreted as BO with a specific\nacquisition function. If you define BO more generally as the reserach\nfield interested in the \"optimization of random functions\" then our approach\nis part of this field anyway.\n\n### Terminology \"stochastic Taylor Expansion\"\n\nWe are sorry this terminology caused confusion. We intended to capture our\noriginal intuition with this terminology. The taylor approximation \"uses\" the\nderivatives in one point up to order $n$ to approximate\na function. Similarly the \"stochastic Taylor Approximation\" also *uses* the first $n$\nderivatives in a single point to define a function approximation. But the\nconditional expectation is the \"best\" approximation, so in this sense it is\nbetter than the Taylor approximation.\n\nWe will add a few lines to ward off against this confusion but believe that the\npaper would lose insight if we cut this description completely. It's valuable that you pointed us towards the need of more explanations.\n\n### \"naturally incorporates covariance based trust\"\n\nSince we introduced $L$-smoothness based trust in L66 and following, we hoped\nthat the mean-reversion in conjunction with Figure 1 would sufficiently explain\nour notion of \"covariance-based trust\". Which ideas following this note helped\nto make more sense of it during the second reading? We would be happy to\nmention them earlier.\n\n### Focus\n\nWe have addressed this point in the joint rebuttal. Thank you for pointing this out!\n\n### Table 1, Figure 2\n\nYes, \"s\" is the length scale. We link the equations defining the covariance\nmodels in the table heading. We unfortunately did not have enough space to\ndefine the covariance models in the main body. We will devote more space to\nthis in the final version.\n\n### L62 correction\n\nYes, this was indeed wrong, it should be $\\frac{L}2\\\\|w-\\theta\\\\|^2$. Thank you! This is now fixed.\n\nThank you for taking the time to read our answers, we hope\nthey were helpful.", "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": "", "extra_scores": {}}, {"review_id": "6FIbPu3JHy", "reviewer": "Reviewer_Y4cG", "summary": "The current paper studies random function descent, draws connection between RFD and SGD, and derives an adaptive step size scheduler. More specifically,  the authors study minimizing a stochastic first Taylor approximation of random functions, which has similar form of gradient descent when the random function is Gaussian process. This connection also hints a step size scheduler for standard GD method. The authors then explore this step size scheduling scheme and study its asymptotic performance, which helps explain some recent step size scheduling tricks such as gradient clipping and warmup. Finally, the authors propose a practical way to evaluate necessary statistics required for the newly found step size scheduler with current ML mini-batch loss. The authors show simulation results for MNIST data to exemplify the effectiveness of the drawn step size scheduler.", "questions": "1. Could the author please add a literature review section to discuss related works (and probably comparisons with current work)? \n\n2. The derived explicit RFD is for Gaussian random function, and I see that there is some relaxation in Section E.3. Could the authors please demonstrate more on to which extent this RFD method is close to real problem setting confronted in machine learning?\n\n3. I feel the part that discusses connection to Adam (Section E.1) can be partly moved to main text since Adam and its variant is pretty dominant in current ML (especially DL) training. Moreover, do the authors think RFD with component-wise estimated variance can match Adam performance with tuned learning rates in DL training?\n\n4. In line 300, it says \"on CIFAR-100, the step sizes given by RFD were too large\". I don't see these experiment results, could the authors please add this part of result for completeness (even if the result is not ideal).\n\n5. How do the authors expect the performance of proposed method compared with D-Adaptation, will they coincide in certain settings? It seems D-Adaptation is applicable for more general (larger model/more recent dataset) cases, and RDF is more limited since it involves more steps for variance estimation and its risk-affine property might be harmful.\n\n(potential) writing issues:\n\n1. In line 244, it seems \"Since all $Z_b$ have the same underlying of cost $J$\" should be \"Since all $Z_b$ have the same underlying cost $J$\"?\n\n2. In line 271, there seems missing a comma between loss $J$ and stochastic errors $\\epsilon_i$", "limitations": "Limitations have been discussed in Section 8.", "rating": 7, "confidence": 3, "soundness": 4, "presentation": 4, "contribution": 4, "strengths": "This paper is very well-written, theoretically sound, and the findings seem new and pretty insightful, thus I feel it makes good contribution to research on optimizer learning rate scheduling. \n\nThe main topic is about random function descent, and the minimization of stochastic first Taylor approximation of random function results in a gradient-type method (when Gaussian random function is considered) is surprising and impressive. \n\nThe writing is well-organized, with all terms being properly defined and all theorems (Theorem 2.3, 4.2, 5.2, 6.2) well-formulated and capture core ideas. Theorems that are more representative is presented in main text for better digestion with more complete/general versions listed in Appendix. Theorems and Definitions are followed by simple and efficient explanations (i.e., discussion after Definition 2.1, Definition 2.2, around Theorem 2.3, and many others). Plots and tables are provided and are clean and easy to interpret.\n\nThe math is clean, sound, and rigorous, with very complete proofs (i.e., D.1.1 and D.1.2). Extensions are well-explored (Section E) and more general cases are discussed (Section E.3 for example). From first derivation of step size (Theorem 4.2), to its asymptotic version A-RFD (Definition 5.2) and its stochastic version S-RFD (Theorem 6.2), all are interesting and important findings.\n\nPracticality of the proposed method has been considered. Though the proposed step size scheduler looks complicated, the authors figure out ways to evaluate necessary statistics required to put the step size scheduler into use (Section 6), and the effectiveness of proposed method applied to current ML tasks is also exemplified by examples (Section 7).\n\nThe research topic is valuable. Learning rate scheduling has been an open research area for a long time in optimization field. Currently in machine learning/deep learning research, a great deal of pressure comes from comparing with baseline methods which involves arduous hyperparameter tuning, among which learning rate is often the core. Thus studying learning rate scheduling is of great importance and this paper provides a novel connection between RFD and GD (with also extended comparison to Adam in Section E.1) which is very encouraging. Moreover, classical convergence result for optimization algorithms are mainly with worst case bound, RFD is instead for average case performance, the authors try hard and derive partial result for convergence (Corollary 5.3), and we expect there would be more study of difference between worst case performance and average case performance.", "weaknesses": "Though I appreciate the presentation quality, theoretical soundness, and novelty of the work. The main drawback of current paper boils down to three parts: lacking comparison with prior work, potential concerns with the practicality and effectivenss of the proposed method, and the (relatively) strict assumption of the theory.\n\n1. The current paper doesn't involve literature review section, though it draws connection to prior work dispersedly, no systematic review has been intended. I currently make my evaluation of the novelty of the work based on my own (might be poor) understanding. I feel adding a related work section is desirable and then a more fair evaluation of value of current work can be made.\n\n2. Still about prior work but for baseline method comparison. The simulation results (mainly Figure 3) only compares the proposed method with SGD/Adam with tuned fixed learning rates. More recent work such as D-Adaptation [1] also studies tuning-free learning rate scheduler for SGD/Adam, from not RFD perspective but more classical optimization angle, hasn't be mentioned/compared against. Moreover, the experiment in current paper seems much simpler and less thorough than the setting considered in D-Adaptation. \n\n3. With respect to practicality, though the authors provide empirical ways to evaluate covariance in mini-batch training, the recipe still looks a bit complex, i.e., one should go evaluate $C$ and $C'$ from the observation first. Unlike current adaptive gradient method such as Adam/AdamW, or even D-Adaptation, which only depends on some statistics involving current/past gradient/function values. Moreover, since RFD is measuring average case performance, it's more risk-affine and tends to predict larger learning rate, which may be harmful for convergence in some cases.\n\n4. Despite that I feel minimizing stochastic Taylor approximation of random function is interesting and worth exploring, the derived GD-type algorithm is for Gaussian random function (Theorem 4.2), though the authors mention this assumption was also used in [2], it might be desirable to more demonstrate to which extent one should expect this assumption to be close to real settings.\n\n\n[1] Learning-Rate-Free Learning by D-Adaptation (Aaron Defazio and Konstantin Mishchenko).\n\n[2] Yann N Dauphin et al. “Identifying and Attacking the Saddle Point Problem in High Dimensional Non-Convex Optimization”.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you so much for taking the time to review our paper so thoroughly, even\ntaking the time to read the appendix. We are glad you found it insightful.\n\n### Related work/Literature review\n\nIn previous drafts the paragraphs on related work in the introduction were more\nextensive but were cut because proofreaders argued that the relation was\nunclear and did not contribute to an understanding of the main work.\nA good compromise might be an extensive discussion at the beginning of the\nappendix that we are going to add. We personally feel that Bayesian Optimization is closely related, but\nas you can see in the review by 1by3 this is not uncontroversial\neither. So the reason that there is not an extensive discussion of related work\nis because our approach is fairly novel and unique.\n\nNevertheless, we would be happy to expand a little on the relation to Bayesian\noptimization. The method most similar to RFD is perhaps expected improvement:\n$$\n\tx_{n+1}\n\t= \\arg\\max_{x} \\mathbb{E}\\Bigl[\n\t\t\\max \\bigl\\\\{ 0, \\min_{i=0,\\dots,n}\\mathbf{J}(x_i)-\\mathbf{J}(x) \\bigr\\\\}\n\t\t\\mid\n\t\t\\mathbf{J}(x_0), \\dots,\\mathbf{J}(x_n)\n\t\\Bigr]\n$$\nIf the rectifier and running minimizer wouldn't be there, this would look similar to a non-greedy version of RFD (without gradients). There has also\nbeen a paper which utilizes gradients [33,53,42,37]. But none utilize the\nentire sparsity one gets by conditioning only on one point. Consequently, none\nof the previous work in BO was applied to truly high dimensional optimization\nand there has never been an analysis of the resulting step size before. Neither\nhas there been any consideration for estimating covariance models in high\ndimension. At least we are not aware of any prior work.\n\n### Gaussian assumption\n\nWhile we provided a relaxation in E.3 we believe that the Gaussian assumption is\nfairly accurate (cf. Figure 4) and does not necessarily need to be attacked (in\ncontrast to the isotropy assumption). But only time will tell and we wanted to\npoint out with E.3 that the Gaussian assumption could be circumvented if\nnecessary.\n\n###\t Connection to Adaptive step sizes (Adam) E.1\n\nAs noted in E.1, there is a small disconnect between the entry-wise scaling\nresulting from geometric anisotropies and the scaling suggested by Adam/RMSProp\n(which apply a square root). Further research is needed to find out where this\ndisconnect is coming from, so we held off from putting it into the main body.\nNevertheless we agree that it is a very interesting connection.\n\nWhen it comes to the competitiveness we believe that it is still necessary to\ndiscover the equivalence of momentum in the framework of optimization of random\nfunctions. That is still missing even with component-wise step sizes. \n\n### D-adaptation\n\nThe classical optimization angle has been to assume convexity (which is also the\nassumption D-adaptation makes prominently). With these classical origins the theory behind D-adaption seems to be relatively unrelated from the theory\nbehind RFD, so a direct comparison is difficult. We could draw empirical\ncomparisons, but the empirical part of this paper was only intended to be a\nproof of concept with an extensive empirical paper being currently in process. \nD-adaptation is also not as accessible as a pre-implemented pytorch optimizer\nand since it also only aims to match the performance of the tuned optimizers the\nbenefits of a comparison seem limited to us.\n\nWhile D-adaptation seems to be more advanced at the moment (with more extensive\nbenchmarks and more reliable performance) it is built with the untenable\nframework of convex optimization. It can only ever explain asymptotic\nperformance hoping that the optimizer eventually enters a locally convex area.\nConvex optimization theory will never be able to explain initial behavior where\nconvexity is simply not true, i.e. it will never be able to explain things\nlike warmup. This shows the strength of our approach for the long term. Our\napproach simply doesn't have the maturity of the conventional convexity\nassumption yet.\n\nNevertheless, it addresses the same issue and should therefore be discussed in\nthe Literature review. Thank you for pointing this out to us.\n\n### Practicality\n\nIn the future it might be possible to estimate covariances in an on-line\nfashion. Then it is not necessary to spend time to fit the covariance at the\nbeginning. But the time it takes to fit the covariance is already relatively\nsmall (i.e. only one epoch worth of samples).\n\n### Cifar-100 experiment\n\nThere is not too much to learn from the experiment on Cifar-100. The step-sizes\nare so large that no convergence happens at all which means that the problem\nis unlikely to be an instability of the RFD algorithm and more likely that the\ndistributional assumption is simply violated.\n\nThe reason is also apparently not necessarily the dataset itself but rather the\nresnet architecture - a different model exhibited good convergence in a later\nexperiment. We believe that it will be necessary to attack the distributional\nisotropy assumption in order to get reliable performance in applications. E.g.\nin Section F.1 we show how isotropy breaks down on linear models and point\ntowards the generalization of linear isotropy. We plan to fully investigate\nempirical performance in a future paper to get a better idea what\ngeneralizations are actually necessary. We will add a preview to the\nappendix.\n\n\n### Writing issues\n\nThank you for catching these! They are now fixed.", "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": "", "extra_scores": {}}, {"review_id": "VRMrMCjeg1", "reviewer": "Reviewer_BoUK", "summary": "The authors derive a novel gradient descent step schedule from a Bayesian point of view, establishing a connection between Bayesian optimization and classical optimization. The theory gives support to some commonly chosen step schedules and is validated on MNIST dataset.", "questions": "In the introduction, the authors mention that classic BO is limited to relatively small dimensions. Does RFD improve upon that?", "limitations": "Yes. Limitations are adequately addressed.", "rating": 5, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "1. The paper is well written, with clearly explained and carefully chosen notations. The figures are very pretty. It's a pleasure to read.\n2. The paper has a good motivation. Worse-case theory, in general, can mislead people. Average-case studies are desired. The disparity between Bayesian optimization and classical optimization is quite obvious, and one can imagine there can be many optimization algorithms with mixed characteristics of both genres. The direction the paper explored is promising.\n3. The research is very detailed and solid. The authors give sound proofs to their theorems and organise the results in a clear manner. The experiments are very extensive and well displayed.", "weaknesses": "1. The so-called \"average case study\" is not fully justified. The expectation of $J(w_n)$ is not in general equal to the expectation of $J(\\theta)$ with $\\theta$ fixed and then replaced by $w_n$. This is because $w_n$ is by itself a random variable. More concretely, suppose that $J$ is sampled randomly from $\\mathcal{N}(\\mu, C)$ with $\\mu$ being a constant, say $\\mu_0$. Then the expectation of $J(w_0)$ would be $\\mu_0$ but the expectation of $J(w_n)$ for $n$ large would be much smaller than $\\mu_0$. The method in this paper can only be thought of as average case study in the initial stage of optimization. The authors mention \"forgetful\" but I believe the problem is more serious than it looks. The authors also mention \"risk-affine\", but I don't necessarily agree with it. The claim \"Since RFD is defined as the minimizer of an average instead of an upper bound – making it more risk affine\" feels weak, because I don't think it's well justified yet that RFD is the minimizer of an average.\n2. Incomplete story and lack of depth. Overall, there are lots of results but none of them are highlighted enough to be a gem. On the theory side, it's not clear whether there is any nontrivial key technical contribution in the proofs. It's not obvious that the derivation of the step schedule from a Bayesian viewpoint involves more than straightforward calculation. It needs more to stand as a strong theoretical paper. Furthermore, it would be better if there was a clear table presenting a convergence rate comparison of this new method and classical ones. On the empirical side, only MNIST is not enough, although the authors did a lot of experiments on MNIST. So as a new methodology paper, we need stronger empirical evidence. It's understood that the authors are studying a very hard problem, but excuses cannot serve as strengths of the paper.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your review, we are happy you found the paper a pleasure to read!\n\n### Question (Complexity of RFD)\n\n> The authors mention that classic BO is limited to relatively small dimensions.\nDoes RFD improve upon that?\n\nWhile classical Bayesian optimization has computational complexity $O(n^3 d^3)$\nwhere $n$ is the number of steps and $d$ the number of dimensions, RFD under the\nisotropy assumption has the same computational complexity as gradient descent\n(i.e. $O(nd)$) as per Theorem 4.2. So yes, it does.\n\n### 1. Random input to J\n\nWe are aware of this and footnote 2 placed at Definition 2.2 of RFD points\nto a discussion of this problem in appendix D.1.1. We have purposefully\nrelegated this discussion to the appendix because it appears to be confusing to\nnon-probabilists and this lie-to-children retains the intuition of this\napproach. We agree that we only formalized the minimization of the average in\nthe inital step but would argue that this is still heuristically true later on.\n\nHere is a sketch for why this is true:\n\nWe have formally proven the following statement for a different paper:\nFor any $n$ let $W_n$ be measurable with regard to\n$\\mathbf{f}(W_{0:n})=(\\mathbf{f}(W_0),\\dots, \\mathbf{f}(W_{n-1}))$\n(where $\\mathbf{f} = (\\mathbf{J},\\nabla\\mathbf{J})$ in our case),\nthen we can treat random inputs as deterministic in the following sense\n$$\n\t\\mathbb{E}[\\mathbf{f}(W_n)\\mid \\mathbf{f}(W_{0:n})]\n\t= \\Bigl(\n\t\t(w_{0:{n+1}})\n\t\t\\mapsto \\mathbb{E}[\\mathbf{f}(w_n) \\mid \\mathbf{f}(w_{0:n})]\n\t\\Bigr)(W_{0:n})\n$$\nwhere $w_{0:n} = (w_0,\\dots, w_{n-1})$. The takeaway from this is, that\nif our method was not forgetful it would be valid to treat the inputs\nas deterministic.\n\nNow how do we treat forgetful methods? To build some intuition for this,\nconsider $W_0$ to be a random variable independent of $\\mathbf{J}$ (note that\nthis is not allowed in the statement above because\n$W_0$ has to be measurable w.r.t $\\mathbf{f}(W_{0:n}) = \\emptyset$). The\ninformation $(\\mathbf{J}(W_0), \\nabla\\mathbf{J}(W_0))$ is then almost useless to\nus for forming a conditional expectation about $\\mathbf{J}(w)$ because we do\nnot know where $W_0$ is (at least if the distribution of $W_0$ is sufficiently\nspread out). To avoid a similar effect for RFD with proper consideration of\nrandom variables, we would have to add at least $W_n$ to the condition of RFD\n(we do not want to add the other $W_k$ because then we would essentially give\naway all the previous gradients assuming a deterministic optimizer).\nI.e. RFD would look like this\n$$\n\tW_{n+1} = \\arg\\min_w \\mathbb{E}[\n\t\t\\mathbf{J}(w)\\mid \\mathbf{J}(W_n), \\nabla\\mathbf{J}(W_n), W_n\n\t].\n$$\nBut if we condition on $W_n$ and $W_0$ is deterministic, then the\nconditional expectation will extract older gradient information from the current\nposition $W_n$ and therefore we do not have a truly forgetful method. The only\nway to prohibit this attempt of the conditional expectation is to let $W_0$\nbe completely spread out (i.e. uniform on $\\mathbb{R}^d$ which is not quite well\ndefined). But since the first optimization step only selects $W_1 - W_0$ as a\nfunction of $\\mathbf{J}(W_0), \\nabla\\mathbf{J}(W_0)$ and its distribution is\nindependent of $W_0$ due to the stationarity of $\\mathbf{J}$, $W_1$ is still\ndistributed uniformly on $\\mathbb{R}^d$ in the sense that the transition kernel\nfrom $W_0$ to $W_1$ we defined above has the lebesgue measure as an invariant\ndistribution. I.e. the distribution of $W_1$ would be independent of\n$\\mathbf{J}$.\n\nSo the only way we can prevent $W_n$ from being a proxy for the\nprevious gradients results in $W_n$ being independent of $\\mathbf{J}$\nAnd this means that our heuristic definition of RFD in appendix D.1.1 captures\nthe forgetfulness we intend much better than any other way we can think of to\nformulate it. It does capture the fact that the expectation of $\\mathbf{J}(W_n)$\nis lower than the expectation of $\\mathbf{J}(W_0)$ because it conditions on\n$\\mathbf{J}(W_{n-1})$ which is already lower.\n\nWe also want to note that we respect the formal definition of D.1.1 in the\nproofs of all our results.\n\n### 2. Story\n\nContaining numerous results can hardly be seen as a weakness. To make the story punchier we will use the keywords “viability” and “advantages” in the following to better group our results. Please also have a look at the general rebuttal.\n \nTo show the viability\n- We prove that RFD reduces to gradient descent with very specific step sizes in Theorem 4.2 (This establishes computability and a scalable complexity - cf. Complexity of RFD). Boilt down, this Theorem requires two deep insights, 1. extreme sparsity of the covariance matrix of a single gradient, 2. splitting the optimization over direction and step size). Extensions which generalize this result (appendix E, Theorem 6.2) could have been turned into one large theorem, but this would distract from the main ideas.\n- We introduce a completely novel way of estimating the covariance in high dimension necessary to compute RFD step sizes.\n\nTo show the advantages of this approach\n- we establish scale invariance (Theorem 2.3), respecting the random input (!)\n- we show how the step size schedule of RFD explains existing step size heuristics like warmup at the beginning, which is something a convexity framework could never deliver because the convexity assumption is false at the beginning and only true asymptotically. Without our insight of Theorem 4.2 that step sizes can be analytically obtained, this step size analysis could not have taken place and the analysis also contains novel insights on how to understand the results of Theorem 4.2 asymptotically.\n \nWe believe that NeurIPS papers should contribute novel background understanding with practical benefits. That’s why we included a standard non-trivial empirical example. We are currently going through an extensive independent empirical study that we believe would have blown the scope of an already very dense paper which pushes many results to the appendix.", "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": "", "extra_scores": {}}]

Author rebuttal:
We warmly thank all our reviewers for their interest, time, insight and constructive criticism.

Writing the paper was a challenge as it requires familiarity with different
mathematical concepts but should be accessible for practitioners at the same
time. Our approach was to simplify the main text as much as possible and provide generalizations in the appendix. And since it is impossible to fit all
backgrounds equally we see different opinions about the writing style in the
reviews. We believe this is normal for a paper of this kind. Introducing new
theory is often harder than presenting improvements to a classical technique,
especially if it should be accessible to empirical researchers as well.

Taking into account your feedback we decided to better present the focus of the
paper. In the present version the main message seems to get a bit lost in the
details. We cannot move even more concepts into the appendix, but we can better focus
the reader’s attention. With very little change to the
paper this can be done by slightly changing abstract, outline, and conclusion and titles of theorems.

## A list of minor changes to improve the story line in the final version

Motivated by reviewers XTWd's suggestion to summarize the overall vision in a
short paragraph, we will add the following paragraph to the outline (L45):

> The main goal of this paper is to demonstrate the **viability** and
**advantages** of replacing the classical "convex function" framework
with a "random function" framework. Theorem 4.2 is the main theoretical result
establishing **viability** (computatability and scalable complexity) for a given covariance model. Section 6
is concerned with practical estimation of the covariance model and viability is
demonstrated with a practical example in the MNIST case study (Section 7).
The **advantages** of this approach are scale invariance (Advantage 2.3) and an explicit step size schedule, which does not require expensive tuning, and explains existing ML heuristics such as warmup (cf. Section 5.2). This explanation of the initial stage of
optimization could never be delivered by the convex framework, because the
convexity assumption is not fulfilled initially so it can at best explain
asymptotic behavior.

To sharpen the focus throughout the text we plan to rename
- "Theorem 2.3 (Scale invariance)" into "Advantage 2.3 (Scale invariance)"
- "Theorem 5.2" into "Proposition 5.2"
- "Theorem 6.2" into "Extension 6.2" grouping it together with the extensions
of appendix E which are all modifications of Theorem 4.2

Theorem 4.2 is then left as the only remaining Theorem in the main body which
should focus the readers attention onto it as the key result enabling this
approach. To better explain its significance we will add the following remark
explaining its scalable complexity

> ### Remark (Scalable Complexity)
> While Bayesian optimization with gradients typically has computational complexity $O(n^3
d^3)$, where $n$ is the number of steps and $d$ the number of dimensions, RFD
under the isotropy assumption therefore has the same computational complexity as
gradient descent (i.e. $O(nd)$).

We will cut L308-312 from section 8, to focus it on the limitations and work
these extensions into an outlook contained in the conclusion, which will be rewritten to be

> ### Conclusion
> In this paper we have demonstrated the **viability** (computability and scalable complexity) and **advantages** (scale
invariance, explainable step size schedule which does not require expensive tuning) of replacing the classical "convex
function" framework with the "random function" framework.  Along the way we
bridged the gap between Bayesian optimization (not scalable so far) and classical optimization
methods (scalable). This theoretical framework not only sheds light on existing step size heuristics, but can also
be used to develop future heuristics.
>
> We envision the following improvements to RFD in the future: 
> 
> 1. The *reliability* of RFD can be improved by generalizing
the distributional assumptions to cover more real world scenarios. In particular
we are interested in the generalization to linear isotropy because
we suspect that regularization such as weight and batch normalization [43, 23]
are used to patch violations of isotropy (cf. Section F).
> 2. The *performance* of RFD can also be improved. Since RFD
is forgetful while momentum methods retains some information it is likely
fruitful to relax the full
forgetfulness. Furthermore, we suspect that adaptive learning rates [e.g. 12,
27], such as those used by Adam, can be incorporated with geometric anisotropies
(cf.  Sec. E.1). Performance could also be further improved by estimating
the covariance (locally) online instead of globally at the start. Finally, the
implementation itself can be made more performant.

Finally, we change the abstract into
> ### Abstract
> Classical worst-case optimization theory neither explains the success of
optimization in machine learning, nor does it help with step size selection.
In this paper we demonstrate the viability and advantages of replacing the
classical "convex function" framework with a "random function" framework.
With complexity $O(n^3d^3)$, where $n$ is the number of steps and $d$ the number of dimensions, Bayesian optimization with gradients
has not been viable in large dimension so far. By bridging the gap between
Bayesian optimization (i.e. random function optimization theory) and classical optimization using a
‘stochastic Taylor approximation’ to rediscover gradient descent (with $O(nd)$ complexity) we establish viability. This
rediscovery yields a step size schedule we call Random Function Descent (RFD).
The advantage of this random function framework is that RFD is scale invariant and that it provides a theoretical foundation for common step size
heuristics such as gradient clipping and gradual learning rate warmup.

We hope these modifications further improve the accessibility of our
paper.

Meta-review: This paper gives a new perspective on stochastic optimization algorithms by beginning with a new starting point: That of Taylor approximations on random functions. The key observation is that when the random functions are in the space of Gaussian processes, an algorithm similar to SGD/Adam/etc. drops out (although with a different step-size, set based on the local curvature. Reviewers seem to have consensus that the ideas as correct and novel and insightful, though there are lingering concerns about the implications of "forgetting" in each iteration and the fairly modest (MNIST) experimental results.

I agree that the new proposed method isn't really proven to be "better" than existing methods. However, given how central stochastic optimization is to the field, I think this paper is valuable simply for the "insight" it provides.

A minor comment (from me) on notation when reading the paper: I found the notational in section 2 to be rather unexplained. It's not too difficult for me to guess what the notation T[J(θ) | J(w), ∇J(w)] notation means, but I think this is not so well-established that a definition is not appropriate. I stumbled more on the random function notation E[**J**(θ) } | **J(w)**, ∇**J**(w)], which is referred to as a Taylor expansion, but a T is not provided. In both cases, a more clear definition (and in the latter case more discussion of the underlying probabilistic model). Again, I *think* I figured this all out, but there's no reasons to leave lingering doubts.
Decision: Accept (poster)