Pith. sign in

REVIEW 2 major objections 4 minor 1 cited by

Complexity of Vector-valued Prediction: From Linear Models to Stochastic Convex Optimization

T0 review · 2 major / 4 minor · reviewed 2026-08-11 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗ Review JSON

Pith's one-line read 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.

desk verdict 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. read the letter →

arxiv 2412.04274 v1 pith:GLQV7WK4 submitted 2024-12-05 cs.LG

Matan Schliserman , Tomer Koren This is my paper · ORCID
classification cs.LG MSC 68Q3268T05
keywords vector-valuedpredictionsamplecomplexityempiricalriskminimizationstochasticconvexoptimizationRademachershatteringwithmarginnear-orthogonalvectorsblack-boxreduction
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

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.

What carries the argument

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.

What would settle it

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.

Watch

Extended reading notes

Core claim

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.

Load-bearing premise

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.

Editorial extensions

If this is right

  • 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.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

  • 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.
Share X Bluesky LinkedIn Reddit HN

Signed reviews

No signed human review yet.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Referee Report

2 major / 4 minor

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.

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 (2)
  1. [3, proof of Lemma 1] 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.
  2. [A.1, proof of Theorem 3] 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.
minor comments (4)
  1. [2 and 3] 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.
  2. [3, proof of Lemma 1] 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.
  3. [3, proof of Lemma 1] 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'.
  4. [4.1, Lemma 2] 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.

Circularity Check

0 steps flagged · score 0.0 of 10

No circularity found; the main derivations are self-contained and do not reduce to their inputs.

full rationale

The paper's central results are derived from explicit constructions and external benchmarks, not from the claims being proved. The lower bound (Theorem 1 via Lemma 1) builds a hard instance from scratch: a near-orthogonal set adapted from Feldman (Lemma 7), an explicit initialization A0, an explicit loss function ℓ defined as a maximum of linear functions, and an explicit matrix A_y for each labeling; no parameter is fitted to data and then renamed as a prediction. The upper bound (Theorem 3) follows from Maurer's vector-contraction inequality and Koren et al.'s Lemma 5, both of which are stated external bounds with assumptions that do not include the present paper's conclusions. The SCO-to-VVP conversion (Theorem 2) defines ℓ and D' directly from the given SCO instance, proves the population-loss comparison via double sampling, Cauchy-Schwarz, and Jensen, and invokes Koren et al.'s Lemma 5 only as an independent SCO generalization bound. The possible non-injectivity of the labeling encoding in Lemma 1 is a correctness concern about the lower-bound proof, not a circularity, because it does not amount to a result being equivalent to its inputs by construction or to a fit being relabeled as a prediction.

Assumptions & free parameters 3 free parameters · 4 assumptions · 0 invented entities

The paper introduces no new conceptual entities. Its constructions use hand-chosen scaling parameters and loss constants, all explicit rather than fitted. The SCO-to-VVP reduction adds an embedding map φ and a reference scale ρ, chosen to satisfy separation and norm constraints. The main load-bearing ingredients are external results (Maurer, Koren et al.) and the near-orthogonal packing lemma proven inside the paper.

free parameters (3)
  • D = 12/ε²
    Scaling constant in Lemma 1 controlling the number of columns and the size of the training set. Chosen by hand to make the shattering construction work, not fitted to external data.
  • ρ = 4B/δ
    Scale of the reference matrix A0 in the SCO-to-VVP reduction (Theorem 2). Chosen so that the optimal SCO solution lies inside the Frobenius ball and the embedding of sample indices is resolvable.
  • Loss construction constants (2√8, 7ε, ε/√8) = explicit constants
    Hand-chosen in the shattering construction to produce ±ε separation in the loss values. These are fixed constants, not fitted to data.
