跳到正文
研踪PaperTrail

论文库

检索计算机领域论文,按研究方向、作者或关键词筛选。

部分采集异常
正在读取账号与研究记录…

全站更新概况

+197新增论文
+151其中 AI 相关
+16已有论文修订
+91新增 AI 导读

arXiv 最近完成扫描:2026-11-22 08:44 · 全站最近入库:2026-11-21 12:19各信源进度 →

统计口径与数据新鲜度

统计 2026-11-21 09:59 — 2026-11-22 09:59(北京时间) · 点击数字查看对应简报;AI 相关包含在新增论文内。

最近完成检查:2026-11-22 08:44最近发现新增版本:2026-11-21 12:19库内论文最新更新时间:2026-11-20 02:59

每分钟刷新已保存的数据。空检查不代表采集异常;新收录可能包含历史论文。AI 导读按新增版本计数。

29,158 已收录论文24,181 AI 相关8,992 有修订112 HF 社区发现

浏览论文库

时间范围跟随排序:版本更新、本站收录或首次发表。最新收录可能包含历史论文。部分信源异常,查看状态 →

找到 2 篇论文 · 按版本更新时间排序上轮扫描起点 2026-11-22 08:42(北京时间)
版本更新 · v4arXiv:2307.07735

Faster Algorithms for Structured Linear and Kernel Support Vector Machines

Yuzhou Gu, Zhao Song, Lichen Zhang

原文摘要

Many machine learning problems are quadratic programs, including Support Vector Machines (SVMs). A general quadratic program has input size $Θ(n^2)$, and assuming the Strong Exponential Time Hypothesis (SETH), no $O(n^{2-o(1)})$ time algorithm exists when the objective matrix is positive semidefinite (Backurs, Indyk, and Schmidt, NeurIPS'17). SVMs, however, are given by $n$ data points of dimension $d$, often much smaller than $n$, and have only $O(1)$ equality constraints. In this work, we design the first nearly-linear time algorithm for solving quadratic programs whenever a low-rank factorization of the quadratic objective matrix is given, the number of linear constraints is small, the coefficients of the objective and some optimal solution are bounded by $\mathrm{poly}(n)$, and some feasible point has all entries between $1/\mathrm{poly}(n)$ and $\mathrm{poly}(n)$. For linear SVM on $d$-dimensional data, our randomized algorithm runs in expected time $\widetilde O(nd^{(ω+1)/2}\log(n/ε))$ when $(d+1)^{ω-1}\le n$ and the data points have norms at most $\mathrm{poly}(n)$ and margin at least $1/\mathrm{poly}(n)$, where $ω<2.258$ is the matrix multiplication exponent. Its output satisfies the equality constraint only approximately. For Gaussian kernel SVM, when $d=O(\log n)$, the squared dataset radius is $o(\log n/\log\log n)$ and the dual variables lie in a box $[0,R]^n$ with $R\le\mathrm{poly}(n)$, our randomized algorithm runs in expected time $n^{1+o(1)}$ for any accuracy $ε\ge 1/\mathrm{poly}(n)$. We also prove that, assuming SETH, when the squared dataset radius is $Ω(\log^2 n)$, $Ω(n^{2-o(1)})$ time is required on some inputs to reach error $\exp(-Θ(\log^2 n))$ for the program without the bias term. This improves upon the prior best lower bound in both the dimension $d$ and the squared dataset radius.

math.OC · cs.LG · stat.ML

版本更新 · v4arXiv:2302.11068

Low Rank Matrix Completion via Robust Alternating Minimization in Nearly Linear Time

Yuzhou Gu, Zhao Song, Junze Yin, Lichen Zhang

原文摘要

Given a matrix $M\in \mathbb{R}^{m\times n}$, the low rank matrix completion problem asks us to find a rank-$k$ approximation of $M$ as $UV^\top$ for $U\in \mathbb{R}^{m\times k}$ and $V\in \mathbb{R}^{n\times k}$ by only observing a few entries specified by a set of entries $Ω\subseteq [m]\times [n]$. In particular, we examine an approach that is widely used in practice -- the alternating minimization framework. Jain, Netrapalli, and Sanghavi [JNS13] showed that if $M$ has incoherent rows and columns, then alternating minimization provably recovers the matrix $M$ by observing a nearly linear in $n$ number of entries. While the sample complexity has been subsequently improved [GLZ17], alternating minimization steps are required to be computed exactly. This hinders the development of more efficient algorithms and fails to depict the practical implementation of alternating minimization, where the updates are usually performed approximately in favor of efficiency. In this paper, we take a major step towards a more efficient and error-robust alternating minimization framework. To this end, we develop an analytical framework for alternating minimization that can tolerate a moderate amount of errors caused by approximate updates. Moreover, our algorithm runs in time $\widetilde O(|Ω| k)$, which is nearly linear in the time to verify the solution while preserving the sample complexity. This improves upon all prior known alternating minimization approaches which require $\widetilde O(|Ω| k^2)$ time.

cs.LG · cs.DS · math.OC · stat.ML