A Prediction--Correction Analysis of Two-Way Block Splitting in Distributed Learning
Abstract
This note revisits the convergence of the Parikh--Boyd two-way block-splitting algorithm for large-scale distributed learning through the He--Yuan prediction--correction framework. Simultaneous row--column partitioning is also relevant to hybrid federated learning, where data may be heterogeneous in both samples and features. We lift the reduced iteration to an equal-dimensional product space and reconstruct the primal and dual coordinates omitted by its implementation. The induced orthogonal-complement structure establishes exact iteration-by-iteration equivalence with the published updates. A mixed variational-inequality representation then yields a fundamental descent inequality, global convergence, an ergodic complexity bound, and current-iterate residual estimates under standard convexity, solvability, exact-subproblem, and invariant-initialization assumptions. The analysis also shows that the reduced state recursion is a metric proximal point iteration. No strong convexity, differentiability, or full-rank condition is imposed. The derivation clarifies which algebraic initialization conditions allow the reduced implementation to inherit the full-space convergence and complexity guarantees without modifying its local updates.
Related
- Primal-dual forward-reflected splitting with linesearch for distributed min-max problems under local Lipschitz smoothness
- Adaptive accuracy-driven splitting in Ozaki matrix multiplication and application to block LU factorization
- Distributed Formation Model Predictive Control Under Communication Denial: An Edge-Splitting ADMM with Centralized-Equivalence Gating and Confidence-Decayed Coupling
- Parallel AI Agent Collaboration as Graph-Structured Distributed Block Optimization
- Explicit Super-Linear Algebra over K[θ1, θ2]: A General Berezinian Correction Formula and Multiplicativity Theorem for Arbitrary Block Size
BibTeX
@misc{wu2026predictioncorrection,
title = {{A Prediction--Correction Analysis of Two-Way Block Splitting in Distributed Learning}},
author = {Xiaofei Wu},
howpublished = {arXiv},
year = {2026},
month = sep,
doi = {10.48550/arxiv.2609.27924},
eprint = {2609.27924},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2609.27924},
}
RIS
TY - UNPB
TI - A Prediction--Correction Analysis of Two-Way Block Splitting in Distributed Learning
AU - Xiaofei Wu
PY - 2026
DA - 2026/09/01
PB - arXiv
DO - 10.48550/arxiv.2609.27924
UR - https://arxiv.org/abs/2609.27924
AB - This note revisits the convergence of the Parikh--Boyd two-way block-splitting algorithm for large-scale distributed learning through the He--Yuan prediction--correction framework. Simultaneous row--column partitioning is also relevant to hybrid federated learning, where data may be heterogeneous in both samples and features. We lift the reduced iteration to an equal-dimensional product space and reconstruct the primal and dual coordinates omitted by its implementation. The induced orthogonal-complement structure establishes exact iteration-by-iteration equivalence with the published updates. A mixed variational-inequality representation then yields a fundamental descent inequality, global convergence, an ergodic complexity bound, and current-iterate residual estimates under standard convexity, solvability, exact-subproblem, and invariant-initialization assumptions. The analysis also shows that the reduced state recursion is a metric proximal point iteration. No strong convexity, differentiability, or full-rank condition is imposed. The derivation clarifies which algebraic initialization conditions allow the reduced implementation to inherit the full-space convergence and complexity guarantees without modifying its local updates.
ER -