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