Information-Computation Gap
The gap between information-theoretically optimal performance and performance achievable in polynomial time. It indicates that the divide between statistical optimality and computational feasibility arises from the intrinsic computational hardness of the problem itself.
Timeline (last 90 days)
There is an essential separation between the information-theoretically optimal regret Õ(md+k) and the regret achievable in polynomial time; this gap is inherent to computational complexity rather than a shortcoming of algorithm design.
Information-theoretic lower bounds characterize the best performance achievable by any algorithm (even exponential-time) without computational resource constraints, corresponding in this problem to Õ(md+k); computational lower bounds, by contrast, assume the algorithm must run in polynomial time, and the resulting bounds are usually larger.
All Facts (2)
There is an essential separation between the information-theoretically optimal regret Õ(md+k) and the regret achievable in polynomial time; this gap is inherent to computational complexity rather than a shortcoming of algorithm design.
50%UnverifiedInformation-theoretic lower bounds characterize the best performance achievable by any algorithm (even exponential-time) without computational resource constraints, corresponding in this problem to Õ(md+k); computational lower bounds, by contrast, assume the algorithm must run in polynomial time, and the resulting bounds are usually larger.
50%