cs.LGFeb 4, 2026

Laws of Learning Dynamics and the Core of Learners

Authors: Inkee Jung, Siu Cheong Lau

Organizations: Department of mathematics, Boston University, Boston, USA.

Abstract

We formulate an algorithm-independent theory of learning dynamics for individual models and ensembles. We establish a conservation law, the vanishing of predictive entropy under successful learning, quantitative entropy and core-expansion bounds, and calibration and finite-sample validation results for identifying reliable predictions. These results motivate a two-generation ensemble that uses Jensen-Shannon (JS) disagreement to route uncertain inputs to specialized learners. CIFAR-10 experiments examine controlled perturbations, distribution shifts, and adversarial attacks. On a heterogeneous test environment, routing improves accuracy over probability averaging while keeping core accuracy near 95%. For adversarial defense, we consider a query-only black-box setting: the attacker can query the overall prediction function but does not know a particular internal decomposition into learners and routing rules. Our current attacks use a fixed-initial-route gradient, which is accurate for a single-step attack when the route remains unchanged, but may deviate from actual multi-step attacks, especially for large perturbations. We evaluate our two-layer defense against this approximation; whether additional adversarially trained layers improve resistance to stronger multi-step attacks remains for future study.

Figures & tables

Explore similar work

Apr 6, 2023

Reliable learning in challenging environments

The problem of designing learners that provide guarantees that their predictions are provably correct is of increasing importance in machine learning. However, learning theoretic guarantees have only been considered in very specific settings. In this work, we consider the design and analysis of reliable learners in challenging test-time environments as encountered in modern machine learning problems: namely adversarial' test-time attacks (in several variations) and natural' distribution shifts. In this work, we provide a reliable learner with provably optimal guarantees in such settings. We discuss practical implementations of the learner and further show that our algorithm achieves strong positive performance guarantees on several natural examples: for example, linear separators under log-concave distributions or smooth boundary classifiers under smooth probability distributions.
Apr 2, 2026

Robust Learning with Optimal Error

We construct algorithms with optimal error for learning with adversarial noise. The overarching theme of this work is that the use of randomized hypotheses can substantially improve upon the best error rates achievable with deterministic hypotheses. - For ηη-rate malicious noise, we show the optimal error is 12⋅η/(1−η)\frac{1}{2} \cdot η/(1-η), improving on the optimal error of deterministic hypotheses by a factor of 1/21/2. This answers an open question of Cesa-Bianchi et al. (JACM 1999) who showed randomness can improve error by a factor of 6/76/7. - For ηη-rate nasty noise, we show the optimal error is 32⋅η\frac{3}{2} \cdot η for distribution-independent learners and ηη for fixed-distribution learners, both improving upon the optimal 2η2 η error of deterministic hypotheses. This closes a gap first noted by Bshouty et al. (Theoretical Computer Science 2002) when they introduced nasty noise and reiterated in the recent works of Klivans et al. (NeurIPS 2025) and Blanc et al. (SODA 2026). - For ηη-rate agnostic noise and the closely related nasty classification noise model, we show the optimal error is ηη, improving upon the optimal 2η2η error of deterministic hypotheses. All of our learners have sample complexity linear in the VC-dimension of the concept class and polynomial in the inverse excess error. All except for the fixed-distribution nasty noise learner are time efficient given access to an oracle for empirical risk minimization.
Jul 22, 2026

Adversarial Frontiers: Minimum-Norm Attack Ensembles for Robustness Evaluation

Adversarial robustness is commonly evaluated with predefined attack ensembles, such as AutoAttack, at a single perturbation budget ε\varepsilon and on a selective choice of perturbation norms. We argue this formulation is fundamentally limited. First, robustness--perturbation curves may intersect or decay at different rates across models, making single-ε\varepsilon rankings unstable. Second, current ensembles provide no evidence of optimality, leaving an unknown gap to worst-case performance. Third, fixed attack configurations provide no systematic control over the trade-off between attack strength and evaluation cost. To address these limitations, we introduce a unified evaluation framework based on a comprehensive pool of minimum-norm attacks and robustness--perturbation curves across ℓ0\ell_0, ℓ1\ell_1, ℓ2\ell_2 and ℓ∞\ell_\infty norms. We define the attack frontier as the worst-case robustness estimate the attack pool produces against a model. We then formalize evaluation as a frontier-approximation problem, constructing minimum-norm attack ensembles, optimized subsets of the comprehensive pool, that approach the frontier under a controllable query budget, with larger budgets monotonically tightening the estimate. Furthermore, we define the defense frontier as the maximum robustness across the model set at each perturbation size. We finally propose the Defense Optimality Index to rank defenses by their gap to the defense frontier, providing a ranking without selecting a reference ε\varepsilon. On CIFAR-10 and ImageNet, our ensembles match or exceed AutoAttack on most defenses at every budget tier, at fixed and controllable query cost, offering practitioners a query-controlled, curve-based alternative to fixed-ε\varepsilon evaluation.