Blockwise Optimization Using Zonal Entropy and Key hYperplanes (BOUZEKY)

Abstract: BOUZEKY, why & how ?

In the current architecture, a significant limitation arises due to the requirement that either every GPU involved in training must hold the entire model state, or they must communicate with ms latency, virtually functionning as 1 big GPU to ensure that gradient propagation is efficiently done.

The same problem arise during inference step, where the GPU must hold the whole stuff in memory in RAM at the same time.

This blog post aim to develop 2 approaches to reduce :

• the dependency to a centralized system during training, by providing practical compute algorithms examples.
• overall RAM dependency during inference through efficient nodes pre-loading in RAM.

Those 2 things seems very important stepping stones to make LLM@home-like projects emerging, and popularized decentralizedly-trained, lightweight, efficient LLMs.

Plan

This document aims to give a bit of context to the suggested algorithm, and to explain why and how we obtained it.

• First, we try to give some elements to explain why neural networks with several layers are solving previously unsolvable problems, albeit at high computational training costs.
• Second, we will try to guess where those training costs are coming from, and what practical constraints it causes.
• Third, we are going to establish why the "gradient descent", despite its disadvantages, still works
• Fourth, we are going to establish the properties of a "perfect neural network layer", and see that because of forward thinking fitting the n-th layer does not require to know the n+i-th layers.
• Fifth, we will establish why fitting a "perfect neural network layer" is a hard problem.
• Sixth, we will finally suggest an empirical way of fitting them, that could have a better "learning density" (how much compute it takes to converge), and that would be more parallelizable than gradient descent.

Why is deep learning so good at solving real-life problems ?

On high complexity problems, algorithm efficiency is a compromise.

When you are making a computer program, you are trying to find a compromise between several metrics :

• Computation speed $s$ during program execution.
• Computation speed $t$ during program construction.
• Size of the program $q$
• Accuracy of the program $a$ Given a price cost $p(s, a, q, t)$; your budget $B$ and an objective cost $o(s,a,q,t)$ you are trying to find $$\max_{s,a,q,t \text{ u.c. } p(s,a,q,t) < B} o(s,a,q,t)$$ How does it looks like in practice ? Let's look at a simple example Conway's game of life). Suppose you want to plot, given a state $u_0$, the state after $n$ iterations, $u_n$, on a $k \times k$ grid.

Two extreme ways to do this with perfect accuracy $a$ :

• Method 1: if $f$ transforms a state $u_n$ into $u_{n+1}$ through some rules, and $u_n = f(...f(u_0))$, you could pre-compute $g = f \circ \dots \circ f$ and store it. In this solution, you have the lowest speed $s$ but a high $t$ and $q$. Method 1 is probably out of budget because of $q$ and $t$
• Method 2: you can simply store $f$ and apply it $n$ times. $t$ and $q$ are very low, but $s$ is high. Method 2 is probably out of budget because of $s$.

Neither ways to do this is very efficient. You would probably like $s$ smaller than in method 1, but $t$ and $q$ smaller than in method 2. You are even ready to give up a bit of accuracy to diminish storage and compute requirements.

What are possible practical tradeoffs ?

• Compared to method 1, you can avoid explicitely computing the entirety of $g$, leaving some part "compressed" to diminish $t$ and $q$, but augmenting $s$.
• Compared to method 1, if you do not care about having a perfect model, you could throw away part of $g$ that "in practice" never called (i.e. given your "usual inputs"). You diminish $t$ and $q$, leave $s$ constant, but diminish $a$.

Deep neural networks is a practically good tradeoff

Deep neural network architecture :

• encapsulates a hierarchical features representation (which is the native design of a lot of practical things like text or image), therefore maintains $a$ high while reducing $q$ and $s$
• only stores features that are seen in real data (random noise is much more dense than real data, but the model does not learn on random data), reducing $q$ while maintaining a high $a$ in practice.
• Express thoses deduced rules in a fast-to-compute framework, therefore reducing $s$

But, and that the topic of this article, the $t$ parameter is still considerable, and we could propose some algorithms to achieve equivalent $s$, $a$, $q$ with less $t$.

Why is training a deep neural network so cost-intensive ?

The problem is not deep learning itself, but the gradient descent training method. It has 2 main drawbacks.

• First, you need to fit the whole network at once : it means having all the weight in RAM simultaneously, or have a very low latency between connected machines if you want to split training on several machines.
• Second, you can't really parallelize the training. Given a data $X$, you need to compute your predicted label $\hat Y$, and then modify your weights, before doing another prediction. One may still use batches, but with a need to limit their size in order to maximize generalisation.
• Third, gradient descent probably does not maximises the use it makes from data at each step. The problem of finding the best neural networks, as we will see further, is non-convex, and thus data probably can't be exploited as optimally as in a linear regression modeling, but one can probably find algorithms that more reliably improves the "density of usage of data".

