Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userConvergence analysis of the stochastic reflected forward-backward splitting algorithm
79
0
0.0
(
0
)
Ask ChatGPT about the research
No Arabic abstract
We propose and analyze the convergence of a novel stochastic algorithm for solving monotone inclusions that are the sum of a maximal monotone operator and a monotone, Lipschitzian operator. The propose algorithm requires only unbiased estimations of the Lipschitzian operator. We obtain the rate $mathcal{O}(log(n)/n)$ in expectation for the strongly monotone case, as well as almost sure convergence for the general case. Furthermore, in the context of application to convex-concave saddle point problems, we derive the rate of the primal-dual gap. In particular, we also obtain $mathcal{O}(1/n)$ rate convergence of the primal-dual gap in the deterministic setting.
rate research
Read More
In this paper, we consider a generalized forward-backward splitting (G-FBS) operator for solving the monotone inclusions, and analyze its nonexpansive properties in a context of arbitrary variable metric. Then, for the associated fixed-point iterations (i.e. the G-FBS algorithms), the global ergodic and pointwise convergence rates of metric distance are obtained from the nonexpansiveness. The convergence in terms of objective function value is also investigated, when the G-FBS operator is applied to a minimization problem. A main contribution of this paper is to show that the G-FBS operator provides a simplifying and unifying framework to model and analyze a great variety of operator splitting algorithms, where the convergence behaviours can be easily described by the fixed-point construction of this simple operator.
We consider monotone inclusions defined on a Hilbert space where the operator is given by the sum of a maximal monotone operator $T$ and a single-valued monotone, Lipschitz continuous, and expectation-valued operator $V$. We draw motivation from the seminal work by Attouch and Cabot on relaxed inertial methods for monotone inclusions and present a stochastic extension of the relaxed inertial forward-backward-forward (RISFBF) method. Facilitated by an online variance reduction strategy via a mini-batch approach, we show that (RISFBF) produces a sequence that weakly converges to the solution set. Moreover, it is possible to estimate the rate at which the discrete velocity of the stochastic process vanishes. Under strong monotonicity, we demonstrate strong convergence, and give a detailed assessment of the iteration and oracle complexity of the scheme. When the mini-batch is raised at a geometric (polynomial) rate, the rate statement can be strengthened to a linear (suitable polynomial) rate while the oracle complexity of computing an $epsilon$-solution improves to $O(1/epsilon)$. Importantly, the latter claim allows for possibly biased oracles, a key theoretical advancement allowing for far broader applicability. By defining a restricted gap function based on the Fitzpatrick function, we prove that the expected gap of an averaged sequence diminishes at a sublinear rate of $O(1/k)$ while the oracle complexity of computing a suitably defined $epsilon$-solution is $O(1/epsilon^{1+a})$ where $a>1$. Numerical results on two-stage games and an overlapping group Lasso problem illustrate the advantages of our method compared to stochastic forward-backward-forward (SFBF) and SA schemes.
In this paper we propose a new operator splitting algorithm for distributed Nash equilibrium seeking under stochastic uncertainty, featuring relaxation and inertial effects. Our work is inspired by recent deterministic operator splitting methods, designed for solving structured monotone inclusion problems. The algorithm is derived from a forward-backward-forward scheme for solving structured monotone inclusion problems featuring a Lipschitz continuous and monotone game operator. To the best of our knowledge, this is the first distributed (generalized) Nash equilibrium seeking algorithm featuring acceleration techniques in stochastic Nash games without assuming cocoercivity. Numerical examples illustrate the effect of inertia and relaxation on the performance of our proposed algorithm.
Many problems in science and engineering involve, as part of their solution process, the consideration of a separable function which is the sum of two convex functions, one of them possibly non-smooth. Recently a few works have discussed inexa
Monotone inclusions play an important role in studying various convex minimization problems. In this paper, we propose a forward-partial inverse-half-forward splitting (FPIHFS) algorithm for finding a zero of the sum of a maximally monotone operator, a monotone Lipschitzian operator, a cocoercive operator, and a normal cone of a closed vector subspace. The FPIHFS algorithm is derived from a combination of the partial inverse method with the forward-backward-half-forward splitting algorithm. As applications, we employ the proposed algorithm to solve several composite monotone inclusion problems, which include a finite sum of maximally monotone operators and parallel-sum of operators. In particular, we obtain a primal-dual splitting algorithm for solving a composite convex minimization problem, which has wide applications in many real problems. To verify the efficiency of the proposed algorithm, we apply it to solve the Projection on Minkowski sums of convex sets problem and the generalized Heron problem. Numerical results demonstrate the effectiveness of the proposed algorithm.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
