Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Multiplying Matrices Without Multiplying

arxiv.org

Post reply on HN
Print view View original

21–30 of 124 posts

Re: Multiplying Matrices Without Multiplying

#21

Post by mhh__ »

jmount wrote: post #10
antonzabirko wrote: post #8

Had this same exact thought as an undergrad like 3 years ago! I kinda gave up due to the massive barrier and difficult financial burdens faced by phd students. This feels nice to know i wasn't crazy.

In my opinion, that is the thing with theoretical computer science. Many of the ideas are comprehendible. And if one has the opportunity to do the work: you may get the result.

The biggest blocker for me is usually working out how I can implement a given idea without either writing a bunch of code (I'll get bored) or trying to verify if the paper even works for my use case without doing the aforementioned. One field I pay attention to with this problem seems to be abstract interpretation, with my background at least, the methods are very theoretically clean and impressive but actually implementing these as code and knowing how to write good implementations seems to be quite obtuse.

I genuinely don't understand why we allow papers to be published on computer science, with graphs plotted of the supposed efficacy of research (i.e. not just a theoretical paper), with no code attached.

Re: Multiplying Matrices Without Multiplying

#22

Post by leecarraher »

For some reason they run all their tests single threaded. Seems like parallelism is where all computing hardware is inevitably going. I also wish they had run time comparisons to more recent matrix sketching and multiplication method such as frequent directions, newer FJLT implementations, and RIP matrices based on hashing.

Re: Multiplying Matrices Without Multiplying

#23

Post by jijji »

mhh__ wrote: post #21
jmount wrote: post #10

Earlier quoted context omitted.

In my opinion, that is the thing with theoretical computer science. Many of the ideas are comprehendible. And if one has the opportunity to do the work: you may get the result.

The biggest blocker for me is usually working out how I can implement a given idea without either writing a bunch of code (I'll get bored) or trying to verify if the paper even works for my use case without doing the aforementioned. One field I pay attention to with this problem seems to be abstract interpretation, with my background at least, the methods are very theoretically clean and impressive but actually imple…

On page six of the paper:

To assess MADDNESS’s effectiveness, we implemented both it and existing algorithms in C++ and Python. All of our code and raw numerical results are publicly available at https://smarturl.it/Maddness. All experiments use a single thread on a Macbook Pro with a 2.6GHz Intel Core i7-4960HQ processor.

edit: the url above redirects to: https://github.com/dblalock/bolt

Re: Multiplying Matrices Without Multiplying

#24

Post by Ar-Curunir »

yangjunpro wrote: post #16

An interesting work, with some to-be-addressed questions: 1.The paper only covers the GEMM part with small-scale experiments(CIFAR-10/100), not covering convolution, not covering GEMM part in more popular network such as Transformer/BERT, etc. 2. It is still an approximating method, meaning potential accuracy loss. So I think this method is less attractive to training acceleration scenario, maybe potentially as a com…

If it works better for inference, it could enable fast inference on devices which don't have good tensor cores/gpus

Re: Multiplying Matrices Without Multiplying

#25

Post by esjeon »

> MADDNESS

I think this name really fits well to the concept. Replacing matrix-multiplication with some hash-lookups! (warning: an overly simplified statement)

This is a really interesting application of PQ(product quantization), which itself also requires learning (usually K-means). Paper: https://lear.inrialpes.fr/pubs/2011/JDS11/jegou_searching_wi...

Considering that ANN has survived through many approximations (e.g. lower precision, pruning), and that many ANN applications are anyway subjective (e.g. image processing, recommendation), I think this can be highly useful in many cases.

Re: Multiplying Matrices Without Multiplying

#26

Post by Ar-Curunir »

mhh__ wrote: post #21
jmount wrote: post #10

Earlier quoted context omitted.

In my opinion, that is the thing with theoretical computer science. Many of the ideas are comprehendible. And if one has the opportunity to do the work: you may get the result.

The biggest blocker for me is usually working out how I can implement a given idea without either writing a bunch of code (I'll get bored) or trying to verify if the paper even works for my use case without doing the aforementioned. One field I pay attention to with this problem seems to be abstract interpretation, with my background at least, the methods are very theoretically clean and impressive but actually imple…

Computer Science doesn't mean empirical stuff only, nor does it mean evaluations with code.

Theory has its place, and so does systems work. No need to denigrate one or the other.

Re: Multiplying Matrices Without Multiplying

#27

Post by Ar-Curunir »

jmount wrote: post #10
antonzabirko wrote: post #8

Had this same exact thought as an undergrad like 3 years ago! I kinda gave up due to the massive barrier and difficult financial burdens faced by phd students. This feels nice to know i wasn't crazy.

In my opinion, that is the thing with theoretical computer science. Many of the ideas are comprehendible. And if one has the opportunity to do the work: you may get the result.

tbh I don't think most ideas in TCS are comprehensible to outsiders without spending at least a year or two building background with the state of the art. Even if you can design an algorithm, to get a good TCS paper you have to prove bounds on how well it approximates and/or on its running time.

Re: Multiplying Matrices Without Multiplying

#28

Post by fnord77 »

alfor wrote: post #11

I wonder how our brain can train billion of neuron without matrix multiplication. What is the biological process that get a similar result?

btw neurons are not the only units of computation in the human body.

allosteric activation in enzyme binding sites act like transistors almost. inside every cell there's various computations occuring

Re: Multiplying Matrices Without Multiplying

#30

Post by erosenbe0 »

echelon wrote: post #7
ausbah wrote: post #2

as a total outside to this sort of stuff, doesn't this have the big issue of error propagation?

Probably, but hill climbing will avoid loss in the long run. The speed boost is probably more than worth it. I wouldn't be surprised if we started using lossier math for faster state space search. Once you find a peak, you could swap out the maths to be more exact.

Suppose you have a set membership question. If you approximate yes, you do a more complex inquiry to grab details. If you approximate no, you tell the user no, don't know that face [answer, command, etc]. So this is ripe for approximate methods as you can tune to get very few false negatives (respond no when it's really yes), but allow a healthy dose of false positives.
Post reply on HN