<p>The fast and robust stochastic optimization algorithms for training deep neural networks (DNNs) are still a topic of heated discussion. As a simple but effective way, the momentum technique, which utilizes historical gradient information, shows significant promise in training DNNs both theoretically and empirically. Nonetheless, the accumulation of error gradients in stochastic settings leads to the failure of momentum techniques, e.g., Nesterov’s accelerated gradient (NAG), in accelerating stochastic optimization algorithms. To address this problem, a novel type of stochastic optimization algorithm based on negative momentum (NM) is developed and analyzed. In this work, we applied NM to vanilla stochastic gradient descent (SGD), leading to SGD-NM. Although a convex combination of previous and current historical information is adopted in SGD-NM, fewer hyperparameters are introduced than those of the existing NM techniques. Meanwhile, we establish a theoretical guarantee for the resulting SGD-NM and show that SGD-NM enjoys the same low computational cost as vanilla SGD. To further show the superiority of NM in stochastic optimization algorithms, we propose a variant of stochastically controlled stochastic gradient (SCSG) based on the negative momentum technique, termed SCSG-NM, which achieves faster convergence compared to SCSG. Finally, we conduct experiments on various DNN architectures and benchmark datasets. The comparison results with state-of-the-art stochastic optimization algorithms show the great potential of NM in accelerating stochastic optimization, including more robust to large learning rates and better generalization.</p>