Proving Expected Sensitivity of Probabilistic Programs with Randomized Execution Time
share
The notion of program sensitivity (aka Lipschitz continuity) specifies that changes in the program input result in proportional changes to the program output. For probabilistic programs the notion is naturally extended to expected sensitivity. Previous approach develops a nice relational program logic framework for expected sensitivity of probabilistic while loops, where the number of iterations is fixed and bounded. In this work we present a sound approach for sensitivity analysis of probabilistic while loops, where the number of iterations is not fixed, but is randomized and only the expected number of iterations is finite. We demonstrate the effectiveness of our approach on several classical examples, e.g., mini-roulette and regularized stochastic gradient descent algorithm.
READ FULL TEXT