tceic.com
学霸学习网 这下你爽了
赞助商链接
当前位置:首页 >> >>

Lasso问题的最新算法研究-论文


I S S N  1 0 0 4 — 9 03 7 , CODEN  S CYCE4  

J o u r n a l   o f   Da t a   Ac q u i s i t i o n   a n d   Pr o c e s s i n g   Vo 1 . 3 0, No .1 , J a n . 2 0 1 5, P P . 3 5— 4 6   D oI : 1 0 . 1 6 3 3 7 / j . 1 0 0 4 — 9 0 3 7 . 2 0 1 5 . 0 1 . 0 0 3  

h t t p : / / s j c j . n u a a . e d u . c n   E — ma i l : s j c j @n u a a . e d u . c a   Te l / Fa x: +8 6 - 0 2 5 — 8 4 8 9 2 7 42  

◎ 2 0   1   5   b y   J o u r n a l   o f   D a t a   Ac q u i s i t i o n   a n d   P r o c e s s i n g  

La s s o问题 的最 新 算 法研 究 
刘  柳   陶大程  
( 悉 尼 科 技 大 学 工 程 与信 息 技 术 学 院量 子 计 算 与 智 能 系 统 研 究 中心 , 悉尼 , 澳 大利 亚 , 2 0 0 7 )  

摘  要 :随 着 大规 模 数 据 的增 加 , 解决 L a s s o问题 成 为 一 个新 的 热 点 , 以往 的 方 法很 难 满 足 大 数 据 背 景  下 的 时 间 和 效 率 问题 。为 了解 决 大规 模 数 据 及 高维 数 据 而 带 来 的 计 算 和 储 存 的 困难 , 本 文 从 三 个 方 面  分析 最 新 的 算 法 , 即一阶方法 、 随 机 方 法及 并 行 和 分 布 计 算 。本 文 介 绍 和 分 析 了解 决 最 小收 缩 和 选 择 算 

子( L e a s t   a b s o l u t e   s h r i n k a g e   a n d   s e l e c t i o n   o p e r a t o r , L a s s o ) 问题 的 最 新 算 法 : 梯度下降方法 、 交 替 方 向 乘 
子 法( Al t e r n a t i n g   d i r e c t i o n   me t h o d   o f   mu l t i p l i e r s ,AD MM ) 和 坐标 下 降 方 法 。其 中梯 度 下 降 结合 一 阶 方  法 和 Ne s t e r o v的 加 速 和 光 滑技 术 ; 交替 方 向 乘 子 方 法 将 随 机 方 法 融 入 在 最 新 的 算 法 中; 坐 标 下 降 方 法 

利 用其 坐标 系的 特 点 结 合 一 阶 方 法 、 随机方法和并行和分布计算 , 本 文 分 别 从 原 始 目标 函数 和 对 偶 目标 
函数 的 角度 对 算 法进 行 分 析 和研 究 。  

关 键 词 :L a s s o问题 ; 一阶方 法; 随机 方 法 ; 交替 方 向 乘子 法 ; 坐标 下 降 
中 图分 类 号 :TP1 8 1   文献 标 志 码 : A  

Re v i e w  o n   Re c e n t   Me t h o d   o f   S o l v i ng   La s s o   Pr o b l e m 
Li u   Li u,Da c h e n g   Ta o  
( Qu a nt um  Co mp ut a t i o n& I n t e l l i g e nt   Sy s t e ms ,Fa c u l t y   o f   En g i n e e r i n g   a n d   I n f o r ma t i o n   Te c h n o l o g y,Un i v e r s i t y   o f   Te c h no l o g y。  
S y d n e y ,Aus t r a l i a ,2 0 0 7 )  

Ab s t r a c t :W i t h   t he   i nc r e a s e   o f   b i g   d a t a ,s o l v i n g   La s s o   p r o b l e m  b e c o me s   t o p   r e s e a r c h   f i e l d .Pa s t   me t h o d s   c o u l d   n o t   s a t i s f y   t h e   t i me   a n d   e f f i c i e n t   p r o b l e m  u nd e r   b i g   d a t a   s i t u a t i o n .I n   o r d e r   t o   d e a l   wi t h   d i f f i c u l t y   o f   c o mp u t a t i o n   a n d   s t o r a ge   b r i n g i n g   f r o m  h u g e — s c a l e   a nd   h i g h — d i me n s i o n   d a t a,t h i s   p a p e r   a n a l y z e   t he   r e c e n t   La s s o   a l g o r i t h m  f r o m  t h r e e   a s p e c t s:o n e — o r d e r   me t h o d,r a n d o m ,a n d   p a r a l l e l   a n d   d i s t r i b u t e d   c o mp u t a —   t i o n,wh i c h   p l a y   a n   i mp o r t a n t   r o l e s   i n   d e a l i ng   wi t h   h ug e — s c a l e   d a t a   p r o bl e m . Ba s e d   o n   t h o s e   t h r e e   a s —   p e c t s ,t h i s   p a pe r   i n t r o d u c e s   a n d   a n a l y z e s   t h e   n o v e l   a l g o r i t h ms :gr a d i e n t   d e s c e n t   me t h o d,Al t e r n a t i n g   Di —   r e c t i o n   me t h o d   o f   mu l t i p l i e r s( A DM M ),a n d   c o o r d i n a t e   d e s c e n t   me t h o d . Gr a d i e n t   d e s c e n t   me t h o d   c o m—  

b i n e   o n e — o r d e r   me t h o d   a nd   Ne s t e r ov   S   a c c e l e r a t e   a n d   s mo o t h i ng   me t h o d; A DM M   p u t   t h e   r a n d o m  a l g o —   r i t hm  i n t o   t h e   r e c e nt   r e s e a r c h;Co o r d i na t e   d e s c e n t   ma k e   u s e   O f   t he   c h a r a c t e r   o f   c o o r d i n a t e   s y s t e m  i n c o r —  
p o r a t i o n   o n e — or d e r   me t h o d, r a nd o m ,a n d  p a r a l l e l   a nd   d i s t r i b u t e d   c o mp u t a t i o n . Mo r e o v e r ,t h i s   p a p e r  

ma k e s   a   d e e p   a n a l y s i s   a n d   r e s e a r c h   f r o m  p r i ma l   a n d   d u a l   o b j   e c t i v e   f u n c t i o n .  
Ke y   wo r d s :La s s o   p r o b l e m ;o n e — o r d e r   me t h o d;r a nd o m  me t h o d;ADM M ;c o o r d i n a t e   d e s c e nt   me t h o d  

收稿 日期 : 2 0 1 4 — 1 0 — 1 0 ; 修 订 日期 : 2 0 1 4 — 1 2 - 3 0  

3 6  

数 据 采 集 与 处理 J o u r n a l   o f   I D a t a   Ac q u i s i t i o n   a n d   Pr o c e s s i n g   Vo 1 . 3 0 , No . 1 ,2 0 1 5  

引 

言 
随 着 科技 的进 步 , 收 集 数 据 的技 术 也 有 了 很 大 的 发 展 。 因此 如 何 有 效 地 从 数 据 中挖 掘 出有 用 的 信 

息 也 越 来 越 受 到 人们 的关 注 。一 般 采 用 基 于 机 器学 习 和 统 计 的方 法 来 解 决 大 规 模 数 据 , 这 种 趋 势 称 为  “ 大数据” 。它在 很 多领 域 中起 着 非 常 重 要 的 作 用 , 如人工智 能 、 网络 应 用 、 计算生 物 、 医学 、 金 融 和 市 场 

等 。虽 然 应 用在 不 同 的方 面 , 但 是 大 数 据 问 题 却 又 几个 共 同 的特 点 : ( 1 ) 数据量非常大 , 包 含 几 百 万 个 或  上亿个训练样本 ; ( 2 ) 数 据 的维 度 很 高 , 通 常 会详 细 记 录 每 一 个 样 本 的 的信 息 ; ( 3 ) 大 规模 的 数 据 通 常 以  
分 布 式 的 方 式储 存 或 收集 。在 机 器 学 习 的算 法 中 , 对 最 新 算 法 的要 求 既 能 够 解 决 数 据 的 复 杂 性 又 能 够  采 用 平 行 或 分 布 式 的 方 法处 理 大数 据 。   L a s s o问题 是 1 9 9 6年 Ti b s h i r a n i   使 用 u 惩 罚 因 子解 决 含 有 独 立 高 斯 分 布 的 线 性 回归 问 题 , L a s s o   问题 包 含 平 方 误 差 的 求 和 以及 L1正 则 化 项 。虽 然 L a s s o问题 出 现 的 比较 晚 , 然而正则 化项 早在 1 9 4 3  

年 T i k h o n o v 就 提 出用 来 逼 近 不 可解 的 整数 等 式 问 题 。通 常 情 况 下 , 在 参 数 中增 加 约 束 化 项 , 用 来 求 解 
评 估 问题 , 如 最 大 似 然 函 数 。正 则 化 项 用 来 减 小 变 量 从 而 避 免 过 拟 合 , 得 到 的正则化 项 的解更 稳 定 ,   B i c k e l l 2   给 出 了 正则 化 项 在 统 计 理 论 中详 细 的 分 析 。  

L a s s o问题 在 解 决 稀 疏 规 划 中起 着 非 常 重 要 的作 用 。它 可 以解 释 为 寻 找 最 小 二 乘 或 线 性 回归 问 题  的稀 疏 问题 , 即采 用 若 干 个 非零 的 变量 。L a s s o问题 在 信 号 处 理 领 域 中 同 样 起 着 重 要 的作 用 , 包 括 解 决  稀疏 信 号修 复  、 稀疏 回 归   ] 、 稀 疏 图 回 归  ] , 稀 疏 逆 协 方 差  和 稀 疏 字 典 的 学 习口 ] 。生 物 数 据 的 分 
析 ] , 比如 选 取 大 数 据 中 的- -4 , 部 分 来 预 测 结 果 。L a s s o问题 同 样 可 以应 用 在 视 频 中 , Ge n g   采 用 并 行  L a s s o的 方 法 解决 大 规 模 视 频 概 念 检 测 , Z h u l 5   使 用 Gr o u p   L a s s o解 决 视 频 标 签 以及 Z h o u   用 稀疏 离 群 

