Title: Provable Robust Learning for Deep Neural Networks under Agnostic Corrupted Supervision. Abstract: Training deep neural models in the presence of corrupted supervisions is challenging as the corrupted data points may significantly impact the generalization performance.  To alleviate this problem, we present an efficient robust algorithm that achieves strong guarantees without any assumption on the type of corruption and provides a unified framework for both classification and regression problems. Different from many existing approaches that quantify the quality of individual data points (e.g., loss values) and filter out data points accordingly, the proposed algorithm focuses on controlling the collective impact of data points on the averaged gradient.  Even when a corrupted data point failed to be excluded by the proposed algorithm, the data point will have very limited impacts on the overall loss, as compared with state-of-the-art filtering data points based on loss values. Extensive empirical results on multiple benchmark datasets have demonstrated the robustness of the proposed method under different types of corruption.