线性草图的高效对称范数回归

Oct, 2019

Efficient Symmetric Norm Regression via Linear Sketching

Zhao Song, Ruosong Wang, Lin F. Yang, Hongyang Zhang, Peilin Zhong

TL;DR提供了高效的算法来解决超定的线性回归问题，其中损失函数是对称范数（在符号反转和坐标置换下不变的范数），当损失函数为 Orlicz 范数时，算法产生一个 (1+ε)- 近似解，在输入稀疏时间内改进了先前已知的算法。

Abstract

We provide efficient algorithms for overconstrained linear regression problems with size $n \times d$ when the loss function is a symmetric norm (a norm invariant under sign-flips and coordinate-permutations). An

overconstrained linear regression symmetric norm orlicz norms input-sparsity time numerical linear algebra

发现论文，激发创造

用 Orlicz 范数进行子空间嵌入和线性回归

本文针对经典线性回归问题进行推广，研究了 Orlicz 范数的损失函数，并提出了一种新的盲嵌入，用于将具有 Orlicz 范数的矩阵空间嵌入到具有二范数的较低维空间，从而得到回归问题和低秩矩阵逼近问题的近似算法。

Jun, 2018

稀疏线性回归的最优草图界限

该论文探讨了在不同的损失函数下，对于 $k$- 稀疏线性回归的随机抽样方法以及其误差上界，其中包括了稀疏的逻辑回归和 ReLU 回归等损失函数，并且给出了相应的维度约束条件。

Apr, 2023

正则化数据拟合的更锐利界限

研究针对线性回归、低秩逼近和规范相关分析的正规化变体的矩阵草图方法，主要关注能够保留规范问题目标函数值的草图技术，为 ridge regularization 在这些问题上展示了算法资源界限，其中统计维度总是小于秩，并随着规范化程度的增加而减少

Nov, 2016

岭回归的算法和下界草图

提出了基于草图的迭代算法，用于解决均方误差损失函数加正则项的岭回归问题，针对早期工作中的子空间嵌入要求而使用更弱的近似矩阵乘法保证，为核岭回归提供了更快的算法，同时我们对均方误差损失函数的算法框架提出了切实可行的草图规模下限。

Apr, 2022

迭代 Hessian 草图：约束最小二乘问题的快速准确解近似

本文研究了随机草图方法，以近似解决带有一般凸约束的最小二乘问题，并提出了一种名为迭代 Hessian 草图的新方法，同时提供了数值模拟实验，包括面部表情分类实验。

Nov, 2014

一般对称范数的近似最近邻

每个对称赋范空间都可以采用双对数逼近的方式建立有效的最近邻搜索数据结构。我们的算法的主要技术是一个对称范数到低维度 “top-k” 范数的迭代乘积的低扭曲嵌入。同时，我们证明这些方法无法推广到一般范数。

Nov, 2016

关于鲁棒线性回归的高效算法及下界

研究了高维线性回归在对抗性污染下的稳健模型问题，并针对从高斯分布生成的未被修正的样本的基本情况给出了几乎最紧的上界和计算下界。

May, 2018

对异常数据鲁棒的回归的高效算法

本文首次给出了一个多项式时间算法，用于在示例和标签中对抗性堕落下执行线性或多项式回归，并基于 SoS 方法提出了一种自然的凸松弛方法来解决非凸优化问题。

Mar, 2018

用于具有尖锐保证的凸和非凸正则化最小二乘的素描

我们提出了一种用于大规模优化问题的快速草图算法，可以处理凸或非凸正则化函数的正则化优化问题。我们给出了原始问题与草图问题的近似误差的一般理论结果，并在温和条件下获得了稀疏信号估计的极小化速率。此外，我们还提出了一种迭代草图算法，可以指数级地减小近似误差。实验结果证明了我们的算法的有效性。

Nov, 2023

用于安全编码回归的迭代素描

本文提出了一种分布式加速线性回归的方法，通过使用随机化草稿技术和改善异步系统中的顽固者韧性来确保安全性，同时应用随机齐次正交矩阵和子采样块来安全获取信息和减少回归问题的维度。

Aug, 2023