值分 割移 动 目标 。在 图像 处 理 中 , A f o n s o   使用 L a s s o方法 解 决 图像 修 复 、 图像 去 噪  和 去 模 糊  , 其  中正 则 化项 是 图像 的梯 度 范 数 、 网页 图 像 排 序  及 图像 质 量 评 估  , 利 用 稀 疏 编码 处 理 图像 标 签  问  
题 。在 遥感 领域 中 , L a s s o问题 用 来 解 决 稀 疏 解 混  删 , 从 而 可 以得 到 每 个 端 元 都 含 有 哪 些 物 质 , 在 航  天、 农业领域 , 对 研 究 物 质 成 分 问题 起 着 非 常 重 要 的 作 用 。   解决 I   a s s o问题 的方 法 有 很 多 , 其中E f r o n _ 1  2 0 0 4年 提 出 最 小 角 回 归 , 它 能 够 有 效 地 解 决 潜 在 的 

L a s s o 优 化 问题 , 同时 在 统 计 和 机 器 学 习 领域 , 它 为加速 L a s s o算 法 提 供 了一 个 重 要 的 工 具 。在 解 决 大 
规模数据问题 中, 梯 度下 降方 法 是 最 简 单 的方 法 。Ne s t e r o v   提 出最 优 的 梯 度 下 降 方 法 和 光 滑 模 型 ,  

在 L a s s o问 题 中 被广 泛 的应 用 , 如 快 速 的 交 替 方 向优 化 方 法  , 锥 模 型 优 化 方 法  以 及 快 速 迭 代 收 缩 
阈值 方 法  。随 着 数 据 量 的 增加 , ADMM 能 够 解 决 大 数 据 问题 , 并且 已经成 功地应 用在很 多领域 , 包 

括解决 L a s s o问 题 , Be c k l 2  结 合 Ne s t e r o v的加 速 方 法 , 提 出了快速 的方法 , 其中T o m[ 2  提 出 了 快 速 的 

A D MM 方 法 。最 近 的研 究 者 T a i j i _ 2   驯 和 Hu a   。   结 合大数据 的特点 采用随机 的方法 , 在 原 有 算 法 的 基  础上 , 提 高 了算 法 的收 敛 率 ,   在 大 数 据 背 景 下 随 机 坐 标 下 降 方法 成 为一 个 新 的热 点 , 而 随 机 优 化 方 法 在 解 决 高 维 数 据 和 大 规 模  样 本 有 至关 重 要 的作 用 。N e s t e r o v l 2  和 J i [ 。  分 别 给 出 了随 机 坐标 下 降方 法 的理 论 分 析 和 证 明 。越 来 越  多 的 基 于 随机 优 化 方 法 出 现 在 L a s s o问 题 , 包 括 原 始 随 机 坐 标 下 降 方 法  法口   和 原 始 随 机 对偶 坐标 下 降方 法  , 对 偶 随 机 坐 标 下 降 方  , 而 且 基 本 的 随 机 下 降 坐 标 方 法 结 合 了 一 阶 最 优 方 法【 3  、 随 

机 方 法 和并 行分 布 系统 , 这 三 个 方 面 在 解 决 大 规模 数 据 中起 着 非 常 重 要 的作 用 , 弥 补 了一 般 算 法 在 大 数 
据背景下的不足 , 其 中 Ne s t e r o v加 速 的一 阶 最 优 方 法 , 只需要 一阶梯度 信息 , 从 而运算 复杂度 小 、 速 度 

快; 随 机 的 方 法 主要 考 虑大 数 据 的本 质 , 因为 最 终 决 定 最 优 解 的 信 息 并 不 需 要 全 部 的 数 据 , 如 果 全 部 的 
数据都用 来 计 算 不 仅 需 要 更 多储 存 空 间, 而且会 消耗更多 的时间, 从 而 影 响 算 法 的 性 能 。 最 近 

Av r o n  训 介 绍 了在 随 机 梯 度 和 随 机 坐 标 下 降 方 法 下 的 多 核 运 算 ,   算 法 中提 出异 步 并 行计 算 提 高 收敛 率 。  

在 Ka c z ma r z 算 法 和 坐 标 下 降 

刘柳 等 : L a s s o问题 的 最 新 算 法 研 究 

3 7  

在解决 L a s s o问 题 的过 程 中 , 很 多 实 验 室 公 开 了软 件 包 和 代 码 , 以供 大 家 学 习 和 研 究 , 其 中包 含 凸 

优化模型框架 C V X   , 它 可 以用 来 解 决所 有 的 凸优 化 问题 ; 压缩感知包 1 1 一 MAG I C   , 它 将 问 题 转 化 为 
两阶凸规划 ( S e c o n d - o r d e r   c o n e   p r o g r a m ,S OC P s ) , 一 阶锥 模 型 ( Te mp l a t e s   f o r   f i r s t — o r d e r   c o n i c   s o l v e r s ,   TF OCS )   , 它 主要 是 将 问题 转 化 为 标 准 的 锥模 型 , 并利用一阶优化方法 ; 共 轭 梯 度 迭 代 方法 ( Co n j u g a t e   g r a d i e n t   i t e r a t i v e   s h r i n k a g e / t h r e s h o l d i n g , C GI S T)   , 它 主要 结 合 向 前 向后 分 裂方 法 和加 速 步 长 方 法 。  

1  L a s s o问题 
在 机 器 学 习 的优 化 算 法 中 , 一 般 的 凸优 化 问题 可 以表 示 为 

m   i n   P (   ) 一  
其 对 偶 函 数 为 

(  ) +  (   ) )  

( 1 )  

{  : 砉 一  一, 一 A g   ( ÷ 砉  ) )  
式中 : a   , …, a  ∈ R  为 ; 7 1 " 个数据样本向量;   , …,   为损 失 函数 ;   … . ,   为  的 共 轭 函 数 ; g   (?) 为 正 则 化 函数 ; g  (?) 为 g的共 轭 函 数 ;  为原始变量 ; Y为 对 偶 变 量 ;  ≥0为 正 则 化 参 数 。  

每一个样本数据 n   对应着一个独立的变量 b   , 当 仍( a T x ) 一寺 ( a T x —b   )   , g (   ) =l  l _ 1 l , 即得到  
z  约束 线 性 回归 的 特 殊 形 式 , 称为 L a s s o问 题 _ 1 ] , 即 

mi n÷ } l   A x—b   +  l l  l     J

( 3 )  

式中 : 变 量 xE   R   ; 矩 阵 A∈R   ; b E   R  ;  > 0是 尺 度 约束 参 数 。La s s o问题 可 以解 释 为寻 找最 小 二  乘 或线 性 回归 问 题 的 稀 疏 解 。  

1 . 1   一般 的 L a s s o问题 

mi n ÷ l   l A x—b   l l ; +  l l   l   l
其 中 F是 任 意 的线 性 变 换 , 一 个 特 殊 的例 子是 当 F为 差 异 矩 阵 时 , 有 
f   1   F  一 一 1   J— i +1   J— i  

( 4 )  

( 5 )  

【 0  

其他 

这 个 问题 转 变 为 T V 降 噪 问题  , 在 信 号 处 理 中有 广 泛 的应 用 。当 A—I , F是 二 次 差 分 矩 阵 , 问 题 
变 为 L1趋 势 滤 波  , 用 来 分 析 在 不 同学 科 中 的 时 间 序 列 数 据 。更 新  的迭 代 过 程 中 , 矩阵A   A+ F   F  是 五对 角矩 阵 , 只需 运 行 0(  ) 的浮点运算 。   1 . 2   组 La s s o问题 

m i n   1   l   I A x —b  +   ∑ 
式 中  一 (  

l  

一 ,   ) , X   ∈R   , 每一个正则化约束项都是分 开 的, 但并不 是完全 的分开 , 这种 L 1 范 

数 约束 的 扩展 问题 称 之 为 组 L a s s o问题  “  , 或者叫做 S u m  o f   n o r ms   r e g u l a r i z a t i o n   , 解 决组 L a s s o问  题 一 般 采 用 分 裂 的方 法 , 并 对 每 一个 子 问 题 进 行 L a s s o问题 的 处 理 。  

随着 大规 模 数 据 的增 加 , 以 往解 决 L a s s o问 题 的 方 法 很 难 满 足 人 们 对 时 间 和 效 率 的 要 求 。 当 数 据 
的维 度 越 来 越 大 , 函数 值 或 梯 度值 计 算 就 会 变 得 越 来 越 困难 , 尤 其 是 当数 据 的 空 间维 度 大 于存 储 空 间  时, 一 般 的梯 度 方 法将 不 再适 用 。如 果储 存 空 间 不 影 响 梯 度 的 运 算 , 那 么 大 数 据 的 运 算 可 能会 消耗 更 多 

3 8  

数 据 采 集 与 处理 J o u r n a l   o f   Da t a   Ac q u i s i t i o n   a n d   Pr o c e s s i n g   Vo 1 . 3 0 , No . 1 ,2 0 1 5  

的时间, 从 而 在 实 际应 用 中会 受 到影 响 , 比如 图像 处 理 过 程 。 除 了 数 据 的 大 小 , 并 不 是 所 有 的数 据 都 要  用 来 描 述 机 器 学 习 的 相 关 问题 , 其 中一部分数 据就 可以解决 优化 问题 , 而 不 是 等 到 全 部 的 数 据 都 处 理 
完 。所 以解 决 这 些 问题 的方 法 不 仅 要 考 虑 算 法 的复 杂 度 , 而 且 还 应从 实 际 问题 出发 , 考 虑 如 何 能 够 更 快  地 解 决 大 规 模 数 据 带 来 的 困难 。  

2  L a s s o问题 解 决 方 法 
大规 模 数 据 下 的 L a s s o问题 主要 面临 着 计 算 复 杂 度 和 时 间 复 杂 度 问 题 , 而 解 决 这 些 问 题 主 要 从 三 

个 方 面考 虑  : ( 1 ) 一 阶方 法 。一 阶 方法 使 用 目标 函数 的梯 度 信 息 , 虽 然 获 得 较 低 或 中等 精 确 的数 值 结 
果, 但 是相 比一 些 复 杂 的运 算 过 程 , 一 阶 方法 消耗 更 短 的 时 间 。根 据 邻 近 映 射 原 则 , 一 阶方 法 能 够 解 决 

非 光 滑 函 数 问题 , 并 且 适 合 分 布 和 并 行 计算 。 ( 2 ) 随 机 性 。随 机 问 题 在 其 他 的 逼 近 问题 中 尤 为 突 出 , 因  为 它 能 够 控 制期 望值 , 从 而 增 加 一 阶 方 法 的 可 扩展 性 。关 键 的 问题 是 随 机 更 新 部 分 变 量信 息 , 而不 是 全 
部的变量 , 进 而并 不 需 要 全 部 的 梯 度 信 息 ; 简单 的统计评估 就能 有很好 的计算 结果 ; ( 3 ) 并 行 和 梯 度 计 

