Title: HYPER-REGULARIZATION: A FRAMEWORK OF ADAP-TIVE CHOICE FOR THE LEARNING RATE IN GRADIENT DESCENT Anonymous

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.

1. INTRODUCTION:

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 Hyper-Regularization. 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.

1.1. RELATED WORK:

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, Hyper-Gradient 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.

1.2. NOTATION:

Before introducing our approach, we present the notation. We denote the set {x > 0 : x ∈ R} by R ++ . For two vectors a, b ∈ R d , we use a/b to denote element-wise division, a • b for elementwise product (the symbol • will be omitted in the explicit context), a n = (a n 1 , a n 2 , . . . , a n d ), and a ≥ b if a j ≥ b j 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 ⊆ R d , a function f : X → R is said to satisfy f ∈ C 1,1 L (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) .

1.3. PROBLEM STATEMENT:

For an online learning problem, a learner faces a sequence of convex functions {f t } with the same domain X ⊆ R d , receives (sub)gradient information g t ∈ ∂f t (x t ) at each step t, and predicts a point x t+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., f t = F . In this setting we assume F ∈ C1,1 L 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 (x t ) 2 2 ≤ ε.

In online learning settings, our analysis follows from Duchi et al. (2011) and Kingma & Ba (2015) . We only assume that f t 's are convex and try to give an upper bound for the regret

R(T ) = T -1 t=0 f t (x t ) -min x∈X T -1 t=0 f t (x).

(1)

2. HYPER-REGULARIZATION:

Following the setting in AdaGrad (Duchi et al., 2011) , we consider a generalization of the standard (sub)gradient descent as

x t+1 = Π diag(βt) 1/2 X x t -diag(β t ) -1/2 g t = arg min x∈X x t -diag(β t ) -1/2 g t 2 diag(βt) 1/2 . (2)

This procedure can be viewed as the minimization problem:

EQUATION

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

EQUATION

where D(β, η) is defined as our hyper-regularizer and B t is a subset in R d . 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 ϕ-divergence 1 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 ϕ : R d ++ × R d ++ → R, which is define by D ϕ (u, v) d j=1 v j ϕ(u j /v j ),

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 ∈ R d ++ , 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 lim z→+∞ ϕ (z) = +∞.

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

EQUATION

EQUATION

)

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.

2.2. MAX-MIN OR MIN-MAX:

Consider a problem similar to (5), min

EQUATION

)

The solution of problem ( 5) is same as (7) in unconstrained case2 , i.e.

X = R d , B t = R d ++ . However, if we set B t = [b t,1 , B t,1 ] × • • • × [b t,d , B t,d ]

