Optimal strategies and minimax lower bounds for online convex games

A number of learning problems can be cast as an Online Convex Game: on each round, a learner makes a prediction x from a convex set, the environment plays a loss function f, and the learner’s long-term goal is to minimize regret. Algorithms have been proposed by Zinkevich, when f is assumed to be convex, and Hazan et al., when f is assumed to be strongly convex, that have provably low regret. We consider these two settings and analyze such games from a minimax perspective, proving minimax strategies and lower bounds in each case. These results prove that the existing algorithms are essentially optimal.

Matrix regularization techniques for online multitask learning

In this paper we examine the problem of prediction with expert advice in a setup where the learner is presented with a sequence of examples coming from different tasks. In order for the learner to be able to benefit from performing multiple tasks simultaneously, we make assumptions of task relatedness by constraining the comparator to use a lesser number of best experts than the number of tasks. We show how this corresponds naturally to learning under spectral or structural matrix constraints, and propose regularization techniques to enforce the constraints. The regularization techniques proposed here are interesting in their own right and multitask learning is just one application for the ideas. A theoretical analysis of one such regularizer is performed, and a regret bound that shows benefits of this setup is reported.

Closing the gap between bandit and full-information online optimization : high-probability regret bound

We demonstrate a modification of the algorithm of Dani et al for the online linear optimization problem in the bandit setting, which allows us to achieve an O( \sqrt{T ln T} ) regret bound in high probability against an adaptive adversary, as opposed to the in expectation result against an oblivious adversary of Dani et al. We obtain the same dependence on the dimension as that exhibited by Dani et al. The results of this paper rest firmly on those of Dani et al and the remarkable technique of Auer et al for obtaining high-probability bounds via optimistic estimates. This paper answers an open question: it eliminates the gap between the high-probability bounds obtained in the full-information vs bandit settings.

Adaptive online gradient descent

We study the rates of growth of the regret in online convex optimization. First, we show that a simple extension of the algorithm of Hazan et al eliminates the need for a priori knowledge of the lower bound on the second derivatives of the observed functions. We then provide an algorithm, Adaptive Online Gradient Descent, which interpolates between the results of Zinkevich for linear functions and of Hazan et al for strongly convex functions, achieving intermediate rates between [square root T] and [log T]. Furthermore, we show strong optimality of the algorithm. Finally, we provide an extension of our results to general norms.

Designing and using historical vignettes in science teaching : a personal account

Historical vignettes are interesting short stories which encapsulate a brief period of scientific history. They can be useful tools for teaching the nature of science, demonstrating the practices of science and making science fun. Historical vignettes illustrate the role of people and social processes in science. In this paper I describe my experience with writing and presenting an historical vignette during a Biology unit. Included is a copy of the vignette and I have identified some possible improvements that might lead to better outcomes. This may be helpful for other teachers who wish to try this strategy for themselves.

Teaching porn

This article gives an account of my experiences as a student and teacher of pornography in the UK university context. From my time as a student at Glasgow University in the late 1970s, to my classes on sexual transgression at Strathclyde in the 2000s, I trace changing attitudes to the pornographic, against the background of changing political and technological environments. The article considers the pedagogy of porn against the backdrop of pro- and anti-porn feminism, the rise of gay rights, and the impact of the internet. Under these influences, and over a period of three decades, pornography was destigmatized and redefined in a variety of contexts, from the irony of lad culture to the postmodern humour of the Graham Norton Show and the pro-porn feminism of the post-Madonna era.