Geometric descent method for convex composite minimization

Introduction

Recently, Bubeck, Lee and Singh proposed a geometric descent method (GeoD) for minimizing a smooth and strongly convex function . They showed that GeoD achieves the same optimal rate as Nesterov’s accelerated gradient method (AGM) . In this paper, we provide an extension of GeoD that minimizes a nonsmooth function in the composite form:

If $h$ vanishes, then the objective function of (1.1) becomes smooth and strongly convex. In this case, it is known that AGM converges with a linear rate $(1-1/\sqrt{\kappa})$, which is optimal among all first-order methods, where $\kappa=\beta/\alpha$ is the condition number of the problem. However, AGM lacks a clear geometric intuition, making it difficult to interpret. Recently, there has been much work on attempting to explain AGM or designing new algorithms with the same optimal rate (see, ). In particular, the GeoD method proposed in has a clear geometric intuition that is in the flavor of the ellipsoid method . The follow-up work attempted to improve the performance of GeoD by exploiting the gradient information from the past with a “limited-memory” idea. Moreover, Drusvyatskiy, Fazel and Roy showed how to extend the suboptimal version of GeoD (with the convergence rate $(1-1/\kappa)$) to solve the composite problem (1.1). However, it was not clear how to extend the optimal version of GeoD to address (1.1), and the authors posed this as an open question. In this paper, we settle this question by proposing a geometric proximal gradient (GeoPG) algorithm which can solve the composite problem (1.1). We further show how to incorporate various techniques to improve the performance of the proposed algorithm.

The rest of this paper is organized as follows. In Section 2, we briefly review the GeoD method for solving smooth and strongly convex problems. In Section 3, we provide our GeoPG algorithm for solving nonsmooth problem (1.1) and analyze its convergence rate. We address two practical issues of the proposed method in Section 4, and incorporate two techniques: backtracking and limited memory, to cope with these issues. In Section C, we report some numerical results of comparing GeoPG with Nesterov’s accelerated proximal gradient method in solving linear regression and logistic regression problems with elastic net regularization. Finally, we conclude the paper in Section 6.

Geometric Descent Method for Smooth Problems

The GeoD method solves (1.1) when $h\equiv 0$, in which the problem reduces to a smooth and strongly convex problem $\min\ f(x)$. We denote its optimal solution and optimal value as $x^{*}$ and $f^{*}$, respectively. Throughout this section, we fix $t=1/\beta$, which together with $h\equiv 0$ implies that $x^{+}=x-\nabla f(x)/\beta$ and $x^{++}=x-\nabla f(x)/\alpha$. We first briefly describe the basic idea of the suboptimal GeoD. Since $f$ is $\alpha$-strongly convex, the following inequality holds

By letting $y=x^{*}$ in (B.2), one obtains that

Note that the $\beta$-smoothness of $f$ implies

Combining (2.2) and (2.3) yields x^{*}\in B\big{(}x^{++},(1-1/\kappa)\|\nabla f(x)\|^{2}/\alpha^{2}-2(f(x^{+})-f^{*})/\alpha\big{)}. As a result, suppose that initially we have a ball $B(x_{0},R_{0}^{2})$ that contains $x^{*}$, then it follows that

The optimal GeoD (with the linear convergence rate $(1-1/\sqrt{\kappa})$) maintains two balls containing $x^{*}$ in each iteration, whose centers are $c_{k}$ and $x_{k+1}^{++}$, respectively. More specifically, suppose that in the $k$-th iteration we have $c_{k}$ and $x_{k}$, then $c_{k+1}$ and $x_{k+1}$ are obtained as follows. First, $x_{k+1}$ is the minimizer of $f$ on $\mathop{\rm Line}(c_{k},x_{k}^{+})$. Second, $c_{k+1}$ (resp. $R_{k+1}^{2}$) is the center (resp. squared radius) of the ball (given by Lemma 2.1) that contains

