# Fast Projection Onto Convex Smooth Constraints

arXiv: https://arxiv.org/abs/2109.09835 · HTML: https://mlsanity.com/paper/2109.09835/

## Key facts

- Cited by 3 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 20 Sep 2021.

## Built on by (most cited first, 3 of 3)

- [Policy Gradient Algorithms for Robust MDPs with Non-Rectangular Uncertainty Sets](https://mlsanity.com/paper/2305.19004/) (2023)
- [Non-convex online learning via algorithmic equivalence](https://mlsanity.com/paper/2205.15235/) (2022)
- [Towards Optimal Offline Reinforcement Learning](https://mlsanity.com/paper/2503.12283/) (2025)

## Abstract (arXiv)

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.