Questions tagged [online-learning]
The online-learning tag has no usage guidance, but it has a tag wiki.
21 questions
0
votes
0
answers
80
views
Why do we use Hoeffding inequality in UCB approach to drive the confidence set in multi-armed bandit problem?
In UCB algorithm, to drive the confidence set for unknown parameters we use Hoeffding inequality. I am wondering why we don't use Normal distribution instead which is much simpler to work with. Based ...
0
votes
0
answers
60
views
The complexity order of regret (especially in online reinforcement learning)?
In online reinforcement learning theory, how to judge the complexity order of regret, if there are two or more terms in there?
For example, the state space is $X$, the action space is $A$, the episode ...
- 1
1
vote
0
answers
45
views
What is the meaning of loss in online convex optimization?
I am studying online convex optimization, and it is stated that when we make a decision, we observe loss corresponding to our decision. In some problems like multi-armed bandit problems, we know the ...
- 111
2
votes
0
answers
105
views
Online *detailed* tutorials about Komogorov Complexity
I'm a private math tutor who also tutors some theoretical CS. Last semester I had a student who needed tutoring in Kolmogorov Complexity. I told her that I only know about Kolmogorov Complexity, but ...
2
votes
1
answer
149
views
Bayes-consistent cost-sensitive classification
In cost-sensitive classification,
we have a confusion (or cost) matrix
$C$, where $C(i,j)$ is the cost incurred
for predicting label $i$ when nature
specifies $j$. The costs are non-negative,
but no ...
- 10.6k
1
vote
0
answers
106
views
What is the state of the art in first order stochastic convex optimization?
What is the optimally fastest convex risk minimizing algorithm which only uses a stochastic first order oracle? Is this SGD?
What is the optimally fastest convex function minimizing algorithm which ...
- 1,453
0
votes
1
answer
243
views
A Simple Auction Game
You are playing the following game.
You have a budget of $B$ dollars. There are $n$ days. Every day $d$, you have to make a bid $b_d\geq0$ that does not exceed your budget. After making the bid, a ...
- 325
3
votes
1
answer
225
views
About estimating escape time of gradient Langevin dynamics
I am trying to understand the argument in the proof of Lemmma 6.3 (page 18) of this paper https://arxiv.org/abs/1902.08179. Let me summarize the conceptual crux of the argument here using a slightly ...
- 1,453
3
votes
1
answer
82
views
Does one player best responding to sample from a mixed strategy, and the other player minimizing regret converge to a Nash eq in a zero sum game?
It is well-known that in a $2$-player zero sum game if one player plays a regret minimizing mixed strategy, and the other player best-responds at each round to that mixed strategy, we are guaranteed ...
- 59
3
votes
1
answer
540
views
Rademacher complexity beyond the agnostic setting
The way I know of to bound generalization error by Rademacher complexity is Theorem 2.4 in this lecture notes, http://ttic.uchicago.edu/~tewari/lectures/lecture9.pdf. Here the quantity on the LHS that ...
- 1,453
1
vote
1
answer
135
views
Average Regret Bounds for Linear Stochastic Bandits
I am reading this paper on linear stochastic bandits :
http://papers.nips.cc/paper/4417-improved-algorithms-for-linear-stochastic-bandits.pdf
All the results are stated in a high-probability ...
- 245
2
votes
1
answer
482
views
Follow the Perturbed Leader for nonlinear cost functions
The famous FTPL algorithm [1] is analyzing linear cost function. Is there any generalized proof for nonlinear functions known?
Note that in the last paragraph of [1] it says "It would be great to ...
- 749
1
vote
0
answers
237
views
Automatically Adapting Forgetting Factor for Online EM
I've been reading some interesting papers recently on methods for automatically and adaptively setting the learning rate in stochastic gradient descent (SGD). In particular, "No more pesky learning ...
- 211
3
votes
1
answer
641
views
Online to batch sample complexity
It is well known that a mistake bound can be converted to a PAC bound. I know how to prove a sample complexity of
$$ O( (1/\epsilon)[M + \log(M/\delta)] ), $$
where $M$ is an upper bound on the number ...
- 10.6k
-3
votes
1
answer
226
views
Which algorithm for a project about online machine learning?
I have a basic understanding of how machine learning works, but my knowledge isn't enough in order to develop a personal project I would like to start.
I want to develop a system based on online ...
- 103
19
votes
1
answer
924
views
The Warren Buffett Problem
Here is an abstraction of an online learning / bandit problem that I've been working on in the summer. I haven't seen a problem like this before, and it looks quite interesting. If you know of any ...
- 591
20
votes
1
answer
431
views
What are the best possible time/error tradeoffs for approximate solution of linear programs?
For concreteness consider the LP for solving a two-player zero-sum game where each player has $n$ actions. Suppose each entry of the payoff matrix $A$ is at most 1 in absolute value. For simplicity ...
- 1,874
16
votes
1
answer
2k
views
Separation between coarse correlated equilibria and correlated equilibria
I am looking for examples of techniques for proving price of anarchy bounds that have the power to separate the price of anarchy over coarse correlated equilibria (the limiting set of no-external-...
- 9,910
6
votes
2
answers
415
views
Online learning: Perceptron updates
It seems that the perceptron updates come from some notion of primal-dual updates for convex programs. Can anyone explain how this is true or point to relevant literature?
- 69
19
votes
2
answers
611
views
Internal Regret in Online Convex Optimization
Zinkevich's "online convex optimization" ( http://www.cs.cmu.edu/~maz/publications/ICML03.pdf ) generalizes "regret minimization" learning algorithms from a linear settings to a convex setting and ...
- 9,389
11
votes
5
answers
3k
views
What are good references on understanding online learning?
Specifically, I'm asking for resources to learn about machine learning systems that can update their respective belief networks (or equivalent) during operation. I've even run across a few, though I ...