Paper Abstract and Keywords |
Presentation |
2017-11-09 13:00
Online Optimization Method for Generalized $ell_1$ Regularized Problems Yoshihiro Nakazato, Kazuto Fukuchi (Tsukuba Univ.), Jun Sakuma (Tsukuba Univ./Riken/JST) IBISML2017-47 |
Abstract |
(in Japanese) |
(See Japanese page) |
(in English) |
Structured sparse regularization is vital to enhance the precision and the interpretability of the model by introducing the prior knowledge.
Also, it decreases the substantial number of features and improves the learnability of the model.
In this paper, we shed light on the structured $ell_1$ regularized problems including generalized fused Lasso (GFL) and trend filtering.
We propose a novel online convex optimization algorithm that solves the structured $ell_1$ regularized problems.
Taking advantage of proximal averagecite{yu2013better} in dual space, our method success decreasing its convergence rate regarding the dimensional dependency exponentially.
Besides, we propose an efficient implementation of proximal mapping and show the computational complexity of GFL is $O(dk)$, whereas state-of-the-art is $O(d|E|)$,
where $d$ is the number of features, and $k$ is the max degree of the graph, and $|E|$ is the number of the edges.
In experiments, we demonstrate our proposal can solve the GFL faster than normal proximal average in both synthetic and real dataset.
Also, we show our method spends only up to 20 ms in each iteration with the enormous dataset with 100,000 features and about 340,000 edges. |
Keyword |
(in Japanese) |
(See Japanese page) |
(in English) |
Online convex optimization / Generalized fused Lasso / Trend filtering / Online mirror descent / / / / |
Reference Info. |
IEICE Tech. Rep., vol. 117, no. 293, IBISML2017-47, pp. 93-100, Nov. 2017. |
Paper # |
IBISML2017-47 |
Date of Issue |
2017-11-02 (IBISML) |
ISSN |
Print edition: ISSN 0913-5685 Online edition: ISSN 2432-6380 |
Copyright and reproduction |
All rights are reserved and no part of this publication may be reproduced or transmitted in any form or by any means, electronic or mechanical, including photocopy, recording, or any information storage and retrieval system, without permission in writing from the publisher. Notwithstanding, instructors are permitted to photocopy isolated articles for noncommercial classroom use without fee. (License No.: 10GA0019/12GB0052/13GB0056/17GB0034/18GB0034) |
Download PDF |
IBISML2017-47 |
Conference Information |
Committee |
IBISML |
Conference Date |
2017-11-08 - 2017-11-10 |
Place (in Japanese) |
(See Japanese page) |
Place (in English) |
Univ. of Tokyo |
Topics (in Japanese) |
(See Japanese page) |
Topics (in English) |
Information-Based Induction Science Workshop (IBIS2017) |
Paper Information |
Registration To |
IBISML |
Conference Code |
2017-11-IBISML |
Language |
Japanese |
Title (in Japanese) |
(See Japanese page) |
Sub Title (in Japanese) |
(See Japanese page) |
Title (in English) |
Online Optimization Method for Generalized $ell_1$ Regularized Problems |
Sub Title (in English) |
|
Keyword(1) |
Online convex optimization |
Keyword(2) |
Generalized fused Lasso |
Keyword(3) |
Trend filtering |
Keyword(4) |
Online mirror descent |
Keyword(5) |
|
Keyword(6) |
|
Keyword(7) |
|
Keyword(8) |
|
1st Author's Name |
Yoshihiro Nakazato |
1st Author's Affiliation |
University of Tsukuba (Tsukuba Univ.) |
2nd Author's Name |
Kazuto Fukuchi |
2nd Author's Affiliation |
University of Tsukuba (Tsukuba Univ.) |
3rd Author's Name |
Jun Sakuma |
3rd Author's Affiliation |
University of Tsukuba/Riken/JST (Tsukuba Univ./Riken/JST) |
4th Author's Name |
|
4th Author's Affiliation |
() |
5th Author's Name |
|
5th Author's Affiliation |
() |
6th Author's Name |
|
6th Author's Affiliation |
() |
7th Author's Name |
|
7th Author's Affiliation |
() |
8th Author's Name |
|
8th Author's Affiliation |
() |
9th Author's Name |
|
9th Author's Affiliation |
() |
10th Author's Name |
|
10th Author's Affiliation |
() |
11th Author's Name |
|
11th Author's Affiliation |
() |
12th Author's Name |
|
12th Author's Affiliation |
() |
13th Author's Name |
|
13th Author's Affiliation |
() |
14th Author's Name |
|
14th Author's Affiliation |
() |
15th Author's Name |
|
15th Author's Affiliation |
() |
16th Author's Name |
|
16th Author's Affiliation |
() |
17th Author's Name |
|
17th Author's Affiliation |
() |
18th Author's Name |
|
18th Author's Affiliation |
() |
19th Author's Name |
|
19th Author's Affiliation |
() |
20th Author's Name |
|
20th Author's Affiliation |
() |
Speaker |
Author-1 |
Date Time |
2017-11-09 13:00:00 |
Presentation Time |
150 minutes |
Registration for |
IBISML |
Paper # |
IBISML2017-47 |
Volume (vol) |
vol.117 |
Number (no) |
no.293 |
Page |
pp.93-100 |
#Pages |
8 |
Date of Issue |
2017-11-02 (IBISML) |
|