東華大學圖書館 |

語系: 繁體中文

說明(常見問題)

回圖書館首頁

手機版館藏查詢

登入

回首頁

切換: 標籤 | MARC模式 | ISBD

Competitive and Regret Analysis for ...

Yang, Lin.

FindBook

Google Book

Amazon

博客來

Competitive and Regret Analysis for Online Optimization.

紀錄類型:	書目-電子資源 : Monograph/item
正題名/作者:	Competitive and Regret Analysis for Online Optimization./
作者:	Yang, Lin.
出版者:	Ann Arbor : ProQuest Dissertations & Theses, : 2018,
面頁冊數:	162 p.
附註:	Source: Dissertation Abstracts International, Volume: 80-06(E), Section: B.
Contained By:	Dissertation Abstracts International80-06B(E).
標題:	Computer science. -
電子資源:	http://pqdd.sinica.edu.tw/twdaoapp/servlet/advanced?query=13837926
ISBN:	9780438852242

Competitive and Regret Analysis for Online Optimization.
Yang, Lin.

Competitive and Regret Analysis for Online Optimization. - Ann Arbor : ProQuest Dissertations & Theses, 2018 - 162 p.

Source: Dissertation Abstracts International, Volume: 80-06(E), Section: B.

Thesis (Ph.D.)--The Chinese University of Hong Kong (Hong Kong), 2018.

For optimization problems involving time-varying input, if the entire input is available from the start, decisions of an algorithm can be determined offline. However, in practice, knowledge on the system is usually limited, and input for the algorithm can be only acquired piece by piece. In this case, optimization for algorithm decisions must be conducted in an online fashion. Motivated by this, there are increasing research interests on online optimization and efficient online algorithms, whose decision making only depends on current or past inputs. This thesis focuses on several influential online optimization paradigms in computer science and operations research: the online QoS (Quality of Service) buffer management problem, the online trading problem, and the online learning problem.

ISBN: 9780438852242Subjects--Topical Terms:

523869
Computer science.

Competitive and Regret Analysis for Online Optimization.
LDR:04368nmm a2200325 4500 001 2203298
005 20190528072656.5
008 201008s2018 ||||||||||||||||| ||eng d
020 $a 9780438852242
035 $a (MiAaPQ)AAI13837926
035 $a AAI13837926
040 $a MiAaPQ $c MiAaPQ
100 1 $a Yang, Lin. $3 1259477
245 1 0 $a Competitive and Regret Analysis for Online Optimization.
260 1 $a Ann Arbor : $b ProQuest Dissertations & Theses, $c 2018
300 $a 162 p.
500 $a Source: Dissertation Abstracts International, Volume: 80-06(E), Section: B.
502 $a Thesis (Ph.D.)--The Chinese University of Hong Kong (Hong Kong), 2018.
520 $a For optimization problems involving time-varying input, if the entire input is available from the start, decisions of an algorithm can be determined offline. However, in practice, knowledge on the system is usually limited, and input for the algorithm can be only acquired piece by piece. In this case, optimization for algorithm decisions must be conducted in an online fashion. Motivated by this, there are increasing research interests on online optimization and efficient online algorithms, whose decision making only depends on current or past inputs. This thesis focuses on several influential online optimization paradigms in computer science and operations research: the online QoS (Quality of Service) buffer management problem, the online trading problem, and the online learning problem.
520 $a The online QoS buffer management problem is a standard online paradigm in resource allocation. In its basic setting, packets with different values defined according to their QoS requirements arrive in an online fashion to a switching node. To maximize cumulative profit, the switch needs to decide whether to admit the incoming packet based on the packet value and its buffer availability. Even though this problem was proposed more than a decade ago, no optimal online solution has been proposed in the literature. In this thesis, we define a new online algorithm by leveraging a novel construction involving virtual queues, and prove that it can achieve the lower bound of the competitive ratio for any online algorithms.
520 $a This thesis also investigates another important application of online optimization in online trading. Nowadays, the electricity market has become more deregulated, resulting in individual participants to design more intelligent trading algorithms. The individual consumers and electricity suppliers both need to bid to offer or procure along with other competitors, faced with unpredictable market price fluctuation. Compared to traditional study, the novelty of our work is that we study a more general scenario where the cargo can be stored somewhere, as in a pumped storage system, for more desirable prices. In the presence of storage, it is more challenging to design online trading strategies, due to the additional design space enabled by the storage. In this thesis, we study the online trading problems from both sides of the electricity market (energy suppliers and consumers) and provide optimal online solutions, respectively.
520 $a The last investigated online optimization problem is the online learning problem, where regret is taken as an important performance metric for an online algorithm. Much efforts have been devoted to the Expert learning problem and the Online Convex Optimization (OCO) problem etc. Those traditional frameworks are limited in some recent application scenarios, especially when the learning set is from a metric space or the learning algorithm is faced with non-convex losses. Motivated by this, we focus our efforts on the Online Non-Convex Learning problem (ONCL), which generalizes the OCO problem by removing the convexity assumption on both the cost function and the decision set. In this thesis, we propose a novel online algorithm, which improves the known result O(√T ln T) to O(√T), achieving the lower bound for the OCO problem and filling the regret gap between the state-of-the-art results in online convex and non-convex learning problems.
590 $a School code: 1307.
650 4 $a Computer science. $3 523869
650 4 $a Artificial intelligence. $3 516317
650 4 $a Computer engineering. $3 621879
690 $a 0984
690 $a 0800
690 $a 0464
710 2 $a The Chinese University of Hong Kong (Hong Kong). $b Information Engineering. $3 3180141
773 0 $t Dissertation Abstracts International $g 80-06B(E).
790 $a 1307
791 $a Ph.D.
792 $a 2018
793 $a English
856 4 0 $u http://pqdd.sinica.edu.tw/twdaoapp/servlet/advanced?query=13837926