Compressive algorithmic randomness: Gibbs-randomness proposition for massively energy efficient deep learning

Figure: Dual Tomographic Compression
Performance, Süzen, 2025.

Preamble

Randomness is elusive and its probably one of the outstanding concepts for human scientific endeavour, along with gravity. Kolmogorov complexity, appears to be so novel in trying to answering "what is randomness?". The idea that the length of the smallest model that can generate the random sequence determines its complexity was a turning point in history of science. Similarly, it implies choosing the simplest model for explaining a phenomenon. That's why Kolmogorov's work was also supported by the ideas of Solomonoff and Chaitin. A recent work, explores this algorithmic information from compression perspective with Gibbs entropy.

A strange tale of path from applied research to fundamental proposition. 

During study of model compression algorithm development, I have noticed an amazing behaviour that information, entropy and compression over compression process have a more in depth. 

New concepts in compression and randomness via train-compress cycles

Here, we explain the new concepts for both deep learning model compression and on the interplay between compression and algorithmic randomness.

Inverse compressed sensing (iCS): Normally CS procedure is applied to reconstruct an unknown signal with fewer measurements. In the case of deep learning train-compress, weights are known at one point in the training cycle. If we create hypothetical measurements, using CS formulations, we can reconstruct weights sparse projection. 

Dual Tomographic Compression: Applying iCS for the input and output of neuronal level, layer-wise, simultaneously.  

Weight rays:  An output reconstructed vector out of DTC; weights given sparsity level, though they are not generated in isolation but within train-compress cycle.

Gibbs randomness proposition : An extension of Kolmogorov complexity for a compression process. That, directed randomness is the same as complexity reduction, i.e., compression. 

Conclusion 

A new technique called DTC can be used to train deep learning with model compression on the fly. This gives rise to massively energy efficient deep learning, reaching almost ~98% reduction in energy use.  Moreover, the technique also demonstrated an extended version of Kolmogorov complexity. 

Further reading 

Paper & codes are released :

• Paper: Gibbs randomness-compression proposition: An efficient deep learning 
  arXiv:2505.23869 (2025)
• Codes: https://github.com/msuzen/research/tree/main/gibbs-randomness-compression 

Cite as 

 @misc{suzen25car, 

     title = {Compressive algorithmic randomness: <br>Gibbs-randomness proposition for massively energy efficient deep learning}, 

     howpublished = {\url{ https://science-memo.blogspot.com/2025/06/compressive-algorithmic-randomness.html}}, 

     author = {Mehmet Süzen},

     year = {2025}

}  

Ultimate physical limit of data storage: Connecting Bekenstein Bound to Landauer Principle

Preamble 

Bekenstein's Information
(Wikipedia)

Black holes are not too esoteric anymore after LIGO's success and successful imaging efforts. Their entropy behaves much different than the entropy of an ordinary matter. This leads to incredible discovery of so called holographic principle. The principle stating that we live on a projection of higher-dimensional manifestation of universe. On the other hand, Landauer made silently a discovery on energy expenditure of keeping information processing reversible. Similar bound put forward by Bekenstein for black holes made Landauer-Bekenstein bound for quantum gravity a natural avenue to study. 

What is the Bekenstein Bound?

Basically, this puts limits the size of a black hole, via its entropy bound. Essentially it states that, entropy of a black hole $S$ is bounded with the radius of the black hole $R$ and Energy $E$, other constants being 1, 

$$S \le R \dot E$$

What is Landauer Principle?

A limit on any process wants to delete 1 bit of information,  has to dissipate energy proportional to its temperature, 

$$ E \ge T ln 2$$ 

Again we made the constants to 1. 

Physical limit of data storage: 1 BekensteinBytes

Using both Bekenstein bound and Landauer principle one can compute the a physical limit for a data storage on a unit sphere,

$$S \sim T$$

If we scaled this with inverse of Planck area $\ell_{p}$; One bit of information proportional to Planck area and maximum attainable temperature $10^{32}$ K is scaled with this. The final value corresponds to $\approx 10^{100}$ bits. This again corresponds to about 10 Giga-Quetta-Quatta-Quatta bytes (1 Quetta byte is $10^{30}$ bytes). 

At this point in time, we can propose that $10^{100}$, would be to call 1 BekensteinBytes.  However with more fine-grain computations, the number may change. Our purpose here is to give a very rough idea about the scale of ultimate physical limitations of data storage in BekensteinBytes.

Bekenstein Information Conjecture : One cannot compress more than 1 BekensteinBytes on a smallest patch of space.

Outlook

An interesting connections in quantum gravity and computation, provides certain physical limitations on how much information we can be stored at a given unit space.  We called this Bekenstein Information Conjecture. 

Further reading

•  Insights into Bekenstein entropy with an intuitive mathematical definitions: A look into Thermodynamics of Black-holes (2023) 
• Bekenstein Bound (Wikipedia)
• Landauer's Principle (Wikipedia)
• On the relation between Bekenstein entropy and Landauer’s principle,  D. Song (2024) DOI
• Planck Scales (Wikipedia)
• Metric Prefixes (Wikipedia)

Cite as 

 @misc{suezen25datalimit, 

     title = {Ultimate physical limit of data storage: Connecting Bekenstein Bound  to Landauer Principle}, 

     howpublished = {\url{https://science-memo.blogspot.com/2025/04/ultimate-physical-limit-of-data-storage.html}}, 

     author = {Mehmet Süzen},

     year = {2025}

}  

Imputation of missing data: Recursive 1D discrete KNN algorithm

Any generated data is often have missing components or values. Probably, the most common occurrence manifest in time series data where there is no value available on the given time point, hence a NaN is placed in general (or NA in R). There is a large literature on how a statistical analysis must be performed in such data sets. For example, a seminal book by Little & Rubin called Statistical Analysis With Missing Data provides very detailed exposure to the field. Probably the simplest of all methods is called imputation. For example there are high quality R packages like imputation or mi that does the job for you. Similarly knnimpute from MATLAB bioinformatics toolbox provides similar solution.
  
k-nearest neighbour algorithm (KNN) is the most common approach to discover the closest available value in the data vector. However, often implementations of KNN contains a lot of options that are not needed for simple imputations in 1D and Euclidean metric. Here I propose 1D discrete KNN recursive algorithm that scans a given vector and determines the closest available value to given index). The main idea is assuming periodic boundary conditions for the vector index boundaries (Two-way linear search on the ring, see simple sketch). This is an $O(\bf{N})$ algorithm, we scan the vector twice in the worst case scenario. I have implemented this idea in MATLAB, for a given matrix. Files are available on the matworks file exchange [link]. This tool could be useful in imputing data in regression design matrices.
  
   

Optimal random search

A recent work shows how to exploit a priori distribution in random search.It is shown that square of the distribution must be selected as a search distribution [pre][arxiv].

Data Storage: How long can we keep it?

Apart from physical limitations, like extreme heat, failure rate and many other factors,
keeping our data storage accessible and recoverable long time is a huge challenge.
A recent article [link] on ACM queue discusses some issues on this line.