acceptodds
Under review as a conference paper at ICLR 2027

Margin, Not Dimension, Governs the Complexity of Training a ReLU

Abstract

Training a single rectified linear unit on labeled points is -hard and -hard in the input dimension . Under the Exponential Time Hypothesis (ETH), no algorithm runs in time for any computable . We study the geometric activation margin of an optimal neuron. If some optimum separates the sample with margin at least , squared-loss training on rational data has a global minimizer computable in time , where is the input bit length. The bound extends to convex coercive losses with polynomial-time exact solvers for fixed activation patterns. Its exponent is independent of and optimal up to a constant factor: margin-promised training is -hard in and, under ETH, admits no algorithm. For squared loss, no computable margin rate asymptotically above holds uniformly across a family witnessing dimension hardness. Conversely, a computable uniform rate above gives a algorithm.

Primary area:
foundation or frontier models, including LLMs
Keywords:
ReLU training, activation margin, parameterized complexity, empirical risk minimization, computational hardness

Reviews

Among:
Shape:
1234this paper, Top 17%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.75 over 4 reviews, above 83% of the others.
Reviewer_EVBNOpenReview ↗
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 nn data points from Rd\mathbb R^d with labels in R\mathbb R, the goal is to find weights w∈Rdw\in\mathbb R^d which minimize the empirical loss for some loss function ℓ\ell. The paper considers the margin γ\gamma (the maximum separating margin for an optimal solution) as a parameter and shows an XP-algorithm (in terms of parameterized complexity) running in nO(1/γ2)polyn^{O(1/\gamma^2)}\text{poly}. 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 γ\gamma "governs" the complexity as opposed to the dimension dd. I would expect an FPT result then, or at least an XP-algorithm for a smaller parameter. But dd and 1/γ1/\gamma 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 γ\gamma 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 γ\gamma as a parameter? (I think it is usually considered in classification tasks.)

Is it empirically large in practice (so that 1/γ1/\gamma is small)?

How do you compute the optimum margin in practice?

Reviewer_if6JOpenReview ↗
Rating
4
Confidence
4
Informativeness
2
Presentation
3
Soundness
3
Read review
Paper summary

The paper present the following result on empirical risk minimization (training problem) of neural networks with ReLU activation under square loss.

  • They show that on instances with a margin assumption of γ\gamma instances under squared loss, single-neuron empirical risk minimization is solvable optimally in time n O(n1/γ)poly(L)O(n^{1/\gamma}) poly(L), for nn samples with input size LL with dimension dd, where γ\gamma is independent of dd.
  • They also show that the above dependence n1/γn^{1/\gamma} is essentially tight, even for every multiplicative factor of 1/γ1/\gamma.
  • They also show that margin 1/(d)1/\sqrt(d) is the turning point: for computable uniform margin rate above it there is a ϕ(d)no(d)poly(L)\phi(d)n^{o(d)} poly(L) algorithms.
Critical strengths
  • The paper presents important, tight result for a fundamental problem
  • The main message that the margin can replace teh dimension dependence is quite strong
  • I believe the result is sound
Critical weaknesses
  • No experiments
  • While the writing is generally good, some extra polishing of the intro may be helpful
Questions for authors

Could this margin assumption change the complexity for other ERM or learning formulations? could you elaborate?

Reviewer_tKgwOpenReview ↗
Rating
3(+1)
Confidence
3
Informativeness
2
Presentation
2
Soundness
3
Read review
Paper summary

The paper studies the computational complexity of training a neural network consisting of a single rectified linear unit (ReLU). Previous work by Froese et al. showed that this problem is NP-hard, that there is an XP-algorithm for the number d of dimensions, and that this algorithm is essentially tight: it is W[1]-hard with respect to d and if the ETH is true then there is no f(d)\cdot n^o(d) algorithm. This paper studies the complexity of this problem with respect to a second parameter: the geometric activation margin γ\gamma. For this, the input samples are normalized to the unit ball and now an instance is γ\gamma-separated if the activation boundary of an optimal neuron keeps every lifted input at distance at least γ\gamma (here lift means that the bias of the unique neuron is modeled as another weight). The paper has 3 main results:

  1. An XP-algorithm with respect to γ\gamma.
  2. For p≥1p\geq 1 and the l_p-loss: W[1]-hardness with respect to γ\gamma and a tight ETH bound.
  3. Assuming the ETH, there is no witness for the dimension lower bound above 1/(d)1/\sqrt(d).

JUDGMENT:

I did not check all proofs in detail, I mainly looked into the ideas and these were convincing. The exact computational classification of the problem with respect to γ\gamma is nice to see. As written in the weaknesses, however, the technical novelty is limited. Also, in my opinion, the current title claims more than what is actually shown. Hence, I think the paper is marginally below the bar for ICLR.

Critical strengths
  • the paper propose a new interesting parameter γ\gamma for an important well-studied problem

  • parameter γ\gamma in some sense combines a complexity view with a statistical view which is unusual for parameterized complexity

  • the paper provides tight complexity bounds with respect to γ\gamma

