PaperlayerView exact revision on arXiv

Source-linked AI summary

Fixed Point Strategies in Data Science

Patrick L. Combettes, Jean-Christophe Pesquet

arXiv:2008.02260v3math.OC

TL;DR

Data-science problems increasingly include equilibrium and other formulations beyond classical minimization, motivating a framework that can simplify and unify their analysis. The paper develops fixed point strategies and convergence methods, with results that include almost-sure convergence under stochastic perturbations and convergence of forward-backward splitting.

  • Problem

    Many data-science formulations, including variational inequalities, monotone inclusions, games, neural networks, and plug-and-play methods, fall outside standard minimization.

    Source: §I · p. 1

  • Method

    The paper promotes fixed point theory as a framework for modeling and analyzing data-science problems, with convergence principles and stochastic or block-based implementations.

    Source: §I · p. 1

  • Results

    The paper presents convergence guarantees, including almost-sure convergence under stochastic perturbations and convergence of forward-backward splitting for minimization.

    Source: D. Perturbed fixed point methods · p. 8, C. Convex minimization · p. 14

  • Takeaways & Limitations

    Fixed point strategies support stochastic and block-coordinate or block-iterative implementations that can reduce computational load and memory requirements.

    Source: §I · p. 1

Abstract

from arXiv · show

The goal of this paper is to promote the use of fixed point strategies in data science by showing that they provide a simplifying and unifying framework to model, analyze, and solve a great variety of problems. They are seen to constitute a natural environment to explain the behavior of advanced convex optimization methods as well as of recent nonlinear methods in data science which are formulated in terms of paradigms that go beyond minimization concepts and involve constructs such as Nash equilibria or monotone inclusions. We review the pertinent tools of fixed point theory and describe the main state-of-the-art algorithms for provably convergent fixed point construction. We also incorporate additional ingredients such as stochasticity, block-implementations, and non-Euclidean metrics, which provide further enhancements. Applications to signal and image processing, machine learning, statistics, neural networks, and inverse problems are discussed.

I. INTRODUCTION

The introduction argues that fixed point theory can unify and clarify increasingly complex data-science problems, including formulations beyond minimization. The foundations section supplies notation and convex-analysis tools used by the paper’s fixed point approaches.

I. INTRODUCTION

  • Fixed point theory is proposed as a unifying framework for data-science problems beyond classical minimization, including variational inequalities, monotone inclusions, games, neural networks, and plug-and-play methods.The framework is also presented as a source of convergence principles and stochastic or block-based implementations that can reduce computational load and memory requirements.Source: §I · p. 1

A. Notation

  • The paper’s foundations review uses Euclidean spaces and defines notation for product spaces, inner products, norms, adjoints, distances, and relative interiors.Most results are stated in Euclidean spaces, though the introduction notes that most extend to Hilbert spaces with technical adjustments.Source: A. Notation · p. 2, §I · p. 2

B. Convex analysis

  • Convex analysis supplies projection and proximity operators, subdifferentials, conjugates, and Fermat’s rule as tools for expressing minimizers.For differentiable convex functions, the gradient is the subdifferential’s single element; minimizers are characterized through the subdifferential.Source: B. Convex analysis · pp. 2–3
  • The paper also introduces proper, lower semicontinuous convex functions and the epigraph as a convex-set representation of function convexity.The figure illustrates the conjugate as a maximum signed difference between a linear function and the original function, and subgradients as affine minorants.Source: B. Convex analysis · p. 2, Figure 1 · p. 3

C. Nonexpansive operators

This section characterizes relaxations and averaged operators, relates them to other operator classes, and describes operations that preserve averagedness. It also cautions that nonexpansiveness alone does not guarantee fixed points.

C. Nonexpansive operators

  • A relaxation of T is R = Id + λ(T − Id); λ ≤ 1 gives an underrelaxation, λ ≥ 1 an overrelaxation, and λ = 2 a reflection.The section defines α-relaxation sequences for iterative methods and gives conditions on their parameters.Source: C. Nonexpansive operators · p. 3
  • An α-averaged operator can be represented as an underrelaxation of a nonexpansive operator, and firm nonexpansiveness is a special case.Proximity and projection operators, as well as their complements with respect to the identity, are firmly nonexpansive.Source: C. Nonexpansive operators · p. 4
  • Averagedness is preserved under specified relaxations, weighted averages, and compositions, providing reusable constructions for iterative algorithms.The section also gives a composition rule involving two firmly nonexpansive operators and one averaged operator.Source: C. Nonexpansive operators · p. 4
  • A nonexpansive operator may have no fixed point, one fixed point, or infinitely many, while its fixed-point set is closed and convex when nonempty.The section notes that even firmly nonexpansive operators can lack fixed points.Source: C. Nonexpansive operators · p. 5

