Gradient Descent Converges Arbitrarily Fast for Logistic Regression via Large and Adaptive Stepsizes

Thank you for your comments and pointing out missing references. We will cite and discuss them in the revision. We address your questions below.

Q1: “The arbitrarily fast convergence rate is trivial in this setting…..”

A1: We respectfully disagree. Note that the algorithm you proposed is much slower than ours. This is because in Stage I, GD needs to attain a risk smaller than $\Theta(1/n)$, which requires $O(n/\gamma^2)$ steps for a constant stepsize or $O(\ln(n)/\gamma^2)$ for small adaptive stepsizes. In comparison, we show that GD with large adaptive stepsizes only needs $\Theta(1/\gamma^2)$ steps.

Moreover, we can improve our lower bounds construction to show that $\Theta(1/\gamma^2)$ steps is minimax optimal for any first-order batch method to find a linear separator for a separable dataset with margin $\gamma$. The proof is provided at the end of our response. Thus our algorithm is minimax optimal, while the algorithm you proposed is suboptimal by a $n$ or $\ln (n)$ factor. We hope this clarifies your concern!

Q2: “Unclear connection to Edge of stability (EoS). Although this work frequently references EoS, it does not establish a clear link to it. For GD, EoS typically refers to the phenomenon where $\lambda_{max}(\nabla^2 L(w_t))$ oscillates around $2/\eta_t$. However, this article does not analyze $\lambda_{max}(\nabla^2 L(w_t))$ or its relationship with $2/\eta_t$.”

A2: This seems to be a misunderstanding. Note that [Cohen et al., 2020] described EoS by

“...gradient descent enters a regime we call the Edge of Stability, in which (1) the sharpness hovers right at, or just above, the value $2/\eta$; and (2) the train loss behaves nonmonotonically over short timescales, yet decreases consistently over long timescales….”

The second bullet is exactly our definition of EoS, and is arguably more fundamental than the first bullet, since a key surprising feature of EoS is its inconsistency with the descent lemma (see their abstract). We believe our references to EoS are justified.

We formally define first-order batch methods: Let $\ell(\cdot)$ be a locally Lipschitz function. We say $w_t$ is the output of a first-order batch method in $t$ steps with initialization $w_0$ on dataset $(x_i, y_i)\_\{i=1\}\^\{n\}$, if it can be generated by $w_{k} \in w_0 +Lin \\\{\nabla L(w_0), \dots, \nabla L(w_{k-1})\\\},k= 1,\dots, t,$ where $Lin$ is the linear span of a vector set and $+$ is the Minkowski addition.

The improved lower bound: For every $0 < \gamma < 1/6$, $n>16$, and $w_0$, there exists a dataset $(x_i,y_i)\_\{i=1\}\^n$ satisfying Assumption 1.1 such that the following holds. For any $w_t$ output by a first-order batch method in $t$-steps with initialization $w_0$ on this dataset, we have $\min_{i\in[n]} y_i x_i^\top w_t> 0$ implies that $t \geq \min\\\{\ln(n)/(8 \ln 2), 1/(30 \gamma^2)\\\}.$

Proof: We define $d := \lfloor 1/5\gamma^2 \rfloor \geq 6,$ where $\lfloor \cdot \rfloor$ is the floor function. Let $(e_i)\_\{i=1\}\^d$ be a set of standard basis vectors. Note that all defined first order methods defined are rotational invariants. Therefore, we can without loss of generality assume $w_0$ is propotional to $e_1$. Let $k := \min\\{\lfloor \log_2 n \rfloor, d-2\\} \geq 4.$ We construct $(x_i, y_i)\_\{i=1\}\^n$ as follows. Let $y_i=1$ for all $i\in[n]$. For $j=1,\dots,k$, let $x_i := (2/\sqrt{5})e_{j+1} - (1/\sqrt{5}) e_{j+2}$ for $2^{k}-2^{k-j+1}+1 \leq i \leq 2^{k}-2^{k-j}$. Let the remaining $x_i$'s be $x_i:= (1/\sqrt{5}) e_{k+2}$ for $2^k \le i\le n$. Note that $\|x_i\|\le 1$ for $i=1,\dots,n$. Moreover, for the unit vector $w^* = (1/\sqrt{d}) (1,1,\dots,1)^{\top}$, we have $y_i x_i^\top w^* \geq \gamma$ for every $i$. Thus, the dataset satisfies Assumption 1.1.

For a vector $w$, we also write it as $w := (w^{(1)}, w^{(2)},\dots,w^{(d)})^\top$. Then, the objective function can be written as