to constrain the range of β t+1 and suppose X = R d , 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 B t = [b t,1 , B t,1 ] × • • • × [b t,d , B t,d ], and X = R d . Let β * be the solution of unconstrained problem max β (min x Ψ t (x, β)). Then the solution of problem max β∈Bt (min x Ψ t (x, β)) is β j = min{max{β * j , b t,j }, B t,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 + 1 1, 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.

2.4. ISOTROPIC HYPER-REGULARIZATION:

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 B t ⊆ {θ1 : θ ∈ R ++ } of all positive multiples of the vector 1 ∈ R d . Let η t = η t 1, and rewrite problem (5) as

EQUATION

We prefer to use Isotropic Hyper-Regularization as smoothing technique in online learning settings.

3. UPDATE RULES AND ALGORITHMS:

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,

EQUATION

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 x t+1 and new learning rate β t+1 such that β 2 t+1,j ϕ (β t+1,j /η t,j ) = g 2 t,j , j = 1, . . . , d, (10)

x t+1 = x t -g t /β t+1 .

Algorithm 1 GD with Hyper-regularization Input:

β 0 > 0, x 0 1: for t = 1 to T do 2:

Suffer loss f t (x t );

3:

Receive subgradient g t ∈ ∂f t (x t ) of f t at x t ;

4:

Update β t+1,j as the solution of the equation β 2 ϕ (β/η t,j ) = g 2 t,j , j = 1, . . . , d;

5::

Update x t+1 = x t -g t /β 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 + 1

z -2, then we can derive AdaGrad from Algorithm 1.

• If ϕ(z) = 1 z -log( 1 z )

-1, then we can derive WNGrad from Algorithm 1.

3.1. ALTERNATING UPDATE RULE:

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

EQUATION

and update the new predictor x t+1 using

x t+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 x t+1 and new learning rate β t+1 as β t+1,j = η t,j (ϕ ) -1 (g 2 t,j /η 2 t,j ), j = 1, . . . , d,

x t+1 = x t -g t /β t+1 .

Algorithm 2 GD with Hyper-regularization using alternating update rule Input: β 0 > 0, x 0 1: for t = 1 to T do 2:

Suffer loss f t (x t );

3: Receive g t ∈ ∂f t (x t ) of f t at x t ; 4:

Update β t+1,j = η t,j (ϕ ) -1 (g 2 t,j /η 2 t,j ), j = 1, . . . , d;

Update x t+1 = x t -g t /β 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:

x t+1 = arg min x∈X Ψ t (x, β t ), β t+1 = arg max β∈Bt Ψ t (x t+1 , β) .

We leave the corresponding algorithm 3 in Appendix C.

3.2. MONOTONICITY:

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 .

4. THEORETICAL ANALYSIS:

In this section we always set η t = β t and assume that x and β are unconstrained, i.e., X = R d and B t = R d ++ . 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.

4.1. ISOTROPIC HYPER-REGULARIZATION IN FULL BATCH SETTING:

Recall that we set f t = F in the full batch setting, and assume that F ∈ C 1,1 L without convexity. In this case, two update rules can be written as

β 2 t+1 ϕ (β t+1 /β t ) = g t 2 2 , x t+1 = x t -1 βt+1 g t .

(13)

EQUATION

Next we show that both update rules ( 13) and ( 14) are robust to the choice of initial learning rate.

Theorem 6. Suppose that ϕ ∈ C 1,1 l ([1, +∞)), ϕ is α-strongly convex, F ∈ C 1,1 L (R d ), and F * = inf x F (x) > -∞.

For any ε ∈ (0, 1), the sequence {x t } obtained from update rules ( 13) or ( 14) satisfies

min j=0:T -1 ∇F (x j ) 2 2 ≤ ε, 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 as O(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.

4.2. HYPER-REGULARIZATION IN ONLINE LEARNING SETTING:

We now establish the result of convergence rate for Algorithms 1 and 2 in online convex learning, i.e., the f t are convex. Especially, we try to bound regrets (1) by O( √ T ) for Algorithms 1 and 2.

Theorem 7. Suppose that ϕ ∈ C 1,1 l ([1, +∞)), and ϕ is α-strongly convex. Assume that g t ∞ ≤ G, and x t -x * ∞ ≤ D ∞ . Then the sequence {x t } obtained from Algorithm 1 satisfies 2R(T ) ≤ (α + D 2 ∞ ) 2lβ 2 0 + 4G 2 αβ 0 d j=1 g 0:T -1,j 2 + β 0 x 0 -x * 2 2 ,

and the sequence {x t } obtained from Algorithm 2 (or 3) satisfies

2R(T ) ≤ 1 + D 2 ∞ α max √ 2l, 2G β 0 d j=1 g 0:T -1,j 2 + β 0 x 0 -x * 2 2 .

Note that under the assumption in Theorem 7,

d j=1 g 0: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) .

5. EXPERIMENTS:

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.

5.1. THE SET-UP:

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 B t 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 10 1 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.

5.2. UPDATE RULE SELECTION:

Taking the RKL algorithm as an example, we refer to algorithms deduced from Algorithm 1, 2, and 3 as RKL 1 , RKL 2 , and RKL 3 . 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 . 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.

5.3. FULL BATCH SETTING AND ONLINE LEARNING SETTING:

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

6. DISCUSSION:

As a supplement, we point out that logarithmic regret bounds under assumption f t 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.

A SOLUTION EXISTENCE:

Note that the function h(β) = β 2 ϕ (β/η t,j ) is an increasing continuous function and lim z→+∞ ϕ (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.

B SPECIAL CASES OF ALGORITHM 1:

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 + 1 z -2, then the new learning rate β t+1 can be obtained by

β 2 t+1,j 1 - β 2 t,j β 2 t+1,j = g 2 t,j , j = 1, • • • , d,

that implies,

β 2 t+1 = β 2 t + g 2 t ,

and we drive AdaGrad from Hyper-Regularization.

Similarly, we can get WNGrad by setting ϕ(z) = 1 z -log 1 z -1. In fact, β t+1 employs update

β 2 t+1,j β t,j (β t+1,j -β t,j ) β 2 t+1,j = g 2 t,j , j = 1, • • • , d,

on the other words,

β t+1 = β t + g 2 t β t ,

i.e., the update rule of WNGrad.

C SIMPLIFIED ALTERNATING UPDATE RULE:

Algorithm 3 GD with Hyper-regularization using simplified alternating update rule and η t = β t Input:

β 0 > 0, x 0 1: for t = 1 to T do 2:

Suffer loss f t (x t );

3: Receive g t ∈ ∂f t (x t ) of f t at x t ; 4: Update x t+1 = x t -g t /β t ; 5: Update β t+1,j = β t,j (ϕ ) -1 (g 2 t,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 x t+1 by β t which is unrelated to current gradient g t . The regret bound of Algorithm 3 has been shown in Theorem 7.

D SUPPLEMENTARY FOR NUMERICAL EXPERIMENTS:

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:

KL 1 β 2 t+1 log(β t+1 /β t ) = g 2 t x t+1 = x t -g t /β t+1 KL 2 β t+1 = β t exp(g 2 t /β 2 t ) x t+1 = x t -g t /β t+1 KL 3 x t+1 = x t -g t /β t β t+1 = β t exp(g 2 t /β 2 t ) RKL 1 β t+1 = 1 2 β t + β 2 t + 4g 2 t x t+1 = x t -g t /β t+1 RKL 2 β t+1 = β 3 t /(β 2 t -g 2 t ) x t+1 = x t -g t /β t+1 RKL 3 x t+1 = x t -g t /β t β t+1 = β 3 t /(β 2 t -g 2 t ) H 1 β 2 t+1 (1 -β t /β t+1 ) = g 2 t x t+1 = x t -g t /β t+1 H 2 β t+1 = β 5 t /(β 2 t -g 2 t ) 2 x t+1 = x t -g t /β t+1 H 3 x t+1 = x t -g t /β t β t+1 = β 5 t /(β 2 t -g 2 t ) 2 χ 2 1 2β 2 t+1 (β t+1 /βt -1) = g 2 t x t+1 = x t -g t /β t+1 χ 2 2 β t+1 = β t 1 + g 2 t /(2β 2 t ) x t+1 = x t -g t /β t+1 χ 2 3 x t+1 = x t -g t /β t β t+1 = β t 1 + g 2 t /(2β 2 t ) D.2 VERSION COMPARISON ON OTHER ALGORITHMS

Test Accuracy:

Figure 6 : Convergence performances of χ 2 2 and χ 2 3 on the database of MNIST in online learning setting, up:at different initial learning rates, and down:the whole training process with the given initial learning rate in the bracket.

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 β 0 s 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 . 

E PROOF OF LEMMA 2:

Proof. First, it is trivial to get

Ψ t,x (β) min x Ψ t (x, β) = Ψ t x t - g t β , β = - 1 2 g t 2 diag(β) -1 - 1 2 D ϕ (β, η t ) = - 1 2 d j=1 g 2 t,j β j + η t,j ϕ β j η t,j .

The partial derivative of Ψ t,x (β) with respect to β j is

∂Ψ t,x (β) ∂β j = 1 2 g 2 t,j β 2 j -ϕ β j η t,j .

Note that ϕ is a convex function, so ϕ is a non-decreasing function, and ≥ 0. Thus, Ψ t,x (β) with respect to β j is a nondecreasing function, and arg max βj Ψ t,x (β) = B t,j . For a similar reason, if β * j < b t,j , then arg max βj Ψ t,x (β) = b t,j . In conclusion,

arg max βj ∈[bt,j ,Bt,j ] Ψ t,x (β) = min{max{β * j , b t,j }, B t,j }, for j = 1, • • • , d.

F PROOF OF LEMMA 5:

In this section, we denote that Ψ t,x (β) = min x∈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 -x t ) + β 2 x -x t 2 2 - 1 2 D ϕ (β, η t ) < g t (x -x t ) + η t 2 x -x t 2 2 = Ψ t (x, η t ).

Hence, min x∈X Ψ t (x, β) < min x∈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 min x Ψ(x, η t ). If β < η t , then

Ψ t (y, β) = g t (y -x t ) + β 2 y -x t 2 2 - 1 2 D ϕ (β, η t ) < g t (y -x t ) + η t 2 y -x t 2 2 = Ψ t (y, η t ).

Hence β t+1 = arg max β∈B Ψ t (y, β) ≥ η t .

G CONVERGENCE RATES IN ONLINE LEARNING SETTING:

Recall the define of regret

EQUATION

where x * = arg min x∈X T -1 t=0 f t (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 {a i } and its vector representation

EQUATION

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 a 2 t a 1:t 2 ≤ 2 a 1:T -1 2 + a 2 T a 1:T 2 .

We denote b T = T t=1 a 2 t and have

2 a 1:T -1 2 + a 2 T a 1:T 2 = 2 b T -a 2 T + a 2 T √ b T ≤ 2 b T -a 2 T + a 4 T 4b T + a 2 T √ b T = 2 b T .

Lemma 11. Suppose the sequence {x t } and sequence {β t } satisfy x t+1 = x t -g t /β t+1 . Then the regret satisfies

2R(T ) ≤ T -1 t=0 g t 2 diag(βt+1) -1 + T -1 t=0 x t -x * 2 diag(βt+1-βt) + x 0 -x * 2 diag(β0)

Proof. Note that

EQUATION

EQUATION

)

Hence

2R(T ) = 2 T -1 t=0 (f t (x t ) -f t (x * )) ≤ 2 T -1 t=0 g t (x t -x * ) = T -1 t=0 g t 2 diag(βt+1) -1 + T -1 t=0 x t -x * 2 diag(βt+1) -x t+1 -x * 2 diag(βt+1) ≤ T -1 t=0 g t 2 diag(βt+1) -1 + T -1 t=0 x t -x * 2 diag(βt+1-βt) + x 0 -x * 2 diag(β0) .

Lemma 12. Suppose an increasing function ψ satisfies ψ(1) = 0 and ψ(x) ≤ l(x -1). Consider a real valued sequence {g t } t=0:T -1 and a positive sequence {β t } t=0:T which satisfies

EQUATION

where c =

EQUATION

)

Remark. We point out that

• β t+1 ≥ β t (If β t+1 < β t , then β 2 t+1 ψ(β t+1 /β t ) < 0 ≤ g 2 t ),

• β t+1 is unique with respect to β t due to the fact that the function

EQUATION

)

