Venue: NeurIPS 2022 Conference

Reviews:

final_score: rating: 6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.
review_content: summary: This paper studies the implicit bias of the solution found by mirror descent in the problem of classification with a linear model.
Similar problems have been studied for linear regression and/or gradient descent, but not simultaneously for mirror descent and classification.
To be fair, mirror descent is a very general optimization method, but here the paper considers a very specific setting, which they call "p-GD".
This stands for p-norm gradient descent, since (roughly speaking) the (p-1) power of the weights is used to update them.
Perhaps unsurprisingly, the main theoretical result is that p-GD finds the max-margin solution with respect to the p-norm, thus generalizing the previous finding that GD finds the max-margin wrt the 2-norm.
The results of some experiments are shown in support of the theoretical results.

strengths_and_weaknesses: Strenghts:
- The paper is very clear and well written.
- The study of implicit bias of solution found by optimization is an important problem.

Weaknesses:
- It is unclear to me how much this "p-GD" optimizer is relevant for the machine learning community, I don't know of anyone using it. 
Section 4.2 reports an application of p-GD to deep neural networks and image classification but, as acknowledged by the authors, those results are "out of the scope of our theoretical results", so it remains a bit unclear what conclusions we are supposed to draw.

Overall my opinion is that the strengths slightly outweight the weaknesses, so I vote for a weak accept. 

questions: Minor:
- How do we know that the argmin in Eq.2 and the argmax in Eq.3 are unique?
- Eq.(p-GD), first row, w*sign(w) is just the absolute value of w, which implies that the value of the weight w_{t+1} is always positive. 
Doesn't that limit drastically the solutions that can be possibly found by the optimizer?

limitations: OK
review_title: null

final_score: rating: 6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.
review_content: summary: This paper derives the implicit regularization effect for the mirror descent algorithm for linear classification tasks with the exponential-tailed loss and separable data. Specifically, with the potential function being $\Vert * \Vert^p_p$, it is shown that mirror descent converges to the $\ell^p$ max-margin solution. Experiments over linear models and deep neural networks are conducted to support the theoretical findings. 
strengths_and_weaknesses: Strengths:
1. This paper is well-written and I enjoy reading the paper.
2. The theoretical analysis is solid and explicitly explained (the connection with [Ji et al., 2020] is clearly pointed out). The experiment is detailed.

Weakness:
The major weakness lies in the motivation of the paper. The implicit bias of gradient descent (with momentum) and adaptive first-order optimizers over classification problems [Soudry et al., 2017; Qian et al. 2019; Wang et al., 2021] are studied due to their popularity in deep learning's application over classification tasks. However, mirror descent is less employed. Therefore, while it is good to know such a result, this problem has limited importance.

Reference:
1. Ji et al. Gradient descent follows the regularization path for general losses, 2020
2. Soudry et al. The Implicit Bias of Gradient Descent on Separable Data, 2017
3. Qian et al. The Implicit Bias of AdaGrad on Separable Data, 2019
4. Wang et al. Does Momentum Change the Implicit Regularization on Separable Data, 2021
questions: 1. More discussion on the importance of mirror descent in model deep learning is appreciated.
2. In [Soudry et al., 2017], a synthetic dataset is constructed with its max-margin solution known in prior, and the convergence to max-margin solution can thus be verified directly. It is suggested that the authors apply this methodology to verify the correctness of the theoretical results.
3. In this paper, special potential functions are considered. What is the difficulty to extend the results to general potential functions? 
limitations: Please refer to the "weakness".
review_title: null

final_score: rating: 7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.
review_content: summary: This work studies mirror descent in the classification setting with exponential and logistic losses and $p$-norm (to power $p$) potential functions, proving that when data is linearly separable and the step size is sufficiently small, this method converges to the maximum margin direction under the $p$-norm. The authors also describe rates of convergence as a function of iteration. Lastly, the authors perform numerical experiments demonstrating the claims of the theory for toy linear classification problems, as well as application to common deep network models on CIFAR-10, demonstrating the resulting weights have a distribution that reflect the structure imposed by the implicit norm regularization.
strengths_and_weaknesses: **Originality:** 
This work builds on a rich literature of previous work in theoretical analysis of implicit regularization and mirror descent. The main theoretical contribution appears to be that the authors have extended the analysis of Azizan et al. on mirror descent to the classification case where the loss is minimized only for an infinite-norm solution. While Gunasekar et al. have studied classification previously under exponential loss with steepest descent, this work analyzes mirror descent with separable update rules for the logistic loss, which is a more practically relevant setting. I think this work could do a better job of contrasting itself with previous analysis 

