acceptodds
Withdrawn from ICLR 2027

The Price of Convexity in Squared-Loss Representations

Withdrawn from ICLR 2027, so left out of the paper lists and the map.

Abstract

How much does requiring convex prediction losses restrict a model's representation? We study bounded scalar predictors on a fixed convex parameter domain, with squared losses that are -weakly convex for every input and label. We prove that any finite prediction sign matrix realized with margin has sign-rank at most whenever , where is the parameter dimension and bounds the domain radius. The proof controls squared loss on convex hulls of parameter witnesses and then separates those hulls; it requires neither differentiability nor a nonvanishing gradient. An explicit family of bounded-weight ReLU networks with nodes yields an exponential dimension separation: approximation within requires either or . A smooth two-parameter construction shows that the coefficient in the small-margin curvature threshold is optimal. These are unconditional geometric representation bounds for direct squared-loss parameterizations, not lower bounds on optimization time or statistical performance.

Primary area:
learning theory
Keywords:
Representation complexity, convex parameterizations, weak convexity, sign-rank, ReLU neural networks, approximation lower bounds

Reviews

Among:
Shape:
1234this paper, Bottom 1%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 1.00 over 3 reviews, above 0% of the others.
Reviewer_bsPhOpenReview ↗
Rating
1
Confidence
3
Informativeness
1
Presentation
1
Soundness
2
Read review
Paper summary

This paper studies the representational limitations of bounded parameterizations with convex or weakly convex squared losses. The main result shows that sufficiently small negative curvature forces the prediction sign matrix to have sign-rank at most (q+1), where (q) is the parameter dimension. Combining this with a classical Hadamard sign-rank lower bound, the authors obtain an exponential dimension separation from compact ReLU representations. They also provide a construction showing that the leading constant in the curvature threshold is asymptotically optimal.

Critical strengths

The paper establishes a quantitative relationship between weak convexity and sign-rank, with a simple and self-contained proof. The construction showing that the leading constant in the curvature threshold is asymptotically tight is also a nice addition.

Critical weaknesses

My main concern is the limited novelty and significance of the results. The exact convexity phenomenon is closely related to existing results on convex representations and sign-rank, particularly Chornomaz et al. (2025), and the geometric argument is quite elementary in this specialized setting. The main weak-convexity theorem provides a quantitative extension, but the extension itself seems technically straightforward, relying on a weak-convexity inequality followed by the same convex-hull separation argument. The exponential ReLU separation is then largely a direct consequence of classical sign-rank lower bounds. Overall, I find it difficult to identify a substantial new conceptual or technical contribution.

I also find the writing rather formulaic and repetitive, at times reading like AI-generated text. In particular, the manuscript spends considerable space on qualifications about what the results do not establish, while offering relatively little deeper intuition or motivation for why the results are important. This further weakens the presentation of an already fairly narrow contribution.

Questions for authors

Could the authors clarify the novelty of Theorem 2 relative to Chornomaz et al. (2025)? The underlying convex-hull separation argument seems essentially the same, with the main additional step being a straightforward application of the weak-convexity inequality. Is there a more substantive technical distinction?

It seems that Theorem 2 can be derived fairly directly from Theorem 3 of Chornomaz et al. (2025) by constructing a suitable convex surrogate from the weakly convex squared loss. Is there any obstacle to this reduction? If not, what is the substantive novelty of Theorem 2 beyond the existing result?

Reviewer_YqNROpenReview ↗
Rating
1
Confidence
4
Informativeness
1
Presentation
2
Soundness
1
Read review
Paper summary

This paper provides some theoretical results on how requiring the convexity of squared loss in the model parameters restricts a model’s expressive power.

Critical strengths

The main focus of the article is direct, clear, and easy to understand. I did not find obvious flaws in the mathematical details.

Critical weaknesses
  1. The paper is far below the 9 page limit on its main contents. Although the paper length does not completely reflects the quality, it does affect the reviewers' impression on its richness and whether it meets the standard of a ICLR paper.

  2. As the author(s) stated in 'AI Use Statement' section, GenAI tools were used extensively to develop and refine the mathematical contents. Much of their contents include explicit defensive expressions, which further illustrates that the contents may not be carefully modified by human. Considering its focus on learning theory, I cannot identify how much contributions and theoretical understandings were generated solely by GenAI without human participation.

  3. According to the contents, the importance of these results and their impact on real ML problems are insufficiently demonstrated.

Questions for authors

None

Reviewer_JC7POpenReview ↗
Rating
1
Confidence
4
Informativeness
1
Presentation
1
Soundness
1
Read review
Paper summary

This paper studies how convexity of squared losses restricts model expressiveness. It connects weak convexity to sign-rank bounds and uses compact ReLU constructions to show that convex representations may require exponentially many parameters. It also establishes a sharp small-margin curvature threshold.

Critical strengths

none

Critical weaknesses

The manuscript discloses extensive use of generative AI, but my concerns center on the resulting presentation: several claims are difficult to interpret, proofs are overly compressed, and specialized concepts are introduced without sufficient context or explanation of their connections. My main concerns are the clarity of the formulation, the exposition, and the significance of the results. As a couple of examples on the lack of clarity and details: In proposition 1: it says that endpoint losses suffices. But it is unclear what sufficiency it refers to? In general, the joint distribution of (x,y) and the function form h (such as smoothness) determines the population version of the objective. Yet, they do not show up anywhere in this paper. I am very concerned about the correctness of this paper. The proof should explicitly include the quadratic correction involving (\rho). More broadly, the paper should better explain how this distribution-free, pointwise requirement relates to population objectives defined under a joint distribution of ((x,y)), and why it is an informative assumption for relevant model families. The current presentation makes it difficult to assess the scope and implications of the result.As another example, the proof of Lemma 4 is overly compressed. The authors should explicitly show how the XOR construction yields the required parity values at Boolean vertices and separately establish boundedness throughout the continuous input domain. The claimed graph size, depth, bounded coefficients, and description length also require a more explicit construction and accounting. Since this lemma supplies the target family underlying the exponential separation, these details are important for assessing the main result.

Questions for authors

none

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

Related papers

Discussion (0)

Sign in to comment.