Margin-based scenario approach to robust optimization in high dimension

Fabien Lauer (1, 2)

1 ABC - Machine Learning and Computational Biology
2 SYNALP - Natural Language Processing : representations, inference and semantics

This paper deals with the scenario approach to robust optimization. This relies on a random sampling of the possibly infinite number of constraints induced by uncertainties in the parameters of an optimization problem. Solving the resulting random program yields a solution for which the quality is measured in terms of the probability of violating the constraints for a random value of the uncertainties, typically unseen before. Another central issue is the determination of the sample complexity, i.e., the number of random constraints (or scenarios) that one must consider in order to guarantee a certain reliability. In this paper, we introduce an additional margin in the constraints and analyze the probability of violation of solutions to the modified random programs. In particular, using tools from statistical learning theory, we show that the sample complexity of a class of problems does not explicitly depend on the number of variables. In addition, within this class, that includes polynomial constraints among others, the same guarantees hold for both convex and nonconvex instances.

Keywords: Scenario approach; Robust optimization; Randomized algorithms; Statistical learning

Domains: Machine Learning [stat.ML]; Optimization and Control [math.OC]

Fabien Lauer. Margin-based scenario approach to robust optimization in high dimension. IEEE Transactions on Automatic Control, inPress, ⟨10.1109/TAC.2024.3393790⟩. ⟨hal-04012765v2⟩