math.OCNov 10, 2026

Dual-Space Preconditioning for Variational Inequalities and Root-Finding Problems

Authors: Jan Quan, Konstantinos Oikonomidis, Alexander Bodard, Panagiotis Patrinos

Organizations: KU Leuven (STADIUS)

Abstract

This paper develops a dual-space preconditioning framework for variational inequalities and root-finding problems beyond classical cocoercivity and Lipschitz continuity assumptions. To this end, we introduce both a novel cocoercivity-type condition and a relaxed Lipschitz continuity condition, and derive convergence of deterministic and stochastic methods under these generalized conditions. For isotropic preconditioners, the resulting algorithms can be interpreted as variable-stepsize variants of classical methods, extending recent analyses based on (L0,L1)(L_0, L_1)-type growth conditions while allowing simpler proofs and larger stepsize ranges. We also show that the framework naturally handles variational inequalities through weak Minty-type arguments. Finally, we study the associated continuous-time dynamics and derive a variational and optimal control interpretation of the preconditioned flow. Overall, the results show that dual-space preconditioning provides a flexible mechanism for designing and analyzing operator methods beyond the standard Euclidean Lipschitz setting.

Figures & tables

Appendix figures & tables4 assets

Supplementary material from the paper’s appendix.

Appendix

Explore similar work

Aug 12, 2026

Direct Acceleration of Stochastic Root-Finding Without Variance Reduction and Regularization

Acceleration for deterministic root-finding problems has been extensively studied in recent years; specifically, the anchor-based, or Halpern-type methods achieve optimal convergence rates with respect to the operator norm. However, acceleration via these methods does not directly carry over to stochastic setting due to accumulation of errors, unless one enforces diminishing variance via increasing batch sizes or variance reduction techniques. In this work, we show that another class of acceleration, namely the dual-anchor mechanism, extends to the stochastic setting without such error accumulation, in contrast to anchor-based algorithms. Consequently, we cleanly achieve O(ε−3)O(ε^{-3}) complexity with iteration-independent batch size, without any variance reduction or double-loop recursive regularization, for stochastic root-finding (resp. fixed-point) problems with cocoercivity (resp. square-nonexpansivity) in expectation. For strongly monotone operators, the same algorithm attains a sharper O~(ε−2)\widetilde{O} (ε^{-2}) complexity, nearly matching the lower bound in terms of εε-dependence.
Mar 31, 2026

Adaptive Delayed-Update Cyclic Algorithm for Variational Inequalities

Cyclic block coordinate methods are a fundamental class of first-order algorithms, widely used in practice for their simplicity and strong empirical performance. Yet, their theoretical behavior remains challenging to explain, and setting their step sizes -- beyond classical coordinate descent for minimization -- typically requires careful tuning or line-search machinery. In this work, we develop ADUCA\texttt{ADUCA} (Adaptive Delayed-Update Cyclic Algorithm), a cyclic algorithm addressing a broad class of Minty variational inequalities with monotone Lipschitz operators. ADUCA\texttt{ADUCA} is parameter-free: it requires no global or block-wise Lipschitz constants and uses no per-epoch line search, except at initialization. A key feature of the algorithm is using operator information delayed by a full cycle, which makes the algorithm compatible with parallel and distributed implementations, and attractive due to weakened synchronization requirements across blocks. We prove that ADUCA\texttt{ADUCA} attains (near) optimal global oracle complexity as a function of target error ε>0,ε>0, scaling with 1/ε1/ε for monotone operators, or with log⁡2(1/ε)\log^2(1/ε) for operators that are strongly monotone.
Mar 11, 2026

Dual Space Preconditioning for Gradient Descent in the Overparameterized Regime

In this work, we study the convergence properties of the Dual Space Preconditioned Gradient Descent, encompassing optimizers such as Normalized Gradient Descent and Gradient Clipping. We consider preconditioners of the form ∇K\nabla K, where K:Rd×k→RK: \mathbb{R}^{d \times k} \to \mathbb{R} is convex and apply ∇K(⋅)\nabla K(\cdot) to train an over-parameterized linear model with a convex loss of the form ℓ(XW−Y)\ell(X W - Y), for weights W∈Rd×kW \in \mathbb{R}^{d \times k}, labels Y∈Rn×kY \in \mathbb{R}^{n \times k} and data X∈Rn×dX \in \mathbb{R}^{n \times d}. Under the aforementioned assumptions, we prove that the iterates of the full-batch preconditioned gradient descent converge at an exponential rate to a point W∞∈Rd×kW_{\infty} \in \mathbb{R}^{d \times k} satisfying XW∞=YXW_{\infty} = Y. We also study the implicit bias of Dual Space Preconditioned Gradient Descent. First, we demonstrate analytically and empirically that, for general K(⋅)K(\cdot), W∞W_\infty depends on the chosen constant step size, hindering a precise characterization of the implicit bias. We also provide an approximate implicit bias property for general preconditioners, namely, ∥W0−W∞∥F≤c∥W0−WGD,∞∥F\|W_0 - W_{\infty}\|_F \le c \|W_0 - W_{\text{GD}, \infty}\|_F for a constant c>0c>0 and WGD,∞W_{\text{GD}, \infty} denoting the convergence point of GD initialized at W0W_0. Furthermore, for preconditioners of the form K(G)=h(∥G∥F)K(G) = h(\|G\|_F), known as {\it isotropic preconditioners}, and for the stochastic variation of the algorithm with arbitrary batch-size, we prove linear convergence to WGD,∞W_{\text{GD}, \infty}. Finally, in the experiments, we demonstrate faster convergence on a nonlinear model obtained using the smoothed matrix elastic-net as a preconditioner.