We introduce a natural online allocation problem that connects several of the most fundamental problems in online optimization. Let $M$ be an $n$-point metric space. Consider a resource that can be allocated in arbitrary fractions to the points of $M$. At each time $t$, a convex monotone cost function $c_t: [0,1]\to\mathbb{R}_+$ appears at some point $r_t\in M$. In response, an algorithm may change the allocation of the resource, paying movement cost as determined by the metric and service cost $c_t(x_{r_t})$, where $x_{r_t}$ is the fraction of the resource at $r_t$ at the end of time $t$. For example, when the cost functions are $c_t(x)=\alpha x$, this is equivalent to randomized MTS, and when the cost functions are $c_t(x)=\infty\cdot 1_{x<1/k}$, this is equivalent to fractional $k$-server. We give an $O(\log n)$-competitive algorithm for weighted star metrics. Due to the generality of allowed cost functions, classical multiplicative update algorithms do not work for the metric allocation problem. A key idea of our algorithm is to decouple the rate at which a variable is updated from its value, resulting in interesting new dynamics. This can be viewed as running mirror descent with a time-varying regularizer, and we use this perspective to further refine the guarantees of our algorithm. The standard analysis techniques run into multiple complications when the regularizer is time-varying, and we show how to overcome these issues by making various modifications to the default potential function. We also consider the problem when cost functions are allowed to be non-convex. In this case, we give tight bounds of $\Theta(n)$ on tree metrics, which imply deterministic and randomized competitive ratios of $O(n^2)$ and $O(n\log n)$ respectively on arbitrary metrics. Our algorithm is based on an $\ell_2^2$-regularizer.


翻译:我们引入了一个自然的在线分配问题, 将在线优化中几个最基本的问题连接起来。 让 $M 成为美元 。 考虑一个资源可以任意分配到美元。 $t$ 。 每次美元, comvex 单调成本函数 $c_ t: [0, 1\ to\\\\\\\\\\\\\\\R\\\\M$, 在某些点( $美元) 。 作为回应, 一个算法可以改变资源的分配, 支付由美元 (x\\\\\\\ t) 的递增成本, 支付由美元 美元 (x\\\\\\ t) 美元 确定的流动成本, 美元是任意的, 美元是美元 美元 美元 。 当成本函数是美元(x) 时, 当成本(x\\\\\\\\\\\\\\\\\ xxxxxxxxxxxxxxxxxx), 成本功能会变换到 美元, 美元。 我们的递变换到 美元 美元, 美元 美元 货币的货币计算法。

0
下载
关闭预览

相关内容

在数学优化,统计学,计量经济学,决策理论,机器学习和计算神经科学中,代价函数,又叫损失函数或成本函数,它是将一个或多个变量的事件阈值映射到直观地表示与该事件。 一个优化问题试图最小化损失函数。 目标函数是损失函数或其负值,在这种情况下它将被最大化。
专知会员服务
28+阅读 · 2021年8月2日
【图与几何深度学习】Graph and geometric deep learning,49页ppt
专知会员服务
41+阅读 · 2021年4月2日
【ICLR2020】图神经网络与图像处理,微分方程,27页ppt
专知会员服务
47+阅读 · 2020年6月6日
强化学习最新教程,17页pdf
专知会员服务
174+阅读 · 2019年10月11日
[综述]深度学习下的场景文本检测与识别
专知会员服务
77+阅读 · 2019年10月10日
机器学习入门的经验与建议
专知会员服务
92+阅读 · 2019年10月10日
word2Vec总结
AINLP
3+阅读 · 2019年11月2日
【泡泡汇总】CVPR2019 SLAM Paperlist
泡泡机器人SLAM
14+阅读 · 2019年6月12日
A Technical Overview of AI & ML in 2018 & Trends for 2019
待字闺中
16+阅读 · 2018年12月24日
Disentangled的假设的探讨
CreateAMind
9+阅读 · 2018年12月10日
NIPS 2017:贝叶斯深度学习与深度贝叶斯学习(讲义+视频)
机器学习研究会
36+阅读 · 2017年12月10日
【推荐】用Python/OpenCV实现增强现实
机器学习研究会
14+阅读 · 2017年11月16日
【推荐】SVM实例教程
机器学习研究会
17+阅读 · 2017年8月26日
【学习】Hierarchical Softmax
机器学习研究会
4+阅读 · 2017年8月6日
Measure Estimation in the Barycentric Coding Model
Arxiv
0+阅读 · 2022年1月28日
Arxiv
0+阅读 · 2022年1月28日
Arxiv
8+阅读 · 2018年5月15日
Arxiv
3+阅读 · 2017年12月1日
VIP会员
相关VIP内容
专知会员服务
28+阅读 · 2021年8月2日
【图与几何深度学习】Graph and geometric deep learning,49页ppt
专知会员服务
41+阅读 · 2021年4月2日
【ICLR2020】图神经网络与图像处理,微分方程,27页ppt
专知会员服务
47+阅读 · 2020年6月6日
强化学习最新教程,17页pdf
专知会员服务
174+阅读 · 2019年10月11日
[综述]深度学习下的场景文本检测与识别
专知会员服务
77+阅读 · 2019年10月10日
机器学习入门的经验与建议
专知会员服务
92+阅读 · 2019年10月10日
相关资讯
word2Vec总结
AINLP
3+阅读 · 2019年11月2日
【泡泡汇总】CVPR2019 SLAM Paperlist
泡泡机器人SLAM
14+阅读 · 2019年6月12日
A Technical Overview of AI & ML in 2018 & Trends for 2019
待字闺中
16+阅读 · 2018年12月24日
Disentangled的假设的探讨
CreateAMind
9+阅读 · 2018年12月10日
NIPS 2017:贝叶斯深度学习与深度贝叶斯学习(讲义+视频)
机器学习研究会
36+阅读 · 2017年12月10日
【推荐】用Python/OpenCV实现增强现实
机器学习研究会
14+阅读 · 2017年11月16日
【推荐】SVM实例教程
机器学习研究会
17+阅读 · 2017年8月26日
【学习】Hierarchical Softmax
机器学习研究会
4+阅读 · 2017年8月6日
Top
微信扫码咨询专知VIP会员