Suppose are input bits (i.e. 0 or 1) at time t, and is the output bit. You are given samples for . You know that is the OR (or disjunction) of a subset of . For example , . You want to use online learning to learn the function that maps the inputs to . At each time , you will try to predict the output given the input . Every time you make a mistake in your prediction, I will charge you $1. is the OR (or disjuction) of exactly values among . I am free to choose the input samples . I will first ask you for the output . If you are wrong, I will tell the correct value of and charge you $1. How will you minimize your loss if I play optimally to maximize your minimum loss? What is that minimum loss? We need the optimal online learning algorithm.
- Via Subhashini V