Uniform Generalization Bound on Time and Inverse Temperature for Gradient Descent Algorithm and its Application to Analysis of Simulated Annealing
In this paper, we propose a novel uniform generalization bound on the time
and inverse temperature for stochastic gradient Langevin dynamics (SGLD) in a
non-convex setting. While previous works derive their generalization bounds by
uniform stability, we use Rademacher complexity to make our generalization
bound independent of the time and inverse temperature. Using Rademacher
complexity, we can reduce the problem to derive a generalization bound on the
whole space to that on a bounded region and therefore can remove the effect of
the time and inverse temperature from our generalization bound. As an
application of our generalization bound, an evaluation on the effectiveness of
the simulated annealing in a non-convex setting is also described. For the
sample size $n$ and time $s$, we derive evaluations with orders $\sqrt{n^{-1}
\log (n+1)}$ and $|(\log)^4(s)|^{-1}$, respectively. Here, $(\log)^4$ denotes
the $4$ times composition of the logarithmic function.