Define a cubic polynomial

h(β) = l β t β 3 -lβ 2 -g 2 t ,

and h is an increasing function when β ≥ β t .

If h c β 2 0 + 2 l t i=0 g 2 i ≤ 0, according to h(β t+1 ) ≥ 0, then β t+1 ≥ c β 2 0 + 2 l t i=0 g 2 i . Denote b = β 2 0 + 2 l t-1 i=0 g 2 i . So we just need to choose c such that h   c β 2 0 + 2 l t i=0 g 2 i   ≤ lc 2 (b + 2g 2 t /l) b + 2g 2 t /l √ b -1 -g 2 t ≤ 0,

where the first inequality holds for the assumption

β t ≥ c β 2 0 + 2 l t-1 i=0 g 2 i , or c 2 √ b (b + 2g 2 t /l) 2g 2 t /l b + 2g 2 t /l + √ b ≤ g 2 t /l, or 2c 2 √ b (b + 2g 2 t /l) ≤ b + 2g 2 t /l + √ b.

Thus, c just need to satisfy

c 2 ≤ b b + 2g 2 t /l . According to b ≥ β 2 0 , g 2 t ≤ G 2 , hence b b + 2g 2 t /l ≥ β 2 0 β 2 0 + 2G 2 /l . So if we choose c = β 2 0 β 2 0 +2G 2 /l , then β 1 > β 0 > cβ 0 , hence β t ≥ c β 2 0 + 2 l t-1 i=0 g 2 i , t = 1, • • • , T.

Moreover, following from Lemma 10, we have

T -1 t=0 g 2 t β t+1 ≤ T -1 t=0 g 2 t c 2/l t i=0 g 2 i ≤ √ 2l c T -1 t=0 g 2 t .

Lemma 13. Suppose an increasing function ψ satisfies ψ(1) = 0 and ψ(x) ≤ l(x -1). Consider a real valued sequence {g t } t=0:T -1 and a positive sequence {β t } t=0:T which satisfies

|g t | ≤ G, β 2 t ψ βt+1 βt = g 2 t , t = 0, • • • , T -1, β 0 ≥ 0.

We can bound β T as

EQUATION

Moreover, we have

EQUATION

)

Proof. Same as inequality (20), we have

lβ 2 t β t+1 β t -1 ≥ g 2 t ,

hence

β 2 t+1 = β t + g 2 t lβ t 2 ≥ β 2 t + 2 l g 2 t ≥ β 2 0 + 2 l t i=0 g 2 t ≥ min 1, lβ 2 0 2G 2 2 l t+1 i=0 g 2 i , .

Furthermore, following from Lemma 10, we have

T -1 t=0 g 2 t β t ≤ l/2 min{1, lβ 2 0 /(2G 2 )} T -1 t=0 g 2 t t i=0 g 2 i ≤ max √ 2l, 2G β 0 T -1 t=0 g 2 t .

