On the Sample Complexity of Direct Data-Driven Robust Controller Synthesis

Direct data-driven control synthesizes controllers from a single measured trajectory without first identifying a model. It offers deterministic robustness guarantees whenever a known disturbance bound holds. However, existing multiplier-based formulations for robust H2 control typically restrict attention to conservative subclasses of valid certificates. It has remained unclear whether collecting more data drives their certified performance toward the true optimum, or whether a persistent gap remains regardless of trajectory length. This paper answers this question for a discrete-time linear system subject to pointwisebounded disturbances. We first show that the widely used matrix S-lemma formulation suffers from a fundamental limitation. Under a bounded state trajectory, its certified performance remains bounded away from the optimum by a gap that does not vanish as the trajectory length grows. Motivated by this finding, we construct a semidefinite-representable family of multipliers that combines nonnegative sample weights with an auxiliary symmetric matrix. This family contains both the matrix S-lemma family and an existing Frobenius-bound family, and it adds only marginal computational overhead per sample. We then derive deterministic trajectory conditions under which this enlarged family yields a certificate close to the optimal performance. We show that these conditions hold with high probability under mild excitation assumptions on the disturbance and the stateinput trajectory. This yields a non-asymptotic bound on the number of samples needed for a prescribed accuracy. It establishes that the certified performance converges to the true optimum even though the disturbance bound stays fixed rather than vanishing. For disturbances uniform over a Euclidean ball, the relative certificate gap decreases at a rate proportional to the inverse square root of the trajectory length, up to logarithmic factors. Numerical experiments corroborate both the persistent conservatism of the matrix S-lemma approach and the predicted convergence rate of the proposed method.