Exploring New Frontiers in Vertical Federated Learning: the Role of Saddle Point Reformulation

Aleksandr Beznosikov; Georgiy Kormakov; Alexander Grigorievskiy; Mikhail Rudakov; Ruslan Nazykov; Alexander Rogozin; Anton Vakhrushev; Andrey Savchenko

math.OCFeb 17, 2026

Exploring New Frontiers in Vertical Federated Learning: the Role of Saddle Point Reformulation

Authors: Aleksandr Beznosikov, Georgiy Kormakov, Alexander Grigorievskiy, Mikhail Rudakov, Ruslan Nazykov, Alexander Rogozin, Anton Vakhrushev, Andrey Savchenko,

Organizations: Basic Research of Artificial Intelligence Laboratory (BRAIn Lab) · Federated Learning Problems Laboratory · Innopolis University · Sber AI Lab ·

Abstract

The objective of Vertical Federated Learning (VFL) is to collectively train a model using features available on different devices while sharing the same users. This paper focuses on the saddle point reformulation of the VFL problem via the classical Lagrangian function. We first demonstrate how this formulation can be solved using deterministic methods. More importantly, we explore various stochastic modifications to adapt to practical scenarios, such as employing compression techniques for efficient information transmission, enabling partial participation for asynchronous communication, and utilizing coordinate selection for faster local computation. We show that the saddle point reformulation plays a key role and opens up possibilities to use mentioned extension that seem to be impossible in the standard minimization formulation. Convergence estimates are provided for each algorithm, demonstrating their effectiveness in addressing the VFL problem. Additionally, alternative reformulations are investigated, and numerical experiments are conducted to validate performance and effectiveness of the proposed approach.

Figures & tables

Panel of Figure 1 — Figure 1: Comparison of methods for solving the VFL problem in different formulations: minimization ( GD , Nesterov ) and saddle point ( ADMM , ExtraGradient /Algorithm 2 ). The comparison is made on LibSVM datasets mushrooms , a9a , w8a and MNIST .

Figure 2: Comparison of methods for solving the VFL problem in different formulations: minimization ( GD , Nesterov ) and saddle point ( ADMM , ExtraGradient /Algorithm 2 ). The comparison is made on CIFAR-10 dataset.

Appendix figures & tables8 assets

Supplementary material from the paper’s appendix.

Appendix

		Method	Iteration complexity	Local device cost of iteration	Local server cost of iteration	Communication cost of iteration
Formulation	( 4 )	Algorithm 2	$\mathcal{O}\left(\frac{1+\sqrt{\lambda_{\max}(A^{T}A)}+L_{\ell}+L_{r}}{\varepsilon}\right)$	$\mathcal{O}\left(ds\cdot\text{Cost}(\text{a.o.})+\text{Cost}(\nabla r)\right)$	$\mathcal{O}\left(s\cdot\text{Cost}(\text{a.o.})+\text{Cost}(\nabla\ell)\right)$	$\mathcal{O}\left(s\cdot\text{Send}(\text{1 coord.})\right)$
	( 6 )	Algorithm 4.1	$\mathcal{O}\left(\frac{1+\sqrt{\max_{i}\{\lambda_{\max}(A_{i}^{T}A_{i})\}}+nL_{\ell}+L_{r}}{\varepsilon}\right)$	$\mathcal{O}\left(ds\cdot\text{Cost}(\text{a.o.})+\text{Cost}(\nabla r)\right)$	$\mathcal{O}\left(s\cdot\text{Cost}(\text{a.o.})+\text{Cost}(\nabla\ell)\right)$	$\mathcal{O}\left(s\cdot\text{Send}(\text{1 coord.})\right)$
	( 7 )	Algorithm 4.2	$\mathcal{O}\left(\frac{1+\sqrt{\lambda_{\max}(A^{T}A)}+L_{\ell}+L_{r}}{\varepsilon}\right)$ (1)	$\mathcal{O}\left(ds\cdot\text{Cost}(\text{a.o.})+\text{Cost}(\nabla r)\right)$	$\mathcal{O}\left(s\cdot\text{Cost}(\text{a.o.})+\text{Cost}(\nabla\ell)\right)$	$\mathcal{O}\left(s\cdot\text{Send}(\text{1 coord.})\right)$
	( 7 )	ADMM [ Boyd et al., 2011 ; Lu and Yang, 2023 ]	$\mathcal{O}\left(\frac{1+\sqrt{\lambda_{\max}(A^{T}A)}}{\varepsilon}\right)$ (2)	$\mathcal{O}\left(\sqrt{\frac{1+\sqrt{\lambda_{\max}(A^{T}A)}+L_{r}}{e}}\right)\cdot\mathcal{O}\left(d^{2}\cdot\text{Cost}(\text{a.o.})+\text{Cost}(\nabla r)\right)+\mathcal{O}\left(ds\cdot\text{Cost}(\text{a.o.})\right)^{\text{{\color[rgb]{0,0,1}(3)}}}$	$\mathcal{O}\left(\sqrt{\frac{nL_{\ell}}{e}}\right)\cdot\mathcal{O}\left(s\cdot\text{Cost}(\text{a.o.})+\text{Cost}(\nabla\ell)\right)^{\text{{\color[rgb]{0,0,1}(3)}}}$	$\mathcal{O}\left(s\cdot\text{Send}(\text{1 coord.})\right)$
	( 8 )	Algorithm 4.3	$\mathcal{O}\left(\frac{1+\sqrt{\lambda_{\max}(A^{T}A)}+L_{\ell^{*}}+L_{r}}{\varepsilon}\right)$	$\mathcal{O}\left(ds\cdot\text{Cost}(\text{a.o.})+\text{Cost}(\nabla r)\right)$	$\mathcal{O}\left(s\cdot\text{Cost}(\text{a.o.})+\text{Cost}(\nabla\ell^{*})\right)$	$\mathcal{O}\left(s\cdot\text{Send}(\text{1 coord.})\right)$

