Exploiting Local Convergence of Quasi-Newton Methods Globally: Adaptive Sample Size Approach
Authors: Qiujiang Jin
Aryan Mokhtari
Venue: NeurIPS 2021 Poster (2021)
Keywords: Quasi-Newton methods
adaptive sample size methods
second-order methods
large-scale optimization.

Abstract: In this paper, we study the application of quasi-Newton methods for solving empirical risk minimization (ERM) problems defined over a large dataset. Traditional deterministic and stochastic quasi-Newton methods can be executed to solve such problems; however, it is known that their global convergence rate may not be better than first-order methods, and their local superlinear convergence only appears towards the end of the learning process. In this paper, we use an adaptive sample size scheme that exploits the superlinear convergence of quasi-Newton methods globally and throughout the entire learning process. The main idea of the proposed adaptive sample size algorithms is to start with a small subset of data points and solve their corresponding ERM problem within its statistical accuracy, and then enlarge the sample size geometrically and use the optimal solution of the problem corresponding to the smaller set as an initial point for solving the subsequent ERM problem with more samples. We show that if the initial sample size is sufficiently large and we use quasi-Newton methods to solve each subproblem, the subproblems can be solved superlinearly fast (after at most three iterations), as we guarantee that the iterates always stay within a neighborhood that quasi-Newton methods converge superlinearly. Numerical experiments on various datasets confirm our theoretical results and demonstrate the computational advantages of our method.

Exploiting Local Convergence of Quasi-Newton Methods Globally: Adaptive Sample Size Approach
Qiujiang Jin
Aryan Mokhtari
ECE Department The University of Texas Austin
ECE Department
The University of Texas at Austin
Austin, TX 78712, USA qiujiangdaustin. utexas.e..... edu
Austin, TX 78712, USA
mokhtari@austin utwxas.ee............... edu
Abstract
In this paper, we study the application of quasi-Newton methods for solving empir- ical risk minimization (ERM) problems defined over large dataset. Traditional deterministic and stochastic quasi-Newton methods can be executed solve such problems; however, it is known that their global convergence rate may not be better than first-order methods, and their local superlinear convergence only appears towards the end of the learning process. In this paper, we use an adaptive sample size scheme that exploits the superlinear convergence of quasi-Newton methods globally and throughout the entire learning process. The main idea of the proposed adaptive sample size algorithms is to start with a small subset of data points and solve their corresponding ERM problem within its statistical accuracy, and then enlarge the sample size geometrically and use the optimal solution of the problem corresponding to the smaller set initial point for solving the subsequent ERM problem with more samples. We show that if the initial sample size sufficiently large and we quasi-Newton methods to solve each subproblem, the subproblems can be solved superlinearly fast (after at most three iterations), as we guarantee that the iterates always stay within neighborhood that quasi-Newton methods converge superlinearly. Numerical experiments on various datasets confirm our theoretical results and demonstrate the computational advantages of our method.
1 Introduction
In various machine learning problems, we aim find an optimal model that minimizes the expected loss with respect to the probability distribution that generates data points, which is often referred to as expected risk minimization. In realistic settings, the underlying probability distribution of data is unknown and we only have access to finite number of samples (N samples) that are drawn independently according to the data distribution. a result, we often settle for minimizing the sample average loss, which is also known empirical risk minimization (ERM). The gap between expected risk and empirical risk which known as generalization error deeply studied in the statistical learning literature [1-5), and it is well-known that the gap between these two loss functions vanishes as the number samples N in the ERM problem becomes larger.
Several variance reduced first-order methods have been developed to efficiently solve the ERM problem associated with large dataset [3]. However, a common shortcoming of these first-order methods is that their performance heavily depends on the problem condition number := L/μu where the risk function smoothness parameter and μ the risk function strong convexity constant. As result, these first-order methods suffer from slow convergence when the problem has a large condition number, which is often the case datasets with thousands of features. In fact, the best-known bound
35th Conference on Neural Information Processing Systems (NcurIPS 2021).

---

