Accelerated Coordinate Descent Methods for Big Data Problems

在英国和其他地方，现代社会和经济的大部分都在朝着数字化和计算的方向发展。人类现在能够收集和存储大量的数字数据，这些数据来自以下来源：健康记录(例如IBM‘Watson’计划、核磁共振/CT扫描)、政府数据库(例如电子政府、GORS：政府业务研究服务)、社交网络(例如Facebook、Linked-In、Deliar)、在线新闻(例如纽约时报文章数据库)、企业数据库(例如银行记录、亚马逊)和互联网。因此，全球社会面临许多前所未有的挑战和机遇。其中最大的问题之一与提取、理解和以最佳方式利用这些巨大数据源中包含的信息的能力(或者更确切地说，缺乏能力)有关。这个项目的主要技术是“形成一个优化问题”，然后在合适的计算环境(如多核工作站、支持GPU的机器、云)中使用精心选择的优化算法来解决它。在这个项目中，我们的目标是通过开发、分析和实施新的加速并行坐标下降(CD)方法来帮助我们突破解决大数据领域产生的优化问题的能力。由于在大数据问题中，数据通常是高度结构化的，设计良好的CD方法可以具有非常低的内存需求和每次迭代的算术成本-通常比问题的维度小得多。这与单次迭代的算法复杂度至少二次依赖于维度的标准方法形成鲜明对比。我们的研究目标是：1.加速理论。我们将分析使用以下4种策略加速的新的并行坐标下降方法的迭代复杂性(即，给出达到指定精度水平所需的迭代/步骤数量的界限)：a)非一致性(单个坐标被更新的频率)，b)异步性(更新和计算)，c)分布(数据和计算到集群的节点)和d)不精确(算法依赖的某些操作和计算)2.随机梯度下降。我们将对并行坐标下降(CD)方法和并行随机梯度下降(SGD)方法之间的关系进行理论分析和数值验证。ACDC代码。我们将在代码中实现加速算法，我们将公开该代码。

Much of modern society and economy, in the United Kingdom and elsewhere, is moving in the direction of digitization and computation. Humankind is now able to collect and store enormous quantities of digital data coming from sources such as health records (e.g., IBM ``Watson'' project, MRI/CT scans), government databases (e.g., e-Government, GORS: government operational research service), social networks (e.g., Facebook, Linked-IN, delicious), online news (e.g., New York Times article database), corporate databases (e.g., bank records, Amazon.com) and the internet. Global society is, as a consequence, facing many unprecedented challenges and opportunities. One of the biggest of these has to do with the ability (or rather, lack thereof) to distill, understand and utilize in an optimal way the information contained within these gigantic data sources. The main technology for this is to "form an optimization problem'' and then solve it using a well-chosen optimization algorithm in a suitable computing environment (e.g., a multicore workstation, GPU-enabled machine, cloud).In this project we aim to contribute to a breakthrough in our ability to solve optimization problems arising from big data domains via developing, analyzing and implementing new accelerated parallel coordinate descent (CD) methods. Since in big data problems the data is typically highly structured, well-designed CD methods can have very low memory requirements and arithmetic cost per iteration---often much smaller than the dimension of the problem. This is in sharp contrast with standard methods whose arithmetic complexity of a single iteration depends on the dimension at least quadratically.Our research objectives are:1. Acceleration Theory. We will analyze the iteration complexity (i.e., give bounds on the number of iterations/steps needed to achieve a prescribed level of accuracy) of new parallel coordinate descent methods accelerated using the following 4 strategies: a) nonuniformity (of the frequency with which individual coordinates are updated), b) asynchronicity (of updates and computation), c) distribution (of data and computation to nodes of a cluster) and d) inexactness (of certain operations and computations the algorithm depends on).2. Stochastic Gradient Descent. We will analyze theoretically and test numerically the relationship between parallel coordinate descent (CD) methods and parallel stochastic gradient descent (SGD) methods.3. ACDC Code. We will implement the accelerated algorithms in a code which we will make publicly available.