提出新型决策交换后悔机制，实现非线性损失下的高效预测与泛化。
Sample Efficient Omniprediction and Downstream Swap Regret for Non-Linear Losses
- 基于在线对抗框架，统一处理下游交换后悔与全能预测问题。
- 首次给出多维利普希茨损失的多项式样本复杂度上界，突破以往指数级依赖。
- 适用于经济中常见效用函数，如柯布-道格拉斯、列昂惕夫等，适合机制设计研究者。
我们定义了“决策交换后悔”，该概念同时推广了下游交换后悔预测与全能预测。针对任意多维利普希茨损失函数，在在线对抗设置下给出了相应的算法，并通过在线到批量的转换给出了批量设定下的样本复杂度界。应用于全能预测时，我们的算法首次实现了对利普希茨损失函数的多项式样本复杂度上界——此前的边界仅适用于线性损失（或二元结果），或在凸损失假设下仍呈误差参数的指数级增长。应用于下游后悔预测时，我们提出了首个能为所有下游代理在多维结果空间中非线性损失函数下保证交换后悔边界的算法；此前工作仅限于线性损失，建模风险中性代理。一般界随结果空间维度呈指数增长，但我们针对具有经济意义的特定函数族（常替代弹性、柯布-道格拉斯、列昂惕夫效用函数）给出了改进的后悔与样本复杂度界。
原文摘要 · Abstract (English)
We define "decision swap regret" which generalizes both prediction for downstream swap regret and omniprediction, and give algorithms for obtaining it for arbitrary multi-dimensional Lipschitz loss functions in online adversarial settings. We also give sample complexity bounds in the batch setting via an online-to-batch reduction. When applied to omniprediction, our algorithm gives the first polynomial sample-complexity bounds for Lipschitz loss functions -- prior bounds either applied only to linear loss (or binary outcomes) or scaled exponentially with the error parameter even under the assumption that the loss functions were convex. When applied to prediction for downstream regret, we give the first algorithm capable of guaranteeing swap regret bounds for all downstream agents with non-linear loss functions over a multi-dimensional outcome space: prior work applied only to linear loss functions, modeling risk neutral agents. Our general bounds scale exponentially with the dimension of the outcome space, but we give improved regret and sample complexity bounds for specific families of multidimensional functions of economic interest: constant elasticity of substitution (CES), Cobb-Douglas, and Leontief utility functions.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。