Table I: Comparison of adaptive sample size methods, in terms of number of gradient computations, Hessian computations, matrix-vector product evaluations and matrix inversions.
Algorithm
gradient comp.
Hessian comp.
matrix- product
matrix inversion
Ada Newton
((N)
O(N)
Olo N)
Olog N)
AdaQN
O(N)
m0
(loog
achieved by first-order methods belongs to Katyusha | which has a cost of O((N + v VKN) log N)
to achieve the statistical accuracy of an ERM problem with N samples.
To resolve this issue, second-order methods such Newton's method and quasi-Newtor methods are often used, as they improve curvature approximation by exploiting second-orde information. Several efficient implementations of second-order methods for solving large-scale ERM problems have been proposed recently, including incremental Newton-type methods [1]. sub-sampled Newton algorithms [15] and stochastic quasi-Newton methods [0) However, these methods still face two major issues. First, their global convergence requires selection of a small step size which slows down the convergence, or implementation of a line-search scheme which is computationally prohibitive for large-scale ERM problems, since it requires multiple passes over data. The second disadvantade of these (deterministic and stochastic) second-order methods is that their local quadratic or superlinear convergence only appears in a small local neighborhood of the optimal solution. This often means that, when we solve an ERM problem, the fast superlinear or quadratic convergence rate of these methods happens when the iterates have already reached the statistical accuracy of the problem and the test accuracy would not improve, even the ERM problem error (training error) decreases.
To address these two shortcomings of second-order methods for solving large-scale ERM problems, the adaptive sample size Newton (Ada Newton) method was proposed in (21). In adaptive sample size methods, instead of solving the ERM corresponding to the full training set directly (as in deterministic methods) or using a subset of samples at each iteration (as in stochastic methods), we minimize a sequence of geometrically increasing ERM problems. Specifically, we solve the ERM problem corresponding to a subset of samples, e.g. m samples, within their statistical accuracy, then we use the resulting solution as an initial point for the next ERM problem with n = am samples (a > 1). where the larger set with n samples contains the smaller set with m samples. The main principle of this idea is that all training samples are drawn from the same distribution, therefore the optimal values of the ERM problems with m and n samples are close to each other. The main result of Ada Newton in 21 is that if one chooses the expansion factor properly, the solution for the problem with m samples is within the Newton quadratic convergence neighborhood of the next ERM problem with n = am samples. Hence, each subproblem can be solved quickly by exploiting the quadratic convergence of Newton's method at every step of the learning process. This approach is promising as the overall number of gradient and Hessian computations for Ada Newton is O(N), while it requires computing O (log N) Newton's 's directions. Note that O notation only hides absolute constants and these complexities are independent of problem condition number The main drawback of this approach, however, is the requirement of (log N) Newton's 's directions computation, where each could cost (dd) arithmetic operations, where d is the dimension. It also requires ((N) Hessian evaluations which requires (Nd?) arithmetic operations, and this could be computationally costly.
A natural approach to reduce the computational cost of Newton's 's method is the use of quasi-Newton algorithms, in which, instead of exact computation of the Hessian and its inverse required for Newton update, we approximate the objective function Hessian and its inverse only by computing first-order information (gradients). Since this approximation only requires matrix-vector product computations at each iteration, the computational complexity of quasi-Newton methods is reduced. It is known that quasi- quasi-Newton methods such as DFP and BFGS converge superlinearly in a neighborhood close to the optimal solution, i.c., the iterates {w&} converge to the optimal solution w at rate of methods for the described adaptive sample size scheme, explicit superlinear convergence rate of these methods needed to characterize the number of iterations required for solving each ERM problem. The non-asymptotic convergence rate of quasi-Newton methods was unknown until very recently, when a set of concurrent papers 22 2 and 244 showed that in a local neighborhood of the optimal solution,
lim [ w- || = 0. where is the iteration number. To exploit
the iterates of DFP and BFGS converge the optimal solution at a rate of (1/k)*/2.
In this paper, we exploit the finite-time analysis of the quasi-Newton methods studied in 24 to develop an adaptive sample size quasi-Newton (AdaQN) method that reaches the statistical accuracy
2

---

of the ERM corresponding to the full training set after ((N) gradient computations and (log N) -etrix-vector product evaluations and only matrix inversion. In Table we formally compare the computation cost of our proposed AdaQN algorithm and the Ada Newton method in [2]. As shown in Table [ the total number of gradient evaluations and matrix-vector product computations for AdaQN are the same as the ones for Ada Newton, while the number of Hessian computations for AdaQN and Ada Newton are my and (NN) ). respectively, where mi is the size of initial training set in the adaptive sample size scheme, and it is substantially smaller than N. i.e., m0 < N. In our main theorem we show that me is lower bounded by Q mmxx| d, x²s log d where 5 is a parameter determined by the loss function and the structures of the training data (see details in Remark 2) Hence, in this paper, we focus on the regime that the total number of samples satisfies N > max (d, K² log d}. However, numerical experiments in Section 5 show that AdaQN often achieves small risk for mo much smaller than this lower bound and the effectiveness of AdaQN goes beyond this regime. Also, the number of times that Ada Newton requires to compute the inverse of a square matrix (or solving linear system) is (log N), while to implement AdaQN we only require one matrix inversion. We should also add that the implementation of Ada Newton requires backtracking mechanism for the choice of growth factor a. This backtracking scheme is needed to ensure that the size of training set does not grow too fast, and the iterates stay within the quadratic convergence neighborhood Newton's 's method for next ERM problem. Unlike Ada Newton, our proposed AdaQN method does not require such backtracking scheme, and as long as the size of initial training set my is sufficiently large, we can double the size of training set at the end of each phase, i.c., we set = 2.
It is worth noting that in [25 the authors study a similar approach to our proposed adaptive sample size quasi-Newton method called the batch-expansion training (BET) method. The BET method differs from our proposed framework in terms of algorithm development and convergence analysis. Specifically, the BET method uses a similar idea of geometrically increasing the size of the training set, while using the limited-memory BFGS (L-BFGS) method for solving the Empirical Risk Minimization (ERM) subproblems. The authors leverage the linear convergence rate of L-BFGS to characterize the overall complexity of the BET algorithm. We should mention that since the linear convergence rate of L-BFGS is not provably better than first-order methods, the overall iteration complexity of BET is similar to the one for adaptive sample size first-order methods (26 which depends on the problem condition number. In contrast to [5), in this paper, we leverage the local superlinear convergence rate of the BFGS method to improve the overall complexity of adaptive sample size first-order methods, and hence, it also improves the complexity of the BET method.
2 Problem formulation
In this paper, we focus minimizing large-scale empirical risk minimization (ERM) problems. Consider the loss function f Rd x 2 + R that takes inputs as the decision variable w E IRd and random variable Z 2 with probability distribution P. The expected risk minimization problem aims at minimizing the expected loss over all possible choices of Z.
w' == arg min R(w)= = arg min Ez Zw:
Note that in this expression we defined the expected risk R Rd + R as R(w) := Ef Z and w" optimal solution of the expected risk minimization. In this paper we focus loss functions if that are strongly convex with respect to w, hence the optimal solution w' is unique.
The probability distribution P is often unknown, and we only have access to a finite number of realizations of the random variable Z, which we refer to as our training set T = {z1,..., ,,...,,N,, ). These N realizations are assumed to be drawn independently and according to P. Hence, instead of minimizing the expected risk in Q we attempt to minimize the empirical risk corresponding to the training set T [Z1,.... zN }. To formalize this, let us first define S, {zi,..., } as subset of the training set TT which contains its first n elements. Without loss of generality we defined an ordering for the elements of the training set TT The empirical risk corresponding to the set S, is defined as (w) = Σ
1= f(w; 2;) and its optimal solution w is given by
1 ' 2.) n 1=1
w = arg min RA (w) = arg min
(2)
Note that the ERM problem associated with the full training set T is a special case of when .N, and its unique optimal solution is denoted by w
3

---

The gap between the optimal values of empirical risk R., and expected risk R is well-studied in the statistical learning literature and here we assume the following upper bound holds
E [1
R[w")[))))))) < Vn
(3)
where V,, is function of the sample size that approaches zero becomes large. The expectation in (3) is over the set Sn. In this paper, we assume that all the expectations are with respect to the corresponding training set. Classic results have established bounds of the form Vn, (1/vv)) 27 and other recent papers including (255 show that under stronger regularity conditions such as strong convexity, we have V, = (1/n), for n = 52xx² log d). In this paper, we assume the requirements for the bound V = ((1/n) are satisfied.
Since the gap between the optimal empirical and expected risks is always bounded above by the error Vn, there is no point to reducing the optimization error of minimizing R, beyond the statistical accuracy Vn- In other words, if we obtain solution V such that E (wr) R., (,(w))) = OVV.), there would be no benefit in further minimizing Rn, Due to this observation, we say w solves the ERM in 2 within its statistical accuracy if E [R, (w) R. (w;)] S Vn. The ultimate goal is to efficiently find a solution W N that reaches the statistical accuracy of the full training set T, i.e., E [Rw (Wx) [x(w")] S Vx. Next, we state the notations and assumptions.
Assumption 1. For all values of z, the loss function fw: is twice differentiable and p-strongly convex with respect to w and its gradient is Lipschitz continuous with parameter T. > 0.
Assumption 2. For all values of the loss function f(w;z) is self-concordant with respect to w.
Assumptions T and 2 are customary for the analysis of quasi-Newtor methods. These conditions also imply that the empirical risk R., is also self-concordant, strongly convex with μ. and its gradient is Lipschitz continuous with L. Hence, the condition number of R, is K == L/p.
Computational cost notation We report the overall computational cost in terms of these parame- ters: (i) Tgrad and THess which denote the cost of computing one gradient of size d and one Hessian of size dl x d; (ii) Tprod which indicates the cost of computing the product of a square matrix of size x d with a vector of size d; and (iii) Tine which denotes the cost of computing the inverse of a square matrix of size d x d or the cost of solving a linear system with d variables and d equations.
3 Algorithm
Quasi-Newton methods Before introducing our method, we first briefly recap the update of quasi- Newton (QN) methods. Given the current iterate w, the QN update for the ERM problem (2 is
+ w - H (w,,
(4)
where v) > 0 a step size and E Rddd is symmetric positive definite matrix approximating the Hessian inverse V Rr, (w) The main goal of quasi-Newton schemes is to ensure that the matrix H always stays close to V (r, (w)- There are several different approaches for updating the Hessian approximation matrix H, but the two most-widely used updates are the DFP method defined as
Hyy H 88
H - H
(5)
y Hy
STY
and the BFGS update defined
sy s y
ys T
88
H
I
H I
+
(6)
s y
s TTy y
where s := w w is the variable variation and y == VR,(
RR, (w) is the gradient variation. If we follow the updates (5) or (6). then finding the new Hessian inverse approximation and consequently the new descent direction - V R, (w+) only require computing few matrix- vector multiplications. Considering this point and the fact that each step BFGS or DFP requires n gradients evaluations, the computational cost of each step of BFGS and DFP is On + Tprod).

---

Algorithm AdaQN
Input: The initial sample size mo: The initial argument Wmo within the statistical accuracy of Rmo:
The initial Hessian inverse Hmg Rmo (Wmg)
2
1: Set n. + ma0
2: while n S.N do
3: Set the initial argument w <- Wn, the initial matrix H +- H mo and iteration = 1;
4: Increase the sample size: n f- min
5: while iteration I fn do
6: w t w H V R2 (w):
7:
s w W: Rn (w): H I
8:
+ VRn(
9:
H [I sy
ys y
y
5
10: Set w w+, H f- H+ and iteration < iteration +
11: end while
12: Set W. <- w;
13:
end while
3.1 Adaptive sample size quasi-Newton algorithm (AdaQN)
BFGS, DFP or other quasi-Newton (QN) methods can be used to solve the ERM problem correspond- ing to the training set T with N samples, but (i) the cost per iteration would be of O(N Tgrad + Tprod), (ii) the superlinear convergence only appears towards the end of learning process when the iterates approach the optimal solution and statistical accuracy is already achieved, and (iii) they require step size selection policy for their global convergence. To resolve the first issue and reduce the high computational cost of (NNTrad + Tprod), one could use stochastic or incremental QN methods that only use a subset of samples at each iteration; however, stochastic or incremental QN methods (similar deterministic QN algorithms) outperform first-order methods only when the iterates close to the optimal solution and they also require line-search schemes for selecting the step size. Hence, none of these schemes is able to exploit fast superlinear convergence rate of QN methods throughout the entire training process, while always using a constant step size of 1.
Next, we introduce the adaptive sample size quasi-Newton (AdaQN) method that addresses these drawbacks. Specifically, (i) AdaQN does not require any line-search scheme and (ii) exploits the superlinear rate of QN methods throughout the entire training process. In nutshell, AdaQN leverages the interplay between the statistical accuracy of ERM problems and superlinear convergence neighborhood of QN methods to solve ERM problems efficiently. It uses the fact that all samples are drawn from the same distribution, therefore the solution for ERM with m samples not far from the solution of ERM with samples, where samples contain the samples. Hence, the solution of the problem with less samples can be used as a warm-start for the problem with more samples. Note that there two important points here that we should highlight. First, if m and n are chosen properly, the solution of the ERM problem R.n corresponding to the set S... with m samples will be in the superlinear convergence neighborhood of the next ERM problem corresponding to the set S, with samples, where Sn C Sn. Hence, each subproblem can be solved with a few iterations of quasi-Newton methods (see Figure in the appendix). Second, in each subproblem we only use a subset of samples, therefore the cost of running QN methods for solving subproblems with m samples (where
N) is significantly less than the update of QN methods for the full training set.
The steps of AdaQN are outlined in Algorithm I We start with a small subset of the full training set with mo samples and solve its corresponding ERM problem within its statistical accuracy. The initial ERM problem can be solved using any iterative method and its cost will be negligible as it scales with mg instead of N, where mg < N. In the main loop (Step 2-Step 12) implement AdaQN. Specifically, we first use the solution from the previous round (or W mo when n = m2) as the initial iterate, while we set the initial Hessian inverse approximation (Step 3). Then, we double the size of the training set by adding more samples to the active training set (Step 4). In Steps 5-10 we run the BFGS update for minimizing the loss R., while we keep updating the iterates and Hessian inverse approximation. Once, the required condition for convergence specified in Step 5 is obtained, we output the iterate w,, as the iterate that minimizes R, within its
H H mg = 2 (Wm.)" -
5

---

statistical accuracy. In Step 8 we used the update for BFGS, but one can simply replace this step with the update of the DFP method. As we ensure that iterates always stay within the neighborhood that BFGS (or DFP) converges superlinearly, the step size of these methods can be set 1) = 1. We repeat this procedure until we reach the whole dataset T with N samples. In Algorithm [ for the phase that we minimize Rn (Steps 5-10), our goal is to find a solution w,, that satisfies [Rn (Wn)) - Rn (w;)] S Vn. We use i, to indicate the maximum number of QN updates to find such a solution. Our theoretical result (Theorem ( suggests that due to fast convergence of QN methods, at most bn = 3 iterations required to solve each subproblem within its statistical accuracy.
Remark 1. Note that a natural choice for the initial Hessian inverse approximation at each phase of AdaQN with samples is the Hessian inverse at the initial iterate of that phase, i.e., setting the initial Hessian inverse approximation H = Rm (m)) where wm is the solution of the previous phase with m n122 samples. However, if we follow this initialization, then for each phase of AdaQN we need to compute nt new Hessians to evaluate 2 (Ww)) and one matrix inversion to find R²R,, (wm)- which would increase the computational cost of AdaQN. To avoid this issue, for all values of we always use the initial Hessian inverse upproximation matrix corresponding to the first phase with my samples and set H = H = Rmmo (Wma) ( even under this initialization the required condition for superlinear convergence of DFP or BFGS is always satisfied if the initial sample size mo is large enough. Note that by following this scheme, we only need compute my Hessians and a single matrix inversion to implement AdaQN. This is significant gain compared to Ada Newton in (21), which requires computing ( Hessians and (log N) matrix inversions.
(Step 3). We show that
4 Convergence analysis
In this section, we characterize the overall complexity of AdaQN. We only state the results for BFGS defined (6. as the proof techniques and overall complexity bounds for adaptive sample size versions of DFP and BFGS are similar.
First we state an upper bound for the sub-optimality of the variable Wm with respect the empirical risk of Ra, given that wm has achieved the statistical accuracy of the previous empirical risk Rmn-
Proposition 1. Consider Sm and S. such that Sm C Sn TT where there are m. samples in Sm and n samples in Sn and defined based on Sm and Sn, respectively. Assume that Wm solves the ERM problem of Rm within its statistical accuracy, i.e., EE [Rm (W.)) -Rm (wn)),,) S Vn. Then we have R., (w,,) 3Vm.
m. Consider the corresponding empirical risk functions Rm and Rn
E [Rn
Proposition [ characteriies the sub-optimality of the variable Wm. for the empirical risk Rr which plays fundamental role in our analysis. We use this bound later to show Wm. is close enough to w so that wm. is in the superlinear convergence neighborhood of Rn.
Next, we require bound on the number of iterations needed by BFGS to solve subproblem, when the initial iterate is within the superlinear convergence neighborhood. We establish this bound by leveraging the result of [24] which provides non- asymptotic superlinear convergence for BFGS.
Proposition 2. Consider AdaQN in the phase that the active training set contains samples. If
Assumptions
2 hold and the initial iterate wm m and Hessian approximation 22 R2Rmo (Win) satisfy
2 Rn, (w))+ (Wm - -w,,ll S 300
(8)
1 Rn + Rmg (Wmo) 2 Ru Bn(ww, (n( (w;) +11 S 7'
then after by iterations we achieve the output w,, with the following convergence result
RA (w(w))) RR, (w;) I 1.1
RR (w.)
-R,, (w.))
tn
Proposition 2 shows that the initial Hessian approximation error is small and the initial iterate close to the optimal solution, then the iterates of BFGS with step size 1) 1 converge to the optimal

---

solution at superlinear rate of (1/k)* after k iterations. The inequalities in (8) identify the required conditions to ensure that wm is within the superlinear convergence neighborhood of BFGS for R.
In the next two propositions we show that if the initial sample size mg is sufficiently large, both W and 2 Rm (Wmg) satisfy the conditions in (8) in expectation which are required to achieve the local superlinear convergence.
Proposition 3. Consider Algorithm ffor the phase that the active training set contains n samples with empirical risk Ry, Suppose Assumptions 7 2 hold, and further suppose we are given wm which is within the statistical accuracy of Rm. i.e, E Rm (Wm) - Rmm (W (m)) S Vm, and n. = 2m. If the
sample size m is lower bounded by m = 52 (n² log d), then
E R'" (wm will| S 300
(10)
Proposition shows that if the training set size is sufficiently large. then the solution of the previous phase is within the BFGS superlinear convergence neighborhood of the current problem, and the first condition in (8) holds in expectation. This condition indeed satisfied throughout the entire learning process, if it holds for the first training set with mo samples, i.e., ma 52 (R² dl.
Next we establish under what condition the Hessian approximation used in adaptive sample size method which is the Hessian evaluated with respect to mo samples, i.e. V Rmo (Wmg). satisfies the second condition in K in expectation which required for the superlinear convergence of BFGS.
Proposition Consider AdaQN the phase that the active training set contains samples. If hold and the initial sample size my satisfies mn = Ω (max {d, log d)), where
Assumptions 7
R. (w) [w)]l" Then for any 2 2mo we have
8 is defined as == supw.n
(w)
E Ro (w $ 2 Rmp (Wmo) -
V Ro (w Ru (w;)
||
S
1 7
(1I)
Based on Proposition 4 if the size of initial training set satisfies mo Ω (max fd, x²g log d then the second condition in (8) holds in expectation. By combining the results of Propositions 3 and 4
we obtain the required conditions for me. Moreover, Proposition 2 quantifies the maximum number
of iterations required to solve each ERM problem to its corresponding statistical accuracy. In the following theorem, we exploit these results to characterize the overall computational complexity of AdaQN to reach the statistical accuracy of the full training set with N samples.
Theorem 1. Consider AdaQN described in Algorithm for the case that we use BFGS updates in hold, and the initial sample size my lower bounded by
6). Suppose Assumptions 7 2
mo Z (max {d, x² ssloog)) dog);),
(12)
(w) H(w)ll) 2
(w) [I)
where 8 s11P
Then at the stage with n. samples, AdaQN finds w.
within the statistical accuracy of Rn, after at most In = 3 iterations. Further, the computational cost of AdaQN reach the statistical accuracy of the full training set T is
Time + MoTHess 6N GNNg + +3( (1 + log(Nooo)) Tprod-
(13)
Theorem states that if the initial sample size is sufficiently large, the number of required BFGS updates for solving each subproblem is at most iterations. Further, it characterizes the overall computational cost of AdaQN.
Remark 2. Since 11 Vāll Il, parameter in Theorem i belongs to the interval [L, d). Hence, in the worst case d and ma Ω log However, for many common classes of problems including linear regression and logistic regression and for training datasets with specific structures could be O1). In those cases the initial sample size is lower bounded by Ω (max dd, x² log d) )) see Section in the appendix for details. In fact, our numerical experiments also verify this observation and show That the choice of my could be much smaller than the worst-case bound of mo = St (x²2 log d): see Section 5
7

---

Remark 3. In the above complexity bound, we neglect the cost of finding the initial solution w mm-- as the cost of finding an approximate solution for the first ERM problem with my samples is negligible compared to the overall cost of the AdaQN, For instance, if one solves the first ERM problem using the Katyusha algorithm fTZY, the cost of the initial stage would be O (Tgraa (mo + b -Moghano log mo) (where Komg is the condition number for ERM with my samples), which is indeed dominated by the term O (NTgra)), when we are in the regime that N >> ma.
Remark 4. If one uses Katyusha, which is an optimal first-order method, to solve an ERM with N samples, the overall gradient computation to achieve accuracy e VN would be O(NN VNK) log N). The gradient computation cost of AdaQN considering the initialization step is O(((mg + <mok) log ma) + +N). Indeed, if we are in the regime that the size of initial set my is sufficiently smaller than the size of full training set N, (i.e., N 2 mg log me). then AdaQN gradient complexity scales as O(N + -magk log ma) which is smaller than ( log N + V re log N) cost of Katyusha. However, AdaQN requires evaluating one additional matrix inversion, my Hessian evaluations and O (log (N/ mm))) matrix-vector product computations.
5 Numerical experiments
Next, we practically evaluate the performance of AdaQN to solve large-scale ERM problems. We consider a binary classification problem with (2 regularized logistic regression loss function, where a > 0 is the regularization parameter. The logistic loss is convex, and, therefore, all functions in our experiments are μ-strongly convex. We normalize all data points with the unit norm that the loss function gradient is Lipschitz continuous with L S μ + 1, hence condition number is K S 51 + 1/p. Moreover, the logistic regression loss function is self-concordant. Thus, Assumptions
hold.
We compare AdaQN with adaptive sample size Newton method (Ada Newton) 21, standard BFGS quasi-Newton method, the L-BFGS
method (28), the stochastic quasi- Newton (SQN)
method proposed in (29), and three stochastic first-order methods, including stochastic gradient descent (SGD), the Katyusha algorithm (1). and SAGA which is a variance reduced method [7). In our experiments, we start with the initial point wo c * I where > 0 is tuned parameter and I E Rd is the one vector. First we conduct several iterations of the gradient descent method on the initial sub-problem with mo samples until the initial condition | Rmg (Wmo)) S V /2uVm. is satisfied. Note that Rmo (Wma) - Rmg (w* ) I 1 Rmo (Wm.) I implies that this initial condition guarantees Wmg is within the statistical accuracy of Rmg. We use Wmg the initial point of AdaQN and Ada Newton as presented in Algorithm [ We use Wo = c+ I as the initial point of all other algorithms. We include the cost of finding the proper initialization for AdaQN in our comparisons. We compare these methods over (i) MNIST dataset of handwritten digits [30], (ii) Epsilon dataset from PASCAL challenge 2008 B3. (iii) GISETTE handwritten digit classification dataset from the NIPS 2003 feature selection challenge 32 and (iv) Orange dataset of customer
relationship management from KDD Cup 2009 (33 More details provided in Table 2
In our experiments, observe that even when the initial sample size mo is smaller than the threshold in 12). AdaQN performs well and converges superlinearly in each subproblem. This is because (12)
sufficient condition guarantee our theoretical superlinear rate, and in practice smaller choices of mo also work. For Ada Newton we use the same scheme descried in Algorithm I and replace the
QN update with Newton's method with step size 1. The step sizes of the standard BFGS method and the L-BFGS method are determined by the Wolfe condition [35] using the backtracking line search algorithm to guarantee they converge on the whole dataset. All hyper-parameters (initialization parameter step size, batch size, etc.) of BFGS, L-BFGS, stochastic quasi-Newton method, SGD, SAGA, and Katyusha have been tuned to achieve the best performance on each dataset.
The convergence results are shown in Figures 4 for the considered datasets. We report both training error, i.e., Rx passes over dataset and in terms of runtime. In general AdaQN mostly outperforms the first-order optimization methods (SGD, Katyusha and SAGA). This is caused by the fact that our considered problems are highly ill-conditioned. For instance, for the results of Epsilon dataset which has k R 10 there is substantial gap between the performance of AdaQN and first-order methods.
Ry (wx), and test error for all algorithms in terms of number of effective
We use LIBSVM 34 with license: httpp:: www. ntu. edu.
www.ddwww.eeeeeeeeeeeeeeeeeeeeee tw/ wt/rejj1amm1bbmmm000/...t
8

---

Table Datasets information: sample size N, dimension d, initial set size my and regularization μs.
Dataset
N
d
1/1
MNIST
11774
784
1024
0.05
GISETTE
6000
5000
1024
0.05
Orange Epsilon
40000
14000
8192
0.1
80000
2000
4096
0.0001
Sote: J01000
Nuccer Puaus ene Trakiing Dotiane
Mtcche of Prans one Thiiding Doctant
Figure I: Training error (first two plots) and test eтrоr (last two plots) in terms of number of passes dataset and runtime for MNIST dataset.
Heros
RETOR
Role) Bo003
Tosk Ente
BOOK
Ntmber Thume Tratiin Domase
Barthea
Ntrcher Paans Thiniig Duttant
Figure 2: Training eтror (first two plots) and test eπrоr (last two plots) in terms of number of passes over dataset and runtime for GISETTE dataset.
Rowe: Recong
Eir
Figure 3: Training error (first plots) and test error (last two plots) in terms of number of passes over dataset and runtime for Orange dataset.
g
Banthaa
Figure 4: Training error (first plots) and test error (last two plots) in terms of number of passes over dataset and runtime for Epsilon dataset.
We observe that AdaQN outperforms BFGS, L-BFGS and SQN in considered settings. As discussed earlier, this observation is expected since AdaQN is the only quasi-Newton algorithm among these methods that exploits superlinear convergence of quasi-Newton methods throughout the entire training process. Moreover, AdaQN does not require a line search scheme, while to obtain the best performance BFGS and L-BFGS, we used a line-search scheme which often computationally costly.
Next we compare Ada Newton and AdaQN, As shown in Figure for the MNIST dataset with low dimension (d = 784) and moderate number of samples (N ~ T1000), AdaQN performs very similar Ada Newton. However, for settings where either the problem dimension d the number of samples N is very large AdaQN outperforms Ada Newton significantly in terms of runtime. For instance, in Figures 2 and 3 which correspond to GISETTE dataset with N 6000 samples and d = 5000 features and Orange dataset with N 40000 samples and d = 14000 features, Ada Newton and AdaQN have almost similar convergence paths when compared in terms of number of passes data, but in terms of runtime AdaQN is substantially faster than Ada Newton. This gap

---

comes from the fact that in these two examples the problem dimension d is large and as a result the cost of inverting a matrix at each iteration, which required for Ada Newton, prohibitive.
For Epsilon dataset that has a relatively large number of samples N = 80, 000 and moderate dimension d 2000, as shown in Figure 4 Ada Newton outperforms AdaQN in terms of number of passes over data in both training and test errors. However, their relative performance is reversed when we compare them in terms of runtime. This time the slow runtime convergence of Ada Newton is due to the fact that sample size N is very large. Note that Ada Newton requires 2NV Hessian computations, while for AdaQN we only need my Hessian evaluations.
Remark 5. Theoreml 7 requires the size of the initial training set my to satisfy the condition in In our experiments, however, we observe that ma could be much smaller than the threshold in We believe that the main reason for this mismatch is that the recent non-asymptotic convergence analysis of BFGS that we exploit in our analysis may not be tight, and there is room for improving this bound. Specifically, establishing a less strict condition on the initial Hessian approximation error of BFGS required for achieving a superlinear convergence rale could lead a much smaller lower bound for the parameter. Another possible reason for the gap between our theory and experiments is that our analysis is worst-case analysis and it studies a lower bound that works for any setting. There could be some hard instances or corner cases that our current experiments do not capture, and for these hard instances we might need the number of samples required by our theoretical study. Identifying hard instances of empirical risk minimization problems for which larger initial sample size is required is research direction that requires further investigation.
12
12)
Discussion and future work
We proposed AdaQN algorithm that leverages the interplay between the superlinear convergence of quasi-Newton methods and statistical accuracy of ERM problems to efficiently minimize the ERM corresponding to a large dataset. We showed that if the initial sample size mo is sufficiently large, then we can double the size of training set at each iteration and use BFGS method to solve ERM subproblems, while we ensure the solution from previous round stays within the superlinear convergence neighborhood of the next problem. As a result, each subproblem can be solved with at most three BFGS updates with step size 1. In comparison with Ada Newton, AdaQN has three major advantages. (I) Ada Newton requires backtracking technique while for AdaQN we can double the size of training set if the size of initial set is sufficiently large. (II) Ada Newton implementation requires computing the Hessian inverse each iteration, while AdaQN only requires computing a single matrix inversion. (III) Ada Newton requires 2.N Hessian computations overall, while AdaQN only needs mg Hessian evaluations at the initialization step.
determine the growth factor,
In this paper, we showed that using quasi-Newton methods we only require constant number of iterations that is independent of the condition number K and the dimension d to solve each subproblem to its statistical accuracy. More specifically, as the superlinear convergence rate of (1/ (1VV)) for BFGS independent of the problem parameters, each subproblem can be solved with at most three iterations. On the other hand, any other second-order method that enjoys a local convergence rate (either linear or superlinear) that is independent of the problem parameters could be capable of solving each subproblem to its statistical accuracy with a finite constant number of iterations that is independent of the condition number R and dimension d. Hence, studying the application of such second-ordes or quasi-Newton methods for the considered adaptive sample size scheme is an interesting direction of research that requires further investigation.
One limitation of our results is that AdaQN provably outperforms other benchmarks only in the regime that N >> max {d, x²x log d) This due to the lower bound on the size of initial training set mg- Notice that in many large-scale learning problems where N is extremely large, this condition usually holds. We believe this limitation of our analysis could be resolved by tighter non-asymptotic analysis of BFGS method. Morcover, our guarantees only hold for convex settings and extension of our results to nonconvex settings for achieving first-order or second-order stationary points is a natural future direction.
Acknowledgement
This research is supported in part by NSF Grant 2007668, ARO Grant W91 N991NN2110N 10226, the Machine Learning Laboratory at UT Austin, and the NSF AI Institute for Foundations of Machine Learning.
10

---

References
[1] V. Vapnik, The nature of statistical learning theory. Springer Science & Business Media, 2013.
[2] O. Bousquet, "Concentration inequalities and empirical processes theory applied to the analysis of learning algorithms," PhD thesis, Ecole Polytechnique. 2002.
[3] P. L.. Bartlett, M. I. Jordan, and J. D. McAuliffe, "Convexity, classification, and risk bounds," Journal of the American Statistical Association, vol. 101, no. 473, pp. 138-156, 2006.
[4] O. Bousquet and L. Bottou, "The tradeoff's of large scale learning," in Advances in Neural Information Processing Systems, pp. 161-168, 2011.
[5] R. Frostig, R. Ge, S. M. Kakade, and Sidford, "Competing with the empirical risk minimizer in single pass," in The Conference on Learning Theory, pp. 728-763, 2015.
[6] N. Le Roux, M. Schmidt, and F. Bach, "A stochastic gradient method with an exponential convergence rate for finite training sets," in Advances in neural information processing systems, pp. 2663-2671, 2012.
[7] A. Defazio, F. Bach, and S. Lacoste-Julien, "SAGA: A fast incremental gradient method with support for non-strongly convex composite objectives," in Advances in Neural Information Processing Systems, pp. 1646-1654, 2014.
[8] R. Johnson and T. Zhang, "Accelerating stochastic gradient descent using predictive variance reduction," in Advances in Neural Information Processing Systems 26, pp. 315-323, 2013.
[9] S. Shalev-Shwartz and T. Zhang, "Stochastic dual coordinate ascent methods for regularized loss," The Journal of Machine Learning Research, vol. 14, pp. 567-599, 2013.
[10] L. M. Nguyen, Liu, K. Scheinberg, and M. Takáč, "SARAH: A novel method for machine learning problems using stochastic recursive gradient," in International Conference on Machine Learning, pp. 2613-26211 PMLR, 2017.
[11] Z. Allen Zhu, "Katyusha: the first direct acceleration of stochastic gradient methods," " in Proceedings of the 49th Anmual ACM SIGACT Symposium on Theory of Computing, STOC 2017, Montreal. QC, Canada, June 19-23, 2017, pp. 1200-1205, 2017.
[12] C. Fang, C. Li, Z. Lin, and T. Zhang. "Near-optimal non-convex optimization via stochastic path integrated differential estimator," Advances in Neural Information Processing Systems, vol. 31, p. 689, 2018
[13] A. Cutkosky and F. Orabona, "Momentum-based variance reduction in non-convex sgd," Ad- vances in neural information processing systems, vol. 32, 2019.
[14] M. Gürbüüzaalaaan, A. Ozdaglar, and P. Parrilo, "A globally convergent incremental Newton method," Mathematical Programming, vol. 151, no. 1, pp. 283-313, 2015.
[15] M. A. Erdogdu and A. Montanari, "Convergence rates of sub-sampled Newton methods," " in Advances in Neural Information Processing Systems 28: Annual Conference Neural Information Processing Systems 2015, Montreal, Quebec, Canada, pp. 3052-3060, 2015.
[16] N. N. Schraudolph, J. Yu, and S. Günter, "A stochastic quasi-Newton method for online convex optimization," in Proceedings of the Eleventh International Conference on Artificial Intelligence and Statistics, AISTATS 2007, San Juan, Puerto Rico, March 2 21-24, 2007, pp. 436-443, 2007.
[17] A. Mokhtari and A. Ribeiro, "Res: Regularized stochastic BFGS algorithm."" " IEEE Transactions on Signal Processing, vol. 62, no. 23, pp. 6089-6108 2014.
[18] A. Mokhtari and A. Ribeiro, "Global convergence of online limited memory bfgs," The Journal of Machine Learning Research, vol. 16, no. 1, pp. 3151-3181, 2015.
[19] P. Moritz, R. Nishihara, and M. I. Jordan, "A linearly-convergent stochastic L-BFGS algorithm," in Proceedings of Int. Conference on Artificial Intelligence and Statistics, AISTATS, pp. 249-258, 2016.
11

---

[20] A. Mokhtari, M. Eisen, and A. Ribeiro, "IQN: An incremental quasi-Newton method with local superlinear convergence rate," SIAM Journal on Optimization, vol. 28, no. 2, pp. 1670-1698, 2018.
[21] A. Mokhtari, H. Daneshmand, A. Lucchi, T. Hofmann, and A. Ribeiro, "Adaptive Newton method for empirical risk minimization to statistical accuracy," in Advances in Neural Informa- fion Processing Systems, pp.
2016.
[22] A. Rodomanov and Y. Nesterov, "Rates of superlinear convergence for classical quasi-newton methods," Mathematical Programming, pp. 1-32, 2021.
[23] A. Rodomanov and Y. Nesterov, "New results on superlinear convergence of classical quasi- newton methods," " Journal of Optimization Theory and Applications, vol. 188, no. pp. 744- 769, 2021.
[24] Q. Jin and A. Mokhtari, "Non-asymptotic superlinear convergence of standard quasi-newton methods," arXiv preprint arXiv:2003. /3607, 2020.
[25] M. Derezinski, D. Mahajan, S. S. Keerthi, S. V. Vishwamathan, and M. Weimer, "Batch- expansion training: an efficient optimization framework," International Conference on Artificial Intelligence and Statistics, pp. 736-744, 2018.
[26] A. Mokhtari and A. Ribeiro, "First-order adaptive sample size methods to reduce complexity of empirical risk minimization," in Advances in Neural Information Processing Systems, pp. 2060- 2068, 2017.
[27] W. S. Lee, P. L. Bartlett, and R. C. Williamson. "The importance of convexity in learning with squared loss," IEEE Transactions on Information Theory, vol. 44, no. 5, pp. 1980, 1998.
[28] D. C. Liu and J. Nocedal, "On the limited memory BFGS method for large scale optimization." Mathematical programming, vol. 45, no. 1-3, pp. 503-528, 1989.
[29] R. H. Byrd, S. Hansen, J. Nocedal, and Y. Singer. "A stochastic quasi-Newton method for large-scale optimization," SIAM Journal on Optimization, vol. 26, no. 2, pp. 1008-1031, 2016.
[30] Y. LeCun, C. Cortes, and C. J. Burges, "MNIST handwritten digit database," AT&T Labs [Online]. Available: http://aam.eccu..cmm/eee//////
2010.
[31] Epsilon, "Pascal large scale learning challenge," http://www.kallloogppreeelrreeee 2008
[32] G. Isabelle, G. Steve, H. Asa, Ben, and D. Gideon, "Result analysis of the nips 2003 feature selection challenge," " Advances In Neural Information Processing Systems, Volumn 17, 2005.
[33] R. Féraud, M. Boullé, Clérot, F. Fessant, and Lemaire, "The orange customer analysis platform," JMLR WCP, Volume 7, KDD cup 2009, Paris, 2009.
[34] C.-C. Chang and C.-J. Lin, "Libsvm: A library for support vector machines." ACM Transactions on Intelligent Systems and Technology, Article 27, 2011.
[35] R. H. Byrd, J. Nocedal, and Y.-X. Yuan, "Global convergence of a class of quasi-Newton methods on convex problems," " SIAM Journal on Numerical Analysis, vol. 24, no. 5, pp. 1171- 1190, 1987.
[36] J. A. Tropp, "An introduction to matrix concentration inequalities," Volume 8, Issues 1-2 of Foundations and trends machine learning, 2015.
[37] Y. Nesterov, Introductory lectures on convex optimization, vol. 87. Springer Science & Business Media, 2004.
12


Reviews:
[{"review_id": "nCMbRif0Cv", "reviewer": "Reviewer_4SN8", "summary": "This paper \n- introduces a new quasi-Newton (QN) algorithm called AdaQN to solve the ERM problem. This method is adaptive since it increases the sample size after few (3) runs of BFGS on a small ERM subproblem. \n- gives its corresponding convergence analysis using a Matrix Bernstein bound\n- explains that AdaQN perfoms well because of the superlinear convergence on each subproblem which is possible when $m_0$ is large enough (greater than $\\mathcal{O} (\\kappa^2 log (d))$ if we leave out $s$)\n- provides clear comparison in term of theoretical computational cost is made against AdaNewton in Table 1 \n- performs numerical experiments showing the efficiency of the methods on small and medium size problems for l2 regularized logistic regression", "questions": "", "limitations": "", "rating": 7, "confidence": 5, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "The paper is really clear. \nI really liked the idea of exploiting this local superlinear convergence of the QN methods successively, by having $S_1 \\subset S_2 \\subset ...$. The paper explains carefully its concepts, its algorithm implementation compares its cost against AdaNewton and then provides an easy to follow convergence analysis.\n\nMy first main concern (that I will develop below) is that the condition on $m_0$ that is $m_0 = \\Omega (\\kappa^2 s\\log d)$ is to my opinion completely undermined by the authors. \nMy second main concern is the experimental part wish I find unclear and unfair. I develop this below.\n\n\nHere are some comments, critics and questions:\n\nStyle/typo comments:\n- 1) lines 37 and 74/75: not consistent writing of Quasi-Newton / quasi-Newton\n- 2) line 48, not nice looking line because of \\emph\n- 3) line 77: missing word before reference [20]\n- 4) line 106: ERM already defined earlier\n- 5) line 111: $w^*$ is an optimal solution of the expected risk minimization. The authors will agree that $R$ is a function not an optim problem\n- 6) line 264: typo, remove \"the\"\n- 6 bis) line 552-553: strangely few lines are not numbered + typo \" inequality(notice)\" also there at line 570\n\nMinor comments:\n- 7) line 77: What did you mean when saying \"To exploit quasi-newton methods for the described adaptive sample scheme, however ...\" ? To be corrected I think\n- 8) line 7 of Algo. 1: a break-line for $y$ would make it way easier to read\n- 9) $\\mu$ is not really standard for a regularization parameter, I would prefer $\\lambda$ then say $\\mu \\approx \\lambda$\n- 9 bis) line 373: cite maybe the most recent version of Bottou and Bousquet 2011\n\nMajor comments:\n- 10) A long comparison is made against AdaNewton, yet very few comparison is made agaisnt other (stochastic) QN methods like L-BFGS, which is known to perform very well in a lost of case, or the more recent K-BFGS (\"Practical quasi-newton methods for training deep neural networks\", Goldfarb, Ren, Bahamou, 2020) or Stochastic Block BFGS (Stochastic Block BFGS: Squeezing More Curvature out of Data, Gower, Goldfarb, Richtarik, 2016) \n- 11) My main concern (that I will develop below) is that the condition on $m_0$ that is $m_0 = \\Omega (\\kappa^2 s\\log d)$ is to my opinion completely undermined by the authors.  I would have liked a clear explanation about what happens when we are facing a very ill-conditioned problem such that $\\kappa = N$ or even worse  $\\kappa >> N$. What does AdaQN become in such a case ? Does it become QN with a constant sample size $m\\equiv N$ ? In this case isn't it way more costly than 1st order methods ? What about numerical experiments in this case ?\n- 12) In Prop. 1 and elsewhere in the paper, you clearly explain that having $S_1 \\subset S_2 \\subset ...$ is necessary for AdaQN to work. I have been through the proof and I was expecting that you would have to deal with a problem : at each outer loop iteration the points are \\textbf{not} sampled independently. How is that it does not appear in your proof ?\n- 13) Remark 4: Don't you omit the matrix inversions and the matrix vector product required by AdaQN when comparing it to Katyusha ? In other words, is this comparison of gradient complexity really fair between a first and a second order method ? \n- 14) How can you get a condition number which equals 1 in your experiments ? Normalizing can improve the condition number, but I have never seen such a bound related to just simple normalization.\n- 15) It is not clear what is monitored by \"time\" in your experiments. So I have been into the code and I noticed that the initialization which requires inverting the first hessian is not taken into account... In addition, SAGA is not initialized with a full gradient step, plus SAGA algorithm was launched with a decreasing step size which is unnecessary. This is one of the main advantage of VR methods. This is wat I really doubt about the fairness of the experiments.\n- 16) In all your experiments $N$ is at most of medium size, you should have tried on RCV1.binary for instance $N = 600K$ to see if first order methods are still performing poorly compared to AdaQN.\n- 17) Regularization parameters in table 2. look way to large... It is not representing the range of lambda used in practice. I would recommend $10^{-4}$ or $10^{-6}$. Moreover we could maybe see this way an experiment with large $\\kappa$\n\n\nQuestions:\n- 18) Why is AdaQN adaptive since you basically double the sample size at each iteration, so it's not dependent on anything else than the current number of samples m ?\n- 19) Why didn't you include L-BFGS in your experiments ? \n- 20) With is your initial point set to 1 in your experiments ?\n\n---------------------------------------------------------------------------------------------------------------\n\n**Update after rebuttal and exchanges with the authors and the other reviewers**\n\nMain concerns I had about experimental settings, I think have been addressed. I think the authors must detail the experimental settings in the appendix such that the community can understand their numerical experiments and really be convinced that the settings are fair. \n\nDespite the discussion on the practical \"leveraging of superlinearity\", I finally decide to **increase my score** but only up **to 6**. \n\n\n---------------------------------------------------------------------------------------------------------------\n\n**Final words**\n\nIn his updated review, reiewer RQBF wrote :\n\n>   [...] after a discussion with the authors I concluded that the BFGS Hessian updates have basically no effect on the complexity analysis.\n\nI agree with him on this point (and I think the authors too). Yet on my side, this discussion does not diminish the ideas nor the quality of the paper. Moreover, as I said above, my concerns about numerical experiments will be addressed in the final version of the paper (with fairer comparisons). My final thoughts about the paper are that despite this concern about superlinarity, it can be very profitable for the QN community and optimizers interested in adaptive mini-batch/sample size. \nHence, I increase my score to 7 and argue in favor of accepting this paper with one condition : a clear and important remark about this discussion on superlinearity must be added and highlighted.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "The authors did not really talk about the case where $m_0$ is in fact large. \nNo real experiments for very ill-conditioned problem.\n ", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "9"}, "extra_text": {}}, {"review_id": "RX6ABfoopZK", "reviewer": "Reviewer_rmWp", "summary": "This paper introduces an adaptive sample size quasi-Newton (AdaQN) method that exploits the superlinear convergence of quasi-Newton methods globally and throughout the entire learning process. The authors also provide convergence analysis to verify the AdaQN method, showing less gradient computation, as well as computational cost compared with previous SOTA methods. The numerical experiments on various datasets also confirm their theoretical findings.\n", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "\nI consider this work gives an effective QN method through interesting intuition using adaptive sample size. Adopting adaptive sample size arises in previous works [1], but not for Quasi-Newton methods, and it indeed provides convincing results. Therefore, I still approve of the originality of this work. Moreover, the work is well-written and has high quality and clarity.\n\nThe exploitation of the superlinear convergence of quasi-Newton methods globally is an important problem in my view. As far as I know, previous results build on a small local neighborhood of the optimal solution as the authors mentioned. Therefore, the significance of this work is undoubted.\n\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "The only concern is the mismatching of m0 in experiments and theory. At first glance from Theorem 1, I consider such an m0 is only suitable for the well-conditioned case that $N \\geq \\kappa^2\\log d$. However, the numerical experiments show that the initial sample size m0 could be much smaller than the threshold.  Although the authors believe this limitation could be resolved by a tighter non-asymptotic analysis of the BFGS method, I could not believe the explanation from the large gap in theory and experiments. Thus I keep a conservative assessment.\n\nOverall, I am willing to defend my assessment and am unfamiliar with some pieces of related work. Proof details were not carefully checked.\n\n[1] Mokhtari, A., & Ribeiro, A. (2017, December). First-order adaptive sample size methods to reduce complexity of empirical risk minimization. In Proceedings of the 31st International Conference on Neural Information Processing Systems (pp. 2057-2065).\n", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "8"}, "extra_text": {}}, {"review_id": "-KtAxVzPy0b", "reviewer": "Reviewer_RQFB", "summary": "The paper proposes an optimization method for empirical risk minimization, combining two techniques from the literature: (1) adaptive sample sizes, where the optimization algorithm is initially ran on a small batch of data, which is then gradually increased by doubling it every couple iterations; and (2) quasi-Newton methods for updating the iterates, such as the BFGS algorithm. The authors leverage recent results on non-asymptotic local convergence analysis of BFGS and show that with an appropriate choice of sample size, the quasi-Newton method will stay in its local convergence regime throughout the optimization, leading to strong convergence guarantees.", "questions": "", "limitations": "", "rating": 5, "confidence": 5, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Thank you to the authors for the response and the following discussion. The authors have clarified that superlinearity of BFGS is not needed to establish their results, and they promised to clarify this in the paper, which is good. They also promised to include in the future version of the paper a discussion and empirical results comparing to the prior work of [DMKVW18], which is appreciated. On the other hand, in my view a significant part of the technical novelty of the approach rested on the apparent reliance on the superlinear nature of the BFGS updates, but after a discussion with the authors I concluded that the BFGS Hessian updates have basically no effect on the complexity analysis. This weakens the paper in my view. Thus, all in all, I maintain my score.\n\nFirst, there is one important related work that is missing from the literature review, namely [DMKVW18]. In fact, that paper is to my knowledge the first to propose using adaptive sample sizes with a quasi-Newton method (in their case, L-BFGS). However, it does not provide a convergence analysis that is specific to any particular quasi-Newton method, which is the main contribution of the present submission. Instead, they show that if for each sample size an optimizer exhibits a convergence rate of at least, say, (1/2)^t, then one should double the sample size at each stage after a constant number of iterations (same as in the present submission). Thus, in principle, one could combine that result with the recent work on local convergence rates of BFGS [21-23] to establish a guarantee analogous to the one obtained by the authors. Of course, this is by no means straightforward, but it should at least be addressed in the submission. I would also be interested to see an empirical comparison of AdaQN with the BET method proposed by [DMKVW18] (ran with L-BFGS), since that can be considered as the closest baseline from the literature.\n\nSecond, I take issue with the claim that the proposed approach “exploits the superlinear convergence” of quasi-Newton methods. As the authors discuss, the superlinear convergence of BFGS takes the form of roughly (1/t)^t, where t is the number of iterations performed in one stage of Algorithm 1. However, since the algorithm performs only 3 iterations per stage, then it has no opportunity to exploit superlinear convergence, and all you actually obtain is linear convergence that is independent of the condition number. In fact, the proposed analysis demonstrates that the superlinear convergence doesn’t really matter here, because we reach statistical accuracy before it kicks in. So, I think the authors should not say that the algorithm is “exploiting the superlinear convergence”, but it is ok to say that the algorithm is “exploiting local convergence”, because that is still very much accurate. \n\nThe above discussion about the lack of true superlinear convergence highlights another issue with the algorithm, namely, with the way that the Hessian estimate is being updated. Basically, what the authors propose is that every stage is initialized with the Hessian estimate computed from the smallest sample size (stage 1), then three iterations of BFGS slightly improve that estimate, and then it goes back to the original one. This seems strange. Why not continue with the improved estimate and keep updating it with the BFGS updates? The authors partially address this in Remark 1, pointing out that the initial Hessian estimate is good enough to ensure the local convergence phase of BFGS. But then what is the point of the three updates to the estimate? In fact, I’m quite convinced that the convergence guarantee from Theorem 1 can be shown for the method that just uses the initial Hessian estimate without every updating it. But then, this is no longer BFGS or even quasi-Newton. This is why, in my view, the paper is to a certain extent misrepresenting the nature of why the proposed method achieves the convergence it achieves.\n\nOverall, the strategy of combining adaptive sample sizes with quasi-Newton methods is very interesting, and it is very nice to have a complete convergence analysis of an algorithm that follows that strategy. However, I do have some serious concerns regarding the novelty and presentation of this paper. I am open to reconsider the score if those concerns are addressed in the response.\n\n[DMKVW18] M. Derezinski, D. Mahajan, S. S. Keerthi, S. V. N. Vishwanathan, and M. Weimer. \"Batch-expansion training: an efficient optimization framework.\" In International Conference on Artificial Intelligence and Statistics, pp. 736-744, 2018.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Yes.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "6 hours"}, "extra_text": {}}]

Author rebuttal:

Meta-review: This paper focuses on characterizing rates of convergence for Quasi-Newton method applied to empirical risk minimization. Traditional stochastic Quasi-Newton methods have not enjoyed guarantees that are faster than their first order counterparts. This paper uses an adaptive sampling scheme to achieve global superlinear convergence. All reviewers thought the idea of combining adaptive sampling with Quasi-Newton methods is interesting and appreciated the thorough global convergence analysis. The reviewers did however raise a few concerns including: (1) one reviewer had concerns about the claim that the proposed approach “exploits the superlinear convergence” of quasi-Newton methods, (2) lack of discussion of some related literature, (3) mismatch in m0 between theory and practice, and (4) a variety of other technical discussions. The authors provided a thorough response and the reviewers had a lively discussion with the authors and together. As a result some of the above issues were resolved and some reviewers raised their score. Issue number (1) however remained and that reviewer increased their score contingent on this issue being revised in the final version. I agree for the most part with the reviewers that the paper is interesting and clearly written with nice results. But also concur with them about the technical issues and that claims of exploiting superlinearity are a bit misleading. Therefore I recommend acceptance with the requirement that a clear discussion on superlinearity must be highlighted in the paper.
Decision: Accept (Poster)