  Vertical federated learning (VFL) attracts increasing attention due to the
emerging demands of multi-party collaborative modeling and concerns of privacy
leakage. In the real VFL applications, usually only one or partial parties hold
labels, which makes it challenging for all parties to collaboratively learn the
model without privacy leakage. Meanwhile, most existing VFL algorithms are
trapped in the synchronous computations, which leads to inefficiency in their
real-world applications. To address these challenging problems, we propose a
novel {\bf VF}L framework integrated with new {\bf b}ackward updating mechanism
and {\bf b}ilevel asynchronous parallel architecture (VF{${\textbf{B}}^2$}),
under which three new algorithms, including VF{${\textbf{B}}^2$}-SGD, -SVRG,
and -SAGA, are proposed. We derive the theoretical results of the convergence
rates of these three algorithms under both strongly convex and nonconvex
conditions. We also prove the security of VF{${\textbf{B}}^2$} under
semi-honest threat models. Extensive experiments on benchmark datasets
demonstrate that our algorithms are efficient, scalable and lossless.
