Submodular Maximization and Online Linearizable Optimization
Principal Investigator: Vaneet Aggarwal
Many selection problems have "diminishing returns": the tenth sensor, ad, or server adds less value than the first. Such problems are called submodular. Examples include placing sensors, choosing which users to seed for a viral campaign, allocating budgets, and configuring networks. They are hard to solve exactly, and in practice the data often arrives over time, so decisions must be made before the full picture is known.
This project develops fast algorithms for these problems, with guarantees on how close they come to the best possible answer. That guarantee is called the "approximation ratio" when the data is known in advance, and "regret", the gap to the best fixed decision in hindsight, when decisions are made online. Our outcomes include:
- A single framework that turns a broad class of hard optimization problems into simpler linear ones. We call these problems "linearizable" (the continuous version is "DR-submodular"). The framework yields algorithms for many settings at once.
- The first online algorithms that match the best known offline guarantees for a key family of these problems.
- Algorithms that need only the final outcome of each choice ("bandit feedback"), not a full description of the objective.
- Fast methods that avoid expensive projection steps and can run across many cooperating machines.
- Methods that handle changing constraints, noisy data, and preference (comparison) feedback.
- Social-network applications: influence maximization with partial incentives and fractional budgets.
Representative Publications
Guanyu Nie, Mridul Agarwal, Abhishek Kumar Umrawal, Vaneet Aggarwal, and Christopher John Quinn, "An Explore-then-Commit Algorithm for Submodular Maximization Under Full-bandit Feedback," in Proc. UAI, Aug 2022.
Fares Fourati, Vaneet Aggarwal, Christopher Quinn, and Mohamed-Slim Alouini, "Randomized Greedy Learning for Non-monotone Stochastic Submodular Maximization Under Full-bandit Feedback," in Proc. AISTATS, Apr 2023.
Guanyu Nie, Yididiya Y Nadew, Yanhui Zhu, Vaneet Aggarwal, and Christopher John Quinn, "A Framework for Adapting Offline Algorithms to Solve Combinatorial Multi-Armed Bandit Problems with Bandit Feedback," in Proc. ICML, Jul 2023.
Guanyu Nie, Vaneet Aggarwal, and Christopher John Quinn, "Stochastic k-Submodular Bandits with Full Bandit Feedback," in Proc. AAMAS, May 2025.
Mohammad Pedramfar and Vaneet Aggarwal, "Stochastic Submodular Bandits with Delayed Composite Anonymous Bandit Feedback," IEEE Transactions on Artificial Intelligence, vol. 6, no. 7, pp. 1727-1735, July 2025.
Subham Pokhriyal, Shweta Jain, Vaneet Aggarwal, "Multi-Agent Combinatorial-Multi-Armed-Bandit framework for the Submodular Welfare Problem under Bandit Feedback," in Proc. AAMAS, May 2026.
Vaneet Aggarwal, "Adversarial Resilience of Poisson-Process Submodular Maximization over Matroids: From Robust Offline Optimization to Full-Bandit Learning," arXiv, Aug 2026.
Abhishek Kumar Umrawal, Christopher J. Quinn, and Vaneet Aggarwal, "A Community-Aware Framework for Social Influence Maximization," IEEE Transactions on Emerging Topics in Computational Intelligence (TETCI), vol. 7, no. 4, pp. 1253-1262, Aug. 2023.
Abhishek Kumar Umrawal, Vaneet Aggarwal, and Christopher J. Quinn, "Fractional Budget Allocation for Influence Maximization," IEEE Conference on Decision and Control (CDC), Dec 2023.
Mohammad Pedramfar, Christopher John Quinn, and Vaneet Aggarwal, "A Unified Approach for Maximizing Continuous DR-submodular Functions," in Proc. NeurIPS, Dec 2023.
Mohammad Pedramfar, Yididiya Y. Nadew, Christopher John Quinn, and Vaneet Aggarwal, "Unified Projection-Free Algorithms for Adversarial DR-Submodular Optimization," in Proc. ICLR, May 2024.
Mohammad Pedramfar and Vaneet Aggarwal, "From Linear to Linearizable Optimization: A Novel Framework with Applications to Stationary and Non-stationary DR-submodular Optimization," in Proc. NeurIPS, Dec 2024.
Guanyu Nie, Vaneet Aggarwal, and Christopher John Quinn, "Gradient Methods for Online DR-Submodular Maximization with Stochastic Long Term Constraints," in Proc. NeurIPS, Dec 2024.
Fares Fourati, Salma Kharrat, Vaneet Aggarwal, and Mohamed-Slim Alouini, "Every Call is Precious: Global Optimization of Black-Box Functions with Unknown Lipschitz Constants," in Proc. AISTATS, May 2025.
Mohammad Pedramfar, Christopher John Quinn, and Vaneet Aggarwal, "Uniform Wrappers: Bridging Concave to Quadratizable Functions in Online Optimization," in Proc. NeurIPS, Dec 2025.
Fares Fourati, Mohamed-Slim Alouini, and Vaneet Aggarwal, "ECPv2: Fast, Efficient, and Scalable Global Optimization of Lipschitz Functions," in Proc. AAAI, Jan 2026.
Yiyang Lu, Mohammad Pedramfar, and Vaneet Aggarwal, "Decentralized Projection-free Online Upper-Linearizable Optimization with Applications to DR-Submodular Optimization," Transactions on Machine Learning Research, Dec 2025.
Mohammad Pedramfar and Vaneet Aggarwal, "A Generalized Approach to Online Convex Optimization," in Proc. AAMAS, May 2026.
Hareshkumar Jadav, Ranveer Singh, Vaneet Aggarwal, "Stronger Approximation Guarantees for Non-Monotone γ-Weakly DR-Submodular Maximization," Transactions on Machine Learning Research, Aug 2026.
Abhishek Umrawal, Eliot Robson, Vaneet Aggarwal, and Christopher Quinn, "Maximizing the Spread of Influence through a Social Network using Partial Incentives," Journal of Artificial Intelligence Research, vol. 86, Jun 2026.
Yiyang Lu, Haresh Jadav, Mohammad Pedramfar, Ranveer Singh, and Vaneet Aggarwal, "Upper-Linearizability of Online Non-Monotone DR-Submodular Maximization over Down-Closed Convex Sets," in Proc. ICML, Jul 2026.
Mohammad Pedramfar and Vaneet Aggarwal, "γ -weakly θ-up-concavity: Linearizable Non-Convex Optimization with Applications to DR-Submodular and OSS Functions," in Proc. NeurIPS, Dec 2026.
Yiyang Lu, Mohammad Pedramfar, and Vaneet Aggarwal, "BAGEL: Projection-Free Algorithm for Adversarially Constrained Online Convex Optimization," Submitted to TMLR, Aug 2026 (under revision).
Vaneet Aggarwal, "Parameter-Free Dynamic Regret for Online Convex Optimization under Heavy-Tailed Noise," arXiv, Jul 2026.
Vaneet Aggarwal, "Sharp Minimax Regret for Infinite-Memory Logistic Prediction," arXiv, Aug 2026.
Yiyang Lu, Hareshkumar Jadav, Mohammad Pedramfar, Ranveer Singh, and Vaneet Aggarwal, "Online Convex Optimization with Dueling Feedback," arXiv, Aug 2026.
Yiyang Lu, Mohammad Pedramfar, and Vaneet Aggarwal, "Dec-BFTRL: Square-Root Regret for Decentralized Online Upper-Linearizable Optimization under Separation Access with Application to Continuous Submodular Maximization," arXiv, Aug 2026.
Vaneet Aggarwal, "Sharp Oracle-Regret Tradeoffs for Projection-Free Online Convex Optimization," arXiv, Oct 2026.
Vaneet Aggarwal, "Constrained Online Learning with Noisy Constraint Values," arXiv, Sept 2026.
Vaneet Aggarwal and Yiyang Lu, "Online Non-Monotone DR-Submodular Maximization Matching the Offline 0.401 Factor," arXiv, Sept 2026.
Vaneet Aggarwal, "Parameter-Free Interval-Dynamic Regret under Heavy-Tailed Noise," arXiv, Oct 2026.
Vaneet Aggarwal, "Geometry-Dependent Bounds for Online Non-Monotone DR-Submodular Maximization," arXiv, Oct 2026.
Vaneet Aggarwal, "Geometry-Dependent Approximation for Non-Monotone k-Submodular Maximization," arXiv, Oct 2026.
Mohammad Pedramfar, Rajiv Khanna, Christopher John Quinn, and Vaneet Aggarwal, "Tilted Convexity and an Exact Offline-Online Separation," arXiv, Nov 2026.
Vaneet Aggarwal and Donglei Du, "0.4633-Approximation for Online and Offline Non-Monotone DR-Submodular Maximization," arXiv, Oct 2026.
Keywords: adversarial constraints, DR-submodular, influence maximization, k-submodular, online convex optimization, projection-free, regret, submodular bandits, submodular maximization