算: 一 阶梯 度方 法 能 够 用 在 并 行 计 算 和 分 布 优 化 中 , 同 时还 可 以从 集 中通 信 的并 行 计 算 扩 展 到分 散 通 信 
的异 步 算 法 。这 3个 方 面 在 大 数 据 中 起 着 重 要 的作 用 , 比如 随机 一 阶方 法 比确 定 策 略 的 方法 要 快 , 它 能  够 忽 略 一 小 部 分 信 息 而 获得 高 概 率 的最 优 目标 函 数 结 果  。  

2 . 1 梯 度 下 降 方 法 
梯 度 下 降 的 方 法 是 基 于一 阶方 法 , 利 用 局 部 梯 度 信 息 和 迭代 公 式 
X   一X   一a   f( x   )   ( 7 )  

当 目标 函数 为 光 滑 函 数 时 , 可 以使 用 更 快 的加 速 方 法 , 如牛顿方法 , 但 是 它 需 要 目标 函数 更 多 的信 

息, 比如 二 阶求 导 信 息 , 从 而 消耗 更 多 的 时 间 , 而 这 些 信 息 并 不 容 易 在 约 束 函数 和 非 光 滑 函数 中得 到 。   梯 度 下 降 法 却 弥 补 了这 些 缺 点 。一 般 的梯 度 下 降 方 法 需 要 0 ( I / e ) 的迭代次数才 能达到 £ 的精确结果 。  
Ne s t e r o v   提 出 了一 个 改 进 , 增 加 一 个 额 外 的 动量 步长 . 8 一是 / ( 走 +1 ), 从 而 到 达 到 0( 1 / e   ) 的迭代次 数 ,   这种 方 法 称 为 最 优 一 阶 方 法 。表 1给 出 了加 速 方 法 在 凸 函 数 和 强 凸 函数 中 的算 法 复 杂 度 。为 了能 够 得 

到强 凸 函数 , 可 以在 目标 函数 中 增加 约 束 化 项 。 因为 如 果 函数 f ( x ) 一/  ̄ / 2 x ; 是 凸 函数 的 , 那 么 是 厂(   )  
强 凸 函数 , 所 以非 光 滑 函数 也 可 以有强 凸 函数 的性 质 , 在 L a s s o函数 中增 加 一 个 约 束 项 , 即 g(  ) =X   +  /  ̄ / 2 x ; 。  
表 1 梯 度 下 降 方 法 的 算 法 复 杂 度 比较 
Ta bl e   l   Co mp l e xi t y   o f   t he   a l g o r i t hm  c o m pa r i s o n   o f   g r a di e nt   a s c e nt   me t ho d  

2 . 1 . 1   邻 近 梯 度 方 法 

邻 近 算 法  可 以 看 成是 解 决 非 光 滑 、 约束 、 大 规 模 和 分 布 式 问 题 的 工 具 。邻 近 算 法 可 以 看 成 是 求 
解一部分凸优化问题 , 从 邻 近运 算 定 义 可 以看 出 
,   1   、  

p r o x   ( . ) , ) 一a r g m i n { g (   ) +寺 l   —Y   I I ; }  
、  

( 8 )  

函数 的邻 近 运 算 等 价 于 求 解 函数 的梯 度 步长 p r o x   ( y ) 一Y —   g (   )。   L a s s o函 数是 一 般 混 合 目标 函数 的 一 种 特殊 形式 , 邻 近 梯 度 方 法 可 以 利 用 混 合 函数 的性 质 , 获 得 在  光滑 梯 度 方 法 下 的相 同的 收 敛速 度 ( 如表 1 ) , 邻 近梯 度 方 法 可 以看 成 是 最 优 梯 度 方 法 的 扩 展 , 于 是 原 始  的L a s s o问题 结 合 最 优 梯 度方 法 和邻 近梯 度 方 法 , 得到基于 X   展 开 的 目标 函数 

刘柳 等 : La s s o问题 的 最 新 算 法研 究 

3 9  

一 a r g   i “ { _ 厂 (   ) + V f ( x   )   (   一  ) + 壶l   l y 一  l l ; + g ( y ) j  
应 用 Ne s t e r o v的加 速 方 法 , 得 到加 速 的邻 近梯 度 方 法 
X k +  一 p r o x  ( v   一a ^   f( v   ))  
… 一X   +  (   )  

( 9 )  
( 1 0 )  

在 L a s s o问题 中 g( z ) 为 L1范 数 , 邻 近 运 算 可 以通 过 软 阈值 的方 法 求 解 , 这 种 加 速 的 方 法 称 为 快 速  收 缩 阈值 算 法 ( F a s t   i t e r a t i v e   s h r i n k a g e / t h r e s h o l d i n g   a l g o r i t h m, F I S TA)   。除 了 在 迭 代 步 骤 能 够 减 少 

迭代次数 、 增 加 收敛 率 , B l a c k f o r d  
2 . 1 . 2 对 偶 锥 方 法 

采 用 了并 行 矩 阵 一 向量 相 乘 的方 法 来 加 速 运算 。  

对 偶 锥  方 法 结 合 对 偶 、 光 滑和一阶优 化方法 , 用 来 解 决 一 般 的 凸 锥 优 化 问题 。该 方 法 的 优 点 是  能够得到稳定 、 有 效 的迭 代 方 法 。不 用 于邻 近梯 度 方 法 , 对 偶 锥 方 法 在 对 偶 函数 中加 入 一 阶 优 化 方 法 。  

在 原 始 函数 中 , 这 两 种 方 法 都 增 加 了 一个 约 束项 , 使 得 目标 函 数 为 强 凸 函数 , 从 而 达 到表 1中 的收 敛 速  度 。对 偶 锥 方 法 可 以看 成 是 不 断 的缩 减原 始 和对 偶 函数 差 值 , 当 原 始 函 数值 和 目标 函数 值 相 同 时 , 即 达 
到 最 优 解 。对 偶 锥 方 法 包 含 4个 步 骤 。   ( 1 ) 确 定 等 价 的锥 形 式 
La s s o问题 的 锥 形 式 可 以表 示 为 

mi n   l   l l   l 1   S . t .1   l ( 2 ) 确 定 对 偶 形 式  原 始 函数 不 采 用 一 阶优 化 方 法 有 几 种 可 能 : ( 1 ) 原函数非光 滑 ; ( 2 ) 投影在 l l   A   b   I I ≤£ 需 要 消 耗  大量 的时间 , 所 以将 问题 转 化 为 对偶 问 题 用 于 减 少 运 算 时 间 , 对 偶 问 题 表 示 为  ma x   i n f {1  
( 3 ) 应 用 光 滑技 术 

一b   l l≤ e  

( 1 1 )  

1 一< z , A x一 6 ) }  

( 1 2 )  

La s s o问 题 中 含 有 L1范 数 , 从 而 应 用 Ne s t e r o v的光 滑 技 术 , 在 原 目标 函数 中增 加 约束 项 , 得 到 光 滑 
的对 偶 问题 

D   (   ) 一m a x   i n f { l  I  +÷  l  — l   。 l ;  < z , A x 一6 > }  
( 4 ) 使 用 一 阶优 化 方法 

( 1 3 )  

在 对 偶 函数 中使 用 一 阶优 化 方 法 , 类似于邻近梯度方法 , 同样 采 用 Ne s t e r o v的 加 速 方 法 , 只 不 过 变 

量 增 加 了对 偶 变 量 。对 偶 锥 方 法 可 以 看 成 是 鞍 点 方 法 , 通过交替迭代优化原始函数和对偶函数 , 达 到 共  同 的最 优 解 。具 体 的算 法 过程 如 下 


( 1 一 O k )   +  z   ~   A  Y   ,   )  



S o f t Th r e s h o l d ( z 0  

z … 一 Sh r i nk( z  一  t  ( . ) , 一 As c  ),   £ 女 £)  

v … 一( 1一  ) V  +  z ¨ 1  

( 1 4 )  

式中: S h r i n k (?) 是1 。收 缩 运 算 , S o f t Th r e s h o l d (?) 是 软 阈 值 运 算 。 图 l表 示 的 是 模 拟 数 据 下 , 基 

于对 偶 锥 方法 和 加 速对 偶 锥 方 法 的 迭 代 结 果 , 其 中横 坐 标 是 外 部 迭 代 次 数 , 纵 坐 标 表示 迭代 点 与 最 优 点  的 迭代 误 差 l   一X l  l l  /l   l X  l  , l 从 图 1中可 以 看 出 , 基 于 Ne s t e r o v 加速的方法收敛更快 。   2 . 2 交 替 方 向 乘 子 方 法  交 替 方 向乘 子 ( Al t e r n a t i n g   d i r e c t i o n   me t h o d   o f   mu l t i p l i e r s , A D M M) 方 法  结 合 分 布 式 凸 优 化 问  
题, 适 合 解 决 大 规模 数 据 的 问 题 。ADMM 可 以看 成 是 融 合 对 偶 分 解 和 增 广 L a g r a n g i a n的 优 点 , 它 跟 很 

4 0  

数据采集与处理 J o u r n a l   o y   Da t a   Ac q u i s i t i o n   a n d   Pr o c e s s i n g   Vo 1 . 3 0 , No . 1 ,2 0 1 5  

外部迭代 次数 

图 I 对 偶锥 方 法 和加 速 的对 偶 锥方 法 
Fi g .1   Dua l   c on i c   a nd   a c c e l e r at e d   du a l   c on i c   me t h od  

多算 法 有 相 互 联 系 , 如 B r e g ma n迭 代 方 法 , D o u g l a s   Ra c h f o r d分 裂 方 法 及 Dy k s t r a交 替 投 影 方 法 等 。   ADMM 方 法 可 以追 溯 到 1 9 7 0年 , 它 在解 决 大规 模 分 布 计 算 系统 和 大 量 的 优 化 问题 中 起 着 非 常 重 要 的 
作用 。   在 ADMM 形 式 中 , I   a s s o问题 可 以看 成 
mi n f( x ) + g( z )   S . t .  
1  

— z一 0  

( 1 5 )  

N 

式中_ / 、 (   ) 一 专【 【 A x — b  , g (   ) 一   ∑  得 到 基 于A D M M的 算法  
1  

”一( A   A+ p J )   ( A   b+ p ( z  一 “   ))  
z   一S  (   “- + -   )  
l f   一H  +  … 一 z  

( 1 6 )  

式 中  的更 新 是岭 回归 过程 , 解决 L a s s o问题 的 ADMM 方 法 可 以解 释 为 交 替 实 施 岭 回归 过 程 。 图 2  

表示 的是模 拟 数 据 下 , ADMM 与 梯度 迭 代 方法 的 比较 。其 中红 色 曲线 表 示加 速 的 ADMM( F a s t - AD MM) ,  

