# Convex optimization over a probability simplex

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 24 of its 103 references that are in the map.
- First posted on arXiv 15 May 2023.

## Builds on (most cited first, 24 of 24)

- [Kernel and Rich Regimes in Overparametrized Models](https://mlsanity.com/paper/2002.09277/) (2020)
- [Cheap Orthogonal Constraints in Neural Networks: A Simple Parametrization of the Orthogonal and Unitary Group](https://mlsanity.com/paper/1901.08428/) (2019)
- [Relatively-Smooth Convex Optimization by First-Order Methods, and Applications](https://mlsanity.com/paper/1610.05708/) (2016)
- [On the Global Linear Convergence of Frank-Wolfe Optimization Variants](https://mlsanity.com/paper/1511.05932/) (2015)
- [Projection onto the probability simplex: An efficient algorithm with a simple proof, and an application](https://mlsanity.com/paper/1309.1541/) (2013)
- [On the Fenchel Duality between Strong Convexity and Lipschitz Continuous Gradient](https://mlsanity.com/paper/1803.06573/) (2018)
- [Fast and accurate optimization on the orthogonal manifold without retraction](https://mlsanity.com/paper/2102.07432/) (2021)
- [Decentralized Riemannian Gradient Descent on the Stiefel Manifold](https://mlsanity.com/paper/2102.07091/) (2021)
- [More is Less: Inducing Sparsity via Overparameterization](https://mlsanity.com/paper/2112.11027/) (2021)
- [Existence, Stability and Scalability of Orthogonal Convolutional Neural Networks](https://mlsanity.com/paper/2108.05623/) (2021)
- [A Framework of Constraint Preserving Update Schemes for Optimization on Stiefel Manifold](https://mlsanity.com/paper/1301.0172/) (2013)
- [Robust Implicit Regularization via Weight Normalization](https://mlsanity.com/paper/2305.05448/) (2023)
- [Frank-Wolfe and friends: a journey into projection-free first-order optimization methods](https://mlsanity.com/paper/2106.10261/) (2021)
- [From the simplex to the sphere: Faster constrained optimization using the Hadamard parametrization](https://mlsanity.com/paper/2112.05273/) (2021)
- [Ellipsoidal Rounding for Nonnegative Matrix Factorization Under Noisy Separability](https://mlsanity.com/paper/1309.5701/) (2013)
- [Scalable Robust Matrix Recovery: Frank-Wolfe Meets Proximal Methods](https://mlsanity.com/paper/1403.7588/) (2014)
- [A Distributed Frank-Wolfe Algorithm for Communication-Efficient Sparse Learning](https://mlsanity.com/paper/1404.2644/) (2014)
- [Convergence of the Exponentiated Gradient Method with Armijo Line Search](https://mlsanity.com/paper/1712.08480/) (2017)
- [Sparse PCA: a Geometric Approach](https://mlsanity.com/paper/2210.06590/) (2022)
- [Frank-Wolfe algorithm for learning SVM-type multi-category classifiers](https://mlsanity.com/paper/2008.08894/) (2020)
- [Latent Simplex Position Model: High Dimensional Multi-view Clustering with Uncertainty Quantification](https://mlsanity.com/paper/1903.09029/) (2019)
- [A Sketching Method for Finding the Closest Point on a Convex Hull](https://mlsanity.com/paper/2102.10502/) (2021)
- [Fast SVM training using approximate extreme points](https://mlsanity.com/paper/1304.1391/) (2013)
- [Stratifying High Dimensional Data Based on Proximity to the Convex Hull Boundary](https://mlsanity.com/paper/1611.01419/) (2016)

## Abstract (arXiv)

We propose a new iteration scheme, the Cauchy-Simplex, to optimize convex problems over the probability simplex w∈ℝn | sumi wi=1 textrmand wi≥0. Specifically, we map the simplex to the positive quadrant of a unit sphere, envisage gradient descent in latent variables, and map the result back in a way that only depends on the simplex variable. Moreover, proving rigorous convergence results in this formulation leads inherently to tools from information theory (e.g., cross-entropy and KL divergence). Each iteration of the Cauchy-Simplex consists of simple operations, making it well-suited for high-dimensional problems. In continuous time, we prove that f(xT)-f(x^*) = O(1/T) for differentiable real-valued convex functions, where T is the number of time steps and w^* is the optimal solution. Numerical experiments of projection onto convex hulls show faster convergence than similar algorithms. Finally, we apply our algorithm to online learning problems and prove the convergence of the average regret for (1) Prediction with expert advice and (2) Universal Portfolios.