Year: 2018

Abstract:
We present a novel approach for adaptively selecting the learning rate in gradient descent methods. Specifically, we impose a regularization term on the learning rate via a generalized distance, and cast the joint updating process of the parameter and the learning rate into a maxmin problem. Some existing schemes such as AdaGrad (diagonal version) and WNGrad can be rederived from our approach. Based on our approach, the updating rules for the learning rate do not rely on the smoothness constant of optimization problems and are robust to the initial learning rate. We theoretically analyze our approach in full batch and online learning settings, which achieves comparable performances with other first-order gradientbased algorithms in terms of accuracy as well as convergence rate.

heading: 1 INTRODUCTION
text: The automatic choice of the learning rate remains crucial in improving the efficiency of gradient descent algorithms, especially for solving nonconvex optimization problems. It is desirable to adaptively update the learning rate during the training process with a certain strategy. The convergence guarantees of such a strategy in theories usually require the Lipschitz constant or smoothness constant of the objective function to be explicitly known (Nesterov, 2013; Bubeck et al., 2015), which is inaccessible in most cases, e.g., in deep neural networks.
Using the received gradient information to adjust the current learning rate is a natural approach. In particular, the Steepest Descent uses the received gradient direction and an exact or inexact line search to obtain proper learning rates. Another important idea is to approximate second-order methods like Newton method (Nocedal & Wright, 2006) and Quasi-Newton Methods (Liu & Nocedal, 1989). Along this idea, for example, the Barzilai-Borweinin (BB) method (Barzilai & Borwein, 1988) in classical optimization and AdaGrad (Duchi et al., 2011) in online learning have been proposed.
In this paper we propose a novel framework to learn the learning rate that we call HyperRegularization. More specifically, we regard the learning rate as a hyperparameter and cast its adaptive choice with the parameter training into a joint process. We formulate this process as a maxmin framework by imposing a regularizer on the hyperparameter. Furthermore, we demonstrate that AdaGrad and WNGrad (Wu et al., 2018) can be derived using a streamlined scheme based on Hyper-Regularization.
In addition to solving the saddle point problem exactly, we also provide an alternating strategy to solve the problem approximately. We respectively give theoretical analysis for these two updating rules in full batch setting and online learning setting. Specifically, our results of runtime bounds in full batch setting and regret bounds in online learning setting are comparable to the best known bound in corresponding settings and indicate our algorithms converge for any initial learning rate.

heading: 1.1 RELATED WORK
text: Steepest Descent uses the received gradient direction and an exact or inexact line search to obtain proper learning rates. Although Steepest Descent uses the direction that descends most and the best learning rate that gives the most function reduction, Steepest Descent may converge very slow for
convex quadratic functions when the Hessian matrix is ill-conditioned (see, Yuan, 2008). In practice, some line search conditions such as Goldstein conditions or Wolfe conditions (see, Fletcher, 2013) can be applied to compute the learning rate. In online or stochastic settings, one observes stochastic gradients rather than exact gradients and line search methods become less effective.
The Barzilai-Borwein method (Barzilai & Borwein, 1988) which was motivated by quasi-Newton methods presents a surprising result that it could lead to superlinear convergence in convex quadratic problem of two variables. Although numerical results often show the Barzilai-Borwein method converges superlinearly in solving nonlinear optimization problem, no superlinear convergence results have been established even for an n-dimensional strictly convex quadratic problem with the order n > 2 (Barzilai & Borwein, 1988; Dai, 2013). In minimizing the sum of cost functions and stochastic setting, SGD-BB proposed by Tan et al. (2016) takes the average of the stochastic gradients in one epoch as an estimation of the full gradient. But this approach can not directly be applied to online learning settings.
In online convex optimization (Zinkevich, 2003; Shalev-Shwartz et al., 2012; Hazan et al., 2016), AdaGrad (Duchi et al., 2011) adapts the learning rate on per parameter basis dynamically. Intuitively, AdaGrad constructs approximation to the Hessian with diagonal of accumulated outer products of gradients. This leads to many variants such as RMSProp (Tieleman & Hinton, 2012), AdaDelta (Zeiler, 2012), Adam (Kingma & Ba, 2015), etc.
Additionally, Cruz (2011) analyzed Adaptive Stochastic Gradient Descent (ASGD) which is a generalization of Kesten’s accelerated stochastic approximation algorithm (Kesten et al., 1958) for the high-dimensional case. ASGD uses a monotone decreasing function with respect to a time variable to get learning rates. Recently, Baydin et al. (2018) proposed Hyper-Gradient Descent to learn the global learning rate in SGD, SGD with Nesterov momentum and Adam. Hyper-Gradient Descent can be viewed as an approximate line search method in the online learning setting and it uses the update rule for the previous step to optimize the leaning rate in the current step. However, HyperGradient Descent has no theoretical guarantee.
It is worth mentioning that Gupta et al. (2017) proposed a framework named Unified Adaptive Regularization from which AdaGrad and Online Newton Step (Hazan et al., 2007) can be derived. However, Unified Adaptive Regularization gives an approach for approximating the Hessian matrix in second order methods.

heading: 1.2 NOTATION
text: Before introducing our approach, we present the notation. We denote the set {x > 0 : x ∈ R} by R++. For two vectors a, b ∈ Rd, we use a/b to denote element-wise division, a ◦ b for elementwise product (the symbol ◦ will be omitted in the explicit context), an = (an1 , an2 , . . . , and ), and a ≥ b if aj ≥ bj for all j. Let 1 be the vector of ones with an appropriate size, and diag(β) be a diagonal matrix with the elements of the vector β on the main diagonal. In addition, we define ‖a‖A = √ 〈a, Aa〉.
Given a set X ⊆ Rd, a function f : X → R is said to satisfy f ∈ C1,1L (X ) if f is continuously differentiable on X , and the derivative of f is Lipschitz continuous on X with constant L:
‖∇f(x)−∇f(y)‖2 ≤ L‖x− y‖2.
More general definition can be found in Nesterov (2013).

heading: 1.3 PROBLEM STATEMENT
text: For an online learning problem, a learner faces a sequence of convex functions {ft} with the same domain X ⊆ Rd, receives (sub)gradient information gt ∈ ∂ft(xt) at each step t, and predicts a point xt+1 ∈ X . Our theoretical analysis is based on two settings: full batch setting and online learning setting. A full batch setting (or optimization setting) is to optimize a certain function F with exact gradient at each step, i.e., ft = F . In this setting we assume F ∈ C1,1L but it is not necessarily convex. We analyze the convergence of our algorithms by capping the runtime T such that the minimum value
of the norm of received gradients so far is less than a given error accuracy ε, that is,
min t=0:T−1
‖∇F (xt)‖22 ≤ ε.
In online learning settings, our analysis follows from Duchi et al. (2011) and Kingma & Ba (2015). We only assume that ft’s are convex and try to give an upper bound for the regret
R(T ) = T−1∑ t=0 ft(xt)− min x∈X T−1∑ t=0 ft(x). (1)

heading: 2 HYPER-REGULARIZATION
text: Following the setting in AdaGrad (Duchi et al., 2011), we consider a generalization of the standard (sub)gradient descent as
xt+1 = Π diag(βt)
1/2
X
( xt − diag(βt)−1/2gt ) = arg min
x∈X ∥∥∥xt − diag(βt)−1/2gt∥∥∥2 diag(βt)1/2 . (2)
This procedure can be viewed as the minimization problem:
min x∈X 〈gt,x− xt〉+
1 2 ‖x− xt‖2diag(βt). (3)
To derive our hyper-regularization approach, we then formulate this minimization problem as a saddle point problem by adding a hyper-regularizer about the difference between the new learning rate β and an auxiliary vector ηt. Accordingly, we have
max β∈Bt min x∈X
Ψt(x,β) , 〈gt,x− xt〉+ 1
2
( ‖x− xt‖2diag(β) −D(β,ηt) ) , (4)
where D(β,η) is defined as our hyper-regularizer and Bt is a subset in Rd. We solve the saddle point problem for new predictor and new learning rate.
Our framework stems from the work of Daubechies et al. (2010), where the authors adjust the weights of the weighted least squares problem by solving an extra objective function which added a regularizer about the weights to origin objective function. The following subsections will explain some details about our framework.
2.1 THE ϕ-DIVERGENCE
It is reasonable to choose a distance function to measure the difference between β and η. In this paper, we use the ϕ-divergence1 as our hyper-regularizer. Definition 1 (ϕ-divergence). Let ϕ: R++ → R be a differentiable strongly convex function in R++ such that ϕ(1) = ϕ′(1) = 0, where ϕ′ is the derivative function of ϕ. For such a function ϕ, the function Dϕ: Rd++ × Rd++ → R, which is define by
Dϕ(u,v) , d∑ j=1 vjϕ(uj/vj),
is referred to as the ϕ-divergence.
Remark. Note that convex function ϕ with ϕ(1) = ϕ′(1) = 0 satisfies ϕ(z) ≥ 0 for all z > 0, thus Dϕ(u,v) ≥ 0 for all u,v ∈ Rd++, with equality iff u = v. Remark. For any convex function f , ϕ(z) = f(z) − f ′(1)(z − 1) − f(1) is a proper function for our ϕ-divergence.
Remark. In our framework, in order to solve the problem (4) feasibly, we always assume that limz→+∞ ϕ
′(z) = +∞. 1Comparing with Bregman divergence, ϕ-divergence requires nonnegative β and ηt which is apparent for
learning rates.
If one only requires ϕ to be convex and ϕ(1) = 0, the resulting distance function Dϕ is called a f -divergence (Liese & Vajda, 1987; 2006). The f -divergence has been widely applied in statistical machine learning (e.g., Nguyen et al., 2009).
Using the ϕ-divergence as our hyper-regularizer, we can rewrite the problem (4) as
max β∈Bt min x∈X
Ψt(x,β) , g > t (x− xt) +
1 2 ‖x− xt‖2diag(β) − 1 2 Dϕ(β,ηt), or (5)
max β∈Bt min x∈X Ψt(x,β) , d∑ j=1 gt,j(xj − xt,j) + 1 2 ( βj(xj − xt,j)2 − ηt,jϕ(βj/ηt,j) ) . (6)
The form of problem (6) implies that we can solve the problem for each dimension separately, and only a few extra calculations are required for each step.