Appendix

Table 1: Comparison of different saddle point reformulations of the VFL problem ( 2 ) and deterministic methods for solving these reformulations.

Panel of Figure 3 — Figure 3: Comparison of tuned methods for solving the VFL problem in different formulations: minimization ( GD , Nesterov ) and saddle point ( ADMM , ExtraGradient /Algorithm 2 ). The comparison is made on LibSVM datasets mushrooms , a9a , w8a and MNIST .

Panel of Figure 4 — Figure 4: Comparison of Algorithm 2 for solving the VFL problem with different stepsize tunings: according to Theorem 1 and Lemma 4 . The comparison is made on LibSVM datasets mushrooms , a9a , w8a and MNIST .

Panel of Figure 5 — Figure 5: Comparison of Algorithm 3.2 for solving the VFL problem ( 4 ). The comparison is made on LibSVM datasets mushrooms , a9a , w8a and MNIST . The compression operator $Q=\text{RandK}\%$ . The criterion for comparison is the number of full vectors transmitted. The top line reflects the work of methods on the basic problem, the bottom line solves the problem with the $\beta$ -trick (see disscusion after Corollary 1 ).

Panel of Figure 6 — Figure 6: Comparison of Algorithm 3.3 and Algorithm 3.2 for solving the VFL problem ( 4 ). The comparison is made on LibSVM datasets mushrooms , a9a , w8a and MNIST . The compression operators $C=\text{TopK}\%$ and $Q=\text{RandK}\%$ . The criterion for comparison is the number of full vectors transmitted. The top line reflects the work of methods on the basic problem, the bottom line solves the problem with the $\beta$ -trick (see disscusion after Corollary 1 ).

Panel of Figure 7 — Figure 7: Comparison of Algorithm 3.4 for solving the VFL problem ( 4 ). The comparison is made on LibSVM datasets mushrooms , a9a , w8a and MNIST . The criterion for comparison is the number of full vectors transmitted.

Panel of Figure 8 — Figure 8: Comparison of Algorithm 3.5 for solving the VFL problem ( 4 ) on LibSVM datasets mushrooms , a9a , w8a and MNIST . The criterion for comparison is the computational powers. The top line reflects the work of methods on the basic problem, the bottom line solves the problem with the $\beta$ -trick (see disscusion after Corollary 1 ).

Panel of Figure 9 — Figure 9: Comparison of Algorithm 3.6 with different noise levels for solving the VFL problem ( 4 ). The comparison is made on LibSVM datasets mushrooms , a9a , w8a and MNIST . The criterion for comparison is the number of iterations.

Federated Learning

Federated learning trains shared models across data holders without requiring them to pool their raw data.

See all 921 papers

Optimizing Server Placement for Vertical Federated Learning in Dynamic Edge/Fog Networks
May 10, 2026Su Wang, Mung Chiang, H. Vincent PoorEdge Computing Wireless Resource Allocation
Department of Electrical and Computer Engineering, Princeton University, Princeton, NJ, USA · Department of Electrical and Computer Engineering, Purdue University, West Lafayette, IN, USA
Federated learning with heavy-tailed gradient noise and communication noise: a variance-reduction based algorithm
Jun 21, 2026Shengchao Zhao, Yongchao LiuStochastic Optimization Nonconvex Stochastic Optimization
School of Mathematics, China University of Mining and Technology, Xuzhou, China · School of Mathematical Sciences, Dalian University of Technology, Dalian, China
Secure and Privacy-Preserving Vertical Federated Learning
Apr 15, 2026Shan Jin, Sai Rahul Rachuri, Yizhen Wang +2Privacy-Preserving Federated Learning Federated Learning
Visa Research

May 10, 2026J/K move · Enter open · S save

Optimizing Server Placement for Vertical Federated Learning in Dynamic Edge/Fog Networks

Su Wang, Mung Chiang, H. Vincent Poor

Department of Electrical and Computer Engineering, Princeton University, Princeton, NJ, USA · Department of Electrical and Computer Engineering, Purdue University, West Lafayette, IN, USA

Edge Computing Wireless Resource Allocation Federated Learning

Open paper AskPDF arXiv

We investigate the control and optimization of vertical federated learning (VFL), a class of distributed machine learning (ML) methods in which edge/fog devices contain separate data features, in dynamic edge/fog networks. Owing to heterogeneous data features and hardware across edge/fog networks, devices' contributions to VFL vary substantially, and, moreover, dynamic edge/fog networks can lead to the permanent exit or entry of select data features. In this setting, our proposed methodology, server controlled VFL in dynamic networks (SC-DN), first establishes the existence of a global first-order stationary point for every global round, and then leverages this result to jointly optimize ML model training and resource consumption based on four key control variables: (i) server placement, (ii) device-to-server transmit power, (iii) local device processor frequency, and (iv) local training iterations per global round. The resulting optimization formulation contains coupled variables as well as numerous forms of logarithmic constraints which we show is a mixed-integer signomial program, an NP-hard problem, and for which we develop a general solver. Finally, via experiments on both image and multi-modal datasets, we show that our methodology demonstrates superior classification/regression performance and resource consumption savings than even greedy methodologies.

Abstract

Federated Learning

Explore similar work

Optimizing Server Placement for Vertical Federated Learning in Dynamic Edge/Fog Networks

Federated learning with heavy-tailed gradient noise and communication noise: a variance-reduction based algorithm

Secure and Privacy-Preserving Vertical Federated Learning