We consider making outputs of the greedy algorithm for monotone submodular function maximization differentiable w.r.t. parameters of objective functions  . Due to the non-continuous behavior of the algorithm, we must use some smoothing methods. Our contribution is a theoretically guaranteed and widely applicable smoothing framework based on randomization. We prove that our smoothed greedy algorithm almost recovers original approximation guarantees in expectation for the cases of cardinality and \kappa-extensible system constrains. We also show that unbiased gradient estimators of any expected output-dependent quantities can be efficiently obtained by sampling outputs. We confirm the utility and effectiveness of our framework by applying it to sensitivity analysis of the greedy algorithm and decision-focused learning of parameterized submodular models .
We consider making outputs of the greedy algorithm for monotone submodular function maximization differentiable w.r.t. parameters of objective functions ; this is motivated by many applications, e.g., sensitivity analysis and end-to-end learning . Our contribution is a theoretically guaranteed and widely applicable smoothing framework based on randomization. We prove that our smoothed greedy algorithm almost recovers original approximation guarantees in expectation for the cases of cardinality and \kappa-extensible system constrains. We also show how to efficiently compute unbiased gradient estimators of any expected output-dependent quantities by sampling outputs. We demonstrate the utility and effectiveness of our framework by applying it to various situations including the aforementioned ones .
A
; this is motivated by many applications, e.g., sensitivity analysis and end-to-end learning
D
Due to the non-continuous behavior of the algorithm, we must use some smoothing methods.
R
that
how to efficiently compute
D
can be efficiently obtained
R
confirm
demonstrate
R
sensitivity analysis of the greedy algorithm and decision-focused learning of parameterized submodular models
various situations including the aforementioned ones