acceptodds
Under review as a conference paper at ICLR 2027

Distributed Nonconvex Learning under Coupling Constraints over Directed Networks

Abstract

Distributed learning is often formulated through consensus, yet many collaborative models are built from distinct local components that must satisfy global consistency relations rather than agree with one another. This becomes particularly challenging when the objectives are nonconvex, gradients are stochastic, and communication is directed and unbalanced, since global feasibility evolves with the local models and cannot be evaluated at any single node. We study this setting through general affine coupling and propose DiSPART (Directed Stochastic Primal–dual Algorithm with Residual Tracking). DiSPART turns global constraint information into distributed feedback by combining push–sum residual and multiplier tracking with gradient smoothing and moving-center regularization. Under standard smoothness, constraint regularity, bounded-variance stochastic gradients, and an explicit Perron-weighted mixing condition, we establish a finite-time bound on the average expected squared KKT residual that jointly controls stationarity and feasibility. For fixed problem and network parameters, the bound gives convergence with stochastic gradients and with exact gradients, while allowing infeasible primal initialization and a horizon-independent penalty without assuming bounded multipliers. The analysis further makes explicit how affine coupling, network mixing, and Perron imbalance shape finite-time performance. Experiments support the algorithmic design and the predicted network effects, while two real-data classification tasks show that these guarantees translate into practical constrained learning with substantially lower gradient-query costs than exact-gradient baselines.

Primary area:
optimization
Keywords:
distributed optimization, distributed learning, nonconvex optimization, directed network

Reviews

Among:
Shape:
1234this paper, Top 49%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.33 over 3 reviews, above 51% of the others.
Reviewer_XCpCOpenReview ↗
Rating
3
Confidence
3
Informativeness
3
Presentation
3
Soundness
3
Read review
Paper summary

The paper proposes DiSPART for distributed stochastic nonconvex optimization with general affine coupling constraints over unbalanced directed networks. The algorithm combines push–sum residual and multiplier tracking, gradient smoothing, and moving-center regularization. Under the stated assumptions, it establishes finite-time bounds on the average expected squared KKT residual, achieving O(K−1/2)O(K^{-1/2}) convergence with stochastic gradients and O(K−1)O(K^{-1}) with exact gradients. The analysis explicitly characterizes the effects of network mixing, Perron imbalance, and constraint coupling.

Critical strengths

The paper addresses a meaningful combination of challenges and provides a technically substantial convergence analysis. The guarantees jointly control stationarity and feasibility, allow infeasible primal initialization, and use a fixed penalty without assuming bounded multipliers. The key steps of the main convergence argument appear internally consistent upon inspection. The algorithm requires only one fresh stochastic gradient per node and one communication exchange per iteration, and the controlled ablations support its main design choices. Overall, I consider this a solid and useful contribution.

Critical weaknesses

My main concerns concern the completeness and interpretation of the experimental evidence. First, although Section 5 refers readers to Appendix G for experimental details, the appendix describes only the synthetic experiments. The objectives, sources of nonconvexity, coupling constraints, data partitioning, and parameter settings for a9a and Multiple Features are not specified, limiting reproducibility and assessment of their relevance to the proposed setting. Second, the comparison with Du et al. uses an unbalanced communication matrix and unbounded local domains, outside that method’s stated assumptions, as the authors acknowledge. This limits the conclusions that can be drawn from its relative performance. Third, the experiments use empirically selected parameters outside the theorem’s sufficient conditions, while the theoretical choices require global problem and network quantities. More guidance is needed to connect the guarantees with practical parameter selection. Finally, the small synthetic problems provide limited evidence of scalability with the number of agents or coupling constraints, particularly since each message contains two vectors whose dimension equals the number of coupling constraints.

Questions for authors

Could the authors provide complete modeling and implementation details for the two real-data experiments, particularly the sources of nonconvexity and the construction of the coupling constraints? Could the comparison with Du et al. be supplemented by experiments in a setting satisfying both methods’ assumptions? How sensitive is DiSPART to its main parameters, and can the authors provide practical selection guidance or an experiment using theoretically admissible parameters? Finally, how do communication volume and runtime scale with the number of agents and the dimension of the coupling constraints?

6 comments
AuthorsOpenReview ↗

Response to Reviewer XCpC — Overview

Thank you for your careful review and constructive suggestions. Your comments have helped us clarify our models and better connect theory with experiments. We address the weaknesses and their corresponding questions together in the following four points. We hope that these clarifications and additional evidence have addressed your concerns and strengthened your confidence in this work.

AuthorsOpenReview ↗

Response to Reviewer XCpC — Point 1: Real-data models and implementation

Point 1: Specifying the real-data learning problems and their connection to the theory

Thank you for pointing this out. We have expanded Section 5 and added Appendix H, Real-Data Experiments, covering both tasks.

(a) Learning tasks and data partitioning. Both tasks use linear prediction models with features distributed across six nodes, all indexing the same examples. Adult/a9a is binary income classification with 123123 LIBSVM-encoded features, split into blocks (21,21,21,20,20,20)(21,21,21,20,20,20); node 1 adds the only intercept. Multiple Features is ten-class digit recognition with six native views of dimensions (76,216,64,240,47,6)(76,216,64,240,47,6), one per node. The training/validation/test sizes are 26048/6513/1628126048/6513/16281 for a9a and 1200/400/4001200/400/400 for Multiple Features. Both use stratified splitting; a9a splits only its development set, retaining the supplied test set. Preprocessing uses training statistics only. Appendix H.1 specifies the split seeds and feature-assignment rules.

