Before revision:  We consider classical sketching algorithms which first  compress data by multiplication with a random "sketch matrix". Our work improves and extends the "learned sketch " paradigm , in which sketch matrices are optimized to yield better expected performance.This technique has only been used for a suboptimal variant of sketched low-rank decomposition (LRD). Our work extends the problem coverage to optimal sketched LRD, least-squares regression (LS), and ] k-means clustering .
After revision:  We consider classical sketching algorithms which first compress data by multiplication with a random sketch matrix, and then apply the sketch to quickly solve an optimization problem, e.g., low rank approximation. In the learning-based sketching paradigm proposed by Indyk et al. ] k-means clustering .