Research map / Bandits and online learning / Online convex optimization and games
Online Composite Optimization Between Stochastic and Adversarial Environments
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Extends the stochastically extended adversarial (SEA) model to composite (regularized) online optimization, showing optimistic composite mirror descent (OptCMD) matches SEA bounds and proposing a three-layer universal algorithm that adapts to convex, strongly convex, and exp-concave losses.
Problem
Online composite optimization where losses are a fixed non-smooth convex regularizer plus a time-varying function that may be stochastic, adversarial, or intermediate; existing SEA analyses ignore the regularizer and universal methods assume smoothness of the full composite loss.
Approach
Reanalyze optimistic composite mirror descent (OptCMD) under the SEA model, using cumulative stochastic variance and adversarial variation as regret measures, and build a universal meta-expert algorithm that incorporates the fixed regularizer into the meta-losses and optimisms so that cancellation removes the non-smooth term.
Key results
- OptCMD attains O(sqrt(sigma^2_{1:T}) + sqrt(Sigma^2_{1:T})) regret for smooth convex composite losses, matching SEA bounds without regularizer.
- For smooth strongly convex losses, O((sigma^2_max + Sigma^2_max) log(sigma^2_{1:T}+Sigma^2_{1:T})) regret; for exp-concave, O(d log(sigma^2_{1:T}+Sigma^2_{1:T})).
- Universal algorithm achieves these three bounds simultaneously without knowing function type; experiments on mushroom show OptCMD and USC-SEA lower loss than OGD, COMID, Optimistic-OMD, ONS, ProxONS.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use Mt+1 = ∇ft(ˆxt+1) with the original general-convex configuration instead of Mt+1 = ∇ft(xt) (ablation) | OptCMD · Composite SEA, general convex | expected regret bound: O(√σ²₁:T + √Σ²₁:T) -> O(√˜σ²₁:T + √Σ²₁:T) | Hurt |
| Use Mt+1 = ∇ft(ˆxt+1) and the original strongly-convex configuration instead of Mt+1 = ∇ft(xt) (ablation) | OptCMD · Composite SEA, strongly convex | expected regret bound: O(λ⁻¹(σ²max + Σ²max) log(σ²₁:T + Σ²₁:T)) -> O((G²/λ) log(˜σ²₁:T + Σ²₁:T)) | Hurt |
| Use Mt+1 = ∇ft(ˆxt+1) and the original strongly-convex learning rate (ablation) | OptCMD · Composite SEA, strongly convex | expected regret bound: O((σ²max + Σ²max)/λ) -> O(G²/λ) | Hurt |
| Use USC-SEA to adapt to function type without prior knowledge, using OptCMD experts | Composite SEA online optimization · Composite SEA, general convex | expected regret bound: ˜O(√σ²₁:T + √Σ²₁:T) | Helped |
| Use USC-SEA to adapt to function type without prior knowledge, using OptCMD experts | Composite SEA online optimization · Composite SEA, strongly convex | expected regret bound: O((σ²max+Σ²max) log(σ²₁:T +Σ²₁:T)) | Helped |
| Use USC-SEA to adapt to function type without prior knowledge, using OptCMD experts | Composite SEA online optimization · Composite SEA, exp-concave | expected regret bound: O(d log(σ²₁:T +Σ²₁:T)) | Helped |
| Use OptCMD and USC-SEA rather than the baseline methods | Online classification on mushroom datasets · Mushroom, general convex | loss | Helped |
| Use OptCMD and USC-SEA rather than the baseline methods | Online classification on mushroom datasets · Mushroom, strongly convex | loss | Helped |
| Use OptCMD and USC-SEA rather than the baseline methods | Online classification on mushroom datasets · Mushroom, exp-concave | loss | Helped |
Surprising findings
- Scroccaro et al.'s natural choice of optimism leads to a worse dependence on a larger stochastic quantity (tilde sigma), which the authors fix by changing the optimism.
Limitations
- Relies on bounded domain and bounded gradient assumptions
- Universal algorithm has a three-layer structure that is complex to analyze and implement
- Assumes immediate feedback; delayed feedback not handled
Experimental setup
Datasets: mushroom (LIBSVM)
Benchmarks: mushroom (LIBSVM) online classification
Metrics: instantaneous loss cumulative loss average loss regret bound
Baselines: OGD COMID Optimistic-OMD ONS ProxONS
Builds on: OptCMD SEA model MsMwC Yan et al. 2023 universal SEA algorithm optimistic OMD
Closest papers by meaning
- Parameter-free Algorithms for the Stochastically Extended Adversarial Model (NeurIPS 2025 · similarity 0.91)
- Revisiting Projection-Free Online Learning with Time-Varying Constraints (AAAI 2025 · similarity 0.90)
- Gradient-Variation Online Learning under Generalized Smoothness (NeurIPS 2024 · similarity 0.89)
- Projection-Free Online Convex Optimization with Time-Varying Constraints (ICML 2024 · similarity 0.89)
- Stochastic Shortest Path with Sparse Adversarial Costs (NeurIPS 2025 · similarity 0.88)
- From Average Sensitivity to Small-Loss Regret Bounds under Random-Order Model (NeurIPS 2026 · similarity 0.88)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.