Sparsemax
Sparsemax is a mapping from a real-valued score vector to the probability simplex. It resembles the softmax function in converting unconstrained scores into a categorical distribution, but it can assign probabilities that are exactly zero. The transformation is defined by the Euclidean projection of the score vector onto the simplex and is therefore piecewise linear rather than smooth everywhere.
The mapping was introduced in its modern machine-learning form in 2016 by André F. T. Martins, Ramón Fernandez Astudillo, and You Watanabe as a sparse alternative to softmax for probabilistic classification and attention mechanisms. Its mathematical structure connects constrained projection, convex regularization, and loss construction within a single operator.
Definition
For a score vector (z\in\mathbb{R}^K), sparsemax is defined as
[ \operatorname{sparsemax}(z)
\underset{p\in\Delta^{K-1}}{\operatorname{argmin}} ;\frac{1}{2}\lVert p-z\rVert_2^2, ]
where
[ \Delta^{K-1}
\left{ p\in\mathbb{R}^K ;\middle|; p_i\geq 0,; \sum_{i=1}^{K}p_i=1 \right} ]
is the ((K-1))-dimensional probability simplex. The optimization problem has a unique solution because its objective is strictly convex and its feasible region is closed and convex.
The resulting coordinates have the threshold form
[ \operatorname{sparsemax}_i(z)
[z_i-\tau(z)]_+, ]
where ([x]_+=\max(x,0)). The scalar threshold (\tau(z)) is uniquely determined by
[ \sum_{i=1}^{K}[z_i-\tau(z)]_+=1. ]
Consequently, every coordinate below the threshold receives probability zero, while each coordinate above the threshold is shifted downward by the same amount. This distinguishes sparsemax from softmax, whose exponential normalization assigns strictly positive probability to every finite input coordinate.
Computation and support
The threshold can be expressed through the sorted score vector. Let
[ z_{(1)}\geq z_{(2)}\geq\cdots\geq z_{(K)} ]
denote the coordinates arranged in nonincreasing order, and define
[ k(z)
\max\left{ k\in{1,\ldots,K} ;\middle|; 1+kz_{(k)}> \sum_{j=1}^{k}z_{(j)} \right}. ]
The threshold is then
[ \tau(z)
\frac{\sum_{j=1}^{k(z)}z_{(j)}-1}{k(z)}. ]
This characterization follows from the Karush–Kuhn–Tucker conditions for projection onto the simplex. A sorting-based evaluation has time complexity (O(K\log K)), while selection-based simplex-projection methods attain linear expected time without changing the transformation itself.
The active support is
[ S(z)={i\mid \operatorname{sparsemax}_i(z)>0}. ]
Within any region where (S(z)) remains fixed, sparsemax is an affine map. Changes in the support occur on boundaries defined by equalities of the form (z_i=\tau(z)), producing nondifferentiable points between the affine regions.
Differential structure
Away from support boundaries, the Jacobian of sparsemax is
[ J_{\operatorname{sparsemax}}(z)
\operatorname{Diag}(s)
\frac{ss^\top}{|S(z)|}, ]
where (s_i=1) when (i\in S(z)) and (s_i=0) otherwise. For an active coordinate, an infinitesimal score change is centered by the mean change over the support. Inactive coordinates have zero local derivative as long as the perturbation does not alter the support.
This Jacobian is symmetric and idempotent. It represents the orthogonal projection onto the tangent space of the simplex face containing the output distribution. At a support boundary, ordinary differentiability fails, although directional derivatives and generalized Jacobians remain available through nonsmooth analysis.
Sparsemax is invariant under uniform translation of the scores:
[ \operatorname{sparsemax}(z+c\mathbf{1})
\operatorname{sparsemax}(z) ]
for every scalar (c). It is not invariant under positive rescaling, since scaling changes the Euclidean distance between the score vector and the simplex. Large score separations can therefore collapse the output onto a lower-dimensional face or a simplex vertex.
Relation to softmax
Softmax is defined by
[ \operatorname{softmax}_i(z)
\frac{e^{z_i}}{\sum_{j=1}^{K}e^{z_j}}. ]
Its output lies in the relative interior of the simplex for every finite (z). Sparsemax instead projects directly onto the closed simplex, allowing the output to lie on its boundary. The two mappings also arise from different regularized optimization problems.
Softmax can be written as
[ \operatorname{softmax}(z)
\underset{p\in\Delta^{K-1}}{\operatorname{argmax}} \left{ p^\top z+H(p) \right}, ]
where (H(p)=-\sum_i p_i\log p_i) is Shannon entropy. Sparsemax has the corresponding representation
[ \operatorname{sparsemax}(z)
\underset{p\in\Delta^{K-1}}{\operatorname{argmax}} \left{ p^\top z-\frac{1}{2}\lVert p\rVert_2^2 \right}. ]
Thus, softmax uses an entropic regularizer whose boundary gradient diverges, whereas sparsemax uses a quadratic regularizer with finite boundary behavior. This difference accounts for the absence or presence of exact zeros in the resulting distributions.
For two classes, sparsemax reduces to a clipped affine transformation. If (z=(z_1,z_2)), then
[ \operatorname{sparsemax}_1(z)
\left[\frac{z_1-z_2+1}{2}\right]_{[0,1]}, \qquad \operatorname{sparsemax}_2(z)
1-\operatorname{sparsemax}_1(z), ]
where ([x]_{[0,1]}=\min(1,\max(0,x))). Softmax reduces instead to the smooth logistic function.
Sparsemax loss
A classification loss compatible with the transformation follows from the same convex regularization. For a target class (y), the sparsemax loss is
[ L_{\mathrm{sparsemax}}(z;y)
-z_y + \frac{1}{2} \sum_{i\in S(z)} \left(z_i^2-\tau(z)^2\right) + \frac{1}{2}. ]
Its gradient with respect to the score vector is
[ \nabla_z L_{\mathrm{sparsemax}}(z;y)
\operatorname{sparsemax}(z)-e_y, ]
where (e_y) is the one-hot vector associated with the target class. This parallels the gradient of softmax cross-entropy, which equals the softmax distribution minus the target vector.
The loss is convex in (z) and differentiable even though the sparsemax mapping itself is not differentiable at every support boundary. It belongs to the class of Fenchel–Young losses, in which a regularized prediction map and its corresponding loss are generated from a convex conjugate. Mathieu Blondel, André F. T. Martins, and Vlad Niculae subsequently developed this framework as a general account of regularized prediction functions and their associated losses.
Unlike logarithmic loss, sparsemax loss can become exactly zero at a finite score separation. Zero loss occurs when the target coordinate exceeds every competing coordinate by at least one, reflecting the finite margin induced by quadratic regularization.
Use in attention models
In an attention layer, a vector of compatibility scores is normalized into weights over input positions. Replacing softmax with sparsemax yields an attention distribution supported on a subset of those positions. The weighted representation consequently excludes positions assigned zero mass rather than retaining a positive contribution from every position.
The local derivative is also restricted to the active support. Scores outside that support receive zero gradient through the normalization map until a parameter change moves them across the threshold. The resulting optimization dynamics differ from those of smooth, dense attention because changes within one simplex face do not immediately affect inactive coordinates.
Sparsemax has also been applied to structured prediction, including settings in which the feasible probability simplex is replaced by a more general convex polytope. In that context, Euclidean projection produces sparse combinations of admissible structures, while the geometry of the polytope determines which combinations can occur.
Generalizations
Sparsemax is a member of the entmax family, which is based on Tsallis-type entropy regularization. For a parameter (\alpha), the family interpolates between softmax at (\alpha=1) and sparsemax at (\alpha=2). Values greater than one permit exact zeros, while the parameter controls the curvature of the transformation on its active support.
The (\alpha)-entmax transformation is defined through a regularized optimization problem over the simplex, with Tsallis entropy replacing Shannon entropy or the quadratic sparsemax regularizer. Ben Peters, Vlad Niculae, and André F. T. Martins analyzed its use in sequence models, where intermediate parameter values combine sparse support with nonlinear variation among active probabilities.
Related transformations alter the regularizer or the feasible set rather than the score vector alone. These constructions preserve the interpretation of prediction as a regularized maximization problem, but their support patterns and differential properties depend on the chosen convex geometry.