Local large deviations for linear-region growth in random piecewise-linear networks

• URL: http://arxiv.org/abs/2607.07014v1
• Date: Wed, 08 Jul 2026 05:14:19 GMT
• Title: Local large deviations for linear-region growth in random piecewise-linear networks
• Abstract summary: We study a random compositional model for the growth of affine regions in deep piecewise-linear networks.<n>We prove the existence of a submultiplicative pressure for (N_n), yielding exponential upper bounds for both tails of (n-1log N_n)
• Score: 0.0
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: We study a random compositional model for the growth of affine regions in deep piecewise-linear networks. The model is generated by i.i.d.\ perturbations of the symmetric height-one tent map, and the main observable is the number \(N_n\) of affine pieces after \(n\) layers. We prove the existence of a submultiplicative pressure for \(N_n\), yielding exponential upper bounds for both tails of \(n^{-1}\log N_n\). The same argument applies to abstract submultiplicative complexity observables and gives higher-dimensional extensions for convex-polytopal affine-cover counts and worst-line affine-piece counts. Since the true branch count has no matching supermultiplicative inequality, lower bounds require a separate certified construction. We introduce a finite-state defect process that records branches whose future splitting can be guaranteed, and use bridge words to obtain constructive upper-tail lower bounds. In a uniformly favorable small-noise regime, this process is governed by a companion matrix whose Perron root tends to \(2\), implying eventual exclusion of lower tails below \(\log 2-ξ\).

Related papers

• Across the Loss Landscape with Progressive Growth [51.366966420881646]
  We show how grow-and-optimize strategies to train toward flatter regions by viewing growth as progressive relaxation.<n>We empirically validate these predictions in controlled toy basins and in a realistic ResNet/CI-100 setting.<n>Although progressive subspace growth reliably produces flatter solutions, curvature reductions do not universally translate into improved test performance, highlighting subtleties in the flatness-generalization connection.
  arXiv  Detail & Related papers  (2026-08-25T13:50:48Z)
• Neural network realization of binary refinement iterates via a two-chart atlas selector [0.0]
  We show that every compactly supported continuous piecewise linear seed has finite refinement iterates that admit exact ReLU realizations of fixed width and depth growing linearly.<n>The construction also gives exact readout of every continuous piecewise linear circle function satisfying the natural endpoint compatibility condition.
  arXiv  Detail & Related papers  (2026-07-21T14:11:16Z)
• Exact Loop Controllers for ReLU Realization of Homogeneous Curve Refinements [0.0]
  We study homogeneous refinement operators ((V)(t)=sum_jinmathbb ZA_j(Mt-j)), acting on compactly supported continuous piecewise linear curves (:mathbb Rtomathbb Rp), where (Mge2) and only finitely many matrices (A_jinmathbb Rptimes p) are nonzero.<n>We prove that the iterates (Vn) admit exact Re
  arXiv  Detail & Related papers  (2026-05-03T00:44:46Z)
• Regularized Online RLHF with Generalized Bilinear Preferences [68.44113000390544]
  We consider the problem of contextual online RLHF with general preferences.<n>We adopt the Generalized Bilinear Preference Model to capture preferences via low-rank, skew-symmetric matrices.<n>We prove that the dual gap of the greedy policy is bounded by the square of the estimation error.
  arXiv  Detail & Related papers  (2026-02-26T15:27:53Z)
• Entropic Mirror Descent for Linear Systems: Polyak's Stepsize and Implicit Bias [55.72269695392027]
  This paper focuses on applying entropic mirror descent to solve linear systems.<n>The main challenge for the convergence analysis stems from the unboundedness of the domain.<n>To overcome this without imposing restrictive assumptions, we introduce a variant of Polyak-type stepsizes.
  arXiv  Detail & Related papers  (2025-05-05T12:33:18Z)
• Emergent multi-loop nested point gap in a non-Hermitian quasiperiodic lattice [2.518621093955008]
  We propose a geometric series modulated non-Hermitian quasiperiodic lattice model.<n>We show that multiple mobility edges and non-Hermitian point gaps with high winding number can be induced in the system.
  arXiv  Detail & Related papers  (2024-10-06T12:59:14Z)
• Learning with Norm Constrained, Over-parameterized, Two-layer Neural Networks [54.177130905659155]
  Recent studies show that a reproducing kernel Hilbert space (RKHS) is not a suitable space to model functions by neural networks. In this paper, we study a suitable function space for over- parameterized two-layer neural networks with bounded norms.
  arXiv  Detail & Related papers  (2024-04-29T15:04:07Z)
• Stable Nonconvex-Nonconcave Training via Linear Interpolation [51.668052890249726]
  This paper presents a theoretical analysis of linearahead as a principled method for stabilizing (large-scale) neural network training. We argue that instabilities in the optimization process are often caused by the nonmonotonicity of the loss landscape and show how linear can help by leveraging the theory of nonexpansive operators.
  arXiv  Detail & Related papers  (2023-10-20T12:45:12Z)
• Lower Bounds for Learning in Revealing POMDPs [88.23337313766355]
  This paper studies the fundamental limits of reinforcement learning (RL) in the challenging emphpartially observable setting. For emphmulti-step revealing POMDPs, we show that the latent state-space dependence is at least $Omega(S1.5)$ in the sample complexity.
  arXiv  Detail & Related papers  (2023-02-02T18:59:30Z)
• A Sharp Blockwise Tensor Perturbation Bound for Orthogonal Iteration [23.308822706415867]
  We establish blockwise tensor perturbation bounds for the high-order orthogonal iteration (HOOI) We show the upper bounds of mode-$k$ singular subspace estimation are unilateral and converge linearly to a quantity characterized by blockwise errors of the perturbation and signal strength. We prove that one-step HOOI with only a single iteration is also optimal in terms of tensor reconstruction and can be used to lower the computational cost.
  arXiv  Detail & Related papers  (2020-08-06T03:01:28Z)
• Kolmogorov Width Decay and Poor Approximators in Machine Learning: Shallow Neural Networks, Random Feature Models and Neural Tangent Kernels [8.160343645537106]
  We establish a scale separation of Kolmogorov width type between subspaces of a given Banach space. We show that reproducing kernel Hilbert spaces are poor $L2$-approximators for the class of two-layer neural networks in high dimension.
  arXiv  Detail & Related papers  (2020-05-21T17:40:38Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.