在已知设计向量前提下,用先验优化无界损失的在线学习误差上界。
Refined Risk Bounds for Unbounded Losses via Transductive Priors
- 利用事先已知的设计向量构建依赖于数据的先验,改进在线学习算法。
- 分类误差仅依赖维度和轮次数,与数据或最优参数大小无关。
- 适用于无界损失场景,特别适合对统计性能有严格要求的研究者。
我们重新审视平方损失下的线性回归、合页损失下的分类问题以及逻辑回归等序列学习任务,这些任务均在不假设设计向量大小或最优参数范数的条件下进行,且损失函数无界。关键区别在于,我们假设设计向量集合已知(但顺序未知),即所谓的转导式在线学习设定。尽管该假设看似类似固定设计回归或去噪,但我们证明,序列算法可将这些边界转化为随机设计下的统计界,而无需额外关于设计分布的假设——这是标准去噪结果无法实现的。核心工具是使用精心设计的转导先验的指数加权算法,充分利用了全部设计向量的信息。我们的分类后悔界具有文献中仅见于有界损失的特性:仅依赖参数空间维度和轮次数,与设计向量或最优解范数无关。对于平方损失的线性回归,我们进一步分析稀疏情形,给出了依赖于响应变量大小的稀疏后悔界。我们认为这些改进的边界特属于转导设置,在最坏情况的序列设定中不可达。在某些情况下,我们的算法具有多项式时间近似,并退化为对对数凹测度采样,而非对难以构造的ε-覆盖进行聚合。
原文摘要 · Abstract (English)
We revisit the sequential variants of linear regression with the squared loss, classification problems with hinge loss, and logistic regression, all characterized by unbounded losses in the setup where no assumptions are made on the magnitude of design vectors and the norm of the optimal vector of parameters. The key distinction from existing results lies in our assumption that the set of design vectors is known in advance (though their order is not), a setup sometimes referred to as transductive online learning. While this assumption seems similar to fixed design regression or denoising, we demonstrate that the sequential nature of our algorithms allows us to convert our bounds into statistical ones with random design without making any additional assumptions about the distribution of the design vectors--an impossibility for standard denoising results. Our key tools are based on the exponential weights algorithm with carefully chosen transductive (design-dependent) priors, which exploit the full horizon of the design vectors. Our classification regret bounds have a feature that is only attributed to bounded losses in the literature: they depend solely on the dimension of the parameter space and on the number of rounds, independent of the design vectors or the norm of the optimal solution. For linear regression with squared loss, we further extend our analysis to the sparse case, providing sparsity regret bounds that additionally depend on the magnitude of the response variables. We argue that these improved bounds are specific to the transductive setting and unattainable in the worst-case sequential setup. Our algorithms, in several cases, have polynomial time approximations and reduce to sampling with respect to log-concave measures instead of aggregating over hard-to-construct $\varepsilon$-covers of classes.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品;中文卡片由大模型生成,请以原文为准。