Convex optimization over a probability simplex
This provides a new algorithm for optimization tasks in machine learning and online learning, such as prediction with expert advice and universal portfolios, but it is incremental as it builds on existing simplex optimization methods.
The paper tackles the problem of convex optimization over a probability simplex by proposing the Cauchy-Simplex method, which achieves an O(1/T) convergence rate for differentiable convex functions and demonstrates faster convergence in numerical experiments like projection onto convex hulls.
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.