D. Monotone operators

The section develops monotone-operator concepts and connects maximal monotonicity to firmly nonexpansive resolvents. It motivates general monotone-operator splitting through primal-dual formulations that need not correspond to minimization problems.

D. Monotone operators

  • A monotone operator’s graph obeys a pairwise inner-product inequality, and maximal monotonicity means no additional point can be added while preserving monotonicity.The section illustrates the distinction between monotone and maximally monotone graphs.Source: D. Monotone operators · p. 5, Figure 5 · p. 5
  • Subdifferentials of proper lower semicontinuous convex functions are maximally monotone, but monotone operators remain indispensable in convex minimization.The section notes that some useful monotone inclusions do not arise from minimization.Source: D. Monotone operators · p. 6
  • For a maximally monotone operator, its resolvent is everywhere defined, single-valued, and firmly nonexpansive; conversely, firmly nonexpansive operators are resolvents of maximally monotone operators.The proximity operator of a convex function is the resolvent of its subdifferential.Source: D. Monotone operators · p. 6
  • A primal-dual formulation can be rewritten as a maximally monotone inclusion with a skew operator, enabling splitting without a corresponding minimization problem.The passage reports applications of this framework to image restoration and empirical mode decomposition.Source: D. Monotone operators · p. 6

III. FIXED POINT ALGORITHMS

The section reviews fixed-point construction algorithms and develops basic iterations, fixed-point selection, and block operator updates. Across these methods, convergence depends on the stated operator and iteration conditions.

III. FIXED POINT ALGORITHMS

  • The section surveys the main algorithms for constructing fixed points.It then develops basic iteration schemes, selection methods, and block operator updates.Source: §III · p. 6

A. Basic iteration schemes

  • For averaged operators with a nonempty fixed-point set, relaxed iterations converge to a fixed point, whereas unrelaxed successive approximation can fail for a nonexpansive operator.A Banach contraction has a unique fixed point; the section also treats compositions of averaged operators and iteration-dependent composites.Source: A. Basic iteration schemes · pp. 6–7

B. Algorithms for fixed point selection

  • Fixed-point selection methods target a minimizer of a strictly convex function over Fix T, and the stated algorithm converges to the solution when the problem is solvable.The paper notes signal interpolation and machine learning [186] as settings for such formulations.Source: B. Algorithms for fixed point selection · p. 7

C. A fixed point method with block operator updates

  • Block updates avoid activating all m operators at every iteration and converge under the theorem’s conditions; if some T_i is a Banach contraction, convergence is linear to the unique solution.Each operator must be evaluated at least once in any M consecutive iterations.Source: C. A fixed point method with block… · pp. 7–8

D. Perturbed fixed point methods

The section extends fixed-point methods to perturbed and randomized iterations, then applies splitting strategies to monotone-operator inclusions. The results give convergence under the stated assumptions, with some methods trading operator conditions for lower per-iteration cost.

D. Perturbed fixed point methods

  • With the stated conditional second-moment condition, the stochastically perturbed averaged-operator iteration converges almost surely to a fixed point.The errors model settings where exact operator evaluations are not possible.Source: D. Perturbed fixed point methods · p. 8

E. Random block-coordinate fixed point methods

  • Random block-coordinate updates can converge almost surely to a fixed point when every coordinate has positive activation probability and the stated independence conditions hold.Random activation addresses the loss of nonexpansiveness that coordinate sampling can cause.Source: E. Random block-coordinate fixed point… · p. 8

