Skip to main content
Share Your Experience: Take the 2024 Developer Survey

Questions tagged [online-learning]

The tag has no usage guidance, but it has a tag wiki.

Filter by
Sorted by
Tagged with
0 votes
0 answers
64 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 ...
Katan katalan's user avatar
0 votes
0 answers
51 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 ...
white's user avatar
  • 1
1 vote
0 answers
42 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 ...
Amin's user avatar
  • 111
2 votes
0 answers
102 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 ...
Dudley Brooks's user avatar
2 votes
1 answer
109 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 ...
Aryeh's user avatar
  • 10.6k
1 vote
0 answers
100 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 ...
gradstudent's user avatar
  • 1,453
0 votes
1 answer
227 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 ...
zdm's user avatar
  • 325
3 votes
1 answer
223 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 ...
gradstudent's user avatar
  • 1,453
3 votes
1 answer
71 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 ...
SVN's user avatar
  • 59
3 votes
1 answer
480 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 ...
gradstudent's user avatar
  • 1,453
1 vote
1 answer
134 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 ...
rajatsen91's user avatar
2 votes
1 answer
468 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 ...
Daniel's user avatar
  • 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 ...
nomad's user avatar
  • 211
3 votes
1 answer
590 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 ...
Aryeh's user avatar
  • 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 ...
Riccardo T.'s user avatar
19 votes
1 answer
921 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 ...
Martin Pál's user avatar
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 ...
Warren Schudy's user avatar
16 votes
1 answer
1k 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-...
Aaron Roth's user avatar
  • 9,900
6 votes
2 answers
406 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?
Parasaran's user avatar
19 votes
2 answers
607 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 ...
Noam's user avatar
  • 9,369
10 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 ...