64
64

Sep 20, 2013
09/13

by
Claudio Gentile; Francesco Orabona

texts

#
eye 64

#
favorite 0

#
comment 0

We present a novel multilabel/ranking algorithm working in partial information settings. The algorithm is based on 2nd-order descent methods, and relies on upper-confidence bounds to trade-off exploration and exploitation. We analyze this algorithm in a partial adversarial setting, where covariates can be adversarial, but multilabel probabilities are ruled by (generalized) linear models. We show O(T^{1/2} log T) regret bounds, which improve in several ways on the existing results. We test the...

Source: http://arxiv.org/abs/1207.0166v3

3
3.0

Jun 30, 2018
06/18

by
Claudio Gentile; Shuai Li; Giovanni Zappella

texts

#
eye 3

#
favorite 0

#
comment 0

We introduce a novel algorithmic approach to content recommendation based on adaptive clustering of exploration-exploitation ("bandit") strategies. We provide a sharp regret analysis of this algorithm in a standard stochastic noise setting, demonstrate its scalability properties, and prove its effectiveness on a number of artificial and real-world datasets. Our experiments show a significant increase in prediction performance over state-of-the-art methods for bandit problems.

Topics: Machine Learning, Computing Research Repository, Statistics, Learning

Source: http://arxiv.org/abs/1401.8257

9
9.0

Aug 11, 2020
08/20

by
Ofer Dekel; Claudio Gentile; Karthik Sridharan

data

#
eye 9

#
favorite 0

#
comment 0

Source: http://academictorrents.com/details/fb08d84af039c318a50f8406cd679ad90ba2d758

66
66

Jun 26, 2018
06/18

by
Shuai Li; Alexandros Karatzoglou; Claudio Gentile

texts

#
eye 66

#
favorite 0

#
comment 0

Classical collaborative filtering, and content-based filtering methods try to learn a static recommendation model given training data. These approaches are far from ideal in highly dynamic recommendation domains such as news recommendation and computational advertisement, where the set of items and users is very fluid. In this work, we investigate an adaptive clustering technique for content recommendation based on exploration-exploitation strategies in contextual multi-armed bandit settings....

Topics: Machine Learning, Learning, Artificial Intelligence, Statistics, Computing Research Repository

Source: http://arxiv.org/abs/1502.03473

7
7.0

Jun 29, 2018
06/18

by
Shuai Li; Claudio Gentile; Alexandros Karatzoglou

texts

#
eye 7

#
favorite 0

#
comment 0

We investigate an efficient context-dependent clustering technique for recommender systems based on exploration-exploitation strategies through multi-armed bandits over multiple users. Our algorithm dynamically groups users based on their observed behavioral similarity during a sequence of logged activities. In doing so, the algorithm reacts to the currently served user by shaping clusters around him/her but, at the same time, it explores the generation of clusters over users which are not...

Topics: Information Retrieval, Machine Learning, Artificial Intelligence, Learning, Statistics, Computing...

Source: http://arxiv.org/abs/1605.00596

36
36

Sep 22, 2013
09/13

by
Claudio Gentile; Mark Herbster; Stephen Pasteris

texts

#
eye 36

#
favorite 0

#
comment 0

We 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...

Source: http://arxiv.org/abs/1302.7263v3

8
8.0

Aug 11, 2020
08/20

by
Giovanni Cavallanti; Nicol Cesa-Bianchi; Claudio Gentile

data

#
eye 8

#
favorite 0

#
comment 0

Source: http://academictorrents.com/details/e90de45a88ab4dc26492b4489f438d890281a288

49
49

Sep 23, 2013
09/13

by
Dotan Di Castro; Claudio Gentile; Shie Mannor

texts

#
eye 49

#
favorite 0

#
comment 0

We consider a bandit problem over a graph where the rewards are not directly observed. Instead, the decision maker can compare two nodes and receive (stochastic) information pertaining to the difference in their value. The graph structure describes the set of possible comparisons. Consequently, comparing between two nodes that are relatively far requires estimating the difference between every pair of nodes on the path between them. We analyze this problem from the perspective of sample...

Source: http://arxiv.org/abs/1109.2296v1

15
15

Aug 11, 2020
08/20

by
Nicol Cesa-Bianchi; Claudio Gentile; Luca Zaniboni

data

#
eye 15

#
favorite 0

#
comment 0

Source: http://academictorrents.com/details/8e9fbb3ea861d404bb3ad130f2aa9c970ecc4778

12
12

Aug 11, 2020
08/20

by
Nicol Cesa-Bianchi; Claudio Gentile; Luca Zaniboni

data

#
eye 12

#
favorite 0

#
comment 0

Source: http://academictorrents.com/details/6337ffb8648d6c0dd01b9d5463f86c66f7b1c96f

59
59

Sep 21, 2013
09/13

by
Fabio Vitale; Nicolo Cesa-Bianchi; Claudio Gentile; Giovanni Zappella

texts

#
eye 59

#
favorite 0

#
comment 0

Predicting the nodes of a given graph is a fascinating theoretical problem with applications in several domains. Since graph sparsification via spanning trees retains enough information while making the task much easier, trees are an important special case of this problem. Although it is known how to predict the nodes of an unweighted tree in a nearly optimal way, in the weighted case a fully satisfactory algorithm is not available yet. We fill this hole and introduce an efficient node...

Source: http://arxiv.org/abs/1301.5160v2

42
42

Sep 21, 2013
09/13

by
Nicolo Cesa-Bianchi; Claudio Gentile; Fabio Vitale; Giovanni Zappella

texts

#
eye 42

#
favorite 0

#
comment 0

