Explicit and Implicit Graduated Optimization in Deep Neural Networks

Naoki Sato, Hideaki Iiduka · 2024

Read Explicit and Implicit Graduated Optimization in Deep Neural Networks by Naoki Sato, Hideaki Iiduka (2024) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2412-11501.txt.

Introduction

Naoki Sato and Hideaki Iiduka wrote this paper in two thousand twenty-four. It tests graduated optimization for deep neural networks, a trick that smooths a bumpy loss with noise and then eases the noise away to find a broad low point.

The team grades the explicit form, with a best noise plan from past work, on classic test curves and on real network losses, and notes where it stalls. They then stretch the implicit form, which rides on the noise that stochastic gradient descent makes on its own, to the momentum variant. A convergence study and image tests on ResNet builds show the stretch works.

Catalog record

CREATORNaoki Sato, Hideaki Iiduka
YEAR2024
COLLECTIONPAPERS
FORMATTXT
FILE SIZE73 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2412-11501

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Explicit and Implicit Graduated Optimization in Deep Neural Networks Naoki Sato, Hideaki Iiduka Abstract Graduated optimization is a global optimization technique that is used to minimize a multimodal nonconvex function by smoothing the objective function with noise and gradually refining the solution. This paper experimentally evaluates the performance of the explicit graduated optimization algorithm with an optimal noise scheduling derived from a previous study and discusses its limitations. It uses traditional benchmark functions and empirical loss functions for modern neural network architectures for evaluating. In addition, this paper extends the implicit graduated optimization algorithm, which is based on the fact that stochastic noise in the optimization process of SGD implicitly smooths the objective function, to SGD with momentum, analyzes its convergence, and demonstrates its effectiveness through experiments on image classification tasks with ResNet architectures. Code — https://github.com/iiduka-researches/igo-aaai25 Introduction Nonconvex optimization problems are ubiquitous in the machine-learning and artificial-intelligence fields, and those arising in training deep neural networks (DNN) ( Bengio 2009 ) are particularly interesting from multiple aspects. In particular, because the nonconvex functions that appear in DNN training have many local optimal solutions, stochastic gradient descent (SGD) ( Robbins and Monro 1951 ) and its variants, which use gradients to update the sequence, may fall into local optimal solutions and may not minimize losses sufficiently. Graduated optimization ( Blake and Zisserman 1987 ) is a global optimization method that can be applied to multimodal functions in order to avoid local optimal solutions and converge to the global optimal one. The method first prepares M monotone decreasing noises (\delta_{m})_{m\in[M]} . Then, by smoothing the original objective function f with that noise, a sequence of M smoothed functions (\hat{f}_{\delta_{m}})_{m\in[M]} is obtained that gradually approaches the original objective function. The function \hat{f}_{\delta_{1}} smoothed with the largest noise \delta_{1} is then optimized, and the approximate solution is then used as the initial point for optimization of the function \hat{f}_{\delta_{2}} smoothed with the second largest noise \delta_{2} . After that, the function \hat{f}_{\delta_{3}} smoothed with the third largest noise \delta_{3} is optimized with the second approximate solution as the initial point, and the procedure is repeated in order to search for the global optimal solution without falling into a local optimal one. See Figure 1 for a conceptual diagram of this process. Graduated optimization is often used in machine learning and computer vision for, e.g., semi-supervised learning ( Chapelle, Chi, and Zien 2006 ; Sindhwani, Keerthi, and Chapelle 2006 ; Chapelle, Sindhwani, and Keerthi 2008 ) and robust estimation ( Yang et al. 2020 ; Antonante et al. 2022 ; Peng, Kümmerle, and Vidal 2023 ) . In addition, score-based generative models ( Song and Ermon 2019 ; Song and Ermon 2020 ) and diffusion models ( Sohl-Dickstein et al. 2015 ; Ho, Jain, and Abbeel 2020 ; Song et al. 2021 ; Rombach et al. 2022 ) , which are state-of-the-art models of image generation, use this approach. Theoretical analysis of graduated optimization began with the pioneering work by ( Duchi, Bartlett, and Wainwright 2012 ) on nonsmooth convex functions, and several papers ( Mobahi and Fisher III 2015 ; Hazan, Yehuda, and Shalev-Shwartz 2016 ; Iwakiri et al. 2022 ; Li, Wu, and Zhang 2023 ; Sato and Iiduka 2023 ) have produced important results. In particular, ( Hazan, Yehuda, and Shalev-Shwartz 2016 ) defined a family of nonconvex functions that satisfy the conditions for convergence of a graduated optimization algorithm, called \sigma -nice, and proposed a first-order algorithm based on graduated optimization. They also studied the convergence and convergence rate of the algorithm to a global optimal solution for \sigma -nice functions. In addition, ( Sato and Iiduka 2023 ) showed that the stochastic noise in the optimization process that SGD naturally has can implicitly smooth the objective function, and they proposed an implicit graduated optimization algorithm that exploits this property. Furthermore, they defined a new \sigma -nice function, which is an extension of the \sigma -nice function, and provided a convergence analysis of the implicit graduated optimization algorithm for this function. Here, this paper refers to graduated optimization with explicit smoothing operations (see Definition 1 ) as “explicit graduated optimization” and to graduated optimization with implicit smoothing operations as “implicit graduated optimization”. Figure 1: Conceptual diagram of new \sigma -nice function and its smoothed versions and implicit graduated optimization. Note that this is a direct quotation from the prior work ( Sato and Iiduka 2023 ) with minor changes made to fit our results. This paper analyzes the new \sigma -nice function and discusses the implicit graduated optimization algorithm, which has so far been studied in relation to stochastic noise in SGD, in relation to stochastic noise in SGD with momentum. It also complements the prior studies with important theoretical and experimental validations on explicit and implicit graduated optimization. Contributions 1. An example of a new \sigma -nice function. ( Sato and Iiduka 2023 ) proposed new \sigma -nice functions, i.e., a family of nonconvex functions that satisfy the necessary conditions for analysis and convergence of graduated optimization algorithms, but did not provide an example. Here, we theoretically prove that Rastrigin’s function ( Törn and Zilinskas 1989 ; Rudolph 1990 ) , one of the traditional benchmark functions for global optimization, is a new \sigma -nice function (Theorem 1 ). 2. Experimental validation in explicit graduated optimization. ( Sato and Iiduka 2023 ) theoretically derived the optimal decay rate of the noise in both explicit and implicit graduated optimization, but did not provide numerical experiments to determine whether it is valid for explicit graduated optimization (Algorithm 1 ). Here, we applied the explicit graduated optimization algorithm and general global optimization methods to traditional benchmark functions for global optimization and found that the explicit graduated optimization algorithm with the optimal noise schedule outperforms the other methods on some problems (Table 1 ). We also applied the explicit graduated optimization algorithm to DNNs and found that its performance is not superior to other methods (Figure 3 ). 3. Experimental validation in implicit graduated optimization with SGD. ( Sato and Iiduka 2023 ) proposed an implicit graduated optimization algorithm using stochastic noise in SGD (Algorithm 3 ), but did not provide numerical experimental results with the noise decay rate set as per theory. In this paper, we provide numerical experimental results that are consistent with theory as far as computational complexity permits, confirming that their algorithm works effectively (Figure 4 ). 4. Theoretical development of implicit graduated optimization algorithm with SGD with momentum. On the basis that the stochastic noise of SGD is determined by the ratio of learning rate and batch size and that this noise helps to the smooth the objective function, ( Sato and Iiduka 2023 ) proposed an algorithm that achieves implicit graduated optimization by varying those parameters during training so that the noise decreases gradually. In this paper, we extend this argument to SGD with momentum, and on the basis that the stochastic noise of SGD with momentum is determined by the learning rate, batch size, and momentum factor ( Sato and Iiduka 2024 ) , we constructed an algorithm (Algorithm 6 ) to perform implicit graduated optimization in the same way (see Figure 1 ). We also

Read the complete text