We propose a general framework for solving the group synchronization problem, where we focus on the setting of adversarial or uniform corruption and sufficiently small noise. Specifically, we apply a novel message passing procedure that uses cycle consistency information in order to estimate the corruption levels of group ratios and consequently solve the synchronization problem in our setting. We first explain why the group cycle consistency information is essential for effectively solving group synchronization problems. We then establish exact recovery and linear convergence guarantees for the proposed message passing procedure under a deterministic setting with adversarial corruption. These guarantees hold as long as the ratio of corrupted cycles per edge is bounded by a reasonable constant. We also establish the stability of the proposed procedure to sub-Gaussian noise. We further establish exact recovery with high probability under a common uniform corruption model.


翻译:我们提出了一个解决群体同步问题的总体框架,我们在此集中关注对抗性或统一腐败的设置和足够小的噪音。具体地说,我们采用一种新的信息传递程序,使用周期一致性信息来估计群体比率的腐败程度,从而解决我们所处的同步问题。我们首先解释为什么群体周期一致性信息对于有效解决群体同步问题至关重要。然后,我们在对抗性腐败的决定性背景下,为拟议的信息传递程序确立准确的回收和线性趋同保证。这些保证只要每个边缘的腐败循环比率受合理的常数约束,就维持不变。我们还将拟议程序稳定到亚高加索噪音。我们还在共同的统一腐败模式下,非常有可能地确定准确的回收。

0
下载
关闭预览

相关内容

Group一直是研究计算机支持的合作工作、人机交互、计算机支持的协作学习和社会技术研究的主要场所。该会议将社会科学、计算机科学、工程、设计、价值观以及其他与小组工作相关的多个不同主题的工作结合起来,并进行了广泛的概念化。官网链接:https://group.acm.org/conferences/group20/
专知会员服务
84+阅读 · 2020年12月5日
专知会员服务
44+阅读 · 2020年10月31日
Linux导论,Introduction to Linux,96页ppt
专知会员服务
77+阅读 · 2020年7月26日
因果图,Causal Graphs,52页ppt
专知会员服务
246+阅读 · 2020年4月19日
【哈佛大学商学院课程Fall 2019】机器学习可解释性
专知会员服务
103+阅读 · 2019年10月9日
Hierarchically Structured Meta-learning
CreateAMind
26+阅读 · 2019年5月22日
Transferring Knowledge across Learning Processes
CreateAMind
27+阅读 · 2019年5月18日
【TED】生命中的每一年的智慧
英语演讲视频每日一推
9+阅读 · 2019年1月29日
Unsupervised Learning via Meta-Learning
CreateAMind
42+阅读 · 2019年1月3日
meta learning 17年:MAML SNAIL
CreateAMind
11+阅读 · 2019年1月2日
人工智能 | COLT 2019等国际会议信息9条
Call4Papers
6+阅读 · 2018年9月21日
已删除
将门创投
5+阅读 · 2018年6月7日
Hierarchical Disentangled Representations
CreateAMind
4+阅读 · 2018年4月15日
Auto-Encoding GAN
CreateAMind
7+阅读 · 2017年8月4日
The Completion of Covariance Kernels
Arxiv
0+阅读 · 2021年7月19日
Model-based clustering of partial records
Arxiv
0+阅读 · 2021年7月19日
Arxiv
0+阅读 · 2021年7月16日
Arxiv
0+阅读 · 2021年7月16日
VIP会员
相关VIP内容
专知会员服务
84+阅读 · 2020年12月5日
专知会员服务
44+阅读 · 2020年10月31日
Linux导论,Introduction to Linux,96页ppt
专知会员服务
77+阅读 · 2020年7月26日
因果图,Causal Graphs,52页ppt
专知会员服务
246+阅读 · 2020年4月19日
【哈佛大学商学院课程Fall 2019】机器学习可解释性
专知会员服务
103+阅读 · 2019年10月9日
相关资讯
Hierarchically Structured Meta-learning
CreateAMind
26+阅读 · 2019年5月22日
Transferring Knowledge across Learning Processes
CreateAMind
27+阅读 · 2019年5月18日
【TED】生命中的每一年的智慧
英语演讲视频每日一推
9+阅读 · 2019年1月29日
Unsupervised Learning via Meta-Learning
CreateAMind
42+阅读 · 2019年1月3日
meta learning 17年:MAML SNAIL
CreateAMind
11+阅读 · 2019年1月2日
人工智能 | COLT 2019等国际会议信息9条
Call4Papers
6+阅读 · 2018年9月21日
已删除
将门创投
5+阅读 · 2018年6月7日
Hierarchical Disentangled Representations
CreateAMind
4+阅读 · 2018年4月15日
Auto-Encoding GAN
CreateAMind
7+阅读 · 2017年8月4日
Top
微信扫码咨询专知VIP会员