2021/11/10 by Zakaria Mhammedi, Mhammedi, Zakaria · 1 citation
Computer Science · Decision Sciences · Engineering · Mathematics · #Advanced Bandit Algorithms Research #Advanced Optimization Algorithms Research #FOS: Computer and information sciences #FOS: Mathematics #Machine Learning (cs.LG) #Optimization and Control (math.OC) #Sparse and Compressive Sensing Techniques #Stochastic Gradient Optimization Techniques
paper · pdf · doi:10.48550/arxiv.2111.05818
openalex publication_date 2021/11/10 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
In constrained convex optimization, existing methods based on the ellipsoid\nor cutting plane method do not scale well with the dimension of the ambient\nspace. Alternative approaches such as Projected Gradient Descent only provide a\ncomputational benefit for simple convex sets such as Euclidean balls, where\nEuclidean projections can be performed efficiently. For other sets, the cost of\nthe projections can be too high. To circumvent these issues, alternative\nmethods based on the famous Frank-Wolfe algorithm have been studied and used.\nSuch methods use a Linear Optimization Oracle at each iteration instead of\nEuclidean projections; the former can often be performed efficiently. Such\nmethods have also been extended to the online and stochastic optimization\nsettings. However, the Frank-Wolfe algorithm and its variants do not achieve\nthe optimal performance, in terms of regret or rate, for general convex sets.\nWhat is more, the Linear Optimization Oracle they use can still be\ncomputationally expensive in some cases. In this paper, we move away from\nFrank-Wolfe style algorithms and present a new reduction that turns any\nalgorithm A defined on a Euclidean ball (where projections are cheap) to an\nalgorithm on a constrained set C contained within the ball, without sacrificing\nthe performance of the original algorithm A by much. Our reduction requires O(T\nlog T) calls to a Membership Oracle on C after T rounds, and no linear\noptimization on C is needed. Using our reduction, we recover optimal regret\nbounds [resp. rates], in terms of the number of iterations, in online [resp.\nstochastic] convex optimization. Our guarantees are also useful in the offline\nconvex optimization setting when the dimension of the ambient space is large.\n