PaperlayerView exact revision on arXiv

Source-linked AI summary

Randomized Methods for Design of Uncertain Systems: Sample Complexity and Sequential Algorithms

T. Alamo, R. Tempo, A. Luque, D. R. Ramirez

arXiv:1304.0678v2eess.SYmath.OC

TL;DR

Uncertain-system design can be computationally difficult, motivating randomized methods with probabilistic guarantees. The paper derives binomial-based sample-complexity bounds and introduces SPV, whose validation strategy supports probabilistically accurate and confident solutions while addressing limitations of strict validation.

  • Problem

    Uncertain-system design involves semi-infinite optimization problems that are often NP-hard, while deterministic relaxations may be overly conservative.

  • Method

    The paper derives binomial-tail sample-complexity bounds and proposes Sequential Probabilistic Validation (SPV), which validates candidate solutions sequentially.

  • Results

    The paper provides sample-complexity results for uncertain-system analysis and design and shows that non-strict SPV validation can reduce iterations in some cases.

  • Takeaways & Limitations

    Randomized analysis and design can provide probabilistic specifications for uncertain systems, while relaxed validation addresses situations where strict validation is inappropriate.

  • Takeaways & Limitations

    Strict validation may fail to obtain a probabilistic solution when the robust feasible set is empty even though solutions with violation probability at most η exist.

Abstract

from arXiv · show

In this paper, we study randomized methods for feedback design of uncertain systems. The first contribution is to derive the sample complexity of various constrained control problems. In particular, we show the key role played by the binomial distribution and related tail inequalities, and compute the sample complexity. This contribution significantly improves the existing results by reducing the number of required samples in the randomized algorithm. These results are then applied to the analysis of worst-case performance and design with robust optimization. The second contribution of the paper is to introduce a general class of sequential algorithms, denoted as Sequential Probabilistic Validation (SPV). In these sequential algorithms, at each iteration, a candidate solution is probabilistically validated, and corrected if necessary, to meet the required specifications. The results we derive provide the sample complexity which guarantees that the solutions obtained with SPV algorithms meet some pre-specified probabilistic accuracy and confidence. The performance of these algorithms is illustrated and compared with other existing methods using a numerical example dealing with robust system identification.

1 Introduction

The paper addresses computationally difficult uncertain-system design using randomized methods with probabilistic guarantees. It derives improved sample-complexity results and introduces SPV, a sequential validation scheme that permits limited validation violations.

  • Motivation: Randomized algorithms address uncertain-system design problems whose semi-infinite formulations are often NP-hard.Deterministic relaxations may be conservative, while probabilistic methods can produce polynomial-time solutions with probabilistic guarantees.
  • Related methods: Non-sequential methods use sampled constraints with an a priori sample size, but their worst-case bounds can be overly conservative.The bounds grow at least linearly with the number of decision variables.
  • Sequential methods: Sequential validation tests each candidate on a random validation set and terminates when all sampled design specifications are satisfied.The validation-set cardinality increases only mildly at each iteration while retaining probabilistic specifications.
  • Contributions: The paper derives sample complexity for uncertain-system analysis and design, including finite families and robust convex optimization, reducing the required number of samples.The results use bounds on the tail of the binomial distribution and apply to worst-case performance and constraint violation.
  • Contributions: SPV allows candidate solutions to violate specifications for one or more validation-set members, addressing soft constraints or infeasible strict specifications.The paper combines sample-complexity results with SPV algorithms and compares approaches in a robust identification example.

2 Problem Statement

The problem statement formalizes probabilistic violation for uncertain-system design and connects sampled optimization with guarantees on candidate solutions. The framework targets solutions whose violation probability is at most η with confidence at least 1−δ.

  • Problem formulation: The framework assumes a probability measure over the uncertainty space and uses N independent identically distributed samples.The parameters η and δ denote probabilistic accuracy and confidence, respectively.
  • Problem formulation: The robust optimization problem minimizes controller performance J(θ) subject to constraint satisfaction for every uncertainty realization.The uncertainty is bounded in W, while θ belongs to the design-parameter set Θ.
  • Problem formulation: A design parameter θ satisfies a binary constraint for a subset of uncertainty realizations, quantified by its probability of violation E(θ).The probability of violation is defined as Pr_W{g(θ,w)=1}.
  • Sampled optimization: Randomized methods replace the original infinitely constrained problem with an optimization problem containing constraints evaluated on sampled uncertainty realizations.The sampled problem may also allow at most m violations, producing a probabilistic relaxation.
  • Probabilistic guarantees: The probability of failure p(N,η,m) measures whether the non-conforming feasible set is nonempty, and the goal is to choose N so that p(N,η,m)≤δ.When that set is empty, every feasible solution satisfies E(θ)≤η with probability 1−p(N,η,m).