趔 

鞴 
圆 

峰 
I 1 I I  

图 2   ADMM 方 法 和 梯 度 方 法 
Fi g .2   A DM M   a nd   gr a di e nt   me t ho d  

刘柳 等 : L a s s o问题 的 最 新 算 法研 究 

4 l  

黑 色 曲线 表示 ADMM , 绿 色表 示 加 速 的 邻 近 梯 度 放 方 法 , 蓝色表 示邻 近梯度 方法 , 虚 线 表 示 真 实 值 曲  线 。加 速 的 ADMM 比没 有 加 速 的 ADMM 方 法 能 够 更 快 的接 近 最 优 的 目标 函数 值 , 加 速 的邻 近 梯 度 方  法 相 对 于邻 近梯 度 方法 能 够更 快 的 达 到 最 优 的 函数 值 , 但是从 整体来 说 , ADMM 方 法 能 更 快 地 收 敛 最  优 目标 函 数 值 。  


般 的 ADMM 算 法 的收 敛 速 度 为 0( 1 / k ) , Go l d s t e i n [ 2  结 合 Ne s t e r o v   的 一 阶 最 小 方 法 能 达 到 0 

( 1 / k   ) 的全 局 收敛 速 度 。然 而 随着 数 据 的 快 速 增 加 , 如 自然 语 言 处 理 、 图像 识 别 和 生 物 信 息 等 , 随 机 优  化 算 法 已 成 为 在 机 器 学 习 中重 要 的 方 法 。S u z u k i _ 2   提 出 了 基 于 随 机 优 化 算 法 的 ADMM 方 法 , 同样 结 

合 Ne s t e r o v 一阶优化方法 , 应用在一般 的凸函数 , 其收敛速 度为 0( 1 / √ 忌 ) , 而对于强 凸函数能够 达到 0  
( 1 o g ( 忌 ) / 忌 ) 的 收敛 速 度 , S u z u l i   结合随机对偶 坐标下降方 法( S t o c h a s t i c   d u a l   c o o r d i n a t e   a s c e n t , S DCA)   和 ADMM , 由 于在 每次 迭代 中 需 要 一 个 或 多 个 样 本 , 所以 S DC A— ADMM 并 不 需 要 非 常 大 的储 存 空 间 ,   这 种 特 点 尤其 是 在 面 对 大 数 据 量 时 , 能 够 更 好 地 体 现 出算 法 的优 越 性 。   2 . 3 坐 标 下 降 方 法 

在 机 器学 习 中 , 坐 标 下 降 方 法  在 解 决 大 规 模 优 化 问 题 中 起 着 重 要 的作 用 , 尤 其 是 当 样 本 数 m 非 
常大 时 , 求 全 梯 度 或 次 梯 度需 要 消 耗 大 量 的 时 间 和 储 存 空 间 , 这 样 求 解 目标 函 数 的 子 函 数 问题 就 成 为 研  究 大规 模 问题 的 热 点 。 子 函 数 问 题 可 以看 成 选 取 坐 标 系 中 的 某 一 个 坐 标 或 某 一 组 坐 标 , 保 持 其 他 的 坐  标 系 的变 量 不 变 , 在每一次迭代过程 , 只 优 化 在 选 取 坐 标 系 下 的 目标 函 数 。   有 效 的坐 标 下 降方 法取 决 于 每 一 次 迭 代 过 程 消 耗 的 时 间 和 目标 函 数 的 下 降 量 。一 个极 端 的 方 法 是 

贪婪方法 , 即选 取 最 大 的 下 降 方 向 。但 是 贪 婪 方 法 面 临 的 问题 : ( 1 ) 要求 所有 的数据可行 ; ( 2 ) 可 能 会 超 
出计 算 机 的计 算 能 力 , 比如需 要计 算 全 梯 度 的 迭 代 步 长 , 而 不 是 某 个 坐标 系 下 的 迭 代 步 长 。另 外 两 个 选  择 坐标 系 的方 法 是 周期 和 随 机 , 一般的选择坐标方法是基于周期循环 , 循 环 坐 标 下 降 方 法 的全 局 和 局 部  收敛 性 质 在 文献 [ - 5 7  ̄ 中给出了详细的分析 , 它 主 要 分 析 了在 等 渗 性 假 设 下 的 光 滑 凸 函 数 。虽 然 周 期 循 

环 是 求 解 连续 坐 标 系 的 迭 代 过 程 , 但 是 并 不 是 在 所 有 坐 标 系 下 的求 解 对 目标 函数 都 产 生 影 响 。 随 机 选 
取 坐标 或 坐标 块 的 方 法 已经 成 为 在 大 规 模 数 据 分 析 中的 研 究 热 点 。随 机 选 择 坐 标 系 的 方 法 更适 合 大 规  模数据 , 最 近 的 研究 表 明 随 机 方 法 确 实 能 够 增 加 收 敛 率  。   。在 均 匀 概 率 下 , 随 机 选 择 坐 标 系 看 似 等 
效 于周 期 循 环 , 但 是 随 机 坐标 系 的选 择 能 够 避 免 周 期 循 环 下 最 糟 糕 的 情 况 , 比如 某 些 坐 标 系下 的 数 据 对 

目标 函数 并 没 有 作 用 。 除 了均 匀 概率 , 不 同 的 概率 密 度 函 数 同样 可 以 增 加 收敛 速 度 。 同 时 , 并 行 分 布 式  运 算 也 可 以用 在 坐标 下 降 方 法 中 , 从 而达到更好的运算效率 。  
Ne s t e r o v加 速 方 法 已经 成 功 地 应 用 在 全 梯 度 下 降 方 法 , 将 Ne s t e r o v的 加 速 方 法 应 用 在 随 机 坐 标 下 
降 方 法 中 已经 在 文 献 [ 2 1 , 3 4 ] 中进 行 了 分 析 。Ne s t e r o v 口  提 出 了 一 种 加 速 的 随机 坐 标 梯 度 方 法 用 于 解  决 最 小 化 无 约束 的光 滑 函 数 , L u和 Xi a o l 3  给 出 了基 于 Ne s t e r o v方 法 的 证 明分 析 。  
2 . 3 . 1   随 机 坐 标 下 降 方 法 

随机 坐 标 下 降方 法  是 在某 个 概 率 分 布 下 选 择 坐 标 系 进 行 迭 代 的 过 程 , 首先将 N 维空间分成 7 " / 个 

子空 间, u  ∈ R   为矩阵的列置换 , 任何一个 N 维空间 的 向量  可 以唯一 的表示 为  一 >   U  
z“ ’ 一u   、 X∈R  , 当 N  一1时 , 即为 单 位 e向量 。La s s o问 题 可 以 简 单 的 表示 为 
1 T I i n { P(  )一 厂(  ) +A g(  )}  
∈ 

,  

( 1 7 )  

每 一 次 迭 代 过 程 只需 要 在 随机 选择 的 坐 标 系 下 进行 , 即 
P(  + U   t )一 _ 厂 ( X4 - U  t ) +2 g(  + U   t )   ( 1 8 )  
r  

其 中 f( x+ U   t )的 上 界 可 以通 过 / (  ) 函数 的光 滑 性 表 示 :f ( x +U  t ) ≤ 厂(  ) +(   厂(  ) , f ) +  J f   t  

4 2  

数 据 采 集 与 处理 J o u r n a l   o f   Da t a   Ac q u i s i t i o n   a n d   Pr o c e s s i n g   Vo 1 . 3 0, No . 1 ,2 0 1 5  

1 ;  L   为 每个 坐 标 系 下 的 L i p s c h i t z 常 数 。每 一 次 的 迭 代 过 程 需 要 上 一 次 的 迭 代 结 果 , 得 到 基 本 的 随  机 坐 标算 法 

j   T “   ( x k ) 一 a r g m i “ i (  _ 厂 ( X k ) ,   ) + 等l   l } I   2   + g   (   +   ) ,   ∈ R   }  
【 X … 一  + U   T“   (  )  

( 1 9 )  

在L a s s o问题 的 目标 函 数 上增 加 正则 化 项 I I   —X 。  

, 使 得 目标 函数 变 为 严 格 凸 函数 , 这 种 方 法 

应 用 在 基 于 光 滑 函 数 的 坐标 下 降方 法 中得 到 更 好 的 迭 代 结 果 。表 2 对 比 了不 同算 法 的 复 杂 度 的结 果 。  
表 2 不同算法的复杂度比较( 1 )  
T a b l e   2   Co mp l e x i t y   c o mp a r i s o n   o f   t h e   d i f f e r e n t   a i g r i t h m ( I )  

算 法  Yu n   a n d   Ts e n g   S h a l e v — S h wa r t z   。   P e t e r   R i c h t a r i k  

