We prove impossibility results for adaptivity in non-smooth stochastic convex
optimization. Given a set of problem parameters we wish to adapt to, we define
a "price of adaptivity" (PoA) that, roughly speaking, measures the
multiplicative increase in suboptimality due to uncertainty in these
parameters. When the initial distance to the optimum is unknown but a gradient
norm bound is known, we show that the PoA is at least logarithmic for expected
suboptimality, and double-logarithmic for median suboptimality. When there is
uncertainty in both distance and gradient norm, we show that the PoA must be
polynomial in the level of uncertainty. Our lower bounds nearly match existing
upper bounds, and establish that there is no parameter-free lunch.

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