To illustrate the third point, let's compare two ways of fitting a simple linear regression model with one predictor (X) and an intercept:

1. The least-squares method (closed-form solution) finds the optimal parameters in one step by solving the normal equation:

    $\theta = (X^T X)^{-1} X^T Y$

    This method is extremely efficient because it directly computes the best-fitting parameters without iteration. It fully leverages the entire dataset in a single matrix operation, making it optimal in terms of data usage and convergence speed.

2. Gradient descent, in contrast, updates the parameters iteratively:

    $\theta_{t+1} = \theta_t - \alpha \nabla L(\theta_t)$

    where $\alpha$ is the learning rate, and $\nabla L(\theta_t)$ is the gradient of the loss function. Each update uses only part of the information available in the dataset at a given step, leading to a much slower convergence. Moreover, the choice of α\alphaα affects both convergence speed and the risk of overshooting the minimum. If the learning rate is too small, convergence is painfully slow; if it's too large, the model may never reach an optimal solution.

Why is gradient descent backpropagation, despite its important cost, still works ?

You cannot train neurons of a layer independently

Suppose another simple problem. You have a 2x2 pixel grid and want to train a neural network to recognize diagonals. Here are the pixel numbering and shapes we are trying to recognize for reference.

![[Pasted image 20250121104735.png]]

A neural network that would return 1 if the pattern is a diagonal and 0 else could be achieved with a 2-neurons hidden layer and a 1-neuron output layer, as demonstrated here : (the activation function of every neurons is : $\mathbb{1}(aX + b \ge 0)$). Here is an example of possible learned weights :

![[Pasted image 20250121102611.png]] You can see that the "Hidden 1" neuron has learnt to recognize the second diagonal and "Hidden 2" the first diagonal.

If you were training the hidden neurons independently, initialized with random weight, they could converged to fitting the same diagonal.

Gradient descent backpropagation empirically works as an "learning manager", organizing the learning process of a layer.

When you train using backpropagation on the diagonals problem, you can expect to converge to the solution. This is because backpropagation empirically detects that, if a neuron is already fitted on the first diagonal, exploring with the other neuron weights does not degrade the whole network accuracy. Thus, gradient descent "manages knowledge": it (in average) allows neurons that do not have learn something useful to explore.

Formalizing gradient network inefficiency

Formalizing deep learning training process

Let :

• $X$ be a random variable representing your feature,
• $Y$ be a random variable representing your label.

Usually, the goal of your model is presented as such : Finding $f$ the best estimator possible so that $\hat Y = f(X)$ is "as close as possible" from the real $Y$. This is usually measured through a distance metric on real data, often the cross-entropy metric for classification problems, which is expressed as :

The main problem of this approach is that in order to measure the performance $f$ of our model, it should be already fully built and able to produce a $\hat Y$ output, so that this output can be practically evaluated.

Let :

• $f_1, \dots f_l$ being the $l$ neurons of my first network layer.
• $\bar f$ being the next layers of my network.

We can thus express $\hat Y = f(X) = \bar f(f_1(X), \dots, f_l(X))$. And the main problem can be expressed as : is there any way to evaluate $f_1(X), \dots, f_l(X)$ if you do not know $\bar f$ ?

Fortunately, the answer is yes ! There is an indicator, called mutual information, that can be practically approximated, and that verifies :

