Venue: ICLR 2023 Conference

Reviews:

final_score: rating: 6: marginally above the acceptance threshold
review_content: 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. 
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:

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

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

Minor: 
* Eq.(2): "=" should be "<="
clarity,_quality,_novelty_and_reproducibility: This paper is well written. See detailed comments above.
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.
review_title: null

final_score: rating: 8: accept, good paper
review_content: 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.

[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

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.

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

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

One weakness is that the empirical condition on multiplicative smoothness assumed in Theorem 5.2 needs more justification. I imagine that 
one 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. 

There are a few other places that need clarification.
- 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?
This needs to be stated more clearly because the result depends on $B$.
- 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. 


[2] Y Zhong, N Boumal, Near-optimal bounds for phase synchronization, SIAM Journal on Optimization, 2018
[3] Y Chen, Y Chi, J Fan, C Ma, Gradient descent with random initialization: Fast global convergence for nonconvex phase retrieval, Mathematical Programming, 2019
clarity,_quality,_novelty_and_reproducibility: Overall, I find the paper is clearly written. The quality of the theoretical results is high. The key observation, which is the multiplicative smoothness, seems to be novel; and the linear convergence rate results appear to be novel. In terms of reproducibility, I believe that the proofs should be correct, though I didn't check them very carefully.
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.
review_title: null

final_score: rating: 5: marginally below the acceptance threshold
review_content: 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.
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. 
1. [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. 
2. Lemma 4.3 of [2] proves the multiplicative smoothness property for the exponential loss and logistic loss. 
3. [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.

I also have some technical questions:
1. 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$.
2. How do you get the $s^4\log^3\frac{1}{\epsilon}$ iteration complexity in Corollary 4.2 from Theorem 4.1?

References:

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

[2] Ziwei Ji and Matus Telgarsky, 2018. Risk and parameter convergence of logistic regression.

[3] Ziwei Ji and Matus Telgarsky, 2021. Characterizing the implicit bias via a primal-dual analysis.
clarity,_quality,_novelty_and_reproducibility: The paper is well-written, though discussion of related work is not enough.
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.
review_title: null

final_score: rating: 8: accept, good paper
review_content: 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.
strength_and_weaknesses: ### Strengths

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

### Weaknesses

- 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.
clarity,_quality,_novelty_and_reproducibility: (see above)
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.
review_title: null

Meta-review: metareview:_summary,_strengths_and_weaknesses: This paper studies greedy coordinate descent and gradient descent on the logistic loss, in both separable and nonseparable scenarios (a more detailed summary is included below in this meta-review).  The paper has many strengths, however ultimately there was concern over missing references, including references containing claimed contributions of this work.  The authors did not upload a revision, and substantial changes are required, given the extent of the reference updates needed (see, for instance, below, and in reviewer comments).  As such, it is suggested that the authors continue and further revise their work, with careful attention to prior work, and submit to a later venue.

Detailed comments are as follows.

This paper studies convergence rates of greedy coordinate descent and gradient descent on logistic regression.  The work is reliant upon the fact that exponentially-tailed losses maintain a relationship between smoothness constants and function values; this relationship dates back at least to AdaBoost, and has been exploited for steepest descent with all lp norms.  Though this work cites some of these papers, it mistakenly refers to this smoothness relationship as a new discovery; see, e.g., the reviewer discussion below for many further references.  The other component of the paper are "oracle" style bounds that pay for the norm of a comparator.  This proof technique can be found in many places, for instance most closely in the paper "boosting with early stopping: [...]" by Zhang and Yu.

Further comments:

- A key issue with the paper, identified in the reviews below, are missing references and incomplete discussion of referenced papers for multiplicative smoothness and margin maximization rates.  The authors chose not to revise the paper in openreview, and later suggested changes to the first pages in an openreview comment, however it appears that much more extensive changes are needed.

- In the case of coordinate descent, the paper refers to work of Shalev-Shwartz and Singer, but that work uses Franke-Wolfe variants, whereas works of Telgarsky referenced by the reviewers directly invoke coordinate descent and are more similar (and also contain a discussion comparing to Shalev-Shwartz and Singer).

Minor comments:

- The presentation of coordinate descent has some modifications to the step size, specifically the function zeta.  Why is zeta there?  That is not present in AdaBoost (which uses "multiplicative smoothness" and achieves exponential rates) and does not seem necessary.  Step size care does appear in the work of Zhang-Yu referenced above, but overall this is a bit of a delicate discussion and should not be omitted.
justification_for_why_not_higher_score: Significant issues related to prior work.
Decision: Reject