Portrait de Julien Pallage n'est pas disponible

Julien Pallage

julien.pallage@mila.quebec
Maîtrise recherche - Polytechnique Montréal
Superviseur⋅e principal⋅e
Antoine Lesage-Landry
Github

Publications

Online Dynamic Submodular Optimization
Antoine Lesage-Landry
Julien Pallage
We propose new algorithms with provable performance for online binary optimization subject to general constraints and in dynamic settings. W… (voir plus)e 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.
2023-06-19
ArXiv (prépublication)
doi.org
arxiv.org