The quantum Fisher information (QFI) is a fundamental quantity of interest in many areas from quantum metrology to quantum information theory. It can in particular be used as a witness to establish the degree of multiparticle entanglement in quantum many-body systems. In this work, we use polynomials of the density matrix to construct monotonically increasing lower bounds that converge to the QFI. Using randomized measurements we propose a protocol to accurately estimate these lower bounds in state-of-the-art quantum technological platforms. We estimate the number of measurements needed to achieve a given accuracy and confidence level in the bounds, and present two examples of applications of the method in quantum systems made of coupled qubits and collective spins.