From Linear to Linearizable Optimization: A Novel Framework with Applications to Stationary and Non-stationary DR-submodular Optimization

arXiv:2405.00065 · math.OC, cs.CC, cs.LG, stat.ML · Submitted 2024-04-27 · Read on arXiv

math.OC, cs.CC, cs.LG, stat.ML

Submitted: 2024-04-27

Updated: 2026-09-13

Comments: Revised version of the paper published at the 38th Conference on Neural Information Processing Systems (NeurIPS 2024)

License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/

Terminology

• Regret — 79× in this paper · explained in 3 episodes
• Improved Ader — 7× in this paper
• Generalization — 4× in this paper · explained in 13 episodes
• Separation Oracles — 3× in this paper
• Loss Function — 2× in this paper · explained in 2 episodes
• Reward Function — 2× in this paper · explained in 2 episodes
• Sample Complexity — 1× in this paper · explained in 15 episodes
• Unified Framework — 1× in this paper · explained in 5 episodes

Sources

• Continuous Non-monotone DR-submodular Maximization with Down-closed Convex Constraint
• Non-Smooth, H\"older-Smooth, and Robust Submodular Maximization
• Improved Projection-free Online Continuous Submodular Maximization
• A Unified Framework for Analyzing Meta-algorithms in Online Convex Optimization
• Boosting Gradient Ascent for Continuous DR-submodular Maximization

Related papers

• Lions and Muons: Optimization via Stochastic Frank-Wolfe under Heavy-Tailed Noise
• Adam-HNAG: A Convergent Reformulation of Adam with Accelerated Rate
• Incremental Learning in Mirror Flows
• Online Control via Counterfactual Tracking
• Asynchronous Replanning in Two Population Linear Quadratic Mean Field Games: Information Requirements and Stability
• Petrov-Galerkin operator inference with application to stability-encouraging identification