We present very efficient active learning algorithms for link classification in signed networks. Our algorithms are motivated by a stochastic model in which edge labels are obtained through perturbations of a initial sign assignment consistent with a two-clustering of the nodes. We provide a theoretical analysis within this model, showing that we can achieve an optimal (to whithin a constant factor) number of mistakes on any graph G = (V,E) such that |E| = \Omega(|V|^{3/2}) by querying...

Source: http://arxiv.org/abs/1301.4767v2

76
76

Sep 21, 2013
09/13

by
Nicolo Cesa-Bianchi; Claudio Gentile; Fabio Vitale; Giovanni Zappella

texts

#
eye 76

#
favorite 0

#
comment 0

Motivated by social balance theory, we develop a theory of link classification in signed networks using the correlation clustering index as measure of label regularity. We derive learning bounds in terms of correlation clustering within three fundamental transductive learning settings: online, batch and active. Our main algorithmic contribution is in the active setting, where we introduce a new family of efficient link classifiers based on covering the input graph with small circuits. These are...

Source: http://arxiv.org/abs/1301.4769v2

51
51

Sep 23, 2013
09/13

by
Nicolo' Cesa-Bianchi; Claudio Gentile; Fabio Vitale; Giovanni Zappella

texts

#
eye 51

#
favorite 0

#
comment 0

We investigate the problem of sequentially predicting the binary labels on the nodes of an arbitrary weighted graph. We show that, under a suitable parametrization of the problem, the optimal number of prediction mistakes can be characterized (up to logarithmic factors) by the cutsize of a random spanning tree of the graph. The cutsize is induced by the unknown adversarial labeling of the graph nodes. In deriving our characterization, we obtain a simple randomized algorithm achieving in...

Source: http://arxiv.org/abs/1212.5637v1

42
42

Sep 21, 2013
09/13

by
Nicolo Cesa-Bianchi; Claudio Gentile; Fabio Vitale; Giovanni Zappella

texts

#
eye 42

#
favorite 0

#
comment 0

We investigate the problem of active learning on a given tree whose nodes are assigned binary labels in an adversarial way. Inspired by recent results by Guillory and Bilmes, we characterize (up to constant factors) the optimal placement of queries so to minimize the mistakes made on the non-queried nodes. Our query selection algorithm is extremely efficient, and the optimal number of mistakes on the non-queried nodes is achieved by a simple and efficient mincut classifier. Through a simple...

Source: http://arxiv.org/abs/1301.5112v1

4
4.0

Jun 29, 2018
06/18

by
Nicolo' Cesa-Bianchi; Claudio Gentile; Yishay Mansour; Alberto Minora

texts

#
eye 4

#
favorite 0

#
comment 0

We study networks of communicating learning agents that cooperate to solve a common nonstochastic bandit problem. Agents use an underlying communication network to get messages about actions selected by other agents, and drop messages that took more than $d$ hops to arrive, where $d$ is a delay parameter. We introduce \textsc{Exp3-Coop}, a cooperative version of the {\sc Exp3} algorithm and prove that with $K$ actions and $N$ agents the average per-agent regret after $T$ rounds is at most of...

Topics: Computing Research Repository, Learning

Source: http://arxiv.org/abs/1602.04741

11
11

Aug 11, 2020
08/20

by
Nicol Cesa-Bianchi; Claudio Gentile; Fabio Vitale; Giovanni Zappella

data

#
eye 11

#
favorite 0

#
comment 0

Source: http://academictorrents.com/details/66ed1109aa9929c9eb1c24516b32955b7150b2f3

3
3.0

Jun 29, 2018
06/18

by
Géraud Le Falher; Nicolò Cesa-Bianchi; Claudio Gentile; Fabio Vitale

texts

#
eye 3

#
favorite 0

#
comment 0

In the problem of edge sign prediction, we are given a directed graph (representing a social network), and our task is to predict the binary labels of the edges (i.e., the positive or negative nature of the social relationships). Many successful heuristics for this problem are based on the troll-trust features, estimating at each node the fraction of outgoing and incoming positive/negative edges. We show that these heuristics can be understood, and rigorously analyzed, as approximators to the...

Topics: Social and Information Networks, Computing Research Repository, Learning

Source: http://arxiv.org/abs/1606.00182

5
5.0

Jun 29, 2018
06/18

by
Claudio Gentile; Shuai Li; Purushottam Kar; Alexandros Karatzoglou; Evans Etrue; Giovanni Zappella

texts

#
eye 5

#
favorite 0

#
comment 0

We investigate a novel cluster-of-bandit algorithm CAB for collaborative recommendation tasks that implements the underlying feedback sharing mechanism by estimating the neighborhood of users in a context-dependent manner. CAB makes sharp departures from the state of the art by incorporating collaborative effects into inference as well as learning processes in a manner that seamlessly interleaving explore-exploit tradeoffs and collaborative steps. We prove regret bounds under various...

Topics: Information Retrieval, Machine Learning, Artificial Intelligence, Statistics, Learning, Computing...

Source: http://arxiv.org/abs/1608.03544

4
4.0

Jun 30, 2018
06/18

by
Noga Alon; Nicolò Cesa-Bianchi; Claudio Gentile; Shie Mannor; Yishay Mansour; Ohad Shamir

texts

#
eye 4

#
favorite 0

#
comment 0

We present and study a partial-information model of online learning, where a decision maker repeatedly chooses from a finite set of actions, and observes some subset of the associated losses. This naturally models several situations where the losses of different actions are related, and knowing the loss of one action provides information on the loss of other actions. Moreover, it generalizes and interpolates between the well studied full-information setting (where all losses are revealed) and...

Topics: Machine Learning, Computing Research Repository, Statistics, Learning

Source: http://arxiv.org/abs/1409.8428