In this paper, we study the dynamics of contagious spreading processes taking place in complex contact networks. We specifically present a lower-bound on the decay rate of the number of nodes infected by a susceptible-infected-susceptible (SIS) stochastic spreading process. A precise quantification of this decay rate is crucial for designing efficient strategies to contain epidemic outbreaks. However, existing lower-bounds on the decay rate based on first-order mean-field approximations are often accompanied by a large error resulting in inefficient containment strategies. To overcome this deficiency, we derive a lower-bound based on a second-order moment-closure of the stochastic SIS processes. The proposed second-order bound is theoretically guaranteed to be tighter than existing first-order bounds. We also present various numerical simulations to illustrate how our lower-bound drastically improves the performance of existing first-order lower-bounds in practical scenarios, resulting in more efficient strategies for epidemic containment.