Feb, 2024

随机凸优化中的适应性代价

TL;DR证明了在非光滑随机凸优化中的灵活性的不可能性结果,并引入了 “自适应性的代价”(PoA) 的概念来衡量由于参数的不确定性而导致的次优解的多样化增长。通过理论推导,证明了在初始化距离和梯度范数都不确定的情况下,PoA 至少是对于预期次优值是对数级增长的,并且对于中值次优值是对数对数级增长的。而当距离和梯度范数都存在不确定性时,PoA 必须是不确定性程度的多项式级别。本研究的下界差不多与现有的上界相匹配,并且证明了没有免费的参数选择。