针对决策依赖不确定性的非凸优化,提出两种低阶方法提升收敛性与稳定性。
Zeroth-Order Methods for Nonconvex Stochastic Problems with Decision-Dependent Distributions
- 设计带方差调节的单点梯度估计器,动态调整更新策略。
- 引入双点梯度估计器,在可用时提升估计精度。
- 理论证明收敛至驻点,实验显示优于传统方法。
本文研究决策变量影响不确定性的非凸随机优化问题,该问题在机器学习和定价应用中日益重要。由于决策依赖分布未知,目标函数梯度无法显式获取,现有零阶方法依赖采样获得噪声目标值并迭代更新。尽管已有方法具备理论收敛性,但通常依赖强假设或梯度估计方差过大。为此,本文提出两种在温和假设下的零阶方法:首先,设计一种含方差减少参数的新型单点梯度估计器,通过调整参数实现决策变量更新;其次,提出双点梯度估计器,在条件允许时更具实用性。理论分析表明,所提方法可收敛至驻点,并给出最坏情况下的迭代与样本复杂度。基于真实零售服务数据的模拟实验显示,本文方法所得解的目标值显著低于传统零阶方法。
原文摘要 · Abstract (English)
In this study, we consider an optimization problem with uncertainty dependent on decision variables, which has recently attracted attention due to its importance in machine learning and pricing applications. In this problem, the gradient of the objective function cannot be obtained explicitly because the decision-dependent distribution is unknown. Therefore, several zeroth-order methods have been proposed, which obtain noisy objective values by sampling and update the iterates. Although these existing methods have theoretical convergence for optimization problems with decision-dependent uncertainty, they require strong assumptions about the function and distribution or exhibit large variances in their gradient estimators. To overcome these issues, we propose two zeroth-order methods under mild assumptions. First, we develop a zeroth-order method with a new one-point gradient estimator including a variance reduction parameter. The proposed method updates the decision variables while adjusting the variance reduction parameter. Second, we develop a zeroth-order method with a two-point gradient estimator. There are situations where only one-point estimators can be used, but if both one-point and two-point estimators are available, it is more practical to use the two-point estimator. As theoretical results, we show the convergence of our methods to stationary points and provide the worst-case iteration and sample complexity analysis. Our simulation experiments with real data on a retail service application show that our methods output solutions with lower objective values than the conventional zeroth-order methods.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品;中文卡片由大模型生成,请以原文为准。