Critical weaknesses
  • the technical novelty is limited as there is no new technique and every result combines known algorithms/ideas. For example, the W[1]-hardness reduction is very close to the one of Froese et al and reuses their gadget.

  • the title claims that the margin and not the dimension governs the complexity of training a ReLU: I disagree here. In the appendix it is argued that d and γ\gamma are unrelated. Based on this statement, I don't see how such a conclusion is possible.

  • an issue of the new parameter γ\gamma is that (as the paper shows) cannot be computed efficiently. This immediately raises the question about the significance of the developed algorithm. Moreover, it is unclear how d and γ\gamma relate in practice.

  • in lines 213-217 5 additional results are announced but the appendix does not contain any further result.

  • in the main part only about 2.5 pages are used to present the main results such that not too many ideas can be presented there

Questions for authors

Q1: Did I understand it correctly that d and γ\gamma are unrelated? If yes, (1) How do you justify the title? (2) I think there should be a Lemma in the main part about this statement.

Q2: For me, getting an intuition of γ\gamma is quite hard. Are there natural classes of inputs for which γ\gamma is small? More generally, in which classes of inputs is γ\gamma a better parameter than d?

Q3: Lines 213-217 claims 5 more results: What are they are is this a fragment from an earlier version?

Q4: The result of Forese et al. holds for p∈[0,∞)p\in [0, \infty). Can you argue why your result is weaker?

Q5: Line 281: How is the optimization problem solved with the decision problem? Usually, one is confronted with integers and can use binary search. But this is not possible here, due to the loss not being an integer.

ADDITIONAL COMMENTS:

  • I think the term ReLU should be used at least once when rectified linear unit is mentioned

  • line 73: what is the preceptron rule?

  • cross references are often wrong: usually theorem x.y is written but it should be definition/problem/lemma etc

  • it is strange that the open questions section in the first paragraph contains a question which the paper already answers

  • it would be nice to have a concrete example in the main part where γ\gamma is also explained

  • in the related work: specify which activation functions are used: always ReLU? Moreover, the statement in Line 136 sounds much weaker than the one in Line 135; maybe rephrase

  • the statement in Line 216 seems to contradict the known W[1]-hardness for d

  • the 'cited to its core' sounds quite strange

  • Line 320: mention that ||x_i^2||<1

  • Line 336: this inequality seems strange to me: how can it be fulfilled if xi=−1x_i=-1?

  • Line 340: why γ∈(0,1]\gamma\in(0,1] and not γ∈(0,(2)]\gamma\in(0,\sqrt(2)]?

  • Lemma 3.1: describe the relation of n and M

  • the sentence in line 450 is strange

  • the paper of Doron-Arad has no venue etc

  • a visualization for the W[1]-hardness would be appreciated

Reviewer_pVfPOpenReview ↗
Rating
2
Confidence
3
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

This paper studies the computational complexity of training a single ReLU neuron. The authors consider the activation margin of an optimal solution and show that, under a margin assumption, a global minimizer can be found in time nO(1/γ2)n^{O(1/\gamma^2)}. They also establish a matching lower bound under ETH and study the relationship between the activation margin and the input dimension.

Critical strengths
  1. The paper provides both upper and lower bounds for the computational complexity of the problem. The matching bounds give a complete picture under the proposed margin assumption.

  2. The theoretical results are clearly stated, and the proofs appear to be carefully written.

  3. The paper is generally well organized. The authors also provide a detailed discussion of related work and explain how their results build on existing studies.

Critical weaknesses
  1. The technical novelty seems to be limited. The upper bound mainly combines two existing results: the perceptron compression argument for counting large-margin activation patterns (Ben-David et al., 2002) and the convex optimization approach for fixed activation patterns (Arora et al., 2018). The lower-bound analysis also builds on previous constructions (Froese et al. 2022; Diakonikolas et al. 2019). The main techniques are largely based on existing results. Theorem 4.1 is also a direct consequence of the upper bound and the existing dimension-based hardness result.

  2. The significance of the results is somewhat unclear to me. The paper focuses on exact optimization of a single ReLU neuron, which is a rather restricted setting, and the proposed algorithm can still be very expensive even when the margin is a constant. Moreover, the motivation for studying the activation margin is not convincing. The paper introduces this quantity to analyze the complexity of training a ReLU neuron, but it is not clear to me why this is a natural or important assumption.

  3. The interpretation of the results seems somewhat too strong. The title suggests that margin, rather than dimension, determines the complexity of ReLU training. However, the existing nO(d)n^{O(d)} algorithm and the proposed nO(1/γ2)n^{O(1/\gamma^2)} algorithm give a combined upper bound of nO(min⁡d,1/γ2)n^{O(\min{d,1/\gamma^2})}. Both parameters remain relevant. Moreover, the results concern exact optimization of a single ReLU neuron and do not explain the behavior of gradient-based training methods.

Questions for authors
  1. Could the authors explain more clearly what the main technical differences betweeen this paper and previous work? In particular, which parts of the analysis require substantially new ideas?

  2. Are there any natural examples or data distributions such that the activation margin assumption can be justified?

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.