Open Collections

Fan, Zhenan

University of British Columbia

The dual approach in mathematical optimization refers to a class of techniques for tackling a dual problem that arises from the original problem. Numerous notable improvements in strengthening the dual approach have been promoted in the last two decades because of its superior performance for many large-scale optimization problems. In this thesis, we investigate and extend the dual approach to two classes of optimization problems: structured optimization, whose solutions exhibit specific structures, and federated learning, which aims to collaboratively learn a model from decentralized data sources. In the first part of this thesis, we characterize the dual correspondence in structured optimization. We further show that this dual correspondence allows us to develop efficient algorithms and design new models for structured optimization. In the second part of this thesis, we propose a dual approach to the federated optimization problem. We demonstrate theoretically and empirically that our approach enjoys better convergence guarantees than other primal-based approaches under specific scenarios. We also explore some application scenarios for structured optimization in federated learning. In the third part of this thesis, we study the problem of evaluating clients' contributions in federated learning. We propose fair and efficient contribution valuation metrics for both horizontal and vertical federated learning, where structured optimization plays a crucial role in our design.

Text

2022-10-13

Attribution-NonCommercial-NoDerivatives 4.0 International

http://hdl.handle.net/2429/82859

Computer Science

University of British Columbia

UBCV

http://creativecommons.org/licenses/by-nc-nd/4.0/