Skip navigation
Skip navigation

Transitions, Losses, and Re-parameterizations: Elements of Prediction Games

Parameswaran, Kamalaruban

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.authorParameswaran, Kamalaruban
dc.date.accessioned2017-10-18T05:42:14Z
dc.date.available2017-10-18T05:42:14Z
dc.identifier.otherb47392691
dc.identifier.urihttp://hdl.handle.net/1885/131341
dc.description.abstractThis 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.isoen
dc.subjectStatistical Decision Theory
dc.subjectInformation Theory
dc.subjectCost-Sensitive Classification
dc.subjectStrong Data Processing Inequalities
dc.subjectPrediction with Expert Advice
dc.subjectOnline Convex Optimization
dc.titleTransitions, Losses, and Re-parameterizations: Elements of Prediction Games
dc.typeThesis (PhD)
local.contributor.supervisorWilliamson, Robert C.
local.contributor.supervisorcontactBob.Williamson@anu.edu.au
dcterms.valid2017
local.description.notesthe author deposited 18/10/17
local.type.degreeDoctor of Philosophy (PhD)
dc.date.issued2017
local.contributor.affiliationResearch School of Computer Science, ANU College of Engineering and Computer Science, The Australian National University
local.identifier.doi10.25911/5d723bc67a01e
local.mintdoimint
CollectionsOpen Access Theses

Download

File Description SizeFormat Image
Parameswaran Thesis 2017.pdf5.87 MBAdobe PDFThumbnail


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