Tuple-oriented Compression for Large-scale Mini-batch Stochastic Gradient Descent
Li, Fengan
Chen, Lingjiao
Zeng, Yijing
Kumar, Arun
Wu, Xi
Naughton, Jeffrey
Patel, Jignesh
Data compression is a popular technique for improving the efficiency of data processing workloads such as SQL queries and more recently, machine learning (ML) with classical batch gradient methods. But the efficacy of such ideas for mini-batch stochastic gradient descent (MGD), arguably the workhorse algorithm of modern ML, is an open question. MGD's unique data access pattern renders prior art, including those designed for batch gradient methods, less effective. We fill this crucial research gap by proposing a new lossless compression scheme we call tuple-oriented compression (TOC) that is inspired by an unlikely source, the string/ text compression scheme Lempel-Ziv-Welch, but tailored to MGD in a way that preserves tuple boundaries within mini-batches. We then present a suite of novel compressed matrix operation execution techniques tailored to the TOC compression scheme that operate directly over the compressed data representation and avoid decompression overheads. An extensive empirical evaluation with real-world datasets shows that TOC consistently achieves substantial compression ratios by up to 51x and reduces runtimes for MGD workloads by up to 10.2x in popular ML systems.
 Hello, everyone. I'm Fong An. I'm currently at Google. So the agenda, I first going to talk about some overview and then the core technique, our compression and our metrics operation execution algorithm. Finally, I'm going to talk about results and some summary. So hopefully, I don't need to motivate too much that the mini batch gradient send is the algorithm we use for training machine models. The idea is essentially very simple. So you partition the data sets into a couple mini batches. So typically, each mini batch has tens of tuples or hundreds of tuples. Each time you sample a mini batch and you compute some metrics operations on it and you got the gradient and use the gradient to update the machine models. And then you go back. You keep doing like this until either your accuracy is satisfied or some termination condition is met. So this is great. This is essentially the algorithm we use right now. I think people use mini batch gradient send because it's faster than batch gradient send while you have to use all the tuples to update the model. So here you can see the green line is the mini batch gradient send. It's also more stable than pure stochastic gradient send where you only use a single tuple to update the model. Okay. But the problem we are facing now is mini batch gradient send can be really slow and expensive nowadays. So especially if you're working a domain in like computer vision or natural language processing, you know what I'm talking about, training model can take a couple of hours or even weeks and you probably need to spend a thousand dollars in cloud computing just for the experiments or something like that. This is also a problem that machine learning community are aware of and many people are talking about that. So I think there are many, many reasons for this problem. Mostly I think it's just we have more data now. So nowadays it's very easy that you have terabytes of data or petabytes of data and you cannot easily fit the data into memory. So you have to fetch the data from disk which is really, really expensive and our model is getting more and more complicated. For example, you may have very, very deep neural nets, many, many different layers and you have to compute those matrix operation. So my takeaway is don't do machine learning research. It's really expensive. No, I'm kidding. We have to solve this problem. So our solution is really a combo. It's a lossless compression algorithm plus a set of matrix operations that work together to make machine learning training faster and also cheaper. So now you may ask, what is so special about your compression and your matrix operation? Well, our compression is lossless. That means we have no accuracy loss. We guarantee the same result without using our technique. That also means it's orthogonal to all the lossy methods that machine learning community and database community has developed. For example, no precision training, all that kind of stuff, but you can use them together. Our compression also compresses really well. I do have experiment results to back that up. So the compression ratio is better than snappy and on par with GZIP. So it can reduce storage and IO cost a lot. Our matrix operation directly is executed on the compressed output. So we don't need to pay for the decompression cost, which is really expensive. You know, if you have GZIP and you decompress the bandwidth you get is only like 50 megabytes per second, which is really bad. But we don't need a decompression. More than that, we can also reduce the numerical computations. We actually have some theoretical guarantees that the complexity of the matrix operation is reduced by a factor of compression ratio. So in some sense, it's like all the storage redundancy are also avoided in the numerical computations. So this is just a little diagram. We compress the raw data. We get the compressed data. And we exclude a matrix operation on it. And we use computed gradients to optimize the models. Okay. So finally, we're going to talk about our compression. There are some design principles and lessons we learned from it. So basically, our compression has to be schema-aware. You cannot just use any compression which compresses a global bias. World compression actually knows the input is a table and we preserve the structure of the table. Physical encoding is a very simple technique that we use to encode the basic types, like integers and flow numbers. And turns out it plays a very important role in reducing the compressed output. There are three steps. Sparse encoding, logical encoding, and physical encoding. So someone actually wrote a blog about our work and I borrowed this graph from his blog. So thanks for the offer. So sparse encoding is really a very simple technique. We have this input table and we remove all the zeros from the table. For each value, we just prefix the calling index. So for example, the tuple 1 has a value of 5 and we prefix its calling index 3. So it becomes 3 colon 5. Our logical encoding is really the meat of this compression algorithm. And the key idea is that we find there are some repeating sub-sequences across tuples. For example, if you go back to this slide, you may find R2 and R3 are exactly the same and R1 and R2 share the same sub-sequence, which is 2 and 5. So we can dictionary encode these repeating sub-sequences to reduce the space. And furthermore, these dictionary entries can be stored as a prefix tree to further reduce the storage cost. And one interesting thing about the compression algorithm is that we don't need to store the prefix tree, which is essentially the dictionary entries. So it's like, okay, you have a dictionary encoding, but you don't need the dictionary at all. You can just get rid of it. The reason is that we can construct the dictionary on the fly. Well, if you guys know LZW, you know it's not surprising, but if you don't know it, it's kind of an interesting fact. So this is the actual algorithm. You can refer to the paper for more detail. The font is very small, so I don't expect you guys to read it. Okay, so here's an example of logical encoding. So yeah, exactly as I mentioned, we encode all the sub-sequences into the prefix tree. For example, for R2, 2, 2, 3, 5 is encoded as tree node 4 in the prefix tree. So tree node 4 is the last node in the prefix tree, and it represents 2, 2, 3, and 3.5. So now you can encode the sparse table as pointers pointing back to the prefix tree nodes. For example, R2 and R3 are just a single pointer pointing to the tree node 4. So physical encoding is just simple techniques. For example, we have bit packing for integers. So the idea is very simple. If you have a very small integer like 5, 6, or 8, you don't need four bytes to encode the integer. You only need a single byte. Value indexing is just another dictionary encoding for flow numbers. I have to mention all these techniques here are transparent. So you can easily switch to more advanced techniques for encoding these integers or flow numbers. And actually, SIGMOD and VLDB community has many, many great work. We just choose a very simple one. Okay. So now I'm going to talk about how we actually execute a matrix operation on the compressed output without the compression. So many machine learning models can be composed of matrix operations. For example, neural nets are essentially matrix times metric and there are many layers. Just regression SVM are like matrix times vector. As you can see, most of these metrics operation can execute on the compressed output without the compression. For example, general linear models and neural nets can execute on our compressed output directly. So how do we actually do that? So before I talk about these key ideas, there are some theoretical way to think about it. So compression, theoretically speaking, is like you have a linear transformation which maps the input table from the base space to a compression space. So you can do the same thing for the matrix operation, which is essentially another linear function. So you can use the same linear transformation which maps the matrix operation from the base space to the compression space. So this way, you never need to execute on the base space. You just execute everything on the compression space. So actually how we do that is using these key ideas that just give you a flavor of how that is possible. So we basically exploit the dictionary structure by memorizing the computed results and we exploit the prefix tree structure by dynamic programming. So I show you how we actually do it by this example. Suppose we want to compute a matrix times vector and this vector is here. It's very easy how you do that in the original space, right? Just do the inner product. So in our compression outputs, all you need is you do a BFS breadth-first search of the prefix tree and you compute the result, the inner product for each node. So it's very simple for the first three nodes because they only have a single node, right? For the node four, there is a very important trick here because essentially the result of its parent is already computed. So you don't need to start over. All you need is you fetch the result from its parent and append the result for the last node. So this is the dynamic programming which saves a lot of computation costs for us. And then for the table, for the dictionary encoded table, we just fetch all the results from prefix tree. There is no numerical computation here and we fetch all the results, we combine them together and we get the results. We have some theoretical guarantee which I briefly mentioned. So basically the complexity is reduced by a factor of compression ratio. Yeah, some results, so we use some real data sets like Minus and ImageNet. The data size ranges from 6 gigabytes to 20 gigabytes. Our training models such as logistic regression, SVM and neural nets, we compare with a bunch of systems like TensorFlow, system, ML, CycloM and Bismarck. So the compression ratio is basically we are better than snappy consistently and on par with Gzip. So sometimes we beat Gzip, sometimes Gzip beat us. Training time, we use 30 minutes to train logistic regression on ImageNet. 20x faster than no compression, 19x faster than Gzip, 10x faster than snappy. Training costs, so if you want to train a neural net on 150 gigabytes data within the same time, for TensorFlow you need a very powerful machine which costs $900 per month in Google Cloud while our method only needs a moderate machine like $100 or something like that in Google Cloud. So it saves me some money for the experiments, which is nice. So that's pretty much it. Summary, we made a machine learning training faster and cheaper. This is done by a lossless compression algorithm plus a set of metrics execution algorithm that work together. If there are any questions, I'm happy to take it.
 Hello, everyone.  I'm Fong An.  I'm currently at Google.  So the agenda, I first going to talk about some overview and then the core technique,  our compression and our metrics operation execution algorithm.  Finally, I'm going to talk about results and some summary.  So hopefully, I don't need to motivate too much that the mini batch gradient send is  the algorithm we use for training machine models.  The idea is essentially very simple.  So you partition the data sets into a couple mini batches.  So typically, each mini batch has tens of tuples or hundreds of tuples.  Each time you sample a mini batch and you compute some metrics operations on it and  you got the gradient and use the gradient to update the machine models.  And then you go back.  You keep doing like this until either your accuracy is satisfied or some termination  condition is met.  So this is great.  This is essentially the algorithm we use right now.  I think people use mini batch gradient send because it's faster than batch gradient send  while you have to use all the tuples to update the model.  So here you can see the green line is the mini batch gradient send.  It's also more stable than pure stochastic gradient send where you only use a single  tuple to update the model.  Okay.  But the problem we are facing now is mini batch gradient send can be really slow and  expensive nowadays.  So especially if you're working a domain in like computer vision or natural language processing,  you know what I'm talking about, training model can take a couple of hours or even weeks  and you probably need to spend a thousand dollars in cloud computing just for the experiments  or something like that.  This is also a problem that machine learning community are aware of and many people are  talking about that.  So I think there are many, many reasons for this problem.  Mostly I think it's just we have more data now.  So nowadays it's very easy that you have terabytes of data or petabytes of data and you cannot  easily fit the data into memory.  So you have to fetch the data from disk which is really, really expensive and our model  is getting more and more complicated.  For example, you may have very, very deep neural nets, many, many different layers and  you have to compute those matrix operation.  So my takeaway is don't do machine learning research.  It's really expensive.  No, I'm kidding.  We have to solve this problem.  So our solution is really a combo.  It's a lossless compression algorithm plus a set of matrix operations that work together  to make machine learning training faster and also cheaper.  So now you may ask, what is so special about your compression and your matrix operation?  Well, our compression is lossless.  That means we have no accuracy loss.  We guarantee the same result without using our technique.  That also means it's orthogonal to all the lossy methods that machine learning community  and database community has developed.  For example, no precision training, all that kind of stuff, but you can use them together.  Our compression also compresses really well.  I do have experiment results to back that up.  So the compression ratio is better than snappy and on par with GZIP.  So it can reduce storage and IO cost a lot.  Our matrix operation directly is executed on the compressed output.  So we don't need to pay for the decompression cost, which is really expensive.  You know, if you have GZIP and you decompress the bandwidth you get is only like 50 megabytes  per second, which is really bad.  But we don't need a decompression.  More than that, we can also reduce the numerical computations.  We actually have some theoretical guarantees that the complexity of the matrix operation  is reduced by a factor of compression ratio.  So in some sense, it's like all the storage redundancy are also avoided in the numerical  computations.  So this is just a little diagram.  We compress the raw data.  We get the compressed data.  And we exclude a matrix operation on it.  And we use computed gradients to optimize the models.  Okay.  So finally, we're going to talk about our compression.  There are some design principles and lessons we learned from it.  So basically, our compression has to be schema-aware.  You cannot just use any compression which compresses a global bias.  World compression actually knows the input is a table and we preserve the structure of  the table.  Physical encoding is a very simple technique that we use to encode the basic types, like  integers and flow numbers.  And turns out it plays a very important role in reducing the compressed output.  There are three steps.  Sparse encoding, logical encoding, and physical encoding.  So someone actually wrote a blog about our work and I borrowed this graph from his blog.  So thanks for the offer.  So sparse encoding is really a very simple technique.  We have this input table and we remove all the zeros from the table.  For each value, we just prefix the calling index.  So for example, the tuple 1 has a value of 5 and we prefix its calling index 3.  So it becomes 3 colon 5.  Our logical encoding is really the meat of this compression algorithm.  And the key idea is that we find there are some repeating sub-sequences across tuples.  For example, if you go back to this slide, you may find R2 and R3 are exactly the same  and R1 and R2 share the same sub-sequence, which is 2 and 5.  So we can dictionary encode these repeating sub-sequences to reduce the space.  And furthermore, these dictionary entries can be stored as a prefix tree to further reduce  the storage cost.  And one interesting thing about the compression algorithm is that we don't need to store the  prefix tree, which is essentially the dictionary entries.  So it's like, okay, you have a dictionary encoding, but you don't need the dictionary at all.  You can just get rid of it.  The reason is that we can construct the dictionary on the fly.  Well, if you guys know LZW, you know it's not surprising, but if you don't know it, it's  kind of an interesting fact.  So this is the actual algorithm.  You can refer to the paper for more detail.  The font is very small, so I don't expect you guys to read it.  Okay, so here's an example of logical encoding.  So yeah, exactly as I mentioned, we encode all the sub-sequences into the prefix tree.  For example, for R2, 2, 2, 3, 5 is encoded as tree node 4 in the prefix tree.  So tree node 4 is the last node in the prefix tree, and it represents 2, 2, 3, and 3.5.  So now you can encode the sparse table as pointers pointing back to the prefix tree nodes.  For example, R2 and R3 are just a single pointer pointing to the tree node 4.  So physical encoding is just simple techniques.  For example, we have bit packing for integers.  So the idea is very simple.  If you have a very small integer like 5, 6, or 8, you don't need four bytes to encode  the integer.  You only need a single byte.  Value indexing is just another dictionary encoding for flow numbers.  I have to mention all these techniques here are transparent.  So you can easily switch to more advanced techniques for encoding these integers or  flow numbers.  And actually, SIGMOD and VLDB community has many, many great work.  We just choose a very simple one.  Okay.  So now I'm going to talk about how we actually execute a matrix operation on the compressed  output without the compression.  So many machine learning models can be composed of matrix operations.  For example, neural nets are essentially matrix times metric and there are many layers.  Just regression SVM are like matrix times vector.  As you can see, most of these metrics operation can execute on the compressed output without  the compression.  For example, general linear models and neural nets can execute on our compressed output  directly.  So how do we actually do that?  So before I talk about these key ideas, there are some theoretical way to think about it.  So compression, theoretically speaking, is like you have a linear transformation which  maps the input table from the base space to a compression space.  So you can do the same thing for the matrix operation, which is essentially another linear  function.  So you can use the same linear transformation which maps the matrix operation from the base  space to the compression space.  So this way, you never need to execute on the base space.  You just execute everything on the compression space.  So actually how we do that is using these key ideas that just give you a flavor of how  that is possible.  So we basically exploit the dictionary structure by memorizing the computed results and we  exploit the prefix tree structure by dynamic programming.  So I show you how we actually do it by this example.  Suppose we want to compute a matrix times vector and this vector is here.  It's very easy how you do that in the original space, right?  Just do the inner product.  So in our compression outputs, all you need is you do a BFS breadth-first search of the  prefix tree and you compute the result, the inner product for each node.  So it's very simple for the first three nodes because they only have a single node, right?  For the node four, there is a very important trick here because essentially the result  of its parent is already computed.  So you don't need to start over.  All you need is you fetch the result from its parent and append the result for the last  node.  So this is the dynamic programming which saves a lot of computation costs for us.  And then for the table, for the dictionary encoded table, we just fetch all the results  from prefix tree.  There is no numerical computation here and we fetch all the results, we combine them  together and we get the results.  We have some theoretical guarantee which I briefly mentioned.  So basically the complexity is reduced by a factor of compression ratio.  Yeah, some results, so we use some real data sets like Minus and ImageNet.  The data size ranges from 6 gigabytes to 20 gigabytes.  Our training models such as logistic regression, SVM and neural nets, we compare with a bunch  of systems like TensorFlow, system, ML, CycloM and Bismarck.  So the compression ratio is basically we are better than snappy consistently and on par  with Gzip.  So sometimes we beat Gzip, sometimes Gzip beat us.  Training time, we use 30 minutes to train logistic regression on ImageNet.  20x faster than no compression, 19x faster than Gzip, 10x faster than snappy.  Training costs, so if you want to train a neural net on 150 gigabytes data within the  same time, for TensorFlow you need a very powerful machine which costs $900 per month  in Google Cloud while our method only needs a moderate machine like $100 or something  like that in Google Cloud.  So it saves me some money for the experiments, which is nice.  So that's pretty much it.  Summary, we made a machine learning training faster and cheaper.  This is done by a lossless compression algorithm plus a set of metrics execution algorithm that  work together.  If there are any questions, I'm happy to take it.