3 Sample complexity for the binomial distribution

This section develops explicit binomial-tail bounds to determine the sample complexity required by probabilistic methods. The resulting expressions are tuned to the paper’s analysis and can improve existing bounds, especially when violations are allowed.

  • Sample-complexity objective: The section defines sample complexity as a function ˜N(η,m,δ) such that B(N,η,m)≤δ for every N≥˜N(η,m,δ).These binomial inequalities are used in the probabilistic analyses developed later.
  • Binomial bounds: The binomial-tail bounds are tailored to the inequalities arising in the paper’s probabilistic analysis rather than relying only on generic Chernoff expressions.The section contrasts these results with multiplicative and additive Chernoff bounds.
  • Binomial bounds: Lemma 1 provides an upper bound on the binomial distribution B(N,η,m), with the choice of a affecting the resulting sample-complexity bound.Each a≥1 yields an upper bound, while selecting a is consequential when deriving a specific complexity expression.
  • Explicit bounds: Choosing a as the Euler constant gives a suboptimal explicit sample-complexity bound that is numerically a significant improvement over bounds in prior work.For m>0, a more involved choice provides a less conservative bound.
  • Explicit bounds: Numerical computations indicate that the less conservative bound is close to the optimal bound, while the optimum can be obtained numerically using the Lambert W function.A further corollary gives another more involved bound that improves the preceding expression for some parameter values.

4 Sample complexity for probabilistic analysis and design

This section derives explicit sample-complexity bounds for probabilistic analysis and design, using binomial-tail inequalities for finite families and convex scenario optimization. The bounds guarantee prescribed violation probabilities and confidence, including an improved convex-design constant.

  • General sample-complexity results: Explicit sample-size bounds based on binomial-tail inequalities guarantee prescribed probabilistic properties for randomized solutions.The bounds apply across several randomized approaches and connect sample size to accuracy and confidence requirements.
  • Finite families: The finite-family failure bound satisfies p(N, η, m) < nC B(N, η, m).This follows under cardinality at most nC, η ∈ (0, 1), and m < N.
  • Finite families: For a finite design family of cardinality at most nC, the required sample complexity grows logarithmically with nC.The guarantee applies when nC B(N, η, m) ≤ δ, with N > m.
  • Convex scenario optimization: For convex sampled optimization, the optimal solution satisfies E(θ̂N) ≤ η with probability at least 1 − δ under the stated assumptions.The result assumes convexity, feasibility, a unique optimum, and a nonempty feasibility-domain interior.
  • Convex scenario optimization: The improved convex-design bound reduces the constant 2 to e/(e−1) ≈1.59, with substantial numerical improvement for small η.The result is obtained by choosing a equal to the Euler constant and improves bounds reported in earlier work.

5 Sequential algorithms with probabilistic validation

SPV algorithms form a general sequential framework in which candidate solutions are generated and independently validated at each iteration. Their validation sample sizes are designed to ensure prescribed accuracy and confidence for every probabilistic solution obtained.

  • SPV framework: Sequential Probabilistic Validation (SPV) algorithms constitute a general family of randomized algorithms based on probabilistic validation.The family includes most sequential randomized algorithms discussed in the paper’s introduction.
  • Iteration structure: Each SPV iteration computes a candidate solution and then applies a validation step using independently drawn samples.The candidate-generation strategy can vary, while the validation framework provides the probabilistic guarantee.
  • Guarantees: The validation scheme guarantees that all probabilistic solutions obtained by the algorithm have violation probability at most η with probability at least 1 − δ.The parameters η and δ determine the required validation sample size at each iteration.
  • Validation design: At iteration k, the level function m(k) specifies allowed violations and the cardinality function M(k, η, δ) specifies validation-set size.These functions are selected to provide the desired probabilistic properties.
  • Iteration structure: The algorithm repeats candidate generation, validation, and iteration updates until a prescribed exit condition is met.Possible exit conditions include classifying a given number of candidates as probabilistic solutions or reaching a computational-time limit.

6 Adjusting the validation sample size

