Random Function Descent

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.

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. 2. 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. 3. 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. 2. 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.

Questions

In the introduction, the authors mention that classic BO is limited to relatively small dimensions. Does RFD improve upon that?

Rating

5

Confidence

3

Soundness

3

Presentation

3

Contribution

2

Limitations

Yes. Limitations are adequately addressed.

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.

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. The 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. The 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. The 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. Practicality 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). The 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. 1. 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. 2. 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. 3. 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. 4. 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. [1] Learning-Rate-Free Learning by D-Adaptation (Aaron Defazio and Konstantin Mishchenko). [2] Yann N Dauphin et al. “Identifying and Attacking the Saddle Point Problem in High Dimensional Non-Convex Optimization”.

Questions

1. Could the author please add a literature review section to discuss related works (and probably comparisons with current work)? 2. 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? 3. 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? 4. 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). 5. 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. (potential) writing issues: 1. 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$"? 2. In line 271, there seems missing a comma between loss $J$ and stochastic errors $\epsilon_i$

Rating

7

Confidence

3

Soundness

4

Presentation

4

Contribution

4

Limitations

Limitations have been discussed in Section 8.

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 $$ \omega_{n+1} = \omega_n - h \nabla J(\omega_n) = \omega_n - \eta \frac{\nabla J(\omega_n)}{||\nabla J(\omega_n)||} $$ where $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. This 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 $$ \omega_{n+1} = \text{arg min}_{\omega'} \mathbb{E}[J(\omega') | J(\omega), \nabla J(\omega') ] $$ where 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. The paper considers many of the technical and theoretical hurdles and provides solutions in each case. Finally experiments with MNIST are provided. I somewhat struggled with the paper and have set my confidence score to low accordingly.

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 I apologize if my understanding is incorrect, and look forward to the authors response to correct any such errors. - 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, - 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. The below points are my personal subjective comments on the writing. - 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. - 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. - 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. - (there are many topics and details covered the main paper, would it be possible to focus on a few big ideas?) - 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. - L62, should the final term of the equation be $\frac{L}{2}||\omega - \Theta||^2$?

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.

Rating

6

Confidence

2

Soundness

3

Presentation

2

Contribution

2

Limitations

- the assumption of isometric in parameter space

Summary

### Summary The 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. In 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. The 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. The 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.

Strengths

### Strengths 1. **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. 2. **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. 3. **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. 4. **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. 5. **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 1. **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. 2. **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. 3. **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. 4. **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. 5. **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.

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.

Rating

5

Confidence

4

Soundness

4

Presentation

3

Contribution

2

Limitations

n/a

Well written rebuttal

Thanks the authors for their courteous detailed and informative rebuttal. I see that forgetful is somewhat necessary. Still, I'm 100% convinced forgetful is fully able to captured the complicated reality of optimization. But optimization is itself a very harsh subject to study theoretical. I'm fully aware not all of us have the capabilities to do extensive empirical studies, but ideally speaking, a paper on novel methodologies is best supported by extensive empirical results so that we can have an objective view on the true potential of the new methodology. My experience in machine learning tells me that theories haven't been very good in predicting new architecture, new methodologies because the full complexity of the reality is just hard to capture in a finite set of mathematical assumptions. Therefore, I shall stick to my previous judgement.