标志性完整随机投影
通过随机投影方法生成的嵌入向量在计算效率上得到了广泛应用,本文进一步研究了随机投影对点积和余弦相似度的保留效果并提供了新的理论结果,找出了病态案例并用数值实验进行了测试,发现对于低度或高度节点,此方法在点积上得到的嵌入向量相对不可靠,而与随机投影引入的统计噪声相比,余弦相似度得到了更精确的近似。
Apr, 2024
重新审视了差分隐私的输入扰动框架,介绍了有效算法用于保护隐私的发布余弦相似度和计算多特征边际查询,扩展结果适用于稀疏数据集,提供理论视角解释快速输入扰动算法在实践中的良好表现。
Jun, 2024
研究了通信高效的分布式向量均值估计问题,在分布式优化和联邦学习中经常使用。通过引入 Rand-Proj-Spatial 估计器,利用交叉客户相关信息提高了通信效率,种种实验证明了其优越性。
Oct, 2023
本文研究如何通过建立一个索引来实现针对具有 n 个顶点和 m 个正边的完整带符号图的相关聚类问题的复杂度降低,从而达到 $ O (m + n)$ 的复杂度,同时考虑动态改变环境和非协议度量的结构特性。通过对七个真实数据集进行实验,结果表明相比无索引的算法,我们的基于索引的算法的平均时间减少了 34%。
Jan, 2023
通过几何差异理论证明了一种基于符号线性的位域映射方法,利用标准测地线距离在 Sd 球面上和哈明度量在 Hn 上估计了最小整数 n,同时推导了维度修正公式,进一步验证了斯托拉斯基不变原理的类比情形。
Nov, 2015
提出了一种新的算法框架 ProjUnit,用于保证局部隐私均值估计,该算法框架通过将随机器的输入投影到随机低维子空间并规范化结果,然后在低维空间中运行优化算法来实现计算效率高,通讯复杂度低,并且具有最优误差,同时,通过适当地对设备之间的随机投影矩阵进行相关性,可以实现快速服务器运行时间,最后,实验表明,该算法框架在保持优异的准确度的同时,具有显著较低的通讯和计算成本。
Jun, 2023
该研究探讨了分布式协议用于在大型数据集中查找所有相似向量对的方法,重点关注 Hamming 距离,提出了一种新型组合优化问题来捕捉分析上的核心,展示了边等周形状的设计方法和新的距离相关性界限。
Nov, 2016
本文研究了具有 n 个客户机的有限和分布式优化问题,针对流行的 δ- 相似性条件和 μ- 强凸性,提出了 SVRS 和 AccSVRS 两种新算法,其通信复杂度分别为 O (n+√(nδ/μ) ) 和 O (n+ n^(3/4)√(δ/μ) ),并显示了接近匹配的下界以验证其紧密性。
Apr, 2023