Inducing Sparsity Under Simplex Constraints

27 concepts19 papers1 proposal

In machine learning and statistics, we frequently want models that are sparse—models that rely on only a few active features, assets, or coordinates. The standard recipe for achieving sparsity is $\ell_1$ regularization (such as the Lasso). By adding the sum of the absolute values of the parameters to our loss function, we warp the optimization geometry, creating sharp corners that naturally drive unimportant weights to exactly zero.

But this elegant geometric trick completely breaks down when your parameters are constrained to a probability simplex.

If a vector $x$ represents a probability distribution or a portfolio allocation, its elements must be non-negative ($x_i \ge 0$) and must sum to one ($\sum x_i = 1$). Under these constraints, the absolute value signs in the $\ell_1$ norm become redundant, and the norm simplifies to:

$$\|x\|_1 = \sum |x_i| = \sum x_i = 1$$

On the simplex, the $\ell_1$ norm is a constant. It has a gradient of zero everywhere on the feasible set. It cannot distinguish between a perfectly dense uniform distribution and a perfectly sparse one-hot vector. As a result, standard convex proxies for sparsity become entirely ineffective, a phenomenon explored deeply by Suchi Saria et al., who caution against the "premature envelopment" of penalties into standard convex norms when dealing with structured domains.

Where the Breakdown Matters

This mathematical collapse isn't just an academic curiosity; it breaks core algorithms across multiple domains where sparsity and simplex-like constraints intersect.

  • Portfolio Management: In financial index tracking, a manager seeks to replicate a market benchmark using a small subset of assets to minimize transaction costs. However, because the portfolio weights must sum to one and short-selling is often prohibited (long-only), standard $\ell_1$ regularization fails to promote sparsity (Timothy Hospedales et al.; Yu Zheng et al.). The full-investment constraint locks the $\ell_1$ norm at unity, stripping the penalty of its mathematical ability to zero out assets (Timothy Hospedales et al.).
  • Graph Structure Learning: When estimating a sparse graph Laplacian matrix, the diagonal elements are strictly defined as the sum of the off-diagonal elements. Attempting to apply standard $\ell_1$ regularization to the matrix can paradoxically yield denser graph structures as the optimizer struggles to satisfy the structural constraints while maintaining a non-singular matrix (Yakov Medvedovsky et al.).
  • Topic Modeling: In Nonnegative Matrix Factorization (NMF) for text or mixture models, the columns of the factor matrices represent discrete probability distributions over words or topics. Because these columns must form valid stochastic matrices, standard $\ell_1$ penalties fail to deliver the clean, sparse topic distributions required for interpretability (Siwei Lyu et al.).

To overcome this fundamental limitation, researchers have developed three distinct strategies: exact non-convex projections, concave regularization, and alternative convex relaxations.

Strategy 1: Exact Non-Convex Projections

If convex proxies fail, one direct alternative is to embrace the non-convex cardinality constraint ($\|x\|_0 \le k$) and solve the resulting projection problem explicitly. The challenge then shifts to optimization: how do we project an arbitrary vector onto the intersection of a non-convex sparsity constraint and a convex simplex?

Surprisingly, this intersection does not doom us to intractable runtimes. Anastasios Kyrillidis et al. and Anastasios Kyrillidis et al. demonstrated that these sparse projections onto a simplex or hyperplane can actually be solved exactly and very quickly in linear time. By sorting the vector elements and applying a targeted thresholding step, their algorithms bypass the loose approximations of convex relaxations entirely.

Unconstrained Vector ──> [ Sort & Threshold ] ──> Meets Simplex (∑x=1) & Sparsity (||x||_0 ≤ k)

To scale this to high-dimensional learning, these exact projections are embedded into greedy iterative frameworks. For instance, Jacky Y. Zhang et al. extended Iterative Hard Thresholding (IHT) to discrete probability distributions. While the simplex constraint couples the variables together—making support selection significantly harder than in unconstrained spaces—greedy approximations allow fast, high-quality distribution compression. Similarly, Fengmin Xu et al. leveraged a nonmonotone projected gradient method to strictly enforce cardinality constraints in index tracking, outperforming traditional relaxation techniques.

Strategy 2: Steeper Slopes via Concave Regularization

