Under a Fixed Memory Budget, Recommender Training Should Maximize Batch Size and Use Roughly One Negative

arXiv 2608.11061·medium signalXBlueskyLinkedInCopy link

Sampled softmax cuts the O(nK) memory of a full-vocabulary classification layer down to O(nk) by restricting the objective to k candidate negatives, but for a fixed budget B = n·k it has been unclear whether to spend it on larger batches or more negatives. Analyzing convergence under standard smoothness and variance assumptions, the authors find the fastest convergence comes from an n ~ B, k ~ 1 allocation — an actionable rule to include as many objects as possible rather than deepening negative sampling. Controlled synthetic experiments and four real sequential recommendation benchmarks including MovieLens-20M confirm faster convergence and better final recommendation quality than imbalanced alternatives at equal memory.