How to send a real number using a single bit (and some shared randomness)(mybiasedcoin.blogspot.com)
mybiasedcoin.blogspot.com
How to send a real number using a single bit (and some shared randomness)
http://mybiasedcoin.blogspot.com/2021/10/how-to-send-real-number-using-single.html
53 comments
I would have naiively thought that you would just send a 1 with a probability equal to the number you want to send.
Is this compared in the post? Some of it went over my head.
Is this compared in the post? Some of it went over my head.
Yes, that is covered in this half paragraph:
> Randomized rounding, where the sender sends 1 with probability x and 0 otherwise, and the receiver uses the received bit X as the estimate x', has the property that E[x'] = x. Unbiased estimators are arguably more natural for many estimation problems. Here the measure of performance would be the maximum variance for the estimate over all inputs x, so for randomized rounding the cost is 1/4 (when x = 1/2).
The "cost"/"variance" of 1/4 in the above paragraph is talked about later in the article as the "expected squared error"; the main result is a scheme that has a cost of just 0.04599, which is better than the "send a 1 with a probability x" scheme, which has a cost of 1/4 = 0.25.
> Randomized rounding, where the sender sends 1 with probability x and 0 otherwise, and the receiver uses the received bit X as the estimate x', has the property that E[x'] = x. Unbiased estimators are arguably more natural for many estimation problems. Here the measure of performance would be the maximum variance for the estimate over all inputs x, so for randomized rounding the cost is 1/4 (when x = 1/2).
The "cost"/"variance" of 1/4 in the above paragraph is talked about later in the article as the "expected squared error"; the main result is a scheme that has a cost of just 0.04599, which is better than the "send a 1 with a probability x" scheme, which has a cost of 1/4 = 0.25.
Thank you, I found it tricky to read things as I usually do as I had less to latch on to.
The post doesn't put in a lot of effort to be understandable.
What are some real-world situations where you can only send a single bit but have shared randomness? That seems like a bizarre constraint. Is this just - and no shame in this - math for math’s sake?
Real world situation that is very similar to this: you send a friend a few bits (a seed) they plug it into Minecraft and the both of you can play in the same exact yet practically infinite world.
That is possible due to the shared randomness built into the world generation on both computers.
This sounds halfway related to a problem my statistics professor worked on, sending data over a shared interface without detection. Note that these scenarios assume discrete time.
"Shared randomness" might be the current noise level on some radio frequency in enemy territory. You and your receiving friend can both hear everything, but as soon as one of you starts transmitting you must have a very careful strategy to avoid detection.
"Shared randomness" might be the current noise level on some radio frequency in enemy territory. You and your receiving friend can both hear everything, but as soon as one of you starts transmitting you must have a very careful strategy to avoid detection.
I could imagine a scenario where you have many clients sending you information repeatedly, and you’d like to restrict the size of each packet. I think what this post is saying is that during the initial client setup you could add an arbitrary amount of shared randomness to increase accuracy while keeping the packet size down.
To more directly answer your question, the post mentions federated learning of machine models as an application.
To more directly answer your question, the post mentions federated learning of machine models as an application.
Concretely, imagine a sensor node sampling a lot of low-quality sensors frequently. You can afford some setup (to share an AES key, generating as much shared (pseudo-)random as you want), but you want your per-measurement overhead to be small.
… it’s not the most practical, and the single-but version seems to be a toy problem, but I can imagine it being useful in some very particular cases?
… it’s not the most practical, and the single-but version seems to be a toy problem, but I can imagine it being useful in some very particular cases?
On the hardware side, I think delta-sigma ADCs [1] might solve the same problem. They only sample 1-bit at a time, but they do so at a much faster rate than conventional ADCs.
I'm a bit out of my scope here, but I think the concept is really cool.
[1] https://en.wikipedia.org/wiki/Delta-sigma_modulation
I'm a bit out of my scope here, but I think the concept is really cool.
[1] https://en.wikipedia.org/wiki/Delta-sigma_modulation
[deleted]
This wouldn't count as "real world" but this topic reminds me of communication protocols described in the novel: https://en.wikipedia.org/wiki/The_Three-Body_Problem_(novel)
The article clearly mentions distributed learning and its really not that hard to generalise on literally any partially parallelizable computing problem with bandwidth limitations between the compute nodes.
[deleted]
I hate these articles that jump straight into some complex solution without stating the problem clearly... If the problem really is to send a real number using a single bit (and some shared randomness) then clearly that’s just impossible. Next!
The problem is a variation of that, which makes it possible, as explained in the post. The large caveat is that the accuracy is probabilistic, and it’s expected that the receiver is getting many 1-bit from various sensors that are all measuring the same phenomena.
It’s a bit like the concept of dithering in images, where visually we can represent shades of grays just by using many 1 bit pixels.
It’s a bit like the concept of dithering in images, where visually we can represent shades of grays just by using many 1 bit pixels.
Yes, it's a variation on the problem ... but sending many bits to the receiver is a really significant variation on just sending one bit.
I'm not sure whether so many people would be intrigued to read "How to send a real number using arbitrarily many bits."
I'm not sure whether so many people would be intrigued to read "How to send a real number using arbitrarily many bits."
Yes, both the blog and the Arxiv paper are very confusing, because they speak about estimating a real number "Using a Single Bit".
It is obvious that there is no way of guessing more than 1 bit of a number after receiving a single bit (unless you have previously established a convention like 0=any_other_number, 1=a_certain_number, when you can estimate many bits when you receive a "1", but no bits when you receive a "0").
Looking at the text of the article, it is obviously that it does not refer to sending "a Single Bit", but to sending "a Single Bit" many times, because only then the variance and the other statistics used by them can be computed.
If the problem is rephrased as "How to Send a Real Number Using a Single Bit" at each of many transmissions, then the problem becomes banal and it has been studied for more than 60 years, in the field of analog-digital and digital-analog conversions, under names like "stochastic converters", "delta modulation", "delta-sigma modulation", and a few others, and much better solutions are known than discussed in the article.
(The corresponding problem in that field is how to measure an analog signal, i.e. the real number, with a single analog comparator and a single reference value, when you get just 1 bit of information, i.e. whether the measured value is smaller or greater than the reference. The simplest solution is to sum a random noise with the value to be measured, and then compute the average of the 1-bit values, but there are much more sophisticated methods).
It is obvious that there is no way of guessing more than 1 bit of a number after receiving a single bit (unless you have previously established a convention like 0=any_other_number, 1=a_certain_number, when you can estimate many bits when you receive a "1", but no bits when you receive a "0").
Looking at the text of the article, it is obviously that it does not refer to sending "a Single Bit", but to sending "a Single Bit" many times, because only then the variance and the other statistics used by them can be computed.
If the problem is rephrased as "How to Send a Real Number Using a Single Bit" at each of many transmissions, then the problem becomes banal and it has been studied for more than 60 years, in the field of analog-digital and digital-analog conversions, under names like "stochastic converters", "delta modulation", "delta-sigma modulation", and a few others, and much better solutions are known than discussed in the article.
(The corresponding problem in that field is how to measure an analog signal, i.e. the real number, with a single analog comparator and a single reference value, when you get just 1 bit of information, i.e. whether the measured value is smaller or greater than the reference. The simplest solution is to sum a random noise with the value to be measured, and then compute the average of the 1-bit values, but there are much more sophisticated methods).
I think the motivation here is still compression. You know you’re going to have a bunch of input values coming in, and this is about how to minimize the size of each value. So the overall throughput required does go down in the end.
> If the problem really is to send a real number using a single bit (and some shared randomness) then clearly that’s just impossible. Next!
Not impossible. You can perfectly well send say, pi, by implementing a protocol which sends 1 if the number is pi and 0 if not.
And it's about as useful as the mentioned algorithms.
Not impossible. You can perfectly well send say, pi, by implementing a protocol which sends 1 if the number is pi and 0 if not.
And it's about as useful as the mentioned algorithms.
But no! The very first sentence clearly states: "In this post, we'll look at the natural problem of how to communicate an estimate of a real value in [0,1], using just 1 bit." The second paragraph sketches the motivation for the problem.
How much more exposition do you want from a casual blog post? There's a link to the academic paper if you want full details (you can follow up on the numerous references to other papers, which explain applications.)
How much more exposition do you want from a casual blog post? There's a link to the academic paper if you want full details (you can follow up on the numerous references to other papers, which explain applications.)
The blog reproduces rather faithfully what the academic paper says.
The academic paper is confusing, because it defines the problem as it would have been a singular event, the sender chooses a real number, then sends 1 bit to the receiver and the receiver miraculously guesses the real number.
You have to waste time by carefully studying the paper to see that the statistical methods used are meaningless for a singular event, so in fact a large number of transmissions of a single bit are assumed and the accuracy (i.e. the variance) of the estimation of the real number is computed over that very large but unspecified number of transmitted bits.
In any real application, the main quality of an estimation algorithm would be determined by how many single bits must be transmitted and received to guarantee a certain accuracy (variance) of the estimation, i.e. a certain number of recovered bits of the real number, but I have lost patience when reading the paper before discovering whether the authors even mention this somewhere.
What should be clear for everyone, is that recovering N bits of a real number, i.e. reducing the variance of the estimation to that level, always requires transmitting many more single bits than N.
Nevertheless, even if more bits are sent, there are many cases when this is useful, e.g. because losing some single bits or receiving them with errors has little effect, but there may also be other reasons.
The academic paper is confusing, because it defines the problem as it would have been a singular event, the sender chooses a real number, then sends 1 bit to the receiver and the receiver miraculously guesses the real number.
You have to waste time by carefully studying the paper to see that the statistical methods used are meaningless for a singular event, so in fact a large number of transmissions of a single bit are assumed and the accuracy (i.e. the variance) of the estimation of the real number is computed over that very large but unspecified number of transmitted bits.
In any real application, the main quality of an estimation algorithm would be determined by how many single bits must be transmitted and received to guarantee a certain accuracy (variance) of the estimation, i.e. a certain number of recovered bits of the real number, but I have lost patience when reading the paper before discovering whether the authors even mention this somewhere.
What should be clear for everyone, is that recovering N bits of a real number, i.e. reducing the variance of the estimation to that level, always requires transmitting many more single bits than N.
Nevertheless, even if more bits are sent, there are many cases when this is useful, e.g. because losing some single bits or receiving them with errors has little effect, but there may also be other reasons.
some of the comments on this article are so embarrassing. It's just a short and clearly written article on a pretty simple and fundamental type of problem in information theory. Similar ideas are the basis for the systems we use in data compression and transmission and error correction among other things.
Maybe better to think for a few seconds before dismissing the problem as pointless and claiming to hate it.
Maybe better to think for a few seconds before dismissing the problem as pointless and claiming to hate it.
It describes the problem, but not fully. Either do it properly or link to a complete description.
In this case, unlike what the article states as the problem, the point seems not to be how to send a real number using a single bit, but how to aggregate such bits from many agents that measure some shared thing.
That's two very, very different things.
In this case, unlike what the article states as the problem, the point seems not to be how to send a real number using a single bit, but how to aggregate such bits from many agents that measure some shared thing.
That's two very, very different things.
Or encode the number using timing.
That doesn’t work because it requires two clocks that are synchronized .
So?
Suppose you have two clocks that are synchronized to +-dt1, and sending messages takes some known amount of time +-dt2 and you want to make sure the sender is able to transmit within +dt3 of whatever event triggered the send event.
It seems to me that you'd be able to transmit at least dt3/(2*(dt1+dt2)) distinct values with the pretty naive approach of discretizing time into segments longer than the uncertainty between the message-and-clock error. I'd be willing to bet that a sophisticated approach could do much better.
Suppose you have two clocks that are synchronized to +-dt1, and sending messages takes some known amount of time +-dt2 and you want to make sure the sender is able to transmit within +dt3 of whatever event triggered the send event.
It seems to me that you'd be able to transmit at least dt3/(2*(dt1+dt2)) distinct values with the pretty naive approach of discretizing time into segments longer than the uncertainty between the message-and-clock error. I'd be willing to bet that a sophisticated approach could do much better.
Seems like the overhead to ensure two different systems' clocks are sufficiently synchronized would be fairly expensive.
It looks like PTP only works on a local network; not sure how you'd do that across the Internet.
https://en.wikipedia.org/wiki/Precision_Time_Protocol
It looks like PTP only works on a local network; not sure how you'd do that across the Internet.
https://en.wikipedia.org/wiki/Precision_Time_Protocol
Could quantum entanglement do this? If you collapse the wave function on one end, the other collapses instantaneously. It may not be any good in itself for transferring information, but it could be used as the signal to synchronize on?
Wouldn’t that count as sending information?
Yes that’s the point of my argument
No, what you suggestion would also imply superluminal communication because you also have to send what your are measuring (such as polarization) classically. Now you are sending three bits .
It would be luminal. But combine the knowledge of the location with speed of light and you can backwards engineer the difference. But because it's luminal without needing directionality, that cuts out a bunch of the question marks on optical networking.
You can't know when exactly the collapse occurred, I think.
I wouldn’t use the internet. I would instead use wwv or a atomic clock (Facebook has one in development that you can put in a PCIe slot)
Yes, you need more than just a bit, but that is the case also for the article.
Further, you could send the bit as a pulse, where the pulse-width is proportional to the number.
Further, you could send the bit as a pulse, where the pulse-width is proportional to the number.
The first thing I thought of based on the title was sending at a specific time that then is used as a lookup from something like PI or e.
According to the paper, this is sending an estimate of a real number with a finite number of bits (possibly one). The method aims to reduce worst-case(?) error by relying on preshared state (in this case, the seed to a PRNG).
What is "shared randomness" in the context of this article? When I google it I find papers on quantum computing - is that a prerequisite for this implementation?
Shared randomness is when the sender and receiver each have a PRNG or list of random numbers that are synchronized. Both sides know what the “current” and “next” random numbers are.
Thank you! I was confused by the ℎ∼𝑈[−1/2,1/2], thinking that it meant either that they both have a set of random numbers (in which case, how does the receiver know which one of them the sender used?) or that they both had the same single random number in that range (in which case it looks like it's basically the same as the randomised rounding case).
Your explanation that they are both going through the same list at the same rate clarifies that. They have n random numbers and are both using the same one for each transmission/receipt event.
I guess that in practice, synchronising that would be a pain. Either they sync on packets sent/received, which means that one dropped packet messes everything up, or they sync on time, in which case there's clock skew to worry about. Or they could have sync information in the data sent ("I'm using the 1234th item in the shared randomness"), which makes a bit of a nonsense of the whole "one bit" thing.
Am I missing something there?
Your explanation that they are both going through the same list at the same rate clarifies that. They have n random numbers and are both using the same one for each transmission/receipt event.
I guess that in practice, synchronising that would be a pain. Either they sync on packets sent/received, which means that one dropped packet messes everything up, or they sync on time, in which case there's clock skew to worry about. Or they could have sync information in the data sent ("I'm using the 1234th item in the shared randomness"), which makes a bit of a nonsense of the whole "one bit" thing.
Am I missing something there?
I see this as the future of machine learning.
Using a single bit to communicate weight updates during the learning process reduces bandwidth required, and allows highly parallel training.
I suspect in the future we'll even see methods of sub-1-bit weight updates to further decrease bandwidth requirements to keep massive models approximately in sync between distant learning nodes.
Using a single bit to communicate weight updates during the learning process reduces bandwidth required, and allows highly parallel training.
I suspect in the future we'll even see methods of sub-1-bit weight updates to further decrease bandwidth requirements to keep massive models approximately in sync between distant learning nodes.
What would a sub 1-bit weight update look like? I’m having trouble wrapping my head around the concept of (what I assume would be) a fraction of a bit?
First imagine a less-than-bit fact. Suppose you have a set of 1024 computers and you want to pick out a specific computer based on many facts about a single computer. 1 in 4 computers runs Linux and the rest run Windows. Knowing a computer runs Windows is about half a bit of the information necessary to identify the computer.
A less-than-bit update can be combined with another such an update to encode a single bit. For instance, my protocol could use a bit to indicate “the computer runs Linux, or it is one of the 256 Windows computers in this list”. You know the computer has a 50% chance of running Windows.
A less-than-bit update can be combined with another such an update to encode a single bit. For instance, my protocol could use a bit to indicate “the computer runs Linux, or it is one of the 256 Windows computers in this list”. You know the computer has a 50% chance of running Windows.
Imagine we have 2 weights we want to update. For each weight, choose a pseudo-random number known by both sender and receiver. If a "1" bit is received, update both weights with the random number. If a zero is received, don't.
After enough iterations, each weight can converge on any value.
After enough iterations, each weight can converge on any value.
Only tangentially related, but practically how does one only send a single bit of data to a server? If you have a tcp or udp connection then each send is actually a much larger packet. Common rpc frameworks like protobuf also encode a single bit message to a larger structure. I'm sure there's a way, I just can't come up with it.
Anything over a network is going to have layer 2 framing overhead. Something like a serial port would do the trick.
Read a byte, only examine the first bit. Ignore the rest
Some cpus have general purpose IO pins. You could connect wires to those and send whatever signal you want.
Serial ports.
Can somebody please explain in simpler terms how this works?
If I have a real number, and add some (shared) random value to it, then round it to 0 or 1, how is the receiver able to retrieve the original real value???
.
The new Tesla 8 and 16 bit floating number formats in the Dojo system supports this kind of rounding up/down using a PRNG when compressing neural network parameters from higher precision floats (it is specified in the floating point paper).
The random rounding is needed to not have a bias in the neural network weight updates, but this article improves the rounding method to be more accurate (closer to the real rounding than uniform sampling) without reintroducing bias.