Venue: ICLR 2022 Conference

Reviews:

final_score: rating: 5: marginally below the acceptance threshold
review_content: summary_of_the_paper: This paper extends the max margin analysis of the gradient descent (GD) method (using an exponential tail loss with linearly separable data) to its analogous analysis of the Bregman proximal point algorithm (BPPA) and mirror descent (MD). Unlike the GD converging in direction to the max margin solution, the authors show that BPPA/MD converge in direction to a solution with a margin depending on the condition number of the distance generating function.
main_review: Strength
1. Bregman proximal point is gaining interest in applications as mentioned by the authors, and understanding the property of its convergence direction (for a linearly separable data) is of significant interest.
2. This is a non-trivial extension of Gunasekar et al. (2018) showing that the GD converges in direction to the max margin solution for a linearly separable data.

Weakness
1. Applications: For a novice like me on the use of Bregman proximal point method in applications like knowledge distillation and mean-teacher learning (listed in page 1), providing such examples explicitly in the beginning with the specific choice of the Bregman distance could have been useful. I believe that this will also better motivate the presented work from the beginning, although some are mentioned later in the experiments section.
2. Non-trivial margin: It is not clear whether the convergence in direction to "non-trivial margin" solution has any important meaning. The GD converging in direction to the max margin solution somewhat suggested that the GD will generalize well, in the literatures. However, I don't see what one can claim from the non-max margin by BPPA/MD that is $\sqrt{\frac{\mu_w}{L_w}}$-times the max margin. The authors claim, after theorem 3.1, that the data-dependent divergence leads to a better separation and margin, but I don't think there is any theoretical justification for this. Let me know if I am missing something here. This also applies to the sentence "the Bregman divergence in BPPA is highly important to the quality of the obtained solution". I hope to see a more detailed explanation on the "quality" of the solution.
3. When the distance generating function is chosen to be the Mahalanobis distance, one has the max margin solution. Then, what does this make interesting over the classic GD that also find the max margin solution? The authors are aware of such fact (see the beginning of page 5), but other than this is a non-trivial derivation, I don't see any benefit of using BPPA over GD, which I expected from the abstract of this paper.
4. Conditions for the distance generating functions: To the best of my knowledge, the KL divergence in page 9 is not smooth. I suggest the authors clarify this.
5. Experiment on CIFAR-10: The authors claim that BPPA performs better than SGD in early iterations, which is not evident from the figure. In addition, the provided theory is interested in the asymptotic behavior of the methods, and asymptotically SGD and BPPA seem to behave similar in this experiment.

Comments
- page 2: I think (Bregman) proximal point algorithms are considered to be in the class of first-order algorithms.
- page 4: What is the reference point you are referring to? Could you also explain this and the corresponding non-trivial convergence results in more details?
- page 8 synthetic data: How about a constant step size that depends on $L(\theta_t)$? Is either $L(\theta_t)$ or \frac{1}{\sqrt{t+1}}$, or both making the adaptive BPPA/MD better, over the constant step BPPA/MD?
- page 8 synthetic data: How about considering the non-Euclidean distance here?
- page 8 mixture of sphere: Are the choices $D^{(2)}$ or $D^{(3)}$ standard? Any references? Are the first and second figures in figure 2 really almost the same? I personally think that the explanation of this section can be largely improved. I was not able to understand many points clearly. 


summary_of_the_review: The theory is new, but the theory does not seem to support the authors' claim that BPPA finds a better data-dependent solution. The experiment also do not seem to fully support the author's claim.
review_title: null

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: This work studies the use of Bregman Proximal Point Algorithm(BPPA) on training linear classifiers using seperable data. The paper focuses on theoretical findings of the following form

a) BPPA obtains a solution with non-trivial margin lower bound. For the mahalanobis distance, they show that the solution is a max-margin solution. They also show non-asymptotic analysis for constant step size and speed it up to exponential step size using a stepsize selection.

b) Show that the max-margin lower bound is dependent on the condition number of generating function for defining the divergence. As a result suggest that the divergence should be chosen based on the underlying space on which the data resides.

c) It shows that that above results also extend to the dual first order algorithms such as mirror descent.
main_review: Strength

The paper is a very well written paper with analysis and shows the properties of the BPPA algorithm and mirror descent algorithms to learn a linear classifier using separable data. To the best of my understanding the analysis seems correct. I have gone through the proofs and they seems fine.  However, I am not sure if there is earlier work with this analysis for the particular problem they deal with.

Weakness

The main issue or concern is how relevant is the study of these algorithms to find a linear classifiers on separable data. As suggested in future work, even if they had shown empirical results on the non-linear classifiers with some heuristics would have significantly improved the contribution of the paper.