Theorem 14. Suppose that ϕ ∈ C 1,1 l ([1, +∞)), and ϕ is α-strongly convex. Assume that g t ∞ ≤ G, and

x t -x * ∞ ≤ D ∞ .

Then the sequence {x t } obtained from Algorithm 1 satisfies

2R(T ) ≤ (α + D 2 ∞ ) 2lβ 2 0 + 4G 2 αβ 0 d j=1 g 0:T -1,j 2 + β 0 x 0 -x * 2 2 ,

Proof. Following from Lemma 11,

2R(T ) ≤ T -1 t=0 g t 2 diag(βt+1) -1 + T -1 t=0 x t -x * 2 diag(βt+1-βt) + x 0 -x * 2 diag(β0) ≤ T -1 t=0 g t 2 diag(βt+1) -1 + T -1 t=0 x t -x * 2 ∞ β t+1 -β t 1 + x 0 -x * 2 diag(β0) ≤ T -1 t=0 d j=1 g 2 t,j β t+1,j + max 0≤t<T x t -x * 2 ∞ T -1 t=0 d j=1 (β t+1,j -β t,j ) + x 0 -x * 2 diag(β0) .

Recall ϕ is a α-strongly convex function, so,

EQUATION

EQUATION

The function ψ = ϕ satisfies ψ(1) = 0 and ψ(x) ≤ l(x -1) according to the smoothness of ϕ.

Following from Lemma 12, we have

EQUATION

)

Combining inequality ( 23) and ( 24), we have

2R(T ) ≤ 1 + max 0≤t<T x t -x * 2 ∞ α d j=1 T -1 t=0 g 2 t,j β t+1,j + x 0 -x * 2 diag(β0) ≤ (1 + D 2 ∞ α ) d j=1 2lβ 2 0,j + 4G 2 β 0,j g 0:T -1,j 2 + x 0 -x * 2 diag(β0) = (α + D 2 ∞ ) 2lβ 2 0 + 4G 2 αβ 0 d j=1 g 0:T -1,j 2 + β 0 x 0 -x * 2 2 .

Theorem 15. Suppose that ϕ ∈ C 1,1 l ([1, +∞)), and ϕ is α-strongly convex. Assume that g t ∞ ≤ G, and x t -x * ∞ ≤ D ∞ . Then the sequence {x t } obtained from Algorithm 2 (or 3) satisfies

2R(T ) ≤ 1 + D 2 ∞ α max √ 2l, 2G β 0 d j=1 g 0:T -1,j 2 + β 0 x 0 -x * 2 2 .

Proof. Similar to the proof of Theorem 14, for Algorithm 2, we have

2R(T ) ≤ T -1 t=0 d j=1 g 2 t,j β t+1,j + max 0≤t<T x t -x * 2 ∞ T -1 t=0 d j=1 (β t+1,j -β t,j ) + x 0 -x * 2 diag(β0) ≤ T -1 t=0 d j=1 g 2 t,j β t,j + max 0≤t<T x t -x * 2 ∞ T -1 t=0 d j=1 (β t+1,j -β t,j ) + x 0 -x * 2 diag(β0) .

With same reason, for Algorithm 3, we have

2R(T ) ≤ T -1 t=0 g t 2 diag(βt) -1 + T -1 t=0 x t -x * 2 diag(βt) -x t+1 -x * 2 diag(βt) ≤ T -1 t=0 g t 2 diag(βt) -1 + T -1 t=1 x t -x * 2 diag(βt-βt-1) + x 0 -x * 2 diag(β0) ≤ T -1 t=0 d j=1 g 2 t,j β t,j + max 0≤t<T x t -x * 2 ∞ T -1 t=1 d j=1 (β t,j -β t-1,j ) + x 0 -x * 2 diag(β0) ,

Note that for both algorithms

g 2 t,j = β 2 t,j ϕ β t+1,j β t,j ≥ αβ 2 t,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 g 2 t,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 g 2 t,j β t,j + β 0 x 0 -x * 2 2 ≤ (1 + D 2 ∞ α ) d j=1 max √ 2l, 2G β 0 g 0:T -1,j 2 + β 0 x 0 -x * 2 2 .

H LOGARITHMIC BOUNDS:

In this section, we will use a different class of 'distance' function for problem 4, and establish logarithmic regret bounds under assumption f t 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 ⊆ R d be a convex set. We say that a function f :

X → R is µ-strongly convex, if there exists µ ∈ R d 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 2 diag(µ)

. Let ξ = min j=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 2 2 .

The modification SC-Hyper-Regularization of Hyper-Regularization which we propose in the following uses a family of distance function

EQUATION

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 ∈ R d ++ .

Different from Algorithm 1 and 2, we add a hyper-parameter λ > 0 like AdaGrad to SC-Hyper-Gradient. Rewrite problem (5) as

EQUATION

and corresponding two algorithms as Algorithm 4 GD with SC-Hyper-regularization Input:

β 0 > 0, x 0 1: for t = 1 to T do 2:

Suffer loss f t (x t );

3: Receive g t ∈ ∂f t (x t ) of f t at x t ; 4:

Update β t+1,j as the solution of the equation λ(

β 2 /β t,j )ϕ (β/β t,j ) = g 2 t,j , j = 1, • • • , d; 5:

Update x t+1 = x t -g t /β t+1 ; 6: end for Algorithm 5 GD with SC-Hyper-regularization using alternating update rule Input: β 0 > 0, x 0 1: for t = 1 to T do 2:

Suffer loss f t (x t );

3: Receive g t ∈ ∂f t (x t ) of f t at x t ; 4:

Update β t+1,j = β t,j (ϕ ) -1 (g 2 t,j /(λβ t,j )), j = 1, . . . , d;

Update x t+1 = x t -g t /β t+1 ; 6: end for Remark. Same as Lemma 5, the monotonicity of Algorithm 4 and 5 also holds.

