A Stochastic View of Optimal Regret through Minimax Duality

We study the regret of optimal strategies for online convex optimization games. Using von Neumann's minimax theorem, we show that the optimal regret in this adversarial setting is closely related to the behavior of the empirical minimization algorithm in a stochastic process setting: it is equal to the maximum, over joint distributions of the adversary's action sequence, of the difference between a sum of minimal expected losses and the minimal empirical loss. We show that the optimal regret has a natural geometric interpretation, since it can be viewed as the gap in Jensen's inequality for a concave functional--the minimizer over the player's actions of expected loss--defined on a set of probability distributions. We use this expression to obtain upper and lower bounds on the regret of an optimal strategy for a variety of online learning problems. Our method provides upper bounds without the need to construct a learning algorithm; the lower bounds provide explicit optimal strategies for the adversary. Peter L. Bartlett, Alexander Rakhlin

Remote monitoring of outdoor performance of low scale dye sensitized solar cells for nanosensors nodes

This is the first outdoor test of small-scale dye sensitized solar cells (DSC) powering a stand-alone nanosensor node. A solar cell test station (SCTS) has been developed using standard DSC to power a gas nanosensor, a radio transmitter, and the control electronics (CE) for battery charging. The station is remotely monitored through wired (Ethernet cable) or wireless connection (radio transmitter) in order to evaluate in real time the performance of the solar cells and devices under different weather conditions. The 408 cm2 active surface module produces enough energy to power a gas nanosensor and a radio transmitter during the day and part of the night. Also, by using a programmable load we keep the system working on the maximum power point (MPP) quantifying the total energy generated and stored in a battery. These experiments provide useful data for future outdoor applications such as nanosensor networks.

The waddlia genome: A window into chlamydial biology

Growing evidence suggests that a novel member of the Chlamydiales order, Waddlia chondrophila, is a potential agent of miscarriage in humans and abortion in ruminants. Due to the lack of genetic tools to manipulate chlamydia, genomic analysis is proving to be the most incisive tool in stimulating investigations into the biology of these obligate intracellular bacteria. 454/Roche and Solexa/Illumina technologies were thus used to sequence and assemble de novo the full genome of the first representative of the Waddliaceae family, W. chondrophila. The bacteria possesses a 2′116′312bp chromosome and a 15′593 bp low-copy number plasmid that might integrate into the bacterial chromosome. The Waddlia genome displays numerous repeated sequences indicating different genome dynamics from classical chlamydia which almost completely lack repetitive elements. Moreover, W. chondrophila exhibits many virulence factors also present in classical chlamydia, including a functional type III secretion system, but also a large complement of specific factors for resistance to host or environmental stresses. Large families of outer membrane proteins were identified indicating that these highly immunogenic proteins are not Chlamydiaceae specific and might have been present in their last common ancestor. Enhanced metabolic capability for the synthesis of nucleotides, amino acids, lipids and other co-factors suggests that the common ancestor of the modern Chlamydiales may have been less dependent on their eukaryotic host. The fine-detailed analysis of biosynthetic pathways brings us closer to possibly developing a synthetic medium to grow W. chondrophila, a critical step in the development of genetic tools. As a whole, the availability of the W. chondrophila genome opens new possibilities in Chlamydiales research, providing new insights into the evolution of members of the order Chlamydiales and the biology of the Waddliaceae.

Identification of circulating tumour cells in early stage breast cancer patients using multi marker immunobead RT-PCR

Introduction The ability to screen blood of early stage operable breast cancer patients for circulating tumour cells is of potential importance for identifying patients at risk of developing distant relapse. We present the results of a study of the efficacy of the immunobead RT-PCR method in identifying patients with circulating tumour cells. Results Immunomagnetic enrichment of circulating tumour cells followed by RT-PCR (immunobead RT-PCR) with a panel of five epithelial specific markers (ELF3, EPHB4, EGFR, MGB1 and TACSTD1) was used to screen for circulating tumour cells in the peripheral blood of 56 breast cancer patients. Twenty patients were positive for two or more RT-PCR markers, including seven patients who were node negative by conventional techniques. Significant increases in the frequency of marker positivity was seen in lymph node positive patients, in patients with high grade tumours and in patients with lymphovascular invasion. A strong trend towards improved disease free survival was seen for marker negative patients although it did not reach significance (p = 0.08). Conclusion Multi-marker immunobead RT-PCR analysis of peripheral blood is a robust assay that is capable of detecting circulating tumour cells in early stage breast cancer patients.

Multitask learning with expert advice

We consider the problem of prediction with expert advice in the setting where a forecaster is presented with several online prediction tasks. Instead of competing against the best expert separately on each task, we assume the tasks are related, and thus we expect that a few experts will perform well on the entire set of tasks. That is, our forecaster would like, on each task, to compete against the best expert chosen from a small set of experts. While we describe the “ideal” algorithm and its performance bound, we show that the computation required for this algorithm is as hard as computation of a matrix permanent. We present an efficient algorithm based on mixing priors, and prove a bound that is nearly as good for the sequential task presentation case. We also consider a harder case where the task may change arbitrarily from round to round, and we develop an efficient approximate randomized algorithm based on Markov chain Monte Carlo techniques.

Online discovery of similarity mappings

We consider the problem of choosing, sequentially, a map which assigns elements of a set A to a few elements of a set B. On each round, the algorithm suffers some cost associated with the chosen assignment, and the goal is to minimize the cumulative loss of these choices relative to the best map on the entire sequence. Even though the offline problem of finding the best map is provably hard, we show that there is an equivalent online approximation algorithm, Randomized Map Prediction (RMP), that is efficient and performs nearly as well. While drawing upon results from the "Online Prediction with Expert Advice" setting, we show how RMP can be utilized as an online approach to several standard batch problems. We apply RMP to online clustering as well as online feature selection and, surprisingly, RMP often outperforms the standard batch algorithms on these problems.

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.

Multitask learning with expert advice

We consider the problem of prediction with expert advice in the setting where a forecaster is presented with several online prediction tasks. Instead of competing against the best expert separately on each task, we assume the tasks are related, and thus we expect that a few experts will perform well on the entire set of tasks. That is, our forecaster would like, on each task, to compete against the best expert chosen from a small set of experts. While we describe the "ideal" algorithm and its performance bound, we show that the computation required for this algorithm is as hard as computation of a matrix permanent. We present an efficient algorithm based on mixing priors, and prove a bound that is nearly as good for the sequential task presentation case. We also consider a harder case where the task may change arbitrarily from round to round, and we develop an efficient approximate randomized algorithm based on Markov chain Monte Carlo techniques.