near-optimal

Definition

A claim that a method comes within a small factor of a proven lower bound, rather than being exactly best possible. It is a theory word: it presupposes that someone has established what optimal even means for the resource in question. When you see it, the first question is which resource is being bounded — space, time, sample complexity, regret — because near-optimal in one dimension often means clearly suboptimal in another.