Online Complexity Estimation for Repetitive Scenario Design

• URL: http://arxiv.org/abs/2509.02103v2
• Date: Fri, 05 Sep 2025 09:42:23 GMT
• Title: Online Complexity Estimation for Repetitive Scenario Design
• Authors: Guillaume O. Berger, Raphaël M. Jungers,
• Abstract summary: We consider the problem of repetitive design scenario where one has to solve repeatedly a scenario problem problem.<n>We propose an approach to fly the fly sample size based on the pdf in previous scenario.<n>We prove the soundness and convergence of our approach to obtain the optimal sample size for the class of fixed-complexity scenario problems.
• Score: 1.2031796234206136
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We consider the problem of repetitive scenario design where one has to solve repeatedly a scenario design problem and can adjust the sample size (number of scenarios) to obtain a desired level of risk (constraint violation probability). We propose an approach to learn on the fly the optimal sample size based on observed data consisting in previous scenario solutions and their risk level. Our approach consists in learning a function that represents the pdf (probability density function) of the risk as a function of the sample size. Once this function is known, retrieving the optimal sample size is straightforward. We prove the soundness and convergence of our approach to obtain the optimal sample size for the class of fixed-complexity scenario problems, which generalizes fully-supported convex scenario programs that have been studied extensively in the scenario optimization literature. We also demonstrate the practical efficiency of our approach on a series of challenging repetitive scenario design problems, including non-fixed-complexity problems, nonconvex constraints and time-varying distributions.

Related papers

• Forecasting Outside the Box: Application-Driven Optimal Pointwise Forecasts for Stochastic Optimization [0.0]
  We show that, under mild assumptions, the problem can be solved with just one scenario, which we call an optimal scenario''<n>Finding an optimal scenario in general might be hard, but we show that the result can be particularly useful in the case of optimization problems with contextual information.
  arXiv  Detail & Related papers  (2024-11-05T21:54:50Z)
• Generalization Bounds of Surrogate Policies for Combinatorial Optimization Problems [61.580419063416734]
  A recent stream of structured learning approaches has improved the practical state of the art for a range of optimization problems. The key idea is to exploit the statistical distribution over instances instead of dealing with instances separately. In this article, we investigate methods that smooth the risk by perturbing the policy, which eases optimization and improves the generalization error.
  arXiv  Detail & Related papers  (2024-07-24T12:00:30Z)
• Randomized algorithms and PAC bounds for inverse reinforcement learning in continuous spaces [47.907236421762626]
  This work studies discrete-time discounted Markov decision processes with continuous state and action spaces. We first consider the case in which we have access to the entire expert policy and characterize the set of solutions to the inverse problem.
  arXiv  Detail & Related papers  (2024-05-24T12:53:07Z)
• Experiment Planning with Function Approximation [49.50254688629728]
  We study the problem of experiment planning with function approximation in contextual bandit problems. We propose two experiment planning strategies compatible with function approximation. We show that a uniform sampler achieves competitive optimality rates in the setting where the number of actions is small.
  arXiv  Detail & Related papers  (2024-01-10T14:40:23Z)
• Optimal Multi-Distribution Learning [88.3008613028333]
  Multi-distribution learning seeks to learn a shared model that minimizes the worst-case risk across $k$ distinct data distributions.<n>We propose a novel algorithm that yields an varepsilon-optimal randomized hypothesis with a sample complexity on the order of (d+k)/varepsilon2.
  arXiv  Detail & Related papers  (2023-12-08T16:06:29Z)
• Margin theory for the scenario-based approach to robust optimization in high dimension [0.0]
  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 a problem.
  arXiv  Detail & Related papers  (2023-03-07T13:33:46Z)
• Data-driven Prediction of Relevant Scenarios for Robust Optimization [0.0]
  We study robust one- and two-stage problems with discrete uncertainty sets. We propose a data-driven computation to seed the iterative solution method with a set of starting scenarios. Our experiments show that predicting even a small number of good start scenarios by our method can considerably reduce the time of the iterative methods.
  arXiv  Detail & Related papers  (2022-03-30T19:52:29Z)
• Runtime Analysis of Single- and Multi-Objective Evolutionary Algorithms for Chance Constrained Optimization Problems with Normally Distributed Random Variables [11.310502327308575]
  We study the scenario of components that are independent and normally distributed. We introduce a multi-objective formulation of the problem which trades off the expected cost and its variance. We prove that this approach can also be used to compute a set of optimal solutions for the chance constrained minimum spanning tree problem.
  arXiv  Detail & Related papers  (2021-09-13T09:24:23Z)
• Stochastic Saddle-Point Optimization for Wasserstein Barycenters [69.68068088508505]
  We consider the populationimation barycenter problem for random probability measures supported on a finite set of points and generated by an online stream of data. We employ the structure of the problem and obtain a convex-concave saddle-point reformulation of this problem. In the setting when the distribution of random probability measures is discrete, we propose an optimization algorithm and estimate its complexity.
  arXiv  Detail & Related papers  (2020-06-11T19:40:38Z)
• The Simulator: Understanding Adaptive Sampling in the Moderate-Confidence Regime [52.38455827779212]
  We propose a novel technique for analyzing adaptive sampling called the em Simulator. We prove the first instance-based lower bounds the top-k problem which incorporate the appropriate log-factors. Our new analysis inspires a simple and near-optimal for the best-arm and top-k identification, the first em practical of its kind for the latter problem.
  arXiv  Detail & Related papers  (2017-02-16T23:42:02Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.