复 杂 度  O( n L(  _ 厂 )l   X  一  0   / £ )   X o   / e )   o  l ; / e )   O( n p   I   I X  一  。I I ; / e )   O ( n     l X  

S a h a r a   a n d   Te wa r i   ”  O( n L(  厂 )l  

2 . 3 . 2 邻 近 随机 对 偶 坐标 下 降 

邻 近 的 随机 对 偶 坐 标 下 降 方 法 ( P r o x i ma l   s t o c h a s t i c   d u a l   c o o r d i n a t e   a s c e n t , P r o x - S D C A)   是 S h a —  
l e v和 Z h a n g   对 随 机对 偶 问题 的扩 展 , 允 许 正 则 化 函数 g为 一 般 的 强 凸 函 数 , 这 样 可 以 用 来 解 决 非 凸  的 L1正 则 化 函数 。 在 目标 函 数 中增 加 正则 化 项 P(  )+ / 2   l   l X— z   , 其 中 z是 上 一 步 的 迭 代 结 果 ,  


O( 1 /  ̄ n ), 当时 1 / (  ) 》 n, 强 正则 化 项 能 够 使 得 邻 近 随 机 对 偶 坐 标 下 降 的 运算 时 间达 到 O( d n ) 。在 

每次迭代过程中 , 选择合适 的  能够达到 d   一  

的运算 时间。表 3 是不同算 法的运算 时间对 比表 。  

表 3 不 同 算 法 的 运 算 时 间 比 较 
Ta bl e   3   Co m pu t i ng   t i me   c o m pa r i s o n   o f   t he   di f f e r e nt   a l g o r i t hm 

对偶 坐标 下 降 方 法 的 目标 是 增 加 对 偶 目标 函 数 值 , 随 机 选 取 对 偶 变 量 的 Y的 一 个 坐 标 系 e   , 即Y  

对 应 着 原 始 问题 的第 i 个 样 本 。最 大 化 对偶 函数 , 得 到对 偶 变 量 的迭 代 步 长 

A y   = a r g   i n { 一  ( 一(  +A y   ) )  A g   (  ∑&  + i t   1 n   A y   ) )  
的下 界 问 题 

( 2 0 )  

为 了简 化 优化 问题 , 对 共 轭 函数 g做 光滑 处 理 , 即一阶泰勒展开 , 从 而 问 题 转 化 为 最 大 化 对 偶 函 数 

A y   — — a r g   i n { 一  ( 一(  +A y   ) ) 一  g   ( ∑&  ) 一( 2 t i )&   A y   )  
正则 化 项 g (  ) 一  I   l 1 . +  l   l X   1 I 。 ≈  l   l X   l  ( l  足 够 小 ) 。则 g (   ) 的共 轭 函数梯 度 为 

( 2 1 )  

在 L a s s o问 题 的 正则 化项 中 , L1正 则 化 项 不 是 强 凸正 则 化 项 , 增加 L 2正 则 化 项 , 从而定 义 L l — I   2  

g  (  ) 一s i g n ( y   ) [  1 1 一i t /  ̄ 3 +  
Pr o x — S DC A 加 速 方 法 采 用 Ne s t e r o v   S评 估 序 列 技 术 

( 2 2 )  

用 于 逼 近 随 机 的 邻 近 映 射 。在 每 一 次 

P r o x - S D C A的迭代过程中 , 改 进 目标 函数 P(  ) +  / 2     f X   z  ”  

, 其 中 正 则 化 项 围 绕 着 向量 z   ”=  

刘柳 等 : L a s s o问题 的 最新 算 法研 究 

4 3  

X   ”4 - 口 (   ”一  
方法 。  

), 从 而 得 到更 快 的收 敛 速 度 。对 于 选 取 坐 标 系 , 一 般 在 均 匀 分 布 的概 率 下 选 取 ,  

Z h a n g   阳 提 出 了在 对 偶 坐 标 系 下 根 据 任 意 的 分 布 选 取 对 偶 变 量 , 并 获 得 了有 效 的 并 行 和 分 布 式 变 量 
2 . 3 . 3   随 机 原 始 对 偶 坐 标 下 降 方 法 

随 机 原 始 对 偶 坐 标 下 降方 法 ( S t o c h a s t i c   p r i ma l — d u a l   c o o r d i n a t e , S P DC)   是 通 过交 替 优 化 对 偶 函 数 

和 原 始 函数 , 其 中 随机 选 择 对 偶 变量 中 的 一 维 空 间 , 由 于对 偶 变 量 对 应 着 原 始 目标 函数 中 的样 本 数 。在 
给 出随 机 原 始 对 偶 问题 的算 法 前 , 先 定 义原 始 问题 的 凸一 凹 鞍 点 问 题 

mi n   ma x { f ( x , J , ) 一2  (  ( n   ,   ) 一  (  ) ) +A g(   )}  
z∈   y ER   、  

关 于 变 量 Y通 过 最 大 化 目标 函数 f( x,  ) 得到 , 需 要 消 耗 0( n d ) 的计 算 量 , 如 果  很 大 , 需 要 消 耗 更  多 的时间, 所 以通 过 随机 选 取 对 偶 变量 y的坐 标 来 减 少 计 算 量 。这 样 在 选 取 的 坐 标 系 下 最 大 化 目标 函 

数, 然 后 交 替 优 化 原 始 目标 函数 。不 同 于一 般 的原 始 对 偶 问题 , 根 据 Ne s t e r o v   S 的加速技 巧 , 在 原 始 和  对 偶 函数 中增 加 了两 个 正则 化 项 , 从 而 得 到更 快 的 收 敛 速度 , C h e n   介 绍 了随 机 原 始 对 偶 方 法 , 在 原 始  和 对 偶 目标 函数 中增 加 一 阶变 量 并 且 融人 多 阶段 的 Ne s t e r o v 的加速方 法 , 同时 不 需 要 采 用 光 滑 技 术 也  能 达 到 Ne s t e r o v 光 滑 后 的 收敛 速 度 。同 时 , Z h a n g   提 出 Mi n i — b a t c h的方 法 , 自动 选 取 多 个 对 偶 坐标 变 
量, 在 并 行 运 算 中更 新 “ ¨ , 仅需 o(  ) 的迭 代 时 间 , 当然处理多个 对偶坐标 , 它 的 收 敛 率 比一 般 的 S P —   DC方 法 要 快 很 多 , 表 4给 出 了 不 同算 法 的时 间 复 杂 度 。  
表 4 不 同算 法 的 复 杂 度 比 较 ( 2 )  
Ta b l e   4   Co mp l e x i t y   c o mp a r i s o n   o f   t h e   d i f f e r e n t   a l g o r i t h m ( Ⅱ )  

算 法 
Ne s t e r ov [  ]   Ts e n g[  ]  

复 杂 度 
O(( 1+ )l o g( 1 / e ))  

0( (  +  )l o g ( 1 / e ))  
O( (  +Ⅳ)l o g( 1 / e ))  

Sha l e v - Shwa r t z [ 3 2 ]   Zh a ng   a n d   Li nc 。   ]  

O( ( 1 +  

)l o g ( 1 / E ))  

3   结 束 语 
近年来 , 随 着 数 据 量 的增 加 , 对解决 L a s s o问 题 提 出 了更 大 的挑 战 。在 解 决 大 规 模 数 据 中 , 必 须 要  考虑计算时间和储存能力 , 当硬 件 条 件 还 不 能 完 全 满 足 大 数 据 背 景 下 带 来 的需 求 , 尤 其 是 面 对 高 维 数 
据, 以往 的 方 法 很 难 再 满 足 人 们 对 数 据 的分 析 , 研 究 最 新 的算 法 就 成 为 最 新 的 热 点 。一 阶 方 法 、 随机 方 

法 和 并 行 和 分 布 计 算 在 解 决 大 规 模 数 据 中起 中重 要 的 作 用 , 首先 一 阶方法计算起 来简单 , 消耗时 间短 ,   符合人们对时间效率的要求 ; 再次 , 随 机 方 法 主要 从 数 据 的 特 点 来 考 虑 , 大 规 模 数 据 并 不 代 表 所 有 的 数  据都会对算法产生影响 , 如 果 对 所 有 的数 据 进 行 处 理 , 那 么 必 将 消 耗 更 多 的 时 间 和储 存 空 间 , 随 机 算 法  正 好 弥 补 了这 些 缺 点 ; 并 行 和 分 布 计 算 同样 是 为 了减 少 时 间 消耗 , 加 速运 算 , 增加效率 。   本文从 3 个典型的算法分析 了 L a s s o 问 题 的最 新 算 法 : 梯度下降方法 、 交 替 方 向乘 子 法 和 坐 标 下 降  方 法 。解 决 大 规 模 数 据 往 往 采 用 简 单 的方 法 更 能 提 高 效 率 。梯 度 下 降 是 做 简 单 的 方 法 , 它 结 合 一 阶 方  法和 N e s t e r o v的加 速 和光 滑技 术 , 使 最 终 的 收敛 速度 达 到 0 ( 1 / k   ) 。AD MM 和 坐 标 下 降 方 法 也 是 在 梯  度下降方法的基础上进行改进 , 使 得 它 们 能 够 更 适 合 大 规 模 的 数 据 。同 时 A D MM 和 坐 标 下 降 方 法 采  用随机方法进行迭代 , 因为 在 大 规 模 数 据 中能 够 减 少 时 间 消 耗 , 实验结果 也证实 了在大规模 数据 中, 基  于 随 机 算 法 能 够 得 到 更 好 的结 果 。坐 标 下 降 方 法 利 用 其 坐 标 系 的 特 点 结 合 一 阶方 法 、 随 机 方 法 和 并 行  和 分 布计 算 。坐 标 下 降 方 法 之 所 以是 最 近 研 究 的热 点 , 主 要 是 利 用 了其 坐 标 系 的特 点 , 另 一 个 原 因是 数  据 样 本 的增 加 和 数 据 维 度 越 来 越 高 , 为 了提 高 效 率 , 坐标 下 降 方 法 是 可 行 的 方 法 , 在 原 始 目标 函 数 中采 

4 4  

数 据 采 集 与 处理 J o u r n a l   o f   Da t a   Ac q u i s i t i o n   a n d   Pr o c e s s i n g   Vo 1 . 3 0, No . 1 ,2 0 1 5  

用 坐 标 下 降 方 法 是 为 了 避 免 高维 度 , 而 在 对 偶 函数 下 的 坐标 下 降 为 了 解 决 大 数 据 样 本 问题 。 基 于 随 机  的坐 标 下 降 方 法 在 未 来 的研 究 中仍 然 起 着 非 常 重 要 的 作 用 , 同 时 在 某 些 概 率分 布下 , 对 坐 标 系 的 随机 选 
择 将 会 是 下 一 个 阶 段研 究 的热 点 问题 。   参考文献 :  
[ 1 ]   Ti b s h i r a n i   R.Re g r e s s i o n   s h r i n k a g e   a n d   s e l e c t i o n   v i a   t h e   l a s s o [ J ] .J o u r n a l   o f   t h e   R o y a l   S t a t i s t i c a l   S o c i e t y .S e r i e s   B( Me t h o d —  
o l o g i c a 1 ), 1 9 9 6, 1 5 ( 1 ) : 2 6 7 — 2 8 8 .  

E 2 ]  B i c k e l   P   J ,L i   B ,Ts y b a k o v   A   B,e t   a 1 .Re g u l a r i z a t i o n   i n   s t a t i s t i c s [ J ] .S o c i e d a d   d e   E s t a d i s t i c a   e   I n v e s t i g a c i o n   Op e r a t i v a ,  
2 0 06 ,1 5 ( 2 ): 2 7 1 - 3 4 4 .  

[ 3 ]   F a d i l i   M  J , S t a r c k   J   I   Mo n o t o n e   o p e r a t o r   s p l i t t i n g   f o r   o p t i mi z a t i o n   p r o b l e ms   i n   s p a r s e   r e c o v e r y [ C]   I ma g e   P r o c e s s i n g   ( I CI P ) ,2 0 0 9   1 6 t h   I E EE   I n t e r n a t i o n a l   C o n f e r e n c e   o n .Ca i r o ,E g y p t ;s . n . ] ,2 0 0 9 :1 4 6 1 - 1 4 6 4 .   [ 4 ]   I   i u   J , Yu a n   I   ,Ye   J .D i c t i o n a r y   L a s s o :G u a r a n t e e d   s p a r s e   r e c o v e r y   u n d e r   l i n e a r   t r a n s f o r ma t i o n [ C ] ∥ P r o c e e d i n g s   o f   Ma —  

