Home / Curated / Algorithms / RandProx (Primal-Dual Optimization with Randomized Proximal Updates)

RandProx (Primal-Dual Optimization with Randomized Proximal Updates)

Algorithms AIMech:RandProxPrimalDualOptimizationWithRandomizedProximalUpdates DRAFT

Aliases: RandProx, Randomized Primal-Dual Proximal Splitting, RandProx-Minibatch, RandProx-FL

A variance-reduced randomized primal-dual proximal splitting algorithm (Condat & Richtarik 2023, Sections 2-3, Equations 4-11, Algorithm 1) for composite monotone inclusion and convex optimization min_x {f(x) + g(x) + h(K x)} that generalizes Primal-Dual Davis-Yin (PDDY) by replacing the deterministic dual proximity step hat_u^{t+1} = prox_{tau h*}(u^t + tau K hat_x^t) with an underrelaxed unbiased randomized operator update u^{t+1} = u^t + (1 / (1 + omega)) R^t(hat_u^{t+1} - u^t) satisfying E[R^t(r)] = r and E[||R^t(r) - r||^2] <= omega ||r||^2, followed by the primal correction x^{t+1} = hat_x^t - gamma (1 + omega) K*(u^{t+1} - u^t).

Identity Notes & Concept Scope Distinct from ProxSkip / Scaffnew (AIMech:ProxSkipLocalGradientStepsWithAcceleratedCommunicationSkipping, Mishchenko et al. 2022), which is recovered as the special case of RandProx where g = 0, K = I, h is a single indicator/regularization function, and R^t is a Bernoulli coin flip, whereas RandProx handles a third composite term g(x), arbitrary bounded linear operators K, multi-block separable sum structures h_m(K_m x), and general unbiased stochastic compression/sampling operators R^t.

Claims & Grounded Evidence

4 Claims

Mechanism #r451-randomized-dual-proximal-update-and-variance-reduction-mechanism

Because the randomized operator R^t is applied to the dual difference hat_u^{t+1} - u^t, which converges to zero as (x^t, u^t) -> (x*, u*) where u* in partial h(K x*) and 0 in nabla f(x*) + partial g(x*) + K* u*, the variance E[||R^t(hat_u^{t+1} - u^t) - (hat_u^{t+1} - u^t)||^2] <= omega ||hat_u^{t+1} - u^t||^2 vanishes automatically at the solution without external control variates, achieving linear convergence E[Psi^t] <= c^t Psi^0 for strongly convex f (Theorems 1-3).

supports Source: RandProx: Primal-Dual Optimization Algorithms with Randomized Proximal Updates · Locator: Section 3.1 Presentation of RandProx & Section 3.2 Linear Convergence (Theorems 1-3, Equations 5-11), pp. 4-6

Mechanism #r451-unification-of-point-saga-proxskip-splitskip-and-randprox-fl

Varying the operator R^t (Bernoulli skip, coordinate/block sampling, unbiased vector quantization/sparsification) and problem splitting (f, g, h, K) unifies Point-SAGA, Stochastic Decoupling Method (SDM), ProxSkip, SplitSkip, and communication-skipped + compressed federated learning (RandProx-FL and RandProx-Minibatch, Section 5, Algorithms 3-4, Theorems 10-11).

supports Source: RandProx: Primal-Dual Optimization Algorithms with Randomized Proximal Updates · Locator: Section 4 Special Cases of RandProx & Section 5 Application to Federated Learning (Algorithms 3-4, Theorems 10-11), pp. 6-9

Limitation #r451-primal-dual-step-size-coupling-and-operator-norm-limitation

Linear convergence requires step sizes gamma in (0, 2/L_f) and tau > 0 to satisfy the coupled stability bound gamma * tau * (1 + omega) * ||K||^2 <= 1 (or block-weighted norms under coordinate sampling), requiring knowledge of the variance factor omega and operator norm ||K||.

supports Source: RandProx: Primal-Dual Optimization Algorithms with Randomized Proximal Updates · Locator: Section 3.2 Theorem 1 & Theorem 2 Step-Size Conditions, pp. 5-6

Application #r451-composite-splitting-and-compressed-federated-optimization-application

Applied to composite convex splitting with costly proximal or linear operators and to federated learning combining local training steps, partial client participation, and uplink communication compression.

supports Source: RandProx: Primal-Dual Optimization Algorithms with Randomized Proximal Updates · Locator: Section 5 Application to Federated Learning & Appendix Experiments, pp. 8-9

⚠️ Curated Limitations & Negative Results

Requires step sizes gamma and tau to satisfy the coupled operator-norm and randomization-variance inequality gamma * tau * (1 + omega) * ||K||^2 <= 1.
Exact linear convergence guarantees require strong convexity of f (and/or smooth h* / dual strong convexity).

Artificial Intelligence Ontology (AIO) Grounding

Mapped AIO Classes

AIO Target Class	Mapping Relation	Mapping Rationale
`AIO:FederatedLearning` Federated Learning	related_match	RandProx is a primal-dual optimization framework with randomized proximal updates that directly yields communication-skipping and compressed federated learning algorithms (RandProx-FL, RandProx-Minibatch).

Evidence Sources & Primary Literature

3 Sources

Source ID	Publication / Document	Type / Access	Reference & Checksum
`r451-primary-pdf`	RandProx: Primal-Dual Optimization Algorithms with Randomized Proximal Updates Laurent Condat, Peter Richtarik	primary paper full_text	ID: https://openreview.net/forum?id=332bf12183 sha256:5e7df8fc76bf…
`r451-arxiv-abs`	RandProx: Primal-Dual Optimization Algorithms with Randomized Proximal Updates (arXiv abstract) Laurent Condat, Peter Richtarik	primary paper abstract_only	ID: https://arxiv.org/abs/2207.12891 sha256:2a65d00c2f11…
`r451-metadata-cr`	RandProx: Primal-Dual Optimization Algorithms with Randomized Proximal Updates (Crossref metadata) Laurent Condat, Peter Richtarik	primary paper abstract_only	ID: https://openreview.net/forum?id=332bf12183 sha256:66f6328c3fdc…

Ontology & Grounding Topology

Open in interactive network graph →

Curation Provenance

Curator: Antigravity

Method: ai_assisted

Model: Gemini

Created: 2026-10-19T08:54:00Z

Updated: 2026-10-19T08:54:00Z

Source File: data/curated/RandProxPrimalDualOptimizationWithRandomizedProximalUpdates.yaml · Schema: curated_concept.yaml

Explore across X-Mech

Related computational & biological Mechs: Embedding Map Network Graph ProteinTraitsMech (ESM-2 pLM) DUFMech (Domain pLM) TraitMech CultureMech All 14 X-Mech Repositories