A. Splitting sums of monotone operators

  • For zeros of a sum of two maximally monotone operators, Douglas–Rachford, Tseng, and forward-backward splitting methods are presented with convergence results under their respective assumptions.Forward-backward splitting applies when one operator is cocoercive; Tseng splitting instead assumes the single-valued operator is Lipschitzian.Source: A. Splitting sums of monotone operators · pp. 8–9
  • For a three-operator inclusion with a monotone Lipschitz operator, one splitting method converges in both primal and dual variables; an alternative requires cocoercivity and uses one C evaluation per iteration.The alternative also imposes constant proximal parameters.Source: A. Splitting sums of monotone operators · pp. 9–10

B. Splitting sums of composite monotone operators

The section recasts composite monotone inclusions so splitting methods can handle many operators through individual operator steps or reformulations in larger spaces. Under stated assumptions, the resulting iterations converge, and selected preconditioned formulations avoid inverting linear operators.

B. Splitting sums of composite monotone operators

  • Reformulating the inclusion in a larger product space reduces the number of set-valued operators handled directly to at most two.The construction groups the component operators and linear couplings into product-space operators.Source: B. Splitting sums of composite… · p. 10
  • When the smooth operators are cocoercive and the stated invertibility and relaxation conditions hold, the iteration converges to a solution of (65).The method updates q operator-specific variables using resolvents and a shared primal update.Source: B. Splitting sums of composite… · p. 10
  • For Problem 55, a primal-dual iteration converges to a solution under the stated assumptions on the maximally monotone operators and linear maps.The iteration uses operator resolvents and updates the primal and dual variables.Source: B. Splitting sums of composite… · pp. 10–11
  • Preconditioned formulations also converge to solutions of Problem 55 under their stated assumptions, and formulations (73) and (78) do not require linear-operator inversions.Alternative metric operators yield different primal-dual algorithms.Source: B. Splitting sums of composite… · p. 11

C. Block-iterative algorithms

The section presents block-iterative algorithms for coupled inclusion systems and then models convex and split feasibility problems using fixed points. The methods allow partial updates or avoid difficult projections while retaining convergence under their stated conditions.

C. Block-iterative algorithms

  • The block-iterative method permits partial activation of both operator families, individual iteration-dependent proximal parameters, and requires neither linear-operator inversions nor norm knowledge.Each operator index must be used at least once within every M consecutive iterations; the resulting sequence converges to a solution of Problem 59.Source: C. Block-iterative algorithms · pp. 11–12

V. FIXED POINT MODELING OF MINIMIZATION PROBLEMS

  • The paper places these methods among fixed-point applications to minimization problems and describes feasibility as compliance with finitely many convex constraints.The convex feasibility formulation is associated with signal recovery.Source: §V · p. 12, A. Convex feasibility problems · p. 12

A. Convex feasibility problems

  • For convex feasibility, composing averaged operators whose fixed-point sets model the constraint sets yields convergence to a feasible point; projections give the classical POCS algorithm.The result assumes the feasibility problem has a solution.Source: A. Convex feasibility problems · p. 12

B. Split feasibility problems

  • In split feasibility, replacing projection onto the typically intractable preimage L^-1(D) with an operator using L and projection onto D gives a convergent method.The construction converges to a solution when one exists and the stated step-size conditions hold.Source: B. Split feasibility problems · pp. 12–13

C. Convex minimization

The section expresses convex minimization problems through fixed points and develops convergent proximal, splitting, gradient, and projection methods. It extends these approaches to smooth sums and composite objectives, including matrix recovery and data-analysis models.

C. Convex minimization

  • The proximal point algorithm converges to a minimizer by iterating the proximity operator of a convex function.The result assumes the function has at least one minimizer.Source: C. Convex minimization · p. 13
  • The Douglas-Rachford splitting method converges for a sum of two convex functions and applies their proximity operators separately.The section gives matrix applications including graphical lasso and robust PCA.Source: C. Convex minimization · pp. 13–14
  • Forward-backward splitting converges for Problem 66 when one function is differentiable with a Lipschitz gradient, combining a gradient step with a proximity step.The cited result allows step sizes in [ε, 2/(δ(1 + ε))].Source: C. Convex minimization · p. 14
  • Projected-gradient iterations converge for constrained smooth minimization under the stated coercivity-or-boundedness condition.Alternating projections arise as a special case when one set is bounded.Source: C. Convex minimization · p. 15
  • For a sum with multiple smooth functions, block updates converge; if one function is strongly convex, convergence is linear to the unique solution.The updates use subsets of functions that satisfy the stated recurring-activation condition.Source: C. Convex minimization · p. 15
  • A flexible composite minimization model covers multiple nonsmooth terms, linear operators, and smooth losses, with fixed-point splitting algorithms applicable under a qualification condition.The section also relates this model to ADMM and gives a denoising formulation as an instance.Source: C. Convex minimization · pp. 15–16

