Source-linked AI summary
Finite-sample guarantees for data-driven operator splitting methods via martingale inequalities
Andrea Martin, Filippo Fabiani, Giuseppe Belgioioso
TL;DR
When a forward operator evaluation is unavailable or costly, finite noisy samples are used, but existing stability-based residual analyses may not yield excess that vanishes with sample size. This paper derives distribution-free finite-sample Davis-Yin residual certificates using martingale inequalities, with improved iteration dependence under linear convergence.
Problem
Stability analyses based on surrogate losses may yield residual certificates whose statistical excess need not vanish with sample size, motivating asymptotically consistent finite-sample certificates.
Source: §I · p. 1Method
Results
Takeaways & Limitations
The certificates quantify the true residual of a data-driven Davis-Yin output by controlling the sample-average error at that output.
Source: §III · p. 3, §V · p. 9The analysis assumes i.i.d. samples; relaxing that assumption is left for future work.
Source: §V · p. 9
Abstract
from arXiv · showhide
Operator splitting methods are a fundamental class of algorithms for solving structured monotone inclusion problems arising in optimization, control, and game theory. We consider the case, common in stochastic regimes, where the forward evaluation of one of the constituent operators is either unavailable in closed form or computationally expensive to evaluate, and is therefore approximated using a finite number of noisy oracle samples. We establish distribution-free, finite-sample certificates for the quality of the output produced by data-driven Davis-Yin splitting algorithms. Unlike previous works, our analysis directly controls the residual error via martingale inequalities instead of relying on algorithmic stability arguments for a tailored surrogate loss, yielding the first a priori certificates whose statistical excess provably vanishes with the sample size. We further show that, under linear convergence of the Davis-Yin splitting algorithm, the dependence of our bounds on the iteration count improves from linear growth to exponential decay. We validate our theoretical results on a stochastic portfolio optimization problem with uncertain asset returns.
I. INTRODUCTION
Operator splitting reduces structured monotone inclusion problems to simpler subproblems, but stochastic operator evaluations may be unavailable without samples. Existing approaches largely study asymptotic convergence, while this paper develops finite-sample residual certificates for data-driven Davis-Yin splitting.
I. INTRODUCTION
- Finite-sample residual certification matters when an unknown distribution makes required operator evaluations unavailable exactly and generating new samples is costly.The paper cites uncertain demand, uncertain asset returns, and random input-output data as examples.Source: §I · p. 1
- Prior SAA and SA work mainly studies asymptotic convergence as the total number of samples grows unbounded, not accuracy with limited data.SAA uses an empirical average; SA draws new samples at each iteration, reducing per-iteration cost but introducing noise and typically requiring step-size rules and additional convergence assumptions.Source: §I · p. 1
- Stability analyses have been extended to operator splitting, but surrogate-loss residual guarantees may have statistical excess that does not vanish with sample size.The paper frames asymptotically consistent finite-sample residual certification as the open question.Source: §I · p. 1
- The paper answers this question for Davis-Yin splitting with a priori finite-sample certificates based on a Doob martingale and martingale concentration inequalities.A novel replace-one sensitivity bound is combined with martingale inequalities; under linear convergence, its iteration-count dependence improves from linear growth to exponential decay.Source: §I · p. 2
II. PROBLEM FORMULATION
The paper studies monotone inclusions whose forward operator evaluation is approximated from a finite i.i.d. dataset. It asks for a high-probability bound on the true Davis-Yin residual of the data-driven output.
II. PROBLEM FORMULATION
- The target is to find x such that 0 belongs to A(x) + B(x) + C(x), with A and B maximally monotone and C single-valued and cocoercive.The paper assumes the inclusion has a nonempty zero set.Source: §II · p. 2
- Davis-Yin splitting treats A and B through separate resolvents and evaluates C in a forward step; its fixed-point iteration converges under the stated step-size range.For γ in (0, 2θ), the fixed-point operator is averaged and the associated iterates converge as described in the paper.Source: §II · p. 2
- The forward evaluation of C is replaced by a sample-average approximation formed from N i.i.d. oracle samples.The resulting data-driven iteration is deterministic conditional on the dataset and invariant to permutations of its samples.Source: §II · p. 2
- The goal is a radius ε that bounds the true fixed-point residual of the data-driven output with probability at least 1 − δ.The paper also interprets this as an inclusion certificate: one exact Davis-Yin step yields points within γε and operator values satisfying the inclusion up to error ε.Source: §II · pp. 2–3
III. MAIN RESULTS
The main statistical challenge is controlling the sample-average error at an output computed from the same data. The analysis relates the true residual to the empirical residual and bounds the algorithm's sensitivity to replacing a sample.
III. MAIN RESULTS
- The true Davis-Yin residual is bounded using the empirical residual together with the sample-average error evaluated at the data-dependent output.The empirical residual is computable, so certification reduces to controlling that statistical error.Source: §III · p. 3
- At the output, the sample-average error involves random vectors that are generally neither independent nor individually centered because the evaluation point uses the same dataset.This distinguishes the analysis from evaluating the error at a deterministic point.Source: §III · p. 3
- The replace-one sensitivity analysis compares outputs from datasets differing in one sample, and the resulting sensitivity grows at most linearly with iteration count and decays at least as fast as 1/N with sample size.The analysis uses nonexpansiveness of the empirical fixed-point operators and the oracle sensitivity bound to establish the comparison.Source: §III · pp. 3–4
- The sensitivity bound is used to derive distribution-free finite-sample certificates for the sample-average error using stability arguments and martingale inequalities.The paper presents these as two approaches to controlling the error term in the residual bound.Source: §III · p. 4
A. A posteriori certificates via algorithmic stability
The section derives a distribution-free, high-probability residual certificate using algorithmic stability and a surrogate loss. Its statistical correction vanishes with sample size, but the certificate generally need not become asymptotically consistent.
A. A posteriori certificates via algorithmic stability
- The analysis bounds SAA error through a scalar surrogate loss, then uses replace-one sensitivity to derive uniform stability and a generalization bound.The population loss is unavailable directly because the underlying distribution is unknown.Source: A. A posteriori certificates via… · p. 4
- The stability-based certificate is distribution-free and high-probability, but generally fails to be asymptotically consistent.The generalization correction vanishes for fixed iteration count, while the empirical surrogate loss need not vanish.Source: A. A posteriori certificates via… · pp. 4–5
- For fixed K, the stability correction decays at rate 1/√N up to logarithmic factors, but sample-wise oracle dispersion need not converge to zero.Thus, increasing sample size alone does not generally make the stability certificate arbitrarily small.Source: A. A posteriori certificates via… · p. 5
- In a balanced Rademacher-noise example, the SAA matches the true operator and the residual is zero, yet the certificate radius can be arbitrarily large.The surrogate takes norms before averaging, preventing cancellation between opposite-signed oracle errors.Source: A. A posteriori certificates via… · p. 5
B. A priori certificates via martingale inequalities
The section derives an a priori finite-sample certificate by controlling SAA error directly with a Doob martingale rather than a surrogate loss. Replace-one sensitivity bounds and martingale concentration yield a high-confidence residual certificate using quantities known before execution.
B. A priori certificates via martingale inequalities
- The method directly controls SAA error by forming a Doob martingale and bounding its initial value and increments using replace-one sensitivity.Martingale concentration inequalities then provide the finite-sample bound.Source: B. A priori certificates via… · pp. 5–6
- Theorem 2 bounds SAA error and consequently the true DY residual with probability at least 1 − δ.The resulting certificate holds at arbitrarily high confidence regardless of the data distribution.Source: B. A priori certificates via… · pp. 6–7
- Unlike the stability certificate's dataset-dependent loss term, the a priori bound uses quantities known before the data-driven iteration runs.The section states that the residual guarantee holds with arbitrary confidence irrespective of the distribution.Source: B. A priori certificates via… · p. 7
C. Improved bounds under linear convergence
Under Assumption 4, linear convergence of Davis–Yin splitting improves the replace-one sensitivity bound from linear growth in the iteration count to exponential decay. The refined sensitivity yields improved finite-sample residual guarantees, with a remaining exponentially decaying iteration dependence.
C. Improved bounds under linear convergence
- Assumption 4 requires at least one of A, B, or C to be strongly monotone and at least one of A or B to be Lipschitz continuous.Under this assumption, the DY trajectories converge exponentially toward their respective fixed-point sets.Source: C. Improved bounds under linear… · p. 7
- The refined sensitivity compares outputs from neighboring datasets initialized at the same point and depends on the maximum initial distance d0 to the empirical fixed-point sets.The bound also uses the sum of the strong-monotonicity constants, μ̄ = μA + μB + μC.Source: C. Improved bounds under linear… · p. 7
- With linear convergence, the replace-one sensitivity bound improves from linear growth in K to exponential decay, so it no longer deteriorates as the iteration budget increases.The resulting sensitivity bound can be substituted into the finite-sample fixed-point residual guarantees.Source: C. Improved bounds under linear… · pp. 7–8
- Assumption 4 does not ensure DY contractivity, so the sensitivity bound retains an exponentially decaying dependence on K rather than removing iteration-count dependence altogether.Substituting the refined bound into the paper’s certificates improves the finite-sample guarantees for the fixed-point residual.Source: C. Improved bounds under linear… · p. 8
IV. NUMERICAL EXPERIMENTS
The numerical study applies data-driven DY splitting to portfolio optimization with uncertain asset returns and examines residual certificates as sample size grows. The true residual initially falls and then flattens, while the a priori certificate becomes asymptotically tight and the a posteriori certificate plateaus.
IV. NUMERICAL EXPERIMENTS
- The experiment allocates capital across 10 assets to minimize investment risk while ensuring expected return of at least r ≥ 0, with returns modeled as R = m + ξ.The model also includes a regularization term encouraging investment diversity.Source: §IV · p. 8
- The portfolio DY updates can be computed in nearly closed form, making them more computationally efficient than forward-backward methods, especially for large instances.The simulation unrolls 50 iterations over sample sizes from 10^1 to 10^18.Source: §IV · pp. 8–9
- Because asset-return distributions are unknown, the method replaces the forward evaluation with a sample-average approximation built from finite oracle samples.The oracle samples are generated from a normalized dense factor covariance model and satisfy the stated unbiasedness and cocoercivity properties.Source: §IV · p. 8
- 3.6 · 10^-4 is the approximate plateau of the true fixed-point residual after it initially decreases with sample size.Figure 1 shows the residual as a function of sample count, with a shaded envelope over 1,000 dataset draws.Source: §IV · p. 9, Figure 1 · p. 9
- The a priori certificate’s correction term converges to zero, yielding asymptotically tight bounds, while the a posteriori certificate plateaus at approximately 0.112.The reported plateau is attributed to the non-vanishing term ℓ̂D.Source: §IV · p. 9
V. CONCLUSION
The paper analyzes data-driven DY splitting when a constituent operator is approximated by a finite-sample SAA. It uses martingale inequalities to establish asymptotically consistent a priori residual certificates and identifies extensions for future work.
V. CONCLUSION
- Conditional expectations of the SAA error along the sample filtration form a Doob martingale, enabling asymptotically consistent a priori residual certificates via martingale inequalities.The certificates are established under different monotonicity assumptions on the operators.Source: §V · p. 9
- Bounding residual error through the expected surrogate loss can yield conservative certificates whose statistical excess need not shrink with sample size.The paper instead controls the SAA error at the data-driven algorithm’s output.Source: §V · p. 9
- Future work includes extending the analysis to other data-driven splitting algorithms, relaxing i.i.d. sampling, and studying stochastic approximations that draw fresh samples each iteration.Source: §V · p. 9