| 面向大数据分析的在线学习算法综述 |
| |
| 引用本文： | 郎璇聪, 李春生, 刘勇, 王梅. 基于稳定性分析的非凸损失函数在线点对学习的遗憾界[J]. 计算机研究与发展, 2023, 60(12): 2806-2813. DOI: 10.7544/issn1000-1239.202220221 |
| |
| 作者姓名： | 郎璇聪 李春生 刘勇 王梅 |
| |
| 作者单位： | 1.东北石油大学计算机与信息技术学院 黑龙江大庆 163318;2.黑龙江省石油大数据与智能分析重点实验室（东北石油大学） 黑龙江大庆 163318;3.中国人民大学高瓴人工智能学院 北京 100872;4.大数据管理与分析方法研究北京市重点实验室（中国人民大学） 北京 100071 |
| |
| 基金项目： | 国家自然科学基金项目（51774090，62076234）；黑龙江省博士后科研启动金项目（LBH-Q20080）；黑龙江省自然科学基金项目（LH2020F003）；黑龙江省高校基本科研业务费项目（KYCXTD201903，YYYZX202105） |
| |
| 摘 要： | 点对学习（pairwise learning）是指损失函数依赖于2个实例的学习任务. 遗憾界对点对学习的泛化分析尤为重要. 现有的在线点对学习分析只提供了凸损失函数下的遗憾界. 为了弥补非凸损失函数下在线点对学习理论研究的空白，提出了基于稳定性分析的非凸损失函数在线点对学习的遗憾界. 首先提出了一个广义的在线点对学习框架，并给出了具有非凸损失函数的在线点对学习的稳定性分析；然后，根据稳定性和遗憾界之间的关系，对非凸损失函数下的遗憾界进行研究；最后证明了当学习者能够获得离线神谕（oracle）时，具有非凸损失函数的广义在线点对学习框架实现了最佳的遗憾界$O({T^{ - 1/2}})$.
|
| 关 键 词： | 在线点对学习 非凸 稳定性 遗憾界 离线优化神谕 |
| 收稿时间： | 2022-03-14 |
| 修稿时间： | 2023-01-30 |
Online learning algorithms for big data analytics: A survey |
| |
| Lang Xuancong, Li Chunsheng, Liu Yong, Wang Mei. Regret Bounds for Online Pairwise Learning with Non-Convex Loss Functions Using Stability Analysis[J]. Journal of Computer Research and Development, 2023, 60(12): 2806-2813. DOI: 10.7544/issn1000-1239.202220221 |
| |
| Authors: | Lang Xuancong Li Chunsheng Liu Yong Wang Mei |
| |
| Affiliation: | 1.College of Computer and Information Technology, Northeastern Petroleum University, Daqing, Heilongjiang 163318;2.Heilongjiang Provincial Key Laboratory of Petroleum Big Data and Intelligent Analysis (Northeastern Petroleum University), Daqing, Heilongjiang 163318;3.Gaoling School of Artificial Intelligence, Renmin University of China, Beijing 100872;4.Beijing Key Laboratory of Big Data Management and Analysis Methods (Renmin University of China), Beijing 100071 |
| |
| Abstract: | Pairwise learning refers to a learning task which involves a loss function depending on pairs of instances. Recently, there is a growing interest in studying pairwise learning since it includes many important machine learning tasks as specific examples, e.g., metric learning, AUC maximization and ranking. Regret bounds are particularly important for generalization analysis of online pairwise learning. The existing online pairwise learning analysis provides regret bounds only with convex loss functions. To fill the gap in the theoretical study of online pairwise learning with non-convex loss functions, we present a systematic study on the generalization analysis for online pairwise learning and propose regret bounds for non-convex online pairwise learning in this paper. We consider online learning in an adversarial, non-convex setting under the assumption that the learner has access to an offline optimization oracle and the learner’s prediction with expert advice. We first propose a general online pairwise learning framework and establish the stability of online pairwise learning with non-convex loss functions. Then, the regret bounds can be derived naturally from stability. Finally, we show that the general online pairwise learning framework with non-convex loss functions achieves optimal regret bounds of $O({T^{ - 1/2}})$ when the learner has access to an offline optimization oracle. |
| |
| Keywords: | online pairwise learning non-convex stability regret bounds offline optimization oracle |
|
| 点击此处可从《计算机研究与发展》浏览原始摘要信息 |
|
点击此处可从《计算机研究与发展》下载全文 |