Calculating $c_{k+1}$ and $R_{k+1}$ is easy and we refer to Algorithm 1 of for details. By applying Lemma 2.1 with $x_{A}=c_{k}$, $r_{A}=R_{k}$, $r_{B}=\|\nabla f(x_{k+1})\|/\alpha$, $\epsilon=1/\kappa$ and $\delta=\frac{2}{\alpha}(f(x_{k}^{+})-f(x^{*}))$, we obtain $R_{k+1}^{2}=(1-1/\sqrt{\kappa})R_{k}^{2}$, which further implies $\|x^{*}-c_{k}\|^{2}\leq(1-1/\sqrt{\kappa})^{k}R_{0}^{2},$ i.e., the optimal GeoD converges with the linear rate $(1-1/\sqrt{\kappa})$.

Geometric Descent Method for Convex Nonsmooth Composite Problems

Drusvyatskiy, Fazel and Roy extended the suboptimal GeoD to solve the composite problem (1.1). However, it was not clear how to extend the optimal GeoD to solve problem (1.1). We resolve this problem in this section.

The following lemma is useful to our analysis. Its proof is in the appendix.

In this subsection, we describe our proposed geometric proximal gradient method (GeoPG) for solving (1.1). Throughout Sections 3.1 and 3.2, $t\in(0,1/\beta]$ is a fixed scalar. The key observation for designing GeoPG is that in the $k$-th iteration one has to find $x_{k}$ that lies on $\mathop{\rm Line}(x_{k-1}^{+},c_{k-1})$ such that the following two inequalities hold:

Intuitively, the first inequality in (3.2) requires that there is a function value reduction on $x_{k}^{+}$ from $x_{k-1}^{+}$, and the second inequality requires that the centers of the two balls are far away from each other so that Lemma 2.1 can be applied.

The following lemma gives a sufficient condition for (3.2). Its proof is in the appendix.

Therefore, we only need to find $x_{k}$ such that (B.4) holds. To do so, we define the following functions for given $x$, $c$ ($x\neq c$) and $t\in(0,\beta]$:

The functions $\phi_{t,x,c}(z)$ and $\bar{\phi}_{t,x,c}(s)$ have the following properties. Its proof can be found in the appendix.

(i) $\phi_{t,x,c}(z)$ is Lipschitz continuous. (ii) $\bar{\phi}_{t,x,c}(s)$ strictly monotonically increases.

We are now ready to describe how to find $x_{k}$ such that (B.4) holds. This is summarized in Lemma 3.4.

The following two ways find $x_{k}$ satisfying (B.4).

If $\bar{\phi}_{t,x_{k-1}^{+},c_{k-1}}(1)\leq 0$, then (B.4) holds by setting $x_{k}:=c_{k-1}$; if $\bar{\phi}_{t,x_{k-1}^{+},c_{k-1}}(0)\geq 0$, then (B.4) holds by setting $x_{k}:=x_{k-1}^{+}$; if $\bar{\phi}_{t,x_{k-1}^{+},c_{k-1}}(1)>0$ and $\bar{\phi}_{t,x_{k-1}^{+},c_{k-1}}(0)<0$, then there exists $s\in$ such that $\bar{\phi}_{t,x_{k-1}^{+},c_{k-1}}(s)=0$. As a result, (B.4) holds by setting $x_{k}:=x_{k-1}^{+}+s(c_{k-1}-x_{k-1}^{+})$.

If $\bar{\phi}_{t,x_{k-1}^{+},c_{k-1}}(0)\geq 0$, then (B.4) holds by setting $x_{k}:=x_{k-1}^{+}$; if $\bar{\phi}_{t,x_{k-1}^{+},c_{k-1}}(0)<0$, then there exists $s\geq 0$ such that $\bar{\phi}_{t,x_{k-1}^{+},c_{k-1}}(s)=0$. As a result, (B.4) holds by setting $x_{k}:=x_{k-1}^{+}+s(c_{k-1}-x_{k-1}^{+})$.

Case (i) directly follows from the Mean-Value Theorem. Case (ii) follows from the monotonicity and continuity of $\bar{\phi}_{t,x_{k-1}^{+},c_{k-1}}$ from Lemma 3.3. ∎

