#01Oct 30, 2026
cs.CV
A Better Critic Matters for Distribution Matching Distillation
Zongze Wu, Xianbang Wang, Zhengyang Geng and 5 more
Distribution Matching Distillation (DMD) trains a few-step student using the difference between a teacher's score and an online critic's estimate of the student distribution's score. We investigate what the critic needs, in capacity and in information, to provide a reliable training signal. On the capacity side, controlled experiments across seven SiT model sizes on ImageNet show that increasing teacher size while keeping a small critic fixed can degrade student quality and cause training collapse. Scaling the critic alongside the teacher, a strategy we call joint scaling, prevents collapse in our experiments and allows the student to benefit from larger teachers. On the information side, rather than forcing the critic to model a step-agnostic mixture of student outputs, we introduce a step-aware critic (STAC) that conditions on the student's generation step to estimate step-specific scores. Together, joint scaling and STAC consistently improve few-step distillation across class-conditional ImageNet generation, text-to-image generation with SDXL and FLUX.2, and text-to-video generation with Wan2.1.
#02Oct 30, 2026
cs.LG
Instance-dependent sequential limits as an exact information ledger
Akshay Balsubramani
Instance-dependent limits for bandit regret, sequential tests, best-arm identification and Markov decision processes are proved by one chain. It runs from a divergence decomposition through data processing to a statistic, a testing step that turns a class guarantee into a requirement on the history, and optimization over alternatives and allocations. Only the first step is an identity. This work writes the chain as an exact ledger. By the chain rule, data processing loses exactly a conditional divergence, which vanishes for arms in natural exponential families at the per-arm counts and reward sums. A one-parameter family of martingale identities extends the decomposition to every tilt between two instances. The classical limits follow by relaxations with named defects. All defects but the asymptotic step's can be computed from an algorithm's own runs, the uniform quantification's only when the class guarantee is a number. On seven published sources, from movie ratings to engine replacement, the ledger locates the difference between standard algorithms and the classical limits. For identification among trained models and for Wald's test the largest term is usually the uniform quantification's.
#03Oct 30, 2026
cs.LG
Gradient Descent on Two ReLU Neurons: Global Landscape and Bifurcation Dynamics
Binghua Li, Mengzhe Li, Denny Wu and 1 more
Understanding how gradient descent learns features remains a central challenge in neural network theory. We study this question in a minimal multi-index setting that already exhibits rich multi-phase gradient dynamics: a well-specified two-neuron ReLU teacher-student model under isotropic Gaussian inputs, trained by population gradient flow from small initialization. We show that the dynamics are organized by two directions: the "easy" bisector direction, which carries the leading signal, and the "hard" splitting direction, which governs specialization. To characterize the loss structure and learning behavior, we analyze the population squared-loss landscape and show that every critical point with both student weights nonzero is either a global minimum or a saddle. We then track the gradient-flow trajectory, showing that student neurons first collapse toward a bisector saddle before escaping and specializing to teacher neurons. Our results provide both a landscape and dynamics account of the multi-phase symmetry-breaking behavior that arises in a simple multi-index model and under standard algorithmic and architectural choices.
#04Oct 30, 2026
math.ST
On Statistical-Computational Gaps in Graph Combinatorial Testing Problems
Ikjun Choi, Pratik Patil, Alessandro Rinaldo
We study high-dimensional graph combinatorial hypothesis testing problems in which a signal is supported on the edge set of an unknown subgraph drawn from a class invariant under vertex relabeling. For Gaussian observations, we characterize sharp statistical and computational thresholds (at polynomial order) for the signal magnitude required for strong detection across various combinatorial graph alternatives. Our analysis is based on bounding the second moments of the full and low-degree likelihood ratios in terms of the overlap of two independent latent structures and comparing the resulting lower bounds with scan, average, and coordinatewise maximum tests. Under an appropriate low-degree conjecture for computational hardness, we obtain planted-clique thresholds matching those known for Gaussian submatrix detection and identify new statistical-computational gaps for multiple planted cliques and hypercliques, thick cycles and thick paths. We also establish a novel transfer principle across natural exponential family observation models: matching the one-coordinate chi-square divergence preserves full likelihood-ratio second moments exactly and makes low-degree second moments equivalent up to constant factors under a degree condition. Under local regularity, we obtain corresponding testing upper bounds in terms of an effective signal strength. When these upper and lower bounds match, they yield universal threshold scales in the local alternative regime. As a consequence, statistical-computational gaps for planted-clique detection in Erdős--Rényi settings can be deduced from the Gaussian model.
#05Oct 30, 2026
math.OC
Near-Optimal Second-Order Convex Finite-Sum Optimization under Individual Smoothness
Xinliang Zhang, Lesi Chen, Zonghan Li and 1 more
We study the stochastic second-order oracle complexity of solving smooth convex finite-sum optimization with $n$ components. Very recently, Tsedenov \& Kovalev (2026) showed that the minimax optimal complexity under averaged smoothness and convexity is $\tildeΘ(n + n^{6/7} ε^{-2/7})$ by establishing nearly matching upper and lower bounds. In this paper, we show that individual smoothness and convexity provably enable further acceleration, where the lower complexity bound is $Ω(n+ n^{5/7} ε^{-2/7})$ under this stronger assumption. Then, by establishing a novel second-order self-bounding inequality, we design a new Taylor-corrected lazy Newton method, which can lead to a better complexity of $\tilde{\mathcal{O}}(n + n^{5/7} ε^{-2/7})$ by applying the optimal Monteiro-Svaiter acceleration, matching our lower bound up to only logarithmic factors.