D. Inconsistent feasibility problems

For potentially inconsistent feasibility constraints, the section replaces exact feasibility with a weighted relaxation that keeps the hard constraint. Under stated conditions, a block-update algorithm converges to a solution of the relaxed problem.

D. Inconsistent feasibility problems

  • When modeling errors make the feasibility constraints potentially inconsistent, the formulation relaxes them with weighted distance penalties while retaining C as a hard constraint.If the original constraints are feasible, their solutions are the only solutions to the relaxed problem.Source: D. Inconsistent feasibility problems · p. 16
  • The relaxed formulation is cast as an instance of Problem 75, and its block-update algorithm converges under the stated boundedness condition.The condition holds when C is bounded or when some Di is bounded and its corresponding Li is invertible.Source: D. Inconsistent feasibility problems · p. 16

E. Stochastic forward-backward method

The paper extends forward-backward methods to stochastic approximations and develops optimization algorithms that update randomly selected blocks. It gives convergence results under stated conditions and notes benefits from block-specific step sizes.

E. Stochastic forward-backward method

  • The stochastic forward-backward scheme allows approximations to the objective function and gradient, as well as an additive random error.With the function approximation and additive error removed and the step weight set to one, it recovers stochastic gradient descent.Source: E. Stochastic forward-backward method · p. 17
  • An incremental proximal stochastic gradient specialization samples one component gradient at each iteration.It uses the full nonsmooth function f while selecting a random component i(n) from the differentiable terms.Source: E. Stochastic forward-backward method · p. 17
  • Under Theorem 83’s stated assumptions, stochastic forward-backward iterates converge almost surely to a random variable in the minimizer set.The theorem assumes, among other conditions, a nonempty solution set and controls on the step sizes and stochastic errors.Source: E. Stochastic forward-backward method · p. 17
  • Inertial parameters and primal-dual formulations are identified as extensions of stochastic optimization approaches.The stochastic forward-backward iteration is also related to a fixed-point iteration when the gradient is Lipschitzian.Source: E. Stochastic forward-backward method · p. 17

F. Random block-coordinate optimization algorithms

  • Random block-coordinate algorithms update randomly selected variable blocks and, under stated assumptions, converge almost surely to a random variable in the solution set.The paper also gives a block-coordinate forward-backward scheme when the relevant functions are differentiable.Source: F. Random block-coordinate… · pp. 17–18
  • Block-coordinate forward-backward permits a distinct step parameter for each component, which was observed to benefit convergence profiles in applications.Source: F. Random block-coordinate… · p. 18

G. Block-iterative multivariate minimization algorithms

These sections extend fixed-point methods to block-iterative minimization, Bregman distances, and equilibrium formulations. They also show how POCS cycles can be understood as equilibria even when they lack a minimization interpretation.

G. Block-iterative multivariate minimization algorithms

  • A block-iterative primal-dual method produces sequences converging to solutions of both the primal and dual minimization problems.The method specializes a splitting algorithm by replacing resolvents with proximal operators.Source: G. Block-iterative multivariate… · p. 18

H. Splitting based on Bregman distances

  • Bregman splitting can converge in instances where the standard forward-backward method cannot be used because the gradient is not Lipschitzian.Bregman proximal points can also be easier to compute than standard quadratic proximal points for some functions.Source: H. Splitting based on Bregman distances · p. 18

VI. FIXED POINT MODELING OF NASH EQUILIBRIA

  • A Nash equilibrium is characterized as a fixed point of the set-valued best-response operator, covering problems whose solutions are not generally modeled by standard minimization.The paper describes such action-profile problems in settings including signal recovery, telecommunications, machine learning, network science, and control.Source: §VI · p. 19

A. Cycles in the POCS algorithm

  • For consistent feasibility, POCS converges to a solution; when the sets are inconsistent, its iterates instead form a cycle that is an equilibrium without a minimization interpretation.For three sets, Fig. 6 depicts the cycle as (x1, x2, x3).Source: A. Cycles in the POCS algorithm · p. 19, Figure 6 · p. 19