It is indeed very easy to find $x_{k}$ satisfying the two cases in Lemma 3.4. Specifically, for case (i) of Lemma 3.4, we can use the bisection method to find the zero of $\bar{\phi}_{t,x_{k-1}^{+},c_{k-1}}$ in the closed interval $$. In practice, we found that the Brent-Dekker method performs much better than the bisection method, so we use the Brent-Dekker method in our numerical experiments. For case (ii) of Lemma 3.4, we can use the semi-smooth Newton method to find the zero of$\bar{\phi}_{t,x_{k-1}^{+},c_{k-1}}$in the interval$[0,+\infty)$. In our numerical experiments, we implemented the global semi-smooth Newton method and obtained very encouraging results. These two procedures are described in Algorithms 1 and 2, respectively. Based on the discussions above, we know that$x_{k}$ generated by these two algorithms satisfies (B.4) and hence (3.2).

We are now ready to present our GeoPG algorithm for solving (1.1) as in Algorithm 3.

2 Convergence Analysis of GeoPG

We are now ready to present our main convergence result for GeoPG.

Given initial point $x_{0}$ and step size $t\in(0,1/\beta]$, we set $R_{0}^{2}=\frac{\|G_{t}(x_{0})\|^{2}}{\alpha^{2}}(1-\alpha t)$. Suppose that sequence $\{(x_{k},c_{k},R_{k})\}$ is generated by Algorithm 3, and that $x^{*}$ is the optimal solution of (1.1) and $F^{*}$ is the optimal objective value. For any $k\geq 0$, one has $x^{*}\in B(c_{k},R_{k}^{2})$ and $R_{k+1}^{2}\leq(1-\sqrt{\alpha t})R_{k}^{2}$, and thus

Note that when $t=1/\beta$, (3.4) implies the linear convergence rate $(1-1/\sqrt{\kappa})$.

We prove a stronger result by induction that for every $k\geq 0$, one has

Let $y=x^{*}$ in (B.3) we have $\|x^{*}-x^{++}\|^{2}\leq(1-\alpha t)\|G_{t}(x)^{2}\|/\alpha^{2}-2(F(x^{+})-F^{*})/\alpha$, implying

Setting $x=x_{0}$ in (3.6) shows that (3.5) holds for $k=0$. We now assume that (3.5) holds for some $k\geq 0$, and in the following we will prove that (3.5) holds for $k+1$. Combining (3.5) and the first inequality of (3.2) yields

We now apply Lemma 2.1 to (3.7) and (3.8). Specifically, we set $x_{B}=x_{k+1}^{++}$, $x_{A}=c_{k}$, $\epsilon=\alpha t$, $r_{A}=R_{k}$, $r_{B}=\|G_{t}(x_{k+1})\|/\alpha$, $\delta=\frac{2}{\alpha}(F(x_{k}^{+})-F^{*})$, and note that $\|x_{A}-x_{B}\|^{2}\geq r_{B}^{2}$ because of the second inequality of (3.2). Then Lemma 2.1 indicates that there exists $c_{k+1}$ such that

i.e., (3.5) holds for $k+1$ with $R_{k+1}^{2}\leq(1-\sqrt{\alpha t})R_{k}^{2}$. Note that $c_{k+1}$ is the center of the minimum enclosing ball of the intersection of the two balls in (3.7) and (3.8), and can be computed in the same way as Algorithm 1 of . From (3.9) we obtain that $\|x^{*}-c_{k+1}\|^{2}\leq(1-\sqrt{\alpha t})R_{k}^{2}\leq(1-\sqrt{\alpha t})^{k+1}R_{0}^{2}$. Moreover, (3.7) indicates that $F(x_{k+1}^{+})-F^{*}\leq\frac{\alpha}{2}R_{k}^{2}\leq\frac{\alpha}{2}(1-\sqrt{\alpha t})^{k}R_{0}^{2}$. ∎

Practical Issues

In practice, the Lipschitz constant $\beta$ may be unknown to us. In this subsection, we describe a backtracking strategy for GeoPG in which $\beta$ is not needed. From the $\beta$-smoothness of $f$, we have

