Online Convex Optimization
A core subfield of online learning in which, at each round, the learner selects a decision from a continuous convex set and suffers a convex loss, with the goal of minimizing cumulative regret. Unlike the discrete experts framework, OCO permits continuous values and assumes gradient information is available.
Timeline (last 90 days)
In a continuous convex action space, discretizing the action space and applying the discrete algorithm can yield Õ(md+k) regret, but the number of grid points required grows exponentially with the dimension d, making the algorithm infeasible in polynomial time.
Before this study, the best known polynomial-time algorithm for the online convex optimization problem of tracking a sequence of experts that switches k times had regret Õ(dk).
There is an essential separation between the information-theoretically optimal regret Õ(md+k) and the regret achievable in polynomial time; this gap is inherent to computational complexity rather than a shortcoming of algorithm design.
For practical algorithm design, when the dimension d is large and the number of switches k is non-negligible, accepting Õ(dk)-level regret or seeking additional structural assumptions may be a more pragmatic direction than relying on discretization or exact optimization.
All Facts (4)
In a continuous convex action space, discretizing the action space and applying the discrete algorithm can yield Õ(md+k) regret, but the number of grid points required grows exponentially with the dimension d, making the algorithm infeasible in polynomial time.
50%UnverifiedBefore this study, the best known polynomial-time algorithm for the online convex optimization problem of tracking a sequence of experts that switches k times had regret Õ(dk).
50%UnverifiedThere is an essential separation between the information-theoretically optimal regret Õ(md+k) and the regret achievable in polynomial time; this gap is inherent to computational complexity rather than a shortcoming of algorithm design.
50%UnverifiedFor practical algorithm design, when the dimension d is large and the number of switches k is non-negligible, accepting Õ(dk)-level regret or seeking additional structural assumptions may be a more pragmatic direction than relying on discretization or exact optimization.
50%