  Vertical federated learning (VFL) has attracted greater and greater interest
since it enables multiple parties possessing non-overlapping features to
strengthen their machine learning models without disclosing their private data
and model parameters. Similar to other machine learning algorithms, VFL faces
demands and challenges of fairness, i.e., the learned model may be unfairly
discriminatory over some groups with sensitive attributes. To tackle this
problem, we propose a fair VFL framework in this work. First, we systematically
formulate the problem of training fair models in VFL, where the learning task
is modelled as a constrained optimization problem. To solve it in a federated
and privacy-preserving manner, we consider the equivalent dual form of the
problem and develop an asynchronous gradient coordinate-descent ascent
algorithm, where some active data parties perform multiple parallelized local
updates per communication round to effectively reduce the number of
communication rounds. The messages that the server sends to passive parties are
deliberately designed such that the information necessary for local updates is
released without intruding on the privacy of data and sensitive attributes. We
rigorously study the convergence of the algorithm when applied to general
nonconvex-concave min-max problems. We prove that the algorithm finds a
$\delta$-stationary point of the dual objective in $\mathcal{O}(\delta^{-4})$
communication rounds under mild conditions. Finally, the extensive experiments
on three benchmark datasets demonstrate the superior performance of our method
in training fair models.
