We propose matrix norm inequalities that extend the Recht-R\'e (2012) conjecture on a noncommutative AM-GM inequality by supplementing it with another inequality that accounts for single-shuffle, which is a widely used without-replacement sampling scheme that shuffles only once in the beginning and is overlooked in the Recht-R\'e conjecture. Instead of general positive semidefinite matrices, we restrict our attention to positive definite matrices with small enough condition numbers, which are more relevant to matrices that arise in the analysis of SGD. For such matrices, we conjecture that the means of matrix products corresponding to with- and without-replacement variants of SGD satisfy a series of spectral norm inequalities that can be summarized as: "single-shuffle SGD converges faster than random-reshuffle SGD, which is in turn faster than with-replacement SGD." We present theorems that support our conjecture by proving several special cases.
翻译:我们提出矩阵规范不平等,扩大Recht-R\'e-GM(2012年)对非对称性AM-GM不平等的预测,方法是用另一种不平等来补充它,而另一种不平等是单一 Sheffle,这是一种广泛使用的无替换抽样计划,在开始时只打乱一次,在Recht-R\'e的预测中被忽视。我们没有一般的正半确定基质,而是将注意力限制在条件数字小于条件的正确定基质,而这些条件数与分析 SGD 时产生的矩阵更为相关。关于这种矩阵,我们推测SGD的矩阵产品与SGD变异和不替换变异对应,满足一系列光谱规范不平等,可以概括为:“SGDD(Single-shulfle SGD)比随机变异变组合速度更快,转而比变换 SGD(GD)更快。”我们通过证明几个特殊案例来支持我们的预测。