Subspace Embedding and Linear Regression with Orlicz Norm

2018/06/17 by Andoni, Alexandr, Lin, Chengyu, Sheng, Ying +2 · 1 citation
#Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #Machine Learning (cs.LG)

paper · doi:10.48550/arxiv.1806.06430

Abstract

We consider a generalization of the classic linear regression problem to the case when the loss is an Orlicz norm. An Orlicz norm is parameterized by a non-negative convex function G:ℝ₊→ℝ₊ with G(0)=0: the Orlicz norm of a vector x∈ℝⁿ is defined as ‖x‖_G=inf\α>0\large|∑_i=1ⁿ G(|x_i|/α)≤ 1\. We consider the cases where the function G(⋅) grows subquadratically. Our main result is based on a new oblivious embedding which embeds the column space of a given matrix A∈ℝ^{n× d} with Orlicz norm into a lower dimensional space with ℓ₂ norm. Specifically, we show how to efficiently find an embedding matrix S∈ℝ^{m× n},m

Cited by

• Generalized Sobolev IPM for Graph-Based Measures

Related

• Efficient Symmetric Norm Regression via Linear Sketching
• Subspace Embeddings and ℓ_p-Regression Using Exponential Random Variables
• Subspace Embeddings Under Nonlinear Transformations
• Subspace Fitting Meets Regression: The Effects of Supervision and Orthonormality Constraints on Double Descent of Generalization Errors
• Conditional mean embeddings as regressors - supplementary