{"id":"4f9a1f04-8a1d-4e4b-bafa-1e00a6e711c3","arxiv_id":"2412.04274","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":7.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":3,"one_line_summary":"For vector-valued linear prediction with convex Lipschitz losses, ERM's sample complexity is Θ̃(k/ε²), and any d-dimensional stochastic convex optimization problem embeds into this setting with k=Θ(d) outputs.","lead":"This paper proves that empirical risk minimization for vector-valued linear prediction with convex losses requires Ω(k/ε²) samples when the target has dimension k, and shows that any stochastic convex optimization problem can be converted into such a prediction problem with k proportional to the optimization dimension.","discovery_kind":"extension","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Lemma 1's encoding is non-injective: 2^{kD/13} labelings are mapped to at most 2^{kD/156} matrices, so the construction cannot shatter the claimed training set.","rationale":"I read the proof of Lemma 1 carefully and confirmed the reader's weakest-assumption identification. The construction in the proof associates each labeling y with a sequence of D/12 vectors from Û, where Û has size 2^{k/13} by Lemma 7. Since the total number of labelings is 2^{kD/13} and the number of distinct sequences is at most (2^{k/13})^{D/12} = 2^{kD/156}, the encoding cannot be injective. This is not merely a constant-factor issue: the exponent gap is exponential. Moreover, the loss value ℓ(A'_y x_{i,j}) is computed solely from the sequence entries û_{y(j)}, so two labelings that map to the same sequence produce the same function but require conflicting outputs on any bit where they differ. Thus the proof of Lemma 1 is internally inconsistent and Theorem 1's lower bound is unsupported by the provided argument. The upper bound (Appendix A.1) and the SCO-to-VVP reduction (Section 4) rest on different techniques and are not affected by this specific flaw. Because the reader already flagged exactly this issue and issued a conditional verdict, I do not change the verdict; the paper remains conditionally acceptable pending a corrected lower-bound construction.","tokens_in":23936,"tokens_out":14902,"duration_ms":147376,"concrete_test":"Set k = 13, so Û ⊆ R^{12} with |Û| = 2 and each block has 12 bits. Set ε = 1/2, so D = 48 and the number of blocks is D/12 = 4. There are 2^{48} labelings but only 2^4 = 16 sequences; by the pigeonhole principle, choose two labelings y ≠ y' that map to the same sequence. Following the proof's definitions, compute A_y = A_{y'} and evaluate ℓ(A'_y x_{i,j}) for a coordinate (i,j) where y and y' differ. Since the loss value is identical for both labelings but the required outputs are +ε and −ε, the construction cannot shatter S. More generally, check injectivity of the encoding by comparing the number of labelings 2^{kD/13} with the number of distinct sequences |Û|^{D/12} = 2^{kD/156}; for any k with 2^{12k/13} > |Û|, the map is non-injective and the shattering proof fails.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The proof of Lemma 1 constructs, for every labeling y ∈ {0,1}^{kD/13}, a matrix A_y determined by a sequence of D/12 vectors from the near-orthogonal set Û of (12k/13)-dimensional vectors. Lemma 7 gives |Û| = 2^{k/13}. Thus the construction yields at most |Û|^{D/12} = 2^{kD/156} distinct matrices A_y, whereas shattering the kD/13 examples would require 2^{kD/13} distinct functions. Since 2^{kD/156} is exponentially smaller, the map from labelings to sequences is not injective: two labelings y ≠ y' share the same sequence and hence the same matrix A_y. The subsequent loss calculation, however, shows that ℓ(A'_y x_{i,j}) depends only on the sequence, not on the full labeling y. For an example (i,j) where y and y' differ, the same constructed predictor would need to output both ε and −ε, a contradiction. Therefore the claimed shattering of the set S in Lemma 1 fails, and the proof of Theorem 1's lower bound is invalid as written. The upper bound (Theorem 3) and the SCO reduction (Theorem 2) are independent of this construction and appear unaffected.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper studies vector-valued linear prediction with convex and Lipschitz losses, where predictors are matrices constrained to a Frobenius-norm ball around a reference matrix. Its two main claims are: (i) a tight sample-complexity characterization of ERM in this setting, namely a lower bound of Ω~(√(k/n)) on the excess risk, which together with Maurer's upper bound gives a Θ~(k/ε²) sample complexity; and (ii) a black-box reduction showing that any d-dimensional stochastic convex optimization problem can be embedded as a VVP with k=d+2 outputs, with only an O(1/√n) overhead in excess risk. The lower bound is proved through a margin-shattering construction in Lemma 1, and the upper bound is derived from Maurer's vector contraction inequality in Appendix A.1.","tokens_in":24162,"tokens_out":17207,"duration_ms":183831,"significance":"If correct, the lower bound would be a substantial improvement over the polylogarithmic dependence on k obtained by Magen and Shamir, and it would match the classical upper bound of Maurer. The SCO-to-VVP reduction is an elegant structural contribution that makes precise the sense in which VVP interpolates between generalized linear models and general stochastic convex optimization; this part of the paper is independent of the lower-bound construction and appears sound. The upper-bound argument via Maurer's inequality is standard and clean. The main concern is that the proof of the headline lower bound contains a serious counting gap, as detailed below.","major_comments":[{"comment":"The claimed shattering of the set S is impossible by a counting argument. The proof encodes a labeling y∈{0,1}^{kD/13} as a sequence of D/12 elements of Û, where Û=U_{12k/13} has size 2^{k/13} by Lemma 7. Therefore the construction produces at most (2^{k/13})^{D/12} = 2^{kD/156} distinct matrices A_y, whereas shattering the kD/13 examples requires 2^{kD/13} distinct predictors. This is an exponential gap, so the map from labelings to matrices is not injective. Moreover, the loss computation shows that ℓ(A'_y x_{i,j}) depends only on the block y^{(j)}, so two labelings that differ outside block j cannot be realized by distinct predictors when they are assigned the same encoding. Since Theorem 1's lower bound is derived from Lemma 1 via the standard shattering-to-ERM argument in Appendix A.2, the main lower bound is unsupported as written.","section":"3, proof of Lemma 1"},{"comment":"In the proof of Theorem 3, the term E[\\hat F(Â*) − \\hat F(A*)] is non-positive by the definition of Â* as an empirical risk minimizer, while Lemma 5 bounds the opposite quantity E[\\hat F(A*) − \\hat F(Â*)]. The displayed use of Lemma 5 to obtain a positive +4L/√n term is therefore not valid as written. The theorem can be repaired by bounding F(A*) − \\hat F(A*) with the same Rademacher/uniform-convergence bound used for the first term, so this is a local proof error rather than a false claim, but the appendix needs correction.","section":"A.1, proof of Theorem 3"}],"minor_comments":[{"comment":"The symbol D is overloaded: it denotes a distribution in Section 2 and also the constant D=12/ε² in the proof of Lemma 1; renaming one of them would considerably improve readability.","section":"2 and 3"},{"comment":"The exact dimensions in the definition of A0 are garbled: the matrix is written with kD/13 columns while the stated column dimension is a=(k/13+1/12)D, and the indexing of columns such as u'_{r+12k/13(t−1)} should be rewritten with explicit ranges. This makes the proof difficult to verify independently of the counting issue.","section":"3, proof of Lemma 1"},{"comment":"The set Û is enumerated by integers, but the text repeatedly writes û_{y^{(j)}} as though a bit string of length 12k/13 were a valid index. Since |Û| is exponentially smaller than the number of such bit strings, the intended injection must be stated explicitly rather than asserted by the phrase 'identify'.","section":"3, proof of Lemma 1"},{"comment":"The statement of Lemma 2 uses the embedding φ(i)=(sin(π i/(2E)), cos(π i/(2E)))^T, but in Theorem 2 the same map is used with E=2n and arguments in [2n]; the relationship between the two ranges and the value of δ should be stated consistently.","section":"4.1, Lemma 2"}],"recommendation":"major_revision","confidential_remarks":"The counting error in Lemma 1 is the key issue and is not a typographical slip: it invalidates the proof of the paper's first main result. The SCO-to-VVP reduction in Section 4 is independent and appears sound; it could stand alone as a contribution. If the authors can supply a valid shattering construction, the paper would be strong; otherwise the advertised tight lower bound is unproven. I see no reason to doubt the authors' intentions, but a careful rewrite of Section 3 and Appendix A.2 is required."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Yotam,\n\nQuick take on 2412.04274 (Schliserman-Koren). The paper has two results: a claimed tight Ω~(k/ε²) sample complexity lower bound for ERM in convex vector-valued prediction, and a black-box reduction from d-dimensional SCO to VVP with k=Θ(d) outputs. The reduction is real and I think it's the stronger half of the paper. The lower bound, as written, has a serious gap in the current proof.\n\nThe reduction is genuinely new: it embeds an arbitrary SCO loss into a max-of-convex VVP loss with k=d+2 outputs, uses double sampling, and recovers a solution with O(ε(n)+1/√n) excess. The proof goes through Cauchy-Schwarz and the Koren et al. lemma cleanly; I don't see a circularity or a hidden assumption. That's a nice conceptual bridge.\n\nThe upper bound (O(√(k/n)) excess via Maurer's vector contraction) is standard but correctly derived. Fine.\n\nThe problem is Lemma 1. The proof claims to shatter a set S of kD/13 examples, D=12/ε². The predictor for a labeling y is built from a sequence of D/12 vectors, each drawn from a near-orthogonal set Û of size 2^{k/13}. That gives at most (2^{k/13})^{D/12} = 2^{kD/156} distinct matrices. But shattering S requires 2^{kD/13} distinct functions. The gap is exponential: for D=12/ε², the number of labelings is 2^{12k/(13ε²)} while the construction yields 2^{k/(13ε²)}. So most labelings are identified with the same matrix, and the loss calculation can't assign both ε and −ε to the same example for two conflicting labelings. The proof's case analysis implicitly assumes each binary block maps injectively to a distinct û vector, but Û is exponentially smaller than the block space. This isn't a constant-factor slip; it's a counting failure.\n\nCould the lower bound survive? Maybe. The image size is still exponential in k/(13ε²), so a tighter construction might shatter a subset of S of size kD/156 and still get Ω(k/ε²) up to constants. But that repair is nontrivial and would need a new argument; the current lemma, and hence Theorem 1 as proved, doesn't establish the claimed shattering.\n\nSo: the reduction and upper bound are worth your time, and the lower bound question is important. But as it stands, the main theorem is not proven. I'd send it to a serious referee—this is exactly the kind of paper that deserves careful scrutiny—with the expectation that the authors either fix Lemma 1 or weaken the claim.\n\nFor the reading group, I'd maybe bring the reduction; the flawed lower bound makes for a good cautionary exercise.","headline":"The SCO-to-VVP reduction is solid, but the flagship lower bound rests on a shattering lemma whose counting is off by an exponential factor.","tokens_in":24740,"tokens_out":9521,"would_cite":false,"duration_ms":89816,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["68Q32","68T05"],"pacs":[],"model":"deepseek-v4-flash","headline":"This paper proves a tight Ω~(k/ε²) sample-complexity lower bound for ERM in convex vector-valued prediction, and shows that general d-dimensional stochastic convex optimization embeds into vector-valued prediction with k=O(d) outputs.","keywords":["vector-valued prediction","sample complexity","empirical risk minimization","stochastic convex optimization","Rademacher complexity","shattering with margin","near-orthogonal vectors","black-box reduction"],"falsifier":"Count the encodings in Lemma 1: the training set S has kD/13 examples with D=12/ε², so shattering requires $2^{{kD/13}}$ distinct functions; the proof encodes each labeling as a sequence of D/12 vectors drawn from a set of size $2^{{k/13}}$, giving at most $2^{{kD/156}}$ matrices. Checking whether the near-orthogonal set in dimension d can have size $2^{{d}}$ rather than the $2^{{d/12}}$ guaranteed by Lemma 7 would settle whether the construction shatters the claimed number of examples.","tokens_in":23670,"feed_emoji":"🎯","tokens_out":9524,"duration_ms":89372,"temperature":0.7,"pith_summary":"Vector-valued prediction learns maps x ↦ ℓ(Ax) in which an m-dimensional input is sent to a k-dimensional target through a matrix A and a convex Lipschitz loss ℓ. The paper's first result is that empirical risk minimization needs Ω~(k/ε²) samples to reach ε excess population risk in this setting, matching the known O(k/ε²) upper bound and exponentially improving a previous Ω(log k) lower bound. Its second result is a black-box reduction: any d-dimensional stochastic convex optimization (SCO) problem can be rewritten as a vector-valued prediction problem with k=d+2 outputs, so that any VVP algorithm with n-sample excess risk ε(n) yields an SCO solution with excess risk O(ε(n)+1/√n). Taken together, the two results place vector-valued prediction as a bridge between dimension-free generalized linear models and dimension-dependent SCO.","feed_headline":"ERM for vector-valued prediction needs ~k/ε² samples","feed_subtitle":"Tight lower bound matches the known upper bound and embeds d-dimensional SCO into k=O(d) outputs.","key_machinery":"The load-bearing object for the lower bound is an exponentially large near-orthogonal set: a collection of unit vectors in dimension d with pairwise inner products at most 1/2 and size $2^{{d/12}}$ (Lemma 7). Such a set lets one encode labels in O(d) coordinates rather than the exponential number of coordinates used in earlier constructions; the paper's loss ℓ then assigns margin ±ε to each encoded label, making the whole matrix class shatter Ω(k/ε²) points. For the SCO-to-VVP reduction, the machinery is a circle embedding φ(j)=(sin(πj/4n), cos(πj/4n)) that separates the 2n sample indices in two dimensions, together with a max-over-j loss that both decodes the index and applies the original loss to the candidate vector; double-sampling over 2n examples lets the VVP population risk approximate the SCO population risk.","core_discovery":"On the paper's own terms, the central discovery is that the sample complexity of ERM in convex vector-valued prediction is governed by the target dimension: for k outputs, ε-accurate empirical risk minimization requires Θ~(k/ε²) examples, not the poly-logarithmic-in-k dependence suggested by earlier lower bounds. The proof constructs a distribution, a reference matrix, and a convex 1-Lipschitz loss for which the class of predictors in a unit Frobenius ball shatters Ω(k/ε²) examples with margin ε, so with constant probability some ERM has excess risk Ω~(√(k/n)). The second discovery is structural: with k=Θ(d) outputs, vector-valued prediction becomes rich enough to contain any d-dimensional convex stochastic optimization problem, via a loss that encodes the sample index in two output coordinates and evaluates the original loss on a candidate solution stored in the last column; the reduction loses only an O(1/√n) term.","pith_inferences":["The near-orthogonal encoding is a transferable technique: other lower-bound constructions for SCO that rely on packing the parameter space can likely be converted into VVP lower bounds by storing the parameter vector in the extra columns, suggesting that algorithmic separations known for SCO carry over to VVP.","The circle embedding used in the reduction is essentially a one-dimensional index code; replacing it with a higher-dimensional spherical code would let the same black-box conversion handle SCO instances indexed by exponentially many samples, potentially trading output dimension against the 1/√n term.","Because the upper bound comes from Rademacher contraction, any future improvement for VVP would need to break the contraction argument; a natural test is whether a non-ERM algorithm such as SGD enjoys a better dependence on k for convex losses, as in the k=1 GLM case."],"forward_implications":["ERM sample complexity for convex Lipschitz vector-valued prediction is Θ~(k/ε²); generic ERM cannot avoid a linear dependence on the number of outputs.","This matches Maurer's upper bound and improves the previous Ω(log k) lower bound exponentially, so the poly-log dependence in prior work is not the true complexity.","With k=1 the bounds recover the dimension-free Θ(1/ε²) rate of generalized linear models, giving a smooth interpolation to the SCO regime k=Θ(d).","Any VVP algorithm with an O(k/ε²)-type guarantee can be run on the embedded instance to solve a d-dimensional SCO problem with excess risk O(ε + 1/√n), so the two problems have matching worst-case complexity at k=Θ(d).","Because the lower-bound instance requires m=Θ(n) columns, the Ω(mk) parameters keep the result consistent with the known Θ(d/ε + 1/ε²) bound for d-dimensional SCO."],"supporting_citations":[{"why":"Provides the prior Ω(log k) lower bound for convex vector-valued prediction that the paper's Theorem 1 exponentially improves, and contributes the construction style the paper adapts.","marker":"Magen and Shamir [2023]"},{"why":"Supplies the vector-contraction inequality for Rademacher complexity used to prove the O(k/ε²) upper bound which the new lower bound matches.","marker":"Maurer [2016]"},{"why":"Source of the near-orthogonal vector construction (Lemma 7) that lets the lower-bound proof encode exponentially many labels in O(k) rows.","marker":"Feldman [2016]"},{"why":"Provides Lemma 5, the double-sampling inequality that controls the gap between empirical and population losses of held-out examples in the SCO-to-VVP reduction.","marker":"Koren et al. [2022]"},{"why":"Establishes the dimension-free Θ(1/ε²) sample complexity of generalized linear models, the k=1 endpoint of the paper's interpolation.","marker":"Bartlett and Mendelson [2002]"},{"why":"Gives the sharp Θ(d/ε + 1/ε²) ERM sample complexity in d-dimensional SCO, used to place the VVP lower bound and the reduction in context.","marker":"Carmon et al. [2023]"}],"fun_headline_variants":["Tight bound: ERM for k outputs needs ~k/ε² samples","Vector ERM sample complexity: Θ~(k/ε²), tight and matches upper bound","k outputs cost ~k/ε² samples: vector prediction hits tight bound","From linear to SCO: vector prediction bridges with k=Θ(d)","New lower bound: ERM for vector-valued loss needs ~k/ε² examples"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"In the lower-bound instance, the construction must produce a distinct prediction matrix for every labeling of the training set; the encoding scheme it specifies yields only $2^{{kD/156}}$ distinct matrices, exponentially fewer than the $2^{{kD/13}}$ labelings the set is claimed to shatter.","fun_headline_variants_meta":{"raw":{"variants":["Tight bound: ERM for k outputs needs ~k/ε² samples","Vector ERM sample complexity: Θ~(k/ε²), tight and matches upper bound","k outputs cost ~k/ε² samples: vector prediction hits tight bound","From linear to SCO: vector prediction bridges with k=Θ(d)","New lower bound: ERM for vector-valued loss needs ~k/ε² examples"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000618,"raw_usage":{"total_tokens":2892,"prompt_tokens":991,"completion_tokens":1901,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":607,"completion_tokens_details":{"reasoning_tokens":1809}},"tokens_in":607,"tokens_out":1901,"duration_ms":13094,"temperature":1.0,"reasoning_tokens":1809,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-11T21:35:00.918734+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Count the encodings in Lemma 1: the training set S has kD/13 examples with D=12/ε², so shattering requires $2^{{kD/13}}$ distinct functions; the proof encodes each labeling as a sequence of D/12 vectors drawn from a set of size $2^{{k/13}}$, giving at most $2^{{kD/156}}$ matrices. Checking whether the near-orthogonal set in dimension d can have size $2^{{d}}$ rather than the $2^{{d/12}}$ guaranteed by Lemma 7 would settle whether the construction shatters the claimed number of examples.","supporting_citations":[],"review_version":1}