Jets produced in high-energy heavy-ion collisions are modified compared to those in proton-proton collisions due to their interaction with the deconfined, strongly-coupled quark-gluon plasma (QGP). In this work, we employ machine learning techniques to identify important features that distinguish jets produced in heavy-ion collisions from jets produced in proton-proton collisions. We formulate the problem using binary classification and focus on leveraging machine learning in ways that inform theoretical calculations of jet modification: (i) we quantify the information content in terms of Infrared Collinear (IRC)-safety and in terms of hard vs. soft emissions, (ii) we identify optimally discriminating observables that are in principle calculable in perturbative QCD, and (iii) we assess the information loss due to the heavy-ion underlying event and background subtraction algorithms. We illustrate our methodology using Monte Carlo event generators, where we find that important information about jet quenching is contained not only in hard splittings but also in soft emissions and IRC-unsafe physics inside the jet. This information appears to be significantly reduced by the presence of the underlying event. We discuss the implications of this for the prospect of using jet quenching to extract properties of the QGP. Since the training labels are exactly known, this methodology can be used directly on experimental data without reliance on modeling. We outline a proposal for how such an experimental analysis can be carried out, and how it can guide future measurements.