27 research outputs found
Online Similarity Prediction of Networked Data from Known and Unknown Graphs
No full textWe consider online similarity prediction problems over networked data. We begin by relating this task to the more standard class prediction problem, showing that, given an arbitrary algorithm for class prediction, we can construct an algorithm for similarity prediction with "nearly" the same mistake bound, and vice versa. After noticing that this general construction is computationally infeasible, we target our study to {\em feasible} similarity prediction algorithms on networked data. We initially assume that the network structure is {\em known} to the learner. Here we observe that Matrix Winnow \cite{w07} has a near-optimal mistake guarantee, at the price of cubic prediction time per round. This motivates our effort for an efficient implementation of a Perceptron algorithm with a weaker mistake guarantee but with only poly-logarithmic prediction time. Our focus then turns to the challenging case of networks whose structure is initially {\em unknown} to the learner. In this novel setting, where the network structure is only incrementally revealed, we obtain a mistake-bounded algorithm with a quadratic prediction time per round
Vapour phase investigation of the impact of soil organic matter on the sorption and phase distribution of 20% ethanol-blended gasoline in the vadose zone
No full textA Hierarchical Nearest Neighbour Approach to Contextual Bandits
No full textIn this paper we consider the adversarial contextual bandit problem in metric
spaces. The paper "Nearest neighbour with bandit feedback" tackled this problem
but when there are many contexts near the decision boundary of the comparator
policy it suffers from a high regret. In this paper we eradicate this problem,
designing an algorithm in which we can hold out any set of contexts when
computing our regret term. Our algorithm builds on that of "Nearest neighbour
with bandit feedback" and hence inherits its extreme computational efficiency
Nearest Neighbour with Bandit Feedback
No full textIn this paper we adapt the nearest neighbour rule to the contextual bandit
problem. Our algorithm handles the fully adversarial setting in which no
assumptions at all are made about the data-generation process. When combined
with a sufficiently fast data-structure for (perhaps approximate) adaptive
nearest neighbour search, such as a navigating net, our algorithm is extremely
efficient - having a per trial running time polylogarithmic in both the number
of trials and actions, and taking only quasi-linear space. We give generic
regret bounds for our algorithm and further analyse them when applied to the
stochastic bandit problem in euclidean space. We note that our algorithm can
also be applied to the online classification problem
On Similarity Prediction and Pairwise Clustering
No full textInternational audienceWe consider the problem of clustering a finite set of items from pairwise similarity information. Unlike what is done in the literature on this subject, we do so in a passive learning setting, and with no specific constraints on the cluster shapes other than their size. We investigate the problem in different settings: i. an online setting, where we provide a tight characterization of the prediction complexity in the mistake bound model, and ii. a standard stochastic batch setting, where we give tight upper and lower bounds on the achievable generalization error. Prediction performance is measured both in terms of the ability to recover the similarity function encoding the hidden clustering and in terms of how well we classify each item within the set. The proposed algorithms are time efficient
MaxHedge: Maximising a Maximum Online
No full textInternational audienceWe introduce a new online learning framework where, at each trial, the learner is required to select a subset of actions from a given known action set. Each action is associated with an energy value, a reward and a cost. The sum of the energies of the actions selected cannot exceed a given energy budget. The goal is to maximise the cumulative profit, where the profit obtained on a single trial is defined as the difference between the maximum reward among the selected actions and the sum of their costs. Action energy values and the budget are known and fixed. All rewards and costs associated with each action change over time and are revealed at each trial only after the learner's selection of actions. Our framework encompasses several online learning problems where the environment changes over time; and the solution trades-off between minimising the costs and maximising the maximum reward of the selected subset of actions, while being constrained to an action energy budget. The algorithm that we propose is efficient and general that may be specialised to multiple natural online combinatorial problems
Online Convex Optimisation: The Optimal Switching Regret for all Segmentations Simultaneously
No full textWe consider the classic problem of online convex optimisation. Whereas the
notion of static regret is relevant for stationary problems, the notion of
switching regret is more appropriate for non-stationary problems. A switching
regret is defined relative to any segmentation of the trial sequence, and is
equal to the sum of the static regrets of each segment. In this paper we show
that, perhaps surprisingly, we can achieve the asymptotically optimal switching
regret on every possible segmentation simultaneously. Our algorithm for doing
so is very efficient: having a space and per-trial time complexity that is
logarithmic in the time-horizon. Our algorithm also obtains novel bounds on its
dynamic regret: being adaptive to variations in the rate of change of the
comparator sequence
Online Convex Optimisation: The Optimal Switching Regret for all Segmentations Simultaneously
No full textWe consider the classic problem of online convex optimisation. Whereas the notion of static regret is relevant for stationary problems, the notion of switching regret is more appropriate for non-stationary problems. A switching regret is defined relative to any segmentation of the trial sequence, and is equal to the sum of the static regrets of each segment. In this paper we show that, perhaps surprisingly, we can achieve the asymptotically optimal switching regret on every possible segmentation simultaneously. Our algorithm for doing so is very efficient: having a space and per-trial time complexity that is logarithmic in the time-horizon. Our algorithm also obtains novel bounds on its dynamic regret: being adaptive to variations in the rate of change of the comparator sequence
Looking Glass of NFV: Inferring the Structure and State of NFV Network from External Observations
No full text
