Respective labels indicative of compression-related quality degradation for a set of media object tuples which meet a divergence criterion are obtained; each tuple comprises a reference media object and a pair of corresponding compressed media object versions. Pairs of training records for a machine learning model are generated using the labeled media object tuples and multiple perceptual quality algorithms, with each training record comprising respective perceived quality degradation scores generated by each of the multiple algorithms for a given compressed media object of a tuple. A machine learning model is trained, using the record pairs, to predict quality degradation scores for compressed media objects.