- Rating
- 1
- Confidence
- 2
- Informativeness
- 1
- Presentation
- 1
- Soundness
- 1
Read review
Paper summary
The paper aims to study what kind of "simple" solutions does a Bregman proximal-point algorithm produce for linear models with an exponential loss. The authors don't say it explicitly, but this typically occurs in Poisson regression, but Poisson regressions typically have a linear term.
Critical strengths
I was not able to find any strengths, unfortunately.
Critical weaknesses
For me personally the paper was very hard to follow. Filled with lemmas with a lot of cryptic letters and formulas, and symbols, carrying little meaning either geometrically or algebraically. The paper is simply unreadable for me.
The definition of the margin at the beginning, Defn 2.1, was simple. The motivation to the study of the exponential loss needs to be explained. It's not exactly Poisson regression per se. The theoretical study of this setting needs some motivation which is not obvious.
But starting from definition 3.1 the cryptic symbols begin. Why the weights in were chosen the way they were? Why use ratios? What is the motivation behind this definition?
In proposition 3.3 - what is the referred-to null-set?
In Proposition 3.6, item (2) appears to be a proof of linear convergence. It itself probably needs mentioning (contracting a loss by a constant factor), but on the other hand, the loss is exponential so it's not very meaningful. In any case, an explanation of the impact of the results is required.
And it continues on and on throughout the paper. Just a bunch of propositions with a lot of letters, definitions, and results, without explaining their meaning, impact, or giving the readers any insight.
The paper needs a serious revision before publishing, remembering that we write for humans.
Questions for authors
NA
Hard to ask questions about something so hard to follow.
4 comments
Response to Reviewer beME (Part 2)
[W4] Proposition 3.6(2): Item (2) appears to be linear convergence of the loss, which is not very meaningful for an exponential loss, and the impact of the results needs explanation.
Proposition 3.6(2) shows that, with adaptive stepsizes, each proximal step contracts the loss by a constant factor. However, this contraction is not a consequence of the exponential form of the loss. It comes from the convexity of the loss, which gives the one-step inequality
Then, by the inequality , we get . By the bound , we further get
This also holds in the proof for constant stepsizes. We observe that and appear together as a product. If this product is set to , i.e., , we get . This implies that is at most a factor . This contraction does not rely on the explicit form of the exponential loss. It uses only the convexity of the loss, the inequality and the bound on . The result thus shows how to choose the stepsizes so that the loss contracts. The same argument can also be considered for other losses with an exponential tail. The exponential loss itself is the standard choice for linearly separable data, as discussed in [W1]. We have added this discussion after Proposition 3.6 (lines 273–275).
[W5] Readability: The paper is hard to follow, with many symbols and propositions whose meaning and impact are not explained.
We have revised the presentation at the places the reviewer points to, and where the same issue arises. The results and their proofs are unchanged. The revision adds short explanations and simplifies some statements, and all changes are highlighted in the revised version.
In the introduction and Section 2, we add why separable data and the exponential loss are studied (see [W1]), and the loss is stated once so that the theorems do not repeat it. In Section 3, Definition 3.1 and Condition 3 are each followed by a sentence on what the quantity is for and what it gives (see [W2]), and Proposition 3.2 is stated without auxiliary quantities. The assumptions of Theorem 3.5 are stated as a separate condition, with a sentence on what each case allows. Proposition 3.6 (accelerated rates) states the convergence results for each stepsize, together with a discussion of the loss contraction (see [W4]). Theorem 3.8 states clearly that Theorem 3.5 (implicit bias under alignment) is sharp. In Section 4, we explain the motivation and the role of each proof step in more detail. In Section 5, we add a discussion of why the solution of the proximal step has to be selected in this setting. In Section 6, we add the setting and the takeaway of each experiment.
References
[1] Soudry, Hoffer, Nacson and Srebro. The implicit bias of gradient descent on separable data. ICLR, 2018.
[2] Gunasekar, Lee, Soudry and Srebro. Characterizing implicit bias in terms of optimization geometry. ICML, 2018.
[3] Lyu and Li. Gradient descent maximizes the margin of homogeneous neural networks. ICLR, 2020.
[4] Ji and Telgarsky. Characterizing the implicit bias via a primal-dual analysis. ALT, 2021.
[5] Wang, Hu, Muthukumar and Abernethy. Faster margin maximization rates for generic optimization methods. NeurIPS, 2023.
Approaching the end of the discussion period
Dear Reviewer beME,
Thank you again for your review. We have discussed the points you raised and answered the question about the setting. We have also made a dedicated revision of the presentation. As the discussion period ends soon, we wonder whether we have addressed your concerns, and whether any question remains.
Best regards,
The authors
This addresses some of my concerns, but my main readability concern stays - it's a very terse and compressed bulk of symbols, indices, definitions, letters and various cases. I do understand that there's an underlying theme - the margin the direction of the parameters converges to, but it's simply extremely hard to read. Perhaps such a paper doesn't even fit the ICLR short paper format, and should have been a JMLR paper, or alternatively, reduced in scope and made more focused. The concerns are impossible to address with a small diff. I do not believe readers of this papers will be able to learn something from it.
Response to Reviewer beME (Part 1)
We thank the reviewer for the review, and respond to the weaknesses and questions in the following.
The paper studies binary classification with linear models on linearly separable data. This differs from Poisson regression: the labels are ±1, and the exponential loss is used as a classification loss. The exponential loss is the standard choice in this line of work [1-5], and we use it to keep the presentation simple. As for the motivation, on separable data, the loss can be driven to zero along infinitely many directions, so the optimization algorithm itself decides which classifier is returned. This selection is called the implicit bias, and separable classification with an exponentially-tailed loss is the standard setting in which it is studied. It arises in the over-parameterized regime with respect to the number of data points n and the model dimension d, and its characterization helps to understand the generalization of over-parameterized networks. We characterize the classifier selected by the Bregman proximal point algorithm and how this implicit bias depends on the divergence. The paper states this motivation in the introduction (lines 53–78) and the setting in Section 2 (lines 134–141).
cˉT is the weighted average of the alignments ct over the first T steps,
cˉT=∑t<Trt∥Δt∥∑t<Tctrt∥Δt∥,
where ct is the cosine similarity between the primal update and the dual update of step t, ∥Δt∥ is the length of the step, and rt is the ratio of consecutive losses.
This quantity appears in the lower bound on the margin and simplifies the proof. Proposition 3.2 gives mini⟨θT,zi⟩≥−logn+γ∑t<Tctrt∥Δt∥, in which step t enters with the weight rt∥Δt∥, and this is why these weights are used. Dividing by ∥θT∥ gives
mini⟨∥θT∥θT,zi⟩ ≥ −∥θT∥logn+γcˉT∥θT∥∑t<Trt∥Δt∥.
As ∥θT∥→∞ and the steps become small, the first term vanishes and the last ratio is asymptotically at least one, so the normalized margin is at least γcˉT in the limit. Since cˉT is what remains in the final result, we give it a name, which simplifies and unifies the statements.
It also connects this inequality with the theorems. The alignment condition gives a lower bound cw on cˉT, where cw is the alignment constant that appears in the margin guarantee of Theorem 3.5 and is shown to be tight for quadratic divergences.
We have added this explanation after Definition 3.1 (lines 184–186).
The null set accounts for distance-generating functions that are not strongly convex. It allows the lower bound λ(θ) on the Hessian to vanish at some points, as long as these points form a set of measure zero, and this does not affect the conclusion that the alignment constant cw is positive. Thanks to this assumption, the result can handle radial powers such as p1∥θ∥2p, whose Hessian vanishes at some point (Example 3.4).