The Price of Convexity in Squared-Loss Representations

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 $\rho$-weakly convex for every input and label. We prove that any finite prediction sign matrix realized with margin $\mu$ has sign-rank at most $q+1$ whenever $\rho R^2<4\mu -2{\mu }^2$, where $q$ is the parameter dimension and $R$ 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 $O(d)$ nodes yields an exponential dimension separation: approximation within $\text{eps}<1/2$ requires either $q+1\ge 2^{d/2}$ or $(1/2+\text{eps}{)}^2+\rho R^2/2\ge 1$. A smooth two-parameter construction shows that the coefficient $4$ 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.