Delay-Tolerant Algorithms for Asynchronous Distributed Online Learning

1. Abstract

  • Adaptive gradient methods,adapt not only to the sequence of gradients, but also to the precise update delays that occur. 不仅考虑梯度序列,也考虑update delay
  • 首先提出了一个impractical的算法,能够准确量化delay的影响
  • 然后分析了AdaptiveRevision,能够高效实现,获得comparable guarantee
  • 核心的idea是,revise以前梯度步骤的learning rate

2. Intro

2.1 Problem setting

  • the Readers and Updaters may reside on different machines, perhaps located in different parts
    of the world, communication between them is not instantaneous. Reader和updater之间的通信不是瞬时的,因此Reader使用的通常不是最新的参数
  • While the coefficient vector may be stored and updated centrally, predictions must be available in milliseconds in any part of the world. This leads naturally to an architecture in which a large number of Readers maintain local copies of the coefficient vector, sending updates to the Updaters and periodically requesting fresh coefficients from them. 因为参数被中心式地存储和更新,但是prediction必须要实时完成。因此Reader需要保存参数的本地副本,发送更新给Updater,定期地请求最新的参数
  • 线性模型,稀疏数据
  • 因为delay的存在,operation之间交互影响,因此细粒度的分析很困难
  • 假设维度之间是独立的,可以先给出每个coordinate的bound,然后累加每个coordinates,就可以得到总体的bound
  • 假设Inorder,如果s1的read在s2之前,那么s1的update在s2之后
  • 如果产生update s的read发生在t之前,那么我们说update s在t时刻是outstanding的
  • require moderate additional storage and network cost: we store a sum of gradients along with each coefficient, and for each Read, we remember the value of this gradient sum at the time of the Read until the corresponding Update occurs. 存储每个维度的梯度总和,对每个Read,记录Read时的梯度总和,直到对应的Update
  • the gradient sum is sent from the Updater to the Reader and back again, ensuring it is available exactly when needed. 将gradient sum从updater发送给reader,然后reader再发回给reader,这样能保证需要的时候是available

3. Experiments

  • hypothetical algorithms and AdaptiveRevision
  • 两个medium-sized数据集。第一个是web search advertising dataset from a large search engine,310万samples,sparse特征;第二个是恶意URL数据集
  • 机器学习算法:logistic regression

4. Conclusions and future work

  • The key algorithmic technique is maintaining a sum of gradients, which allows the adjustment of
    all learning rates for gradient updates that occurred between the current Update and its Read. 核心的算法是,保存gradient sum,允许调整learning rate,对那些发生在当前Update和对应的Read之间的updates
  • The analysis method is novel, but is also somewhat indirect. Ideally such an analysis would also remove the technical need for the InOrder assumption, and also allow for the analysis of AdaptiveRevision variants of OGD with Projection and Dual Averaging. 证明不是很直接,理想的证明应该去掉InOrder的假设,也应该可以适应projection和dual average的variants
