paperbot · PL 论文追踪

全部论文 待读 收藏

P2 Global Optimisation with Constructive Reals

基于构造性实数的全局优化
LICS 2021 36th Annual ACM/IEEE Symposium on Logic in Computer Science (LICS)2021匹配度 3/10 · 论文属于构造类型论/定理证明与优化-回归的理论交叉,与用户关注的 PL→AI 静态分析、AI→PL 形式化验证自动化、浮点程序分析及贝叶斯程序分析均无直接关联;虽提及以可计算实数替代浮点表示,但只是作为对照背景,并未涉及浮点程序分析或 LLM/Agent 方法。仅在'兼具理论形式化与工程实现(Agda 机器化 + Java 原型)'这一点上与用户偏好弱相关。引用 1 inbox
Dan R. Ghica, Todd Waugh Ambridge
crossref: 2026-09-12

AI 速览

一句话:在构造类型论与可计算实数下建立全局优化与回归的联系,并给出收敛准则及 Agda 机器化证明。

论文研究连续函数的确定性、完备且一般的全局优化与广义回归之间的联系。作者以构造类型论和可计算实数为理论基础,将全局优化视为回归的一种推广,并利用全局优化的收敛性质导出新的回归收敛准则。由于采用可计算实数而非浮点数,该方法能在精度和终止性方面给出强理论保证。全部理论已在证明助手 Agda 的安全模式下形式化;作者还用 Java 的现成构造性实数库实现示例,表明该途径在算法上具有前景。

问题
如何为连续函数的一般全局优化与回归建立可保证精度和终止性的理论联系与收敛准则,避免浮点表示带来的理论保证缺失。
方法
基于构造类型论和可计算实数,将全局优化推广为广义回归,并从全局优化收敛性推导回归收敛准则,全部用 Agda 安全模式形式化。
评估
在 Agda 中完成机器化证明,并用 Java 构造性实数库实现示例,初步验证算法的可行性。
原文摘要(Abstract)

We draw new connections between deterministic, complete, and general global optimisation of continuous functions and a generalised notion of regression, using constructive type theory and computable real numbers. Using this foundation we formulate novel convergence criteria for regression, derived from the convergence properties of global optimisations. We see this as possibly having an impact on optimisation-based computational sciences, which include much of machine learning. Using computable reals, as opposed to floating-point representations, we can give strong theoretical guarantees in terms of both precision and termination. The theory is fully formalised using the safe mode of the proof assistant AGDA. Some examples implemented using an off-the-shelf constructive reals library in JAVA indicate that the approach is algorithmically promising.

链接与引用

DOI 原文 · PDF(开放获取) ·

BibTeX
@inproceedings{paperbot6179,
  title = {Global Optimisation with Constructive Reals},
  author = {Dan R. Ghica and Todd Waugh Ambridge},
  booktitle = {LICS},
  year = {2021},
  doi = {10.1109/lics52264.2021.9470549}
}