For a plurality of client computing devices of a federated learning system, obtain initial compressed embeddings, compressed by clustering, and including output of initial local models for a current minibatch, and initial cluster labels corresponding to the initial embeddings. Recreate an initial overall embedding based on the initial embeddings and the initial labels. At a server of the federated learning system, send a current version of a server model to each of the client computing devices; and obtain, from the client computing devices: updated compressed embeddings, compressed by clustering, and updated cluster labels corresponding to the updated embeddings. Based on local training by the plurality of clients with the overall embedding and the current server model, at the server, recreate an updated overall embedding based on the updated embeddings and the corresponding updated labels, and locally train the server model based on the updated overall embedding.