Li_Chen_Zeng_Kumar_Wu_Naughton_Patel_0_143.png Li_Chen_Zeng_Kumar_Wu_Naughton_Patel_144_227.png Li_Chen_Zeng_Kumar_Wu_Naughton_Patel_228_287.png Li_Chen_Zeng_Kumar_Wu_Naughton_Patel_288_803.png Li_Chen_Zeng_Kumar_Wu_Naughton_Patel_804_923.png Li_Chen_Zeng_Kumar_Wu_Naughton_Patel_924_2303.png Li_Chen_Zeng_Kumar_Wu_Naughton_Patel_2304_3167.png Li_Chen_Zeng_Kumar_Wu_Naughton_Patel_3168_3323.png Li_Chen_Zeng_Kumar_Wu_Naughton_Patel_3324_4451.png Li_Chen_Zeng_Kumar_Wu_Naughton_Patel_4452_5243.png Li_Chen_Zeng_Kumar_Wu_Naughton_Patel_5244_5795.png Li_Chen_Zeng_Kumar_Wu_Naughton_Patel_5796_8447.png Li_Chen_Zeng_Kumar_Wu_Naughton_Patel_8448_8807.png Li_Chen_Zeng_Kumar_Wu_Naughton_Patel_8808_17147.png Li_Chen_Zeng_Kumar_Wu_Naughton_Patel_17148_18695.png Li_Chen_Zeng_Kumar_Wu_Naughton_Patel_18696_19259.png Li_Chen_Zeng_Kumar_Wu_Naughton_Patel_19260_19319.png Li_Chen_Zeng_Kumar_Wu_Naughton_Patel_19320_19367.png Li_Chen_Zeng_Kumar_Wu_Naughton_Patel_19368_19643.png Li_Chen_Zeng_Kumar_Wu_Naughton_Patel_19644_19835.png Li_Chen_Zeng_Kumar_Wu_Naughton_Patel_19836_22031.png Li_Chen_Zeng_Kumar_Wu_Naughton_Patel_22032_24203.png Li_Chen_Zeng_Kumar_Wu_Naughton_Patel_24204_24335.png Li_Chen_Zeng_Kumar_Wu_Naughton_Patel_24336_24453.png
Hello, everyone. I'm Fong An. I'm currently at Google. So the agenda, I first going to talk about some overview and then the core technique, our compression and our metrics operation execution algorithm. Finally, I'm going to talk about results and some summary. So hopefully, I don't need to motivate too much that the mini batch gradient send is the algorithm we use for training machine models. The idea is essentially very simple. So you partition the data sets into a couple mini batches. So typically, each mini batch has tens of tuples or hundreds of tuples. Each time you sample a mini batch and you compute some metrics operations on it and you got the gradient and use the gradient to update the machine models. And then you go back. You keep doing like this until either your accuracy is satisfied or some termination condition is met. So this is great. This is essentially the algorithm we use right now. I think people use mini batch gradient send because it's faster than batch gradient send while you have to use all the tuples to update the model. So here you can see the green line is the mini batch gradient send. It's also more stable than pure stochastic gradient send where you only use a single tuple to update the model. Okay. But the problem we are facing now is mini batch gradient send can be really slow and expensive nowadays. So especially if you're working a domain in like computer vision or natural language processing, you know what I'm talking about, training model can take a couple of hours or even weeks and you probably need to spend a thousand dollars in cloud computing just for the experiments or something like that. This is also a problem that machine learning community are aware of and many people are talking about that. So I think there are many, many reasons for this problem. Mostly I think it's just we have more data now. So nowadays it's very easy that you have terabytes of data or petabytes of data and you cannot easily fit the data into memory. So you have to fetch the data from disk which is really, really expensive and our model is getting more and more complicated. For example, you may have very, very deep neural nets, many, many different layers and you have to compute those matrix operation. So my takeaway is don't do machine learning research. It's really expensive. No, I'm kidding. We have to solve this problem. So our solution is really a combo. It's a lossless compression algorithm plus a set of matrix operations that work together to make machine learning training faster and also cheaper. So now you may ask, what is so special about your compression and your matrix operation? Well, our compression is lossless. That means we have no accuracy loss. We guarantee the same result without using our technique. That also means it's orthogonal to all the lossy methods that machine learning community and database community has developed. For example, no precision training, all that kind of stuff, but you can use them together. Our compression also compresses really well. I do have experiment results to back that up. So the compression ratio is better than snappy and on par with GZIP. So it can reduce storage and IO cost a lot. Our matrix operation directly is executed on the compressed output. So we don't need to pay for the decompression cost, which is really expensive. You know, if you have GZIP and you decompress the bandwidth you get is only like 50 megabytes per second, which is really bad. But we don't need a decompression. More than that, we can also reduce the numerical computations. We actually have some theoretical guarantees that the complexity of the matrix operation is reduced by a factor of compression ratio. So in some sense, it's like all the storage redundancy are also avoided in the numerical computations. So this is just a little diagram. We compress the raw data. We get the compressed data. And we exclude a matrix operation on it. And we use computed gradients to optimize the models. Okay. So finally, we're going to talk about our compression. There are some design principles and lessons we learned from it. So basically, our compression has to be schema-aware. You cannot just use any compression which compresses a global bias. World compression actually knows the input is a table and we preserve the structure of the table. Physical encoding is a very simple technique that we use to encode the basic types, like integers and flow numbers. And turns out it plays a very important role in reducing the compressed output. There are three steps. Sparse encoding, logical encoding, and physical encoding. So someone actually wrote a blog about our work and I borrowed this graph from his blog. So thanks for the offer. So sparse encoding is really a very simple technique. We have this input table and we remove all the zeros from the table. For each value, we just prefix the calling index. So for example, the tuple 1 has a value of 5 and we prefix its calling index 3. So it becomes 3 colon 5. Our logical encoding is really the meat of this compression algorithm. And the key idea is that we find there are some repeating sub-sequences across tuples. For example, if you go back to this slide, you may find R2 and R3 are exactly the same and R1 and R2 share the same sub-sequence, which is 2 and 5. So we can dictionary encode these repeating sub-sequences to reduce the space. And furthermore, these dictionary entries can be stored as a prefix tree to further reduce the storage cost. And one interesting thing about the compression algorithm is that we don't need to store the prefix tree, which is essentially the dictionary entries. So it's like, okay, you have a dictionary encoding, but you don't need the dictionary at all. You can just get rid of it. The reason is that we can construct the dictionary on the fly. Well, if you guys know LZW, you know it's not surprising, but if you don't know it, it's kind of an interesting fact. So this is the actual algorithm. You can refer to the paper for more detail. The font is very small, so I don't expect you guys to read it. Okay, so here's an example of logical encoding. So yeah, exactly as I mentioned, we encode all the sub-sequences into the prefix tree. For example, for R2, 2, 2, 3, 5 is encoded as tree node 4 in the prefix tree. So tree node 4 is the last node in the prefix tree, and it represents 2, 2, 3, and 3.5. So now you can encode the sparse table as pointers pointing back to the prefix tree nodes. For example, R2 and R3 are just a single pointer pointing to the tree node 4. So physical encoding is just simple techniques. For example, we have bit packing for integers. So the idea is very simple. If you have a very small integer like 5, 6, or 8, you don't need four bytes to encode the integer. You only need a single byte. Value indexing is just another dictionary encoding for flow numbers. I have to mention all these techniques here are transparent. So you can easily switch to more advanced techniques for encoding these integers or flow numbers. And actually, SIGMOD and VLDB community has many, many great work. We just choose a very simple one. Okay. So now I'm going to talk about how we actually execute a matrix operation on the compressed output without the compression. So many machine learning models can be composed of matrix operations. For example, neural nets are essentially matrix times metric and there are many layers. Just regression SVM are like matrix times vector. As you can see, most of these metrics operation can execute on the compressed output without the compression. For example, general linear models and neural nets can execute on our compressed output directly. So how do we actually do that? So before I talk about these key ideas, there are some theoretical way to think about it. So compression, theoretically speaking, is like you have a linear transformation which maps the input table from the base space to a compression space. So you can do the same thing for the matrix operation, which is essentially another linear function. So you can use the same linear transformation which maps the matrix operation from the base space to the compression space. So this way, you never need to execute on the base space. You just execute everything on the compression space. So actually how we do that is using these key ideas that just give you a flavor of how that is possible. So we basically exploit the dictionary structure by memorizing the computed results and we exploit the prefix tree structure by dynamic programming. So I show you how we actually do it by this example. Suppose we want to compute a matrix times vector and this vector is here. It's very easy how you do that in the original space, right? Just do the inner product. So in our compression outputs, all you need is you do a BFS breadth-first search of the prefix tree and you compute the result, the inner product for each node. So it's very simple for the first three nodes because they only have a single node, right? For the node four, there is a very important trick here because essentially the result of its parent is already computed. So you don't need to start over. All you need is you fetch the result from its parent and append the result for the last node. So this is the dynamic programming which saves a lot of computation costs for us. And then for the table, for the dictionary encoded table, we just fetch all the results from prefix tree. There is no numerical computation here and we fetch all the results, we combine them together and we get the results. We have some theoretical guarantee which I briefly mentioned. So basically the complexity is reduced by a factor of compression ratio. Yeah, some results, so we use some real data sets like Minus and ImageNet. The data size ranges from 6 gigabytes to 20 gigabytes. Our training models such as logistic regression, SVM and neural nets, we compare with a bunch of systems like TensorFlow, system, ML, CycloM and Bismarck. So the compression ratio is basically we are better than snappy consistently and on par with Gzip. So sometimes we beat Gzip, sometimes Gzip beat us. Training time, we use 30 minutes to train logistic regression on ImageNet. 20x faster than no compression, 19x faster than Gzip, 10x faster than snappy. Training costs, so if you want to train a neural net on 150 gigabytes data within the same time, for TensorFlow you need a very powerful machine which costs $900 per month in Google Cloud while our method only needs a moderate machine like $100 or something like that in Google Cloud. So it saves me some money for the experiments, which is nice. So that's pretty much it. Summary, we made a machine learning training faster and cheaper. This is done by a lossless compression algorithm plus a set of metrics execution algorithm that work together. If there are any questions, I'm happy to take it.
batch gradient send is the algorithm we use for gradient send where you only use a single tuple to update the model. Okay. But the problem we are expensive and our model is getting more and more takeaway is don't do machine learning research. a combo. It's a lossless compression algorithm operation? Well, our compression is lossless. methods that machine learning community and operation directly is executed on the compressed decompression cost, which is really expensive. matrix operation is reduced by a factor of the compressed data. And we exclude a matrix encoding is a very simple technique that we use encoding is really a very simple technique. We a dictionary encoding, but you don't need the advanced techniques for encoding these integers this way, you never need to execute on the base don't need to start over. All you need is you costs for us. And then for the table, for the such as logistic regression, SVM and neural nets, we compare with a bunch of systems like metrics execution algorithm that work together.