Note that the inequality (B.3) holds because of (B.1), which holds when $t\in(0,1/\beta]$. If $\beta$ is unknown, we can perform backtracking on $t$ such that (B.1) holds, which is a common practice for proximal gradient method, e.g., . Note that the key step in our analysis of GeoPG is to guarantee that the two inequalities in (3.2) hold. According to Lemma 3.2, the second inequality in (3.2) holds as long as we use Algorithm 1 or Algorithm 2 to find $x_{k}$, and it does not need the knowledge of $\beta$. However, the first inequality in (3.2) requires $t\leq 1/\beta$, because its proof in Lemma 3.2 needs (B.3). Thus, we need to perform backtracking on $t$ until (B.1) is satisfied, and use the same $t$ to find $x_{k}$ by Algorithm 1 or Algorithm 2. Our GeoPG with backtracking (GeoPG-B) is described in Algorithm 4.

Note that the sequence $\{t_{k}\}$ generated in Algorithm 4 is uniformly bounded away from . This is because (B.1) always holds when $t_{k}\leq 1/\beta$. As a result, we know $t_{k}\geq t_{\min}:=\min_{i=0,\ldots,k}t_{i}\geq\eta/\beta$. It is easy to see that in the $k$-th iteration of Algorithm 4, $x^{*}$ is contained in two balls:

Therefore, we have the following convergence result for Algorithm 4, whose proof is similar to that for Algorithm 3. We thus omit the proof for succinctness.

Suppose $\{(x_{k},c_{k},R_{k},t_{k})\}$ is generated by Algorithm 4. For any $k\geq 0$, one has $x^{*}\in B(c_{k},R_{k}^{2})$ and $R_{k+1}^{2}\leq(1-\sqrt{\alpha t_{k}})R_{k}^{2}$, and thus $\|x^{*}-c_{k}\|^{2}\leq\prod_{i=0}^{k}(1-\sqrt{\alpha t_{i}})^{i}R_{0}^{2}\leq(1-\sqrt{\alpha t_{min}})^{k}R_{0}^{2}.$

2 GeoPG with Limited Memory

The basic idea of GeoD is that in each iteration we maintain two balls $B(y_{1},r_{1}^{2})$ and $B(y_{2},r_{2}^{2})$ that both contain $x^{*}$, and then compute the minimum enclosing ball of their intersection, which is expected to be smaller than both $B(y_{1},r_{1}^{2})$ and $B(y_{2},r_{2}^{2})$. One very intuitive idea that can possibly improve the performance of GeoD is to maintain more balls from the past, because their intersection should be smaller than the intersection of two balls. This idea has been proposed by and . Specifically, suggested to keep all the balls from past iterations and then compute the minimum enclosing ball of their intersection. For a given bounded set $Q$, the center of its minimum enclosing ball is known as the Chebyshev center, and is defined as the solution to the following problem:

(4.2) is not easy to solve for a general set $Q$. However, when $Q:=\cap_{i=1}^{m}B(y_{i},r_{i}^{2})$, Beck proved that the relaxed Chebyshev center (RCC) , which is a convex quadratic program, is equivalent to (4.2), if $m<n$. Therefore, we can solve (4.2) by solving a convex quadratic program (RCC):

where $\Gamma=\{(x,\bigtriangleup):x\in Q,\bigtriangleup\succeq xx^{\top}\}$. If $Q=\cap_{i=1}^{m}B(c_{i},r_{i}^{2})$, then the dual of (4.3) is

where $C=[c_{1},\ldots,c_{m}]$ and $\lambda_{i},i=1,2,\ldots,m$ are the dual variables. Beck proved that the optimal solutions of (4.2) and (4.4) are linked by $x^{*}=C\lambda^{*}$ if $m<n$.

Now we can give our limited-memory GeoPG algorithm (L-GeoPG) as in Algorithm 5.

Backtracking can also be incorporated into L-GeoPG. We denote the resulting algorithm as L-GeoPG-B.

L-GeoPG has the same linear convergence rate as GeoPG, as we show in Theorem 4.3.

Consider L-GeoPG algorithm. For any $k\geq 0$, one has $x^{*}\in B(c_{k},R_{k}^{2})$ and $R_{k}^{2}\leq(1-1/\sqrt{\kappa})R_{k-1}^{2}$, and thus $\|x^{*}-c_{k}\|^{2}\leq(1-1/\sqrt{\kappa})^{k}R_{0}^{2}.$

