Optimistic Online Mirror Descent for Bridging Stochastic and Adversarial Online Convex Optimization
24. července 2023
Řečníci
Sijia Chen
Řečník · 0 sledujících
Wei-Wei Tu
Řečník · 0 sledujících
Lijun Zhang
Řečník · 0 sledujících
O prezentaci
Stochastically Extended Adversarial (SEA) model is introduced by Sachs et al. (2022) as an interpolation between stochastic and adversarial online convex optimization. Under the smoothness condition, they demonstrate that the expected regret of optimistic follow-the-regularized-leader (FTRL) depends on the cumulative stochastic variance σ_1:T^2 and the cumulative adversarial variation Σ_1:T^2 for convex functions. They also provide a slightly weaker bound based on the maximal stochastic variance σ_max^2 and the maximal adversarial variation Σ_max^2 for strongly convex functions. Inspired by their work, we investigate the theoretical guarantee of optimistic online mirror descent (OMD) for the SEA model. For convex and smooth functions, we obtain the same 𝒪(√(σ_1:T^2)+√(Σ_1:T^2)) regret bound, without the convexity requirement of individual functions. For strongly convex and smooth functions, we establish an 𝒪(min{log (σ_1:T^2+Σ_1:T^2), (σ_max^2 + Σ_max^2) log T}) bound, better than their 𝒪((σ_max^2 + Σ_max^2) log T) bound. For exp-concave and smooth functions, we achieve a new 𝒪(dlog(σ_1:T^2+Σ_1:T^2)) bound. Owing to the OMD framework, we can further extend our result to obtain dynamic regret guarantees, which are more favorable in non-stationary online scenarios. The attained results allow us to recover the excess risk bound of stochastic setting and the regret bound of adversarial setting, and derive new guarantees for many intermediate settings.Stochastically Extended Adversarial (SEA) model is introduced by Sachs et al. (2022) as an interpolation between stochastic and adversarial online convex optimization. Under the smoothness condition, they demonstrate that the expected regret of optimistic follow-the-regularized-leader (FTRL) depends on the cumulative stochastic variance σ_1:T^2 and the cumulative adversarial variation Σ_1:T^2 for convex functions. They also provide a slightly weaker bound based on the maximal stochastic variance…
Baví vás formát? Nechte SlidesLive zachytit svou akci!
Profesionální natáčení a streamování po celém světě.
Sdílení
Doporučená videa
Prezentace na podobné téma, kategorii nebo přednášejícího
Polyhedral Complex Extraction from ReLU Networks using Edge Subdivision
Zhlédnout později
Paper Spotlights
Zhlédnout později
Andrew Ilyas, …
RGE: A Repulsive Graph Rectification for Node Classification via Influence
Zhlédnout později
Jaeyun Song, …
Hierarchical Diffusion for Offline Decision Making
Zhlédnout později
Wenhao Li, …
Unsupervised Skill Discovery for Learning Shared Structures across Changing Environments
Zhlédnout později