Theorem 17. Suppose that f t is µ-strongly convex for all t, ϕ ∈ C 1,1 l ([1, +∞)), and ϕ is αstrongly convex. Assume that g t ∞ ≤ G, and λ ≥ G 2 /(α min j=1:d µ j ). Then the sequence {x t } obtained from Algorithm 4 satisfies

2R(T ) ≤ l 1 + G 2 λlβ 0 2 d j=1 ln 1 + g 0:T -1,j 2 2 λlβ 0 + β 0 x 0 -x * 2 2 ,

and the sequence {x t } obtained from Algorithm 5 satisfies

2R(T ) ≤ l d j=1 ln 1 + g 0:T -1,j 2 2 λlβ 0 + β 0 x 0 -x * 2 2 ,

Remark. Under assumption in Theorem 17, we have g

0:T -1,j 2 2 ≤ G 2 T , so R(T ) = O(ln(T )).

To prove Theorem 17, we first prove following lemma. Lemma 18. For an arbitrary real-valued sequence {a i } and a positive real number b,

EQUATION

) Proof. Let b 0 = b, b t = b + t i=1 a 2 i , t ≥ 1, then T t=1 a 2 t b + t i=1 a 2 i = T t=1 b t -b t-1 b t = T t=1 bt bt-1 1 b t dx ≤ T t=1 bt bt-1 1 x dx = b T 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 {g t } t=0:T -1 and a positive sequence {β t } t=0:T which satisfies

EQUATION

and

EQUATION

Meanwhile, if

EQUATION

and

EQUATION

)

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 f t (x t ) -f t (x * ) ≤ 2 T -1 t=0 g t , x t -x * - T -1 t=0 x t -x * 2 diag(µ) = T -1 t=0 g t 2 diag(βt+1) -1 + T -1 t=0 x t -x * 2 diag(βt+1) -x t+1 -x * 2 diag(βt+1) - T -1 t=0 x t -x * 2 diag(µ) ≤ T -1 t=0 g t 2 diag(βt+1) -1 + T -1 t=0 x t -x * 2 diag(βt+1-βt-µ) + x 0 -x * 2 diag(β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 = β 2 t,j β 2 t+1,j g 2 t,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 = g 2 t,j λα ≤ G 2 λα . Hence, if λ ≥ max j=1:d G 2

αµj , then β t+1 -β t ≤ µ, and

T -1 t=0 x t -x * 2 diag(βt+1-βt-µ) ≤ 0.

On the other hand,

T -1 t=0 g t 2 diag(βt+1) -1 = d j=1 T -1 t=0 g 2 t,j β t+1,j ,

following from Lemma 19, we have

T -1 t=0 g t 2 diag(βt+1) -1 ≤ l 1 + G 2 λlβ 0 2 d j=1 ln 1 + g 0:T -1,j 2 2 λlβ 0 in Algorithm 4, T -1 t=0 g t 2 diag(βt+1) -1 ≤ l d j=1 ln 1 + g 0:T -1,j 2 2

λlβ 0 in Algorithm 5.

I CONVERGENCE RATES IN FULL BATCH SETTING:

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 ∈ C 1,1 L (R d ) and F * = inf x F (x) > -∞. Consider gradient descent with constant step size,

x t+1 = x t -∇F (xt) b . If b > L 2 , then min 0≤t≤T -1 ∇F (x t ) 2 2 ≤ ε

after at most a number of steps

T = 2b 2 (F (x 0 ) -F * ) ε(2b -L) = O 1 ε

Proof. Following from the fact that F is L-smooth, we have

EQUATION

) When b > L 2 , 1 -L 2b > 0. So T -1 t=0 ∇F (x t ) 2 2 ≤ 2b 2 2b -L (F (x 0 ) -F (x T )) ≤ 2b 2 2b -L (F (x 0 ) -F * ),

and

min 0≤t≤T -1 ∇F (x t ) 2 2 ≤ 1 T T -1 t=0 ∇F (x t ) 2 2 ≤ 2b 2 T (2b -L) (F (x 0 ) -F * ) ≤ ε.

Remark. If we choose b ≤ L 2 , 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:

EQUATION

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

β 2 t+1 ϕ (β t+1 /β t ) = g t 2 2

, while in update rule ( 14) and ( 33), β t+1 satisfies

β 2 t ϕ (β t+1 /β t ) = g t 2 2 . Theorem 21 (Convergence rate of update rule (13)). Suppose that ϕ ∈ C 1,1 l ([1, +∞)), ϕ is α- strongly convex, and F ∈ C 1,1 L (R d ), F * = inf x F (x) > -∞.

For any ε ∈ (0, 1), the sequence {x t } obtained from update rule (13) satisfies

min j=0:T -1 ∇F (x j ) 2 2 ≤ ε, 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( ε lL 2 +1) + L+(1+ 2 α ) F (x0)-F * + lL(L-β 0 ) 2β 0 2 ε otherwise.

Theorem 22 (Convergence rate of update rule ( 14)). Suppose that ϕ ∈ C 1,1 l ([1, +∞)), ϕ is αstrongly convex, and

F ∈ C 1,1 L (R d ), F * = inf x F (x) > -∞.

For any ε ∈ (0, 1), the sequence {x t } obtained from update rule (14) satisfies

min j=0:T -1 ∇F (x j ) 2 2 ≤ ε after T steps, where T =        1 + 2(β0+ g0 2 2 /(αβ0)+2(F (x0)-F * )/α)(F (x0)-F * ) ε if β 0 ≥ L or β 1 ≥ L, 1 + log( L β 0 ) log( ε lL 2 +1) + L+ 2l αβ 0 L 2 + 2l α L+(1+ 8 α ) F (x0)-F * + lL(L-β 0 ) 2β 0 2 ε otherwise.

Theorem 23 (Convergence rate of update rule (33)). Suppose that ϕ

∈ C 1,1 l ([1, +∞)), ϕ is α- strongly convex, and F ∈ C 1,1 L (R d ), F * = inf x F (x) > -∞.

