We introduce a method to lower bound an entropy-based measure of genuine multipartite entanglement via nonlinear entanglement witnesses. We show that some of these bounds are tight and explicitly work out their connection to a framework of nonlinear witnesses that were published recently. Furthermore, we provide a detailed analysis of these lower bounds in the context of other possible bounds and measures. In exemplary cases, we show that only a few local measurements are necessary to determine these lower bounds.
