RECORD
Convex optimization over a probability simplex
Optimization and Control · Submitted 15 May 2023
abstract compiled · 2026-09-23 · no language-model review
The authors' main claim In continuous time, we prove that $f(x_T)-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.
The compiled record
The paper's own sentences, arranged. Each label is drawn from a closed vocabulary; the number beside it is the probability the classifier gave that label. Numbers in the tables are the authors', checked by code. No sentence in this record was written by a model.
Open the compiled record
The abstract, sentence by sentence
We propose a new iteration scheme, the Cauchy-Simplex, to optimize convex problems over the probability simplex $\{w\in\mathbb{R}^n\ |\ \sum_i w_i=1\ \textrm{and}\ w_i\geq0\}$. 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(x_T)-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.
background contribution method result interpretation main claim
| # | sentence | role | the authors' own work | states the main conclusion | strength |
|---|---|---|---|---|---|
| s0 | We propose a new iteration scheme, the Cauchy-Simplex, to optimize convex problems over the probability simplex $\{w\in\mathbb{R}^n\ |\ \sum_i w_i=1\ \textrm{and}\ w_i\geq0\}$. | contribution 0.98 | 0.93 | 0.33 | asserted 1.00 |
| s1 | 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. | method 0.99 | 0.92 | 0.06 | asserted 0.98 |
| s2 | Moreover, proving rigorous convergence results in this formulation leads inherently to tools from information theory (e.g., cross-entropy and KL divergence). | interpretation 0.55 | 0.78 | 0.07 | asserted 0.99 |
| s3 | Each iteration of the Cauchy-Simplex consists of simple operations, making it well-suited for high-dimensional problems. | method 0.35 | 0.65 | 0.07 | asserted 0.95 |
| s4 | In continuous time, we prove that $f(x_T)-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. | result 0.99 | 0.94 | 0.27 | asserted 1.00 |
| s5 | Numerical experiments of projection onto convex hulls show faster convergence than similar algorithms. | result 1.00 | 0.92 | 0.10 | asserted 1.00 |
| s6 | 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. | contribution 0.54 | 0.95 | 0.19 | asserted 1.00 |
What was examined, and what was not
- arXiv listing abstract v2
- full text
- figures and tables
- references and citing sentences
- relations to other papers
- P abstract
- S sections
- T body sentences
- C citations
- R cross-paper relations
The paper
Original abstract
We propose a new iteration scheme, the Cauchy-Simplex, to optimize convex problems over the probability simplex $\{w\in\mathbb{R}^n\ |\ \sum_i w_i=1\ \textrm{and}\ w_i\geq0\}$. 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(x_T)-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.
Human review
How the literature uses it
2 arXiv papers cite this in 4 sentences
Papers citing it · 1 sentence without a confident label
Uses its method or tool 1 paper
-
These algorithms are either direct solves (SLSQP [ref] , the standard projected gradient descent (PGD), Cauchy [ref] , and SOCP [ref] and [ref] ), or LP-type algorithms (Clarkson [ref] and Seidel [ref] ).
Minimal intersection radius for $n$ growing, non-homogeneous ellipsoids in $\mathbb{R}^d$ · Introduction · 1.00
Discussion
Know something about this paper? Leave a comment, or highlight any passage above to comment on it.