最后编辑于
©著作权归作者所有,转载或内容合作请联系作者
  • 序言:七十年代末,一起剥皮案震惊了整个滨河市,随后出现的几起案子,更是在滨河造成了极大的恐慌,老刑警刘岩,带你破解...
    沈念sama阅读 212,686评论 6 492
  • 序言:滨河连续发生了三起死亡事件,死亡现场离奇诡异,居然都是意外死亡,警方通过查阅死者的电脑和手机,发现死者居然都...
    沈念sama阅读 90,668评论 3 385
  • 文/潘晓璐 我一进店门,熙熙楼的掌柜王于贵愁眉苦脸地迎上来,“玉大人,你说我怎么就摊上这事。” “怎么了?”我有些...
    开封第一讲书人阅读 158,160评论 0 348
  • 文/不坏的土叔 我叫张陵,是天一观的道长。 经常有香客问我,道长,这世上最难降的妖魔是什么? 我笑而不...
    开封第一讲书人阅读 56,736评论 1 284
  • 正文 为了忘掉前任,我火速办了婚礼,结果婚礼上,老公的妹妹穿的比我还像新娘。我一直安慰自己,他们只是感情好,可当我...
    茶点故事阅读 65,847评论 6 386
  • 文/花漫 我一把揭开白布。 她就那样静静地躺着,像睡着了一般。 火红的嫁衣衬着肌肤如雪。 梳的纹丝不乱的头发上,一...
    开封第一讲书人阅读 50,043评论 1 291
  • 那天,我揣着相机与录音,去河边找鬼。 笑死,一个胖子当着我的面吹牛,可吹牛的内容都是我干的。 我是一名探鬼主播,决...
    沈念sama阅读 39,129评论 3 410
  • 文/苍兰香墨 我猛地睁开眼,长吁一口气:“原来是场噩梦啊……” “哼!你这毒妇竟也来了?” 一声冷哼从身侧响起,我...
    开封第一讲书人阅读 37,872评论 0 268
  • 序言:老挝万荣一对情侣失踪,失踪者是张志新(化名)和其女友刘颖,没想到半个月后,有当地人在树林里发现了一具尸体,经...
    沈念sama阅读 44,318评论 1 303
  • 正文 独居荒郊野岭守林人离奇死亡,尸身上长有42处带血的脓包…… 初始之章·张勋 以下内容为张勋视角 年9月15日...
    茶点故事阅读 36,645评论 2 327
  • 正文 我和宋清朗相恋三年,在试婚纱的时候发现自己被绿了。 大学时的朋友给我发了我未婚夫和他白月光在一起吃饭的照片。...
    茶点故事阅读 38,777评论 1 341
  • 序言:一个原本活蹦乱跳的男人离奇死亡,死状恐怖,灵堂内的尸体忽然破棺而出,到底是诈尸还是另有隐情,我是刑警宁泽,带...
    沈念sama阅读 34,470评论 4 333
  • 正文 年R本政府宣布,位于F岛的核电站,受9级特大地震影响,放射性物质发生泄漏。R本人自食恶果不足惜,却给世界环境...
    茶点故事阅读 40,126评论 3 317
  • 文/蒙蒙 一、第九天 我趴在偏房一处隐蔽的房顶上张望。 院中可真热闹,春花似锦、人声如沸。这庄子的主人今日做“春日...
    开封第一讲书人阅读 30,861评论 0 21
  • 文/苍兰香墨 我抬头看了看天上的太阳。三九已至,却和暖如春,着一层夹袄步出监牢的瞬间,已是汗流浃背。 一阵脚步声响...
    开封第一讲书人阅读 32,095评论 1 267
  • 我被黑心中介骗来泰国打工, 没想到刚下飞机就差点儿被人妖公主榨干…… 1. 我叫王不留,地道东北人。 一个月前我还...
    沈念sama阅读 46,589评论 2 362
  • 正文 我出身青楼,却偏偏与公主长得像,于是被迫代替她去往敌国和亲。 传闻我的和亲对象是个残疾皇子,可洞房花烛夜当晚...
    茶点故事阅读 43,687评论 2 351

推荐阅读更多精彩内容

  • Aria2 是一个轻量级多协议和多源命令行下载实用工具。它支持 HTTP / HTTPS, FTP, SFTP, ...
    孤逐王阅读 31,694评论 0 17
  • 片段为黄色部分区域,作者介绍了预防愤怒的方法:在自我意识到愤怒时主动将其遏制住,并将愤怒的想法写下来,通过个人的实...
    小太阳and小煤球阅读 180评论 0 0
  • 【以赛 亚书41:10】你不要害怕、因为我与你同在.不要惊惶、因为我是你的神.我必坚固你、我必帮助你、我必用我公义...
    高桥先生阅读 501评论 1 2
  • “公主!您就吃点吧!您几天没吃饭!我们可怎么跟竹大人交代?” “我不吃!滚开!”朱尧娥怒吼道。砰地一声把门狠狠的摔...
    莫弦一阅读 441评论 0 1
  • 阿碧,我从来不缺爱,从来努力爱别人,所以,你不要给我织毛衣。 阿碧,我已经不那么伤心了,多情的,痴情的,无情的,皆...
    唐诗远阅读 347评论 2 12