Decentralized Optimization with Coupled Constraints
Authors: Demyan Yarmoshik, Alexander Rogozin, Nikita Kiselev, Daniil Dorin, Alexander Gasnikov, Dmitry Kovalev
ICLR 2025 | Venue PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Experimental | In this section we perform numerical experiments on a synthetic linear regression problem with ℓ2-regularization: min x1,...,xn Rdi 2 Cixi di 2 2 + θ i=1 (Aixi bi) = 0, (22) where we randomly generate matrices Ci Rdi di, Ai Rm di and vectors di Rdi, bi Rm from the standard normal distribution. Local variables xi Rdi have the same dimension di, equal for all devices. Regularization parameter θ is 10−3. In the Fig. 1 we demonstrate the performance of the our method on the problem, that has the following parameters: κf = 3140, κA = 27, κW = 89. There we use Erd os Rényi graph topology with n = 20 nodes. Local variables dimension is di = 3 and number of linear constraints is m = 10. We compare performance of Algorithm 2 with Tracking ADMM algorithm Falsone et al. (2020) and DPMM algorithm Gong and Zhang (2023). |
| Researcher Affiliation | Collaboration | Demyan Yarmoshik MIPT; Research Center for Artificial Intelligence, Innopolis University, Innopolis, Russia EMAIL Alexander Rogozin MIPT; Skoltech EMAIL Nikita Kiselev Research Center for Artificial Intelligence, Innopolis University, Innopolis, Russia; MIPT EMAIL Daniil Dorin MIPT EMAIL Alexander Gasnikov Research Center for Artificial Intelligence, Innopolis University, Innopolis, Russia; MIPT; Skoltech EMAIL Dmitry Kovalev Yandex Research EMAIL |
| Pseudocode | Yes | Algorithm 1 APAPC 1: Parameters: u0 U η, θ, α > 0, τ (0, 1) 2: Set u0 f = u0, z0 = 0 U 3: for k = 0, 1, 2, . . . do 4: uk g := τuk + (1 τ)uk f 5: uk+ 1 2 := (1 + ηα) 1(uk η( G(uk g) αuk g + zk)) 6: zk+1 := zk + θK (Kuk+ 1 2 b ) 7: uk+1 := (1 + ηα) 1(uk η( G(uk g) αuk g + zk+1)) 8: uk+1 f := uk g + 2τ 2 τ (uk+1 uk) 9: end for |
| Open Source Code | No | No explicit statement regarding the release of source code or a link to a code repository was found in the paper. |
| Open Datasets | Yes | VFL linear regression on real data. Now we return to the problem, that we have announced in the introduction section. We apply VFL in the linear regression problem: ℓis a typical mean squared loss Published as a conference paper at ICLR 2025 function, that is ℓ(z, l) = 1 2 z l 2 2, and ri are ℓ2-regularizers, i.e. ri(xi) = λ xi 2 2. To adapt this from (2) to (1), we redefine x1 := x1 z and x2 := x2, . . . , xn := xn. Thus, we can derive constraints matrices as in the (1): A1 = (F1 I) , A1x1 = F1w1 z, (23) Ai = Fi, i = 2, . . . , n, i=1 Fiwi z. (24) For numerical simulation, we use mushrooms dataset from Lib SVM library Chang and Lin (2011). |
| Dataset Splits | No | We split m = 100 samples subset vertically between n = 7 devices. Regularization parameter λ = 10−2. The results are in the Fig. 2. This specifies how the samples are distributed among devices but does not provide information about training, validation, or test splits. |
| Hardware Specification | Yes | The experiments were run on CPU Intel(R) Core(TM) i9-7980XE, with 62.5 GB RAM. |
| Software Dependencies | No | No specific software dependencies with version numbers were mentioned in the paper. |
| Experiment Setup | Yes | Regularization parameter θ is 10−3. In the Fig. 1 we demonstrate the performance of the our method on the problem, that has the following parameters: κf = 3140, κA = 27, κW = 89. There we use Erd os Rényi graph topology with n = 20 nodes. Local variables dimension is di = 3 and number of linear constraints is m = 10. We compare performance of Algorithm 2 with Tracking ADMM algorithm Falsone et al. (2020) and DPMM algorithm Gong and Zhang (2023). For numerical simulation, we use mushrooms dataset from Lib SVM library Chang and Lin (2011). We split m = 100 samples subset vertically between n = 7 devices. Regularization parameter λ = 10−2. |