This paper proposes a new approach for step size adaptation in gradient methods. The proposed method called step size optimization (SSO) formulates the step size adaptation as an optimization problem which minimizes the loss function with respect to the step size for the given model parameters and gradients. Then, the step size is optimized based on alternating direction method of multipliers (ADMM). SSO does not require the second-order information or any probabilistic models for adapting the step size, so it is efficient and easy to implement. Furthermore, we also introduce stochastic SSO for stochastic learning environments. In the experiments, we integrated SSO to vanilla SGD and Adam, and they outperformed state-of-the-art adaptive gradient methods including RMSProp, Adam, L4-Adam, and AdaBound on extensive benchmark datasets. First-order gradient methods (simply gradient methods) have been widely used to fit model parameters in machine learning and data mining, such as training deep neural networks. In the gradient methods, step size (or learning rate) is one of the most important hyperparameters that determines the overall optimization performance. For this reason, step size adaptation has been extensively studied from various perspectives such as second-order information (Byrd et al., 2016; Schaul et al., 2013) , Bayesian approach (Mahsereci & Henning, 2015) , learning to learn paradigm (Andrychowicz et al., 2016) , and reinforcement learning (Li & Malik, 2017) . However, they are hardly used in practice due to lack of solid empirical evidence for the step size adaptation performance, hard implementation, or huge computation. For these reasons, some heuristically-motivated methods such as AdaGrad (Duchi et al., 2011) , RMSProp (Tieleman & Hinton, 2012) , and Adam (Kingma & Ba, 2015) are mainly used in practice to solve the large-scale optimization problems such as training deep neural networks. Recently, two impressive methods, called L 4 (Rolinek & Martius, 2018) and AdaBdound (Luo et al., 2019) , were proposed to efficiently adapt the step size in training of models, and showed some improvement over existing methods without huge computation. However, performance comparisons to them were conducted only on relatively simple datasets such as MNIST and CIFAR-10, even though L 4 has several newly-introduced hyperparameters, and AdaBound needs manually-desgined bound functions. Moreover, L 4 still requires about 30% more execution time, and AdaBound lacks the time complexity analysis or empirical results on training performance against actual execution time. This paper proposes a new optimization-based approach for the step size adaptation, called step size optimization (SSO). In SSO, the step size adaptation is formulated as a sub-optimization problem of the gradient methods. Specifically, the step size is adapted to minimize a linearized loss function for the current model parameter values and gradient. The motivation of SSO and the justification for the performance improvement by SSO is clear because it directly optimizes the step size to minimize the loss function. We also present a simple and efficient algorithm to solve this step size optimization problem based on the alternating direction method of multipliers (ADMM) (Gabay & Mercier, 1976) . Furthermore, we provide a practical implementation of SSO on the loss function with L 2 regularization (Krogh & Hertz, 1992) and stochastic SSO for the stochastic learning environments. SSO does not require the second-order information (Byrd et al., 2016; Schaul et al., 2013) and any probabilistic models (Mahsereci & Henning, 2015) to adapt the step size, so it is efficient and easy to implement. We analytically and empirically show that the additional time complexity of SSO in the gradient methods is negligible in the training of the model. To validate the practical usefulness of SSO, we made two gradient methods, SSO-SGD and SSO-Adam, by integrating SSO to vanilla SGD and Adam. In the experiments, we compared the training performance of SSO-SGD and SSOAdam with two state-of-the-art step size adaptation methods (L 4 and AdaBdound) as well as the most commonly used gradient methods (RMSProp and Adam) on extensive benchmark datasets.
We propose an efficient and effective step size adaptation method for the gradient methods. A new step size adaptation in first-order gradient methods that establishes a new optimization problem with the first-order expansion of the loss function and regularization, where step size is treated as variable.