講演抄録/キーワード |
講演名 |
2016-11-16 15:00
近接平均を用いた加速近接勾配法の適応的リスタート ○中里佳央・福地一斗・佐久間 淳(筑波大) IBISML2016-55 |
抄録 |
(和) |
複数のスパース正則化項を含む目的関数を最適化する際にその近接写像を求めるためには非常に多くの計算量が必要であり,劣勾配法と同程度の計算時間になりうるcite{villa2013accelerated}.
複数のスパース正則化項にある条件が成り立つと仮定することで最適化する手法が提案されているcite{yu2013decomposing}cite{martins2011online}が,それらの条件を満たすスパース正則化項は一部に限られているため,条件を満たさないスパース正則化項の組み合わせは最適化することができない.
それぞれのスパース正則化項がリプシッツ定数を持ち,近接写像を求められるという条件のみで複数のスパース正則化項を含む目的関数を最適化できる近似手法が2つある.
1つはNesterovが提案したHuber損失関数を用いて微分不可能点の周りを二乗近似する手法である.
もう1つは近接写像の出力の平均を用いて近似するProximal Averageという手法である.
YuはProximal Averageを用いて,近似を行いFISTAcite{beck2009fast}を用いて最適化することで$epsilon$最適な解を得るために必要な反復数が$O(1/sqrt{epsilon})$であると主張しているcite{yu2013better}.
本研究では,正則化項のリプシッツ定数の二乗の平均が損失関数の勾配のリプシッツ定数より大きい時,$epsilon$最適仲居を得るために必要な反復回数が$O(1/epsilon)$となることを示し,ステップサイズを調整し,加速法において用いられるヒューリスティック手法であるリスタートアルゴリズムを適用することで収束が経験的に早くなる手法を提案した. |
(英) |
When using multiple regularizers, their proximal mapping is not easily available in closed form.
The method to calculate proximal mapping of multiple regularizers needs many calculating cost.
When the regularizers satisfy some certain conditioncite{yu2013decomposing}cite{martins2011online}, there are optimization methods to solve multiple sparse regularization problem.
But their condition is not always satisfied.
There are some approximation method for multiple regularizers: smoothingcite{nesterov2005smooth}, proximal averagecite{yu2013better}.
Yu showed that by using proximal average and FISTA, $O(1/sqrt{epsilon})$ iteration is needed for $epsilon$-optimal.
In this research, when the average of the square of Lipschitz constant of regularizers is larger than the Lipschitz constant of the gradient of the loss function, we show that the Algorithm proximal average accelerated proximal gradient(PA-APG) is as slow as $1/epsilon$.
And, we propose new algorithm which is faster than PA-APG. |
キーワード |
(和) |
凸最適化 / スパース正則化 / / / / / / |
(英) |
Convex Optimization / Composite Sparse Regularizers / / / / / / |
文献情報 |
信学技報, vol. 116, no. 300, IBISML2016-55, pp. 65-71, 2016年11月. |
資料番号 |
IBISML2016-55 |
発行日 |
2016-11-09 (IBISML) |
ISSN |
Print edition: ISSN 0913-5685 Online edition: ISSN 2432-6380 |
著作権に ついて |
技術研究報告に掲載された論文の著作権は電子情報通信学会に帰属します.(許諾番号:10GA0019/12GB0052/13GB0056/17GB0034/18GB0034) |
PDFダウンロード |
IBISML2016-55 |
研究会情報 |
研究会 |
IBISML |
開催期間 |
2016-11-16 - 2016-11-18 |
開催地(和) |
京都大学 |
開催地(英) |
Kyoto Univ. |
テーマ(和) |
情報論的学習理論ワークショップ(IBIS2016) |
テーマ(英) |
Information-Based Induction Science Workshop (IBIS2016) |
講演論文情報の詳細 |
申込み研究会 |
IBISML |
会議コード |
2016-11-IBISML |
本文の言語 |
日本語 |
タイトル(和) |
近接平均を用いた加速近接勾配法の適応的リスタート |
サブタイトル(和) |
|
タイトル(英) |
Proximal Average Accelerated Proximal Gradient Algorithm with Adaptive Restart |
サブタイトル(英) |
|
キーワード(1)(和/英) |
凸最適化 / Convex Optimization |
キーワード(2)(和/英) |
スパース正則化 / Composite Sparse Regularizers |
キーワード(3)(和/英) |
/ |
キーワード(4)(和/英) |
/ |
キーワード(5)(和/英) |
/ |
キーワード(6)(和/英) |
/ |
キーワード(7)(和/英) |
/ |
キーワード(8)(和/英) |
/ |
第1著者 氏名(和/英/ヨミ) |
中里 佳央 / Yoshihiro Nakazato / ナカザト ヨシヒロ |
第1著者 所属(和/英) |
筑波大学 (略称: 筑波大)
University of Tsukuba (略称: Univ. Tsukuba) |
第2著者 氏名(和/英/ヨミ) |
福地 一斗 / Kazuto Fukuchi / フクチ カズト |
第2著者 所属(和/英) |
筑波大学 (略称: 筑波大)
University of Tsukuba (略称: Univ. Tsukuba) |
第3著者 氏名(和/英/ヨミ) |
佐久間 淳 / Jun Sakuma / サクマ ジュン |
第3著者 所属(和/英) |
筑波大学 (略称: 筑波大)
University of Tsukuba (略称: Univ. Tsukuba) |
第4著者 氏名(和/英/ヨミ) |
/ / |
第4著者 所属(和/英) |
(略称: )
(略称: ) |
第5著者 氏名(和/英/ヨミ) |
/ / |
第5著者 所属(和/英) |
(略称: )
(略称: ) |
第6著者 氏名(和/英/ヨミ) |
/ / |
第6著者 所属(和/英) |
(略称: )
(略称: ) |
第7著者 氏名(和/英/ヨミ) |
/ / |
第7著者 所属(和/英) |
(略称: )
(略称: ) |
第8著者 氏名(和/英/ヨミ) |
/ / |
第8著者 所属(和/英) |
(略称: )
(略称: ) |
第9著者 氏名(和/英/ヨミ) |
/ / |
第9著者 所属(和/英) |
(略称: )
(略称: ) |
第10著者 氏名(和/英/ヨミ) |
/ / |
第10著者 所属(和/英) |
(略称: )
(略称: ) |
第11著者 氏名(和/英/ヨミ) |
/ / |
第11著者 所属(和/英) |
(略称: )
(略称: ) |
第12著者 氏名(和/英/ヨミ) |
/ / |
第12著者 所属(和/英) |
(略称: )
(略称: ) |
第13著者 氏名(和/英/ヨミ) |
/ / |
第13著者 所属(和/英) |
(略称: )
(略称: ) |
第14著者 氏名(和/英/ヨミ) |
/ / |
第14著者 所属(和/英) |
(略称: )
(略称: ) |
第15著者 氏名(和/英/ヨミ) |
/ / |
第15著者 所属(和/英) |
(略称: )
(略称: ) |
第16著者 氏名(和/英/ヨミ) |
/ / |
第16著者 所属(和/英) |
(略称: )
(略称: ) |
第17著者 氏名(和/英/ヨミ) |
/ / |
第17著者 所属(和/英) |
(略称: )
(略称: ) |
第18著者 氏名(和/英/ヨミ) |
/ / |
第18著者 所属(和/英) |
(略称: )
(略称: ) |
第19著者 氏名(和/英/ヨミ) |
/ / |
第19著者 所属(和/英) |
(略称: )
(略称: ) |
第20著者 氏名(和/英/ヨミ) |
/ / |
第20著者 所属(和/英) |
(略称: )
(略称: ) |
講演者 |
第1著者 |
発表日時 |
2016-11-16 15:00:00 |
発表時間 |
180分 |
申込先研究会 |
IBISML |
資料番号 |
IBISML2016-55 |
巻番号(vol) |
vol.116 |
号番号(no) |
no.300 |
ページ範囲 |
pp.65-71 |
ページ数 |
7 |
発行日 |
2016-11-09 (IBISML) |