**Quality & Clarity:** 
I believe the theoretical results presented to be technically sound. The biggest issue is that there appears to be some inconsistency with respect to the loss function from result to result, which is a bit confusing to draw conclusions from (I elaborate in the *Questions* section). 

**Significance:**
It is of critical importance that we understand the implicit biases of our optimization algorithms in this era of overparameterized machine learning, and this work makes an important contribution by demonstrating how $p$-norm regularization can be achieved solely via efficient optimization methods in classification problems. In particular, it has been recently shown [1] that fast rates for interpolation in noisy settings require $p < 2$, so it is crucial that we go beyond standard gradient descent, both in theory and in practice. This work is an important step in that direction.

[1] Donhauser et al., "Fast rates for noisy interpolation require rethinking the effects of inductive bias." https://arxiv.org/abs/2203.03597
questions: I have one major question for the authors below. I assume that they will answer it satisfactorily, so I have decided to tentatively give this paper a **weak accept**. Depending on the response, I will increase my score to **accept** or decrease to **reject**.

**Questions:**
- The authors appear to be somewhat inconsistent regarding which loss function each result applies for. At the start of the paper (line 84), they suggest that most results will apply for exponential loss and logistic loss. However, it appears that the exponential loss cannot satisfy Lemma 2, because $\psi - \eta \exp(\cdot)$ can never be convex. On the other hand, the results on convergence rate are given only for the exponential loss (with proof for the logistic loss left as an exercise for the reader). Can the authors either 1) fix Lemma 2 so that the exponential loss works, or 2) specialize all results to the logistic loss, and omit the exponential loss in result statements?

**Suggestions:**
- Point out that when $d > n$, linear separability of the data is trivially satisfied. Additionally, comment more on the importance of the separability assumption (allowing interpolation / the loss to going to zero).
- Make a note that while the hinge loss does not satisfy the assumptions (it attains its minimum), it gives the same maximum-margin solution.
- More clearly define $u_p^\mathsf{m}$ and $u_p^\mathsf{r}$, and make it clear that the superscripts $\mathsf{m}$ and $\mathsf{r}$ are not parameters of the problem such as sample sizes. 
- Explain why the choice of $p = 1$ doesn't work.
- Add the citation [1] discussed under *Significance* above.

**Formatting/typographical:**
- Use a unified numbering scheme for theorems/remarks/definitions/etc. With so many, it is difficult to find them.
- (minor) Tables: use `booktabs` package
- line 206: "has exponential tail" -> "have exponential tail"
- line 251: "space constraint" -> "space constraints"

***

**Edit after review responses** 

The authors have satisfactorily responded to my main question, so I have increased my score from **weak accept** to **accept**.
limitations: As mentioned above, the analysis as-is appears to only apply to the logistic loss, even though it is presented in a generic manner that would appear to be able to accommodate other common losses like exponential and hinge. I found no ethical limitations with this work.
review_title: null

final_score: rating: 6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.
review_content: summary: This paper studies theoretical details of convergence point of Mirror Descent algorithm those are having potential function as p-th power of l_p norm. Moreover, in the case of linearly separable classification the convergence has been shown to be in the direction which is called generalized maximum margin.
strengths_and_weaknesses: Strengths:

- Paper is theoretically sound, and investigates theoretical characteristics of MD with more suitable potential function 1/p || . ||_p^{p} which could be applicable to train Deep Learning trainings.
- The paper studies further characteristics of linearly separable classes which is an important first step question to answer.
- There has been experiments performed to verify results.


Weaknesses:

- This would be interpreted as question as well instead of weakness, how do you choose the best p depending on the problem. Is this a new hyper-parameter to tune or there is a structured method to find the necessary p. I am more pointing this issue in terms of experimentation ?
-  Studying characteristics of linearly separable problems is interesting, but is there any way that p-GD could be studied more complicated decision boundaries ?

questions: - To me it seems that if we check multiple values of p, one of them likely to overperform p=2 case (SGD), so i was curious if there is way to do this process better. Also, it would be nice to have accuracy studies in experimentation with other Optimization Algorithms.

- Is it possible to understand characteristics of p-GD solutions with more complicated decision boundaries ?


limitations: -
review_title: null

Meta-review: metareview: This paper studies mirror descent in the classification setting with exponential and logistic losses. The reviewers agreed that the problem is important, and the paper is clear and well written.
confidence: Certain
Decision: Accept