(b) Local objectives, nonconvexity, and coupling. Let FiF_i be node ii's feature matrix and WiW_i its weights. Training rows j=0,…,Ntr−1j=0,\ldots,N_{\rm tr}-1 are assigned cyclically through Ii=j:j mod 6=i−1\mathcal I_i=\\{j:j\bmod6=i-1\\}; node ii owns the corresponding auxiliary scores ZIiZ_{\mathcal I_i} and loss terms. Both tasks solve

min⁡Wi,ZIii=16∑i=16[Ri(Wi)+1Ntr∑j∈Iiℓ(Zj,yj)]subject to∑i=16FiWi−Z=0.\min_{\\{W_i,Z_{\mathcal I_i}\\}_{i=1}^{6}}\\ \sum_{i=1}^{6}\left[R_i(W_i)+\frac1{N_{\rm tr}}\sum_{j\in\mathcal I_i}\ell(Z_j,y_j)\right]\quad\text{subject to}\quad\sum_{i=1}^{6}F_iW_i-Z=0.

Here NtrN_{\rm tr} is the training size, and

ℓ(z,y)={log⁡(1+ez)−yz,a9a,y∈0,1,log⁡(∑a=09eza)−zy,Multiple Features.\ell(z,y)=\begin{cases}\log(1+e^z)-yz,&\text{a9a},\\ y\in\\{0,1\\},\\\\ \log(\sum_{a=0}^{9}e^{z_a})-z_y,&\text{Multiple Features}.\end{cases}

The regularizer is Ri(Wi)=10−3∑a∈PiWi,a2/(1+Wi,a2)R_i(W_i)=10^{-3}\sum_{a\in\mathcal P_i}W_{i,a}^2/(1+W_{i,a}^2), penalizing all weights except the a9a intercept. Its negative curvature makes the lifted objective nonconvex. To construct the coupling locally, node ii contributes FiWi−EiZIiF_iW_i-\mathcal E_iZ_{\mathcal I_i}, where Ei\mathcal E_i places its owned rows into an otherwise zero score array. Summing these contributions gives the displayed equality. Eliminating ZZ recovers the regularized classifier with scores ∑iFiWi\sum_iF_iW_i; Appendix H.2 provides the corresponding operators.

(c) Correspondence to the setting and implementation. Both tasks follow the structure of problem (1): each node's weights and owned auxiliary scores form its local variable, its regularizer and owned losses form the smooth nonconvex objective fif_i, and consistency between the auxiliary scores and combined local predictions gives the global affine coupling constraint. DiSPART operates over a fixed column-stochastic, unbalanced directed network in both tasks. Both tasks therefore match the setting studied here.

Fresh local estimates average component gradients sampled uniformly from Ii\mathcal I_i and are unbiased for ∇fi\nabla f_i. Stochastic DiSPART uses Bi=1B_i=1 for Multiple Features and Bi=64B_i=64 with replacement for a9a, including initialization. The latter follows the appendix's with-replacement oracle analysis; at Bi=1B_i=1, with- and without-replacement sampling coincide. Appendix H.3 verifies the model and oracle conditions.

The empirical DiSPART settings are listed as (α,τ,γ,β,ρ,ω)(\alpha,\tau,\gamma,\beta,\rho,\omega), where β\beta is the EMA coefficient:

Task and methodParameter tuple
Multiple Features, DiSPART(.08,6⋅10−6,.5,.05,10−4,2)(.08,6\cdot10^{-6},.5,.05,10^{-4},2)
Multiple Features, DiSPART-Det.(.1,10−5,.5,.05,10−4,2)(.1,10^{-5},.5,.05,10^{-4},2)
a9a, DiSPART(.02,.2,.2,.005,10,1)(.02,.2,.2,.005,10,1)
a9a, DiSPART-Det.(.04,.2,.2,.005,1,1)(.04,.2,.2,.005,1,1)

Appendix H.4 gives all baseline configurations, initialization, run lengths, and repetition seeds. The distinction between empirical settings and theorem-sufficient choices is addressed in Point 3.

(d) Interpretation of the results. Figures 4–5 compute validation cross-entropy from the learned weights through ∑iFiWi\sum_iF_iW_i, not from auxiliary training scores. Tables 2–3 separately report predictive quality, physical constraint violation, a common stationarity/feasibility diagnostic, and gradient-query costs including training and evaluation. Appendix H.5 defines these quantities. Results use five paired initialization/oracle repetitions on each fixed prepared task.

The results show that DiSPART combines competitive predictive performance with accurate constraint satisfaction on both real-data tasks. In particular, stochastic DiSPART achieves lower mean validation cross-entropy than all three baselines on Multiple Features, while using substantially fewer gradient queries than the exact-gradient baselines on both tasks at the reported communication budgets. These findings support the practical effectiveness of the proposed method for the coupled learning problems considered here.

AuthorsOpenReview ↗

Response to Reviewer XCpC — Point 2: Du comparison under compact domains and balanced mixing

Point 2: Explaining the original Du comparison and the supplementary comparison under Du's setting

Thank you for this helpful suggestion. The original comparison examined different methods under our target setting, so we adapted Du et al.'s method to the same problem and communication environment. Your suggestion helps us examine how these findings depend on the network and local-domain conditions, strengthening the experimental evidence. We have completed the supplementary comparison under Du's setting and prepared its specification and results for the baseline-comparison section of Appendix G.4.

(a) Rationale for the original comparison. Du et al. also study distributed nonconvex optimization with coupling constraints, and their primal–dual structure and constraint-tracking mechanism are closely related to ours. To compare implementations under our target setting, we encoded the affine equality as equivalent paired inequalities, used unrestricted local domains and the same unbalanced column-stochastic communication matrix as DiSPART, and retained Du's main update structure. Both implementations thus used the same problem, initialization, and communication conditions. DiSPART-Det. attained lower final mean comparison residuals and constraint violations, supporting its design for our target setting. These findings concern the implementations evaluated in that environment.

(b) Supplementary comparison under Du's setting and adjustments to our method. The supplementary experiment uses a doubly stochastic communication matrix WW, satisfying W1=1W\mathbf1=\mathbf1 and 1⊤W=1⊤\mathbf1^\top W=\mathbf1^\top, and common compact convex boxes Xi=[−4,4]8X_i=[-4,4]^8. It retains nonconvex objectives and affine coupling, with n=10n=10, di=8d_i=8, and m=5m=5, directly addressing the communication-weight and compact-domain conditions you identified.

Du uses its native updates and local box-constraint treatment. Our supplementary method is explicitly labeled Projected DiSPART-Det., with the primal step adjusted to

xik+1=ΠXi!(xik−α[gik+Ai⊤(λik+ρqik)+ω(xik−zik)]).x_i^{k+1}=\Pi_{X_i}\\!\left(x_i^k-\alpha\left[g_i^k+A_i^\top(\lambda_i^k+\rho q_i^k)+\omega(x_i^k-z_i^k)\right]\right).

Constraint tracking uses the actual post-projection increment Ai(xik+1−xik)A_i(x_i^{k+1}-x_i^k), while gradient smoothing, moving-center regularization, and multiplier tracking retain their original structure. Both methods use exact fresh gradients; under doubly stochastic mixing, the push–sum weights remain one. This projected version is used for the supplementary comparison. The main-text algorithm and Theorem 1 remain unchanged, and the theorem's guarantee is not directly extended to this variant.

(c) Experimental results and main findings. Under Du's doubly stochastic network and compact-domain conditions, each method evaluated 25 candidate configurations on the same three development problems with an equal tuning budget. After freezing the selected configurations, we evaluated them on ten new independent paired problems, running each trajectory for 6000 iterations. All runs completed successfully.

We use a common box-aware KKT residual RXR_X and the physical constraint error ∣Axk−b∣/m\\|Ax^k-b\\|/\sqrt m to assess joint stationarity/feasibility and affine feasibility, respectively. For each problem, we first average the last 20 saved checkpoints; the table reports the cross-problem mean and sample standard deviation.

MethodKKT residual RXR_XPhysical RMS
Projected DiSPART-Det.(2.68±3.08)×10−7(2.68\pm3.08)\times10^{-7}(2.90±1.59)×10−6(2.90\pm1.59)\times10^{-6}
Du et al.(4.67±3.10)×10−6(4.67\pm3.10)\times10^{-6}(1.99±0.76)×10−4(1.99\pm0.76)\times10^{-4}

Projected DiSPART-Det. achieved lower late-window values for both metrics on all ten paired problems. At the same 6000-iteration budget, its mean KKT residual and physical constraint error were approximately 1/17.41/17.4 and 1/68.81/68.8 of Du's, respectively. Thus, after restoring Du's network and local-domain conditions and providing equal additional tuning opportunities, our projected supplementary version still achieved a lower KKT residual and more accurate constraint satisfaction. This provides further support for the effectiveness observed in the original comparison within the tested setting and search range.

Reviewer_SaswOpenReview ↗
Rating
2
Confidence
2
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

This paper investigates distributed smooth non-convex optimization problems with general affine coupling constraints over fixed, unbalanced directed networks. The paper proposes the DiSPART algorithm, which combines push–sum residual and multiplier tracking, stochastic gradient smoothing, and moving-center proximal regularization. Under assumptions concerning smoothness, constraint regularity, stochastic oracles, and network mixing, the method achieves a convergence rate of O(K−1/2)O(K^{-1/2}) for the average expected squared KKT residual when using stochastic gradients, and O(K−1)O(K^{-1}) when using exact gradients—with parameters that are horizon-dependent (i.e., dependent on the total number of iterations) and remain fixed throughout a single run. These bounds explicitly characterize the impacts of affine coupling, network mixing, and Perron imbalance. The empirical evaluation include convergence simulations, ablation studies, comparisons with existing methods, controlled network experiments, and two classification tasks based on real-world data; the evaluation metrics include predictive performance, constraint satisfaction, and gradient query costs.

Critical strengths
  1. This paper proposes the DiSPART algorithm, which integrates a "push–sum" residual-tracking mechanism—driven by local residual increments—with multiplier updates. By reusing the updated residual-tracking quantities within the multiplier updates, both processes require only single round of inter-neighbor communication. Incorporating gradient smoothing and a moving-center regularization, this design provides a distributed feedback mechanism for non-convex stochastic objective functions subject to general affine-coupled constraints in environments with unbalanced directed communication. In each iteration, the algorithm requires only one stochastic gradient evaluation per node and eliminates the need to solve internal optimization subproblems. The contribution of this work lies in the synergistic design of these mechanisms tailored to the problem under study.

  2. The convergence analysis accounts for the interplay among stochastic gradient estimation errors, distributed tracking errors, and moving-center updates. It employs the averaged expected squared KKT residual to simultaneously control both stationarity and constraint violation. Under specified sufficient conditions, the algorithm achieves convergence guarantees of O(K−1/2)O(K^{-1/2}) for stochastic gradients and O(K−1)O(K^{-1}) for exact gradients, while explicitly disentangling the respective impacts of sampling noise, optimization error, network effects, and initial tracking error. Furthermore, the analysis accommodates infeasible initial points, uses a fixed penalty parameter independent of the total number of iterations, and does not require the assumption that the multipliers are bounded.

Critical weaknesses
  1. The description of the optimization problems addressed in the real-data experiments in Section 5 lacks sufficient detail. While the paper presents results for classification tasks—specifically in terms of cross-entropy loss on validation sets—it fails to explicitly define the training objectives, model architectures, local variables, or coupling constraints. Consequently, it is difficult to understand the precise relationship between the problems solved in Figures 4–5 and Tables 2–3 and the problem formulation (1). Furthermore, it is difficult to assess from the information provided how these experiments align with the theoretical assumptions, which complicates the interpretation of the experimental results and hinders their reproducibility.

  2. Some baseline comparisons provide limited evidence for performance differences attributable to the methods themselves. Appendix G.4 explicitly notes that the experimental setup used to evaluate the method proposed by Du et al. does not satisfy the assumptions of "doubly stochastic networks" and "compact local sets" required by that approach; thus, the observed performance gaps may, to some extent, stem from these specific adjustments. Moreover, although the final parameters were selected using a consistent procedure, the effort invested in the initial hyperparameter tuning varied across the different methods. These factors weaken the support for the claimed algorithmic advantages, as the specific implementation details, configuration choices, and tuning processes could all significantly influence the observed performance differences.

Questions for authors
  1. I am interested in how the mini-batch size BB affects the convergence rate presented in Theorem 1. Could you provide an explicit expression for this bound in terms of BB and KK? In a finite-sum setting where each node has NN samples, how does the convergence rate behave when BB is held constant versus when it scales with NN? Specifically, under what sampling assumptions and scaling rules for BB does this bound recover the O(K−1)O(K^{-1}) convergence rate associated with the use of exact gradients?

  2. Please specify the model architectures, training objectives, local variables, and coupling constraints for the classification tasks (Adult/a9a and Multiple Features) discussed in Section 5, so that the experiments presented in Figures 4–5 and Tables 2–3 can be mapped back to the problem formulation in (1). Additionally,please provide details on data partitioning, batch sizes, sampling procedures, and key algorithmic parameters, and explain how the cost of gradient queries is calculated.

  3. For the ablation variants that omit gradient momentum or moving-center regularization, did you attempt to tune their respective step sizes using the same tuning budget as that allocated for the full method? Does the full method retain its performance advantage after such tuning? Furthermore, how robust are the result of the full method to variations in its key step-size parameters and gradient-smoothing coefficients?

  4. As a supplementary experiment, it would be good to compare accuracy and computational cost for B∈{1,2,4,8,16}B \in \{1, 2, 4, 8, 16\} to show the impact of batch size on practical performance.

  5. If feasible, please compare the wall-clock time required for each method to reach a common KKT residual threshold, using the same hardware environment. Additionally, please report the number of gradient queries and the communication costs to clarify the trade-offs between different computational resources

10 comments
AuthorsOpenReview ↗

Response to Reviewer Sasw — Overview

Thank you for your careful assessment and for recognizing the algorithmic integration and convergence analysis. We organize our response into eight points, following the order of your review and addressing each concern separately. We hope the clarifications and additional evidence below reflect our careful consideration of your comments and strengthen your confidence in the paper's contributions.

AuthorsOpenReview ↗

Response to Reviewer Sasw — Point 1: Real-data learning models

Point 1 (W1): Clarifying the real-data learning problems and their correspondence to our formulation

Thank you for highlighting this issue. We have expanded the real-data experimental description in Section 5 and added a dedicated appendix, Real-Data Experiments, covering both Adult/a9a and Multiple Features.

(a) Learning tasks and feature partitions. Both tasks use six-node linear classifiers, with nodes holding different features of the same training examples. Adult/a9a is a binary income-classification task: its 123 encoded features form nearly equal blocks of sizes (21,21,21,20,20,20)(21,21,21,20,20,20), with an additional intercept at node 1. Multiple Features is a ten-class digit-classification task retaining six unequal native views: Fourier coefficients, profile correlations, Karhunen–Loève coefficients, pixel averages, Zernike moments, and morphological features, of dimensions 76,216,64,240,47,676,216,64,240,47,6, respectively.

(b) Training objective and loss functions. Let FiF_i and WiW_i denote node ii's feature matrix and classifier weights. Complete prediction scores are ∑iFiWi\sum_iF_iW_i. Introduce auxiliary scores ZZ and partition the training-example indices into sets Ii\mathcal I_i, assigning their losses to node ii. Each node optimizes (Wi,ZIi)(W_i,Z_{\mathcal I_i}), and both tasks minimize

min⁡(Wi,ZIi)i=16∑i=16[Ri(Wi)+1Ntr∑j∈Iiℓ(Zj,yj)].\displaystyle \min_{\\{(W_i,Z_{\mathcal{I}_i})\\}_{i=1}^{6}}\quad \sum_{i=1}^{6}\left[R_i(W_i)+\frac{1}{N_{\mathrm{tr}}}\sum_{j\in\mathcal{I}_i}\ell(Z_j,y_j)\right].

where NtrN_{\rm tr} is the number of training examples. The losses are binary logistic and ten-class softmax cross-entropy, respectively:

\begin{cases} \log(1+e^z)-yz, & \text{a9a},\quad y\in\\{0,1\\}, \\\\ \log\\!\left(\sum_{a=0}^{9}e^{z_a}\right)-z_y, & \text{Multiple Features}. \end{cases}$$ The weight regularizer is $$R_i(W_i)=10^{-3}\sum_{a\in\mathcal P_i} \frac{W_{i,a}^{2}}{1+W_{i,a}^{2}},$$ where $\mathcal P_i$ indexes regularized weights, excluding only the a9a intercept. Cross-entropy is convex in the scores; the smooth saturated regularizer introduces nonconvexity through its negative curvature at some weight values. **(c) Affine coupling and local decision variables.** The auxiliary scores must agree with the predictions jointly produced by the nodes: $$\sum_{i=1}^{6}F_iW_i-Z=0.$$ Each node jointly updates its weights and assigned auxiliary scores, evaluating their local losses while the constraint couples these scores to all nodes' weights. At feasibility, $Z$ equals the complete prediction scores, and the objective is the classifier's cross-entropy plus weight regularization. **(d) Correspondence with our model and algorithm.** In problem (1), local variables comprise each node's weights and owned auxiliary scores; local objectives comprise their cross-entropy losses and nonconvex weight regularizer; and the affine equality couples all nodes. Each node averages component gradients from $B$ randomly sampled assigned examples to estimate its local gradient, then applies gradient smoothing. Nodes communicate over a fixed unbalanced directed network, using push-sum normalization and residual tracking to coordinate the coupling constraint. Both tasks thus match the nonconvex objectives, stochastic gradients, affine coupling, and directed communication studied here. Appendix H.3 details the model and oracle assumption checks. **(e) Interpretation and support from the reported results.** Figures 5–6 and Tables 2–3 evaluate these learning problems from complementary perspectives. Validation cross-entropy measures the prediction quality of the learned weights, while the constraint RMS and comparison residual assess coupling feasibility and optimization progress. Validation predictions are computed directly from the learned weights through $\sum_iF_iW_i$, without using the auxiliary training scores or including the regularizer. These metrics therefore show both the learning performance and how well the nodes coordinate their coupled decisions. Across five paired repetitions, stochastic DiSPART achieves mean validation cross-entropy $0.3429$ on a9a, slightly above IPDC's $0.3287$, while using approximately $1/40$ of its gradient queries. On Multiple Features, it achieves lower mean validation cross-entropy than IPDC ($2.1201$ versus $2.1860$), using approximately $1/66$ of its queries. Its mean endpoint constraint RMS is below $0.01$ on both tasks. Query counts include training and evaluation. At the reported communication budgets and parameter settings, these results demonstrate a practical advantage of DiSPART: obtaining the reported predictive performance while meeting the mean feasibility requirement with substantially fewer gradient queries than the exact-gradient IPDC baseline.
AuthorsOpenReview ↗

Response to Reviewer Sasw — Point 2: Du baseline comparison

Point 2 (W2-1): Clarifying the Du baseline comparison in our target setting

Thank you for highlighting this concern. We selected Du et al. (2026) because it addresses distributed nonconvex optimization with constraints coupling distinct local variable blocks through primal–dual updates and distributed constraint tracking. This closely matches the coordination structure of our problem, making it a relevant reference for evaluating DiSPART.

Our paper jointly considers nonconvex objectives, stochastic gradients, general affine coupling, and unbalanced directed communication. None of the external guarantees summarized in Table 1 covers this full combination. We therefore evaluated structurally related methods on a common benchmark with explicitly specified adaptations. Keeping the benchmark fixed provides a common basis for comparison; changing the objective, feasible set, or communication environment separately for each method would mix task differences with algorithmic differences.

For Du et al., we encoded the benchmark's affine equalities as paired inequalities, preserving their feasible set, retained the complete smooth local objectives, and used the common full-space local domains with the optional nonsmooth term set to zero. We supplied the same unbalanced column-stochastic matrix as DiSPART while retaining the core primal, relaxation, multiplier, and constraint-tracking recursions, without adding push-sum or a balancing mechanism. These adaptations were documented in the original Appendix G.4.

The comparison is thus anchored to a common problem and evaluation protocol. Within each synthetic instance, the methods shared the problem data, affine constraint, initial primal point, and physical communication graph. Du et al.'s implementation and DiSPART-Det. both used exact local gradients. All methods were evaluated using the same primal comparison residual, with gradient-query and communication costs counted according to each implementation. These controls support an empirical comparison of the specified implementations in our target setting, without implying that their original theoretical guarantees carry over.

Under the reported synthetic configurations, Figure 2 shows a lower terminal mean comparison residual for DiSPART-Det. than for the adapted Du implementation. Our conclusion concerns the effectiveness of a design tailored to this combined setting, rather than a universal performance ranking across different problem classes. The normalization ablation in Figure 1(b) further examines the contribution of DiSPART's weighting correction within the same algorithm, complementing the baseline comparison. We have also completed an equal-budget comparison under Du's doubly stochastic network and compact-domain conditions. The explicitly projected supplementary version, Projected DiSPART-Det., attained lower box-aware KKT residuals and physical constraint errors on all ten independent paired problems; this does not extend the original full-space theorem to the projected variant. We have clarified this purpose here and explicitly identified the Du implementation as adapted, consistently with the scope stated in the original appendix.

Reviewer_yb4dOpenReview ↗
Rating
2
Confidence
3
Informativeness
2
Presentation
3
Soundness
2
Read review
Paper summary

The paper is devoted to coupling constraints optimization in the nonconvex scenario and directed networks. Coupling constraints optimization is a branch of decentralized optimization, where each node locally holds a vector of variables, and the individual vectors are interconnected by cross-coupling affine constraints. The nodes are equal, they communicate through a directed network and exchange information with their immediate neighbours. The paper gives an algorithm based on push-pull technique and performs a theoretical analysis of convergence. Numerical simulations are also performed.

Critical strengths

The paper addresses a novel problem in distributed optimization. The nonconvex scenario and directed graphs have not been studied before for coupling constraints, to the best of my knowledge. The paper has an easily-readable form and includes all needed parts: comparison to previous works, formulation of assumptions and algorithm, analysis of algorithm and numerical simulations.

Critical weaknesses

My main concern is the convergence speed presented in Table 1. Traditionally in numerical optimization, one provides not only dependence on the number of steps K but also on the function parameters, such as smoothness L_i (I think this quantities are held implicitly in D_0 from Theorem 1). The convergence rate seems strange, since O(K^{-1/2} + K^{-1}) is just O(K^{-1/2}). Moreover, since the paper focuses on the nonconvex case, the comparison with works that do not study nonconvex case should be more accurate: this manuscript cannot be directly compared to the paper that studies only strongly convex scenario, i.e. it cannot be said that the results are stronger or weaker.

Questions for authors

I think some more relevant literature should be cited in the paper. The authors may be interested in the works of the following authors in decentralized optimization: Angelia Nedich, Gesualdo Scutari, Dmitry Kovalev and Kevin Scaman.

7 comments
AuthorsOpenReview ↗

Response to Reviewer yb4d — Point 1: Parameter Dependence 1

Point 1 (Critical Weaknesses): Clarifying the parameter dependence behind the convergence rates in Table 1

Thank you for this helpful comment. We agree that parameter dependence is important for interpreting convergence guarantees. Table 1 was designed to help readers compare the combinations of settings covered by different methods. Expanding every rate would require source-specific definitions, normalizations, and admissibility conditions, making the overview harder to read within the available space. We therefore retain concise leading orders in KK and discuss parameter dependence separately. Following your suggestion, we explain these dependencies below and will include DiSPART's detailed parameter analysis in the revised appendix.

The response has three parts: (a) DiSPART's dependence on LL, including its role in D0D_0, admissible stepsizes, and rate coefficients, together with the effects of nn, βπ\beta_{\pi}, and κπ\kappa_{\pi}; (b) comparisons explaining why similar iteration orders can have different parameter dependencies; and (c) detailed bounds for the comparison methods as supporting material.

Table 1. Representative nonconvex methods: settings and convergence guarantees.

MethodSGGCUNCriterionLeading rate
SONATA (Scutari and Sun, 2019)——✓Stationarity / consensusO(K−1)O(K^{-1}) (i)
IPDC (Zhang et al., 2022)—✓—KKT residualO(K−1)O(K^{-1})
MG-Push-DIGing (Liang et al., 2025)✓—✓Gradient normO(K−1/2)O(K^{-1/2})
Huang et al. (2025)✓✓—Moreau gradient normO(K−1/2)O(K^{-1/2})
D-SMPL (Sharma et al., 2026)✓——Stationarity meritO(K−2/3)O(K^{-2/3}) (ii)
Du et al. (2026)—✓ (iii)—Stationarity errorO(K−1/3)O(K^{-1/3})
DiSPART✓✓✓Average KKT residualO(K−1/2)O(K^{-1/2})
DiSPART-Det.—✓✓Average KKT residualO(K−1)O(K^{-1})

Notes. SG: stochastic gradients; GC: coupling across distinct variable blocks, excluding consensus; UN: unbalanced directed networks. Criteria use squared errors under each source's definitions. Rates hold under the respective assumptions with other parameters fixed; stochastic bounds are in expectation. KK counts outer iterations, whose costs may differ. SONATA and IPDC use best iterates; the other bounds use iteration averages. (i) Converted from first-hit complexity. (ii) D-SMPL uses recursive variance reduction under the stronger mean-square smoothness assumption. Its merit combines nearby-point penalized stationarity, proximity, and consensus errors. (iii) Nonconvex nonlinear coupled inequalities; only the stationarity component is shown.

(a). Parameter dependence of DiSPART.

As you noted, D0D_0 does depend on smoothness. For our objective f(x)=∑ifi(xi)f(x)=\sum_i f_i(x_i) over distinct local variable blocks, the full gradient admits L=max⁡iLiL=\max_iL_i. The initialization estimates in Appendix E.1--E.2 give a positive bound satisfying

D0≥[f(x0)−f\*]++(1ω+2ω−L)∥∇f(x0)∥2+[4ρ+L+2ωσA2+50ρ2A02ω−L]∥Ax0−b∥2+8σ02cβ,D0>0.D_0\geq[f(x^0)-f_\*]_++\left(\frac{1}{\omega}+\frac{2}{\omega-L}\right)\lVert\nabla f(x^0)\rVert^2+\left[4\rho+\frac{L+2\omega}{\sigma_A^2}+\frac{50\rho^2A_0^2}{\omega-L}\right]\lVert Ax^0-b\rVert^2+\frac{8\sigma_0^2}{c_\beta},\qquad D_0>0.

Here A0=∥A∥A_0=\lVert A\rVert, σA=σmin⁡(A)>0\sigma_A=\sigma_{\min}(A)>0, f∗f_* is an objective lower bound, and σ02\sigma_0^2 bounds the expected squared initial gradient-estimation error. The displayed weights show explicitly how LL, the regularization gap ω−L\omega-L, and the coupling geometry enter the initialization bound.

Smoothness also appears outside D0D_0. The admissible parameters satisfy

αK≤12(L+ρA02+ω),cβ≥max⁡{1,16L},ω>L.\alpha_K\leq\frac{1}{2(L+\rho A_0^2+\omega)},\qquad c_\beta\geq\max\lbrace 1,16L\rbrace,\qquad\omega>L.

where ρ\rho and ω\omega are the penalty and proximal coefficients, and β=cβαK\beta=c_\beta\alpha_K is the gradient-smoothing parameter. Before merging coefficients into the constant CC in Theorem 1, Appendix E.3 gives

MK≤B[28cβ σRD0K+D0Hπ+16IπK].M_K\leq\mathsf B\left[2\sqrt{8c_\beta}\,\sigma_{\rm R}\sqrt{\frac{D_0}{K}}+\frac{D_0H_\pi+16I_\pi}{K}\right].

Here MKM_K is the average expected squared KKT residual, B\mathsf B denotes the comparison constant called BB in Appendix D, σR\sigma_{\rm R} is the aggregate mini-batch noise bound, HπH_\pi controls the admissible inverse stepsize, and IπI_\pi measures the initial tracking contribution. Besides D0D_0, smoothness enters cβc_\beta, HπH_\pi, and B\mathsf B; the latter also involves geometric estimates such as H2=ω2/[σA2(ω2−L2)]\mathcal H^2=\omega^2/[\sigma_A^2(\omega^2-L^2)]. Thus, the dependence on LL is not confined to the initialization constant or reducible to the explicit square root of cβc_\beta alone.

AuthorsOpenReview ↗

Response to Reviewer yb4d — Point 1: Parameter Dependence 2

Smoothness also appears outside D0D_0. The admissible parameters satisfy

αK≤12(L+ρA02+ω),cβ≥max⁡{1,16L},ω>L,\alpha_K\leq\frac{1}{2(L+\rho A_0^2+\omega)},\qquad c_\beta\geq\max\lbrace 1,16L\rbrace,\qquad\omega>L,

where ρ\rho and ω\omega are the penalty and proximal coefficients, and β=cβαK\beta=c_\beta\alpha_K is the gradient-smoothing parameter. Before merging coefficients into the constant CC in Theorem 1, Appendix E.3 gives

MK≤B[28cβ σRD0K+D0Hπ+16IπK].M_K\leq\mathsf B\left[2\sqrt{8c_\beta}\,\sigma_{\rm R}\sqrt{\frac{D_0}{K}}+\frac{D_0H_\pi+16I_\pi}{K}\right].

Here MKM_K is the average expected squared KKT residual, B\mathsf B denotes the comparison constant called BB in Appendix D, σR\sigma_{\rm R} is the aggregate mini-batch noise bound, HπH_\pi controls the admissible inverse stepsize, and IπI_\pi measures the initial tracking contribution. Besides D0D_0, smoothness enters cβc_\beta, HπH_\pi, and B\mathsf B; the latter also involves geometric estimates such as H2=ω2/[σA2(ω2−L2)]\mathcal H^2=\omega^2/[\sigma_A^2(\omega^2-L^2)]. Thus, the dependence on LL is not confined to the initialization constant or reducible to the explicit square root of cβc_\beta alone.

Agent count and network effects are exposed through

ΓA=nAmax⁡2+n Amax⁡A0≤2nAmax⁡2,Amax⁡=max⁡i∥Ai∥,σR2=∑iσi,R2,\Gamma_A=nA_{\max}^2+\sqrt n\,A_{\max}A_0\leq2nA_{\max}^2,\qquad A_{\max}=\max_i\lVert A_i\rVert,\qquad \sigma_{\rm R}^2=\sum_i\sigma_{i,\rm R}^2,

Hπ≤CH[1+(1+κπΓA)βπ1−βπ],16Iπ≤Ctr[1+κπ2βπ21−βπ2].H_\pi\leq C_H\left[1+\frac{(1+\kappa_\pi\Gamma_A)\beta_\pi}{1-\beta_\pi}\right],\quad16I_\pi\leq C_{\rm tr}\left[1+\frac{\kappa_\pi^2\beta_\pi^2}{1-\beta_\pi^2}\right].

The quantity σi,R2\sigma_{i,\rm R}^2 bounds the batch-gradient variance at node ii. For fixed problem data, algorithm coefficients, and initialization, CHC_H and CtrC_{\rm tr} are independent of the network. Slower mixing increases the displayed factors involving βπ\beta_\pi, while greater Perron imbalance enters through κπ\kappa_\pi and κπ2\kappa_\pi^2. These explicit network effects occur in the K−1K^{-1} contributions. Node count also affects aggregate noise, initialization, and coupling geometry, so the displayed linear envelope for ΓA\Gamma_A is not a claim that the complete complexity is linear in nn.

For the squared-residual target MK≤εM_K\leq\varepsilon, the same bound gives a sufficient iteration complexity

Kε=O(1+B2cβσR2D0ε2+B(D0Hπ+Iπ)ε).K_\varepsilon=\mathcal O\left(1+\frac{\mathsf B^2c_\beta\sigma_{\rm R}^2D_0}{\varepsilon^2}+\frac{\mathsf B(D_0H_\pi+I_\pi)}{\varepsilon}\right).

This expression retains the smoothness, coupling, and network dependence described above. With exact gradients, σR=0\sigma_{\rm R}=0 and the ε−2\varepsilon^{-2} contribution vanishes. For a prescribed horizon, the parameters remain fixed throughout the run; training uses (K+1)∑iBi(K+1)\sum_iB_i component-gradient evaluations, including initialization and estimator refreshes, and KK neighbor exchanges.

(b). What the parameter expressions reveal about the different settings.

Although SONATA, IPDC, and deterministic DiSPART share the K−1K^{-1} order, their variable structures differ. SONATA's shared-variable coefficients include LΣ=∑iLiL_\Sigma=\sum_iL_i, whereas IPDC and DiSPART use distinct local blocks and L=max⁡iLiL=\max_iL_i. With Li=LˉL_i=\bar L, these scales become nLˉn\bar L and Lˉ\bar L. This reveals how local curvature accumulates differently; the complete dependence on nn also involves each bound's normalization.

For IPDC and DiSPART, the separate local variables must jointly satisfy a global affine constraint, introducing another source of node dependence. IPDC's nBmax⁡2nB_{\max}^2 factor bounds how local variable errors can add together in that constraint. In DiSPART, the coupling scale ΓA≤2nAmax⁡2\Gamma_A\leq2nA_{\max}^2 also enters distributed constraint tracking and is multiplied by κπβπ/(1−βπ)\kappa_\pi\beta_\pi/(1-\beta_\pi) in the displayed network contribution. Thus, this part of our bound links node count and constraint strength to communication conditions: slower mixing or greater imbalance can amplify the tracking contribution. This shows where handling affine coupling over an unbalanced directed network changes the coefficient while preserving the K−1K^{-1} iteration order.

The stochastic bounds reflect the same structural distinction. MG-Push-DIGing's term σLΔ/(nRK)\sigma\sqrt{L\Delta/(nRK)} benefits from averaging gradient information across nodes and samples. DiSPART's estimates form separate blocks of the full gradient, giving the aggregate variance bound σR2=∑iσi,R2\sigma_{\rm R}^2=\sum_i\sigma_{i,\rm R}^2. MG-Push-DIGing uses RR samples per node and 2R2R communication rounds per iteration, while DiSPART uses BiB_i samples at node ii and one neighbor exchange. Their common K−1/2K^{-1/2} order thus accompanies different roles for nn: averaging can reduce noise in the former, while the latter controls noise across distinct variable blocks together with global feasibility.

AuthorsOpenReview ↗

Response to Reviewer yb4d — Point 1: Parameter Dependence 3

(c1). Additional technical details: SONATA, IPDC, and MG-Push-DIGing.

The expressions below provide the quantitative basis for the comparisons above. Each block uses its own notation for problem, initialization, and algorithm quantities; similarly named symbols need not have the same meaning across methods. Except where quoted directly, the expressions are conservative consequences of the cited analyses under suitable sufficient parameter choices. They are not claims of optimized dependence on each parameter.

SONATA (Scutari and Sun, 2019). For its squared stationarity/consensus merit, a conservative reconstruction under a sufficiently small admissible fixed stepsize gives

min⁡0≤k<KMS(xk)≤1K[2nΩcτ,Sϕlb{adαS+bαS(qFSμS+3n2u)}+FSHxμS+3n2Hy].\min_{0\leq k<K}\mathcal M_{\rm S}(x^k)\leq\frac1K\Bigg[\frac{2n\Omega}{c_{\tau,\rm S}\phi_{\rm lb}}\left\lbrace \frac{a_d}{\alpha_{\rm S}}+b\alpha_{\rm S}\left(\frac{qF_{\rm S}}{\mu_{\rm S}}+3n^2u\right)\right\rbrace+\frac{F_{\rm S}H_x}{\mu_{\rm S}}+3n^2H_y\Bigg].

The local smoothness constants {Li}\lbrace L_i\rbrace enter ad,u,FSa_d,u,F_{\rm S}, the admissible stepsize αS\alpha_{\rm S}, and the initial-energy bound Ω\Omega. Agent count nn appears explicitly and through q,u,FSq,u,F_{\rm S} and αS\alpha_{\rm S}. Network dependence enters through the window length bb, the window contraction rr underlying qq, and the push--sum weight bounds, including ϕlb\phi_{\rm lb}; these also affect the derived coefficients and admissible stepsize. Here Ω,Hx,Hy\Omega,H_x,H_y collect initialization and first-window energies.

IPDC (Zhang et al., 2022). Combining the positive descent inequality of Lemma 24 with the source's error bounds gives, for a conservative admissible parameter choice ensuring positive descent margins,

min⁡0≤k<KRI(zk)≤ΔΦmax⁡{2(p2+L2),nBmax⁡2}K×[2pβ+20σ22a2ℓ211(ρ−12)+4ζ(σ2a6+σ4)2+σ22a4α].\min_{0\leq k<K}\mathcal R_{\rm I}(z^k)\leq{}\frac{\Delta_\Phi\max\lbrace 2(p^2+L^2),nB_{\max}^2\rbrace}{K} \times\left[\frac{2}{p\beta}+\frac{20\sigma_2^2a_2\ell^2}{11(\rho-\tfrac12)}+4\zeta(\sigma_2\sqrt{a_6}+\sigma_4)^2+\frac{\sigma_2^2a_4}{\alpha}\right].

Here RI\mathcal R_{\rm I} is the maximum of the squared stationarity and feasibility components, ΔΦ\Delta_\Phi is the initial potential gap, pp is the proximal parameter, and Bmax⁡=max⁡i∥Bi∥B_{\max}=\max_i\lVert B_i\rVert. Smoothness L=γ+L=\gamma^+ appears explicitly in the prefactor and enters σ2,a2,a4\sigma_2,a_2,a_4 and the admissible algorithm parameters. Agent count nn appears explicitly in nBmax⁡2nB_{\max}^2, with additional dependence carried by the graph and coupling geometry. Network dependence enters through ℓ=λmax⁡(L+)\ell=\lambda_{\max}(\mathcal L^+), where L+\mathcal L^+ is the signless graph Laplacian, and through the joint graph/coupling error-bound coefficients in a2,a4,a6a_2,a_4,a_6. These quantities also restrict the admissible stepsizes. The symbols σ2,σ4\sigma_2,\sigma_4 here are deterministic sensitivity coefficients, not stochastic noise levels.

MG-Push-DIGing (Liang et al., 2025). Under the source's smoothness, variance, initialization, and parameter conditions, Appendix C, Eq. (42), gives

1K+1∑k=0KE∥∇f(xˉk)∥2=O(σLΔn(K+1)R+LΔp(1−βπ)(K+1)R).\frac{1}{K+1}\sum_{k=0}^{K}\mathbb E\lVert \nabla f(\bar x^k)\rVert^2=\mathcal O\Biggl(\sigma\sqrt{\frac{L\Delta}{n(K+1)R}}+\frac{L\Delta p}{(1-\beta_\pi)(K+1)R}\Biggr).

Here T=(K+1)RT=(K+1)R, Δ\Delta is the initial objective gap, and σ2\sigma^2 bounds the local gradient variance. Smoothness LL appears explicitly in both terms. Agent count nn enters the stochastic term and the coefficient pp. Network contraction βπ\beta_\pi and Perron imbalance κπ\kappa_\pi enter through pp and the mixing length R=⌈p/(1−βπ)⌉R=\lceil p/(1-\beta_\pi)\rceil. Each outer iteration uses RR gradient samples per node and 2R2R communication rounds, so the dependence on RR also reflects the work performed per iteration.

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.