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

This paper addresses stochastic optimization problems where the goal is not only to optimize an average-case objective but also to mitigate rare catastrophic events. The authors consider the following generic rare-event optimization formulation:

min F (x) = f (x) + γp(x) (Equation 1)

where x is the decision variable, f is the expectation of some loss function, and p is an extreme-risk term involving the tail of underlying randomness (such as the probability of a rare event or value-at-risk at a high level). The parameter γ > 0 balances expected loss and extreme risk.

The paper is motivated by safety-aware decision-making and AI training, including applications such as self-driving vehicles, financial portfolio management, and robust classification with neural networks.

The authors note that naive Monte Carlo estimation of rare-event probabilities is poor when p is tiny because more likely than not we would simply output 0 as the estimate due to 0 hits. The relative error for naive sample proportion is √((1-p)/p), which blows up the required sample size when p is tiny. Variance reduction methods (importance sampling, multilevel splitting) can reduce this to order p2 instead of p as p → 0.

The authors identify a curse of circularity in rare-event optimization: on one hand a good optimizer needs a good variance reduction scheme, and on the other hand a good variance reduction scheme requires knowledge about the optimal solution. This arises because most variance reduction schemes are double-edged swords that are highly sensitive to the problem instance. Prior work (He et al. 2024, Aolaritei et al. 2025) proposed adaptivity as a remedy, showing central limit theorems for updated solutions.

The main focus of this paper is the lack of bridge between classical efficiency notions in rare-event estimation and optimization efficiency. The authors explain:

"In estimation, the variance of an estimator translates directly into the required sample size, since the standard Chebyshev inequality reveals that the latter is proportional to the (squared) relative error σ2/p2. In optimization, the situation is substantially more complicated since there are no longer simple guiding inequalities to inform the conversion of relative error into sampling complexity."

The authors show that embedding adaptive variance reduction into an iterative algorithm like SGD is fundamentally inadequate in achieving desirable sampling complexity, even if the variance reduction is excellent for the evaluation task. Specifically, Theorem 2 states that without safe start, there exist problem instances where "for any sequence of (projected) SGD schemes A(λ) λ>0 chosen from the universal class of all monotonically diminishing step sizes," the sampling complexity grows exponentially.

The intuition is that risky solutions can exhibit exponentially larger gradients than 'safe' solutions, leading to a dichotomic failure of convergence regardless of what step size we select. Either the step size is too small (slow convergence) or too large (unstable big jumps requiring many iterations to recover).

The authors introduce a new notion called safe start – initializing the solution to be in a safe region where the risk term p(x) is suitably small. Theorem 1 establishes that given efficient gradient estimators, a safe start is sufficient to guarantee sub-exponential sampling complexity across standard SGD algorithms.

The safe start condition (Assumption 3) requires:

lim sup (1/λ) log p(x0(λ)) ≤ -I

meaning the risk level of the SGD initialization is upper bounded by that of the optimal solution, in exponential scale.

Theorem 3 shows that even if we enforce safe start, without efficient gradient estimator, we can run into problem instances with poor sampling complexity no matter how we tune the SGD. This establishes that both safe start AND efficient adaptive variance reduction are needed for optimization efficiency.

The paper makes several key assumptions:

• Assumption 1 (LDP of Target Risk): The optimal risk decays exponentially with rate I, and γ(λ) matches this exponential scale

• Assumption 2 (Unbiased and Efficient Gradient Estimators): Gradient estimators exist with variance bounded by σ2 p(λ)∥∇p(x)∥2 where σ p(λ) grows at most sub-exponentially

• Assumption 3 (Safe Start): Initial risk is bounded by optimal risk in exponential scale

• Assumptions 4-8: Standard regularity conditions (smoothness, convexity, sublevel-boundedness, relative gradient/Hessian bounds on extreme risk)

• Assumption 9 (Sub-Exponential Initial Distance): Initialization is not exponentially far from the average-case minimizer

• Rarity-Aware Sampling Complexity (Definition 1): Minimum number of stochastic gradient samples needed to achieve F(x̂;λ) ≤ (1+ε)·F(x*(λ);λ) with probability at least 1-κ

• Efficient Configuration (Definition 2): Sampling complexity grows sub-exponentially in λ

• Safe Start (Assumption 3): Initial risk level is upper bounded by optimal risk in exponential scale

The analysis centers on the initial sublevel set S(x0, λ, c):= x ∈ X F(x;λ) ≤ c·F(x0;λ). Lemma 1 establishes three regularity properties within this set:

1. Bounded distance to optimal solution

2. Local smoothness (Lipschitz constant LS)

3. Bounded gradient noise (variance bound σ2 S)

Lemma 2 shows that with safe start, all these constants grow sub-exponentially in λ.

The authors develop a joint containment–descent analysis because any smoothness and variance bounds that allow to drive a descent step hold only when the iterate lies in the safe region S. This creates a coupling: if the current iterate descends, then, by definition of a sublevel set, it remains within the set. However, deriving that descent property in the first place requires the update to already lie within the safe region.

