Transitions, Losses, and Re-parameterizations: Elements of Prediction Games
Download (5.87 MB)
-
Altmetric Citations
Description
This thesis presents some geometric insights into three different types of two-player prediction games – namely general learning task, prediction with expert advice, and online convex optimization. These games differ in the nature of the opponent (stochastic, adversarial, or intermediate), the order of the players' move, and the utility function. The insights shed some light on the understanding of the intrinsic barriers of the prediction problems and the...[Show more]
dc.contributor.author | Parameswaran, Kamalaruban | |
---|---|---|
dc.date.accessioned | 2017-10-18T05:42:14Z | |
dc.date.available | 2017-10-18T05:42:14Z | |
dc.identifier.other | b47392691 | |
dc.identifier.uri | http://hdl.handle.net/1885/131341 | |
dc.description.abstract | This thesis presents some geometric insights into three different types of two-player prediction games – namely general learning task, prediction with expert advice, and online convex optimization. These games differ in the nature of the opponent (stochastic, adversarial, or intermediate), the order of the players' move, and the utility function. The insights shed some light on the understanding of the intrinsic barriers of the prediction problems and the design of computationally efficient learning algorithms with strong theoretical guarantees (such as generalizability, statistical consistency, and constant regret etc.). The main contributions of the thesis are: • Leveraging concepts from statistical decision theory, we develop a necessary toolkit for formalizing the prediction games mentioned above and quantifying the objective of them. • We investigate the cost-sensitive classification problem which is an instantiation of the general learning task, and demonstrate the hardness of this problem by producing the lower bounds on the minimax risk of it. Then we analyse the impact of imposing constraints (such as corruption level, and privacy requirements etc.) on the general learning task. This naturally leads us to further investigation of strong data processing inequalities which is a fundamental concept in information theory. Furthermore, by extending the hypothesis testing interpretation of standard privacy definitions, we propose an asymmetric (prioritized) privacy definition. • We study efficient merging schemes for prediction with expert advice problem and the geometric properties (mixability and exp-concavity) of the loss functions that guarantee constant regret bounds. As a result of our study, we construct two types of link functions (one using calculus approach and another using geometric approach) that can re-parameterize any binary mixable loss into an exp-concave loss. • We focus on some recent algorithms for online convex optimization, which exploit the easy nature of the data (such as sparsity, predictable sequences, and curved losses) in order to achieve better regret bound while ensuring the protection against the worst case scenario. We unify some of these existing techniques to obtain new update rules for the cases when these easy instances occur together, and analyse the regret bounds of them. | |
dc.language.iso | en | |
dc.subject | Statistical Decision Theory | |
dc.subject | Information Theory | |
dc.subject | Cost-Sensitive Classification | |
dc.subject | Strong Data Processing Inequalities | |
dc.subject | Prediction with Expert Advice | |
dc.subject | Online Convex Optimization | |
dc.title | Transitions, Losses, and Re-parameterizations: Elements of Prediction Games | |
dc.type | Thesis (PhD) | |
local.contributor.supervisor | Williamson, Robert C. | |
local.contributor.supervisorcontact | Bob.Williamson@anu.edu.au | |
dcterms.valid | 2017 | |
local.description.notes | the author deposited 18/10/17 | |
local.type.degree | Doctor of Philosophy (PhD) | |
dc.date.issued | 2017 | |
local.contributor.affiliation | Research School of Computer Science, ANU College of Engineering and Computer Science, The Australian National University | |
local.identifier.doi | 10.25911/5d723bc67a01e | |
local.mintdoi | mint | |
Collections | Open Access Theses |
Download
File | Description | Size | Format | Image |
---|---|---|---|---|
Parameswaran Thesis 2017.pdf | 5.87 MB | Adobe PDF |
Items in Open Research are protected by copyright, with all rights reserved, unless otherwise indicated.
Updated: 17 November 2022/ Responsible Officer: University Librarian/ Page Contact: Library Systems & Web Coordinator