Another way to restore sparsity-inducing pressure on the simplex is to replace the linear $\ell_1$ penalty with a concave penalty, such as a logarithm or a fractional power ($\ell_p$ with $0 < p < 1$).

The intuition lies in the behavior of the derivative. A linear penalty has a constant derivative, which gets completely canceled out by the flat geometry of the simplex constraint. A concave penalty, however, gets progressively steeper as a coordinate approaches zero. Its derivative blows up to infinity at the boundaries of the simplex. This extreme slope overrides the sum-to-one constraint, aggressively pushing small values all the way to absolute zero.

Penalty Value
  ^
  │      / (Linear L1: Constant slope, becomes flat on simplex)
  │     /
  │    /  _ ─── (Concave: Infinite slope near zero, forces sparsity)
  │  _─▀
  └──────────────────> Parameter Value
  0

Martin O. Larsson et al. successfully utilized this mechanism for sparse mixture models. By employing a "pseudo-Dirichlet" log-penalty, they achieved the necessary concave pressure to zero out components while utilizing the Mountain Pass Theorem to guarantee a unique global maximum during optimization. However, moving away from convexity requires care; as Thang Nguyen et al. noted in spectral topic modeling, balancing the need for sparse Dirichlet priors against the mathematical tractability of convex objectives remains a delicate trade-off.

Strategy 3: Redesigning the Convex Proxy

Must we abandon convex optimization entirely? Not necessarily. The failure belongs specifically to homogeneous norm relaxations like $\ell_1$. If we relax the requirement that our proxy must be a standard norm, we can design convex functions that vary meaningfully across the simplex.

Mert Pilanci et al. proposed a brilliant workaround: instead of minimizing the sum of elements, minimize the reciprocal of the infinity norm ($1/\|x\|_\infty$).

To see why this works intuitively, consider two vectors on a 3-dimensional simplex:

  1. A dense, uniform vector: $x_{\text{dense}} = [1/3, 1/3, 1/3]$
  2. A sparse, one-hot vector: $x_{\text{sparse}} = [1, 0, 0]$

For both vectors, the $\ell_1$ norm is exactly $1$. However, their infinity norms (the maximum element) are vastly different:

  • $\|x_{\text{dense}}\|_\infty = 1/3 \implies 1/\|x_{\text{dense}}\|_\infty = 3$
  • $\|x_{\text{sparse}}\|_\infty = 1 \implies 1/\|x_{\text{sparse}}\|_\infty = 1$

By minimizing $1/\|x\|_\infty$, the optimization objective acts as a valid convex function that heavily penalizes dense distributions and rewards sparse ones.

This insight aligns with a broader theoretical truth uncovered by Marwa El Halabi et al.: when complex combinatorial or monotone structures are forced into tight, homogeneous convex norms, the structural details collapse into a generic $\ell_1$ norm. By moving to non-homogeneous or alternative convex relaxations, we can preserve the structural constraints of our problem without sacrificing the algorithmic guarantees of convexity.

Key Foundational Work

A concave regularization technique for sparse mixture models (2011) — contributed 3 concept elements to this direction.
Recovery of Sparse Probability Measures via Convex Programming (2012) — contributed 2 concept elements to this direction.
Sparse projections onto the simplex (2012) — contributed 2 concept elements to this direction.
History & citationVersion 2 · 2026-10-04

Current · Permanent link

  1. Version 2 (latest) · 2026-10-04 · 18 papers
  2. Version 1 · 2026-10-04 · 17 papers
Cite this direction

Latest version (a living page):

@misc{lacuna_simplex_constrained_sparsity_c650f276,
  title = {simplex-constrained sparsity},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/simplex-constrained-sparsity/rdr_c650f27686c341bbbe1172cf621aa2ed},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-22},
}

This exact version (version 2, frozen text):

@misc{lacuna_simplex_constrained_sparsity_c650f276_v2,
  title = {simplex-constrained sparsity},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/simplex-constrained-sparsity/rdr_c650f27686c341bbbe1172cf621aa2ed/v/2},
  note = {Version 2, frozen 2026-10-04. Accessed 2026-11-22},
}
About

These directions overlap with this one through shared papers.

See something wrong? Report a mistake