  Negative sampling has been heavily used to train recommender models on
large-scale data, wherein sampling hard examples usually not only accelerates
the convergence but also improves the model accuracy. Nevertheless, the reasons
for the effectiveness of Hard Negative Sampling (HNS) have not been revealed
yet. In this work, we fill the research gap by conducting thorough theoretical
analyses on HNS. Firstly, we prove that employing HNS on the Bayesian
Personalized Ranking (BPR) learner is equivalent to optimizing One-way Partial
AUC (OPAUC). Concretely, the BPR equipped with Dynamic Negative Sampling (DNS)
is an exact estimator, while with softmax-based sampling is a soft estimator.
Secondly, we prove that OPAUC has a stronger connection with Top-K evaluation
metrics than AUC and verify it with simulation experiments. These analyses
establish the theoretical foundation of HNS in optimizing Top-K recommendation
performance for the first time. On these bases, we offer two insightful
guidelines for effective usage of HNS: 1) the sampling hardness should be
controllable, e.g., via pre-defined hyper-parameters, to adapt to different
Top-K metrics and datasets; 2) the smaller the $K$ we emphasize in Top-K
evaluation metrics, the harder the negative samples we should draw. Extensive
experiments on three real-world benchmarks verify the two guidelines.