This section develops a general validation-set cardinality strategy for SPV algorithms. The resulting choice guarantees, with confidence exceeding 1−δ, that obtained probabilistic solutions have violation probability at most η.

  • The cardinality-adjusting strategy generalizes prior schemes and uses the paper’s preceding sample-complexity results.
  • If m(k) < M(k, η, δ) for every k and a suitable failure function exists, all obtained probabilistic solutions have violation probability at most η with probability greater than 1−δ.
  • The section introduces a general expression for the validation-set cardinality at each SPV iteration.
  • Theorem 5 provides a cardinality function that guarantees the same η–δ violation bound for all probabilistic solutions produced by SPV.
  • The level and failure functions can be selected as m(k)=⌊ak⌋ and µ(k)=1/(ξ(α)k^α), with α>1, recovering earlier validation strategies when a=0.

7 Comparison with other validation schemes

This section compares SPV with strict validation schemes and shows why allowing controlled validation failures matters when the robust feasible set is empty. It also establishes finite-iteration and almost-sure solution guarantees under stated conditions.

  • When the robust feasible set is empty, strict validation may fail to find a probabilistic solution even when solutions with violation probability at most η exist.
  • Under E(θ)≥µ>0 for all θ and a=0, SPV may fail to find a probabilistic solution during the first L iterations with high probability.
  • The strict-validation issue arises because candidates are accepted only when every sampled validation constraint is satisfied.
  • In a numerical example, α=1.1 with a=0 fails to find a solution with probability greater than 0.98, whereas α=2 yields probability greater than 0.99.
  • Under the stated technical assumptions, SPV obtains a probabilistic solution with probability one in a finite number of iterations.
  • Increasing validation-set cardinality makes the probability of classifying a suitable candidate as probabilistic approach at least one-half, supporting eventual finite termination.

8 Numerical example

The numerical example compares finite-family, convex scenario, and SPV approaches for probabilistic approximation under uncertainty. SPV achieves the best reported performance index, while finite families use fewer samples than the convex scenario approach.

  • Problem: The example seeks probabilistic upper and lower bounds for a random time function with unknown parameters A and B.The parameters satisfy t ∈ [0, 1] and A, B ∈ [1, 3].
  • Finite families approach: 1981 samples are required for the finite-family approach with nC = 400, m = 0, δ = 10^-6, and η = 0.01.The family is constructed with dmax = jmax = 20, giving nC = 400.
  • Finite families approach: The finite-family solution uses d = 15 and j = 11, achieving a performance index of 0.9814.Figure 1 displays the sampled set V and the resulting probabilistic upper and lower bounds.
  • Scenario approach: 7090 samples are required by the convex scenario approach, which achieves a performance index of 0.9613.The experimental violation probability is ηexp = 8.4626 · 10^-5 for the specification η = 0.05.
  • SPV approach: 4163 samples are required by SPV, which achieves a performance index of 0.9406 and is slightly better than the other approaches.The SPV procedure uses sequential validation sets drawn independently from the uncertainty distribution.
  • Comparison: For small violation probabilities η, the convex scenario approach has the largest sample complexity, while SPV obtains slightly better performance indices.SPV does not rely on convexity or finite-cardinality assumptions.

9 Conclusions

The conclusions combine new sample-complexity results with a general SPV framework for randomized design. SPV uses adjustable, non-strict validation to guarantee probabilistic specifications without requiring convexity, finite families, or a robust feasible solution.

  • Sample complexity: The paper derives sample complexities for analysis and design problems involving uncertain systems and bounds binomial distribution tails by prescribed confidence levels.The results are applied to worst-case performance analysis and robust optimization design.
  • SPV framework: SPV adjusts validation-set cardinality so obtained solutions meet specified probabilistic requirements.The strategy is based on probabilistic validation and is compared with existing schemes.
  • SPV framework: Non-strict validation permits some validation-set constraint violations and can dramatically reduce the number of sequential iterations.The approach also does not require a robust feasible solution.
  • SPV framework: SPV is general because it does not rely on finite-family or convexity assumptions.This scope is stated as an advantage of the proposed strategy.

A Appendix: Auxiliary proofs and properties

The appendix establishes monotonicity and recursive bounds for binomial-distribution expressions used in the paper’s sample-complexity analysis. It also develops sufficient inequalities for bounding these expressions by the confidence parameter δ.

  • Binomial bounds: When m = 0, B(N, η, 0) = (1 − η)^N ≤ e^−ηN, yielding the condition e^−ηN ≤ δ.This provides the zero-failure case of the sample-complexity bound.
  • Binomial properties: For fixed m and N with m < N, B(N, η, m) strictly decreases as η increases over (0, 1).The proof establishes negativity of the derivative with respect to η.
  • Auxiliary property: The recursive inequality is verified first at t = 1 and then extended to every integer t greater than 0.The resulting bound follows by repeated substitution from S(0) = 1.
Loading 1304.0678v2…