assumptions (4)
  • standard math Maurer's vector-contraction inequality (Lemma 3)
    Used to prove the upper bound Theorem 3. This is an external result from Maurer [2016].
  • standard math Lemma 5 from Koren et al. [2022]: expected ERM generalization bound in SCO
    Used in Theorem 2 to pass from empirical to population excess risk in the embedded SCO problem. Prior work by the authors, but a standard result.
  • standard math Near-orthogonal vector packing (Lemma 7)
    Proven in the paper via the probabilistic method. Guarantees sets of size 2^{d/12} in R^d with pairwise inner product at most 1/2. Underlies both main constructions.
  • standard math Convexity and Lipschitzness of max-of-linear and max-of-convex losses
    Used to construct valid VVP loss functions. These are standard facts about convex analysis.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Complexity of Vector-valued Prediction: From Linear Models to Stochastic Convex Optimization." pith.science (2026). https://pith.science/paper/GLQV7WK4

@misc{pith2026241204274,
  author       = {Pith},
  title        = {Pith review of: Complexity of Vector-valued Prediction: From Linear Models to Stochastic Convex Optimization},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/GLQV7WK4}},
  note         = {Machine review of arXiv:2412.04274}
}
abstract

We study the problem of learning vector-valued linear predictors: these are prediction rules parameterized by a matrix that maps an $m$-dimensional feature vector to a $k$-dimensional target. We focus on the fundamental case with a convex and Lipschitz loss function, and show several new theoretical results that shed light on the complexity of this problem and its connection to related learning models. First, we give a tight characterization of the sample complexity of Empirical Risk Minimization (ERM) in this setting, establishing that $\smash{\widetilde{\Omega}}(k/\epsilon^2)$ examples are necessary for ERM to reach $\epsilon$ excess (population) risk; this provides for an exponential improvement over recent results by Magen and Shamir (2023) in terms of the dependence on the target dimension $k$, and matches a classical upper bound due to Maurer (2016). Second, we present a black-box conversion from general $d$-dimensional Stochastic Convex Optimization (SCO) to vector-valued linear prediction, showing that any SCO problem can be embedded as a prediction problem with $k=\Theta(d)$ outputs. These results portray the setting of vector-valued linear prediction as bridging between two extensively studied yet disparate learning models: linear models (corresponds to $k=1$) and general $d$-dimensional SCO (with $k=\Theta(d)$).

Discussion (0). Continue with ORCID to comment.

Forward citations

Cited by 1 Pith paper

Reviewed papers in the Pith corpus that reference this work. Sorted by Pith novelty score. Full citation record

  1. Multiclass Loss Geometry Matters for Generalization of Gradient Descent in Separable Classification

    cs.LG 2025-05 accept novelty 8.0 of 10

    In separable multiclass classification, the risk of gradient descent scales as k^{2/p} for losses with ℓ_p-smooth templates, giving logarithmic k-dependence for p=∞ and linear k-dependence for p=2 (provably unavoidable).

Reference graph

Works this paper leans on

19 extracted references · 13 canonical work pages · cited by 1 Pith paper

  1. [1]

    I. Amir, T. Koren, and R. Livni. SGD generalizes better than GD (and regularization doesn’t help). In Conference on Learning Theory, pages 63--92. PMLR, 2021

    work page 2021

  2. [2]

    I. Amir, R. Livni, and N. Srebro. Thinking outside the ball: Optimal learning with gradient descent for generalized linear stochastic convex optimization. Advances in Neural Information Processing Systems, 35: 0 23539--23550, 2022

    work page 2022

  3. [3]

    P. L. Bartlett and S. Mendelson. Rademacher and gaussian complexities: Risk bounds and structural results. Journal of Machine Learning Research, 3 0 (Nov): 0 463--482, 2002

    2002

  4. [4]

    The Sample Complexity Of ERMs In Stochastic Convex Optimization

    D. Carmon, R. Livni, and A. Yehudayoff. The sample complexity of ERM s in stochastic convex optimization. arXiv preprint arXiv:2311.05398, 2023

    work page Pith review arXiv 2023

  5. [5]

    Crammer and Y

    K. Crammer and Y. Singer. On the algorithmic implementation of multiclass kernel-based vector machines. Journal of machine learning research, 2 0 (Dec): 0 265--292, 2001

    work page 2001

  6. [6]

    Daniely and E

    A. Daniely and E. Granot. Generalization bounds for neural networks via approximate description length. Advances in Neural Information Processing Systems, 32, 2019

    work page 2019

  7. [7]

    On the Sample Complexity of Two-Layer Networks: Lipschitz vs. Element-Wise Lipschitz Activation

    A. Daniely and E. Granot. On the sample complexity of two-layer networks: Lipschitz vs. element-wise lipschitz activation. CoRR, abs/2211.09634, 2022. doi:10.48550/arXiv.2211.09634

    work page Pith review arXiv doi:10.48550/arxiv.2211.09634 2022

  8. [8]

    V. Feldman. Generalization of ERM in stochastic convex optimization: The dimension strikes back. In Advances in Neural Information Processing Systems, volume 29, 2016

    work page 2016

