Beyond Online Balanced Descent: An Optimal Algorithm for Smoothed Online Optimization
Gautam Goel, Yiheng Lin, Haoyuan Sun, Adam Wierman
–Neural Information Processing Systems
Weproveanewlower bound onthe competitive ratio of any online algorithm in the setting where the costs aremstrongly convex and the movement costs are the squared`2 norm. This lower bound shows that no algorithm can achieveacompetitiveratio that iso(m 1/2) asmtendstozero.
Neural Information Processing Systems
Feb-13-2026, 06:40:52 GMT
- Country:
- Technology: