Feasibility optimality of periodwise static priority policies for a quality of service model in wireless networks and convergence analysis for an online recommendation system

Truong, Anh

Permalink

https://hdl.handle.net/2142/26347 Copy

Description

Title

Feasibility optimality of periodwise static priority policies for a quality of service model in wireless networks and convergence analysis for an online recommendation system

Author(s)

Truong, Anh

Issue Date

2011-08-26T15:24:21Z

Director of Research (if dissertation) or Advisor (if thesis)

• Kiyavash, Negar
• Kumar, P.R.

Department of Study

Electrical & Computer Eng

Discipline

Electrical & Computer Engr

Degree Granting Institution

University of Illinois at Urbana-Champaign

Degree Name

M.S.

Degree Level

Thesis

Keyword(s)

• QoS scheduling
• randomized policies
• feasibility optimal
• priority policies
• submodularity
• polymatroid
• learning with experts
• weighted average prediction
• availability
• accuracy
• convergence
• sleeping experts
• recommendation system.
• Quality of Service (QoS)

Abstract

In the first part of this thesis, we consider a proposed Quality of Service (QoS) model in which a set of clients require their own timely-throughput from an access point, with packet deadlines restricted to be in one period. It is known that two debt-based policies, including time-based debt and weighted delivery-based debt, are feasibility optimal in the sense that they can fulfill the requirements of all sets of feasible clients. We analyze why these poli- cies are optimal by considering a class of periodwise static priority policies. We prove that this latter class of policies can achieve whatever a history- dependent policy can, i.e., it suffices to consider only this class of policies for such a scheduling problem. Our approach proceeds by investigating the submodularity of the complement of the idle time function. We thereby show that the set defined by the timely-throughput constraints is a polymatroid, from which the optimality within the class of periodwise static priority poli- cies follows. The second part of the thesis analyzes the convergence of an algorithm for the problem of learning with expert advice. At the present time, several web-based recommendation systems use votes from experts or other users to recommend objects to other customers. We apply the `learning from expert advice' framework for this system, and propose a recommendation algorithm that uses a weighted update rule. Often, recommendation algorithms make assumptions that do not hold in practice, such as requiring a large number of good objects, presence of experts with the identical taste as the user receiving the recommendation, or experts who vote on all or a majority of objects. Our algorithm relaxes these assumptions by allowing an arbitrary proportion of bad objects as well as arbitrary tastes of experts. Moreover, it can deal with the issues that arise because of the existence of sleeping-experts, i.e., experts who are not available for voting at all rounds. A key attribute of our approach is to define the concept of the best expert on the basis of both availability and accuracy of experts. We then prove that the algorithm converges almost surely to the best expert(s) regardless of whether the predictions of experts are binary or continuous valued. Moreover, we derive an upper bound on loss of the proposed algorithm by comparing it to the loss of an appropriately defined `current best' and show that the regret of our algorithm is logarithmic in the number of experts. Besides theoretical performance guarantees, we present simulation results that show the proposed algorithm outperforms Dsybil, the current state-of-the-art recommendation algorithm.

Graduation Semester

2011-08

Permalink

http://hdl.handle.net/2142/26347

Copyright and License Information

Copyright 2011 Anh Truong

Owning Collections