Computational Foundations of Machine Learning in the Era of Big Data

点击翻译按钮获取中文摘要

Machine learning (ML), a field that develops software that can improve itself through learning and experience, has been largely driven by the availability of historical data, and by the need to develop efficient and scalable algorithms and supporting theories. Conversely, the success of ML in science, engineering, and commerce, along with technological innovations, has led to an unprecedented growth and enthusiasm in big data collection, thereby redefining computational efficiency and inviting system solutions. For example, the recent AlphaGo system of Deepmind that beats top human Go players needed 1900 CPUs and 280 GPUs to carry out the computation. How to balance computation with communication in this vast distributed cluster, without compromising system throughput or correctness? On the other hand, a small startup developing a mobile app may not afford the same computational power as Google, hence often has to turn into primitive solutions. How to build an algorithmic framework for ML that provides ''knobs'' to adjust the computational load, with explicit, controllable loss on the accuracy? Meeting such diverse computational needs in the big data era has thus been a grand challenge for the ML field. We attempt to address such computational challenge in ML and big data, through three complementary objectives: (1) Real problems are hard, but also structured. Over the years the importance of designing statistical methodologies and computational algorithms that can exploit certain structure in data and model has become evident. Encouraged by our previous work on sparsity and low-rankness, we propose to investigate two additional structures that are common in ML applications: monotonicity and multi-modality (in the tensor format), and developing efficient algorithms that benefit from the presence of such structures. (2) Data is always noisy and full of random fluctuations, hence diminishing the need of obtaining exact or even high-precision solutions in ML. Approximate computation, if done properly, can significantly reduce the computation time in ML. We initiate a systematic study of the tradeoffs of approximate computation in ML, from ''downgrading'' computationally expensive programs to simpler and cheaper ones, to ''optimally" smooth nondifferentiable functions, and to attach measures of nonconvexity to nonconvex functions. (3) Distributed computation has become the norm in handling big datasets. We propose the Bounded Asynchronous Protocol (BAP) to better balance communication and computation in distributed ML systems, and we continue to investigate the speedups and convergence guarantees of typical ML iterative algorithms under BAP and possibly less stringent convex or smooth assumptions. Our work will further advance the computational theory and practice in ML, and the resulting algorithms and system will be fundamental for analyzing big datasets using ML methodologies.