# Coordinate Linear Variance Reduction for Generalized Linear Programming arXiv: https://arxiv.org/abs/2111.01842 · HTML: https://mlsanity.com/paper/2111.01842/ ## Key facts - Cited by 10 papers in the map (data through 14 Oct 2026). - Builds on 31 of its 78 references that are in the map. - First posted on arXiv 2 Nov 2021. ## Builds on (most cited first, 30 of 31) - [Convex optimization](https://mlsanity.com/paper/2106.01946/) (2021) - [Learning Models with Uniform Performance via Distributionally Robust Optimization](https://mlsanity.com/paper/1810.08750/) (2018) - [Data-driven Distributionally Robust Optimization Using the Wasserstein Metric: Performance Guarantees and Tractable Reformulations](https://mlsanity.com/paper/1505.05116/) (2015) - [Algorithms for Verifying Deep Neural Networks](https://mlsanity.com/paper/1903.06758/) (2019) - [Statistics of Robust Optimization: A Generalized Empirical Likelihood Approach](https://mlsanity.com/paper/1610.03425/) (2016) - [Large-Scale Methods for Distributionally Robust Optimization](https://mlsanity.com/paper/2010.05893/) (2020) - [Katyusha: The First Direct Acceleration of Stochastic Gradient Methods](https://mlsanity.com/paper/1603.05953/) (2016) - [Distributionally Robust Logistic Regression](https://mlsanity.com/paper/1509.09259/) (2015) - [Lower complexity bounds of first-order methods for convex-concave bilinear saddle-point problems](https://mlsanity.com/paper/1808.02901/) (2018) - [Stochastic Variance Reduction for Variational Inequality Methods](https://mlsanity.com/paper/2102.08352/) (2021) - [Variance Reduction for Matrix Games](https://mlsanity.com/paper/1907.02056/) (2019) - [Practical Large-Scale Linear Programming using Primal-Dual Hybrid Gradient](https://mlsanity.com/paper/2106.04756/) (2021) - [Stochastic Primal-Dual Coordinate Method for Regularized Empirical Risk Minimization](https://mlsanity.com/paper/1409.3257/) (2014) - [Stochastic Primal-Dual Hybrid Gradient Algorithm with Arbitrary Sampling and Imaging Applications](https://mlsanity.com/paper/1706.04957/) (2017) - [Variance Reduction via Accelerated Dual Averaging for Finite-Sum Optimization](https://mlsanity.com/paper/2006.10281/) (2020) - [Fast Distributionally Robust Learning with Variance Reduced Min-Max Optimization](https://mlsanity.com/paper/2104.13326/) (2021) - [Coordinate Methods for Matrix Games](https://mlsanity.com/paper/2009.08447/) (2020) - [Faster First-Order Primal-Dual Methods for Linear Programming using Restarts and Sharpness](https://mlsanity.com/paper/2105.12715/) (2021) - [Stochastic Block Mirror Descent Methods for Nonsmooth and Stochastic Optimization](https://mlsanity.com/paper/1309.2249/) (2013) - [Ergodic convergence of a stochastic proximal point algorithm](https://mlsanity.com/paper/1504.05400/) (2015) - [A New Randomized Block-Coordinate Primal-Dual Proximal Algorithm for Distributed Optimization](https://mlsanity.com/paper/1706.02882/) (2017) - [Primal-dual stochastic gradient method for convex programs with many functional constraints](https://mlsanity.com/paper/1802.02724/) (2018) - [A Coordinate Descent Primal-Dual Algorithm with Large Step Size and Possibly Non Separable Functions](https://mlsanity.com/paper/1508.04625/) (2015) - [Random extrapolation for primal-dual coordinate descent](https://mlsanity.com/paper/2007.06528/) (2020) - [Variance Reduction via Primal-Dual Accelerated Dual Averaging for Nonsmooth Convex Finite-Sums](https://mlsanity.com/paper/2102.13643/) (2021) - [On the convergence of stochastic primal-dual hybrid gradient](https://mlsanity.com/paper/1911.00799/) (2019) - [Adversarial Classification via Distributional Robustness with Wasserstein Ambiguity](https://mlsanity.com/paper/2005.13815/) (2020) - [Smooth Primal-Dual Coordinate Descent Algorithms for Nonsmooth Convex Optimization](https://mlsanity.com/paper/1711.03439/) (2017) - [A First-Order Algorithmic Framework for Wasserstein Distributionally Robust Logistic Regression](https://mlsanity.com/paper/1910.12778/) (2019) - [A Stochastic Variance-reduced Accelerated Primal-dual Method for Finite-sum Saddle-point Problems](https://mlsanity.com/paper/2012.13456/) (2020) ## Built on by (most cited first, 10 of 10) - [Distributionally Robust Optimization via Ball Oracle Acceleration](https://mlsanity.com/paper/2203.13225/) (2022) - [Smooth Monotone Stochastic Variational Inequalities and Saddle Point Problems: A Survey](https://mlsanity.com/paper/2208.13592/) (2022) - [On the Complexity of a Practical Primal-Dual Coordinate Method](https://mlsanity.com/paper/2201.07684/) (2022) - [Efficient Stochastic Approximation of Minimax Excess Risk Optimization](https://mlsanity.com/paper/2306.00026/) (2023) - [Accelerated Cyclic Coordinate Dual Averaging with Extrapolation for Composite Convex Optimization](https://mlsanity.com/paper/2303.16279/) (2023) - [A Whole New Ball Game: A Primal Accelerated Method for Matrix Games and Minimizing the Maximum of Smooth Functions](https://mlsanity.com/paper/2311.10886/) (2023) - [Learning a Single Neuron Robustly to Distributional Shifts and Adversarial Label Noise](https://mlsanity.com/paper/2411.06697/) (2024) - [Nearly Optimal Linear Convergence of Stochastic Primal-Dual Methods for Linear Programming](https://mlsanity.com/paper/2111.05530/) (2021) - [Solving Convex-Concave Problems with tildeO(ε-4/7) Second-Order Oracle Complexity](https://mlsanity.com/paper/2506.08362/) (2025) - [Adaptive Delayed-Update Cyclic Algorithm for Variational Inequalities](https://mlsanity.com/paper/2603.29128/) (2026) ## Abstract (arXiv) 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 Coordinate Linear Variance Reduction (textscclvr; pronounced "clever"). textscclvr 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, textscclvr 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 textscclvr 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.