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?