We prove that the capacity of the binary deletion channel satisfies C(d)\le (1-d)/4 for every 13/20\le d<1. The proof describes the output from right to left, using a six-bit context to assign a description length. We bound the increase in expected description length minus output entropy when one input bit is added. A relative-entropy identity reduces this bound to finitely many linear inequalities. A potential on input windows of length 26 makes the inequalities telescope, giving a bound for every input word. Deletion composition extends the result from d=13/20 to all larger deletion probabilities. We also obtain finite-block bounds on mutual information and decoding error, with explicit O(\log n/n) corrections. The finite certificate is checked using exact integer arithmetic, and the proof is formalized end to end in Lean.
2025
Monomial Matrix Relocation on the Loss Function Level-Set of Feedforward Neural Networks
Ozgur Soysal, Arda Ozdemir, Yigit Yildirim, and 1 more author
In 2025 Asia Pacific Signal and Information Processing Association Annual Summit and Conference (APSIPA ASC), Sep 2025
Deep neural networks often achieve state-of-the-art performance by relying on substantial parameter counts, which can make training and deployment costly in memory and compute. Pruning aims to reduce this redundancy by removing parameters that contribute little to the model’s predictions. This paper proposes a novel mid-training pruning scheme that uses the Fisher Information Matrix (FIM) and gradient directions to identify removable parameters while training is still ongoing. Rather than pruning only after convergence, this method interleaves optimization with pruning by estimating parameter importance via efficient estimation of an augmented FIM and progressively masks low-score weights as learning continues. This produces a sparsity trajectory that adapts to the model’s evolving sensitivity, enabling earlier and more aggressive compressions with reduced performance loss. This paper benchmarks the approach against unpruned baselines, evaluating final accuracy, training stability, and finds that augmented FIM-based mid-training pruning better preserves accuracy.