$$ \max_{f_1, \dots, f_l}{I(Y; f_1(X), ... f_n(X))} = \max_{f_1, \dots, f_l, \bar f}{I(Y; \bar f(f_1(X), ..., f_n(X))} \ge I(Y, \hat Y), \forall{\hat Y}$$ with equality case for the best possible estimator.

Note that the estimator $f$ that maximises $I(Y; \hat Y)$ turns $X$ into $\hat Y$ that has exactly the probability distribution $P(Y = y|X)$. Note that such an estimator would minimize the cross entropy :

$$\text{Cross-Entropy Loss} =−E_{(X,Y)}​[\log \hat P(Y|X)] = H(Y|X)+D_{KL}​(P(Y|X)∥ \hat P(Y|X))$$

since $D_{KL}(P_1, P_2) = 0 \Leftrightarrow P_1 = P_2$ !

Thus, if you can somehow solve this $\max_{f_1, \dots, f_l}{I(Y; f_1(X), ... f_n(X))}$, you can train your layer optimally, without having to train your whole network

The problem is non-convex, and thus not analytically solvable. but the following algorithm build iteratively $f_{i+1}$ given $f_1, \dots f_i$. and guarantees that $I(Y; f_1(X), \dots, f_i(X)) \le I(Y; f_1(X), \dots, f_{i+1}(X))$, (with much more interestingly, almost always a strict inequality in practice).

This algorithm is easy to parallelize, without much communication between machines (at least, much less often than using backpropagation). and could be used to decentralizedly train large neural networks models.

First, in the light of this framework, why does backpropagation takes forever to converge ?

The backpropagation method is trying to solve the same problem : $$ \max_{f_1, \dots, f_l}{I(Y; f_1(X), ... f_l(X))}$$ but it takes $I(Y; \bar f(f_1(X), ..., f_l(X))$ as a proxy of ${I(Y; f_1(X), ... f_l(X))}$, with is technically ok if $\bar f$ is perfect, but can be a really bad proxy, especially at the beginning of the training, when $\bar f$ is completely random. Plus, suppose that you have $f_1, ..., f_l$ and $g_1, ..., g_l$ so that $$I(Y; f_1(X), ..., f_l(X)) > (Y; g_1(X), ..., g_l(X))$$you have absolutely no guarantee, since $\bar f$ is not bijective, that $$I(Y; \bar f(f_1(X), \dots, f_l(X))) > I(Y; \bar f(g_1(X), \dots, g_l(X)))$$and thus that the gradient descent will favor $f_1, ..., f_l$.

The new training algorithm

Why is fitting neurons a hard problem ?

1. Finding the best hyperplan is not a convex problem

Given those data, let us find the hyperplan that best separate the data, i.e. that maximizes mutual information.

![[Pasted image 20250115164214.png]] Given our data, let us define $X$ the random variable associated to the position on the space. Let us define X_{\alpha}. $X = x$. Let us define :

• $S$ the random variable associated to the the shape (circle or triangle),
• $X$ the random variable associated to the shape position.
• $X_{\alpha} = \mathbb{1}(X \ge alpha)$ defines on which side of $\alpha$ the random variable is.
• $f : \alpha \longrightarrow I(S ; X_{alpha})$ representing the mutual information gained by knowing $X_{\alpha}$ value.

Finding our best hyperplan is equivalent to finding $\max_{\alpha} f(\alpha)$. But if we represent $f(\alpha)$ in our case, it is clearly non-convex. Therefore, this problem has no simple analytical solution !

![[Pasted image 20250116085336.png]]

2. Even if you solve this non-convex problem, the greedy algorithm does not converge to the optimal solution.

Let us take this example ![[Pasted image 20250115114128.png]] The best hyperplans to separate data are clearly the following $H_1$ and $H_2$.

![[Pasted image 20250115114744.png]] The main problem is that a greedy algorithm that would find the best possible hyperplan, would not converge to this solution, since both $H_1$ and $H_2$ alone do not increase mutual information : $$I(S|H_1(X)) = I(S|H_2(X)) = 0$$ But ($E$ being the informational entropy) : $$I(S | H_1(X), H_2(X)) = E(X)$$ A greedy algorithm would produce $H_1'$ that would more look like this :

![[Pasted image 20250116151124.png]]

Of course, after convergence, you would probably have something like this :

![[Pasted image 20250116151435.png]]

That would contain $H^{'}_3 = H_1$ and $H^{'}_4 = H_2$, but with other now redundant hyperplans. With some pruning, one could detect that $H^{'}_3, H^{'}_4$ are sufficient.

Fitting one algorithm in practice

The algorithm would look like : while the weighted entropy potential is above a certain threshold, add a new Hyperplan to separate the data. Once the layer is created, repeat with next layer.

But how to efficiently find the "next best hyperplan" I will propose one highly parallelizable algorithm that converges, but this is probably not the best one. Some further research should probably be made to find empirical improvements. I will precisely detail where I am doing approximations.

The idea is :

• Take the subzone defined by the already created hyperplans with the biggest potential for mutual information improvement, or the whole space if it is the first iteration.
• Compute the weighted center of mass of the $n$ classes. Then do a hierarchical clustering to separate them in 2 groups, and compute 2 new center of mass. Finally, split the space orthogonally to the segment defined by the 2 obtained centers of mass (the centers should be on different sides of the hyperplan). This will always increase the mutual information if the 2 centers are distinct points. You can either split in the middle or look for a better split point manually, or even use techniques similar to Maximum margin separation algorithm
• Repeat until the mutual information potential gain (weighted entropy) is too limited.
• Prune the network to find redundant hyperplans (by computing the mutual information of the layer minus this hyperplan for all defined hyperplans)

Note that :

• Choose the next hyperplan based only on a subzone is suboptimal
• Choose the next hyperplan with the center of mass technique guarantees a mutual information gain, but not that the gain will be the biggest (see 1D example).

But also, note that :

• Several subzones can be studied in parallel.
• Center of mass can be computed in parallel.
• Mutual information potential gain can be computed in parallel (actually, this is weighted entropy of the remaining zones)

If $S$ is the subzone, $n$ the number of samples in the subzone, $S$ the shape random variable, with $P$ its distribution, the weighted entropy is denoted :

$$E_{W}(S)=- n\sum_{s \in S}{P(s)\log_{2}(P(s))}$$ Basically, everything can be parallelized, without much need for constant communication between processors.