c h i n e   L e a r n i n g ,2 0 1 2   3 0 t h   I E E E   i n t e r n a t i o n a 1   C o n f e r e n c e .At l a n t a ,US A: E s . n . ] , 2 0 1 2 :1 - 2 8 .  
E s 3  Z h o u   T,T a o   D.Mu l t i — t a s k   c o p u l a   b y   s p a r s e   g r a p h   r e g r e s s i o n [ C ]   P r o c e e d i n g s   o f   t h e   2 0 t h   AC M  S I GKD D   I n t e r n a t i o n a l   C o n f e r e n c e   o n   Kn o wl e d g e   D i s c o v e r y   a n d   D a t a   Mi n i n g .Ne w  Yo r k,US A: E s . n . ] ,2 0 1 4 : 7 7 1 - 7 8 0 .   [ 6 3   Yu a n   x .Al t e r n a t i n g   d i r e c t i o n   me t h o d s   f o r   s p a r s e   c o v a r i a n e e   s e l e c t i o n [ J ] .J o u r n a l   o f   S c i e n t i f i c   C o mp u t i n g , 2 0 1 2 ,5 1 ( 2 ) :  
261 — 273  

[ 7 ] S u n   Y, L i u   Q,T a n g   J ,e t   a 1 .L e a r n i n g   d i s c r i mi n a t i v e   d i c t i o n a r y   f o r   g r o u p   s p a r s e   r e p r e s e n t a t i o n [ J ] .I E EE   T r a n s a c t i o n   o n  
I ma ge   Pr o c e s s i n g,2 0 1 4,2 3 ( 9 ): 3 81 6 - 3 8 2 6  

[ 8 ]   Ha s t i e   T, Ti b s h i r a n i   R, F r i e d ma n   J , e t   a 1 .Th e   e l e me n t s   o f   s t a t i s t i c a l   l e a r n i n g: Da t a   mi n i n g ,i n f e r e n c e   a n d   p r e d i c t i o n [ J ] .  
Th e   Ma t h e ma t i c a l   I n t e l l i g e nc e r ,2 0 0 5,2 7( 2) : 8 3 — 8 5 .  

[ 9 ]   Ge n g   B ,L i   Y,Ta o   D,e t   a 1 .P a r a l l e l   l a s s o   f o r   l a r g e — s c a l e   v i d e o   c o n c e p t   d e t e c t i o n [ J ] .Mu l t i me d i a , I E E E   Tr a n s a c t i o n s   o n ,  
2 O 1 2, 1 4 ( 1 ): 5 5 - 6 5 .  

[ 1 O ]  Z h o u   T, Ta o   D.S h i f t e d   s u b s p a e e s   t r a c k i n g   o n   s p a r s e   o u t l i e r   f o r   mo t i o n   s e g me n t a t i o n [ C ]  P r o c e e d i n g s   o f   t h e   T we n t y — Th i r d  

I n t e r n a t i o n a l   J o i n t   C o n f e r e n c e   o n   Ar t i f i c i a l   I n t e l l i g e n c e .B e i j i n g ,C h i n a : [ s . n . ] ,2 0 1 3 :1 9 4 6 — 1 9 5 2 .   o n s o   M  V ,Bi o u c a s - Di a s   J   M ,Fi g u e i r e d o   M  A. Fa s t   i ma ge   r e c o v e r y   u s i n g   v a r i a b l e   s p l i t t i n g   a n d   c o n s t r a i n e d   o p t i mi z a t i o n   [ 1 i 3  Af
E J ] .I ma g e   P r o c e s s i n g ,I E E E   Tr a n s a c t i o n s   o n , 2 0 1 0 ,1 9 ( 9 ) : 2 3 4 5 — 2 3 5 6 .   [ 1 2 ]  E l a d   M ,Ma t a l o n   B ,Z i b u l e v s k y   M.I ma g e   d e n o i s i n g   wi t h   s h r i n k a g e   a n d   r e d u n d a n t   r e p r e s e n t a t i 0 n s [ c ] ∥ C o mp u t e r   V i s i o n   a n d   P a t t e r n   Re c o g n i t i o n ,2 0 0 6   I E E E   C o mp u t e r   S o c i e t y   C o n f e r e n c e ,Ne w   Yo r k ,US A:s . n . ] ,2 0 0 6 , 2 :1 9 2 4 — 1 9 3 1 .   [ 1 3 ]  F i g u e i r e d o   M  A,N o wa k   R   D .A n   e m   a l g o r i t h m   f o r   wa v e l e t — b a s e d   i ma g e   r e s t o r a t i o n [ J ] .I ma g e   P r o c e s s i n g , I E E E   Tr a n s a c —  
t i o n s   on.2 0 0 3,】 2 ( 8) . 9 0 6 - 9 1 6 .  

g 1 4 3  Yu   J ,Ru i   Y,T a o   D  Cl i c k   p r e d i c t i o n   f o r   w e b   i ma g e   r e r a n k i n g   u s i n g   mu l t i mo d a l   s p a r s e   c o d i n g [ J 3 .I E E E   Tr a n s a e t i o n s   0 n  
I ma g e   Pr o c e s s i ng,2 0 1 4,2 3( 5 ):2 0 1 9 - 2 0 3 2.  

[ 1   5 ]  He   I   ,Ta o   D, I A   x,e t   a 1 .S p a r s e   r e p r e s e n t a t i o n   f o r   b l i n d   i ma g e   q u a l i t y   a s s e s s me n t [ C ] ∥C o mp u t e r   Vi s i o n   a n d   P a t t e r n   Re c —  
o g n i t i o n( C VP R ) ,2 0 1 2   I E E E   C o n f e r e n c e .Rh o d e ,I s l a n d :s . n . ] ,2 0 1 2 ,1 1 4 6 — 1 1 5 3 .  
ou c a s — Di a s   J   M ,Fi g u e i r e d o   M  A.Al t e r n a t i n g   d i r e c t i o n   a l go r i t h ms   f o r   c o n s t r a i n e d   s p a r s e   r e g r e s s i o n:Ap p l i c a t i o n   t o   h y p e r —   [ 1 6 ]  Bi

s p e c t r a l   u n mi x i n g [ C ] ∥ Hy p e r s p e c t r a l   I ma g e   a n d   S i g n a l   P r o c e s s i n g :E v o l u t i o n   i n   R e mo t e   S e n s i n g( W HI S P ER S ) ,2 0 1 0   2 n d  
Wo r k s h o p .Re y k j a v i k ,I c e l a n d : [ s . n . ] ,2 0 i 0 :l 一 4 .   [ 1 7 ]  L i n e a r   A.F o r e wo r d   t o   t h e   s p e c i a l   i s s u e   o n   s p e c t r a l   u n mi x i n g   o f   r e mo t e l y   s e n s e d   d a t a [ J ] .I E E E   Tr a n s a c t i o n s   o n   G e o s c i e n c e  
a n d   Re mo t e   S e n s i n g, 2 0 1 1,4 9( 1 1 ): 4 1 0 3 .  

[ 1 8 ]  R i c h a r d s   J   A.Re mo t e   s e n s i n g   d i g i t a l   i ma g e   a n a l y s i s [ M] .Ne w   Y o r k: S p r i n g e r ,1 9 9 9 .   [ 1 9 ]  E f r o n   B,Ha s t i e   T,J o h n s t o n e   I 。e t   a 1 .L e a s t   a n g l e   r e g r e s s i o n [ J ] .T h e   An n a l s   o f   S t a t i s t i c s , 2 0 0 4 ,3 2 ( 2 ) : 4 0 7 — 4 9 9 .  

[ 2 0 ]  Ne s t e r o v   Y,N e s t e r o v   I   E .I n t r o d u c t o r y   l e c t u r e s   o n   c o n v e x   o p t i mi z a t i o n : A  b a s i c   c o u r s e  ̄ M] .US A: S p r i n g e r ,2 0 0 4 .  
[ 2 1 ]  N e s t e r o v   Y.S mo o t h   mi n i mi z a t i o n   o f   n o n — s mo o t h   f u n c t i o n s [ J  ̄ .Ma t h e ma t i c a l   P r o g r a mmi n g ,2 0 0 5 ,1 0 3 ( 1 ) : 1 2 7 — 1 5 2 .  
o y d   S,P a r i kh   N ,Ch u   E,e t   a 1 .Di s t r i b u t e d   o p t i mi z a t i o n   a nd   s t a t i s t i c a ¨e a r n i n g   v i a   t h e   a l t e r n a t i n g   d i r e c t i o n   me t h o d   o f   mul —   [ 2 2 ]  B

t i p l i e r s [ J ] .F o u n d a t i o n s   a n d   Tr e n d s   R   i n   Ma c h i n e   L e a r n i n g ,2 0 1 1 ,3 ( 1 ) : 1 - 1 2 2 .   E 2 3 ]  B e c k e r   S .R, C a n d 6 s   E   J ,Gr a n t   M  C.Te mp l a t e s   f o r   c o n v e x   c o n e   p r o b l e ms   wi t h   a p p l i c a t i o n s   t o   s p a r s e   s i g n a l   r e c o v e r y [ J ] .  
Ma t h e ma t i c a l   Pr o g r a mm i ng   Co mp u t a t i o n,2 0 1 1,3 ( 3 ): 1 6 5 — 21 8 .  

[ 2 4 ]  B e c k   A,T e b o u l l e   M.A   f a s t   i t e r a t i v e   s h r i n k a g e — t h r e s h o l d i n g   a l g o r i t h m   f o r   l i n e a r   i n v e r s e   p r o b l e ms [ J ] .S I AM  J o u r n a l   o n   I m—  
a g i n g   S c i e n c e s ,2 0 0 9,2 ( 1 ): 1 8 3 — 2 0 2 .  

[ 2 5 ]  G o l d s t e i n   T,OD o n o g h u e   B ,S e t z e r   S .F a s t   a l t e r n a t i n g   d i r e c t i o n   o p t i mi z a t i o n   me t h o d s [ J ] .S I AM  J o u r n a l   I ma g i n g   S c i e n c e s ,  

刘柳 等 : La s s o问题 的 最 新 算 法研 究 
Z Ol 4,7( 3) : l 5 8 8 一 l 6 Z 3 .  

4 5  

