Cases abound in which nearly identical traits have appeared in distant species facing similar environments. These unmistakable examples of adaptive evolution offer opportunities to gain insight into their genetic origins and mechanisms through comparative analyses. Here, we present a novel comparative genomics approach to build genetic models that underlie the independent origins of convergent traits using evolutionary sparse learning. We test the hypothesis that common genes and sites are involved in the convergent evolution of two key traits: C4 photosynthesis in grasses and echolocation in mammals. Genetic models were highly predictive of independent cases of convergent evolution of C4 photosynthesis. These results support the involvement of sequence substitutions in many common genetic loci in the evolution of convergent traits studied. Genes contributing to genetic models for echolocation were highly enriched for functional categories related to hearing, sound perception, and deafness (P < 10-6); a pattern that has eluded previous efforts applying standard molecular evolutionary approaches. We conclude that phylogeny-informed machine learning naturally excludes apparent molecular convergences due to shared species history, enhances the signal-to-noise ratio for detecting molecular convergence, and empowers the discovery of common genetic bases of trait convergences.