Note that $Q_{k}:=\cap_{i=k-m+1}^{k}B(x_{i}^{++},r_{i}^{2})\subset B(x_{k}^{++},r_{k}^{2})$. Thus, the minimum enclosing ball of $B(c_{k-1},R_{k-1}^{2})\cap B(x_{k}^{++},r_{k}^{2})$ is an enclosing ball of $B(c_{k-1},R_{k-1}^{2})\cap Q_{k}$. The proof then follows from the proof of Theorem 3.5, and we omit it for brevity. ∎

Numerical Experiments

In this section, we compare our GeoPG algorithm with Nesterov’s accelerated proximal gradient (APG) method for solving two nonsmooth problems: linear regression and logistic regression, both with elastic net regularization. Because of the elastic net term, the strong convexity parameter $\alpha$ is known. However, we assume that $\beta$ is unknown, and implement backtracking for both GeoPG and APG, i.e., we test GeoPG-B and APG-B (APG with backtracking). We do not target at comparing with other efficient algorithms for solving these two problems. Our main purpose here is to illustrate the performance of this new first-order method GeoPG. Further improvement of this algorithm and comparison with other state-of-the-art methods will be a future research topic.

The initial points were set to zero. To obtain the optimal objective function value $F^{*}$, we ran APG-B and GeoPG-B for a sufficiently long time and the smaller function value returned by the two algorithms is selected as $F^{*}$. APG-B was terminated if $(F(x_{k})-F^{*})/F^{*}\leq tol$, and GeoPG-B was terminated if $(F(x_{k}^{+})-F^{*})/F^{*}\leq tol$, where $tol=10^{-8}$ is the accuracy tolerance. The parameters used in backtracking were set to $\eta=0.5$ and $\gamma=0.9$. In GeoPG-B, we used Algorithm 2 to find $x_{k}$, because we found that the performance of Algorithm 2 is slightly better than Algorithm 1 in practice. The codes were written in Matlab and run on a standard PC with 3.20 GHz I5 Intel microprocessor and 16GB of memory. In all figures we reported, the $x$-axis denotes the CPU time (in seconds) and $y$-axis denotes $(F(x_{k}^{+})-F^{*})/F^{*}$.

In this subsection, we compare GeoPG-B and APG-B for solving linear regression with elastic net regularization, a popular problem in machine learning and statistics :

We conducted tests on two real datasets downloaded from the LIBSVM repository: a9a, RCV1. The results are reported in Figure 1. In particular, we tested $\alpha=10^{-8}$ and $\mu=10^{-3},10^{-4},10^{-5}$. Note that since $\alpha$ is very small, the problems are very likely to be ill-conditioned. We see from Figure 1 that GeoPG-B is faster than APG-B on these real datasets, which indicates that GeoPG-B is preferable than APG-B. In the appendix, we show more numerical results on different $\alpha$, which further confirm that GeoPG-B is faster than APG-B when the problems are more ill-conditioned.

2 Logistic regression with elastic net regularization

In this subsection, we compare the performance of GeoPG-B and APG-B for solving the following logistic regression problem with elastic net regularization:

We tested GeoPG-B and APG-B for solving (C.2) on the three real datasets a9a, RCV1 and Gisette from LIBSVM, and the results are reported in Figure 2. In particular, we tested $\alpha=10^{-8}$ and $\mu=10^{-3},10^{-4},10^{-5}$. Figure 2 shows that for the same $\mu$, GeoPG-B is much faster than APG-B. More numerical results are provided in the appendix, which also indicate that GeoPG-B is much faster than APG-B, especially when the problems are more ill-conditioned.

3 Numerical results of L-GeoPG-B

