Abstract Fourier-based learning algorithms rely on being able to effificiently fifind the large coeffificients of a function’s spectral representation. In this paper, we introduce and analyze techniques for fifinding large coeffificients. We show how a previously introduced search technique can be generalized from the Boolean case to the real-valued case, and we apply it in branch-and-bound and beam search algorithms that have signifificant advantages over the best-fifirst algorithm in which the technique was originally introduced