Scheduling Algorithms for the Optimization of Distributed Machine Learning Models on Heterogeneous Resources  

Será defendida no dia 7 de agosto de 2026, às 10:00 horas, na sala 310 do Instituto de Computação e por videoconferência, a Tese de Doutorado intitulada “Scheduling Algorithms for the Optimization of Distributed Machine Learning Models on Heterogeneous Resources”, do candidato ao título de Doutor em Computação – Alan Lira Nunes.

Link para defesa: https://rendez-vous.renater.fr/private/PhD_Thesis_Defense_LIRA_NUNES__ulmen8swtnrj_a10ee6-e7850c-77413c

Resumo:

O Aprendizado Federado (Federated Learning, FL) permite que múltiplos clientes treinem colaborativamente modelos de aprendizado de máquina sem compartilhar seus dados brutos. No entanto, o FL cross-device permanece desafiador na prática, pois os clientes diferem em capacidade computacional, qualidade de comunicação, energia disponível, distribuições locais de dados e confiabilidade. No FL síncrono, essas diferenças afetam a eficiência do sistema e o desempenho do aprendizado: clientes lentos, com restrições de energia ou pouco representativos podem atrasar o treinamento, aumentar o consumo de recursos ou degradar a convergência. A maioria das estratégias existentes decide apenas se um cliente participa de uma rodada de comunicação, enquanto clientes selecionados geralmente treinam o modelo sobre todos os seus dados locais, limitando a adaptação da carga por cliente. Esta tese aborda a seleção de clientes no FL síncrono cross-device sob a perspectiva do escalonamento de tarefas. Os clientes são modelados como recursos heterogêneos, e a carga de uma rodada é decomposta em tarefas correspondentes a subconjuntos de dados locais. Assim, o servidor pode decidir quais clientes participam e quantos dados cada um deve processar. Essa formulação permite uma alocação fina da carga sobre recursos heterogêneos e possibilita a otimização conjunta de objetivos relacionados ao sistema e ao aprendizado. Esta tese propõe inicialmente MEC e ECMTC, dois algoritmos ótimos de escalonamento para alocação de carga considerando tempo e energia. MEC minimiza primeiro a duração da rodada e depois o consumo de energia, enquanto ECMTC minimiza primeiro o consumo de energia e depois a duração da rodada sob restrição de tempo. Esses algoritmos se baseiam em programação dinâmica e fornecem escalonamentos ótimos para suas respectivas ordens de objetivos. A tese introduz então o MetaCS-FL, um framework baseado em meta-heurística que estende essa perspectiva para um cenário multiobjetivo mais abrangente. Além do tempo de execução e da energia, o MetaCS-FL considera a utilidade do modelo, a qualidade da distribuição de classes, a diversidade de participação e a confiabilidade dos clientes. Ele usa o escalonamento produzido pelo ECMTC como solução inicial e refina as atribuições de tarefas aos clientes por meio da meta-heurística Large Neighborhood Search. O framework também integra resseleção orientada por eventos, reúso de soluções, controle de capacidade sensível à confiabilidade e privacidade diferencial, permitindo explorar informações ruidosas sobre distribuições de classes sem acessar distribuições exatas. Os métodos propostos são avaliados em classificação de imagens e textos, sob distribuições IID e não-IID, usando clientes heterogêneos emulados e comparações com FedAvg e estratégias do estado da arte. Nos cenários avaliados, o MetaCS-FL supera globalmente os demais algoritmos e alcança o melhor compromisso entre tempo de treinamento, energia, velocidade de convergência e equidade. Sob disponibilidade estática, ele reduz o tempo total de treinamento e o consumo de energia ao atingir a acurácia-alvo em menos rodadas, sem concentrar a carga em poucos clientes. A variante privada permanece próxima da versão não privada, indicando que a divulgação ruidosa das distribuições preserva informações úteis para a seleção enquanto melhora a privacidade. Sob disponibilidade dinâmica, com clientes tardios ou intermitentes, o MetaCS-FL mantém desempenho superior ao adaptar as atribuições de carga conforme disponibilidade, conclusão e confiabilidade dos clientes.

Abstract:

Federated Learning (FL) enables multiple clients to collaboratively train machine learning models without sharing their raw data. However, practical cross-device FL remains challenging because clients differ in computational capacity, communication quality, available energy, local data distributions, and reliability. In synchronous FL, these differences affect system efficiency and learning performance: slow, energy-constrained, or poorly representative clients can delay training, increase resource consumption, or degrade convergence. Most existing strategies only decide whether a client participates in a communication round, while selected clients usually train the model on all their local data, limiting per-client workload adaptation. This thesis addresses client selection in synchronous cross-device FL from a task scheduling perspective. Clients are modeled as heterogeneous resources, and the workload of a round is decomposed into tasks corresponding to subsets of local data. Thus, the server can decide which clients participate and how much data each one should process. This formulation enables fine-grained workload allocation over heterogeneous resources and supports the joint optimization of system-level and learning-related objectives. This thesis first proposes MEC and ECMTC, two optimal scheduling algorithms for workload allocation considering time and energy. MEC first minimizes round duration and then energy consumption, whereas ECMTC first minimizes energy consumption and then round duration under a time constraint. These algorithms rely on dynamic programming and provide optimal schedules for their respective objective orderings. The thesis then introduces MetaCS-FL, a metaheuristic-based framework that extends this perspective to a broader multiobjective setting. Beyond execution time and energy, MetaCS-FL considers model utility, class-distribution quality, participation diversity, and client reliability. It uses the schedule produced by ECMTC as an initial solution and refines task assignments to clients through the Large Neighborhood Search metaheuristic. The framework also integrates event-driven reselection, solution reuse, reliability-aware capacity control, and differential privacy, allowing noisy information about class distributions to be exploited without accessing exact distributions. The proposed methods are evaluated in image and text classification, under IID and non-IID distributions, using heterogeneous emulated clients and comparisons with FedAvg and state-of-the-art strategies. In the evaluated scenarios, MetaCS-FL outperforms the other algorithms overall and achieves the best trade-off among training time, energy, convergence speed, and fairness. Under static availability, it reduces total training time and energy consumption while reaching the target accuracy in fewer rounds, without concentrating the workload on few clients. The private variant remains close to the non-private version, indicating that noisy disclosure of distributions preserves useful selection information while improving privacy. Under dynamic availability, with late-joining or intermittent clients, MetaCS-FL maintains superior performance by adapting workload assignments according to client availability, completion behavior, and reliability.

Banca  examinadora:

Profa. Lúcia Maria de Assumpção Drummond, UFF – Presidente

Profa. Maria Cristina Silva Boeres, UFF

Profa. Débora Christina Muchaluat Saade, UFRJ

Profa. Flávia Coimbra Delicato, UFF 

Prof. Laércio Lima Pilla, CNRS 

Prof. Shadi Ibrahim, Inria 

Prof. Alfredo Goldman Vel Lejbman, USP 

Prof. Valmir Carneiro Barbosa, UERJ 

Prof. César Augusto Fonticielha De Rose, PUCRS