带有L1正则化问题的随机优化算法

作     者：杜康乐 

作者单位：浙江师范大学 

学位级别：硕士

导师姓名：张莹

授予年度：2023年

学科分类：12[管理学] 1201[管理学-管理科学与工程(可授管理学、工学学位)] 07[理学] 070105[理学-运筹学与控制论] 0701[理学-数学] 

主      题：结构风险最小 随机优化算法 牛顿算法 邻近算子 方差缩减 共轭梯度 

摘      要：随着科技的进步,各行各业产生了大量的数据,这些数据携带着丰富的信息.但是社会生产生活中采集到的数据都是最原始的数据,它们具有维数高、规模大的特点,往往包含大量的冗杂信息.如何处理这些数据,从中提取出需要的信息是一个重要的问题.将数据有效分类、剔除冗余是机器学习中一个最基本也是最重要的问题,又因为需要处理的数据量大且维数多,因此对机器学习模型的求解又可以归结为大规模优化问题的求解.本文正是基于机器学习这一热门话题,研究其中一类模型:“损失函数+L正则化问题.此问题中“损失函数部分为可微凸函数,“L正则化部分为不可微凸函数,因此整体目标函数为不可微的凸函数.对于该目标函数的求解,由于整体不可微,因此一般梯度算法无法适用.次梯度下降法可以对整体求微分,从而进行求解,但是这种算法受限较多且不稳定.近似点梯度法在梯度下降法的基础上引入临近算子,对目标函数可微的部分使用梯度下降法,对不可微的部分使用临近算子,从而达到求解整体目标函数的目的.本文正是基于这一思想,对梯度下降算法进行改进.由于数据规模大,应用梯度下降法求解目标函数需要巨大的计算量,所以引入了随机的概念,即按照均匀分布随机地从数据集中选取一个样本,这样可以极大地减少计算量,却会引入一个方差,导致收敛速度下降,从原有的O(1/K)降低到O((?)).针对这个问题,本文从降低方差的角度进行研究:第一种是运用方差缩减的技术SAGA,将之与牛顿法结合,再引入临近算子,从而提出一种新的方法——基于方差缩减的临近随机牛顿算法(SNVR),该算法加快了收敛速度,数值效果表现好;第二种是针对于SNVR算法中由于需要计算目标函数的Hessian阵,从而产生巨大的计算量的问题,考虑选用共轭梯度法,同时引入另一种方差缩减的技术SVRG,再将之与临近算子相结合,从而提出一种新的算法——基于方差缩减的共轭梯度法(ProxCGVR).本文对上述两种算法皆进行了收敛性分析,并进行了数值验证.最后,又结合实际问题,将算法SNVR应用于股票价格预测,进行实用性研究.