CRII: RI: Stochastic Optimization via Embedding Counting as Optimization with Randomized Constraints

随机优化是一种利用世界上的随机性来解决问题的方法。 随机性在经济学、运筹学和人工智能等许多应用中自然出现。以野生动物保护的网络设计问题为例。野生动物的运动可以用随机函数来描述。其目标是确定最佳的保护措施，使动物的扩散最大化的预期。网络设计问题是随机优化的一个特例，它的求解将有助于生态学家和政府官员明智地确定环境保护计划的优先级，这对确保我们的可持续发展具有重要意义。然而，随机优化是非常棘手的，因为它结合了两个棘手的问题，其中之一是计算指数级概率结果的期望的内部计数问题，另一个是外部优化问题，寻找最大化期望的最优策略。该建议的重点是扩展一种新的方法，嵌入计数作为随机约束优化（ECOR），解决随机优化问题。ECOR通过受随机奇偶约束的优化查询来逼近棘手的计数子问题，这些优化查询又嵌入到全局优化任务中。因此，随机优化推理可以减少到一个单一的联合优化的多项式大小的原始问题与可证明的保证。这项研究的重点是将ECOR扩展为一系列适用于机器学习和网络设计应用的方法。目前的ECOR算法的局限性主要是由于它的实施作为一个单一的，大的约束程序，除了长奇偶校验约束，提供了很强的概率保证，但具有挑战性的计算。扩大ECOR的关键原则是综合考虑内部计数和外部最大化问题。该奖项反映了NSF的法定使命，并通过使用基金会的知识价值和更广泛的影响审查标准进行评估，被认为值得支持。

Stochastic optimization is a problem-solving method that makes use of randomness in the world. Randomness arises naturally in many applications ranging from economics, operational research, and artificial intelligence. Take the network design problem for wild-life animal protection as an example. The movements of wild-life animals can be described using a stochastic function. The goal is to decide optimal protection measures that maximize animals' dispersal in expectation. Solving the network design problem, a special case of stochastic optimization, would help ecologists and government officials to prioritize environmental protection plans wisely, which is meaningful in securing our sustainable future.Nevertheless, stochastic optimization is highly intractable because it combines two intractable problems, one of which is the inner counting problem to compute the expectation across exponentially many probabilistic outcomes, the other of which is the outer optimization problem to search for the optimal policy that maximizes the expectation. This proposal focuses on expanding a novel approach, Embedding Counting as Optimization with Randomized Constraints (ECOR), to solve stochastic optimization problems. ECOR approximates intractable counting sub-problems with optimization queries subject to randomized parity constraints, which are in turn embedded into the global optimization task. As a result, the stochastic optimization inference can be reduced to a single joint optimization of a polynomial size of the original problem with provable guarantees. This research focuses on expanding ECOR into a family of approaches that is practical for machine learning and network design applications. The limitation of the current ECOR algorithm is mainly due to its implementation as a single, large constraint program, in addition to the long parity constraints, which provide strong probabilistic guarantees but are challenging computationally. The key principle to scale up ECOR is to take an integrated view of the inner counting and the outer maximization problem. The algorithmic contribution will be driven by the intuitions gained from working on several real-world problems.This award reflects NSF's statutory mission and has been deemed worthy of support through evaluation using the Foundation's intellectual merit and broader impacts review criteria.