For any ε ∈ (0, 1), the sequence {x t } obtained from update rule (33) satisfies

min j=0:T -1 ∇F (x j ) 2 2 ≤ ε after T steps, where T =                    1 + 2(β0+2(F (x0)-F * )/α)(F (x0)-F * ) ε if β 0 ≥ L, 2 +     β0+ g 0 2 2 αβ 0 +(1+ 2 α ) F (x0)-F * + lL g 0 2 2 2αβ 2 0 2 ε     if β 0 < L, β 1 ≥ L, 1 + log( L β 0 ) log( ε lL 2 +1) + (1+ 2l α )L+ 2lL 2 αβ 0 +(1+ 2 α ) F (x0)-F * + lL 2β 0 (1+ 2l α )L+ 2lL 2 αβ 0 -β0 2 ε otherwise.

We begin our proof by following lemma.

Lemma 24. Suppose ϕ ∈ C 1,1 l (R ++ ). Fix ε ∈ (0, 1]. In both update rules ( 13) and ( 14), after

T = log( L β 0 ) log( ε lL 2 +1) + 1 steps, either min t=0:T -1 g t 2 2 ≤ ε, or β T ≥ L holds.

Proof. Assume that β T < L and min t=0:T -1 g t 2 2 > ε. 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 = g t 2 2 β 2 t+1 > ε L 2 (in Algorithm 1), ϕ β t+1 β t = g t 2 2 β 2 t > ε L 2 (in Algorithm 2).

Note that ϕ is a l-smooth convex function, and

EQUATION

then

β t+1 β t > ε lL 2 + 1.

In this case,

L > β T = β 0 ε lL 2 + 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 ∈ C 1,1 L (R d ), ϕ ∈ C 1,1 l (R ++ )

, and ϕ is α-strongly convex function. Denote F * = inf x F (x) > -∞. Let t 0 ≥ 1 be the first index such that β t0 ≥ L. Then for all t ≥ t 0 ,

EQUATION

and moreover,

EQUATION

Proof. Same as equation (32),

F (x t+1 ) ≤ F (x t ) - 1 β t+1 1 - L 2β t+1 g t 2 2 . For t ≥ t 0 -1, β t+1 ≥ L, so F (x t+1 ) ≤ F (x t ) - 1 2β t+1 g t 2 2 .

Hence, for all k ≥ 0,

EQUATION

i.e.,

EQUATION

Note that ϕ is α-strongly convex and

EQUATION

EQUATION

Combining equation ( 38) and equation ( 39), we have

β t0+k ≤ β t0-1 + 1 α k i=0 g t0+i-1 2 2 β t0+i ≤ β t0-1 + 2 α (F (x t0-1 ) -F * ).

We remain to give an a upper bound for F (x t0-1 ) in the case t 0 > 1. Using equation ( 32) again, we get

F (x t0-1 ) -F (x 0 ) ≤ t0-2 i=0 - 1 β i+1 1 - L 2β i+1 g i 2 2 ≤ L 2 t0-2 i=0 g i 2 2 β 2 i+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 t 0 = 1, by equation ( 37), for all t ≥ 1, we have

F (x t ) ≤ F (x 0 ) - 1 2 t-1 i=0 g i 2 2 β i+1 ≤ F (x 0 ) - 1 2 t-1 i=0 g i 2 2 β 0 + 2 α (F (x 0 ) -F * )

.

Then after T = 1 + 2(β0+2(F (x0)-F * )/α)(F (x0)-F * ) ε steps,

min t=0:T -1 g t 2 2 ≤ 1 T T -1 t=0 g t 2 2 ≤ 2 T (F (x 0 ) -F * )(β 0 + 2 α (F (x 0 ) -F * )) ≤ ε.

Otherwise, if t 0 > 1, we have β t0-1 < L. Then for all t ≥ t 0 , Next we prove Theorem 22.

EQUATION

Lemma 26. In update rule ( 14), suppose F ∈ C 1,1 L (R d ), ϕ ∈ C 1,1 l (R ++ ), and ϕ is α-strongly convex function. Denote F * = inf x F (x). Let t 0 ≥ 1 be the first index such that β t0 ≥ L. Then for all t ≥ t 0 ,

EQUATION

and moreover,

EQUATION

EQUATION

Proof. Same as the proof of Lemma 25, we first get for all k ≥ 0,

k i=0 g t0+i-1 2 2

β t0+i ≤ 2(F (x t0-1 ) -F * ).

Note that in update rule (14), β 2 t ϕ (β t+1 /β t ) = g t 2 2 . 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 α g t0+k 2 2 β t0+k ≤ β t0+k + 2 α g t0+k -g t0+k-1 2 2 + g t0+k-1 2 2 β t0+k ≤ β t0+k + 2 α L 2 x t0+k -x t0+k-1 2 2 + g t0+k-1 2 2 β t0+k ≤ β t0+k + 2 α L 2 g t0+k-1 2 2 β 3 t0+k + 2 α g t0+k-1 2 2 β t0+k ≤ β t0+k + 4 α g t0+k-1 2 2 β t0+k ≤ β t0 + 4 α k i=0 g t0+i-1 2 2 β t0+i

≤ β t0 + 8 α (F (x t0-1 ) -F * ).

If t 0 = 1, then

β t0 ≤ β 0 + g 0 2 2

αβ 0 , and if t 0 ≥ 2, then

β t0 ≤ β t0-1 + g t0-1 2 2 αβ t0-1 = β t0-1 + 2L 2 α g t0-2 2 2 β 3 t0-1 + 2 α g t0-2 2 2 β t0-2 ≤ β t0-1 + 2L 2 α l(β t0-1 -β t0-2 )β t0-2 β 3 t0-1 + 2 α l(β t0-1 -β t0-2 ) ≤ L + 2l αβ 0 L 2 + 2l α L.

At last, for t 0 > 0, we have

