Tractable Big Data and Big Models in Machine Learning

在几乎所有的科学和工程领域，我们收集的数据量都在以前所未有的速度增长。我们不再生产从MB到GB的数据大小，而是从TB到PB(甚至更高)。机器学习是我们用来理解这些不断增长的数据量(大数据)的关键工具之一，现在它正被用来解决非常复杂的任务，方法是将越来越复杂的模型适应这些巨大的数据集(“大模型”)。机器学习被用于日常技术，如电子邮件垃圾邮件过滤、产品推荐系统、广告排名系统、新的运动传感设备，以及最近在语音识别方面的改进。机器学习仍然有巨大的潜力，可以影响从物理到生物，从教育技术到人机交互的各种应用。*大规模机器学习的成功和潜力正在推动开发能够考虑不断增加的数据和模型大小的技术的需求，而这一提议的主要目标是推动将大型模型适应大数据集的技术水平。*基于我现有的工作，可以使用特殊的模型结构来实现运行时的数量级改进，但这项研究的结果将是比现有技术快得多的新技术(例如，多项式时间而不是指数时间，或者通过可能与数据或模型大小一样大的因子来改善运行时间)。具体地，研究将集中在：*1.改进的增量梯度方法：这扩展了我们最近关于指数收敛的随机梯度方法的工作，导致具有更快的收敛速度的方法，以及避免昂贵的完整数据遍历的无存储器方法。*2.利用新的问题结构：该线程寻找新的问题结构来利用(例如图和非二次代理函数)，这将导致发现新的可处理的问题类别。*3.并行和分布式方法：该线程专注于开发当在并行和分布式环境中实现时具有吸引人的理论和实用特性的方法，允许扩展到更大的数据集。*通过专注于提高数据驱动应用程序背后的核心使能技术的可扩展性，这项工作可能会影响学术界和工业界产生巨大数据集的各种科学和工程学科。此外，这项研究将为研究生和本科生提供关键培训。它将培养出具有大规模数据分析技能和经验的高素质人才，具有解决更大问题和模拟更复杂现象所需的理论背景。这些技能将被证明是加拿大不断增长的以知识为基础的经济扩张的一项主要资产。

In nearly all fields of science and engineering, the amount of data we collect is growing at unprecedented rates. We no longer produce data sizes from megabytes to gigabytes, but rather from terabytes to petabytes (and beyond). Machine learning is one of the key tools we use to make sense of these ever-growing quantities of data ('big data'), and it is now being used to solve very complicated tasks by fitting increasingly-complicated models to these huge data sets ('big models'). Machine learning is used in everyday technologies like e-mail spam filtering, product recommendation systems, advertisement ranking systems, new motion sensing devices, and recent improvements in speech recognition. There remains a huge potential for machine learning to impact applications ranging from physics to biology and from education technology to human-computer interaction. ***The successes and potential of large-scale machine learning are driving the need to develop techniques that can consider constantly-increasing data and model sizes, and the objective of this proposal is to advance the state of the art in fitting big models to big data sets. Building on my existing work showing that special model structures can be used to give order-of-magnitude improvements in runtimes,  the outcome of this research will be new techniques that are substantially faster than existing techniques (e.g., polynomial-time instead of exponential-time, or improving runtime by a factor that may be as large as the data or model size). In particular, the research will focus on:***1. Improved incremental gradient methods: this extends our recent work on exponentially-convergent stochastic gradient methods, leading to methods that have faster convergence rates, as well as memory-free methods that avoid expensive full passes through the data.***2. Exploiting new problem structures: this thread seeks out new problem structures to exploit (such as graphs and non-quadratic surrogate functions), which will lead to the discovery of new tractable problem classes.***3. Parallel and distributed methods: this thread focuses on developing methods that have appealing theoretical and practical properties when implemented in a parallel and distributed settings, allowing scaling to much larger datasets.***By focusing on improving the scalability of core enabling technologies behind data-driven applications, this work could affect a wide variety of scientific and engineering disciplines that produce huge datasets, in both academia and industry. Further, this research will provide key training to graduate and undergraduate students. It will produce highly-qualified personnel with skills and experience in large-scale data analysis, with the theoretical background required to solve ever-larger problems and model even more complex phenomena. These skills will prove to be a major asset in the expansion of Canada's growing knowledge-based economy.**