Safe Start: Configuring Optimization Algorithms for Decision-Making under Extreme Risks

We consider stochastic optimization where the goal is not only to optimize an average-case objective, but also mitigate the occurrence of rare catastrophic events. This problem is motivated from safety-aware decision-making and AI training. We first argue that, in the presence of a simulation model, natural attempts to integrate variance reduction into optimization, even executed in a reasonable adaptive fashion, encounters fundamental challenges in guaranteeing realistic runtime when using common stochastic gradient descent algorithms. This challenge arises from the extreme sensitivity of tail-based objectives with respect to the decision variables, which renders the failure of traditional Lipschitz-based analyses. We offer remedies based on a new notion of safe start that allows for efficient finite-time error control, and show how the sampling complexity scales favorably under the combination of safe start and variance reduction. We illustrate our methodologies on examples in portfolio Value-at-Risk and extreme-quantile estimation.