Gradient Descent Converges Linearly for Logistic Regression on Separable Data
Authors: Kyriakos Axiotis
Maxim Sviridenko
Venue: Submitted to ICLR 2023 (2023)
Keywords: logistic regression
gradient descent
sparse optimization

Abstract: We show that running gradient descent on the logistic regression objective guarantees loss $f(x) \leq 1.1 \cdot f(x^*) + \epsilon$, where the error $\epsilon$ decays exponentially with the number of iterations. This is in contrast to the common intuition that the absence of strong convexity precludes linear convergence of first-order methods, and highlights the importance of variable learning rates for gradient descent. For separable data, our analysis proves that the error between the predictor returned by gradient descent and the hard SVM predictor decays as $\mathrm{poly}(1/t)$, exponentially faster than the previously known bound of $O(\log\log t / \log t)$. Our key observation is a property of the logistic loss that we call multiplicative smoothness and is (surprisingly) little-explored: As the loss decreases, the objective becomes (locally) smoother and therefore the learning rate can increase. Our results also extend to sparse logistic regression, where they lead to an exponential improvement of the sparsity-error tradeoff.


Under review as a conference paper at ICLR 2023
GRADIENT DESCENT CONVERGES LINEARLY FOR LO- GISTIC REGRESSION ON SEPARABLE DATA
Anonymous authors Paper under double-blind review
ABSTRACT
We that running gradient descent on the logistic regression objective guaran- tees loss f(x) S 1.1- f(x") ) + E, where the error e decays exponentially with the number of iterations. This is in contrast to the common intuition that the absence of strong convexity precludes linear convergence of first-order methods, and high- lights the importance of variable learning rates for gradient descent. For separable data, our analysis proves that the error between the predictor returned by gradi- ent descent and the hard SVM predictor decays as poly(1/t), exponentially faster than the previously known bound of Ollog log t/ log t). Our key observation is a property of the logistic loss that we call multiplicative smoothness and is (sur- prisingly) little-explored: As the loss decreases, the objective becomes (locally) smoother and therefore the learning rate can increase. Our results also extend to sparse logistic regression, where they lead to an exponential improvement of the sparsity-error tradeoff.
INTRODUCTION
Logistic regression is one of the most widely used classification methods because of its simplic- ity, interpretability, and good practical performance. Yet, the convergence behavior of first-order methods on this task is not well understood: In practice gradient descent performs much better than what the theory predicts. In particular, a general analysis of gradient descent for smooth functions implies convergence with the еттог in function value decaying as O(1TT). Analyses with stronger, linear convergence guarantees generally require the function to satisfy the strong convexity property, which, in contrast to other losses such as the &g loss, the logistic loss only satisfies in bounded set of solutions around zero. As a result, this introduces an exponential runtime dependency on the magnitude of the optimal solution Rätsch et al. (200T); Freund et al. (2018), which is undesirable in practice. This poses a serious obstacle to obtaining favorable error rates for logistic regression that lead to figh-precision solutions.
A deeper study into the structure of the exponential and logistic losses was done in Telgarsky & Singer (2012), who showed that, for linearly separable data, greedy coordinate descent achieves linear convergence with a rate that depends on the maximum linear classification margin (i.e. hard SVM margin). Unfortunately, for logistic regression, it also has 2 dependence the number of examples, making it inefficient for any real-world task. The significance of the separability of the data for convergence has also been observed in Telgarsky (2013); Freund al. (2018), who present convergence results based on quantitative measures of separability. Telgarsky (2013) also refines the results of Telgarsky & Singer (2012) for the exponential loss, but still suffers from an exponential overhead originating the multiplicative discrepancy between the exponential and the logistic loss. Interestingly Telgarsky (2013) points out that logistic regression experiments paint much more favorable picture than the theory predicts. For separable data, [Soudry et al. (2018) showed that the gradient descent logistic regression estimator converges to the maximum margin estimator at a rate of Olog log T log 7'), which implies function value convergence a rate of O(ITT). Interestingly,
Nacson et al. (2019) experimentally observed that these rates seem to be exponentially improvable one uses variable step sizes, in the case of logistic regression and shallow neural networks. However, as shown in Ji & Telgarsky (2018), the separability assumption is important, and the poly(1/T) bound of function value convergence is tight for gradient descent arbitrary data.

---

Under review as a conference paper at ICLR 2023
Another approach obtain high-precision solutions is by using second order methods, which in ad- dition to first order (gradient) information, use second order (Hessian) information about the func- tion. These make use of second order stability properties, such as quasi-self-concordame (2010) combined with Newton's method Karimireddy et al. (2018), or ball oracles Carmon et al.
[Bach
22000) Adil et al. (202T). Such approaches are generally not suitable for large-scale applications because of their reliance on repeated calls to large linear system solvers.
Our work. In this paper, we show that (under appropriate assumptions) can get the best of both worlds of first and second order methods, thus giving a partial explanation for the excel- lent performance that first-order methods have on logistic regression in practice. In particular, given binary classification instance (A E {-1,
b E {-1, with associated logis- tic loss f=) log(1 + exp( (sp(-bi(Az) (+(())))) we show that simple variants of gradient descent
return a solution with f(x) & (1+6) 6) f(x*) + after O (K (+ log = iterations, where OK
K == [n, []= Even though the error still decays as 1/T in the worst case because of the de- pendence, the additive error is now ff(x") instead of f())), allowing for much faster convergence when the optimal loss f(x=) is smaller (which is our measure of linear separability of the data). For linearly separable data, i.e. as f(x") approaches the convergence becomes linear. We also show
that the distance the maximum margin estimator ||
12 decays 1/T, exponentially
improving the log log T/ log T bound of Soudry et al. (0188)
Instead of properties like Lipschitzness, smoothness, strong convexity that are commonly used in the study of first order methods, we find that there are two properties that are more relevant to the structure of the logistic regression problem. The first one is second order robustness, which means that the Hessian stable (in spectral sense) in any small enough norm ball Cohen al. (2017). This is closely related to quasi-self-concordaacce a property that has been previously used in the analysis of second order algorithms Bachh (2010). The second property is what we call multiplicative smoothness, which means that the function is locally smooth, with the smoothness constant being proportional the function value (loss). Together, these properties show that, the loss decreases, the objective becomes (locally) smoother and therefore the learning rate can increase. This motivates a variable step size schedule that is inversely proportional to the loss, thus making larger steps as the solution approaches optimality. This in fact agrees with the observations of Soudry et al. (2018); Nacson et al. (2019) on the importance of a variable learning rate. As can be seen in the toy example from Soudry al. (2018) in Figure[ ! simply replacing the fixed learning rate 1) used in (Suudry et al. (011 by an increasing learning rate 7) fx²)// fxx") yields an exponential improvement, both in loss and distance to the maximum margin estimator.
logistic
1, distance maximum margin estimator
10a
4 tistance to max:mum margin extmmattr
0.05
10a1
0.04
10-1
0.03
10.1
0.02
10
0.01
10-1
stop size g
step size 8
step size g-1. (illa)
0.00
step size g-1 fhx Wit"
160
10a
10a
10a
10" number of itarations
10a
number of iterstions
Figure 1: Comparison between fixed and increasing step sizes in the toy example from Figure 1 of Soudry et al. (2018). The fixed step size is set to 3-1 : |||| -2 and the increasing to 3-1 f( (// f(x The estimator error is defined as ||=*/ |x'1l2 x=/ ||x Ialll-
2

---

Under review as a conference paper at ICLR 2023
Algorithm
Order
Guarantee
Runtime Error Dependence
Gradient descent
First
f()) S f(x)) +e
m/e
Accelerated gradient descent
First
f(z) f(x*) +E
vm/E
Newton/Trust region
Second
f(z) - f(x*) ) +
log(m/E)
This paper
First
f(z) - (1 f(=") +e
8 + log(m/E)
Table I: Algorithms for logistic regression and dependence on m/s (omitting extra polylog (m. n) factors). Algorithms with exponential dependences on any problem parameter are ommitted.
Algorithm
Guarantee
Sparsity
Order
Shalev-Shwartz et al. (2010)
f(x) S f(x") +e
x 1|? m/s
First
This paper
[w) s (1+ f(x*) +
|| (8-1 log(m//)
First
Table 2: Algorithms for sparse logistic regression
1.1 SPARSE LOGISTIC REGRESSION
practice, is often important to force the solution of a logistic regression problem to sparse, i.e. have only few non-zero entries, which is form of feature selection. This is because most of the features might only be marginally useful, and thus one can drastically reduce the size of the model while significantly sacrificing the predictive performance. Apart from computational efficiency, feature selection also important to improve interpretability and avoid overfitting.
Most progress in sparse optimization has focused objective functions with condition number bounded by some k > 0. Results in this line of work guarantee a solution with relaxed spar- sity 8¹ 2 8, where is the target sparsity, and algorithms include lasso, orthogonal matching pur- suit (OMP), and iterative hard thresholding (IHT) Natarajan (1995); Blumensath & Davies (2009); Shalev-Shwartz al. (2010); Jain et al. (201 2014)) Axiotis Sviridenko (2021 The state of the art result by Axiotis & Sviridenko (2022) gives sparsity of s' = ((k) using variant of the IHT algorithm.
However, the condition number of the logistic loss is unbounded, because it is not strongly convex. Therefore, these results do not directly apply, although they do apply to fz-regularized logistic re- gression. Some works Van de Geer (2008); [Bunea] (2008) have analyzed lasso methods for logistic regression without condition number assumptions, and Saahhha-Shhaan et al. (20TO) provides three different analyses for smooth but not strongly convex functions. These apply to logistic regression
and give a sparsity of O (Il== || m to achieve a loss of f()) < f(x") + e. The most practical of these is forward greedy selection algorithm, which also known as greedy coordinate descent.
Our work. Using the second order stability and multiplicative smoothness properties, we show that a slight variation of greedy coordinate descent gives a sparsity of
(I 11 (8-1 + log(m/e))
and a loss of f(x) < (1+8) f(x*) + s. As long as the 1 + approximation in front of f(=") tolerated, as is the case when f(x') < m, this implies an exponential improvement in the dependence from to log m In addition, our analysis does not require (but is also not affected by) fully corrective steps, in which the function fully re-optimized over the support the current solution.
2 PRELIMINARIES
Notation. We denote [n] =
We will use bold to refer to vectors or matrices. We denote by O the all-zero vector, the all-one vector, O the all-zero matrix, and by I the identity
3

---

Under review as a conference paper at ICLR 2023
matrix (with dimensions understood from the context). Additionally, will denote by 1, the i-th basis vector, i.c. the vector that is O everywhere except at position i.
In order to ease notation and where not ambiguous for two vectors 2, E R", we denote by zy E R" a vector with elements (æy); = ziyi, i.c. the element-wise multiplication of two vectors and y. In contrast, denote their inner product by (ar, y) x. y. Similarly, x? IR" will be the element-wiss wise square of vector x.
For any vector æ R" and set S S [nz], we denote by z the vector that results from after zeroing out all the entries except those in positions given by indices in S. We will also use the notation (=] (v)())) to denote the restriction of gradient to S.
We use the notation Ō (-) to hide poly (n, m) factors O-notation, where n is the dimension of the problem and m is the number of examples.
Norms. For any p E (0, 00) and weight vector w 2 0, we define the weighted lp norm of a vector R as:
1/P
|| |==||p.00 =
Σ Was?
For p O, we denote || = Hi x; + 031 to be the sparsity of æ. For p oc, we denote x oloo = max, |ay| to be the maximum absolute value of æ.
Smoothness and convexity. A differentiable function f : R is called convex if for any RD æ, y E R we have f(y) 2 f(x) + (Vf(z), y z). Furthermore, f is called f-smooth (with respect to some norm [1-1]) for some real number 3 0 if for any x, y E R= we have f(y) S f(x) + (VI(a) y - x) + (3/2) lyy æ1|² If f is only 3-smooth along s-sparse directions (i.e. only for 2; y E IR. such that 1// æl1o S s). then we call 8-smooth at sparsity level s and denote the smallest such 33 by 33 and call it the restricted smoothness constant (at sparsity level s).
LOGISTIC REGRESSION ANALYSIS VIA MULTIPLICATIVE SMOOTHNESS
m
In the logistic regression problem, our goal is to minimize the function f(x) Σ log(1 +e- (Ae))),
where E m
x is a data matrix
Our starting point, as is usually the case with first-order methods, will be the second order Taylor expansion of f:
f(x + +) f()) + (x)))
V2 ())))
where, by the mean value theorem for twice continuously differentiable functions, H is entry-wise the Hessian of ž. In fact, as long as the step 0 is not too
between æ and x', and f2 large, the Hessian at 전 will not differ much (spectrally) from the Hessian at æ. This is because of the following property of the logistic function called second order robustness Cohen et al. (2017). which is also very closely related to quasi-self quasi-seef-cooccrddane Bach (2010).
Definition 3.1 (Second-org -odder robustness). A twice differentiable function f :R - R is called q gesecond order robust with respect to norm ||-I| if its Hessian is stable in any (1/q)-sized bblll, i.e. for any x, x' E _R such that || x0 - x < 1/g, we have v = f²x()) 2V 2V²
It is not hard to see that f is 2.M-sc order robust with respect the E, norm, where M is upper bound on the entries of in absolute value. Because of this, (T) implies the much simpler
f(x + क) f(x) + (Vf((), 3) + (ä, f(x()))
as long as |ا6|| S 1/(2M). We can easily calculate that ( = - A (1-0 (Ax)), where (4) = 1/(1+ is the sigmoid function, and f()()) A diag( w (A)) where w w(x) =
'This formulation is without loss of generality, hecause can incorporate the binary +1 labels into the matrix A and assume that all the labels positive.
4

---

Under review as a conference paper at ICLR 2023
(1- -x))) are diagonal weights. Now, should note that the second order term of be re-written as (w(x)) ( (Az) of the algorithm and in turn the bound the total number of iterations, becomes smaller as the weights w at) become smaller. The crucial observation that these weights are bounded way that depends on the loss of ã, concretely:
This term, whose magnitude is what will determine the step size
Σ 2 (w)x)); S fz))
In other words, as the loss decreases, f becomes smoother (in an appropriate sense). This is the main observation on which our analysis based, and is what allows the algorithm employ step size that is inversely proportional to the loss.
Multiplicative smoothness. The above discussion motivates the following definition of multi- plicative smoothness. This is related to the usual definition of smoothness but also incorporates the property that the function becomes smoother as the loss decreases.
Definition 3.2 (Multiplicative smoothness). We call twice differentiable function R - Ry0 u-multiplicatively smooth with respect to a norm ||-1]. for any æ, N. E IR? we have
((x)
Our of general norm is not over-generalization, since as will see the ε norm is more suitable for sparse logistic regression, and the &2 norm is more suitable for the unrestricted case. In fact, it can be proved that f is M M smooth with respect the & norm, where remind that M is a bound on the entries of A in absolute value.
In the following sections, we will see how the second order robustness and multiplicative smoothness properties play into the design and analysis of algorithms for sparse and general logistic regression.
4 SPARSE LOGISTIC REGRESSION
As we saw, the logistic loss is 2. -sccond order robust and M lulliiippliicativelyy smooth with respect the & norm. This is ideal norm for sparse logistic regression, where in addition minimizing the loss we want to restrict the solution to have few non-zero entries. In particular, it yields variant of the & gradient descent algorithm (aka greedy coordinate descent), which is presented in Algorithm
Algorithm Greedy Coordinate Descent
1: procedure m
BB
2: Let f(x) == Σ log(1 +e b(()): b((r))
3: for t- 0....,, do
X
if xf =0
4:
For all [n] define Ci
if | I| B and vif(x') -I
otherwise
5:
i argmax, {Ce (+f(='))
6:
ア - (2M max Mmax(Mf(ar) (f')), (+
7:
x
++ + x 7/ (x')
return
The first thing that should be noted about this algorithm the crucial parameters A These parame- ters offer quantitative threshold between sparsity and speed of convergence. In particular, when A 1. then all entries (regardless of whether they are zero or not) are treated the same. When X & 1, on the other hand, the gradient entries corresponding zero entries discounted by a factor & 1, thus making the algorithm less eager to update these as opposed to non-zen zero entries, whose update doesn't 't increase sparsity.
5

---

Under review as a conference paper at ICLR 2023
A practical consideration about Algorithm is order. The second condition in line is to make sure that the & norm of the solution never exceeds a given bound on the L norm of the optimal solu- tion. This check is useful for the theoretical analysis but should likely be removed in any practical implementation.
We are ready for the main theorem of this section. In the proof, which be found in Ap- pendix A.2.2 we present an analysis of Algorithm [ for sparse logistic regression. In addition Il One possible ap-
upper bound B 2 ||æ*|| al it also requires an approximation B₁ of ||**||-
proach is to approximate it by B, but in practice this would be a learning rate hyperparameter to be tuned.
Theorem 4.1 (Sparse logistic regression). Given a binary classification instance (A )1.-1)") and for any solution x²
[-M, M| m
[- (-B B with M >
max x loo __B and a known parameter Bi E [t
for some C Z 1, Algo-
rithm 7 with X min B1/ ||01|| 13, initial solution x E ER", and error tolerance < m/2
returns a solution æ with
f(x) $ (1+ f(x'){
and sparsity
: || =0 0110"1 ( + +og f(x")- f(xx)
8
in
T=o 1 =1=11=++11=11 B² (1 +
( log f(x²) f(x")-1(x* f(x²)
iterations, for any choice of ó E (0, 1) and parameter > O. Each iteration consists of evaluating the logistic regression gradient f plus O(m + ni additional time.
Corollary 4.2. If M, B,C
(1) and x² is s-sparse, then Algorithm with X min (1/ ||= 1 11 returns solution with
f(x) 1.1. f((=f((()))))))))))))(())) te
and sparsity
s = | = =ō =Ō(²² log
in
T ==Ō (5
iterations.
useful to compare these results to the results Shalev-Shwarle et al. (2010) for sparse opti- mization of general smooth convex functions. Even though they achieve the stronger error bound of f(x) S f(x*) e, the sparsity of the final solution is in the order of m, which has an exponen- tially worse error dependence than s log m in front of f(="). then can obtain exponentially faster sparsity and convergence.
E Therefore, the approximation rate (1+ is tolerable
we are willing to perform fully corrective steps as described Algorithm then we can get cleaner and slightly simpler analysis. This presented in Theorem 4.3 and proved in Ap- pendix A.2.3 Fully corrective steps can be useful when there is an efficient (dense) optimization algorithm and wishes use it black box for sparse optimization. In practice, does need to perform full correction, but only small number of corrective (usually gradient) steps over the current support of the solution.
"t theorem can be stated without this additional constraint, but include it because it makes the bounds considerably simpler

---

Under review as a conference paper at ICLR 2023
Algorithm 2 Greedy coordinate descent with fully corrective steps
1: procedure EULLKCORBCCVVORRREOCOODEEEEEEEED
M, B)
2:
Let ((x) 2
log(1 + (((l))))
3:
5 supp(x=))
4:
for 0, O,.... ......TT
do
5:
i + argmax, (f'))())) 5t+1 + St (i)
6:
7:
x x(41 (uu
argmin (()
return x²
Theorem 4.3 (Sparse logistic regression with fully corrective steps). Given binary classification
instance (A E M, Ml b E (1.-1)-) and for any solution x² R", Algorithm 2 error tolerance
with
m/2 and initial solution x" returns a solution æ with
f(æ) S 61+ ((=))))))))++ +
and sparsity
:= luu ||200 |/=011 + 10011++11100 00011a01 M22 +++log log f(x²) f(xx"
(
in == | iterations, for any choice of 8 E (0,1). Each iteration consists of evaluating the logistic regression gradient f. solving logistic regression problem on s' variables, plus (m additional time.
DENSE LOGISTIC REGRESSION
In this section, our goal to minimize the logistic function f without any constraint on the sparsity of the solution. The results of the Section Dappliee to full sparsity of n already imply Corollary 5.1
Corollary 5.1 (Dense logistic regression). Given binary classification instance (A 1-1, and for any solution x" [- Bi" with M 2
M- MM mxn max
|1 ||-1 ,,B'' .BB-)] Algorithm 1 with X = for all initial solution x E. and error tolerance 0 < m/2 returns solution with
f (1+ ((=+))f(())))))) +E +E
in
T T= n2
(1+ +og S(x0 - -((
(1
E
iterations, for any choice of 8 E (0, 1). Additionally, ||0|| S B 2M- Each iteration consists of evaluating the logistic regression gradient f plus O(m + n)) additional time.
Even though Corollary has the same favorable convergence in terms of and e as Theorem 4.1 based practical intuitions would expect (fa-based) gradient descent perform better than greedy coordinate descent, which only updates one coordinate at time, while having access to the full gradient. In fact, we can verify that the logistic loss does have the multiplicative smoothness condition with respect to the Ez norm, albeit in an almost trivial sense:
(w) (Az)² < (=)]l A 2 < f(x) || |l
|| < 8<0)811111
Here, using the inequality |||| || < A 2 := implies 3-multiplicative smoothness with re- spect to the norm. Unfortunately, this is not significantly better than the e case: The number of iterations will be proportional to / "|="1" which can be m.

---

in Under review as a conference paper at ICLR 2023
Table 3: Upper bounds on the quantity (10(a), (AV[())) / (
Shown
here is the maximum of this over æ being one one of the first 1000 iterates.
Dataset
Max ratio
Dataset
Max ratio
Dataset
Max ratio
letter
0.40
skin
0.44
census
0.50
rcv1. 1.test
0.36
w8all
0.40
adult
0.40
ijennl 0.47
shuttle.binary
0.37
poker
0.36
vchy2binary
0.37
kddeup04.pp phy
0.36
nomao 0.50
magic04
0.37
iddcup04.bio
0.48
covtype 0.36
Interestingly, real logistic regression instances exhibit the & multiplicative smoothness property with significantly better constants, In our experiments we found that along the path of gradients encountered by gradient descent in a variety of instances, the following property was true:
(w()), (AV)())) <
[x))1
This is an effective 3m-1--uutiphle -muutiiipiili smoothness property, because it is only assumed be true for æ's encountered by the gradient descent algorithm. As such, it is an empirical property. In order check our hypothesis, we have run the gradient descent algorithm with the step sizes that implied by Theorem 5.2 which we will see later. For each of the 15 experiments, have run gradient descent for 1000 iterations, and calculated the maximum of the following quantity, over all iterations:
(w(x), (AV f(x (m=) AAV
If this bounded by and using the fact that [AVf()) S ([V]((=) this implies that effectively 33-- -mmltipppplciatiiee smooth with respect to the l norm. Indeed, T these values are indeed less than 1 for all datasets and all iterations.
In the following, our plan prove convergence, assuming that / has the multiplicative smoothness property with the constants in our hypothesis above. Under this assumption, we can now prove much stronger convergence theorem (here we are also using the fact that M to replace 2M- by 2-3-sen order robustness):
Theorem 5.2. Let f RR - be a convex function that is 2 B-second order robust with respect to the & norm and fm- -mm--ppiiicictieel smooth with respect to the Eg norm. Let x." E T be an initial solution and x' R be an arbitrary solution, where =
1 x² and 2 vn
Then, gradient descent with step size TJs 0.5 min 8m T(a) VF
returns a solution
with
f(x) < (1+0)f(xz) +e
after
BR²
f(x²) f(xx')
=
0 + log
iterations.
MAXIMUM MARGIN SOLUTIONS
is known that running gradient descent on the logistic loss on linearly separable data converges to the hard SVM (maximum margin) classifier Soudry et al. (2018), yet at the slow rate of
log log
x
l|
x
log
'The assumption R > V is necessary but simplifies the bounds.
8

---

Under review as a conference paper at ICLR 2023
As all our results work best when the data is separable, it is natural to ask about what they imply for margin maximization.
We consider the constrained logistic regression problem
min |
fx(x) Σ log(1 te ())))(A)))))
(4)
We start by observing that Corollary 5.1 and Theorem 5.2 can be modified to solve (4) with
blowup of p² in the number of iterations. In particular, the number of iterations will be
Ö (p² x {1 + log 4)), where depends on whether we use Corollary 5.1 or Theorem 5.2 but
is beyond the point of this section, since here we are interested in the error dependence.
Picking 8 = 1, pa and p lmg(6m) for some target error ε E (0, 1), get the following theorem:
at
Theorem 6.1. Consider a linearly separable binary classification instance (A R
(1,")) and solution x² that maximizes min; b: ((Axx); == Then, we can obtain a solu-
tion with ||0||| 1 and fp(x) 3fp(x²) in Ô oe
iterations of gradient descent, where Furthermore, x has (1 - -opptimll margins:
log(6m))
ab
bx(A));;
min
2 a(1 -
||0||
and is close the maximum margin classifier:
x
x²
$ 2V
||1||
x
ll
2
not hard to see that Theorem
6.1
gives an exponential improvement the error dependence
compared to (Suudyy al. (018))
7 NUMERICAL EXAMPLE
In order to numerically validate our algorithm, run logistic regression on the well known UCI adult binary classification dataset. order to simulate a separable dataset, we first run gradient descent the whole data, and then discard the misclassified data points. This gives dataset. Then, we run two variants of gradient descent: One with constant step size given by 8-1, and one with increasing step size given by 7/2 B f(x")/((x)) with no other change. This is motivated by our findings, which suggest that the step size should increase proportionally to the decrease of the loss. As we
separable
in Figure [ the error in the case of fixed step size decays as poly(1/t). while in the case of increasing step size we have linear convergence (albeit with a low rate because the margins are in the order of 10 10-6).
adult dataset
size ø-1
step size (bet)b))))
mean logistic loss
10-2
10-1
10a
20
10a
10a
10'
107
number of Iterations
Figure 2: Comparison of fixed vs increasing step size on logistic regression on adult dataset

---

Under review as a conference paper at ICLR 2023
REFERENCES
Deeksha Adil, Brian Bullins, and Sushant Sachdeva. Unifying width-reduced methods for quasi- self-concordant optimization. Advances in Neural Information Processing Systems, 34, 2021.
Kyriakos Axiotis and Maxim Sviridenko. Sparse convex optimization via adaptively regularized hard thresholding. Journal of Machine Learning Research, 22:1-47, 2021.
Kyriakos Axiotis and Maxim Sviridenko. Iterative hard thresholding with adaptive regularization: Sparser solutions without sacrificing runtime. arXiv preprint arXiv:2204.08274, 2022.
Francis Bach. Self-concordant analysis for logistic regression. Electronic Journal of Statistics, 4: 384 414, 2010.
Thomas Blumensath and Mike E. Davies. Iterative hard thresholding for compressed sensing. Ap- plied and computational harmonic analysis, 27(3):265-274, 2009.
Florentina Bunea. Honest variable selection in linear and logistic regression models via & and L le penalization. Electronic Journal of Statistics, 1594-194, 2008.
Yair Carmon, Arun Jambulapati, Qijia Jiang, Yujia Jin, Yin Tat Lee, Aaron Sidford, and Kevin Tian. Acceleration with a ball optimization oracle. Advances in Neural Information Processing Systems, 33: 33:19052-19063, 2020.
Michael B Cohen, Aleksander Madry, Dimitris Tsipras, and Adrian Vladu. Matrix scaling and balancing via box constrained newton's method and interior point methods. In 2017 IEEE 58th Annual Symposium on Foundations of Computer Science (FOCS), pp. 902-913. IEEE, 2017.
Robert M Freund, Paul Grigas, and Rahul Mazumder. Condition number analysis of logis- tic regression, and its implications for standard first-order solution methods. arXiv preprint 11Xiv:1810.00877, 2018
Prateek Jain, Ambuj Tewari, and Inderjit $ Dhillon. Orthogonal matching pursuit with replacement. In Advances in neural information processing systems, pp. 1215-1223, 2011.
Prateek Jain, Ambuj Tewari, and Purushottam Kar. On iterative hard thresholding methods for high- dimensional m-estimation. Advances in Neural Information Processing Systems, pp. 685-693, 2014.
Ziwei Ji and Matus Telgarsky. Risk and parameter convergence of logistic regression. arXiv preprint arXivv:803.07.300 2018
Sai Praneeth Karimireddy, Sebastian U Stich, and Martin Jaggi. Global linear convergence of new- ton's method without strong-convexity lipschitz gradients. arXiv preprint crxiv:1806.00413. 2018.
Mor Shpigel Nacson, Jason Lee, Suriya Gunasekar, Pedro Henrique Pamplona Savarese, Nathan Srebro. and Daniel Soudry. Convergence of gradient descent on separable data. In The 22nd International Conference on Artificial Intelligence and Statistics, pp. 3420-3428. PMLR, 2019.
Balas Kausik Natarajan. Sparse approximate solutions to linear systems. SIAM journal on comput- ing, 24(2):277-334, 1995.
Gunnar Rätsch, Sebastian Mika, and Manfred KK Warmuth. On the convergence of leveraging. Advances in Neural Information Processing Systems, 14, 2001.
Shai Shalev-Shwartz, Nathan Srebro, and Tong Zhang. Trading accuracy for sparsity in optimization problems with sparsity constraints. SIAM Journal on Optimization, 2066):280-2232,, 2010.
Daniel Soudry, Elad Hoffer, Mor Shpigel Nacson, Suriya Gunasekar, and Nathan Srebro. The im- plicit bias of gradient descent separable data. The Journal of Machine Learning Research, 19 (1):2822 2878, 2018.
Matus Telgarsky. Margins, shrinkage, and boosting. In International Conference on Machine Leam- ing, pp. 307-315. PMLR, 2013.
10

---

Under review as a conference paper at ICLR 2023
Matus Telgarsky and Yoram Singer. A primal-dual convergence analysis of boosting. Journal of Machine Learning Research, 13(3), 2012.
Sara Van de Geer. High lige-siimnsi generalized linear models and the lasso. The Annals of Statistics, 36(2):614-645 2008.
A MISSING PROOFS FROM SECTION 4
A.1 PROOF OF MAIN LEMMA
Lemma A.1 (Gradient lower bound). Let f BR + R be differentiable convex function and let
l-B,', B""" x [-B, 3) be two solutions for some parameters B' 2 B 0. For all E [n] define
G = O
A
fx if 2 B and Vef(x) Is <0
otherwise
where O < X < 1, and let i* = argmax, {sr [+](2)) }.
Then, at least one of the the following is true:
f(x) - f(x*)
\+-[(>)) 2
||000| 1| + X |
f(x) f(x*)
[+-((z) 2 --1 ||00 + |
and x; + 0.
Proof.
Let S = ii x # 0} and == = ii |x11 < or or V.l(x) 2 0}. By convexity of f. we
have
f(x)) 2 [(x)+ (V/ x² x)
2 (VF)z))/((z) x" x))
= f(x) + (VF((x) x²) (VsnFf
2 f(x) [ | - |/ |=||
therefore
V (ff()l)l |
V snn (=)) ||>|| f(x) f(x)).
(5)
Now, if S, by definition of the & and have
A >|Vrf(=)lls A f(x) sn
and so 5 implies
fxx) x + + f(x) f(x")
f(x) f(x')
[--((>)]> | + A |||||
Otherwise E S, we have
\snef(=)]ls = A
and so 5 implies
X
Vr f-)f(x)
x [V | 2 f(x) f(x²)
f(x) f(x
x x +
11

---

Under review as a conference paper at ICLR 2023
Lemma A.2 (Coordinate update). Let IR" 1R"-Ryy be twice continuously differentiable convex function that is 2yyseconn order robust and mndd2=mmlinn miimiiiiplccatiiely smooth with respect to the l norm, for some Y O. Let E [-B', B3Th be suboptimal solution such that f(x) 2 f(x"), where x² e [-B, B]" is some unknown solution with 7 |x 1, and B' 2 B > O are some parameters. We make the update.
x²' Vff(=)),
where picked as Lemma A. for some parameter E (0. and "i
0.5 min { (र))) Nर.(Cा } step size. Then, least one of the following is true about the progress in decreasing f:
(f(x) f(x)))
[(x) - [(x')
4-² f(x) (1|=*) 11 + X 1|=2112)
(f(x) f(x*)()
[(x) - ((x))
and x; # 0,
412 f(x) (A-1 x + 1=]11)
and the norm of the new solution is bounded || I max BB', B 3. In the case that f(x) < f(x") we have f(x') f(x).
Proof. We first consider generic update x'' T. By Taylor's theorem and the fact that is twice continuously differentiable, we have
f(x') f(=) (VI(x), vo,
for some z that is entrywise between æ and ă.
Since 2y-seconndordder-rouss and yy-mutiplicativelyssmooth with respect to the norm, as long the update is bounded in ε norm as
|ا||| - 1/
(6)
have
f(x') < f(x) + (V/(2),, (7. V (z) f()) (V](>),, + + 2 (()) |ل|
Note that the right hand side is minimized for
H1 (Vf(z)) 2x f())
where H2 is the hard thresholding operator that zeroes out all but the top entry in absolute value. This a coordinate descent step. Our step will be slightly more careful so that it doesn't 't unnecessarily increase the sparsity of We consider the following coordinate step
v(=),
where 7) > 0 and are as defined in the lemma statement. We now have
f(x) f(x') 2 (1 The term (17 1 f()))(x)) is maximized r .-त addition, to stay in the é neighborhood where the Hessian in stable, we need to satisfy (6) by making sure that 1) S 2;[../()]' Based on these requirements, we pick
(vif()))²
= min
(2>f((x)' v.f()
and conclude that
f(x) - f(x') 2 min
(V.f(x))²
(4>2f(x)' 4. [x))
(V.f(x))² V+f(z))
min
4y2
4y
Note that this always 2 0 and so we have f(x') ) < f(x) even if f(x) < f(x*). ). We now take two cases and use the two bullets of Lemma A.1 accordingly.
12

---

Under review as a conference paper at ICLR 2023
Case 1: x2 0.
The first bullet of Lemma
A.1 has to be true, i...
f(z) f(x=)
v.f(z)) >
x 1|
Therefore,
(f(x) - 1(=
[(x)) f(x*)
- - f(x') 2 min
fx)) (1|2* X | 4y (1|='11 1/2 + X 1121111)
(f(x) f(z)))²
(x2 (1 > \
where we used the facts that f(x) - f(x*) & f(z) and y || 1| 2 1.
Case 2: 2; F O. If the first bullet of Lemma A.1 is true, we can proceed in the previous case.
Otherwise, we use the second bullet of Lemma A.1 and similarly get
(J(x) (xx)))
f(x) f(x²) 2 f()) (A- x 1 + 1
Finally, in order bound || we first note that || B'. Now, by our choice of have that either [and] < B, or f(x()) 2ie > 0. In the first case, we have
B + 2ny
where we used (6) Otherwise, we have that |aaa| and H; have different signs, so
B and fif(z)
Iz > O. This implies that m;;
1
- = lx + 3,| < max (1rz),
[o. S max
B',
27
Therefore, in any case we have | S max { (B' 27
A.2 PROOFS OF THEOREMS
A.2.1 PROOF OF COROLLARY 5.1
Proof. We will apply Lemma A.2 for T iterations to obtain solutions x0 x". where for some T that will be defined later. The logistic function f is 2--send order robust and M mfl-multiplccatively smooth with respect the & norm, so Lemma A.2 can be applied with y M and B' B + 2M
Based on the guarantee of Lemma A.2
A.2 we get the following bound on the l norm of x at all times:
|>d||, I n | 1l.0 S n
B + 2M
S (3/2)nB.
Let be the smallest t 2 for which f(x²)= & 2z(x") or f(xt) S f(x") + E, and let f = oo if this
never happens. Therefore, for all I. < 7 we have f(x)) 2 25(x)) (aa")((a")) 2 2. and the statement of Lemma A.2 gives:
f(x
f(x') - f(x")
1(x') - 1(x(11) 2
8M2 xx || + ar 111)
f(x') f(x"
8n 2 M2 + B)2
f(x') (<'')=f(x*
50n
where we used the fact that || 5 n ||
< nB. Equivalently,
fax'11) - f(x²) (1
(f(x') M0n2>>B²> )
f(x)))
13

---

Under review as a conference paper at ICLR 2023
and summing up these for t {0, ........... 1}, we get
f(x²) - f(xx))
(f(x²) - f(x²))
M
S
as long
22 50n2 M B² log f(x²) - f(x")
therefore we conclude that & most this quantity.
Now consider the iterations & 2 f. If f(x²) I f(=") + there are such iterations and
done. Therefore we have that f(x²) - 2f(x").. We again use Lemma A.2 for all such which gives
(f(x') / fxx))
f(a²) - 11x(11)
4M² x 11 | 112)1122
2 (f(x') - f(xx))²
25
50f(<*)n2
By known convergence results, this recurrence leads the bound
100f(2 )n M
f(x < f(x")
T-i 100n² 2
$ f(x") (1+
T-
implying that f(x") $ (x=) after
T --i=0 (0nnn2nn (nPMP
additional iterations after T. Therefore, the total number of iterations to achieve {( (1+ f(x") E is
S
o (n'MM B² (1 + log ʃ(x)) ((a9)-((²')) 1(67)))
A.2.2 PROOF OF THFOREM 4.1
Proof. Similarly the proof of Corollary 5.1 apply Lemma A.2 for T iterations to obtain solutions x ......, xT, but now we also have to account for the sparsity increase x'. For this reason, use X which disincentivizes updating zero entries of the solution vector.
Compared to Corollary 5.1 we have the differences that --==|1101
x x:" max - ||00||,
|| [|==\|]]]]
and that we have the following tighter bounds because sparsity:
x
sB
x ||
0 ll |=01_~
s | (3/2)B.
We first bound the sparsity. Note that the sparsity increases by at most 1 every time the first bullet of Lemma is is true, and does not increase when the second bullet true. Therefore, the progress iteration is
in each
(f(x') - f(x*)) 4f(x* (||=') ||; + de || (f(x') - f(
f(x') f(x
4(1 f(= | 112
14

---

Under review as a conference paper at ICLR 2023
Completely analogously the proof of Corollary 5.1 this implies that the total number of such iterations (and thus total sparsity) is
(1 log
[(x9) ((00))((00))
=
-=11==1l oo
(1+ +c) (1
E
Now it remains to bound the total number of iterations. We have
max { ||x0|| + de
x A,
| || + || [|
x max
{1 ||1 + || ,
x
+ *||a 1
||00||
(1 (1+c=)) ||01||
3
< ||0|||
2 [1 c
|| |00l B
||
2 + (1+c-)) x B.
As result, the progress bound Lemma A.2 becomes
(f(x)-((x*))
f(x') f(x
4f(x)M² (|<*1|, + ) + c- x llo B)²
and, analogously to the proof of Corollary 5.1 and using the fact that | I || llo B, the total number of iterations is bounded by
T = O (1+
(1~*))
+ | M²
( + log f(x²) - =f(a²)
E
A.2.3
PROOF OF THEOREM 4.3
Proof. We move similarly the proof of Theorem but now we can strengthen Lemma A.2 because x' is fully corrected for all t, i.e. V.f(x") for all i e supp(x*). As in the proof of
Lemma A.2 we can lower bound the amount of progress as a function of V=(xx))l as follows:
f(x") - f(x min (V.f(x!))
Vif(=*)]
4M²)(x*')
4M
Now, by convexity of f we have
(Vf(x'), x' x²) 2 f(x") f(x").
Because of fully corrective steps we have (Vf(x*), x²) = 0, and so the left hand side of is upper
bounded by Vf(x*)ll | 1- As result, have
|( 2 (f(w) 1(x*))²
xx
and so we get the progress bound of
(f(x*) ((x)))
[ax') f(x*)
f(x²) - (1x')_((xtt))) 2 min
4M2 ff f(x))((x))))))))){)))) ||
4M x ll
(f(=*) fxxx))²
4M²)(w')) x
because M ||=||| ||, > 1. Similarly to the proof of Theorem
4.1 this progress bound leads to a sparsity
of
||= M² (3- + log f(x)) s(a'))
= x
50
E
and the same number of iterations.
15

---

Under review as a conference paper at ICLR 2023
B MISSING PROOFS FROM SECTION 5
B.1 GRADIENT UPDATE LEMMA
Lemma B.1 (Gradient update). Let f IR" - Ry0 be twice continuously differentiable convex
function that is secoec order robust with respect the (i norm and y-muliplicatively smooth with respect to the Eg norm for some 7, u > 0. Let a E Rn be a solution such that f(æ) > f(x"),
where x R an unknown solution with || x= 2l S ||=" ||00
We make the update
x¹ = )))),
where 7) 0.5 min
} is step size. Then, the progress in decreasing is:
f(x) f(x))= 2 min {
(f()))f(x*) - f(x*))2 f(x) f(x²)
41f((z) || 44/0l | 1l2
Additionally, long x' is still suboptimal with respect to x", iee f(x)) f(x)), the distance x² x²1l2. Finally, if f(x)= S f(x"), then f(x') S. f(x).
to x" decreases: x x= x=112 S 2|
Proof. We first consider a generic update x' = x + x. By Taylor's theorem and the fact that f is
twice continuously differentiable, we have
f(x') = f(x) (Vf(z), + (2,
for some that is entrywise between æ and x'.
Since f is 2y-ssccond-order-robur with respect to & and and j-multiplicativel--smod with respect
the & norm, long as the update is bounded in norm as
2 1l S 1/(27)
(8)
we have
f(x') & f(x) + (Vf(z) (7, (2x $ f()) + (Vf(x), + uf( x
Note that the right hand side is minimized for
I
2xf(x) Vf(x).
In addition, to stay in the é neighborhood where the Hessian in stable, need to satisfy 8 on these requirements, we make the update T = f(x), where
Based
min 2uf(x)) 2n [[ }
We thus have
((x) 5(x') > (n ))))(()) [V(())]
2 1 [
and so
1
f(x) f(x') 2 min
|Vf()))
4uf(x) 4y [V](()]l,
[V]())]
[Vf(a)]l
min
4uf(z) 4yy0
16

---

Under review as a conference paper at ICLR 2023
This takes care of the case f(x) & f(z"), since it shows that f(x') & f(x). Now we deal with the case f(x) > f(x"). ). By convexity we have
f(x)) 2 f(x) ((x) x x) 2 ((z) V (z) a [| x x: ll
f(x) (x) ll 112
which gives
(f(z) f(z*))²
|V 2
12
and
[(x) [(x') 2 min (f(z) f(x))) f(x) f(x 4xf((=) ||x0 112
44yn n x 2=112
For the norm bound, suppose that f(x') f(x²) (otherwise we are done). We have
|| x - x $12 - || x 11
|| x=12 ? 2(x x² x² x))
= xブ² [V.f(>))11 2n/xx xx, vf(x))
Now, note that
1 [ f(x) - f(x') - f(x) f(x*)
2
and by convexity (æ= x,, vf(z)) 2 - f( so
|| x² x x: 1
1/ [V[())] 2n/a - x. vf(z))
0.
B.2 PROOF OF THEOREM 5.2
Proof. We repeatedly use Lemma B. obtain iterates x: xx .e.....,a"" xT. f(x*) > f(x"), we have ||x - x || x 20112= R.
Note that as long as
Let 7 be the smallest i 2 for which f(xx) (x( or f(xt) S f(x") + e, and let -= oo if this f(a))
never happens. Therefore, for all t < f we have f(x²) 2 2f(x²) f(a))
> 2. and so the
statement of Lemma B.I gives:
1
S(x') f(x'+1) 2 min
(f(x')) -((x))
8p ||
4 xx |00
(f(x²) - f(x")).
8p x 112 + 4n |
Equivalently,
f(xtt1)-f(6 S
(f(z') - ((x))) f(x")),
8/ xx* 4 |
and summing up these for t E f0.1....,, F 1}. we get
7 8/ || 112 + 47 / (f(0)-)(=²))
1
f(x))f(x²)) f(x") <
1
17

---

Under review as a conference paper at ICLR 2023
as long
i 2 (8μR² + 4y/nR) log ʃ(x²)) s(xx))
therefore we conclude that ė is at most this quantity.
Now we consider the iterations 2 f. If fxx) S f(xx) + e there are no such iterations and we are done. Therefore we have that f(x²) - 2f(x") We again use Lemma B.1 for all such which gives
f(x') - f(x)))) (f(x')
f(="))²
(2) (s(m') {(x)))
3xf(x²) R2
By known convergence results, this recurrence leads to the bound
f(x²) f(xx)+ 16 RR --
={(x") (1+
16
T T-
implying that f(x?) S (1 (a) after
T --t=0- T- (w1z1)
additional iterations after Therefore, the total number of iterations to achieve
f(x²) $ (1 +1100 5) f(x*) +
o ((uté +V/RRR
(1 + log f(x.) [ax") f((=))
For μ = 3m 1,7 = VB, and using the fact that R 2 vT, we get
o 3R
(1
5 + log f(x²) - f(x'))
E
iterations.
C PROOF OF THEOREM 6.
Proof. Let consider classifier xx with ||=:"|| and margins 2 a, i.e. (((A"),, 2 for all i E [m]. Now, Corollary 5.1 and Theorem 5.2 imply that we can compute solution fx(Ø). S 2ff(x*) + E after = O (X X log ! iterations. Now, note that
Σ log(1 (1 +e e )b:))) < Σ log(1 + e (-bbi(Az"))) ): +
< 2m log(1 t te
2m +
< 3me
after setting -da
Now, re-arranging and using the fact that 3me Aa < 2 implies 3ime < 1 6me -ma- have that
b, (Ax)), 2 -X log ( Ao
-1)
2 -X-1 log (6me-
= a A -1 log (6m)
2 a(1 8)
18

---

Under review as a conference paper at ICLR 2023
where the last equality follows by our setting of À log(6m) a(1%a)= I (a=Es) Additionally, || I | 112-
Therefore, the number of iterations is
aē
To bound the distance from the classifier, we note that
E²
x
x:
a:
|
On the other hand, we let a
x and compute its smallest margin
1 12
bi( (((A)) k
o11-8)
2|
a
2
/
4 +
2 x*)
Re-arranging, we get that
1- 1- F3/4 2 4 (2 - 8) = - 8 8
E² < 48 8) 4
Therefore, we have
22VE
2
or in other words
S E
after (a2E2) iterations.
19


Reviews:
[{"review_id": "kzlmXQ0tcK", "reviewer": "Reviewer_qF3Q", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 4, "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": "", "summary_of_the_paper": "This paper proposes a greedy coordinate/gradient descent algorithm on logistic regression and proves a multiplicative convergence error and a linear convergence rate. Specifically, for sparse logistic regression, this paper proposes a coordinate descent algorithm where the learning rate is normalized by the logistic loss (or the gradient norm), and shows that the loss converges to $1.1f(x^*)$ at a linear rate where $x^*$ is a reference solution, and also provides a sparsity bound. If there is no sparsity constraint, this gives a convergence rate for dense logistic regression. In the linearly separable case, a poly(1/t) margin maximization rate is proved.", "summary_of_the_review": "Currently I put the paper marginally below the acceptance threshold; I think a detailed comparison with prior results should be included, and I also hope the authors can answer my questions above.", "strength_and_weaknesses": "I think linear convergence to $1.1f(x^*)$ is a nice result, since it interpolates nicely between the separable case and non-separable case. It is also interesting to obtain sparsity using coordinate descent. On the other hand, there is a large literature on this topic, which is poorly discussed. \n1. [1] considers the exponential loss and learning rate $\\frac{1}{f(x_t)\\sqrt{t}}$, and shows a $\\frac{1}{\\sqrt{t}}$ margin maximization rate. \n2. Lemma 4.3 of [2] proves the multiplicative smoothness property for the exponential loss and logistic loss. \n3. [3] uses an adaptive learning rate and proves $\\frac{1}{t}$ margin maximization rate. For the logistic loss, [3] uses learning rate $\\frac{1}{2f(x_t)}$ in the first phase and a slightly different normalized learning rate in the second phase. If the maximum margin is denoted by $\\alpha$, and the target additive margin-maximization error is $\\epsilon$, then [3] needs $\\frac{1}{\\alpha\\epsilon}$ iterations, while this paper needs $\\frac{\\alpha}{\\epsilon^3}$ iterations. Since it only makes sense to let $\\epsilon<\\alpha$, the convergence rate of [3] is better.\n\nI also have some technical questions:\n1. In Theorem 4.1 and 4.3, why do the sparsity bounds depend on $||x^*||_1$? Based on Corollary 4.2, it seems the bounds should depend on $||x^*||_0$.\n2. How do you get the $s^4\\log^3\\frac{1}{\\epsilon}$ iteration complexity in Corollary 4.2 from Theorem 4.1?\n\nReferences:\n\n[1] Mor Shpigel Nacson, Jason Lee, Suriya Gunasekar, Pedro Henrique Pamplona Savarese, Nathan Srebro, and Daniel Soudry, 2019. Convergence of Gradient Descent on Separable Data.\n\n[2] Ziwei Ji and Matus Telgarsky, 2018. Risk and parameter convergence of logistic regression.\n\n[3] Ziwei Ji and Matus Telgarsky, 2021. Characterizing the implicit bias via a primal-dual analysis.", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "Not applicable"}, "extra_text": {}}, {"review_id": "fpCZy6tlx00", "reviewer": "Reviewer_DG4g", "summary": "", "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": "", "summary_of_the_paper": "This paper considers the optimization of the logistic regression problem with separable data assumption. They observe that when the iteration variable is far from zero, the smoothness parameter decreases (i.e., the function is smoother), which allows more aggressively long step size. They prove the linear convergence of the modified algorithm to a multiplicative sublevel set. They claim this result improves the dependency on the magnitude of the optimal solution exponentially compared with existing works. They also show rate improvement on the sparsity and speed of alignment to a maximum margin estimator. ", "summary_of_the_review": "In sum, this paper studies a classic ML model and introduces interesting new analytic and algorithmic techniques to prove linear convergence to a sublevel set with better dependency on the magnitude of the optimal solution. The improved sparsity and alignment also seem very valuable for the community.", "strength_and_weaknesses": "This paper exploits two interesting properties of the logistic loss function, namely second-order robustness and manipulatively smoothness, to prove the sublevel set linear convergence results. The improved sparsity and alignment also seem very valuable for the community. My concerns are as follows:\n\n* The linear convergence results only concern the computation of a point with a sublevel set, which is fundamentally different from the sublinear rate of gradient descent methods. It might be somehow misleading to use the notation x^* in Tables 1 and 2 as for any bounded x^*, GD also has a linear convergence rate (as the loss function is sharp around such x^*). The \"Guarantee\" of the sublinear rate of GD should be written with inf f. It is recommended to clarify the meaning of x^* early in the introduction, as this might cause confusion even in the abstract part.\n\n* On Thm 5.2: it seems this theorem is a generalized version for any convex function with second-order robustness and multiplicative smoothness. But if we have f(x^*) < 0 and f(x^0) > 0, the statement seems problematic. We can choose a sufficient large delta such that (1+delta) f(x^*) + epsilon < inf f. The problem seems from Lemma B.1, in which the function is required to have a positive range. \n\nMinor: \n* Eq.(2): \"=\" should be \"<=\"", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "UI8KIaAUnBd", "reviewer": "Reviewer_9NWd", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 4, "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": "", "summary_of_the_paper": "The paper aims to characterize the convergence of gradient descent (and greedy coordinate descent) with carefully chosen (variable) learning rates for logistic regression. The analysis identifies two special properties of logistic regression loss function: second-order robustness and multiplicative smoothness, which implies that as the loss decreases, the objective function becomes (locally) smoother and the learning rate can be increased (proportional to the value of the loss) to achieve better convergence. This observation is applied to obtain new bounds on the convergence rate for sparse and dense logistic regression, which adds a multiplicative error term to the estimation but only depends logarithmically on the number of sample points. For linearly separable data, the loss approaches zero and the convergence becomes linear and is significantly better than pre-existing bounds.", "summary_of_the_review": "The paper addresses a meaningful question and the approach is novel and of broad interest. The work is strong in all aspects: novel and practical bounds, rigorous theoretical framework, and useful insights about the theoretical and algorithmic properties of the problem studied.", "strength_and_weaknesses": "### Strengths\n\n- The paper obtains a new and stronger bound on the convergence of (variable learning rate) gradient descent for logistic regression on separable data. The result is interesting since the loss function of logistic regression is not strongly convex. It also highlights the importance of variable learning rates for gradient descent.\n- The mathematical analyses of the work are rigorous and of high quality. Beyond the central result on separable data, several components of the analyses are technically interesting and could be of broad interest, including:\n    - the insight about second-order robustness and multiplicative smoothness of logistic regression, which gives rise to an intuitive schedule of the learning rate for better convergence\n    - the result on sparse logistic regression, though not completely dominate the result of Shalev-Shwartz et al. (2010), provides an altenative to approach the problem (and is better than the previous bound at least when f(x*) <<m). The result also provides a new technique to analyze convex but not strongly-convex losses for l1-regression.\n- The main ideas and techniques of the work were developed based on well-founded rationales. The paper is well-written with a sufficient literature review.\n\n### Weaknesses\n\n- None noted. However, I want to note that the title of the work doesn’t reflect the “variable learning rates” aspect of the result, which is a very important detail. This could lead to the result being misinterpreted in future discussions.", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "4: The contributions are significant, and do not exist in prior works.", "empirical_novelty_and_significance": "4: The contributions are significant, and do not exist in prior works."}, "extra_text": {}}, {"review_id": "3KgKSjRElTW", "reviewer": "Reviewer_gbUi", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 4, "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": "", "summary_of_the_paper": "In this paper, the authors studied logistic regression on separable data. It is known, for example in [1], that when the data is linearly separable, gradient descent (GD) on the logistic loss converges to the max-margin classifier with a very slow rate $O(\\log \\log t/\\log t)$. In the setting of sparse linear regression, the author considered coordinate descent and GD with varying step sizes---which builds on ideas from prior papers. A key contribution is the observation that logistic loss satisfies a condition called multiplicative smoothness, under which the step size is allowed to increase, which speeds up the convergence. Under the multiplicative smoothness condition, linear convergence results are established.\n\n[1] Daniel Soudry, Elad Hoffer, Mor Shpigel Nacson, Suriya Gunasekar, and Nathan Srebro, The im- plicit bias of gradient descent on separable data. The Journal of Machine Learning Research, 2019\n", "summary_of_the_review": "This paper is a nice addition to the growing literature on implicit bias and convergence properties of GD. I would recommend acceptance of this paper.", "strength_and_weaknesses": "This paper follows an interesting line of work where people study the implicit bias of GD algorithms for separable data (or more generally, data under over-parametrized models). The algorithmic aspect of implicit bias is the convergence properties of GD, including the convergence rate in particular. It is known that, somewhat undesirably, the convergence is very slow for logistic loss.\n\nThe idea of adapting the step size to objective value at each iteration is quite natural. I am not sure if multiplicative smoothness or similar conditions have been studied before, but it appears to me that this critical condition captures the structure of logistic loss well, and it is key to establishing the linear convergence rate. As far as I know, this multiplicative smoothness condition is a novel and useful notation.\n\nIn my opinion, the novelty of the multiplicative smoothness condition, the generality of the setup (sparse linear regression), and the strong results (linear convergence), are the main strengths of this paper. \n\nOne weakness is that the empirical condition on multiplicative smoothness assumed in Theorem 5.2 needs more justification. I imagine that \none can perhaps use some random matrix theory to provide an argument for why the empirical multiplicative smoothness is smaller by a factor of $m$. For example, if the matrix $A$ is random and $A, x$ are independent, then the trivial bound on multiplicative smoothness is too pessimistic and thus can be improved. Perhaps it can be shown empirically that even running a few iterations $A, x$ remain weakly dependent so multiplicative smoothness can still be bounded well. See [] for instance. \n\nThere are a few other places that need clarification.\n- There are some statements involving \"for any solution $x^*$\". For example, in Corollary 5.1, it is assumed that $x^*$ lies in $[-B,B]^n$. Do we choose $x^*$ to be the max-margin solution, or a scalar times the max-margin solution? Or is it an arbitrary deterministic solution?\nThis needs to be stated more clearly because the result depends on $B$.\n- The connection between coordinate descent and gradient descent is not clear. So it is a bit confusing how the results in Section 5 are related. \n\n\n[2] Y Zhong, N Boumal, Near-optimal bounds for phase synchronization, SIAM Journal on Optimization, 2018\n[3] Y Chen, Y Chi, J Fan, C Ma, Gradient descent with random initialization: Fast global convergence for nonconvex phase retrieval, Mathematical Programming, 2019", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}]

Author rebuttal:

Decision: Reject