We study a class of generalized linear programs (GLP) in a large-scale setting, which includes simple, possibly nonsmooth convex regularizer and simple convex set constraints. By reformulating (GLP) as an equivalent convex-concave min-max problem, we show that the linear structure in the problem can be used to design an efficient, scalable first-order algorithm, to which we give the name \emph{Coordinate Linear Variance Reduction} (\textsc{clvr}; pronounced "clever"). \textsc{clvr} yields improved complexity results for (GLP) that depend on the max row norm of the linear constraint matrix in (GLP) rather than the spectral norm. When the regularization terms and constraints are separable, \textsc{clvr} admits an efficient lazy update strategy that makes its complexity bounds scale with the number of nonzero elements of the linear constraint matrix in (GLP) rather than the matrix dimensions. On the other hand, for the special case of linear programs, by exploiting sharpness, we propose a restart scheme for \textsc{clvr} to obtain empirical linear convergence. Then we show that Distributionally Robust Optimization (DRO) problems with ambiguity sets based on both $f$-divergence and Wasserstein metrics can be reformulated as (GLPs) by introducing sparsely connected auxiliary variables. We complement our theoretical guarantees with numerical experiments that verify our algorithm's practical effectiveness, in terms of wall-clock time and number of data passes.
翻译:广义线性规划的坐标线性方差缩减
翻译后的摘要:
我们研究了一类广义线性规划问题(GLP),在大规模情况下考虑了包含简单但可能非光滑的凸正则项和简单的凸集约束。通过将(GLP)重写为等价的凸-凹极小极大问题,我们展示了问题中的线性结构可以用于设计有效且可伸缩的一阶算法,并且我们将该算法命名为“坐标线性方差缩减”(CLVR)。CLVR使得(GLP)的复杂度改进取决于线性约束矩阵的最大行范数而非其谱范数。当正则化项和约束是可分离的时,CLVR采用高效的延迟更新策略,使得其复杂度与(GLP)中线性约束矩阵的非零元素数量相关而非矩阵维度相关。另一方面,对于线性规划的特殊情形,通过利用锐度,我们提出了一个重启方案,以获得实际线性收敛。然后,我们展示了通过引入稀疏连接的辅助变量,基于$f$-散度和Wasserstein度量的模糊优化问题(DRO)可以重写为(GLP)。我们使用数值实验来验证算法的实际有效性,包括墙时钟时间和数据通道数等方面的表现。