The design and complexity analysis of randomized coordinate descent methods, and in particular of variants which update a random subset (sampling) of coordinates in each iteration, depends on the notion of expected separable overapproximation (ESO). This refers to an inequality involving the objective function and the sampling, capturing in a compact way certain smoothness properties of the function in a random subspace spanned by the sampled coordinates. ESO inequalities were previously established for special classes of samplings only, almost invariably for uniform samplings. In this paper we develop a systematic technique for deriving these inequalities for a large class of functions and for arbitrary samplings. We demonstrate that one can recover existing ESO results using our general approach, which is based on the study of eigenvalues associated with samplings and the data describing the function.

研究并分析随机坐标下降方法的设计和复杂度，特别是每次迭代在一个随机子集（采样）中更新的变体，这取决于期望可分离过逼近（ESO）的概念。本文为一类函数和任意采样推导了这种不等式，该方法基于与采样和描述函数的数据相关的特征值的研究。

任意采样坐标下降 II: 期望可分离上估计