  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.
