Venue: ICLR 2023 Conference

Reviews:

final_score: rating: 5: marginally below the acceptance threshold
review_content: summary_of_the_paper: The paper establishes minimax object function for perceptron algorithm, and treat it as a minimax optimization problem. For this problem, faster convergence rate (than perceptron) can be obtained. 
strength_and_weaknesses: Strength. The minimax formulation is an interesting view of what perceptron tries to optimize, although it is fairly straight-forward.

Weakness
I am not sure what's the main message. Minimax problem is well-studied in optimization. This particular problem is a very specialized formulation of minimax problem. It will be nice to understand what makes it special and why it is not trivial to use some results for general minimax problems to derive convergence for this problem. Are there really new algorithms or merely reinterpretation of standard results for this specialized problem? If the latter, what's the benefit of the specialization?  
clarity,_quality,_novelty_and_reproducibility: I think the paper tries to cover multiple earlier works using minimax perspective (although some of the algorithms are not necessarily directly solving the minimax problem). I find it difficult to understand its consequence in optimization.

First it does not explain well what's especial for this problem that makes its analysis beyond existing analysis for minimax problem. 

Second some online terminologies are used which is different from what would have been used in the optimization literature, and makes it somewhat more difficult for researchers in optimization to make connection to this paper. I am not sure this is necessary as the authors did not treat the problem as an online learning problem at all, but only use online learning as a technical tool to prove optimization convergence results.

Third many different results that are not coherent are discussed. I am not sure that's necessary as it looses focus. 

What I have missed is that what new idea does this work bring to minimax optimization? 
summary_of_the_review: I think the paper has potential, and tries to make interesting interpretation and connection to minimax optimization of a very specialized problem related to the perceptron algorithm. 

However, due to the content of the paper, it should be regarded as an optimization paper. For such a paper, the problem considered is quite narrow, so I'd expect more, including  what's special about this problem beyond standard minimax optimization, and what are the new optimization methods this paper actually develops in the broader context of minimax optimization. As it is currently written, I find it hard to interpret its significance.
review_title: null

final_score: rating: 8: accept, good paper
review_content: summary_of_the_paper: This paper introduces a unified analysis for accelerated perceptrons via reduction to a certain minmax game. Improved rates are then achieved by designing the dynamics of the min and max player. The analysis is simple and easily captures several prior works as special cases, while also easily enabling the authors to develop new algorithms with improved rates.
strength_and_weaknesses: The paper is very strong overall. The writing is clear and the math is easy to follow (particularly for those already familiar with optimistic MD/FTRL). The analysis is elegant and leads to novel results while capturing existing works as special cases. 

My only issue with the paper is that there are some connections to recent works on acceleration that I think would be worth discussing in the paper. In particular, Allen-Zhu (2016) and Joulani (2020) similarly view accelerated algorithms as decomposing into two online learning algorithms with interacting dynamics, with optimistic FTRL being the key component in Joulani 2020. I think these are both similar in spirit to what's happening here and would be worth discussing (or at least citing).

- Joulani, P., Raj, A., Gyorgy, A., & Szepesvari, C. (2020). A simpler approach
  to accelerated optimization: iterative averaging meets optimism. In H. D. III,
  & A. Singh, Proceedings of the 37th International Conference on Machine
  Learning (pp. 4984–4993). : PMLR.
- Allen-Zhu, Z., & Orecchia, L. (2016). Linear coupling: an ultimate unification
  of gradient and mirror descent.

clarity,_quality,_novelty_and_reproducibility: The paper was well-written and easy to follow throughout. The approach is novel and unifies a number of existing works using relatively simple analysis.
summary_of_the_review: This is an excellent paper and I highly recommend its acceptance.
review_title: null

final_score: rating: 8: accept, good paper
review_content: summary_of_the_paper: Consider the problem of finding a linear classifier with positive margin for a given linearly separable dataset, which can be formulated as a bilinear minmax problem. This paper proposes a unified interpretation for two algorithms by Soheili & Pena (2012) and Ji et al. (2021) and a new algorithm based on Nesterov's accelerated gradient method. The key idea is to consider a slightly modified minmax problem---a game---and solve it via no-regret learning. The idea is reminiscent of the papers by Abernethy and Wang on interpreting convex optimization algorithms via no-regret learning in Fenchel games. 
strength_and_weaknesses: ***Strength***
The problem is classic. The results are new and interesting. The unified interpretation provides new insights. 

***Weaknesses***
I don't see any significant weakness. Due to the *unreasonably tight review deadline*, I only checked the proof of Theorem 3. 
clarity,_quality,_novelty_and_reproducibility: ***Clarity***
The writing is overall clear enough. Some minor flaws: 
1. Using $\Omega$ to write upper bounds of the iteration complexity is unusual. I think most of the $\Omega$'s should be replaced by $O$'s. 
2. Second paragraph on p. 3: The $O ( \mathrm{poly} (n) \log ( 1 / \gamma ) )$ rate seems to be wrong, as it does not vanish. 
3. I suggest writing $w$ and $p$, instead of $v$ and $q$, in (4) to keep the notations consistent. 
4. First line in Algorithm 2: The $\theta_t$ and $\beta_t$ should not be inputs. They are computed in the iterations. 
5. p. 9: I do not understand the sentence "we consider the ERM problem in (7)..." I suppose the authors are not solving (7) in Section 5.1. 
5. I think it is better to explicitly state that the function $g$ are the same in Section 4.2, Section 4.3, and Section 5.1. 

***Quality***
The paper is well written. 

***Novelty***
The paper is novel enough to me. One may be concerned about the technical novelty. The no-regret learning interpretations are reminiscent of the works by Abernethy and Wang; in particular, the unusual FTRL+ algorithm, unrealizable in standard online convex optimization problems, was also considered by Abernethy and Wang. Nevertheless, this paper does not directly apply existing results; the technical details are different enough and the unified interpretation of the algorithms by by Soheili & Pena (2012) and Ji et al. (2021) was not obvious to me. 

***Reproducibility***
This is a theory paper. 
summary_of_the_review: The paper considers a classic problem, is novel, and provides new insights for understanding existing algorithms. I don't see any significant weakness but only some minor flaws in the presentation. Therefore, I suggest acceptance of this paper.
review_title: null

Meta-review: metareview:_summary,_strengths_and_weaknesses: This paper proposes a formulation of the Perception algorithm as a minimax optimization problem, that is solved thanks to the use of Nesterov's accelerated method.

+ Novel contribution in a field that has been studied for long
+ Paper clearly written
- Empirical test could have been performed. 
justification_for_why_not_higher_score: Technical novelty not high enough.
justification_for_why_not_lower_score: Always hard to find a significant contribution on a field that has been long studied.
Decision: Accept: poster