In this subsection, we test GeoPG with limited memory described in Algorithm 5 for solving (C.2) on the Gisette dataset. Since we still need to use the backtracking technique, we actually tested L-GeoPG-B. The results with different memory sizes $m$ are reported in Figure 3. Note that $m=0$ corresponds to the original GeoPG-B without memory. The subproblem (4.4) is solved using the function “quadprog” in Matlab. From Figure 3 we see that roughly speaking, L-GeoPG-B performs better for larger memory sizes, and in most cases, the performance of L-GeoPG-B with $m=100$ is the best among the reported results. This indicates that the limited-memory idea indeed helps improve the performance of GeoPG.

Conclusions

In this paper, we proposed a GeoPG algorithm for solving nonsmooth convex composite problems, which is an extension of the recent method GeoD that can only handle smooth problems. We proved that GeoPG enjoys the same optimal rate as Nesterov’s accelerated gradient method for solving strongly convex problems. The backtracking technique was adopted to deal with the case when the Lipschitz constant is unknown. Limited-memory GeoPG was also developed to improve the practical performance of GeoPG. Numerical results on linear regression and logistic regression with elastic net regularization demonstrated the efficiency of GeoPG. It would be interesting to see how to extend GeoD and GeoPG to tackle non-strongly convex problems, and how to further accelerate the running time of GeoPG. We leave these questions in future work.

References

Appendix A Geometric Interpretation of GeoPG

We argue that the geometric intuition of GeoPG is still clear. Note that we are still constructing two balls that contain $x^{*}$ and shrink at the same absolute amount. In GeoPG, since we assume that the smooth function $f$ is strongly convex, we naturally have one ball that contains $x^{*}$, and this ball is related to the proximal gradient $G_{t}$, instead of the gradient due to the presence of the nonsmooth function $h$. To construct the other ball, GeoD needs to perform an exact line search, while our GeoPG needs to find the root of a newly constructed function $\bar{\phi}$, which is again due to the presence of the nonsmooth function $h$. The two changes of GeoPG from GeoD are: replace gradient by proximal gradient; replace the exact line search by finding the root of $\bar{\phi}$, both of which are resulted by the presence of the nonsmooth function $h$.

Appendix B Proofs

From the $\beta$-smoothness of $f$, we have

where the last inequality is due to the convexity of $h$ and $G_{t}(x)\in\nabla f(x)+\partial h(x^{+})$. ∎

B.2 Proof of Lemma 3.2

holds. By letting $y=x_{k-1}^{+}$ and $x=x_{k}$ in (B.3), we have

where the last inequality is due to (B.4). Moreover, from the definition of $x_{k}^{++}$ and (B.4) it is easy to see

B.3 Proof of Lemma 3.3

Before we prove Lemma 3.3, we need the following well-know result, which can be found in .

Lemma. (see Lemma 3.9 of ) For $t\in(0,1/\beta]$, $G_{t}(x)$ is strongly monotone, i.e.,

where the last inequality is due to the non-expansiveness of the proximal mapping operation.

We now prove (ii). For $s_{1}<s_{2}$, let $z_{1}=x+s_{1}(c-x)$ and $z_{2}=x+s_{2}(c-x)$. We have

where the first inequality follows from (B.5). ∎

Appendix C Numerical Experiment on Other Datasets

In this section, we report some numerical results of other data sets. Here we set the terminate condition as $\|G_{t}(x_{k}^{+})\|_{\infty}\leq tol$ for GeoP-B and $\|G_{t}(x_{k})\|_{\infty}\leq tol$ for APG-B.

In this subsection, we compare GeoPG-B and APG-B for solving linear regression with elastic net regularization:

We first compare these two algorithms on some synthetic data. In our experiments, entries of $A$ were drawn randomly from the standard Gaussian distribution, the solution $\bar{x}$ was a sparse vector with 10% nonzero entries whose locations are uniformly random and whose values follow the Gaussian distribution $3*\mathcal{N}(0,1)$, and $b=A*\bar{x}+\mathbf{n}$, where the noise $\mathbf{n}$ follows the Gaussian distribution $0.01*\mathcal{N}(0,1)$. Moreover, since we assume that the strong convexity parameter of (C.1) is equal to $\alpha$, when $p>n$, we manipulate $A$ such that the smallest eigenvalue of $A^{\top}A$ is equal to 0. Specifically, when $p>n$, we truncate the smallest eigenvalue of $A^{\top}A$ to 0, and obtain the new $A$ by eigenvalue decomposition of $A^{\top}A$. We set $tol=10^{-8}$.

