权益分类	功能权益	普通用户	{{item.name}}会员
{{category.name}}	{{benefitItem.name}}

Accelerated Coordinate Descent Methods for Big Data Problems

大数据问题的加速坐标下降法

基本信息

批准号：
EP/K02325X/1
负责人：
Peter Richtarik
金额：
$ 12.83万
依托单位：
University of Edinburgh
依托单位国家：
英国
项目类别：
Research Grant
财政年份：
2013
资助国家：
英国
起止时间：
2013 至无数据
项目状态：
已结题

来源：
https://gtr.ukri.org/projects?ref=EP%2FK02325X%2F1
关键词：
Accelerated Coordinate Descent Methods Big

项目摘要

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.

在英国和其他地方，现代社会和经济的大部分正在朝着数字化和计算的方向发展。人类现在能够收集和存储来自诸如健康记录（例如，IBM "沃森“项目，MRI/CT扫描），政府数据库（例如，电子政务，GORS：政府运营研究服务），社交网络（例如，Facebook、LinkedIn、delicious）、在线新闻（例如，纽约时报文章数据库）、公司数据库（例如，银行记录，Amazon.com）和互联网。因此，全球社会正面临许多前所未有的挑战和机遇。其中最大的挑战之一是以最佳方式提取、理解和利用这些巨大数据源中包含的信息的能力（或者更确切地说，缺乏这种能力）。其主要技术是“形成优化问题”，然后在合适的计算环境中使用精心选择的优化算法来解决它（例如，在这个项目中，我们的目标是通过开发、分析和实施新的加速并行坐标下降（CD）方法，在解决大数据领域产生的优化问题的能力上取得突破。由于在大数据问题中，数据通常是高度结构化的，因此设计良好的CD方法可以具有非常低的内存需求和每次迭代的算法成本-通常比问题的维度小得多。这与标准方法形成了鲜明的对比，标准方法的单次迭代的算术复杂度至少与维数成二次方关系。加速理论我们将分析迭代复杂度（即，给出实现规定精度水平所需的迭代/步骤的数量的界限）的新的并行坐标下降方法的加速使用以下4个策略：a）不均匀性（单个坐标更新的频率），B）重复性（更新和计算），c）（数据和计算到集群的节点的）分布和d）（算法所依赖的某些操作和计算的）不精确性。随机梯度下降。我们将从理论上和数值上分析并行坐标下降法和并行随机梯度下降法之间的关系. ACDC代码。我们将在代码中实现加速算法，我们将公开提供。