[ 2 6 ]  S u z u k i   T.D u a l   a v e r a g i n g   a n d   p r o x i ma l   g r a d i e n t   d e s c e n t   f o r   o n l i n e   a l t e r n a t i n g   d i r e c t i o n   mu l t i p l i e r   me t h o d i C ]f ,P r o c e e d i n g s  
o f   t h e   3 o t h   I n t e r n a t i o n a l   C o n f e r e n c e   o n   Ma c h i n e   L e a r n i n g( I CML - 1 3 ) .At l a n t a ,US A: [ s . n . ] , 2 0 1 3 :3 9 2 — 4 0 0 .   [ 2 7 ]  S u z u k i   T .S t o c h a s t i c   d u a l   c o o r d i n a t e   a s c e n t   w i t h   a l t e r n a t i n g   d i r e c t i o n   mu l t i p l i e r   me t h 0 d [ E B / 0L ] .h t t p : ∥a r x i v . o r g / , 2 0 1 4 .  

[ 2 8 3  Ou y a n g   H ,He   N, Tr a n   L, e t   a 1 .S t o c h a s t i c   a l t e r n a t i n g   d i r e c t i o n   me t h o d   o f   mu l t i p l i e r s [ C  ̄ ∥P r o c e e d i n g s   o f   t h e   3 0 t h   I n t e r —  
n a t i o n a l   Co n f e r e n c e   o n   Ma c hi ne   Le a r n i n g,At l a n t a ,USA : s . n .   2 O1 3:8 O 一 8 8 .  

[ 2 9 ]   Ne s t e r o v   Y.E f f i c i e n c y   o f   c o o r d i n a t e   d e s c e n t   me t h o d s   o n   h u g e — s c a l e   o p t i mi z a t i o n   p r o b l e ms [ J ] .S I AM  J o u r n a l   o n   Op t i mi z a —  
t i o n,2 0 1 2,2 2 ( 2 ): 3 41 - 3 6 2 .  

[ 3 0 ]   1   i u   J , Wr i g h t   S   J .As y n c h r o n o u s   s t o c h a s t i c   c o o r d i n a t e   d e s c e n t : P a r a l l e l i s m  a n d   c o n v e r g e n c e   p r o p e r t i e s[ E B / OL ] .h t t p : ∥  
a r x i v . o r g / ,2 0 1 4 .  
Ri c h t d r i k   P,Ta k d  c   M.I t e r a t i o n   c o mp l e x i t y   o f   r a n d o mi z e d   b l o c k — c o o r d i n a t e   d e s c e n t   me t ho d s   f o r   mi n i mi z i n g   a   c o mp o s i t e   [ 3 1 ]  

f u n c t i o n [ J ] .Ma t h e ma t i c a l   P r o g r a mmi n g , 2 0 1 4 。1 4 4 ( 1 - 2 ) : 1 - 3 8 .   [ 3 2 ]  S h a I e v   S h wa r t z   S ,Z h a n g   T.S t o c h a s t i c   d u a l   c o o r d i n a t e   a s c e n t   me t h o d s   f o r   r e g u l a r i z e d   l o s s [ J ] .Th e   J o u r n a l   o f   Ma c h i n e  
Le a r n i n g   Re s e a r c h,2 01 3 ,1 4 ( 1 ): 5 6 7 — 5 9 9 .  

[ 3 3 ]   S h a l e v — S h w a r t z   S, Z h a n g   T .Ac c e l e r a t e d   p r o x i ma l   s t o c h a s t i c   d u a l   c o o r d i n a t e   a s c e n t   f o r   r e g u l a r i z e d   l o s s   mi n i mi z a t i o n [ E B /  

OL ] .h t t p t ? ? l i n k . s p r i n g e r . c o m/ j o u r n a l / 1 0 1 0 7 ,2 0 1 5 .  
[ 3 4 ]   Z h a n g   Y,Xi a o   L .S t o c h a s t i c   p r i ma l — d u a l   c o o r d i n a t e   me t h o d   f o r   r e g u l a r i z e d   e mp i r i c a l   r i s k   mi n i mi z a t i o n[ E B / OL ] .h t t p : ∥ 
a r x i v . o r g /,2 0 1 4 .  

[ 3 5 ]   Ch e n   Y,L a n   G,Ou y a n g   Y.Op t i ma l   p r i ma l   d u a l   me t h o d s   f o r   a   c l a s s   o f   s a d d l e   p o i n t   p r o b l e ms [ J ] .S I AM  J o u r n a l   o n   Op t i mi —  
z a t i o n,2 0 1 4,2 4( 4 ): 1   7 7 9 - 1 8 1 4 .  

[ 3 6 3   De v o l d e r   O, Gl i n e u r   F, Ne s t e r o v   Y .F i r s t — o r d e r   me t h o d s   o f   s mo o t h   c o n v e x   o p t i mi z a t i o n   wi t h   i n e x a c t   o r a c l e [ J ] .Ma t h e ma t i —  
c a l   Pr o g r a mm i n g,2 01 4,1 4 6( 1 — 2 ): 3 7 — 7 5 .  
Av r o n   H [ 3 7 ]   ,Dr u i n s k y   A ,Gu p t a   A. Re v i s i t i n g   a s y n c hr o no u s   l i n e a r   s o l v e r s :Pr o v a bl e   c o nv e r g e nc e   r a t e   t h r o u g h   r a n d o mi z a t i o n  

[ E B / OL ] .h t t p  ? } a r x i v . o r g /  2 0 1 4 .   E 3 8 ]   Re e h t   B, Re   C, Wr i g h t   S, e t   a 1 .Ho g wi l d : A   l o c k — f r e e   a p p r o a c h   t o   p a r a l l e l i z i n g   s t o c h a s t i c   g r a d i e n t   d e s c e n t [ C ] ∥ Ad v a n c e s   i n   Ne u r a l   I n f o r ma t i o n   P r o c e s s i n g   S y s t e ms .Gr a n a d a ,S p a i n : I s . 1 3 _ . ] ,2 0 1 1 :6 9 3 — 7 0 1 .  
[ 3 9 ]   Ri c h t d r i k   P, Ta k d  c   M .P a r a l l e l   c o o r d i n a t e   d e s c e n t   me t h o d s   f o r   b i g   d a t a   o p t i mi z a t i o n[ E B / OL ] .h t t p : ∥a r x i v . o r g / ,2 0 1 4 .  

[ 4 o ]   L i u   J ,Wr i g h t   S   J , R6   C, e t   a 1 .An   a s y n c h r o n o u s   p a r a l l e l   s t o c h a s t i c   c o o r d i n a t e   d e s c e n t   a l g o r i t h m[ E B / OL ] .h t t p : ∥a r x i v .  
o r g / ,2 0 1 4 .  

