A Nearly-Optimal Bound for Fast Regression with ℓ_∞ Guarantee
24. července 2023
Řečníci
Mingquan Ye
Řečník · 0 sledujících
Lichen Zhang
Řečník · 0 sledujících
O prezentaci
Given a matrix A∈ℝ^n× d and a vector b∈ℝ^n, we consider the regression problem with ℓ_∞ guarantees: finding a vector x'∈ℝ^d such that ||x'-x^* ||_∞≤ϵ/√(d)· ||Ax^*-b||_2· ||A^†|| with x^* being the optimal solution to the regression ||Ax-b||_2. One popular approach for solving ℓ_2 regression problem is via sketching: picking a structured random matrix S∈ℝ^m× n with m≪ n and SA can be quickly computed, solve the “sketched” regression problem x'=argmin ||SAx-Sb||_2.In this paper, we show that in order to obtain such ℓ_∞ guarantee for ℓ_2 regression, one has to use sketching matrices that are dense. To the best of our knowledge, this is the first user case in which dense sketching matrices are necessary. On the algorithmic side, we prove that, there exists a distribution of dense sketching matrices with m=ϵ^-2dlog^3(n/δ) such that solving the sketched regression problem gives the ℓ_∞ guarantee, with probability at least 1-δ. Moreover, the matrix SA can be computed in time O(ndlog n). Our row count is nearly-optimal up to logarithmic factors, and significantly improves the result in [Price, Song and Woodruff, ICALP'17], in which m=Ω(ϵ^-2d^1+γ) for γ∈ (0, 1) is required.Moreover, we develop a novel analytical framework for ℓ_∞ guarantee regression that utilizes the Oblivious Coordinate-wise Embedding (OCE) property introduced in [Song and Yu, ICML'21]. Our analysis is much simpler and more general than that of [Price, Song and Woodruff, ICALP'17]. Leveraging this framework, we extend the ℓ_∞ guarantee regression result to dense sketching matrices for computing fast tensor product of vectors.Given a matrix A∈ℝ^n× d and a vector b∈ℝ^n, we consider the regression problem with ℓ_∞ guarantees: finding a vector x'∈ℝ^d such that ||x'-x^* ||_∞≤ϵ/√(d)· ||Ax^*-b||_2· ||A^†|| with x^* being the optimal solution to the regression ||Ax-b||_2. One popular approach for solving ℓ_2 regression problem is via sketching: picking a structured random matrix S∈ℝ^m× n with m≪ n and SA can be quickly computed, solve the “sketched” regression problem x'=argmin ||SAx-Sb||_2.In this paper, we show that in o…
Baví vás formát? Nechte SlidesLive zachytit svou akci!
Profesionální natáčení a streamování po celém světě.
Sdílení
Doporučená videa
Prezentace na podobné téma, kategorii nebo přednášejícího
Existence, Stability and Scalability of Orthogonal Convolutional Neural Networks
Zhlédnout později
Scalable Safe Policy Improvement via Monte Carlo Tree Search
Zhlédnout později
Optimal LP Rounding and Linear-Time Approximation Algorithms for Clustering Edge-Colored Hypergraphs
Zhlédnout později
Internet Explorer: Targeted Representation Learning on the Open Web
Zhlédnout později
Phase-aware Adversarial Defense for Improving Adversarial Robustness
Zhlédnout později
Da-Wei Zhou, …
Nearly-tight Bounds for Deep Kernel Learning
Zhlédnout později
Yi-Fan Zhang, …