- Rating
- 2
- Confidence
- 3
- Informativeness
- 2
- Presentation
- 2
- Soundness
- 2
Read review
Paper summary
This paper studies when joint training of low-dimensional input/output embeddings can learn a large softmax state-transition model. The main result shows constant prediction gain for perturbed gradient descent at width , with additional results for tied embeddings and transfer to unseen input states. I think there is real technical novelty here: the trace-based curvature argument improves the direct generic comparison from to . I did not find a clear correctness issue in the main results. My main concern is significance. The topic is relevant to ICLR, but I am not yet convinced that the current theorems tell us something important enough about actual training dynamics. I am therefore leaning weak reject.
Critical strengths
-
There is a concrete new technical idea. The trace-packing argument in Appendix B.4 uses the total categorical curvature budget and obtains , while the direct generic factorized bound gives only . This is what makes the guarantee possible.
-
The main theorem is stronger than a stationary-point result. Thm 4.1 controls every iterate in the final fraction of the run. The repeated-SOSP-visit plus objective-refresh argument is nontrivial and directly addresses the training trajectory.
Critical weaknesses
-
Significance: the novelty is real, but I am not convinced what the guarantee tells us about learning. The target is already representable when , while thn 4.1 needs . The paper does not show that this gap is necessary, close to necessary, or associated with an actual optimization barrier. At the moment, this looks more like a technically interesting sufficient condition than a strong explanation of training dynamics.
-
Scope: the strongest transfer result remains conditional on an important property that training itself does not establish. Thm 5.4 requires centered coverage and uniformly bounded learned rows, and the paper explicitly states that the optimization analysis does not prove the learned-row condition. This makes the transfer result less satisfying as a statement about what the proposed training algorithm actually learns.
Questions for authors
-
Is there any evidence that the scale is intrinsic? For example, can the authors give a lower bound, hard instance, or failure mode below this scale?
-
Can the bounded learned-row assumption in Thm 5.4 be proved from the training dynamics, or substantially weakened?
-
Beyond improving the sufficient width bound, is there a stronger consequence of the trace-based argument that would distinguish a genuine learning phenomenon from proof slack?
3 comments
Responses to Questions
Q1: Is there any evidence that the scale is intrinsic? For example, can the authors give a lower bound, hard instance, or failure mode below this scale?
A3: Please see our response A1 to W1.
Q2: Can the bounded learned-row assumption in Thm 5.4 be proved from the training dynamics, or substantially weakened?
A4: Please see our response A2 to W2.
Q3: Beyond improving the sufficient width bound, is there a stronger consequence of the trace-based argument that would distinguish a genuine learning phenomenon from proof slack?
A5: The most important consequence of the trace-based argument is a quantitative connection between the prediction quality and the optimization landscape. That is, the local information, i.e., the gradient (first order) and the Hessian (second order), reveals the global information, i.e., the value of the loss, or equivalently, the prediction quality. Specifically, in the region reached by training, every point whose objective is above the level required for gain must have either a large gradient or a direction of negative curvature (Lemma B.4).
This is relevant to learning, because the generic saddle-escaping analysis only guarantees approximate second-order stationarity, which does not imply useful predictions. Our result supplies this missing implication. Combined with the control on the increase of the objective between consecutive visits to such points, it yields high prediction gain throughout the final window of training.
If our responses and revision have addressed your remaining concerns, we kindly ask you to consider a higher score. We welcome any further questions and thank you again for your time and feedback.
thanks for the clarification. I agree that a sufficient guarantee need not identify a sharp optimization threshold. the trace-based argument and final-window guarantee are genuine contributions, as I noted in my review. however, I am still not convinced that their significance is strong enough to change my assessment. the transfer result also remains conditional on a learned-row bound that the training analysis does not establish. the suggested extensions may help, but without precise statements and proofs, I cannot assess whether they resolve these concerns. I therefore maintain my weak-reject recommendation.
Responses to Weaknesses
We thank the reviewer for careful reading and thoughtful comments. We provide detailed responses below.
W1: Significance: the novelty is real, but I am not convinced what the V guarantee tells us about learning. The target is already representable when d≥r, while thn 4.1 needs d≥Ω(V). The paper does not show that this gap is necessary, close to necessary, or associated with an actual optimization barrier. At the moment, this looks more like a technically interesting sufficient condition than a strong explanation of training dynamics.
A1: Thank you for raising this insightful question. We do not view the V threshold as a fundamental optimization barrier. Instead, d=Ω(V) is a simple sufficient condition that supports a common analysis for the untied and tied models, and balances generality, practical relevance, and clarity. Specifically,
In addition, although d≥r guarantees that the ground truth is representable, establishing that training leads a useful predictor is substantially more difficult, since both embeddings evolve simultaneously under a nonconvex cross-entropy objective, whose Hessian depends on the learned predictions and can become nearly singular. In the untied model, our analysis can relax d=Ω(V). However, the proof is lengthy, introduces extremely large constants, and does not directly extend to tied embeddings. Therefore, relaxing the lower bound on d in general requires further non-trivial effort.
W2: Scope: the strongest transfer result remains conditional on an important property that training itself does not establish. Thm 5.4 requires centered coverage and uniformly bounded learned rows, and the paper explicitly states that the optimization analysis does not prove the learned-row condition. This makes the transfer result less satisfying as a statement about what the proposed training algorithm actually learns.
A2: Thank you for raising this insightful question. We do not view this condition as fundamental to the transfer through tied embeddings. In fact, our analysis can remove it at the cost of a larger embedding dimension and a weaker rate, or under additional structure on the ground truth. However, the corresponding proofs are lengthy, and removing the condition while keeping the same class of ground truths, the same requirement on the embedding dimension, and the same rate requires further non-trivial analysis. We therefore present the conditional guarantee to balance the generality of the ground truth, the strength of the bound, and clarity.
Specifically, the difficulty in removing this condition is that our optimization analysis controls the total energy ∥X∥F2 of the embeddings, which does not exclude the concentration of the energy on a few embeddings. Such concentration can have a small effect on the training loss on the observed states, while substantially changing the predictions on the unseen states. The bound on the learned embeddings rules this out. It keeps the logits bounded and thus controls the curvature of the softmax, which allows us to translate the bound on the training loss into a bound on the Gram matrix XX⊤, and then into the guarantee on the unseen states.