A Unified Framework for Randomized Row-Action Methods for Structured Data Fitting and Constraint Geometry
Abstract
We study randomized row-action methods for problems with linear observations, convex constraints, and non-Euclidean geometry. Our starting point is a unified formulation in which the data-fitting term acts in observation space, while the feasible set and the regularizer encode structure in variable space. It covers constrained least squares, nonnegative and simplex-constrained models, regularized data fitting, and equality-constrained Bregman selection problems. The structure of these problems leads naturally to two algorithmic branches. The first uses primal Bregman-proximal row steps for soft data-fitting problems. The second uses dual Bregman--Kaczmarz steps for problems with hard equality constraints. We first derive a common one-step inequality. We then give deterministic and stochastic convergence results for the soft branch under relative smoothness. For constrained least squares, the normalized row oracle has exact first- and second-moment identities. They yield an expected ergodic bound in the inconsistent case, an O(1/K) bound in the interpolating case, and linear convergence of the actual iterates under a residual error bound. For equality-constrained selectors, we prove linear convergence in expected Bregman distance under a residual-to-Bregman error bound. We recall global sufficient conditions for this bound and derive local constants for the nonnegative quadratic geometry and the entropy geometry on the simplex. Numerical experiments illustrate the noisy stepsize trade-off and the local entropy selector theory, and show that entropic row-action updates can recover interpretable factors in a simplex-structured nonnegative matrix factorization problem.
Related
- Geometry of Relaxed Fair Regression: A Unified Framework for Aware and Unaware Settings
- Covariate Adjustment in Randomized Experiments: A Unified Framework for Decision and Practice
- The Priority-Axis Z-Algebra: A Unified Framework of Axioms, Structure Theory, and Intrinsic Differential Geometry
- The Operator–Spectral Framework of ZEBTS: A Unified Structure for Geometry, Arithmetic, and the Riemann Hypothesis
- The Unified Separation Condition: A General Constraint Qualification for Smooth and Nonsmooth Optimization
BibTeX
@misc{leplat2026unified,
title = {{A Unified Framework for Randomized Row-Action Methods for Structured Data Fitting and Constraint Geometry}},
author = {Valentin Leplat and Zeyu Dong and Junfeng Yin},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2610.14764},
eprint = {2610.14764},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2610.14764},
}
RIS
TY - UNPB
TI - A Unified Framework for Randomized Row-Action Methods for Structured Data Fitting and Constraint Geometry
AU - Valentin Leplat
AU - Zeyu Dong
AU - Junfeng Yin
PY - 2026
DA - 2026/10/10
PB - arXiv
DO - 10.48550/arxiv.2610.14764
UR - https://arxiv.org/abs/2610.14764
AB - We study randomized row-action methods for problems with linear observations, convex constraints, and non-Euclidean geometry. Our starting point is a unified formulation in which the data-fitting term acts in observation space, while the feasible set and the regularizer encode structure in variable space. It covers constrained least squares, nonnegative and simplex-constrained models, regularized data fitting, and equality-constrained Bregman selection problems. The structure of these problems leads naturally to two algorithmic branches. The first uses primal Bregman-proximal row steps for soft data-fitting problems. The second uses dual Bregman--Kaczmarz steps for problems with hard equality constraints. We first derive a common one-step inequality. We then give deterministic and stochastic convergence results for the soft branch under relative smoothness. For constrained least squares, the normalized row oracle has exact first- and second-moment identities. They yield an expected ergodic bound in the inconsistent case, an O(1/K) bound in the interpolating case, and linear convergence of the actual iterates under a residual error bound. For equality-constrained selectors, we prove linear convergence in expected Bregman distance under a residual-to-Bregman error bound. We recall global sufficient conditions for this bound and derive local constants for the nonnegative quadratic geometry and the entropy geometry on the simplex. Numerical experiments illustrate the noisy stepsize trade-off and the local entropy selector theory, and show that entropic row-action updates can recover interpretable factors in a simplex-structured nonnegative matrix factorization problem.
ER -