[HN Gopher] How to send a real number using a single bit (and so...
___________________________________________________________________
How to send a real number using a single bit (and some shared
randomness)
Author : adunk
Score : 36 points
Date : 2021-10-31 19:09 UTC (3 hours ago)
(HTM) web link (mybiasedcoin.blogspot.com)
(TXT) w3m dump (mybiasedcoin.blogspot.com)
| IanCal wrote:
| 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.
| ant6n wrote:
| The post doesn't put in a lot of effort to be understandable.
| rav wrote:
| 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.
| amelius wrote:
| Or encode the number using timing.
| zitterbewegung wrote:
| That doesn't work because it requires two clocks that are
| synchronized .
| amelius wrote:
| 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.
| Aerroon wrote:
| 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.
| londons_explore wrote:
| 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.
| asxd wrote:
| 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?
| londons_explore wrote:
| 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.
| fwip wrote:
| 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).
| wk_end wrote:
| 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?
| Gormisdomai wrote:
| 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?
| bjornsing wrote:
| 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!
| asxd wrote:
| 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.
| oh_my_goodness wrote:
| 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."
| asxd wrote:
| 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.
| ch33zer wrote:
| 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.
| lcampbell wrote:
| Anything over a network is going to have layer 2 framing
| overhead. Something like a serial port would do the trick.
| sesuximo wrote:
| Some cpus have general purpose IO pins. You could connect wires
| to those and send whatever signal you want.
| gpderetta wrote:
| Serial ports.
| kupopuffs wrote:
| Read a byte, only examine the first bit. Ignore the rest
___________________________________________________________________
(page generated 2021-10-31 23:00 UTC)