We study the relationship between gradient-based optimization of parametric models (e.g., neural networks) and optimization of linear combinations of random features. Our main result shows that if a parametric model can be learned using mini-batch stochastic gradient descent (bSGD) without making assumptions about the data distribution, then with high probability, the target function can also be approximated using a polynomial-sized combination of random features. The size of this combination depends on the number of gradient steps and numerical precision used in the bSGD process. This finding reveals fundamental limitations of distribution-free learning in neural networks trained by gradient descent, highlighting why making assumptions about data distributions is often crucial in practice. Along the way, we also introduce a new theoretical framework called average probabilistic dimension complexity (adc), which extends the probabilistic dimension complexity developed by Kamath et al. (2020). We prove that adc has a polynomial relationship with statistical query dimension, and use this relationship to demonstrate an infinite separation between adc and standard dimension complexity.

Data attribution methods aim to answer useful counterfactual questions like "what would a ML model's prediction be if it were trained on a different dataset?" However, estimation of data attribution models through techniques like empirical influence or "datamodeling" remains very computationally expensive. This causes a critical trust issue: if only a few computationally rich parties can obtain data attributions, how can resource-constrained parties trust that the provided attributions are indeed ``good,'' especially when they are used for important downstream applications (e.g., data pricing)? In this paper, we address this trust issue by proposing an interactive verification paradigm for data attribution. An untrusted and computationally powerful Prover learns data attributions, and then engages in an interactive proof with a resource-constrained Verifier. Our main result is a protocol that provides formal completeness, soundness, and efficiency guarantees in the sense of Probably-Approximately-Correct (PAC) verification (Goldwasser et al., 2021). Specifically, if both Prover and Verifier follow the protocol, the Verifier accepts data attributions that are $\varepsilon$-close to the optimal data attributions (in terms of the Mean Squared Error) with probability $1-\delta$. Conversely, if the Prover arbitrarily deviates from the protocol, even with infinite compute, then this is detected (or it still yields data attributions to the Verifier) except with probability $\delta$. Importantly, our protocol ensures the Verifier's workload, measured by the number of independent model retrainings it must perform, scales only as $O(1/\varepsilon^2)$; i.e., independently of the dataset size. At a technical level, our results apply to efficiently verifying any linear function over the boolean hypercube computed by the Prover, making them broadly applicable to various attribution tasks.

Designing computationally efficient algorithms in the agnostic learning model (Haussler, 1992; Kearns et al., 1994) is notoriously difficult. In this work, we consider agnostic learning with membership queries for touchstone classes at the frontier of agnostic learning, with a focus on how much computation can be saved over the trivial run-time of $2^n$. This approach is inspired by and continues the study of “learning with nontrivial savings” (Servedio and Tan, 2017). To this end, we establish multiple agnostic learning algorithms, highlighted by: An agnostic learning algorithm for circuits consisting of a sublinear number of gates, which can each be any function computable by a sublogarithmic degree $k$ polynomial threshold function (the depth of the circuit is bounded only by size). This algorithm runs in time $2^{n -s(n)}$ for $s(n) \approx n/(k+1)$, and learns over the uniform distribution over unlabelled examples on $\{0,1\}^n$. An agnostic learning algorithm for circuits consisting of a sublinear number of gates, where each can be any function computable by a $\sym^+$ circuit of subexponential size and sublogarithmic degree $k$. This algorithm runs in time $2^{n-s(n)}$ for $s(n) \approx n/(k+1)$, and learns over distributions of unlabelled examples that are products of $k+1$ \textit{arbitrary and unknown} distributions, each over $\{0,1\}^{n/(k+1)}$ (assume without loss of generality that $k+1$ divides $n$). Furthermore, we apply our new agnostic learning algorithms for these classes to also obtain algorithms for randomized compression, exact learning with membership and equivalence queries, and distribution-independent PAC-learning with membership queries. Our core technique, which may be of independent interest, remixes the learning from natural proofs paradigm (Carmosino et al. 2016, 2017), so that we can tolerate concept classes fundamentally different than $\AC^0[p]$, and achieve fully agnostic learning. We make use of communication-complexity-based natural proofs (Nisan, 1993), rather than natural proofs of Razborov (1987) and Smolensky (1987) for $\AC^0[p]$.

Recently, multimodal machine learning has enjoyed huge empirical success (e.g. GPT-4). Motivated to develop theoretical justification for this empirical success, Lu (NeurIPS ’23, ALT ’24) introduces a theory of multimodal learning, and considers possible separations between theoretical models of multimodal and unimodal learning. In particular, Lu (ALT ’24) shows a computational separation, which is relevant to worst-case instances of the learning task. In this paper, we give a stronger average-case computational separation, where for "typical" instances of the learning task, unimodal learning is computationally hard, but multimodal learning is easy. We then question how "natural" the average-case separation is. Would it be encountered in practice? To this end, we prove that under basic conditions, any given computational separation between average-case unimodal and multimodal learning tasks implies a corresponding cryptographic key agreement protocol. We suggest to interpret this as evidence that very strong computational advantages of multimodal learning may arise infrequently in practice, since they exist only for the "pathological" case of inherently cryptographic distributions. However, this does not apply to possible (super-polynomial) statistical advantages.

Carmosino et al. (2016) demonstrated that natural proofs of circuit lower bounds for $Λ$ imply efficient algorithms for learning $Λ$-circuits, but only over \textit{the uniform distribution}, with \textit{membership queries}, and provided $\AC^0[p] \subseteq Λ$. We consider whether this implication can be generalized to $Λ\not\supseteq \AC^0[p]$, and to learning algorithms which use only random examples and learn over arbitrary example distributions (Valiant's PAC-learning model). We first observe that, if, for any circuit class $Λ$, there is an implication from natural proofs for $Λ$ to PAC-learning for $Λ$, then standard assumptions from lattice-based cryptography do not hold. In particular, we observe that depth-2 majority circuits are a (conditional) counter example to the implication, since Nisan (1993) gave a natural proof, but Klivans and Sherstov (2009) showed hardness of PAC-learning under lattice-based assumptions. We thus ask: what learning algorithms can we reasonably expect to follow from Nisan's natural proofs? Our main result is that all natural proofs arising from a type of communication complexity argument, including Nisan's, imply PAC-learning algorithms in a new \textit{distributional} variant (i.e., an ``average-case'' relaxation) of Valiant's PAC model. Our distributional PAC model is stronger than the average-case prediction model of Blum et al. (1993) and the heuristic PAC model of Nanashima (2021), and has several important properties which make it of independent interest, such as being \textit{boosting-friendly}. The main applications of our result are new distributional PAC-learning algorithms for depth-2 majority circuits, polytopes and DNFs over natural target distributions, as well as the nonexistence of encoded-input weak PRFs that can be evaluated by depth-2 majority circuits.