Research map / Bandits and online learning / Online convex optimization and games
From Linear to Linearizable Optimization: A Novel Framework with Applications to Stationary and Non-stationary 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.
Introduces upper-linearizable/quadratizable function classes and a meta-algorithm (OMBQ) that converts linear/quadratic online maximization algorithms into methods for up-concave/DR-submodular maximization, plus feedback-conversion meta-algorithms, yielding projection-free static, dynamic and adaptive regret bounds.
Problem
Online and offline maximization of adversarial γ-weakly up-concave (generalizing concave and DR-submodular) functions under different feedback types (first/zeroth order, full-information/semi-bandit/bandit), monotone/non-monotone settings, and static, dynamic and adaptive regret notions.
Approach
Define upper-quadratizable functions, i.e. functions upper-bounded by a linear/quadratic surrogate built from a gradient-like query, so any linear/quadratic online maximizer (e.g. projection-free SO-OGD with separation oracles) can be lifted to these classes via a query-transforming meta-algorithm, combined with boosting-based query oracles and random-permutation blocking.
Key results
- Projection-free static regret improved over prior SOTA in all 18 cases of Table 1 for online up-concave maximization using SO-OGD as base.
- First algorithms with dynamic and adaptive regret guarantees for online DR-submodular / up-concave maximization (Tables 3).
- Offline projection-free results improve sample complexity in 6 cases of Table 2 (e.g. O(1/eps^2) for monotone general convex sets and non-monotone case).
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Apply the linearizable/quadratizable framework with SO-OGD to online up-concave maximization | Projection-free online DR-submodular maximization · Online up-concave maximization, Table 1 cases | static-regret guarantee | Helped |
| Apply the framework to obtain offline algorithms from SO-OGD | Projection-free offline up-concave maximization · Offline up-concave maximization, Table 2 cases | regret guarantee | Helped |
| Apply the framework to SO-OGD adaptive-regret guarantees | Online DR-submodular maximization · Non-stationary up-concave maximization, Table 3 cases | adaptive regret | Helped |
| Apply the framework to Improved Ader dynamic-regret guarantees | Online DR-submodular maximization · Non-stationary up-concave maximization, Table 3 cases | dynamic regret | Helped |
| Use the framework for monotone γ-weakly functions with bounded curvature over general convex sets | Monotone up-concave maximization · General convex sets | approximation ratio | Helped |
Limitations
- Only three classes of up-concave functions are shown to be upper-quadratizable; other classes require new proofs.
- Some improvements rely on results requiring smoothness or differentiability assumptions in prior work; the paper claims fewer assumptions but some cases still need Lipschitz assumptions.
- Results for the Improved Ader variant use projection-based methods, so the dynamic-regret results are not projection-free.
Experimental setup
Metrics: static regret dynamic regret adaptive regret sample complexity approximation ratio
Baselines: SO-OGD Meta-Frank-Wolfe Boosting-based DR-submodular methods (Zhang et al.) Online gradient ascent based methods Ader
Builds on: Optimization by quadratization (Hazan and Minasyan / Pedramfar et al. FOTZO/STB Meta-Frank-Wolfe with random permutations boosting for DR-submodular maximization SO-OGD Improved Ader
Closest papers by meaning
- Upper-Linearizability of Online Non-Monotone DR-Submodular Maximization over Down-Closed Convex Sets (ICML 2026 · similarity 0.94)
- Online Non-Monotone DR-Submodular Maximization (AAAI 2021 · similarity 0.91)
- Gradient Methods for Online DR-Submodular Maximization with Stochastic Long-Term Constraints (NeurIPS 2024 · similarity 0.91)
- Nearly Minimax Optimal Submodular Maximization with Bandit Feedback (NeurIPS 2024 · similarity 0.91)
- Online Submodular Maximization via Online Convex Optimization (AAAI 2024 · similarity 0.91)
- A Reduction from Delayed to Immediate Feedback for Online Convex Optimization with Improved Guarantees (NeurIPS 2026 · similarity 0.89)
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.