Overall my belief is that the work  has some good results but I am not sure of the relevance of these results in the present day machine learning.
summary_of_the_review: The paper addresses the use of BPPA algorithm and the mirror descent algorithm to find the max-margin linear classifier in case of separable data.  My only concern is if there is some other work if this has already been addressed and relevance of the work to present day machine learning.
review_title: null

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: This article provides an analysis of Bregman PPA / mirror descent for classification. This work is largely motivated by the recent works on implicit regularisation (of gradient descent). Their theoretical results show how the recovered margins depend on the Bregman divergence used.
main_review: The typical study of implicit regularisation in the literature looks at how doing plain gradient descent on reparameterized problems lead to bias effects (such as sparsity or low rank). Moreover, these regularisation effects are because gradient dynamics along with reparameterization precisely correspond to mirror flows. I find it slightly odd that you call your setting 'implicit regularisation', because your results are dependent on a norm which is explicitly imposed by the Bregman divergence used. In this sense, I find the results obtained unsurprising. Moreover, many of the citations are related to implicit regularisation, and very few to the study of mirror descent. For example, 
Orabona, Francesco, Koby Crammer, and Nicolo Cesa-Bianchi. "A generalized online mirror descent with applications to classification and regression." Machine Learning 99.3 (2015): 411-435.
Ghai, Udaya, Elad Hazan, and Yoram Singer. "Exponentiated gradient meets gradient descent." Algorithmic Learning Theory. PMLR, 2020.

I think what is missing is a review of the existing theoretical contributions on mirror descent and the authors should clarify their contributions in the context of existing works.
summary_of_the_review: In my opinion, linking this to implicit regularisation is an over-sell of the paper. The authors derive some interesting results on margin convergence, but similar results also exist in the literature, and proving convergence results in terms of the norm that you are strongly convex with respect to is not new.
review_title: null

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: This paper studies theoretical properties of Bregman proximal point algorithm in the linearly separable binary classification problem. The main theorem shows that the margin obtained by BPPA is lower bounded by the maximum margin multiplied by a factor, which depends on the distance generating function of the Bregman divergence. Similar results are extended to mirror descent. The theorems emphasize the importance of the choice of Bregman divergence, which is further demonstrated in several numerical experiments.
main_review: ## Strengths

This paper provides a framework to study theoretical guarantees of BPPA. It provides both a lower bound and an upper bound on the margin obtained by BPPA, both depending on the condition number of the distance generating function of Bregman divergence. It is a step-stone for further studies about BPPA and relevant algorithms.

## Weakness

1. The setting is restricted to binary classification on linearly separable data. I'd want to know how the results generalize to other settings, like regression and multi-classification. 
2. No comparison with the convergence rate of SGD. Since SGD is the more popular alternative of BPPA, it would be helpful to state the convergence property of SGD and make a comparison with BPPA. There are some comparisons in experiments. But the difference between SGD and BPPA is not very large. It would be interesting to know which one is better in a certain situation. 
3. The comparison between SGD and BPPA in the experiment with CIFAR-100 may not be a fair comparison. Tf-KD\_self is a more sophisticated method than the one studied in this paper. There are also variants of SGD, e.g. Adam, which are more commonly used and probably more efficient. So comparing vanilla SGD with Tf-KD\_self does not seem fair.

summary_of_the_review: I recommend accepting the paper. Even though the setting is restricted to binary classification with linearly separable data, it adds some new understandings of the properties of BPPA and gives some suggestions on how to choose the Bregman divergence.
review_title: null

Meta-review: The paper extends the analysis of Telgarsky (2013) and Gunasekar et al. (2018) to the Breman proximal point algorithm and to mirror descent. Upper and lower bounds show a dependency on the condition number of the distance generating function used in the Bregman divergence.

The paper received lukewarm reviews, also because the topic does not seem to be a good match for this community. In fact, none of the algorithms analyzed seem to be commonly used as optimization algorithms for deep learning, despite of the applications mentioned by the authors.

So, I didn't take into account the concerns about the relevance of the results for deep learning people, the complains about missing references from the OMD literature, and the supposed restricted setting.

However, even ignoring the above issues, the paper seems to fall squarely on the borderline. Hence, I carefully read it.

It seems to me that the analysis heavily builds on previous work, in particular the seminal paper of Telgarsky (2013) and the Fenchel-Young trick in Ji&Telgarsky (2019). The part on the Bregman divergence is novel, but technically speaking it is also straightforward for people in this sub-community. For example, Lemma B.3 is very well-known to any optimization person. Moreover, the curvature of the Bregman divergence is exactly the term one would expect to appear. So, the upper bound seems to be incremental compared to past work and it does not really add much to our understanding of this problem.
The matching lower bound is probably the only truly interesting result. However, it still does not exclude the possibility to achieve a better margin when measuring it in a different way. Indeed, measuring the margin according to the (dual) norm appearing in the strong convexity definition of Bregman divergence is not completely justified, but rather it seems a way to make the analysis work coherently.

Overall, given the overall lukewarm reviews and my evaluation of the limited novelty of the theoretical results, I recommend rejecting this paper.
Decision: Reject