Controlling Distributed Optimization from a Stochastic Oracle, by Adit Jain

Date 26 July 2024
Abstract: Distributed optimization is used extensively in areas like pricing optimization and federated learning. In a centralized distributed optimization setting, when the distributed setup (oracle) is stochastic, it becomes important to ensure that optimization happens in a robust fashion, for e.g. when the oracle is in a 'good' state. We model the problem of dynamically learning from a stochastic oracle as a Markov decision process (MDP), and control the stochastic gradient descent performed by the learner. Under structural assumptions on the cost and transition matrix, we show that the optimal policy of the MDP has a threshold structure. Exploiting the structural results, a stochastic approximation algorithm is proposed to efficiently search for the optimal policy. The framework and structural results are extended to multiple central learners by formulating a switching control game. We numerically show the efficacy of our proposed methods in performing covert optimization and ensuring group fairness in federated learning.