[ 4 1 3   L i u   J ,W r i g h t   S   J ,S r i d h a r   S .A n   a s y n c h r o n o u s   p a r a l l e l   r a n d o mi z e d   k a e z ma r z   a l g o r i t h m [ E B / OL ] .h t t p : ∥a r x i v . o r g / ,  
2 O 1 4 .  

[ 4 2 3   S t r o h me r   T, Ve r s h y n i n   R.A   r a n d o mi z e d   k a c z ma r z   a l g o r i t h m   w i t h   e x p o n e n t i a l   c o n v e r g e n c e [ J ] .J o u r n a l   o f   F o u r i e r   An a l y s i s  
a n d   Ap p l i c a t i o n s ,2 0 0 9,1 5( 2 ): 2 6 2 — 2 7 8 .  

[ 4 3] Gr a n   M ,B o y d   S ,Ye   Y.C v x :Ma t l a b   s o f t w a r e   f o r   d i s c i p l i n e d   c o n v e x   p r o g r a mmi n g [ E B / OL ] .h t t p : ∥c v x r . c o m/ c v x / ,  
2 0 0 8 .  

[ 4 4 ]C a n d e s   E, Ro mb e r g   J .1 1 一 ma g i c :Re c o v e r y   o f   s p a r s e   s i g n a l s   v i a   c o n v e x   p r o g r a mmi n g .[ E B / O L] .h t t p : ∥ e —d u / l l ma g i c /  
d o wn l o a d s / l l ma g i c , 2 0 0 5 .  

[ 4 5 3   Go l d s t e i n   T,Os h e r   S .Th e   s p l i t   b r e g ma n   me t h o d   f o r   1 1 一 r e g u l a r i z e d   p r o b l e ms [ J ] .S I AM  J o u r n a l   o o   I ma g i n g   S c i e n c e s ,2 0 0 9 ,  
2 ( 2 ): 3 2 3 - 3 4 3 .  

[ 4 6 ] Ru d i n   I   I   Os h e r   S, F a t e mi   E .No n l i n e a r   t o t a l   v a r i a t i o n   b a s e d   n o i s e   r e mo v a l   a l g o r i t h ms [ J ] .P h y s i c a   D: No n l i n e a r   P h e n o me —  
n a,1 9 9 2,6 O( 1 ): 2 5 9 - 2 6 8.  

[ 4 7 ] Ki m  S   J ,Ko h   K, B o y d   S .S k y s t r e n d   f i l t e r i n g [ J ] .S i a m   Re v i e w, 2 0 0 9 ,5 1 ( 2 ) : 3 3 9 — 3 6 0 .  

[ 4 8 3   Z h u   x,Hu a n g   Z ,C u i   J ,e t   a 1 .Vi d e o — t o — s h o t   t a g   p r o p a g a t i o n   b y   g r a p h   s p a r s e   g r o u p   l a s s o [ J  ̄ .Mu l t i me d i a ,I E E E   T r a n s a c —  
t i o n s   o n,2 O 1 3,1 5( 3 ): 6 3 3 - 6 4 6 .  

[ 4 9 ] Yu a n   M, Li n   Y.Mo d e l   s e l e c t i o n   a n d   e s t i ma t i o n   i n   r e g r e s s i o n   wi t h   g r o u p e d   v a r i a b l e s [ J ] .J o u r n a l   o f   t h e   R o y a l   S t a t i s t i c a l   S o —  
c i e t y:Se r i e s   B( St a t i s t i c a l   Me t h o d o l o g y) ,2 0 0 6,6 8( 1 ): 4 9 — 6 7 .  

[ 5 O ]Oh l s s o n   H, I  ̄ u n g ,L ,B o y d   S .S e g me n t a t i o n   o f   a r x - mo d e l s   u s i n g   s u m— o f — n o r ms   r e g u 1 a r i z a t i o n [ J ] .Au t o ma t i c a ,2 0 1 0 ,4 6  
( 6 ): 1 1 0 7 — 1 1 1 1 .  

[ 5 1 ]C e v h e r   V, B e c k e r   S , S c h mi d t   M.C o n v e x   o p t i mi z a t i o n   f o r   b i g   d a t a : S c a l a b l e ,r a n d o mi z e d , a n d   p a r a l l e l   a l g o r i t h ms   f o r   b i g   d a —   t a   a n a l y t i c s [ J ] .S i g n a l   P r o c e s s i n g   Ma g a z i n e ,I E E E,2 0 1 4 , 3 1 ( 5 ) : 3 2 — 4 3 .   E 5 2 ]P a r i k h   N, B o y d   S .P r o x i ma l   a l g o r i t h ms [ J ] .F o u n d a t i o n s   a n d   Tr e n d s   i n   Op t i mi z a t i o n ,2 0 1 3 ,1 ( 3 ) : 1 2 3 — 2 3 1 .  

4 6  

数 据 采 集 与 处理 J o u r n a l   o f   Da t a   Ac q u i s i t i o n   a n d   Pr o c e s s i n g   Vo 1 . 3 0 , No . 1 ,2 0 1 5  

E 6 3 3   B l a c k f o r d   L   S , Ch o i   J , C l e a r y   A,e t   a 1 .S c a L AP AC K   u s e r s  g u i d e [ E B / oL ] .h t t p : ∥ WWW . n e t l i b . 0 r g / s c a l a p a c k / s c a l a p a c k  
u g . p s .2 0 0 6 .  

E 5 4 3   D e mme l M  J   W ,He a t h   M  T, Va n   De r   Vo r s t   H   A.P a r a l l e l   n u me r i c a l   l i n e a r   a l g e b r a [ J ] .Ac t a   Nu me r i c a ,1 9 9 3 ,2 : 1 1 1 — 1 9 7 .  

[ 5 5 3   Ga l l i v a n   K  A, P l e mmo n s   R   J , S a me h   A.P a r a l l e l   a l g o r i t h ms   f o r   d e n s e   l i n e a r   a l g e b r a   c o mp u t a t i o n s [ J ] .S I AM  r e v i e w,1 9 9 0 ,  
3 2 ( 1 ): 5 4 - 1 3 5 .  

E 5 7 ]S a h a   A ,T e w a r i   A.On   t h e   f i n i t e   t i me   c o n v e r g e n c e   o f   c y c l i c   c o o r d i n a t e   d e s c e n t   me t h o d s [ J ] .S i a m   J o u r n a l   o f   Op t i mi z a t i o n ,  
2 0 l 3,2 3( 1) : 5 7 6 — 6 01 .  

[ 5 6 ]   F r i e d ma n   J ,Ha s t i e   T,Ho f l i n g   H, e t   a 1 .P a t h wi s e   c o o r d i n a t e   o p t i mi z a t i o n [ J ] .Th e   A n n a l s   o f   A p p l i e d   S t a t i s t i c s ,2 0 0 7 ,1  
( 2 ): 3 0 2 - 3 3 2 .  

[ 5 8 3   L e v e n t h a l   D,L e wi s   A   S .R a n d o mi z e d   me t h o d s   f o r   l i n e a r   c o n s t r a i n t s :C o n v e r g e n c e   r a t e s   a n d   c 0 n d i t i o n i n g [ J ] .Ma t h e ma t i c s  
o f   Op e r a t i o n s   Re s e a r c h,2 01 0,3 5 ( 3 ): 6 4 1 — 6 5 4 .  

[ 5 9 ]S h a l e v ~ S h wa r t z   S ,T e wa r i   A.S t o c h a s t i c   me t h o d s   f o r   1 卜r e g u l a r i z e d   l o s s   mi n i mi z a t i o n [ J ] .Th e   J o u r n a l   o f   Ma c h i n e   L e a r n i n g  
Re s e a r c h,2 0 1 l,1 2: 1 8 6 5 — 1 8 9 2 .  

[ 6 0 ] Qu   Z, Ri c h t d r i k   P, Z h a n g   T.R a n d o mi z e d   d u a l   c o o r d i n a t e   a s c e n t   wi t h   a r b i t r a r y   s a mp l i n g[ E B / OL ] .h t t p : ∥a r x i v . o r g / ,  
2 O1 4 .  

E 6 1 ] Ne s t e r o v   Y.G r a d i e n t   me t h o d s   f o r   mi n i mi z i n g   c o mp o s i t e   f u n c t i o n s [ J ] .Ma t h e ma t i c a l   P r o g r a mmi n g , 2 0 1 3 ,1 4 0 ( 1 ) : 1 2 5 — 1 6 1 .   E 6 2 ] Ts e n g   P.On   a c c e l e r a t e d   p r o x i ma l   g r a d i e n t   me t h o d s   f o r   c o n v e x - c o n c a v e   o p t i mi z a t i o n   E E B / OL ] .h t t p   t} } WWW. mi t . e d u /~ 
d i mi t r i b / P T s e n g / p a p e r s . b t ml ,2 0 0 8 .  

[ 6 3 ] Ts e n g   P,Yu n   S .B l o c k — c o o r d i n a t e   g r a d i e n t   d e s c e n t   me t h o d   f o r   l i n e a r l y   c o n s t r a i n e d   n o n s mo o t h   s e p a r a b l e   o p t i mi z a t i o n [ J ] .  
J o u r n a l   o f   Op t i mi z a t i o n   Th e o r y   a nd   Ap p l i c a t i o n s,2 0 0 9,1 4 0( 3) : 51 3 — 5 3 5 .  

作 者 简介 ; 刘柳 ( 1 9 8 7 一 ) , 女, 博士研究生 , 研究方向 : 机 器 学 习 ,E — ma i l : L i u . L i u 一 2 @s t u d e n t . u t s . e d u . a u ; 陶大程( 1 9 7 8 一 ) , 男, 教 授  研究方 向: 模式识别, 机器 学 习 , 计算机视觉 , E — ma i l : d a c h e n g . t a o @g ma i l . c o n。 r  


推荐相关:

Lasso问题的最新算法研究_论文.pdf

Lasso问题的最新算法研究_军事/政治_人文社科_专业资料。ISSN 1004


基于LASSO的多变量过程调整算法研究_论文.pdf

基于LASSO的多变量过程调整算法研究 - 第 1 9 卷年9 第月 3 期Jo


从理论到应用浅谈lasso模型.doc

本科生学年论文题目:从理论到应用浅谈 lasso ...问题,能够在参数估计的同时实现变量的选择的回归方法...揭示更多的传统技术, 给向前逐步选择方法带来了的...


基于LASSO算法的恒星α元素丰度估计方法研究_论文.pdf

基于LASSO算法的恒星α元素丰度估计方法研究 - 第3 7卷,第1月 1期 2


针对Lasso问题的多维权重求解算法_论文.pdf

针对Lasso问题的多维权重求解算法 - Jounarl of Computer Applications ISSN 1 ...... 针对Lasso问题的多维权重求解算法_电子/电路_工程科技_专业资料。Jounarl of ...


结合LASSO算法与logistic回归模型的P2P信贷审批结果研....pdf

结合LASSO算法与logistic回归模型的P2P信贷审批结果研究_教育学/心理学_人文社科_专业资料。LASS O算法与 Io[1isti c回 归模型的 P2 P信贷审批结果研究 倪新洁 ...


基于LASSO方法的结构突变理论研究综述_论文.pdf

基于LASSO方法的结构突变理论研究综述_哲学/历史_人文社科_专业资料。第3 9卷第...是 近几 年结 构突变问题的最新 研究方 法. 为了在 国内推行 该方法 , ...


成分数据中基于MCLasso的修正EM算法_论文.pdf

Lasso 算法进行改进. 对新的方法进行实证分析, 并与基于线性回归的修正 EM 算法、 基于均值插 补法和 Bootstrap 的修正 EM 算法进行比较研究, 验证了该方法的...


Lasso及其相关方法在多元线性回归模型中的应用.pdf

北京交通大学 硕士学位论文 Lasso及其相关方法在多元...新的求解Lasso估计的算法一一随机模拟算法,该算法可以...问题中,但关于多元线性回归模型中变量选择方法的研究...


lasso算法.doc

修正的 LARS 算法和 lasso 2011/04/25 郝智恒在小弟的上一篇文章中,简单的...lasso方法的综述 13页 1下载券 Lasso问题的最新算法研究... 暂无评价 12页...


lasso.txt

如果想了了解这方面更详细的信息,可加qq:381823441,他的硕士论文做的就是这...Lasso问题的最新算法研究... 暂无评价 12页 5.00 支持向量机与LASSO算法...


Lasso及其相关方法在广义线性模型模型选择中的应用_图文.pdf

Tibshirani,R.(1996)针 对这一问题提出了一种称之为Lasso的新的模型选择方法...本人声明,所呈交的学位论文是本人在导师指导下进行的研究工 作及取得的研究成果...


基于LASSO.SVM的软件缺陷预测模型研究_论文.pdf

基于LASSO.SVM的软件缺陷预测模型研究 - 第3 0卷第 9期 201 3年9月 计算机应用研究 Application Rese...


graphical lasso算法_图文.pdf

graphical lasso算法 - 对高斯逆协方差矩阵的极大似然估计。包括算法原理... 他在自己的论文里证明了这个问题是收敛的,...Lasso问题的最新算法研究... 暂无评价 12...


基于序lasso的时间序列分析方法_论文.pdf

shirani提出了一种的变量选择方法(leastabsoluteshrinkageandselectionoperator,lasso)[5]。 该方法用模型系数的 1 范数作为惩罚来压缩模型 系数,使绝对值较小的...


Group Lasso正则化问题的邻近梯度算法的线性收敛性_论文.pdf

Group Lasso正则化问题的邻近梯度算法的线性收敛性 - 第41卷 第 6


lasso.doc

我们再次提出一个新的方法LASSO,其最小残差平 ...我们的模拟研究显示 LASSO 在岭回归的子集选择中有...这张图暴露出一个很有趣的问题:LASSO 预测结果会...


Lasso算法介绍和R实例.pdf

Lasso算法介绍和R实例_数学_自然科学_专业资料。对于Lasso算法的介绍,有大量R代码示例 Abstract Key words: l1 -NORM CONSTRAINT; LASSO; VARIABLE SELECTION; ...


基于lasso方法的银行对中小企业贷款供给意愿研究_论文.pdf

/ /金融与经济 2017.03 ournal ofFinance and Economics 基于 lasso 方法的 ■ 龙泽海 ,杨毅, 赵月丽 本 文基 于l asso 方法研 究银行对 中小企 业贷款 ...


基于Lasso的稀疏微波成像分块成像原理与方法研究_论文.pdf

基于Lasso的稀疏微波成像分块成像原理与方法研究 - 第 2卷第 3期 201

网站首页 | 网站地图
All rights reserved Powered by 学霸学习网 www.tceic.com
copyright ©right 2010-2021。
文档资料库内容来自网络,如有侵犯请联系客服。zhit325@126.com