東華大學圖書館 |

Language: English

Help

回圖書館首頁

手機版館藏查詢

Back

Switch To: Labeled | MARC Mode | ISBD

A Regularization Perspective on Spec...

Liao, Zhenyu.

Linked to FindBook

Google Book

Amazon

博客來

A Regularization Perspective on Spectral Sparsification.

Record Type:	Electronic resources : Monograph/item
Title/Author:	A Regularization Perspective on Spectral Sparsification./
Author:	Liao, Zhenyu.
Published:	Ann Arbor : ProQuest Dissertations & Theses, : 2019,
Description:	80 p.
Notes:	Source: Dissertations Abstracts International, Volume: 81-06, Section: B.
Contained By:	Dissertations Abstracts International81-06B.
Subject:	Computer science. -
Online resource:	http://pqdd.sinica.edu.tw/twdaoapp/servlet/advanced?query=13424514
ISBN:	9781392668023

A Regularization Perspective on Spectral Sparsification.
Liao, Zhenyu.

A Regularization Perspective on Spectral Sparsification. - Ann Arbor : ProQuest Dissertations & Theses, 2019 - 80 p.

Source: Dissertations Abstracts International, Volume: 81-06, Section: B.

Thesis (Ph.D.)--Boston University, 2019.

This item must not be sold to any third party vendors.

In this thesis, we study how to obtain faster algorithms for spectral graph sparsifi-cation by applying continuous optimization techniques. Spectral sparsification is thetask of reducing the number of edges in a graph while maintaining a spectral ap-proximation to the original graph. Our key conceptual contribution is the connectionbetween spectral sparsification and regret minimization in online matrix games, i.e.,online convex programming over the positive semidefinite cone. While this connec-tion was previously noted [24, 47], we formally reduce graph sparsification to a matrixregret minimization problem, which we solve by applying mirror descent with a non-entropic regularizer. In this way, we not only obtain a new proof of the existenceof linear-sized spectral sparsifiers, originally given by [19], but improve the runningtime from Ω(n4)([19, 54]) to almost quadratic. More generally, our framework canalso be applied for the matrix multi-armed bandit online learning problem to reducethe regret bound to the optimalO(√nT), compared to theO(√nTlog(n) given bythe traditional matrix-entropy regulariz.

ISBN: 9781392668023Subjects--Topical Terms:

523869
Computer science.

A Regularization Perspective on Spectral Sparsification.
LDR:02166nmm a2200301 4500 001 2263151
005 20200214113158.5
008 220629s2019 ||||||||||||||||| ||eng d
020 $a 9781392668023
035 $a (MiAaPQ)AAI13424514
035 $a AAI13424514
040 $a MiAaPQ $c MiAaPQ
100 1 $a Liao, Zhenyu. $3 3540235
245 1 0 $a A Regularization Perspective on Spectral Sparsification.
260 1 $a Ann Arbor : $b ProQuest Dissertations & Theses, $c 2019
300 $a 80 p.
500 $a Source: Dissertations Abstracts International, Volume: 81-06, Section: B.
500 $a Advisor: Orecchia, Lorenzo.
502 $a Thesis (Ph.D.)--Boston University, 2019.
506 $a This item must not be sold to any third party vendors.
506 $a This item must not be added to any third party search indexes.
520 $a In this thesis, we study how to obtain faster algorithms for spectral graph sparsifi-cation by applying continuous optimization techniques. Spectral sparsification is thetask of reducing the number of edges in a graph while maintaining a spectral ap-proximation to the original graph. Our key conceptual contribution is the connectionbetween spectral sparsification and regret minimization in online matrix games, i.e.,online convex programming over the positive semidefinite cone. While this connec-tion was previously noted [24, 47], we formally reduce graph sparsification to a matrixregret minimization problem, which we solve by applying mirror descent with a non-entropic regularizer. In this way, we not only obtain a new proof of the existenceof linear-sized spectral sparsifiers, originally given by [19], but improve the runningtime from Ω(n4)([19, 54]) to almost quadratic. More generally, our framework canalso be applied for the matrix multi-armed bandit online learning problem to reducethe regret bound to the optimalO(√nT), compared to theO(√nTlog(n) given bythe traditional matrix-entropy regulariz.
590 $a School code: 0017.
650 4 $a Computer science. $3 523869
690 $a 0984
710 2 $a Boston University. $b Computer Science GRS. $3 3169364
773 0 $t Dissertations Abstracts International $g 81-06B.
790 $a 0017
791 $a Ph.D.
792 $a 2019
793 $a English
856 4 0 $u http://pqdd.sinica.edu.tw/twdaoapp/servlet/advanced?query=13424514