Apply Learned Sketch to Iterative Hessian Sketch

Jiangwei Chen ； Bai Lin Ji ； Yuankai Sun ； Meier Chen

《International Core Journal of Engineering》 7卷9期 (2021/09) Pp. 375-378

https://doi.org/10.6919/ICJE.202109_7(9).0051

摘要

The goal of this experiment is to study Randomize Sketch Methods and combine the Learned Sketch with Hessian Sketch to produce optimization results that are both fast and accurate. Assess different types of Random Sketch Methods then take the most accurate one and apply Iterative Hessian Sketch method to minimize the function: X_(OPT)=argmin_(xєc)1/2 || Ax-b||2/2, The new method Iterative Hessian Sketch, which uses a random projection dimension proportional to the statistical complexity of the least-squares minimizer. This method is tested both on unconstrained least square problem and LASSO. Finally compare the test results to other famous Sketch Methods in terms of accuracy.

關鍵字

Random Projection ； Lasso ； Convex Optimization ； Count Sketch ； Learned Sketch ； Iterative Hessian Sketching

參考文獻

Cormode G and Dickens C. Public on October 30, 2019. Iterative Hessian Sketch in Input Sparsity. Machine Learning (stat.ML) p3-4.

Pilanci M and Martin J. Public on November 3, 2014. Iterative Hessian sketch: Fast and accurate solution approximation for constrained least-squares. P11-12.

Yi Li, Honghao Lin, David P. Woodruff (2021). Learning-Augmented Sketches for Hessians. https:// openreview. net/forum?id=Lnomatc-1s

Simin Liu, Tianrui Liu, Ali Vakilian, Yulin Wan, David P. Woodruff (July 20, 2020). Learned Sketches for Randomized Numerical Linear Algebra. P3-4. https://arxiv.org/abs/2007.09890

Meifan Zhang, Hongzhi Wang, Jianzhong Li, Hong Gao. Learned sketches for frequency estimation. Inf. Sci. 507: 365-385 (2020) https://dblp.org/rec/journals/isci/ZhangWLG20.html