2023/05/15 by James Chok, Chok, James, Geoffrey M. Vasil +1
Computer Science · Decision Sciences · Engineering · #65K10 #68W27 #68W40 #91G10 #97U40 #Advanced Bandit Algorithms Research #FOS: Computer and information sciences #FOS: Economics and business #FOS: Mathematics #Machine Learning (cs.LG) #Machine Learning (stat.ML) #Numerical Analysis (math.NA) #Optimization and Control (math.OC) #Portfolio Management (q-fin.PM) #Sparse and Compressive Sensing Techniques #Stochastic Gradient Optimization Techniques
paper · pdf · doi:10.48550/arxiv.2305.09046
openalex publication_date 2023/05/15 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
We propose a new iteration scheme, the Cauchy-Simplex, to optimize convex problems over the probability simplex \w∈ℝn | ∑i 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.