heading: 2.2 MAX-MIN OR MIN-MAX
text: Consider a problem similar to (5), min x∈X max β∈Bt Ψt(x,β). (7)
The solution of problem (5) is same as (7) in unconstrained case2, i.e. X = Rd,Bt = Rd++. However, if we set Bt = [bt,1, Bt,1] × · · · × [bt,d, Bt,d] to constrain the range of βt+1 and suppose X = Rd, the solution of (7) is more difficult to get from the solution of the unconstrained problem, while the solution of (5) can be easily obtained by clipping the solution of the unconstrained problem to required range (see Lemma 2). Thus, we choose (5) as our basic problem.
Lemma 2. Suppose that Bt = [bt,1, Bt,1] × · · · × [bt,d, Bt,d], and X = Rd. Let β∗ be the solution of unconstrained problem maxβ(minxΨt(x,β)). Then the solution of problem maxβ∈Bt(minxΨt(x,β)) is
βj = min{max{β∗j , bt,j}, Bt,j}, for j = 1, · · · , d.
2.3 SELECTION OF ηt
There are many ways to choose the sequence {ηt}:
• The sequence {ηt} is chosen in advance, before our methods start the job. For example, set 1) ηt = η 1; 2) ηt = η √ t+ 11, where η > 0 is a prespecified constant.
• ηt can be obtained from other adaptive learning rate methods such as AdaGrad. • Set ηt = βt. In this case, the hyper-regularizer is the penalty for the change between βt+1
and βt.
The first two ways can be treated as a smoothing technique to stabilize the learning rate. We want to ensure the learning rate sequence {βt} close to another learning rate sequence {ηt}. Although setting ηt = βt is our main focus, we keep the sequence of {ηt} to maintain this flexibility.

heading: 2.4 ISOTROPIC HYPER-REGULARIZATION
text: We now show a special form of our framework that only adaptively maintains a single scalar learning rate. We modify Hyper-regularization so that β is optimized over the set Bt ⊆ {θ1 : θ ∈ R++} of all positive multiples of the vector 1 ∈ Rd. Let ηt = ηt1, and rewrite problem (5) as
max β1∈Bt min x∈X
Ψt(x, β) = g > t (x− xt) +
β 2 ‖x− xt‖22 − 1 2 ηtϕ(β/ηt). (8)
We prefer to use Isotropic Hyper-Regularization as smoothing technique in online learning settings.
2Using partial derivative, we can obtain the saddle point of Ψt and ensure this fact.

heading: 3 UPDATE RULES AND ALGORITHMS
text: In this section we present two update rules of our hyper-regularization framework. The first update rule is solving the saddle point problem (5) exactly. That is,
Ψt(xt+1,βt+1) = max β∈Bt min x∈X Ψt(x,β). (9)
The following lemma and Algorithm 1 give the concrete scheme of our iterations. Lemma 3. Considering problem (6) without constraints and solving the problem exactly, we get new predictor xt+1 and new learning rate βt+1 such that
β2t+1,jϕ ′(βt+1,j/ηt,j) = g 2 t,j , j = 1, . . . , d, (10)
xt+1 = xt − gt/βt+1.
Algorithm 1 GD with Hyper-regularization Input: β0 > 0, x0 1: for t = 1 to T do 2: Suffer loss ft(xt); 3: Receive subgradient gt ∈ ∂ft(xt) of ft at xt; 4: Update βt+1,j as the solution of the equation β2ϕ′(β/ηt,j) = g2t,j , j = 1, . . . , d; 5: Update xt+1 = xt − gt/βt+1; 6: end for
Remark. Note that AdaGrad (Duchi et al., 2011) and WNGrad (Wu et al., 2018) are special cases of Algorithm 1 with a particular choice of ϕ (detailed derivation in Appendix B).
• If ϕ(z) = z + 1z − 2, then we can derive AdaGrad from Algorithm 1.
• If ϕ(z) = 1z − log( 1 z )− 1, then we can derive WNGrad from Algorithm 1.

heading: 3.1 ALTERNATING UPDATE RULE
text: However, it is sometimes difficult to solve the equation (10), especially in the case where ϕ is a quadratic function (equation (10) will be a cubic equation in one variable for any j). In practice, using an alternating update strategy is more recommended. Under the assumption that the optimal value of β is close to ηt, we solve an approximate equation for βt+1
βt+1 = arg max β∈Bt Ψt ( arg min x∈X Ψt(x,ηt),β ) , (11)
and update the new predictor xt+1 using xt+1 = arg min
x∈X Ψt(x,βt+1).
Applying the alternating update rule under the same assumption in Lemma 3, we obtain the following lemma and Algorithm 2. Lemma 4. Considering problem (6) without constraint and following from the alternating update rule, we get new predictor xt+1 and new learning rate βt+1 as
βt+1,j = ηt,j(ϕ ′)−1(g2t,j/η 2 t,j), j = 1, . . . , d, (12)
xt+1 = xt − gt/βt+1.
Algorithm 2 GD with Hyper-regularization using alternating update rule Input: β0 > 0, x0 1: for t = 1 to T do 2: Suffer loss ft(xt); 3: Receive gt ∈ ∂ft(xt) of ft at xt; 4: Update βt+1,j = ηt,j(ϕ′)−1(g2t,j/η 2 t,j), j = 1, . . . , d;
5: Update xt+1 = xt − gt/βt+1; 6: end for
Computing the inverse function of ϕ′ is usually easier than solving the equation (10) in practice, especially for the widely used ϕ-divergences (more details can be found in Appendix D.1).
Remark. If ηt = βt, the following simplified alternating rule can be employed:
xt+1 = arg min x∈X Ψt(x,βt),
βt+1 = arg max β∈Bt Ψt (xt+1,β) .
We leave the corresponding algorithm 3 in Appendix C.

heading: 3.2 MONOTONICITY
text: Before giving more analysis, let us show monotonicity of both the two update rules. The monotonicity implies that only the property of convex function ϕ on interval [1,+∞) will influence the efficiency of our algorithms.
Lemma 5. βt+1 obtained from equation (9) or (11) satisfies βt+1 ≥ ηt.
When setting βt = ηt, we have that βt+1 ≥ βt.

heading: 4 THEORETICAL ANALYSIS
text: In this section we always set ηt = βt and assume that x and β are unconstrained, i.e., X = Rd and Bt = Rd++. We first discuss the convergence rate of the two update rules in full batch setting with assumption that the objective function F is L-smooth but not necessarily convex in Section 4.1. Next we turn to online convex learning setting and establish a theorem about the regret bounds in Section 4.2. Our results for both the settings show that our algorithms are robust to the choice of initial learning rates and do not rely on the Lipschitz constant or smoothness constant.

