3.8 Proceedings Paper

Fast Projection Onto Convex Smooth Constraints

Journal

INTERNATIONAL CONFERENCE ON MACHINE LEARNING, VOL 139
Volume 139, Issue -, Pages 7492-7501

Publisher

JMLR-JOURNAL MACHINE LEARNING RESEARCH

Keywords

-

Funding

  1. European Research Council (ERC) under the European Union [815943]
  2. Swiss National Science Foundation [SNSF 200021 172781]
  3. NCCR Automation [51NF40 180545]
  4. Israel Science Foundation [447/20]

Ask authors/readers for more resources

The paper focuses on the important problem of Euclidean projection onto a convex set in constrained optimization tasks. It proposes a simple and efficient primal-dual approach for projection problems with smooth constraints and significantly fewer constraints than dimensions, with a runtime linear in dimension and logarithmic in the inverse of target accuracy. Empirical results demonstrate its performance compared to standard baselines.
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.

Authors

I am an author on this paper
Click your name to claim this paper and add it to your profile.

Reviews

Primary Rating

3.8
Not enough ratings

Secondary Ratings

Novelty
-
Significance
-
Scientific rigor
-
Rate this paper

Recommended

No Data Available
No Data Available