Show all 19 references
  1. [9]

    Koren, R

    T. Koren, R. Livni, Y. Mansour, and U. Sherman. Benign underfitting of stochastic gradient descent. In S. Koyejo, S. Mohamed, A. Agarwal, D. Belgrave, K. Cho, and A. Oh, editors, Advances in Neural Information Processing Systems, volume 35, pages 19605--19617. Curran Associate...

    2022

  2. [10]

    Lei, \"U

    Y. Lei, \"U . Dogan, D.-X. Zhou, and M. Kloft. Data-dependent generalization bounds for multi-class classification. IEEE Transactions on Information Theory, 65 0 (5): 0 2995--3021, 2019

    2019

  3. [11]

    R. Livni. The sample complexity of gradient descent in stochastic convex optimization. arXiv preprint arXiv:2404.04931, 2024

    2024 arXiv

  4. [12]

    Magen and O

    R. Magen and O. Shamir. Initialization-dependent sample complexity of linear predictors and neural networks. arXiv preprint arXiv:2305.16475, 2023

    2023 arXiv

  5. [13]

    A. Maurer. A vector-contraction inequality for rademacher complexities. In Algorithmic Learning Theory: 27th International Conference, ALT 2016, Bari, Italy, October 19-21, 2016, Proceedings 27, pages 3--17. Springer, 2016

    2016

  6. [14]

    Mohri, A

    M. Mohri, A. Rostamizadeh, and A. Talwalkar. Foundations of machine learning. MIT press, 2018

    2018

  7. [15]

    Schliserman, U

    M. Schliserman, U. Sherman, and T. Koren. The dimension strikes back with gradients: Generalization of gradient methods in stochastic convex optimization. arXiv preprint arXiv:2401.12058, 2024

    2024 arXiv

  8. [16]

    Shalev - Shwartz and S

    S. Shalev - Shwartz and S. Ben - David. Understanding Machine Learning - From Theory to Algorithms. Cambridge University Press, 2014. ISBN 978-1-10-705713-5

    2014

  9. [17]

    Shalev-Shwartz, O

    S. Shalev-Shwartz, O. Shamir, N. Srebro, and K. Sridharan. Learnability, stability and uniform convergence. The Journal of Machine Learning Research, 11: 0 2635--2670, 2010

    2010

  10. [18]

    Vardi, O

    G. Vardi, O. Shamir, and N. Srebro. The sample complexity of one-hidden-layer neural networks. CoRR, abs/2202.06233, 2022

    2022 arXiv

  11. [19]

    Zhang and M.-L

    Y. Zhang and M.-L. Zhang. Generalization analysis for multi-label learning. In R. Salakhutdinov, Z. Kolter, K. Heller, A. Weller, N. Oliver, J. Scarlett, and F. Berkenkamp, editors, Proceedings of the 41st International Conference on Machine Learning, volume 235 of Proceedings...

    2024

Pith tools

Reviewed August 11, 2026 · model on record in the stance chip above.