heading: 4.1 ISOTROPIC HYPER-REGULARIZATION IN FULL BATCH SETTING
text: Recall that we set ft = F in the full batch setting, and assume that F ∈ C1,1L without convexity. In this case, two update rules can be written as{
β2t+1ϕ ′(βt+1/βt) = ‖gt‖22 , xt+1 = xt − 1βt+1 gt. (13)
{ βt+1 = βt(ϕ
′)−1(‖gt‖22 /β2t ), xt+1 = xt − 1βt+1 gt.
(14)
Next we show that both update rules (13) and (14) are robust to the choice of initial learning rate.
Theorem 6. Suppose that ϕ ∈ C1,1l ([1,+∞)), ϕ is α-strongly convex, F ∈ C 1,1 L (Rd), and F ∗ = infx F (x) > −∞. For any ε ∈ (0, 1), the sequence {xt} obtained from update rules (13) or (14) satisfies
min j=0:T−1
‖∇F (xj)‖22 ≤ ε,
after T = O (
1 ε
) steps.
More detailed results of Theorem 6 for runtime can be found in Theorems 21 and 22 in Appendix I. Theorem 6 shows that both runtime of the two update rules can be bound asO(1/ε) for any constant L and initial learning rate β0. As a comparison, in classical convergence result ((1.2.13) in Nesterov (2013) or Theorem 20 in Appendix), the upper bound of runtime is O(1/ε) only for a certain range (related to L) of initial learning rates.

heading: 4.2 HYPER-REGULARIZATION IN ONLINE LEARNING SETTING
text: We now establish the result of convergence rate for Algorithms 1 and 2 in online convex learning, i.e., the ft are convex. Especially, we try to bound regrets (1) by O( √ T ) for Algorithms 1 and 2.
Theorem 7. Suppose that ϕ ∈ C1,1l ([1,+∞)), and ϕ is α-strongly convex. Assume that ‖gt‖∞ ≤ G, and ‖xt − x∗‖∞ ≤ D∞. Then the sequence {xt} obtained from Algorithm 1 satisfies
2R(T ) ≤ (α+D 2 ∞) √ 2lβ20 + 4G 2
αβ0
d∑ j=1 ‖g0:T−1,j‖2 + β0‖x0 − x∗‖22,
and the sequence {xt} obtained from Algorithm 2 (or 3) satisfies
2R(T ) ≤ (
1 + D2∞ α
) max {√ 2l, 2G
β0 } d∑ j=1 ‖g0:T−1,j‖2 + β0‖x0 − x∗‖22.
Note that under the assumption in Theorem 7, ∑d j=1 ‖g0:T−1,j‖2 ≤ dG √ T , hence R(T ) = O( √ T ). Our result is comparable to the best known bound for convex online learning problem (see Hazan et al., 2016; Duchi et al., 2011; Kingma & Ba, 2015).

heading: 5 EXPERIMENTS
text: In this paper our principal focus has been to develop a new approach for adaptive choice of the learning rate in first-order gradient-type methods. However, this new approach also brings some insights into the resulting algorithms. Thus, it is interesting to conduct empirical analysis of the learning algorithms with different choice methods for the learning rate.

heading: 5.1 THE SET-UP
text: To derive a learning algorithm from the Hyper-Regularization framework, we have to first give the ϕ divergences (Pardo, 2005). Specifically, the algorithms from our framework in the following experiments are derived from the following four ϕ divergences (full implementations are displayed in the Appendix D.1):
• ϕ(t) = t log t− t+ 1 from KL-divergence inducing KL algorithm. • ϕ(t) = − log t+ t− 1 from Reverse KL-divergence inducing RKL algorithm. • ϕ(t) = ( √ t− 1)2 from Hellinger distance inducing Hellinger algorithm.
• ϕ(t) = (t− 1)2 from χ2 distance inducing χ2 algorithm.
As mentioned in Section 3, even with a fixed ϕ divergence, the generated algorithm still varies with different update rules. For simplicity, different update rules were compared in advance to select the specific one for any ϕ divergence in the following experiments.
To maintain stable performance, the technique of growth clipping is applied to all algorithms in our framework. Actually, growth clipping fulfills the constraints placed on the increasing speed of βt by Bt in Lemma 2. Specifically, βt+1 in our experiments falls in [βt, 2βt]. Detailed observations on how the βt of our algorithms increases are left in Appendix D.3.
Experiments involve the four algorithms generated above as well as other first-order gradient-based algorithms including SGD (with no learning rate decay), SGD-BB, and Hyper-Gradient Descent algorithms. These algorithms are evaluated on tasks of image classification with a logistic classifier on the databases of MNIST (LeCun et al., 2010) and CIFAR-10 (Krizhevsky & Hinton, 2009). Initial learning rate (in the usual sense, i.e., 1/β0) varies from 10−3 to 101 for the test of convergence performance of these algorithms. Experiments are run using Tensorflow (Abadi et al., 2016), on a machine with Intel Xeon E5-2680 v4 CPU, 128 GB RAM, and NVIDIA Titan Xp GPU.

heading: 5.2 UPDATE RULE SELECTION
text: Taking the RKL algorithm as an example, we refer to algorithms deduced from Algorithm 1, 2, and 3 as RKL1, RKL2, and RKL3. We train a two-layer neural network with a hidden layer of 500 units on the MNIST database. Experiments are in online learning setting with a batch size of 128, and `2 regularization is applied with a coefficient of 10−4.
Figure 1 demonstrates the training loss and test accuracy of these algorithms with various initial learning rates. After fixing the learning rate with the least training loss, we compare their performances throughout the training process. Sharing comparable performances at small initial learning rate with RKL3, RKL1 and RKL2 perform better at relatively large learning rate.
Generally speaking, Algorithm 1 often suffers a higher computation complexity than Algorithm 2 for the difficulty of getting an analytical solution. Detailed observations are left in Appendix D.1. Therefore, we apply the second update rule to our algorithms without explicit notifications.

heading: 5.3 FULL BATCH SETTING AND ONLINE LEARNING SETTING
text: We investigate our algorithms in the full batch setting on the MNIST database where algorithms receive the exact gradients of the objective loss function each iteration. 3
In terms of online learning setting, we train a VGG Net (Simonyan & Zisserman, 2014) with batch normalization on the CIFAR-10 database with a batch size of 128, and an `2 regularization coefficient of 10−4. We as well perform data augmentation as He et al. (2016) to improve the training.
Figure 2 and Figure 3 show the convergence performances on both settings, respectively. Achieving general comparable performances with other first-order gradient-based algorithms, our algorithms outperform most of other algorithms at risky large initial learning rate. Even at the fixed initial learning rate with the least training loss, the performances of our algorithms still achieve the same training performances with others.
3Since it is a pure optimization problem, testing performance is out of our main consideration.

heading: 6 DISCUSSION
text: As a supplement, we point out that logarithmic regret bounds under assumption ft is strongly convex, like Hazan et al. (2007); Mukkamala & Hein (2017), can be established with a different class of distance function. We leave the details in Appendix H.
In this paper, we propose a novel framework distinct from previous main approaches like line search and approximate second-order methods. It worth noting that Hyper-Regularization can generates efficient algorithms for optimization problems with regularization terms shown above and we expect new ideas of more efficient terms in the future.

heading: A SOLUTION EXISTENCE
text: Note that the function h(β) = β2ϕ′(β/ηt,j) is an increasing continuous function and limz→+∞ ϕ
′(z) = +∞ ϕ′(1) = 0, so [0,+∞) is a subset of the range of h(β) and the solution of (10) exists. For the same reason, the solution of (12) exists.

heading: B SPECIAL CASES OF ALGORITHM 1
text: In this section, We will point out that Adagrad (Duchi et al., 2011) and WNGrad (Wu et al., 2018) are special cases of Algorithm 1. If we set ϕ(z) = z + 1z − 2, then the new learning rate βt+1 can be obtained by
β2t+1,j
( 1−
β2t,j β2t+1,j
) = g2t,j , j = 1, · · · , d,
that implies,
β2t+1 = β 2 t + g 2 t ,
and we drive AdaGrad from Hyper-Regularization.
Similarly, we can get WNGrad by setting ϕ(z) = 1z − log 1 z − 1. In fact, βt+1 employs update
β2t+1,j
( βt,j(βt+1,j − βt,j)
β2t+1,j
) = g2t,j , j = 1, · · · , d,
on the other words,
βt+1 = βt + g2t βt ,
i.e., the update rule of WNGrad.

heading: C SIMPLIFIED ALTERNATING UPDATE RULE
text: Algorithm 3 GD with Hyper-regularization using simplified alternating update rule and ηt = βt Input: β0 > 0, x0 1: for t = 1 to T do 2: Suffer loss ft(xt); 3: Receive gt ∈ ∂ft(xt) of ft at xt; 4: Update xt+1 = xt − gt/βt; 5: Update βt+1,j = βt,j(ϕ′)−1(g2t,j/β 2 t,j), j = 1, . . . , d;
6: end for
The weakness of the simplified alternating update rule is that we get the new predictor xt+1 by βt which is unrelated to current gradient gt. The regret bound of Algorithm 3 has been shown in Theorem 7.

heading: D SUPPLEMENTARY FOR NUMERICAL EXPERIMENTS
text: Full versions of Hellinger, KL, RKL, and χ2 algorithms through Algorithm 1, 2, and 3 are listed below. Apparently, it is of great complexity to compute an analytical solution for βt+1 for the equations marked red.
D.1 FULL VERSIONS OF GENERATED ALGORITHMS
KL1
{ β2t+1 log(βt+1/βt) = g 2 t
xt+1 = xt − gt/βt+1
KL2
{ βt+1 = βt exp(g 2 t /β 2 t )
xt+1 = xt − gt/βt+1
KL3 { xt+1 = xt − gt/βt βt+1 = βt exp(g 2 t /β 2 t )
RKL1
{ βt+1 = 1 2 ( βt + √ β2t + 4g 2 t ) xt+1 = xt − gt/βt+1
RKL2
{ βt+1 = β 3 t /(β 2 t − g2t )
xt+1 = xt − gt/βt+1
RKL3 { xt+1 = xt − gt/βt βt+1 = β 3 t /(β 2 t − g2t )
H1
{ β2t+1(1− √ βt/βt+1) = g 2 t
xt+1 = xt − gt/βt+1
H2
{ βt+1 = β 5 t /(β 2 t − g2t )2
xt+1 = xt − gt/βt+1
H3 { xt+1 = xt − gt/βt βt+1 = β 5 t /(β 2 t − g2t )2
χ21 { 2β2t+1(βt+1/βt− 1) = g2t xt+1 = xt − gt/βt+1
χ22
{ βt+1 = βt ( 1 + g2t /(2β 2 t ) )
xt+1 = xt − gt/βt+1
χ23 { xt+1 = xt − gt/βt βt+1 = βt ( 1 + g2t /(2β 2 t ) )
D.2 VERSION COMPARISON ON OTHER ALGORITHMS
Figure 4, 5 and 6 shows the results of comparison between versions of KL, Hellinger, and χ2 algorithms on the base of MNIST in the online learning setting.
D.3 FIGURES ON βt INCREASING PROCESS
All the following experiments are based on the MNIST database in online learning setting with a batch size of 128. For simplicity, all initial β0s are fixed to be 10−0.5. Considering the sparse feature of parameters in this task, figure 7 only observe the changing process of the maximum of βt.

heading: E PROOF OF LEMMA 2
text: Proof. First, it is trivial to get
Ψt,x(β) ,minxΨt(x,β) = Ψt ( xt −
gt β ,β ) = − 1
2 ‖gt‖2diag(β)−1 −
1 2 Dϕ(β,ηt)
= − 1 2 d∑ j=1 ( g2t,j βj + ηt,jϕ ( βj ηt,j )) .
The partial derivative of Ψt,x(β) with respect to βj is
∂Ψt,x(β)
∂βj =
1
2 ( g2t,j β2j − ϕ′ ( βj ηt,j )) .
Note that ϕ is a convex function, so ϕ′ is a non-decreasing function, and ∂Ψt,x(β)∂βj is a non-increasing function. Recall that β∗ be the solution of unconstrained problem maxβ(minxΨt(x,β)), hence, β∗j is a zero of function ∂Ψt,x(β) ∂βj . Moreover, if β∗j > Bt,j , we have ∂Ψt,x(β) ∂βj
≥ 0. Thus, Ψt,x(β) with respect to βj is a nondecreasing function, and arg maxβj Ψt,x(β) = Bt,j . For a similar reason, if β ∗ j < bt,j , then arg maxβj Ψt,x(β) = bt,j . In conclusion,
arg max βj∈[bt,j ,Bt,j ]
Ψt,x(β) = min{max{β∗j , bt,j}, Bt,j}, for j = 1, · · · , d.

heading: F PROOF OF LEMMA 5
text: In this section, we denote that Ψt,x(β) = minx∈X Ψt(x, β).
Lemma 8. βt+1 obtained from equation (9) satisfies βt+1 ≥ ηt.
Proof. Recall that ϕ(1) = ϕ′(1) = 0, so ϕ(x) ≥ 0 for all x and Dϕ(β, ηt) = ηtϕ(β/ηt) ≥ 0. If β < ηt, then for all x ∈ X
Ψt(x, β) = g > t (x− xt) +
β 2 ‖x− xt‖22 − 1 2 Dϕ(β, ηt)
< g>t (x− xt) + ηt 2 ‖x− xt‖22
= Ψt(x, ηt).
Hence, minx∈X Ψt(x, β) < minx∈X Ψt(x, ηt), i.e., Ψt,x(β) < Ψt,x(ηt). It means βt+1 = arg maxβ∈B Ψt,x(β) ≥ ηt.
Lemma 9. βt+1 obtained from equation (11) satisfies βt+1 ≥ ηt.
Proof. Let y = arg minxΨ(x,ηt). If β < ηt, then
Ψt(y, β) = g > t (y − xt) +
β 2 ‖y − xt‖22 − 1 2 Dϕ(β, ηt)
< g>t (y − xt) + ηt 2 ‖y − xt‖22
= Ψt(y, ηt).
Hence βt+1 = arg maxβ∈B Ψt(y, β) ≥ ηt.

heading: G CONVERGENCE RATES IN ONLINE LEARNING SETTING
text: Recall the define of regret
R(T ) = T−1∑ t=0 (ft(xt)− ft(x∗)), (15)
where x∗ = arg minx∈X ∑T−1 t=0 ft(x). We show our hyper-regularizer method with three update
rules (Algorithm 1, 2 and 3) have O( √ T ) regret bounds.
Lemma 10 (Lemma 4 in Adagrad). Consider an arbitrary real-valued sequence {ai} and its vector representation a1:i = (a1, · · · , ai)>. Then
T∑ t=1 a2t ‖a1:t‖2 ≤ 2‖a1:T ‖2 (16)
holds.
Proof. Let us use induction on T to prove inequality (10). For T = 1, the inequality trivially holds. Assume the bound (16) holds true for T − 1, in which case
T∑ t=1 a2t ‖a1:t‖2 ≤ 2‖a1:T−1‖2 + a2T ‖a1:T ‖2 .
We denote bT = ∑T t=1 a 2 t and have
2‖a1:T−1‖2 + a2T ‖a1:T ‖2 = 2 √ bT − a2T + a2T√ bT
≤ 2 √ bT − a2T +
a4T 4bT + a2T√ bT
= 2 √ bT .
Lemma 11. Suppose the sequence {xt} and sequence {βt} satisfy xt+1 = xt − gt/βt+1. Then the regret satisfies
2R(T ) ≤ T−1∑ t=0 ‖gt‖2diag(βt+1)−1 + T−1∑ t=0 ‖xt − x∗‖2diag(βt+1−βt) + ‖x0 − x ∗‖2diag(β0)
Proof. Note that
xt+1 = xt − diag(βt+1)−1gt,
and
‖xt+1 − x∗‖2diag(βt+1) = ‖xt − x∗ − diag(βt+1)−1gt‖2diag(βt+1) = ‖xt − x∗‖2diag(βt+1) + ‖gt‖ 2 diag(βt+1)−1 − 2g>t (xt − x∗),
i.e., 2g>t (xt − x∗) = ‖gt‖2diag(βt+1)−1 + ( ‖xt − x∗‖2diag(βt+1) − ‖xt+1 − x ∗‖2diag(βt+1) ) . (17)
Hence
2R(T ) = 2 T−1∑ t=0 (ft(xt)− ft(x∗))
≤ 2 T−1∑ t=0 g>t (xt − x∗)
= T−1∑ t=0 ‖gt‖2diag(βt+1)−1 + T−1∑ t=0 ( ‖xt − x∗‖2diag(βt+1) − ‖xt+1 − x ∗‖2diag(βt+1) )
≤ T−1∑ t=0 ‖gt‖2diag(βt+1)−1 + T−1∑ t=0 ‖xt − x∗‖2diag(βt+1−βt) + ‖x0 − x ∗‖2diag(β0).
Lemma 12. Suppose an increasing function ψ satisfies ψ(1) = 0 and ψ(x) ≤ l(x − 1). Consider a real valued sequence {gt}t=0:T−1 and a positive sequence {βt}t=0:T which satisfies |gt| ≤ G, β2t+1ψ ( βt+1 βt ) = g2t , t = 0, · · · , T − 1, β0 ≥ 0. We can bound βT as
βt ≥ c √√√√β20 + 2l t−1∑ i=0 g2i , t = 1, · · · , T (18)
where c = √
β20 β20+2G 2/l . Moreover, we have
T−1∑ t=0 g2t βt+1 ≤ √ 2lβ20 + 4G 2 β0 √√√√T−1∑ t=0 g2t . (19)
Remark. We point out that
• βt+1 ≥ βt (If βt+1 < βt, then β2t+1ψ(βt+1/βt) < 0 ≤ g2t ),
• βt+1 is unique with respect to βt due to the fact that the function ψ̂(β) = β2ψ(β/βt) is strictly increasing.
Proof. Assume that βt ≥ c √ β20 + 2 l ∑t−1 i=0 g 2 i , where c > 0 is a variable coefficient.
Let us find out a specific c such that βt+1 ≥ c √ β20 + 2 l ∑t i=0 g 2 i . Note that
g2t = β 2 t+1ψ ( βt+1 βt ) ≤ lβ2t+1 ( βt+1 βt − 1 ) . (20)
Define a cubic polynomial
h(β) = l
βt β3 − lβ2 − g2t ,
and h is an increasing function when β ≥ βt. If h ( c √ β20 + 2 l ∑t i=0 g 2 i ) ≤ 0, according to h(βt+1) ≥ 0, then βt+1 ≥ c √ β20 + 2 l ∑t i=0 g 2 i .
Denote b = β20 + 2 l ∑t−1 i=0 g 2 i . So we just need to choose c such that
h c √√√√β20 + 2l t∑ i=0 g2i  ≤ lc2(b+ 2g2t /l) (√ b+ 2g2t /l√ b − 1 ) − g2t ≤ 0,
where the first inequality holds for the assumption βt ≥ c √ β20 + 2 l ∑t−1 i=0 g 2 i , or
c2√ b (b+ 2g2t /l) 2g2t /l√ b+ 2g2t /l + √ b ≤ g2t /l,
or 2c2√ b (b+ 2g2t /l) ≤ √ b+ 2g2t /l + √ b.
Thus, c just need to satisfy
c2 ≤ b b+ 2g2t /l .
According to b ≥ β20 , g2t ≤ G2, hence b
b+ 2g2t /l ≥ β
2 0
β20 + 2G 2/l
. So if we choose c = √
β20 β20+2G 2/l , then β1 > β0 > cβ0, hence
βt ≥ c √√√√β20 + 2l t−1∑ i=0 g2i , t = 1, · · · , T.
Moreover, following from Lemma 10, we have
T−1∑ t=0 g2t βt+1 ≤ T−1∑ t=0
g2t c √ 2/l √∑t
i=0 g 2 i
≤ √ 2l
c √√√√T−1∑ t=0 g2t .
Lemma 13. Suppose an increasing function ψ satisfies ψ(1) = 0 and ψ(x) ≤ l(x − 1). Consider a real valued sequence {gt}t=0:T−1 and a positive sequence {βt}t=0:T which satisfies |gt| ≤ G, β2t ψ ( βt+1 βt ) = g2t , t = 0, · · · , T − 1, β0 ≥ 0. We can bound βT as
βt ≥ √√√√β20 + 2l t−1∑ i=0 g2i , t = 1, · · · , T. (21)
Moreover, we have
T−1∑ t=0 g2t βt ≤ max {√ 2l, 2G β0 }√√√√T−1∑ t=0 g2t . (22)
Proof. Same as inequality (20), we have
lβ2t ( βt+1 βt − 1 ) ≥ g2t ,
hence
β2t+1 = ( βt +
g2t lβt
)2 ≥ β2t + 2
l g2t ≥ β20 +
2
l t∑ i=0 g2t ≥ min { 1, lβ20 2G2 } 2 l t+1∑ i=0 g2i , .
Furthermore, following from Lemma 10, we have
T−1∑ t=0 g2t βt ≤
√ l/2
min{1, lβ20/(2G2)} T−1∑ t=0 g2t√∑t i=0 g 2 i ≤ max {√ 2l, 2G β0 }√√√√T−1∑ t=0 g2t .
Theorem 14. Suppose that ϕ ∈ C1,1l ([1,+∞)), and ϕ is α-strongly convex. Assume that ‖gt‖∞ ≤ G, and ‖xt − x∗‖∞ ≤ D∞. Then the sequence {xt} obtained from Algorithm 1 satisfies
2R(T ) ≤ (α+D 2 ∞) √ 2lβ20 + 4G 2
αβ0
d∑ j=1 ‖g0:T−1,j‖2 + β0‖x0 − x∗‖22,
Proof. Following from Lemma 11,
2R(T ) ≤ T−1∑ t=0 ‖gt‖2diag(βt+1)−1 + T−1∑ t=0 ‖xt − x∗‖2diag(βt+1−βt) + ‖x0 − x ∗‖2diag(β0)
≤ T−1∑ t=0 ‖gt‖2diag(βt+1)−1 + T−1∑ t=0 ‖xt − x∗‖2∞‖βt+1 − βt‖1 + ‖x0 − x∗‖2diag(β0)
≤ T−1∑ t=0 d∑ j=1 g2t,j βt+1,j + max 0≤t<T ‖xt − x∗‖2∞ T−1∑ t=0 d∑ j=1 (βt+1,j − βt,j) + ‖x0 − x∗‖2diag(β0).
Recall ϕ is a α-strongly convex function, so,
g2t,j = β 2 t+1,jϕ ′ ( βt+1,j βt,j ) ≥ αβt+1,jβt,j ( βt+1,j βt,j − 1 ) ,
and T−1∑ t=0 (βt+1,j − βt,j) ≤ 1 α T−1∑ t=0 g2t,j βt+1,j . (23) The function ψ = ϕ′ satisfies ψ(1) = 0 and ψ(x) ≤ l(x − 1) according to the smoothness of ϕ. Following from Lemma 12, we have
T−1∑ t=0 g2t,j βt+1,j ≤
√ 2lβ20,j + 4G 2
β0,j
√√√√T−1∑ i=0 g2t,j = √ 2lβ20,j + 4G 2 β0,j ‖g0:T−1,j‖2. (24)
Combining inequality (23) and (24), we have 2R(T ) ≤ ( 1 + max0≤t<T ‖xt − x∗‖2∞
α
) d∑ j=1 T−1∑ t=0 g2t,j βt+1,j + ‖x0 − x∗‖2diag(β0)
≤ (1 + D 2 ∞ α ) d∑ j=1
√ 2lβ20,j + 4G 2
β0,j ‖g0:T−1,j‖2 + ‖x0 − x∗‖2diag(β0)
= (α+D2∞)
√ 2lβ20 + 4G 2
αβ0
d∑ j=1 ‖g0:T−1,j‖2 + β0‖x0 − x∗‖22.
Theorem 15. Suppose that ϕ ∈ C1,1l ([1,+∞)), and ϕ is α-strongly convex. Assume that ‖gt‖∞ ≤ G, and ‖xt − x∗‖∞ ≤ D∞. Then the sequence {xt} obtained from Algorithm 2 (or 3) satisfies
2R(T ) ≤ (
1 + D2∞ α
) max {√ 2l, 2G
β0 } d∑ j=1 ‖g0:T−1,j‖2 + β0‖x0 − x∗‖22.
Proof. Similar to the proof of Theorem 14, for Algorithm 2, we have
2R(T ) ≤ T−1∑ t=0 d∑ j=1 g2t,j βt+1,j + max 0≤t<T ‖xt − x∗‖2∞ T−1∑ t=0 d∑ j=1 (βt+1,j − βt,j) + ‖x0 − x∗‖2diag(β0)
≤ T−1∑ t=0 d∑ j=1 g2t,j βt,j + max 0≤t<T ‖xt − x∗‖2∞ T−1∑ t=0 d∑ j=1 (βt+1,j − βt,j) + ‖x0 − x∗‖2diag(β0).
With same reason, for Algorithm 3, we have
2R(T ) ≤ T−1∑ t=0 ‖gt‖2diag(βt)−1 + T−1∑ t=0 ( ‖xt − x∗‖2diag(βt) − ‖xt+1 − x ∗‖2diag(βt) )
≤ T−1∑ t=0 ‖gt‖2diag(βt)−1 + T−1∑ t=1 ‖xt − x∗‖2diag(βt−βt−1) + ‖x0 − x ∗‖2diag(β0)
≤ T−1∑ t=0 d∑ j=1 g2t,j βt,j + max 0≤t<T ‖xt − x∗‖2∞ T−1∑ t=1 d∑ j=1 (βt,j − βt−1,j) + ‖x0 − x∗‖2diag(β0),
Note that for both algorithms
g2t,j = β 2 t,jϕ ′ ( βt+1,j βt,j ) ≥ αβ2t,j ( βt+1,j βt,j − 1 ) ,
holds, so T−1∑ t=1 (βt,j − βt−1,j) ≤ T−1∑ t=0 (βt+1,j − βt,j) ≤ 1 α T−1∑ t=0 g2t,j βt,j ,
Thus, following from Lemma 13, for both Algorithm 2 and 3, we have
2R(T ) ≤ (1 + D 2 ∞ α ) d∑ j=1 T−1∑ t=0 g2t,j βt,j + β0‖x0 − x∗‖22
≤ (1 + D 2 ∞ α ) d∑ j=1 max {√ 2l, 2G β0 } ‖g0:T−1,j‖2 + β0‖x0 − x∗‖22.

heading: H LOGARITHMIC BOUNDS
text: In this section, we will use a different class of ‘distance’ function for problem 4, and establish logarithmic regret bounds under assumption ft is strongly convex. Our analysis and proof follow from Hazan et al. (2007); Mukkamala & Hein (2017).
First, we define µ-strongly convexity. Definition 16 (Definition 2.1 in (Mukkamala & Hein, 2017)). Let X ⊆ Rd be a convex set. We say that a function f : X → R is µ-strongly convex, if there exists µ ∈ Rd with µj > 0 for j = 1, · · · , d such that for all x,y ∈ X ,
f(y) ≥ f(x) + 〈∇f(x),y − x〉+ 1 2 ‖y − x‖2diag(µ).
Let ξ = minj=1:d µj , then this function is ξ-strongly convex (in the usual sense), that is
f(y) ≥ f(x) + 〈∇f(x),y − x〉+ ξ 2 ‖y − x‖22.
The modification SC-Hyper-Regularization of Hyper-Regularization which we propose in the following uses a family of distance function D : Rd++ × Rd++ → R formulated as
D(u,v) = d∑ j=1 ϕ(uj/vj), (25)
where ϕ is convex function with ϕ(1) = ϕ′(1) = 0 like we used in ϕ-divergence. Remark. Same as ϕ-divergence, D(u,v) ≥ 0 for any u,v ∈ Rd++.
Different from Algorithm 1 and 2, we add a hyper-parameter λ > 0 like AdaGrad to SC-HyperGradient. Rewrite problem (5) as
max β∈Bt min x∈X
Ψt(x,β) , g > t (x− xt) +
1 2 ‖x− xt‖2diag(β) − λ 2 d∑ j=1 ϕ(βj/βt,j), (26)
and corresponding two algorithms as
Algorithm 4 GD with SC-Hyper-regularization Input: β0 > 0, x0 1: for t = 1 to T do 2: Suffer loss ft(xt); 3: Receive gt ∈ ∂ft(xt) of ft at xt; 4: Update βt+1,j as the solution of the equation λ(β2/βt,j)ϕ′(β/βt,j) = g2t,j , j = 1, · · · , d; 5: Update xt+1 = xt − gt/βt+1; 6: end for
Algorithm 5 GD with SC-Hyper-regularization using alternating update rule Input: β0 > 0, x0 1: for t = 1 to T do 2: Suffer loss ft(xt); 3: Receive gt ∈ ∂ft(xt) of ft at xt; 4: Update βt+1,j = βt,j(ϕ′)−1(g2t,j/(λβt,j)), j = 1, . . . , d; 5: Update xt+1 = xt − gt/βt+1; 6: end for
Remark. Same as Lemma 5, the monotonicity of Algorithm 4 and 5 also holds. Theorem 17. Suppose that ft is µ-strongly convex for all t, ϕ ∈ C1,1l ([1,+∞)), and ϕ is αstrongly convex. Assume that ‖gt‖∞ ≤ G, and λ ≥ G2/(αminj=1:d µj). Then the sequence {xt} obtained from Algorithm 4 satisfies
2R(T ) ≤ l ( 1 + G2
λlβ0 )2 d∑ j=1 ln ( 1 + ‖g0:T−1,j‖22 λlβ0 ) + β0‖x0 − x∗‖22,
and the sequence {xt} obtained from Algorithm 5 satisfies
2R(T ) ≤ l d∑ j=1 ln
( 1 + ‖g0:T−1,j‖22
λlβ0
) + β0‖x0 − x∗‖22,
Remark. Under assumption in Theorem 17, we have ‖g0:T−1,j‖22 ≤ G 2T , so R(T ) = O(ln(T )).
To prove Theorem 17, we first prove following lemma. Lemma 18. For an arbitrary real-valued sequence {ai} and a positive real number b,
T∑ t=1
a2t b+ ∑t i=1 a 2 i ≤ ln
( 1 + ∑T t=1 a 2 t
b
) . (27)
Proof. Let b0 = b, bt = b+ ∑t i=1 a 2 i , t ≥ 1, then
T∑ t=1
a2t b+ ∑t i=1 a 2 i = T∑ t=1 bt − bt−1 bt = T∑ t=1 ∫ bt bt−1 1 bt dx
≤ T∑ t=1 ∫ bt bt−1 1 x dx = ∫ bT b 1 x dx = ln ( 1 + ∑T t=1 a 2 t b ) .
Like Lemma 12 and 13, similar lemma holds for Algorithm 4 and 5. Lemma 19. Suppose an increasing function ψ satisfies ψ(1) = 0 and ψ(x) ≤ l(x − 1). Consider a real valued sequence {gt}t=0:T−1 and a positive sequence {βt}t=0:T which satisfies |gt| ≤ G, β0 > 0. If (β2t+1/βt)ψ(βt+1/βt) = g 2 t , t = 0, · · · , T − 1, then we have
βt ≥ (
β0 β0 +G2/l
)2( β0 + 1
l t−1∑ i=0 g2i
) , t = 1, · · · , T (28)
and T−1∑ t=0 g2t βt+1 ≤ l ( β0 +G 2/l β0 )2 ln ( 1 + ∑T−1 t=0 g 2 t lβ0 ) . (29)
Meanwhile, if βtψ(βt+1/βt) = g2t , t = 0, · · · , T − 1, then we have
βt ≥ β0 + 1
l t−1∑ i=0 g2i , t = 1, · · · , T (30)
and T−1∑ t=0 g2t βt+1 ≤ l ln ( 1 + ∑T−1 t=0 g 2 t lβ0 ) . (31)
Proof. Using same methods in proof of Lemma 12 and 13, the conclusion can be deduced from Lemma 18 easily.
proof of Theorem 17. Like Lemma 11, in strongly convex case, we have 2R(T ) = 2 T−1∑ t=0 ft(xt)− ft(x∗)
≤ 2 T−1∑ t=0 〈gt,xt − x∗〉 − T−1∑ t=0 ‖xt − x∗‖2diag(µ)
= T−1∑ t=0 ‖gt‖2diag(βt+1)−1 + T−1∑ t=0 ( ‖xt − x∗‖2diag(βt+1) − ‖xt+1 − x ∗‖2diag(βt+1) ) − T−1∑ t=0 ‖xt − x∗‖2diag(µ)
≤ T−1∑ t=0 ‖gt‖2diag(βt+1)−1 + T−1∑ t=0 ‖xt − x∗‖2diag(βt+1−βt−µ) + ‖x0 − x ∗‖2diag(β0).
Note that in Algorithm 4,
βt+1,j − βt,j = βt,j(βt+1,j/βt,j − 1) ≤ βt,j α ϕ′ ( βt+1,j βt,j ) = β2t,j β2t+1,j g2t,j λα ≤ G 2 λα
holds, and in Algorithm 5, same conclusion holds: βt+1,j − βt,j = βt,j(βt+1,j/βt,j − 1)
≤ βt,j α ϕ′ ( βt+1,j βt,j ) = g2t,j λα ≤ G 2 λα .
Hence, if λ ≥ maxj=1:d G 2
αµj , then βt+1 − βt ≤ µ, and T−1∑ t=0 ‖xt − x∗‖2diag(βt+1−βt−µ) ≤ 0.
On the other hand, T−1∑ t=0 ‖gt‖2diag(βt+1)−1 = d∑ j=1 T−1∑ t=0 g2t,j βt+1,j ,
following from Lemma 19, we have T−1∑ t=0 ‖gt‖2diag(βt+1)−1 ≤ l ( 1 + G2 λlβ0 )2 d∑ j=1 ln ( 1 + ‖g0:T−1,j‖22 λlβ0 ) in Algorithm 4,
T−1∑ t=0 ‖gt‖2diag(βt+1)−1 ≤ l d∑ j=1 ln
( 1 + ‖g0:T−1,j‖22
λlβ0
) in Algorithm 5.

heading: I CONVERGENCE RATES IN FULL BATCH SETTING
text: In this section, we will discuss the convergence of our methods in full batch settings.
We first review a classical result on the convergence rate for gradient descent with fixed learning rate. Theorem 20. Suppose that F ∈ C1,1L (Rd) and F ∗ = infxF (x) > −∞. Consider gradient descent with constant step size, xt+1 = xt − ∇F (xt)b . If b > L 2 , then
min 0≤t≤T−1
‖∇F (xt)‖22 ≤ ε
after at most a number of steps
T = 2b2(F (x0)− F ∗)
ε(2b− L) = O
( 1
ε ) Proof. Following from the fact that F is L-smooth, we have
F (xt+1) ≤F (xt) +∇F (xt)>(xt+1 − xt) + L
2 ‖xt+1 − xt‖22
=F (xt)− 1
b ‖∇F (xt)‖22 +
L
2b2 ‖∇F (xt)‖22
=F (xt)− 1
b
( 1− L
2b
) ‖∇F (xt)‖22 . (32)
When b > L2 , 1− L 2b > 0. So
T−1∑ t=0 ‖∇F (xt)‖22 ≤ 2b2 2b− L (F (x0)− F (xT )) ≤ 2b2 2b− L (F (x0)− F ∗),
and
min 0≤t≤T−1
‖∇F (xt)‖22 ≤ 1
T T−1∑ t=0 ‖∇F (xt)‖22 ≤ 2b2 T (2b− L) (F (x0)− F ∗) ≤ ε.
Remark. If we choose b ≤ L2 , then convergence of gradient descent with constant learning rate is not guaranteed at all.
Like Algorithm 3, another update rule is worth considering in full batch setting:{ xt+1 = xt − 1βt gt, βt+1 = βt(ϕ ′)−1(‖gt‖22 /β2t ) (33)
Next we will show that both update rules (13) and (14) are robust to the choice of initial learning rate. Our proof is followed from the proof of Theorem 2.3 in WNGrad (Wu et al., 2018). Note that in update rule (13), βt+1 satisfies
β2t+1ϕ ′(βt+1/βt) = ‖gt‖22 ,
while in update rule (14) and (33), βt+1 satisfies
β2t ϕ ′(βt+1/βt) = ‖gt‖22 .
Theorem 21 (Convergence rate of update rule (13)). Suppose that ϕ ∈ C1,1l ([1,+∞)), ϕ is αstrongly convex, and F ∈ C1,1L (Rd), F ∗ = infx F (x) > −∞. For any ε ∈ (0, 1), the sequence {xt} obtained from update rule (13) satisfies
min j=0:T−1
‖∇F (xj)‖22 ≤ ε,
after T steps, where
T =  1 + ⌈ 2(β0+2(F (x0)−F∗)/α)(F (x0)−F∗) ε ⌉ if β0 ≥ L or β1 ≥ L, 1 + ⌈ log( Lβ0 )
log( ε lL2 +1)
⌉ + ⌈( L+(1+ 2α ) ( F (x0)−F∗+ lL(L−β0)2β0 ))2 ε ⌉ otherwise.
Theorem 22 (Convergence rate of update rule (14)). Suppose that ϕ ∈ C1,1l ([1,+∞)), ϕ is αstrongly convex, and F ∈ C1,1L (Rd), F ∗ = infx F (x) > −∞. For any ε ∈ (0, 1), the sequence {xt} obtained from update rule (14) satisfies
min j=0:T−1
‖∇F (xj)‖22 ≤ ε
after T steps, where
T =  1 + ⌈ 2(β0+‖g0‖22/(αβ0)+2(F (x0)−F ∗)/α)(F (x0)−F∗) ε ⌉ if β0 ≥ L or β1 ≥ L, 1 + ⌈ log( Lβ0 )
log( ε lL2 +1)
⌉ + ⌈( L+ 2lαβ0 L2+ 2lα L+(1+ 8 α ) ( F (x0)−F∗+ lL(L−β0)2β0 ))2 ε ⌉ otherwise.
Theorem 23 (Convergence rate of update rule (33)). Suppose that ϕ ∈ C1,1l ([1,+∞)), ϕ is αstrongly convex, and F ∈ C1,1L (Rd), F ∗ = infx F (x) > −∞. For any ε ∈ (0, 1), the sequence {xt} obtained from update rule (33) satisfies
min j=0:T−1
‖∇F (xj)‖22 ≤ ε
after T steps, where
T =  1 + ⌈ 2(β0+2(F (x0)−F∗)/α)(F (x0)−F∗) ε ⌉ if β0 ≥ L, 2 +  ( β0+ ‖g0‖ 2 2 αβ0 +(1+ 2α ) ( F (x0)−F∗+ lL‖g0‖ 2 2 2αβ20 ))2 ε  if β0 < L, β1 ≥ L, 1 + ⌈ log( Lβ0 )
log( ε lL2 +1)
⌉ + ⌈( (1+ 2lα )L+ 2lL2 αβ0 +(1+ 2α ) ( F (x0)−F∗+ lL2β0 ( (1+ 2lα )L+ 2lL2 αβ0 −β0 )))2 ε ⌉ otherwise.
We begin our proof by following lemma.
Lemma 24. Suppose ϕ ∈ C1,1l (R++). Fix ε ∈ (0, 1]. In both update rules (13) and (14), after
T =
⌈ log( Lβ0 )
log( ε lL2 +1)
⌉ + 1 steps, either mint=0:T−1 ‖gt‖22 ≤ ε, or βT ≥ L holds.
Proof. Assume that βT < L and mint=0:T−1 ‖gt‖22 > ε. Recall that the sequence {βt} is an increasing sequence. Hence, βt < L for 0 ≤ t ≤ T . So, for all 0 ≤ t ≤ T − 1,
ϕ′ ( βt+1 βt ) = ‖gt‖22 β2t+1 > ε L2 (in Algorithm 1),
ϕ′ ( βt+1 βt ) = ‖gt‖22 β2t > ε L2 (in Algorithm 2).
Note that ϕ is a l-smooth convex function, and βt+1/βt ≥ 1. So ϕ′ ( βt+1 βt ) ≤ l ( βt+1 βt − 1 ) , (34)
then βt+1 βt > ε lL2 + 1.
In this case,
L > βT = β0 ( ε lL2 + 1 )T
holds but it is impossible according to the setting of T in the lemma.
We first prove Theorem 21 using following lemma.
Lemma 25. In update rule (13), suppose F ∈ C1,1L (Rd), ϕ ∈ C 1,1 l (R++), and ϕ is α-strongly convex function. Denote F ∗ = infx F (x) > −∞. Let t0 ≥ 1 be the first index such that βt0 ≥ L. Then for all t ≥ t0,
βt ≤ βt0−1 + 2
α (F (xt0−1)− F ∗), (35)
and moreover,
F (xt0−1)− F ∗ ≤ F (x0)− F ∗ + Ll
2β0 (βt0−1 − β0) (36)
Proof. Same as equation (32),
F (xt+1) ≤ F (xt)− 1
βt+1
( 1− L
2βt+1
) ‖gt‖22 .
For t ≥ t0 − 1, βt+1 ≥ L, so
F (xt+1) ≤ F (xt)− 1
2βt+1 ‖gt‖22 .
Hence, for all k ≥ 0,
F (xt0+k) ≤ F (xt0−1)− 1
2 k∑ i=0 ‖gt0+i−1‖ 2 2 βt0+i , (37)
i.e., k∑ i=0 ‖gt0+i−1‖ 2 2 βt0+i ≤ 2(F (xt0−1)− F ∗). (38)
Note that ϕ is α-strongly convex and β2t+1ϕ ′(βt+1/βt) = ‖gt‖22. So
‖gt‖22 βt+1 = βt+1ϕ ′ ( βt+1 βt ) ≥ αβt ( βt+1 βt − 1 ) ,
and
βt+1 − βt ≤ 1
α ‖gt‖22 βt+1 . (39)
Combining equation (38) and equation (39), we have
βt0+k ≤ βt0−1 + 1
α k∑ i=0 ‖gt0+i−1‖ 2 2 βt0+i
≤ βt0−1 + 2
α (F (xt0−1)− F ∗).
We remain to give an a upper bound for F (xt0−1) in the case t0 > 1. Using equation (32) again, we get
F (xt0−1)− F (x0) ≤ t0−2∑ i=0 − 1 βi+1 ( 1− L 2βi+1 ) ‖gi‖22 ≤ L 2 t0−2∑ i=0 ‖gi‖22 β2i+1
= L
2 t0−2∑ i=0 ϕ′ ( βi+1 βi ) ≤ Ll 2 t0−2∑ i=0 ( βi+1 βi − 1 )
≤ Ll 2 t0−2∑ i=0 ( βi+1 − βi β0 ) = Ll 2β0 (βt0−1 − β0).
In the above, the second inequality follows from the assumed l-smoothness of ϕ, and the last inequality follows from βt ≥ β0 for all t ≥ 0.
proof of Theorem 21. If t0 = 1, by equation (37), for all t ≥ 1, we have
F (xt) ≤ F (x0)− 1
2 t−1∑ i=0 ‖gi‖22 βi+1
≤ F (x0)− 1
2 t−1∑ i=0 ‖gi‖22 β0 + 2 α (F (x0)− F ∗) .
Then after T = 1 + ⌈
2(β0+2(F (x0)−F∗)/α)(F (x0)−F∗) ε
⌉ steps,
min t=0:T−1
‖gt‖22 ≤ 1
T T−1∑ t=0 ‖gt‖22
≤ 2 T (F (x0)− F ∗)(β0 + 2 α (F (x0)− F ∗)) ≤ ε.
Otherwise, if t0 > 1, we have βt0−1 < L. Then for all t ≥ t0,
βt ≤ L+ 2
α
( F (x0)− F ∗ +
lL(L− β0) 2β0
) (40)
Denote the right hand of equation (40) as βmax. Using equation (37) again, for we have
F (xt0+M ) ≤ F (xt0−1)− 1
2 M∑ i=0 ‖gt0+i−1‖ 2 2 βt0+i
≤ F (xt0−1)− 1
2βmax M∑ i=0 ‖gt0+i−1‖ 2 2 .
Hence,
min t=0:t0+M−1 ‖gt‖22 ≤ mint=t0−1:t0+M−1 ‖gt‖22
≤ 1 M + 1 M∑ i=0 ‖gt0+i−1‖ 2 2
≤ 1 M + 1 2βmax(F (xt0−1)− F ∗)
≤ 2βmax M + 1
( F (x0)− F ∗ +
lL(L− β0) 2β0
) .
At last, with recalling the conclusion of Lemma 24, after
T =
⌈ log( Lβ0 )
log( εlL2 + 1)
⌉ + ⌈ 2βmax ε ( F (x0)− F ∗ + lL(L− β0) 2β0 )⌉ + 1
steps, we have mint=0:T−1 ‖gt‖22 ≤ ε.
Next we prove Theorem 22.
Lemma 26. In update rule (14), suppose F ∈ C1,1L (Rd), ϕ ∈ C 1,1 l (R++), and ϕ is α-strongly convex function. Denote F ∗ = infx F (x). Let t0 ≥ 1 be the first index such that βt0 ≥ L. Then for all t ≥ t0,
βt ≤ βt0 + 8
α (F (xt0−1)− F ∗), (41)
and moreover,
F (xt0−1)− F ∗ ≤ F (x0)− F ∗ + Ll
2β0 (βt0−1 − β0), (42)
βt0 ≤
{ β0 + ‖g0‖22 αβ0
if t0 = 1, L+ 2lαβ0L 2 + 2lαL if t0 ≥ 2, (43)
Proof. Same as the proof of Lemma 25, we first get for all k ≥ 0, k∑ i=0 ‖gt0+i−1‖ 2 2 βt0+i ≤ 2(F (xt0−1)− F ∗).
Note that in update rule (14), β2t ϕ ′ (βt+1/βt) = ‖gt‖22. So
βt0+k+1 = βt0+k + βt0+k ( βt0+k+1 βt0+k − 1 )
≤ βt0+k + βt0+k α ϕ′ ( βt0+k+1 βt0+k ) = βt0+k + 1 α ‖gt0+k‖ 2 2 βt0+k
≤ βt0+k + 2
α
‖gt0+k − gt0+k−1‖ 2 2 + ‖gt0+k−1‖ 2 2
βt0+k
≤ βt0+k + 2
α
L2 ‖xt0+k − xt0+k−1‖ 2 2 + ‖gt0+k−1‖ 2 2
βt0+k
≤ βt0+k + 2
α
L2 ‖gt0+k−1‖ 2 2
β3t0+k +
2
α
‖gt0+k−1‖ 2 2
βt0+k
≤ βt0+k + 4
α
‖gt0+k−1‖ 2 2
βt0+k ≤ βt0 +
4
α k∑ i=0 ‖gt0+i−1‖ 2 2 βt0+i
≤ βt0 + 8
α (F (xt0−1)− F ∗).
If t0 = 1, then
βt0 ≤ β0 + ‖g0‖22 αβ0 ,
and if t0 ≥ 2, then
βt0 ≤ βt0−1 + ‖gt0−1‖ 2 2
αβt0−1
= βt0−1 + 2L2
α
‖gt0−2‖ 2 2
β3t0−1 +
2
α
‖gt0−2‖ 2 2
βt0−2
≤ βt0−1 + 2L2
α l(βt0−1 − βt0−2)βt0−2 β3t0−1 + 2 α l(βt0−1 − βt0−2)
≤ L+ 2l αβ0 L2 + 2l α L.
At last, for t0 > 0, we have
F (xt0−1)− F (x0) ≤ t0−2∑ i=0 − 1 βi+1 ( 1− L 2βi+1 ) ‖gi‖22
≤ L 2 t0−2∑ i=0 ‖gi‖22 β2i+1 ≤ L 2 t0−2∑ i=0 ‖gi‖22 β2i
= L
2 t0−2∑ i=0 ϕ′ ( βi+1 βi ) ≤ Ll 2 t0−2∑ i=0 ( βi+1 βi − 1 )
≤ Ll 2 t0−2∑ i=0 ( βi+1 − βi β0 ) = Ll 2β0 (βt0−1 − β0).
proof of Theorem 22. The proof is completely similar to the proof of Theorem 21.
Next, we prove Theorem 23.
Lemma 27. In update rule (33), suppose F ∈ C1,1L (Rd), ϕ ∈ C 1,1 l (R++), and ϕ is α-strongly convex function. Denote F ∗ = infx F (x). Let t0 ≥ 0 be the first index such that βt0 ≥ L. Then for all t ≥ t0,
βt ≤ βt0 + 2
α (F (xt0)− F ∗), (44)
and moreover,
F (xt0)− F ∗ ≤ F (x0)− F ∗ + Ll
2β0 (βt0 − β0), (45)
βt0 ≤
{ β0 + ‖g0‖22 αβ0
, if t0 ≥ 1,( 1 + 2lα ) L+ 2lαβ0L 2, if t0 ≥ 2. (46)
Proof. Same as the proof of Lemma 25, we first get
F (xt0+k+1) ≤ F (xt0+k)− 1
βt0+k
( 1− L
2βt0+k
) ‖gt0+k‖ 2 2
≤ F (xt0+k)− 1
2βt0+k ‖gt0+k‖ 2 2
≤ F (xt0)− 1
2 k∑ i=0 ‖gt0+i‖ 2 2 βt0+i ,
and k∑ i=0 ‖gt0+i‖ 2 2 βt0+i ≤ 2(F (xt0)− F ∗).
Note that in Algorithm 2, β2t ϕ ′ (βt+1/βt) = ‖gt‖22. So
βt0+k+1 = βt0+k + βt0+k ( βt0+k+1 βt0+k − 1 )
≤ βt0+k + βt0+k α ϕ′ ( βt0+k+1 βt0+k ) = βt0+k + 1
α
‖gt0+k‖ 2 2
βt0+k
≤ βt0 + 1
α k∑ i=0 ‖gt0+i‖ 2 2 βt0+i
≤ βt0 + 2
α (F (xt0)− F ∗).
At last, for t0 > 0, we have
F (xt0)− F (x0) ≤ L
2 t0−1∑ i=0 ‖gi‖22 β2i
= L
2 t0−1∑ i=0 ϕ′ ( βi+1 βi ) ≤ Ll
2β0 (βt0 − β0).
Recall that
αβt(βt+1 − βt) ≤ ‖gt‖22 ≤ lβt(βt+1 − βt). So if t0 = 1,
βt0 ≤ β0 + ‖g0‖22 αβ0 .
And if t0 ≥ 2, we have
βt0 ≤ βt0−1 + ‖gt0−1‖ 2 2
αβt0−1
≤ βt0−1 + 2 ‖gt0−1 − gt0−2‖ 2 2 + ‖gt0−2‖ 2 2
αβt0−1
≤ βt0−1 + 2L2
α
‖xt0−1 − xt0−2‖ 2 2
βt0−1 +
2
α
‖gt0−2‖ 2 2
βt0−2
= βt0−1 + 2L2
α
‖gt0−2‖ 2 2
β2t0−2βt0−1 +
2
α
‖gt0−2‖ 2 2
βt0−2
≤ βt0−1 + 2L2
α l(βt0−1 − βt0−2) βt0−2βt0−1 + 2 α l(βt0−1 − βt0−2)
≤ L+ 2l αβ0 L2 + 2l α L.
proof of Theorem 23. The proof is completely similar to the proof of Theorem 21.

Review summaries:
This paper presents a method for adaptively tuning the learning rate in gradient descent methods. The authors consider the formulation of each gradient descent update as a quadratic minimization problem and they propose adding a phi-divergence between the learning rate that would be used and an auxiliary vector. The authors also propose adding a maximization over all learning rates in the update.