Stein’s Lemma and Subsampling in Optimization
Murat A. Erdoğdu
Statistics and optimization have been closely linked since the very outset. This connection have become more essential lately, mainly because of the recent advances in computational resources, the availability of large amount of data, and the consequent growing interest in statistical and machine learning algorithms. In the broadest sense, statistical estimation methods have been usually the primary beneficiary of this relation, and in this work we reverse this arrangement. We show that optimization algorithms can also immensely benefit from the classical techniques from statistics such as Stein’s lemma and subsampling. We propose algorithms that have wide applicability to many supervised learning problems such as binary classification with smooth surrogate losses, robust statistics with m-estimators, and generalized linear models. We provide theoretical guarantees of the proposed algorithms, and analyze their convergence behavior in terms of data dimensions. Finally, we demonstrate the performance of our algorithms on well-known classification and regression problems, through extensive numerical studies on large-scale datasets, and show that they achieve the highest performance compared to other widely used and specialized algorithms.