For last-iterate schemes (Aα,last), Lemma 3 establishes Safe Descent – a single controlled step ensures both next-step containment and descent. Lemma 4 provides sufficient conditions for convergence, and Lemma 5 constructs explicit rarity-scaled configurations. Proposition 1 establishes sufficiency of safe starts for last-iterate SGD.

For average-iterate schemes (Aα,avg), the analysis tracks two trajectory-level quantities in parallel: the expected optimality gap over the initial sublevel set, which governs descendance, and the first-time escape probability, which governs containment. Lemmas 6-9 develop these bounds, and Lemma 10 constructs explicit configurations. Proposition 2 establishes sufficiency for average-iterate SGD.

The authors construct a two-dimensional instance with f(x) = u2 + v, p(x) = e(-u-v), and γ(λ) = e λ. With unsafe start x0(λ) = (λ/4, 0), they show that for any monotonically diminishing step sizes, the sampling complexity grows exponentially. The analysis splits into two cases:

• Large step size (η0 ≥ e(-λ/2)): the exponentially large initial risk gradient makes the first v-update overshoot by v1 = Ω(η0e(3λ/4)), an exponentially large distance from v*(λ)

• Small step size (η0 (1/10)e(λ/2) iterations

The authors construct a one-dimensional instance with f(x) = x, p(x) = e(-x), and γ(λ) = e λ, where the gradient estimator has high variance in a region H λ = (1.5(λ+1), 1.6(λ+1)). They show that even with safe start, the sampling complexity grows exponentially when the gradient estimator is not efficient.

The authors estimate VaR at level q = 1 - 10−5 for a derivatives portfolio. Results show that the two IS schemes reliably converge to the target VaR when started from a safe initialization with an appropriate step size, whereas unsafe initializations fail regardless of step size. The standard MC scheme fails across all tested configurations, illustrating that variance reduction remains necessary even with a safe start.

For a 10-asset portfolio, the authors find that "projected gradient descent converges to the optimal allocation only when it is both equipped with adaptive variance reduction and initialized at a safe start. The empirical convergence probability is zero for every configuration with either the unsafe start or without the variance reduction scheme."

The authors train an MLP for robust classification. Results show that SGD with the unsafe start does not reach these targets at any step size we tested. In contrast, SGD with the safe start reaches them at initial step sizes 10−6 and 10−7. The safe start is constructed by modifying solely the final-layer bias of the positive class, setting it to a constant (15 here) large enough that the model predicts almost exclusively that class.

The paper provides a first bridge between rare-event estimation and optimization efficiency. Key findings:

1. Adaptive variance reduction alone does not suffice for optimization efficiency

2. Safe start (initializing with low risk level) combined with efficient variance reduction guarantees sub-exponential sampling complexity

3. Both safe start and efficient gradient estimators are necessary and sufficient for rare-event optimization efficiency

The authors conclude that safe start is simple to configure and crucial in rare-event optimization.

Based on this paper, here are specific improvements I can make to AI systems:

Improvement: Implement a safe start initialization protocol that ensures the AI system begins training in a region where catastrophic failure probability is exponentially bounded relative to the optimal solution's risk level.

What the improved system can do:

• For autonomous driving models: Initialize neural networks with weights that guarantee low probability of dangerous actions (e.g., collision scenarios) before training begins, rather than starting from random weights that may explore risky behaviors

• For financial trading agents: Start with conservative portfolio allocations where tail-risk (e.g., 99.99% VaR) is already within acceptable bounds, then optimize toward higher returns while maintaining safety

• For medical diagnosis systems: Begin with a model biased toward conservative diagnoses (avoiding false negatives for critical conditions) before fine-tuning for accuracy

Improvement: Integrate importance sampling or multilevel splitting estimators that are automatically calibrated to the current iterate's risk profile, with safeguards that prevent variance reduction from becoming unstable when the solution moves toward risky regions.

Improvement: Add runtime checks that detect when gradient estimators become inefficient (variance growing exponentially relative to the true gradient) and trigger corrective actions.

Improvement: Implement a step-size scheduling mechanism that accounts for the exponential scaling of gradients in risky regions, preventing both crawling (too small steps) and overshooting (too large steps) failures.

Improvement: Create a two-phase training protocol: first, establish a safe baseline solution with low extreme-risk, then optimize average-case performance while maintaining a safety buffer that prevents drift into high-risk regions.

Improvement: Add convergence criteria that specifically track the extreme-risk component's progress, not just average loss, ensuring the optimization doesn't prematurely stop while rare-event risk remains unoptimized.

Improvement: Implement algorithms that automatically determine whether a given initialization satisfies the safe start condition (Assumption 3) by estimating the exponential decay rate of initial risk relative to optimal risk.

These improvements collectively enable AI systems to be trained more reliably in domains where rare catastrophic events matter, with guaranteed sub-exponential sampling complexity and stability guarantees that standard optimization methods lack.