Drug delivery vehicles can improve the functional efficacy of existing antimicrobial therapies by improving biodistribution and targeting. A critical property of such nanomedicine formulations is their ability to control the release kinetics of their payloads. The combination of (and interactions between) polymer, drug, and nanoparticle properties gives rise to nonlinear behavioral relationships and a large data space. These factors complicate both first-principles modeling and screening of nanomedicine formulations. Predictive analytics may offer a more efficient approach toward rational design of nanomedicines by identifying key descriptors and correlating them to nanoparticle release behavior. In this work, antibiotic release kinetics data were generated from polyanhydride nanoparticle formulations with varying copolymer compositions, encapsulated drug type, and drug loading. Four antibiotics, doxycycline, rifampicin, chloramphenicol, and pyrazinamide, were used. Linear manifold learning methods were used to relate drug release properties with polymer, drug, and nanoparticle properties, and key descriptors were identified that are highly correlated with release properties. However, these linear methods could not predict release behavior. Non-linear multivariate modeling based on graph theory was then used to deconvolute the governing relationships between these properties, and predictive models were generated to rapidly screen lead nanomedicine formulations with desirable release properties with minimal nanoparticle characterization. Release kinetics predictions of two drugs containing atoms not included in the model showed good agreement with experimental results, validating the model and indicating its potential to virtually explore new polymer and drug pairs not included in training data set. The models were shown to be robust after inclusion of these new formulations in that the new inclusions did not significantly change model regression. This approach provides the first steps towards development of a framework that can be used to rationally design nanomedicine formulations by selecting the appropriate carrier for a drug payload to program desirable release kinetics.