Appreciating music is cognitively demanding: listeners must learn to divide a continuous space of sound into culturally defined, discrete categories, and maintain a high degree of accuracy in their representations of those sounds. Here, we present a formal analysis of pitch category learning that reveals the trade-offs associated with learning the relative pitch categories that make music possible. Consistent with this, an empirical study reveals how under normal circumstances, people’s ability to represent absolute frequency information is lost as a consequence of the learning processes that facilitate relative pitch acquisition, a finding which may help explain the rarity of absolute pitch among the general population. Understanding the contradictory computational demands of conceptual and perceptual learning can inform the design of musical training and may offer insight into the development of phonological categories in language.