Batch Size or Negatives? A Selection Rule for Memory-Constrained Recommender Training

• URL: http://arxiv.org/abs/2608.11061v1
• Date: Tue, 11 Aug 2026 15:29:01 GMT
• Title: Batch Size or Negatives? A Selection Rule for Memory-Constrained Recommender Training
• Abstract summary: Large-scale neural recommender systems are typically trained with a softmax cross-entropy objective over the full item vocabulary.<n>For a fixed budget $B = n k$, it remains unclear whether one should prioritize larger batches or the inclusion of more negative items.<n>We propose a theoretical and empirical foundation for configuring memory during the training of recommender systems.
• Score: 0.8782033967242784
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Large-scale neural recommender systems are typically trained with a softmax cross-entropy objective over the full item vocabulary. For a typical large number of possible items $K$, the final classification layer dominates memory, requiring $O(nK)$ logits and gradients to materialize for a batch of $n$ examples. Sampled softmax reduces this cost by restricting the objective to only $k \ll K$ candidate negative items, resulting in an $O(nk)$ memory. However, for a fixed budget $B = n k$, it remains unclear whether one should prioritize larger batches or the inclusion of more negative items. We address this question by analyzing sampled-softmax training under a fixed memory constraint. Under standard smoothness and variance assumptions, our theoretical evidence suggests that the fastest convergence arises from an $ n \sim B, k \sim 1$ allocation. So, an actionable rule is to include as many objects as possible given computational constraints. Our theory is supported by controlled synthetic and synthetic and four real sequential recommendation benchmarks, including MovieLens-20M. The suggested configuration achieve faster convergence and better final recommendation quality than imbalanced alternatives within the same memory constraint. These findings provide a theoretical and empirical foundation for configuring memory during the training of recommender systems. Code, reproducibility materials, and all scripts for generating figures are available at https://anonymous.4open.science/r/LimitedMemoryRule-BBFB

Related papers

• Scaling Laws for Behavioral Foundation Models over User Event Sequences [2.924581427482972]
  We study a common two-part behavioral-model architecture, a feature-based event embedder, and a decoder-only transformer.<n>Across roughly 600 runs on real interaction data, spanning $1015$-$1019$ training FLOPs, we vary four deployment-relevant axes.<n> Compute-optimal training is data-heavy relative to text at low compute, but its $D/N$ ratio moves toward the Chinchilla as compute increases.
  arXiv  Detail & Related papers  (2026-06-03T15:59:25Z)
• Sharp Capacity Thresholds in Linear Associative Memory: From Winner-Take-All to Listwise Retrieval [59.859592671274704]
  How many key-value associations can a $dtimes d$ linear memory store?<n>We show that the answer depends not only on the $d2$ degrees of freedom in the memory matrix, but also on the retrieval criterion.
  arXiv  Detail & Related papers  (2026-05-06T17:53:20Z)
• Few Batches or Little Memory, But Not Both: Simultaneous Space and Adaptivity Constraints in Stochastic Bandits [21.76698452732286]
  We study multi-armed bandits under simultaneous constraints on space and adaptivity.<n>We prove that any algorithm with a $W$-bit memory constraint must use at least $(K/W)$ batches to achieve near-minimax regret $widetildeO(sqrtKT)$.
  arXiv  Detail & Related papers  (2026-03-14T04:02:50Z)
• DISCO: Diversifying Sample Condensation for Efficient Model Evaluation [59.01400190971061]
  Costly evaluation reduces inclusivity, slows the cycle of innovation, and worsens environmental impact.<n>We argue that promoting diversity among samples is not essential; what matters is to select samples thatmaximise diversity in model responses.<n>Our method, $textbfDiversifying Sample Condensation (DISCO)$, selects the top-k samples with the greatest model disagreements.
  arXiv  Detail & Related papers  (2025-10-09T08:53:59Z)
• Transfer Q Star: Principled Decoding for LLM Alignment [105.89114186982972]
  Transfer $Q*$ estimates the optimal value function for a target reward $r$ through a baseline model. Our approach significantly reduces the sub-optimality gap observed in prior SoTA methods.
  arXiv  Detail & Related papers  (2024-05-30T21:36:12Z)
• Provably Efficient High-Dimensional Bandit Learning with Batched Feedbacks [93.00280593719513]
  We study high-dimensional multi-armed contextual bandits with batched feedback where the $T$ steps of online interactions are divided into $L$ batches. In specific, each batch collects data according to a policy that depends on previous batches and the rewards are revealed only at the end of the batch. Our algorithm achieves regret bounds comparable to those in fully sequential setting with only $mathcalO( log T)$ batches.
  arXiv  Detail & Related papers  (2023-11-22T06:06:54Z)
• SlateFree: a Model-Free Decomposition for Reinforcement Learning with Slate Actions [5.647516208808729]
  We consider the problem of sequential recommendations, where at each step an agent proposes some slate of $N$ distinct items to a user. We propose a novel model-free SARSA and Q-learning algorithm that performs $N$ parallel iterations per step, without any prior user knowledge.
  arXiv  Detail & Related papers  (2022-09-05T10:15:16Z)
• GraB: Finding Provably Better Data Permutations than Random Reshuffling [39.067886932979874]
  Random reshuffling, which randomly permutes the dataset each epoch, is widely adopted in model training because it yields faster convergence than withreplacement sampling. Recent studies indicate greedily chosen data orderings can further speed up convergence empirically, at the cost of using more computation and memory. We show that Gradient Balancing algorithm (GraB) can outperform random reshuffling in terms of both training and validation performance.
  arXiv  Detail & Related papers  (2022-05-22T04:17:32Z)
• Minimax Optimal Quantization of Linear Models: Information-Theoretic Limits and Efficient Algorithms [59.724977092582535]
  We consider the problem of quantizing a linear model learned from measurements. We derive an information-theoretic lower bound for the minimax risk under this setting. We show that our method and upper-bounds can be extended for two-layer ReLU neural networks.
  arXiv  Detail & Related papers  (2022-02-23T02:39:04Z)
• More Optimal Simulation of Universal Quantum Computers [0.0]
  Worst-case sampling cost has plateaued at $le(2+sqrt2)xi_t delta-1$ in the limit that $t rightarrow infty$. We reduce this prefactor 68-fold by a leading-order reduction in $t$ through correlated sampling.
  arXiv  Detail & Related papers  (2022-02-02T19:00:03Z)
• Near-Optimal Regret Bounds for Contextual Combinatorial Semi-Bandits with Linear Payoff Functions [53.77572276969548]
  We show that the C$2$UCB algorithm has the optimal regret bound $tildeO(dsqrtkT + dk)$ for the partition matroid constraints. For general constraints, we propose an algorithm that modifies the reward estimates of arms in the C$2$UCB algorithm.
  arXiv  Detail & Related papers  (2021-01-20T04:29:18Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.