揭示向量输出线性预测的样本复杂度，连接单输出与高维优化问题。
Complexity of Vector-valued Prediction: From Linear Models to Stochastic Convex Optimization
- 给出向量输出预测的精确样本复杂度下界，依赖目标维数k。
- 证明Erm达到ε误差需约k/ε²个样本，优于之前结果。
- 将一般凸优化问题转化为向量输出预测，揭示两类学习模型的桥梁作用。
我们研究向量值线性预测问题：即用一个矩阵将m维特征映射到k维目标。针对凸且Lipschitz损失函数的情形，提出若干新理论结果，揭示该问题的复杂性及其与相关学习模型的联系。首先，给出了经验风险最小化（ERM）的紧致样本复杂度下界，表明达到ε过剩（总体）风险需至少˜Ω(k/ε²)个样本；相比Magen和Shamir（2023）的工作，在目标维数k上的依赖关系实现指数级改进，并与Maurer（2016）的经典上界一致。其次，提出一种黑箱转换方法，可将任意d维随机凸优化（SCO）问题嵌入为具有k=Θ(d)输出的预测问题。这些结果表明，向量值线性预测是连接经典线性模型（对应k=1）与一般d维随机凸优化（对应k=Θ(d)）两类广泛研究模型的重要桥梁。
原文摘要 · Abstract (English)
We study the problem of learning vector-valued linear predictors: these are prediction rules parameterized by a matrix that maps an $m$-dimensional feature vector to a $k$-dimensional target. We focus on the fundamental case with a convex and Lipschitz loss function, and show several new theoretical results that shed light on the complexity of this problem and its connection to related learning models. First, we give a tight characterization of the sample complexity of Empirical Risk Minimization (ERM) in this setting, establishing that $\smash{\widetildeΩ}(k/ε^2)$ examples are necessary for ERM to reach $ε$ excess (population) risk; this provides for an exponential improvement over recent results by Magen and Shamir (2023) in terms of the dependence on the target dimension $k$, and matches a classical upper bound due to Maurer (2016). Second, we present a black-box conversion from general $d$-dimensional Stochastic Convex Optimization (SCO) to vector-valued linear prediction, showing that any SCO problem can be embedded as a prediction problem with $k=Θ(d)$ outputs. These results portray the setting of vector-valued linear prediction as bridging between two extensively studied yet disparate learning models: linear models (corresponds to $k=1$) and general $d$-dimensional SCO (with $k=Θ(d)$).
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。