# Online Dynamic Submodular Optimization

arXiv: https://arxiv.org/abs/2306.10835 · HTML: https://mlsanity.com/paper/2306.10835/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 12 of its 42 references that are in the map.
- First posted on arXiv 19 Jun 2023.

## Builds on (most cited first, 12 of 12)

- [Introduction to Online Convex Optimization](https://mlsanity.com/paper/1909.05207/) (2019)
- [pandapower - an Open Source Python Tool for Convenient Modeling, Analysis and Optimization of Electric Power Systems](https://mlsanity.com/paper/1709.06743/) (2017)
- [An Online Convex Optimization Approach to Dynamic Network Resource Allocation](https://mlsanity.com/paper/1701.03974/) (2017)
- [Bandit Convex Optimization for Scalable and Dynamic IoT Management](https://mlsanity.com/paper/1707.09060/) (2017)
- [Second-order Online Nonconvex Optimization](https://mlsanity.com/paper/2001.10114/) (2020)
- [Power Systems Without Fuel](https://mlsanity.com/paper/1506.04799/) (2015)
- [Online Stochastic Optimization of Networked Distributed Energy Resources](https://mlsanity.com/paper/1711.09953/) (2017)
- [Online Convex Optimization with Binary Constraints](https://mlsanity.com/paper/2005.02274/) (2020)
- [Setpoint Tracking with Partially Observed Loads](https://mlsanity.com/paper/1709.04077/) (2017)
- [Real-Time Feedback-Based Optimization of Distribution Grids: A Unified Approach](https://mlsanity.com/paper/1711.01627/) (2017)
- [Real-Time Minimization of Average Error in the Presence of Uncertainty and Convexification of Feasible Sets](https://mlsanity.com/paper/1612.07287/) (2016)
- [A Submodular Approach for Electricity Distribution Network Reconfiguration](https://mlsanity.com/paper/1711.03517/) (2017)

## Abstract (arXiv)

We propose new algorithms with provable performance for online binary optimization subject to general constraints and in dynamic settings. We consider the subset of problems in which the objective function is submodular. We propose the online submodular greedy algorithm (OSGA) which solves to optimality an approximation of the previous round loss function to avoid the NP-hardness of the original problem. We extend OSGA to a generic approximation function. We show that OSGA has a dynamic regret bound similar to the tightest bounds in online convex optimization with respect to the time horizon and the cumulative round optimum variation. For instances where no approximation exists or a computationally simpler implementation is desired, we design the online submodular projected gradient descent (OSPGD) by leveraging the Lova'sz extension. We obtain a regret bound that is akin to the conventional online gradient descent (OGD). Finally, we numerically test our algorithms in two power system applications: fast-timescale demand response and real-time distribution network reconfiguration.