论文标题
随机线性优化永远不会因一般数据的四次结合损失而过量
Stochastic linear optimization never overfits with quadratically-bounded losses on general data
论文作者
论文摘要
这项工作为线性预测指标上的迭代固定点方法提供了测试错误界限 - 特别是随机和批次镜下降（MD）和随机的时间差学习（TD），并具有两个核心贡献：（a）单一的证明技术，即使不具有预测，正规化，或任何相等的损失，也可以提供高概率保证，即提供统一的平方和逻辑损失处理）； （b）不取决于全局问题结构（例如条件数量和最大利润率）的本地适应率，而是基于可能遭受一些多余测试误差的低规范预测因子的属性。证明技术是一个基本和多功能的耦合参数，在以下设置中在此进行了证明：随机MD在可靠性下；一般马尔可夫数据的随机MD；一般IID数据的批量MD；重尾数据的随机MD（仍然没有预测）；马尔可夫链上的随机TD（所有先前的随机TD边界都在预期）。
This work provides test error bounds for iterative fixed point methods on linear predictors -- specifically, stochastic and batch mirror descent (MD), and stochastic temporal difference learning (TD) -- with two core contributions: (a) a single proof technique which gives high probability guarantees despite the absence of projections, regularization, or any equivalents, even when optima have large or infinite norm, for quadratically-bounded losses (e.g., providing unified treatment of squared and logistic losses); (b) locally-adapted rates which depend not on global problem structure (such as condition numbers and maximum margins), but rather on properties of low norm predictors which may suffer some small excess test error. The proof technique is an elementary and versatile coupling argument, and is demonstrated here in the following settings: stochastic MD under realizability; stochastic MD for general Markov data; batch MD for general IID data; stochastic MD on heavy-tailed data (still without projections); stochastic TD on Markov chains (all prior stochastic TD bounds are in expectation).