Consider a sequence $(w_s)\_\{s=0\}\^t$ generated by a first-order method. We know the gradient at $w_0$ vanishes in all coordinates except the second and the $(k+2)$-th coordinates. By induction, we conclude that for $t \leq t_0-2$ for $t_0:= \lfloor (k+1)/2\rfloor,$ it holds that $w_t \in Lin\\{e_1, \dots, e_{t+1}, e_{k+3-t}, \dots, e_{k+2}\\}$. So for all $(w_s)_\{s=0\}\^t$, their $t_0$-th and $(t_0+1)$-th coordinates must be zero. By our dataset construction, there exists $i\le 2^k-1$ such that $y_i x_i^\top w_k= 0$ for $k=0,\dots,t.$ This means that the dataset cannot be separated by any of $(w_k)\_\{k=0\}\^t$. Thus, for the first-order method to output a linear separator, we must have $t \geq t_0-1 \geq \lfloor(k-1)/2\rfloor\geq \min\\{\ln n/(8 \ln 2), 1/(30 \gamma^2)\\}$.

We will elaborate on this lower bound and its proof in the revision.

We thank the reviewer for their comments and for pointing out the typos. We will make sure to fix all typos in the revision. We address your questions as follows.

Q1: “It is widely accepted that the average-iterate convergence and the last-iterate convergence are not directly comparable in general. Thus, the authors' comment that "Theorem 2.2 improves Proposition 2.1" is not accurate, since Theorem 2.2 is not about the last-iterate convergence.”

A1: When treating the output as part of the algorithm design, it is fair to compare GD with large adaptive stepsizes that outputs the averaged iterate and GD with small adaptive stepsizes that outputs the last iterate. Moreover, GD in Proposition 2.1 satisfies the descent lemma, so their averaged iterate would only be slower than their last iterate—so Theorem 2.2 improves Proposition 2.1. We will clarify this in the revision.

Q2: “The evidence provided by simulations and upper bounds actually motivates the following two intuitive points: 1. For the "large-stepsize" regime, the last-iterate convergence is not good in general, even with high burn-in cost. 2. … However, Theorem 3.2 only manifest the second point above. This might not be fatal, but the discussion about the first point I mentioned here is indeed missing in the main text.”

A2: We would like to point out that our Figure 1 does not seem to imply that “the last-iterate convergence is not good in general”. Our paper is limited to averaged iterate, and it remains open to analyze the performance of the last-iterate. We will comment on this in the revision.

Q3: “For linearly separable binary classification, …perceptron is able to find the separating hyperplane in the "last-iterate" sense after 1/\gamma^2 iterations, while the simulations and upper bounds in this paper intuitively suggest an evidence that logistic regression is only able to do so in an "average-iterate" or even "best-iterate" sense. This subtlety make logistic regression sounds like a method even worse than perceptron, at least for this task. The authors should elaborate more on this point.”

A3: When viewing output design as part of the algorithm, our algorithm (GD with large stepsizes and outputs the averaged iterate) matches perceptron in terms of step complexity. So it seems unfair to say our algorithm is “worse” than perceptron. Additionally, we have improved our lower bound construction, showing that our algorithm is minimax optimal among all first-order methods in this problem (see our response to Reviewer QkHV). We will make a detailed comparison with Perceptron in the revision.

Q4: “.... Even in the i.i.d. case, if the support of the data distribution is decently non-trivial, i.e., regions near the boundary are not null sets, \gamma will decrease as the sample size n increases, which will in turn amplify the burn-in cost $\gamma^{−2}$ in this paper. Thus, Assumption 1.1 has a significant oversight even for the optimization results in this paper.”

A4: This is a good question. First, we would like to emphasize that this is a standard assumption in binary classification problems and has been widely adopted in literature. We agree that under certain distributional assumptions, the margin of the empirical dataset might be a decreasing function of the sample size. However there are also other cases where the margin of the empirical data remains large. For example, this is the case if the population distribution is (almost) separable with a margin $\gamma$. We will discuss this in the revision.

Q5: “By the way, yi=1 in Assumption 1.1 is mathematically not a typo since all proofs go through even all labels are positive, but it makes the readers realize that the implication of the upper bounds (when all labels are positive) is not very interesting.”

A5: Note that our results apply to the case where $y_i \in \{\pm 1 \}$. In this case, we can replace $y_i$ by $1$ and $x_i$ by $y_i x_i$ respectively, then apply our current analysis. So our assumption that $y_i=1$ does not cause any loss of generality. We will clarify this in the revision.

Thank you for supporting our paper! We will make sure to correct all the typos in the revision.

Thank you for supporting our paper! You are correct that there is a typo in the statement of Theorem 5.2. We will make sure to fix it (and all other typos) in the revision. We address your other questions as follows.

Q1: “...Is this type of adaptive stepsize useful for non-separable linear classification problems? Does it help when training both layers of a 2 layer MLP (in theory or practice)? Does it help when training more realistic neural networks in practice?”

A1: Good question. Our main focus is understanding the benefits of EoS/large stepsizes. It is unclear to what extent our results generalize to other cases, such as non-separable linear classification, two-layer networks with non-linearly separable data, or even practical network training. We will comment on this as a future direction.

Q2: “eq (13): what is $(-\ell^{-1}(z))'$ referring to? What is z? Is this supposed to be the derivative of the inverse of negative ell evaluated at 1/n sum_i \ell(z_i)? If so, the "(z)" is a little confusing here.”

A2: Here $(-\ell^{-1}(z))$ should be replaced by $-\ell^{-1}$. This is a typo and we will fix it in the revision.