arXiv:2504.03560math.OCcs.LG2025-04被引 2

提出一种新算法,让优化与采样同时更新,解决采样依赖优化的难题。

Stochastic Optimization with Optimal Importance Sampling

  • 用单循环算法同步优化变量和采样分布,无需分时步或嵌套计算。
  • 收敛后方差达到理论最优,媲美已知最优采样器的性能。
  • 适合需要高效随机优化的稀有事件模拟等场景。

重要性采样(IS)是提升蒙特卡洛方法效率的常用方差缩减技术,尤其在稀有事件模拟中表现突出。然而,其性能对提议分布选择极为敏感,常需随机校准。尽管在估计场景下已有广泛研究,但将IS用于随机优化时面临一个未被充分认识的根本挑战:决策变量与重要性采样分布相互依赖,形成循环优化结构,使收敛分析与方差控制变得复杂。本文研究带有线性约束的凸随机优化通用情形,提出一种基于Nesterov对偶平均的单循环随机逼近算法,可联合更新决策变量与重要性采样分布,且无需时间尺度分离或嵌套优化。该方法全局收敛,并实现所有随机梯度方案中的最小渐近方差,该性能与针对最优解自适应的预言采样器相当,从而有效解决循环优化问题。

原文摘要 · Abstract (English)

Importance Sampling (IS) is a widely used variance reduction technique for enhancing the efficiency of Monte Carlo methods, particularly in rare-event simulation and related applications. Despite its effectiveness, the performance of IS is highly sensitive to the choice of the proposal distribution and often requires stochastic calibration. While the design and analysis of IS have been extensively studied in estimation settings, applying IS within stochastic optimization introduces a lesser-known fundamental challenge: the decision variable and the importance sampling distribution are mutually dependent, creating a circular optimization structure. This interdependence complicates both convergence analysis and variance control. In this paper, we consider the generic setting of convex stochastic optimization with linear constraints. We propose a single-loop stochastic approximation algorithm, based on a variant of Nesterov's dual averaging, that jointly updates the decision variable and the importance sampling distribution, notably without time-scale separation or nested optimization. The method is globally convergent and achieves the minimal asymptotic variance among stochastic gradient schemes, which moreover matches the performance of an oracle sampler adapted to the optimal solution and thus effectively resolves the circular optimization challenge.

随机优化重要性采样凸优化方差缩减

Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品;中文卡片由大模型生成,请以原文为准。