Efficient projections onto the l1-ball for learning in high dimensions

By John C. Duchi, Shai Shalev-Shwartz, Yoram Singer, Tushar Chandra. 2008

1,599 citations recorded by the source corpus.

Subfields: Artificial Intelligence, Computational Mechanics, Optimization & Training

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Computational Mechanics

In Optimization & Training

Citations in the corpus

Agnostic Federated Learning (2019, background): “If Λ is the full simplex, then there exist simple and efficient algorithms for this projection (Duchi et al., 2008).”
Parseval Networks: Improving Robustness to Adversarial Examples (2017, methodology): “This is a well studied problem (Michelot, 1986; Pardalos & Kovoor, 1990; Duchi et al., 2008; Condat, 2016).”
OptNet: Differentiable Optimization as a Layer in Neural Networks (2017, background): “…seem possible to represent this in closed form as a simple network: the closed form solution of such a projection operator requires sorting or ﬁnding a particular median term of the data (Duchi et al., 2008), which is not feasible with a single layer for any form of network that we are aware of.”
Variance-based Regularization with Convex Objectives (2016, methodology): “Notably [19], the projection p(λ) has the form pi(λ) = (vi − η)+ for some η ∈ R, where η is chosen such that ∑n i=1 pi(λ) = 1.”
From Softmax to Sparsemax: A Sparse Model of Attention and Multi-Label Classification (2016, methodology): “Projecting onto the simplex is a well studied problem, for which linear-time algorithms are available (Michelot, 1986; Pardalos & Kovoor, 1990; Duchi et al., 2008).”
Accelerated proximal stochastic dual coordinate ascent for regularized loss minimization (2013, positive): “By the properties of projection onto the simplex (see [9]), for every z ∈ (zj , zj+1) we have that the projection of μ onto the set {b ∈ R+ : ‖b‖1 = z} is of the form ar = max{0, μr − θ/j} where θ = (−z + μ̄j)/j.”
Auto-Sizing Neural Networks: With Applications to n-gram Language Models (2015, methodology): “But this situation seems similar to another optimization problem, projection onto the `1-ball, which Duchi et al. (2008) solve in linear time without pre-sorting.”
Greedy Direction Method of Multiplier for MAP Inference of Large Output Domain (2017, background): “As in [20], (4) can be solved via a simplex projection operation with time complexity O(|Ai| log(|Ai|).”
End-to-End Learning for Structured Prediction Energy Networks (2017, background): “This is similarly problematic for projection onto ∆ w × h D (Duchi et al., 2008).”
Web-scale k-means clustering (2010, methodology): “[2], referred to here as LTL1P.”
Differentiable Neural Architecture Search via Proximal Iterations (2019, background): “Closed-form solution for the PA update exists for many constraint sets in (4), such as `1- and `2-norm ball [10].”
Learning to Detect Salient Objects with Image-Level Supervision (2017, methodology): “In the first step, the optimal ŵ can be computed in O(d) time using the projection algorithm [9].”