Extending the Standard Model (SM) by a $U(1)_{L_mu-L_tau}$ group gives potentially significant new contributions to $g_mu-2$, allows the construction of realistic neutrino mass matrices, incorporates violation of lepton universality violation, and offers an anomaly-free mediator for a Dark Matter (DM) sector. In a recent analysis we showed that published LHC searches are not very sensitive to this model. Here we apply several Machine Learning (ML) algorithms in order to distinguish this model from the SM using simulated LHC data. In particular, we optimize the $3mu$-signal, which has a considerably larger cross section than the $4mu$-signal. Furthermore, since the $2$-muon plus missing $E_T$ final state gets contributions from diagrams involving DM particles, we optimize it as well. We find greatly improved sensitivity, which already for $36$ fb$^{-1}$ of data exceeds the combination of published LHC and non-LHC results. We also emphasize the usefulness of Boosted Decision Trees which, unlike Neural Networks, easily allow to extract additional information from the data which directly connect to the theoretical model. The same scheme could be used to analyze other models.