Research map / Bandits and online learning / Online convex optimization and games
Unified Projection-Free Algorithms for Adversarial DR-Submodular Optimization
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.
Proposes a unified family of projection-free Frank-Wolfe algorithms for adversarial continuous DR-submodular maximization covering full-information, semi-bandit and bandit feedback, monotone and non-monotone objectives, and several constraint geometries.
Problem
Online adversarial continuous DR-submodular maximization under varied feedback (gradient/value, full-information/semi-bandit/bandit), monotone or non-monotone objectives, and different convex constraint sets, where prior projection-free methods lack sublinear alpha-regret in several cases.
Approach
Combines meta-actions (K online linear optimizers mimicking offline Frank-Wolfe), random permutations across blocks of functions, and a one-point smoothed gradient estimator with shrunk constraint sets, handling stochastic oracles without momentum/variance reduction to get improved alpha-regret bounds across cases.
Key results
- Achieves alpha-regret O(T^{2/3 - beta/3}) with T^beta queries for monotone and non-monotone full-information gradient feedback, improving prior bounds in most cases.
- Gives first sublinear alpha-regret for monotone functions over general convex sets with full-information value feedback and bandit feedback; state of the art among projection-free methods in 7 of 8 monotone cases.
- In experiments, GMFW(beta=1/2) performs best overall while using far fewer gradient queries and less computation than Meta baselines.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use unified projection-free Frank-Wolfe algorithms instead of prior projection-free methods | Adversarial non-monotone DR-submodular optimization · Non-monotone settings considered in Table 1 | α-regret bound: 2/3 - β/3 vs. 1 - β/3 | Helped |
| Use unified projection-free Frank-Wolfe algorithms instead of prior projection-free methods | Adversarial monotone DR-submodular optimization · 7 of 8 considered cases | α-regret bound | Helped |
| Use unified Frank-Wolfe rather than the prior method | Monotone DR-submodular optimization with origin-containing constraints and stochastic gradient feedback · Online stochastic optimization | α-regret: O(T^{3/4}) | No clear effect |
| Use unified Frank-Wolfe rather than the prior method | Non-monotone DR-submodular optimization with downward-closed constraints and stochastic gradient feedback · Online stochastic optimization | α-regret: O(T^{3/4}) | No clear effect |
| Use unified Frank-Wolfe rather than the prior method | DR-submodular optimization with stochastic bandit or semi-bandit feedback · Online stochastic optimization | α-regret | No clear effect |
| Use GMFW(β=1/2) instead of Meta baselines | Non-monotone quadratic maximization with downward-closed constraints · Empirical regret experiments | regret | Helped |
| Use GMFW(β=0) instead of Mono | Non-monotone quadratic maximization with downward-closed constraints · Empirical regret experiments | regret | Helped |
Surprising findings
- Bandit-type feedback with noisy stochastic value oracles can be handled without momentum or variance reduction while keeping the same regret order as deterministic settings.
Limitations
- For general convex sets with full-information gradient queries of T^{1/2} per round, regret matches but does not strictly improve prior O(sqrt(T)) result.
- Bounds assume bounded stochastic oracles, a stronger assumption than bounded variance used in some prior work.
- Experiments are limited to a single synthetic non-monotone quadratic setting with downward-closed sets.
Experimental setup
Datasets: synthetic online non-monotone quadratic maximization instances with randomly generated downward-closed constraints
Benchmarks: online non-monotone quadratic maximization (synthetic)
Metrics: alpha-regret cumulative regret run-time
Baselines: ODC Mono-Frank-Wolfe Meta-Frank-Wolfe Bandit-Frank-Wolfe boosting-based projection-free methods
Builds on: Meta-Frank-Wolfe Mono-Frank-Wolfe Bandit-Frank-Wolfe smoothing trick online vee-learning
Closest papers by meaning
- Projection-Free Online Optimization with Stochastic Gradient: From Convexity to Submodularity (ICML 2018 · similarity 0.91)
- Projection-Free Online Convex Optimization with Time-Varying Constraints (ICML 2024 · similarity 0.87)
- Gradient Methods for Online DR-Submodular Maximization with Stochastic Long-Term Constraints (NeurIPS 2024 · similarity 0.87)
- From Linear to Linearizable Optimization: A Novel Framework with Applications to Stationary and Non-stationary DR-submodular Optimization (NeurIPS 2024 · similarity 0.85)
- Parameter-free Algorithms for the Stochastically Extended Adversarial Model (NeurIPS 2025 · similarity 0.85)
- Faster Rates for Private Adversarial Bandits (ICML 2025 · similarity 0.85)
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.