Large-scale randomized-coordinate descent methods with non-separable linear constraints

Ahmed Hefny Carnegie Mellon University, Sashank Jakkam Reddi Carnegie Mellon University, Carlton Downey Carnegie Mellon University, Avinava Dubey Carnegie Mellon University, Suvrit Sra
Proceedings of the 31st Conference on Uncertainty in Artificial Intelligence, PMLR R13:586-595, 2015.

Abstract

We develop randomized block coordinate de- scent (CD) methods for linearly constrained con- vex optimization. Unlike other large-scale CD methods, we do not assume the constraints to be separable, but allow them be coupled linearly. To our knowledge, ours is the first CD method that allows linear coupling constraints, without making the global iteration complexity have an exponential dependence on the number of con- straints. We present algorithms and theoreti- cal analysis for four key (convex) scenarios: (i) smooth; (ii) smooth + separable nonsmooth; (iii) asynchronous parallel; and (iv) stochastic. We discuss some architectural details of our methods and present preliminary results to illustrate the behavior of our algorithms.

Cite this Paper

BibTeX
@InProceedings{pmlr-vR13-university15m, title = {Large-scale randomized-coordinate descent methods with non-separable linear constraints}, author = {University, Ahmed Hefny Carnegie Mellon and University, Sashank Jakkam Reddi Carnegie Mellon and University, Carlton Downey Carnegie Mellon and University, Avinava Dubey Carnegie Mellon and Sra, Suvrit}, booktitle = {Proceedings of the 31st Conference on Uncertainty in Artificial Intelligence}, pages = {586--595}, year = {2015}, editor = {Meila, Marina and Heskes, Tom}, volume = {R13}, series = {Proceedings of Machine Learning Research}, month = {12--16 Jul}, publisher = {PMLR}, pdf = {https://raw.githubusercontent.com/mlresearch/r13/main/assets/university15m/university15m.pdf}, url = {https://proceedings.mlr.press/r13/university15m.html}, abstract = {We develop randomized block coordinate de- scent (CD) methods for linearly constrained con- vex optimization. Unlike other large-scale CD methods, we do not assume the constraints to be separable, but allow them be coupled linearly. To our knowledge, ours is the first CD method that allows linear coupling constraints, without making the global iteration complexity have an exponential dependence on the number of con- straints. We present algorithms and theoreti- cal analysis for four key (convex) scenarios: (i) smooth; (ii) smooth + separable nonsmooth; (iii) asynchronous parallel; and (iv) stochastic. We discuss some architectural details of our methods and present preliminary results to illustrate the behavior of our algorithms.}, note = {Reissued by PMLR on 04 October 2026.} }
Endnote
%0 Conference Paper %T Large-scale randomized-coordinate descent methods with non-separable linear constraints %A Ahmed Hefny Carnegie Mellon University %A Sashank Jakkam Reddi Carnegie Mellon University %A Carlton Downey Carnegie Mellon University %A Avinava Dubey Carnegie Mellon University %A Suvrit Sra %B Proceedings of the 31st Conference on Uncertainty in Artificial Intelligence %C Proceedings of Machine Learning Research %D 2015 %E Marina Meila %E Tom Heskes %F pmlr-vR13-university15m %I PMLR %P 586--595 %U https://proceedings.mlr.press/r13/university15m.html %V R13 %X We develop randomized block coordinate de- scent (CD) methods for linearly constrained con- vex optimization. Unlike other large-scale CD methods, we do not assume the constraints to be separable, but allow them be coupled linearly. To our knowledge, ours is the first CD method that allows linear coupling constraints, without making the global iteration complexity have an exponential dependence on the number of con- straints. We present algorithms and theoreti- cal analysis for four key (convex) scenarios: (i) smooth; (ii) smooth + separable nonsmooth; (iii) asynchronous parallel; and (iv) stochastic. We discuss some architectural details of our methods and present preliminary results to illustrate the behavior of our algorithms. %Z Reissued by PMLR on 04 October 2026.
APA
University, A.H.C.M., University, S.J.R.C.M., University, C.D.C.M., University, A.D.C.M. & Sra, S.. (2015). Large-scale randomized-coordinate descent methods with non-separable linear constraints. Proceedings of the 31st Conference on Uncertainty in Artificial Intelligence, in Proceedings of Machine Learning Research R13:586-595 Available from https://proceedings.mlr.press/r13/university15m.html. Reissued by PMLR on 04 October 2026.

Related Material