A function ( f: \mathbb{F}_2^n \to \mathbb{R}) is said to be ( s)-Fourier sparse if its Fourier expansion contains at most ( s) nonzero coefficients. In general, the existence of a sparse representation in the Fourier basis serves as a key enabler for the design of efficient learning algorithms. However, most existing techniques assume prior knowledge of the function's Fourier sparsity, with algorithmic parameters carefully tuned to this value. This motivates the following decision problem: given ( s > 0), determine whether a function is ( s)-Fourier sparse. In this work, we study the problem of tolerant testing of Fourier Sparsity for real-valued functions over ( \mathbb{F}_2^n), accessed via oracle queries. The goal is to decide whether a given function is close to being ( s)-Fourier sparse or far from every ( s)-Fourier sparse function. Our algorithm provides an estimator that, given oracle access to the function, estimates its distance to the nearest ( s)-Fourier sparse function with query complexity ( \widetilde{O}(s)), for constant accuracy and confidence parameters. A key structural ingredient in our analysis is a new spectral concentration result for real-valued functions over ( \mathbb{F}_2^n) when restricted to small-dimensional random affine subspaces. We further complement our upper bound with a matching lower bound of ( \Omega(s)), establishing that our tester is optimal up to logarithmic factors.

A recent trend in online algorithms has seen the use of future predictions generated by ML techniques to bypass pessimistic worst-case lower bounds.

We address the general task of learning with a set of candidate models that is too large to have a uniform convergence of empirical estimates to true losses. While the common approach to such challenges is SRM (or regularization) based learning algorithms, we propose a novel learning paradigm that relies on stronger incorporation of empirical data and requires less algorithmic decisions to be based on prior assumptions. We analyze the generalization capabilities of our approach and demonstrate its merits in several common learning assumptions, including similarity of close points, clustering of the domain into highly label-homogeneous regions, Lipschitzness assumptions of the labeling rule, and contrastive learning assumptions. Our approach allows utilizing such assumptions without the need to know their true parameters a priori.

Interactive submodular set cover is an interactive variant of submodular set cover over a hypothesis class of submodular functions, where the goal is to satisfy all sufficiently plausible submodular functions to a target threshold using as few (cost-weighted) actions as possible. It models settings where there is uncertainty regarding which submodular function to optimize. In this paper, we propose a new extension, which we call smooth interactive submodular set cover, that allows the target threshold to vary depending on the plausibility of each hypothesis. We present the first algorithm for this more general setting with theoretical guarantees on optimality. We further show how to extend our approach to deal with real-valued functions, which yields new theoretical results for real-valued submodular set cover for both the interactive and non-interactive settings.

Motivated by learning theory, Aaronson et al. introduced many (weaker) learning models: the

A recent trend in online algorithms has seen the use of future predictions generated by ML techniques to bypass pessimistic worst-case lower bounds.

For a range of activation functions, including ReLUs, we establish super-polynomial Statistical Query (SQ) lower bounds for this learning problem.

Eq. 7 implies that gradient operator is Below we supplement the Lemma A.1 used to prove Theorem 1. ( j 1) Jacobian matrix, the second equality is due to the induction hypothesis, and the third equality is an adoption of chain rule. Then by induction, we can conclude the proof. For a sake of clarity, we first introduce few notations in algebra and real analysis. Definition B.2. (Differential Operator) Suppose a compact set Definition B.4. (F ourier Transform) Given real-valued function Definition B.5. (Convolution) Given two real-valued functions Before we prove Theorem 2, we enumerate the following results as our key mathematical tools: First of all, we note the following well-known result without a proof. Lemma B.2. (Stone-W eierstrass Theorem) Suppose A C ( X, R) is a unital sub-algebra which separates points in X .