COLT 2011 Accepted Papers

The list of accepted papers for COLT 2011 are available here. I will update this post by adding related papers to my own research soon

Online Learning with a Partially Observable Future Cost

The main idea in proving regret bound for the Follow the Perturbed Leader (FPL) algorithm is as follows: first, we define the hypothetical leader which knows the future cost vector before prediction on round which attains zero regret. Then we can prove that by adding some perturbation to the current cumulative cost vectors till time the Player gets regret bound. Now the question is that if we have some partial information about future cost or we are allowed to query some information about the next round's cost, can we design algorithms with improved regret bounds. This problem is tackled down in two recent papers. In Online Learning with Prior Knowledge the authors proposed an algorithm which utilize such information as a kind of prior information. Recently in Online Learning with Queries a variant of Weighted Majority Algorithm with capability of querying limited information about the future cost vector is proposed.

No Free Experts, Hedging on Cost

Consider the following setting for learning from expert advice. In each round of the game between Player and Adversary, the player can ask for experts' suggestions but by paying some amount of money determined by each expert at the beginning of the round. In other words, at the beginning of each trial, the Player gets a cost vector which determines the cost of querying each expert for that round. Also let assume that Player has a budget constraint which would be for each round or long term constraint defined for all rounds. The goal of Player is to attain nontrivial regret bound under the budget constraint. Formally the Player tries to minimize and simultaneously satisfies the constraint .

The mentioned constraint is a long term constraint and we can alternatively define round based constraint as:.

Online Learning with Unbounded and Non-convex Loss Function

Actually this a a new thought attracted me. In all of the online learning algorithms, we assume that the loss function is bounded. Also, if we do not use perturbation in our algorithm, the loss function should be convex in first argument. So the question is that is there any way to relax these assumptions, more specifically

1) How can we get rid of boundedness constraint?

2) How can we use non-convex loss function in learning?

The motivation for second problem is well known 0-1 loss function. We know by adding some randomization in our prediction, this loss function behaves like absolute loss function. So, can we generalize this idea to other nonconvex or maybe some other soft constraints? Are there any real applications for such loss functions?

I will post more info regarding this problem when I rich my knowledge.

Betting on Permutation using Expert Advices

Today I had a chance to read original paper of Hedge algorithm. The motivating problem was about betting on horse races. A gambler, decides to allow a group of his friends to make bets on his behalf and the question is how to combine the decisions of friends. This is exactly the setting of learning using expert advice. After reading, I thought about betting languages. Betting only on one horse as a winner is a special case of betting languages. Permutation betting and betting on a interval are another languages for betting. In permutation betting you bet on a permutation of all horses and in interval betting you bet on subset of size k of horses for first k ranks. Another betting language maybe be considered as pairwise betting. In this type of betting you bet on a mapping between horses and ranks. Now the question is that can we apply Hedge or other types of algorithms for learning betting of types of mentioned languages?

Model selection in Online learning

Reading the paper "On the Generalization Ability of On-Line Learning
Algorithms", I felt that i.i.d assumption is not a big deal. Recently I've read this excellent post Adaptivity in online models? and tuned myself. The point is that i.i.d assumption is not just for ensuring generalization ability of learning. Another usefulness of i.i.d assumption is in model selection. In regularized error minimization for machine learning algorithms we have a trading parameter between error and regularization. Having i.i.d assumptions for samples, we can employ cross validation method to find a value for his parameter. In other words, if we want to choose an appropriate value for a regularization parameter we can split the samples and use a validation set to find a good approximation of parameter.

So, the question is how can we choose such parameters in online learning algorithms having no i.i.d assumption and not having all samples in advance. At the first glance, adaptive adjustment of parameter is obvious solution. Are there other methods, or can current methods be improved considering the inherent limitations of online learning setting?

Theories in Statistical learning theory

In my view, two main important questions regarding learning algorithms are generalization ability and stability analysis. When I have started working on learning algorithms, I asked myself this question: "Why can a learning algorithm predict future samples only by finding a classifier which minimizes the empirical error on training samples?". I have encountered a lot of theories and concepts looking for a answer to this question and I wanna deep my understanding of them. Please note that all of following concepts are not exactly related to answering the mentioned question but somehow related to it.

1) No free launch theorem
2) PAC learning (realizable and agnostic)
3) Occam learning
4) VC dimension
5) Covering numbers
6) Growth functions
7) Rademacher complexity

Wait for my future post for a survey of these concepts.