F (x t0-1 ) -F (x 0 ) ≤ t0-2 i=0 - 1 β i+1 1 - L 2β i+1 g i 2 2 ≤ L 2 t0-2 i=0 g i 2 2 β 2 i+1 ≤ L 2 t0-2 i=0 g i 2 2 β 2 i = 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 ∈ C 1,1 L (R d ), ϕ ∈ C 1,1 l (R ++ ), and ϕ is α-strongly convex function. Denote F * = inf x F (x). Let t 0 ≥ 0 be the first index such that β t0 ≥ L. Then for all t ≥ t 0 ,

EQUATION

and moreover,

EQUATION

EQUATION

)

Proof. Same as the proof of Lemma 25, we first get

F (x t0+k+1 ) ≤ F (x t0+k ) - 1 β t0+k 1 - L 2β t0+k g t0+k 2 2 ≤ F (x t0+k ) - 1 2β t0+k g t0+k 2 2 ≤ F (x t0 ) - 1 2 k i=0 g t0+i 2 2

β t0+i , and k i=0 g t0+i 2 2

β t0+i ≤ 2(F (x t0 ) -F * ).

Note that in Algorithm 2, β 2 t ϕ (β t+1 /β t ) = g t 2 2 . 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 α g t0+k 2 2 β t0+k ≤ β t0 + 1 α k i=0 g t0+i 2 2 β t0+i ≤ β t0 + 2 α (F (x t0 ) -F * ).

At last, for t 0 > 0, we have

F (x t0 ) -F (x 0 ) ≤ L 2 t0-1 i=0 g i 2 2 β 2 i = L 2 t0-1 i=0 ϕ β i+1 β i ≤ Ll 2β 0 (β t0 -β 0 ).

Recall that αβ t (β t+1 -β t ) ≤ g t 2 2 ≤ lβ t (β t+1 -β t ). So if t 0 = 1,

β t0 ≤ β 0 + g 0 2 2

αβ 0 .

And if t 0 ≥ 2, we have

β t0 ≤ β t0-1 + g t0-1 2 2 αβ t0-1 ≤ β t0-1 + 2 g t0-1 -g t0-2 2 2 + g t0-2 2 2 αβ t0-1 ≤ β t0-1 + 2L 2 α x t0-1 -x t0-2 2 2 β t0-1 + 2 α g t0-2 2 2 β t0-2 = β t0-1 + 2L 2 α g t0-2 2 2 β 2 t0-2 β t0-1 + 2 α g t0-2 2 2 β t0-2 ≤ β t0-1 + 2L 2 α l(β t0-1 -β t0-2 ) β t0-2 β t0-1 + 2 α l(β t0-1 -β t0-2 ) ≤ L + 2l αβ 0 L 2 + 2l α L.

proof of Theorem 23. The proof is completely similar to the proof of Theorem 21.

:

Comparing with Bregman divergence, ϕ-divergence requires nonnegative β and ηt which is apparent for learning rates.

Using partial derivative, we can obtain the saddle point of Ψt and ensure this fact.

Since it is a pure optimization problem, testing performance is out of our main consideration.

Figures and Tables:

3

Figure 2: Convergence performances of algorithms on MNIST in the full batch setting. left: the train loss of the last training epoch at different initial learning rates, right: the whole training process with the given initial learning rate in the bracket for each algorithm.

Figure 3: Convergence performances of algorithms on CIFAR-10 in the online learning setting, left: the train loss of the last training epoch at different initial learning rates, right: the whole training process with the given initial learning rate in the bracket for each algorithm.

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.

Figure 7: The values of the maximum β t at each training step for various algorithms.

40)Denote the right hand of equation (40) as β max . Using equation (37) again, for we haveF (x t0+M ) ≤ F (x t0-1 ) -have min t=0:T -1 g t 2 2 ≤ ε.

Convergence performances of RKL 1 , RKL 2 , and RKL 3 on the database of MNIST in online learning setting, up: performances at different initial learning rates, and down: the whole training process with the given initial learning rate in the bracket for each algorithm.

Table content: <table><tr><td>1.2</td><td/><td/><td/><td/><td/><td>1.00</td><td/><td/><td/><td/><td/></tr><tr><td>0.2 0.4 0.6 0.8 1.0 Train Loss</td><td/><td/><td/><td/><td/><td>0.65 0.70 0.75 0.80 0.85 0.90 0.95 Test Accuracy</td><td>RKL1 RKL2 RKL3</td><td/><td/><td/><td/></tr><tr><td>10 3 0.02 0.04 0.06 0.08 0.10 Train Loss</td><td/><td colspan="3">10 2 Initial Learning Rate 10 1 10 0 RKL1 (10 0.5 ) RKL2 (10 0.5 ) RKL3 (10 0.5 )</td><td colspan="2">10 1 Test Accuracy 0.9850 10 3 0.9675 0.9700 0.9725 0.9750 0.9775 0.9800 0.9825</td><td colspan="3">10 2 Initial Learning Rate 10 1 10 0</td><td/><td>10 1</td></tr><tr><td>0.00</td><td>10</td><td>20</td><td>30 Epoch</td><td>40</td><td>50</td><td>0.9650</td><td>10</td><td>20</td><td>30 Epoch</td><td>40</td><td>50</td></tr><tr><td>Figure 1:</td><td/><td/><td/><td/><td/><td/><td/><td/><td/><td/><td/></tr></table>

Convergence performances of H 2 and H 3 on the database of MNIST in online learning setting, up:at different initial learning rates, and down:the whole training process with the given initial learning rate in the bracket.