From Tables 1, 2 and 3 we see that GeoPG-B is more efficient than APG-B in terms of CPU time when $\alpha$ is small. For example, Table 1 indicates that GeoPG-B is faster than APG-B when $\alpha\leq 10^{-4}$, Table 2 indicates that GeoPG-B is faster than APG-B when $\alpha\leq 10^{-6}$, and Table 3 shows that GeoPG-B is faster than APG-B when $\alpha\leq 10^{-8}$. Since a small $\alpha$ corresponds to a large condition number, we can conclude that in this case GeoPG-B is more preferable than APG-B for ill-conditioned problems. Note that “f-diff” is very small in all cases, which indicates that the solutions returned by GeoPG-B and APG-B are very close.

We also conducted tests on three real datasets downloaded from the LIBSVM repository: a9a, RCV1 and Gisette, among which a9a and RCV1 are sparse and Gisette is dense. The size and sparsity (percentage of nonzero entries) of these three datasets are $(32561\times 123,11.28\%)$, $(20242\times 47236,0.16\%)$ and $(6000\times 5000,99.1\%)$, respectively. The results are reported in Tables 4, 5 and 6, where $\alpha=10^{-2},10^{-4},10^{-6},10^{-8},10^{-10}$ and $\mu=10^{-3},10^{-4},10^{-5}$. We see from these tables that GeoPG-B is faster than APG-B on these real datasets when $\alpha$ is small, i.e., when the problem is more ill-conditioned.

C.2 Logistic regression with elastic net regularization

In this subsection, we compare the performance of GeoPG-B and APG-B for solving the following logistic regression problem with elastic net regularization:

In Tables 7, 8 and 9 we report the comparison results of GeoPG-B and APG-B for solving different instances of (C.2). From results in these tables we again observe that GeoPG-B is faster than APG-B when $\alpha$ is small, i.e., when the condition number is large.

We also tested GeoPG-B and APG-B for solving (C.2) on the three real datasets a9a, RCV1 and Gisette from LIBSVM, and the results are reported in Tables 10, 11 and 12. We again have the similar observations as before, i.e., GeoPG-B is faster than APG-B for more ill-conditioned problems.

C.3 More discussions on the numerical results

To the best of our knowledge, the FISTA algorithm does not have a counterpart for strongly convex problem, but we still conducted some numerical experiments using FISTA for solving the above problems. We found that FISTA and APG are comparable, but they are both worse than GeoPG for more ill-conditioned problems. Moreover, from the results in this section, we can see that when the problem is well-posed such as $\alpha=0.01$, APG is usually faster than GeoPG in the CPU time, and when the problem is ill-posed such as $\alpha=10^{-6}$, $10^{-8}$, $10^{-10}$, GeoPG is usually faster, but the iterate of GeoPG is less than APG in the most cases. So GeoPG is not always better than APG in the CPU time. But since ill-posed problems are more challenging to solve, we believe that these numerical results showed the potential of GeoPG. The reason why GeoPG is better than APG for ill-posed problem is still not clear at this moment, but we think that it might be related to the fact that APG is not monotone but GeoPG is, which can be seen from the figures in our paper. Furthermore, although GeoPG requires to find the root of a function $\bar{\phi}$ in each iteration, we found that a very good approximation of the root can be obtained by running the semi-smooth Newton method for 1-2 iterations on average. This explains why these steps of GeoPG do not bring much trouble in practice.

C.4 Numerical results of L-GeoPG-B

In this subsection, we tested GeoPG-B with limited memory described in Algorithm 5 on solving (C.2) on Gisette dataset. The results for different memory size $m$ are reported in Table 13. Note that $m=0$ corresponds to the original GeoPG-B without memory.

From Table 13 we see that roughly speaking, L-GeoPG-B performs better for larger memory size, and in almost all cases, the performance of L-GeoPG-B with $m=100$ is the best among the reported results. This indicates that the limited-memory idea indeed helps improve the performance of GeoPG.