Fast Projection Onto Convex Smooth Constraints

Ilnura Usmanova, Maryam Kamgarpour, Andreas Krause, Kfir Levy
Proceedings of the 38th International Conference on Machine Learning, PMLR 139:10476-10486, 2021.

Abstract

The Euclidean projection onto a convex set is an important problem that arises in numerous constrained optimization tasks. Unfortunately, in many cases, computing projections is computationally demanding. In this work, we focus on projection problems where the constraints are smooth and the number of constraints is significantly smaller than the dimension. The runtime of existing approaches to solving such problems is either cubic in the dimension or polynomial in the inverse of the target accuracy. Conversely, we propose a simple and efficient primal-dual approach, with a runtime that scales only linearly with the dimension, and only logarithmically in the inverse of the target accuracy. We empirically demonstrate its performance, and compare it with standard baselines.

Cite this Paper

BibTeX
@InProceedings{pmlr-v139-usmanova21a, title = {Fast Projection Onto Convex Smooth Constraints}, author = {Usmanova, Ilnura and Kamgarpour, Maryam and Krause, Andreas and Levy, Kfir}, booktitle = {Proceedings of the 38th International Conference on Machine Learning}, pages = {10476--10486}, year = {2021}, editor = {Meila, Marina and Zhang, Tong}, volume = {139}, series = {Proceedings of Machine Learning Research}, month = {18--24 Jul}, publisher = {PMLR}, pdf = {http://proceedings.mlr.press/v139/usmanova21a/usmanova21a.pdf}, url = {https://proceedings.mlr.press/v139/usmanova21a.html}, abstract = {The Euclidean projection onto a convex set is an important problem that arises in numerous constrained optimization tasks. Unfortunately, in many cases, computing projections is computationally demanding. In this work, we focus on projection problems where the constraints are smooth and the number of constraints is significantly smaller than the dimension. The runtime of existing approaches to solving such problems is either cubic in the dimension or polynomial in the inverse of the target accuracy. Conversely, we propose a simple and efficient primal-dual approach, with a runtime that scales only linearly with the dimension, and only logarithmically in the inverse of the target accuracy. We empirically demonstrate its performance, and compare it with standard baselines.} }
Endnote
%0 Conference Paper %T Fast Projection Onto Convex Smooth Constraints %A Ilnura Usmanova %A Maryam Kamgarpour %A Andreas Krause %A Kfir Levy %B Proceedings of the 38th International Conference on Machine Learning %C Proceedings of Machine Learning Research %D 2021 %E Marina Meila %E Tong Zhang %F pmlr-v139-usmanova21a %I PMLR %P 10476--10486 %U https://proceedings.mlr.press/v139/usmanova21a.html %V 139 %X The Euclidean projection onto a convex set is an important problem that arises in numerous constrained optimization tasks. Unfortunately, in many cases, computing projections is computationally demanding. In this work, we focus on projection problems where the constraints are smooth and the number of constraints is significantly smaller than the dimension. The runtime of existing approaches to solving such problems is either cubic in the dimension or polynomial in the inverse of the target accuracy. Conversely, we propose a simple and efficient primal-dual approach, with a runtime that scales only linearly with the dimension, and only logarithmically in the inverse of the target accuracy. We empirically demonstrate its performance, and compare it with standard baselines.
APA
Usmanova, I., Kamgarpour, M., Krause, A. & Levy, K.. (2021). Fast Projection Onto Convex Smooth Constraints. Proceedings of the 38th International Conference on Machine Learning, in Proceedings of Machine Learning Research 139:10476-10486 Available from https://proceedings.mlr.press/v139/usmanova21a.html.

Related Material