Table content: <table><tr><td>0.5</td><td/><td/><td/><td/><td/><td>1.000</td><td/><td/><td/><td/><td/></tr><tr><td>10 3 0.1 0.2 0.3 0.4 Train Loss 0.01 0.02 0.03 0.04 0.05 0.06 0.07 0.08 Train Loss</td><td/><td colspan="3">10 2 Initial Learning Rate 10 1 10 0 H2 (10 0.5 ) H3 (10 0.5 )</td><td colspan="2">10 1 Test Accuracy 0.825 10 3 0.850 0.875 0.900 0.925 0.950 0.975 0.800 0.984 0.972 0.974 0.976 0.978 0.980 0.982 Test Accuracy</td><td>H2 H3</td><td colspan="2">10 2 Initial Learning Rate 10 1 10 0</td><td/><td>10 1</td></tr><tr><td>0.00</td><td>10</td><td>20</td><td>30 Epoch</td><td>40</td><td>50</td><td>0.970</td><td>10</td><td>20</td><td>30 Epoch</td><td>40</td><td>50</td></tr><tr><td>0.5 Figure 5: 10 3 0.1 0.2 0.3 0.4 Train Loss 0.02 0.03 0.04 0.05 0.06 0.07 0.08 Train Loss</td><td/><td colspan="3">10 2 Initial Learning Rate 10 1 10 0 2 2 3 (10 0.5 ) 2 (10 0.25 )</td><td>10 1</td><td>1.0 10 3 0.4 0.5 0.6 0.7 0.8 0.9 Test Accuracy 0.3 0.974 0.976 0.978 0.980 0.982 0.984</td><td>2 2 2 3</td><td colspan="2">10 2 Initial Learning Rate 10 1 10 0</td><td/><td>10 1</td></tr><tr><td>0.01</td><td/><td/><td/><td/><td/><td>0.972</td><td/><td/><td/><td/><td/></tr><tr><td>10 3 0.1 0.2 0.3 0.4 0.5 Train Loss 0.01 0.02 0.03 0.04 0.05 0.06 0.07 0.08 Train Loss 0.00</td><td>10</td><td colspan="3">10 2 Initial Learning Rate 10 1 10 0 KL3 (10 0.5 ) KL2 (10 0.5 ) 20 30 40 Epoch</td><td colspan="2">10 1 Test Accuracy 0.972 10 3 0.974 0.976 0.978 0.980 0.982 0.984 0.4 0.5 0.6 0.7 0.8 0.9 1.0 Test Accuracy 50 0.970</td><td>KL2 KL3 10</td><td colspan="2">10 2 Initial Learning Rate 10 1 10 0 20 30 Epoch</td><td>40</td><td>10 1 50</td></tr><tr><td>0.00</td><td>10</td><td>20</td><td>30 Epoch</td><td>40</td><td>50</td><td>0.970</td><td>10</td><td>20</td><td>30 Epoch</td><td>40</td><td>50</td></tr></table>

be the solution of unconstrained problem max β (min x Ψ t (x, β)), hence,

Table content: <table><tr><td/><td/><td/><td>∂Ψt,x(β) ∂βj</td><td>is a non-increasing</td></tr><tr><td>function. Recall that β  β  *  j is a zero of function</td><td>∂Ψt,x(β) ∂βj</td><td>.</td></tr><tr><td colspan="3">Moreover, if β  *  j &gt; B t,j , we have</td><td>∂Ψt,x(β) ∂βj</td></tr></table>

Peer review (iclr2019):
 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. The authors study an important problem and propose a novel method. The algorithms suggested by the author are also relatively clear, and it is great that the paper presents both theoretical results as well as numerical experiments. On the other hand, I didn*t find the main idea of hyper-regularization to be well-justified. It is not clear why adding an additional regularization term for the learning rate makes sense , and it is even less clear why this should be presented as a maxmin problem. This can make the update step much more complicated and is probably why the authors also propose a simpler alternating optimization algorithm as an alternative. Unfortunately, the authors do not discuss how this alternating optimization problem relates to the original one, and the theoretical guarantees are only presented for the original algorithm. The authors also do not justify the choice of phi-divergence as the regularizer for the learning rate. The theoretical guarantees in the paper also do not suggest that the algorithm presented in the paper is better than existing state-of-the-art methods, even in specific situations (i.e. the regret bounds don*t appear better than the AdaGrad regret bounds). Moreover, without tests for statistical significance, I also didn*t find the experimental results sufficiently compelling. Specific comments and questions: 1) Page 3: Equation (4): The paper would be stronger if the authors motivated why the regularization should be posed as an outer maximization. 2) Page 3: "we use the .phi-divergence as our hyper-regularization". Why is this a good choice of reuglarizer? 3) Page 3: "only a few extra calculations are required for each step". This is a misleading comment, because the maximization can be hard when phi is complicated, even if the problem splits across dimensions. 4) Page 4: "The solution of problem (5) is the same as (7) in unconstrained case". You should provide a reference for this statement as well as discuss the specific assumptions on the objective that allow you to arrive at this claim. 5) Page 4: "while the solution of (7) is more difficult to get. Thus, we choose (5) as our basic problem". This seems like a very bad motivation for choosing the maxmin formulation. For instance, the problem would be even simpler if you didn*t include this extra phi-divergence at all. 6) Page 4: "Although setting .eta-t=.beta_t is our main focus...". Why is smoothness in the learning rate a good property? 7) Page 5: Equation (11). How do these iterates relate to the ones in equation (5) (e.g. when do they coincide, if ever)? 8) Page 5: "influence the efficient of our algorithms." Grammatical error. 9) Page 6. "our algorithms are robust to the choice of initial learning rates and do not rely on the Lipschitz constant or smoothness constant". I*m not sure why this is a valuable property, since AdaGrad doesn*t rely on these parameters either. 10) Page 6: Theorems 6 and 7. How do these results depend on alpha and .beta_t? This paper would be much stronger if the bounds depend on .phi more clearly and if the authors were able to show that there exist choices of phi that make this algorithm better than existing methods. 11) Page 6: Theorem 7: The dependence on G in the regret bound actually makes this worse than the AdaGrad regret bound. 12) Page 7: "KL_devergence". Typo. 13) Page 7: "different update rules were compared in advance to select the specific one for any phi divergence in the following experiments." What does this mean exactly? How much of a difference does the choice of update rule make? 14) Page 7: "growth clipping is applied to all algorithms in our framework". Why is this necessary, and how does it affect the theoretical results? 14) Page 7-8: Figures 1, 2, and 3. It*s hard to interpret the significance of these results without error bars.