B. Proximal cycles

Proximal cycles generalize projection-based cycles by allowing each player’s self-loss to be represented by a convex function. The paper then formulates Nash-equilibrium problems as monotone inclusions and gives splitting algorithms with convergence results under specified conditions.

B. Proximal cycles

  • Proximal cycles replace each set indicator with a convex self-loss function, and each player’s best response becomes a proximal operator.The corresponding monotone-inclusion and fixed-point representations of projection-based cycles continue to hold.Source: B. Proximal cycles · p. 20

C. Construction of Nash equilibria

  • Under Assumption 88, the Nash-equilibrium problem can be represented as a monotone inclusion and solved using a splitting scheme.The paper gives a convergence result for the resulting algorithm under the additional conditions of Proposition 89.Source: C. Construction of Nash equilibria · p. 20
  • A second splitting result also gives convergence of the players’ iterates to a solution under its stated assumptions.This scheme uses proximal steps for the player-specific functions and a shared function.Source: C. Construction of Nash equilibria · p. 21
  • The example’s smooth terms satisfy the Lipschitz condition but need not satisfy cocoercivity, so the cocoercivity-based three-operator splitting route does not apply there.The text notes failure of cocoercivity when both smooth functions are zero.Source: C. Construction of Nash equilibria · p. 21

VII. FIXED POINT MODELING OF OTHER NON-MINIMIZATION PROBLEMS

The paper models feedforward networks as compositions of affine maps and activation operators, then uses fixed-point theory to analyze their averagedness and Lipschitz behavior. It also connects recurrent networks to fixed points and inclusion systems.

A. Neural network structures

  • A feedforward network composes affine layers with activation operators, and suitable conditions on the weight matrices can make the network averaged.Each layer applies a linear weight operator, bias, and activation operator.Source: A. Neural network structures · pp. 21–22
  • A recurrent network converges to a fixed point under the stated condition when its step parameters form an α-relaxation sequence.When the activations are proximity operators, the network asymptotically delivers a solution to a system of inclusions.Source: A. Neural network structures · p. 22
  • The paper derives a network Lipschitz bound that is more accurate than multiplying individual layer bounds; separable activations can yield tighter estimates.When all weight matrices have nonnegative components, the norm of their product is a Lipschitz constant for the network.Source: A. Neural network structures · p. 22
  • Unrolling a fixed-point algorithm yields a network whose algorithm and problem parameters can be optimized from training data using differentiable programming.The cited results can then characterize the resulting network’s nonexpansiveness properties.Source: A. Neural network structures · p. 22

B. Plug-and-play methods

Fixed point strategies provide a framework for analyzing and solving data-science problems, including methods beyond classical minimization. The section applies this framework to plug-and-play methods, adjoint mismatch, and nonlinear observations.

B. Plug-and-play methods

  • Plug-and-play algorithms replace a proximity operator with a denoiser Q, but their solution properties are generally elusive.Forward-backward and Douglas-Rachford iterations converge under averagedness and relaxation conditions, when their fixed-point sets are nonempty.Source: B. Plug-and-play methods · p. 23

C. Adjoint mismatch problem

  • Replacing the adjoint H* with an approximation K addresses physical or computational limitations, but the resulting surrogate need not solve a minimization problem.When L = K ◦ H + κId is cocoercive, the surrogate is a forward-backward splitting instance; it is generally not a gradient when L is not a gradient.Source: C. Adjoint mismatch problem · p. 23

D. Problems with nonlinear observations

  • For nonlinear observations R_k x = r_k, proxifiable operators yield firmly nonexpansive maps whose common fixed points solve the recovery task.The construction uses T_k = S_k ◦ R_k + Id − S_k ◦ R_k; the text also describes broader fixed-point models that require neither optimization nor monotone inclusions.Source: D. Problems with nonlinear observations · p. 24

VIII. CONCLUDING REMARKS

  • The paper concludes that fixed point theory can model and solve data-science problems ranging from minimization to Nash equilibria, monotone inclusions, and nonlinear operator equations.Averaged operators support provably convergent iterations, while monotone operators underpin many modeling approaches.Source: §VIII · p. 24
Loading 2008.02260v3…