- Rating
- 2
- Confidence
- 4
- Informativeness
- 2
- Presentation
- 1
- Soundness
- 3
Read review
Paper summary
The paper studies the parameterized complexity of training a single ReLU neuron (that is, empirical risk minimization). Given a sample of data points from with labels in , the goal is to find weights which minimize the empirical loss for some loss function . The paper considers the margin (the maximum separating margin for an optimal solution) as a parameter and shows an XP-algorithm (in terms of parameterized complexity) running in . Moreover, the authors prove a corresponding ETH-based running time lower bound and W[1]-hardness via reduction from Multicolored Clique.
Critical strengths
The paper settles the parameterized complexity status of a well known problem with respect to a new parameter (the margin).
Critical weaknesses
The margin parameter is not well motivated: The title claims that the margin "governs" the complexity as opposed to the dimension . I would expect an FPT result then, or at least an XP-algorithm for a smaller parameter. But and are incomporable (there are clearly instances where one is larger than the other and vice versa) and have the same complexity status. So it is not clear why is more interesting. It is even not clear how to efficiently compute the optimal margin beforehand.
The presented results are rather simple to obtain (adaptions of already existing ideas) and poorly presented:
The results are only starting on page 7 and are merely stated as a list of lemmas and theorems. The main pages do not contain any deeper technical ideas. All proof details (also some crucial ingredients for the algorithm like Lemma A.5 and Theorem A.6) are only given in the appendix, but I believe their correctness (I did not check them in full detail). The ideas are rather simple (an enumeration algorithm and a hardness reduction inspired by previous reductions). The writing seems heavily AI-generated and is not nice to read, often imprecise and rather hard to follow.
Questions for authors
Is there a good motivation for the margin as a parameter? (I think it is usually considered in classification tasks.)
Is it empirically large in practice (so that is small)?
How do you compute the optimum margin in practice?