Conclusion
What the paper is about. The paper establishes a general model-theoretic (first-order-logic / quantifier-elimination) framework, Theorem 4.1, for bounding the pseudo-dimension of multi-dimensional hyperparameter-tuning loss classes {ell_alpha : alpha in R^p}, generalizing prior one-dimensional-hyperparameter results (Balcan et al. 2025) to p>1 for the first time. It instantiates this for training-loss tuning (Theorem 5.1: Pdim=O(pd log(M+T+d)+p^2 d log Delta), with a matching lower bound Theorem 5.2) and validation-loss tuning (Theorem 6.1, d^2 factor), extends it beyond piecewise-polynomial classes to general semi-algebraic functions (finite fat-shattering despite non-polynomial structure, e.g. group LASSO), and derives a tighter, explicit-solution-path bound (Theorem 7.2) applied to weighted group LASSO (Theorem 8.1: O(p^3 d+p^2 d^2)) and weighted fused LASSO (Theorem 8.2: O(d^2), notably free of the extra p-blowup terms).
How we tried to reproduce it. This is a pure theory paper: no code, checkpoints, or datasets were released (code_available: false in our feasibility eval), so we built three independent, executable CPU-only checks from scratch (common.py + exp1_polybase.py, exp1_mc.py, exp2_grouplasso.py, exp3_fusedlasso.py, all uv run + logged via trackio logbook run). Claim 1: exact LP-based shattering for polynomial-threshold families (ground truth Pdim=p) plus a Monte Carlo menu-coverage pseudo-dimension estimator applied to a genuine piecewise-polynomial value function with a real inner argmin. Claim 2: the actual (non-polynomial) weighted-group-LASSO bilevel problem solved exactly via cvxpy/CLARABEL, empirical Pdim estimated the same way. Claim 3: both weighted group LASSO (Theorem 8.1) and weighted fused LASSO (Theorem 8.2) solved exactly and swept over (p,d), comparing measured pseudo-dimension growth to each theorem's asymptotic order. All scale-downs (small p,d,n, Monte Carlo shattering instead of exhaustive search) are disclosed loudly on each claim page.
What we found. Claim 1: verified — an exact, non-Monte-Carlo LP-shattering check reproduced the theorem's linear-in-p pseudo-dimension scaling to machine precision across 18/18 configs (Pdim=p exactly, p=1..6), with a disclosed supplementary MC check under the full Assumption-3.2 structure trending consistently (R^2=0.74 in log-log regression). Claim 2: toy — the real, non-polynomial group-LASSO objective was solved exactly (all SOCPs converged) and empirically shown to have finite, p-scaling pseudo-dimension (measured 1,1,2,2,3 across 5 configs, always well below the O(p^3d+p^2d^2) envelope), confirming the "beyond piecewise-polynomial" mechanism at small scale. Claim 3: toy — both group-LASSO (O(p^3d+p^2d^2)) and fused-LASSO (O(d^2)) bounds were individually consistent with measurement across 10 configs (measured Pdim 1-3 and 2-6 respectively, both always inside their theoretical envelopes), but sizes up to d<=8 are too small to observe the asymptotic separation between the two bounds that the "improved" claim is actually about. All scripts, raw JSON results, and logs are attached via executed trackio logbook run cells on each claim page.