跳到正文
研踪PaperTrail

论文库

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

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

全站更新概况

+979新增论文
+781其中 AI 相关
+119已有论文修订
+95新增 AI 导读

arXiv 最近完成扫描:2026-11-20 08:48 · 全站最近入库:2026-11-20 19:58各信源进度 →

统计口径与数据新鲜度

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

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

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

28,961 已收录论文24,030 AI 相关8,912 有修订112 HF 社区发现

浏览论文库

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

找到 8 篇论文 · 按版本更新时间排序上轮扫描起点 2026-11-20 08:46(北京时间)
版本更新 · 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

版本更新 · v3arXiv:2112.07628

Training Multi-Layer Over-Parametrized Neural Network in Subquadratic Time

Zhao Song, Lichen Zhang, Ruizhe Zhang

原文摘要

We consider the problem of training the last layer of a multi-layer over-parametrized neural network to minimize the empirical risk induced by a loss function. In the typical setting of over-parametrization, the network width $m$ is much larger than the data dimension $d$ and the number of training samples $n$ ($m=\mathrm{poly}(n,d)$), which induces a prohibitively large weight matrix $W\in\mathbb{R}^{m\times m}$ per layer above the first. Naively, when the layer inputs are dense, one has to pay $O(m^2)$ time to read the weight matrix and evaluate the neural network function in both forward and backward computation. To reduce the training cost per iteration, we propose a framework that uses $O(m^2nL)$ time in the initialization phase and achieves a truly subquadratic amortized cost per iteration in terms of $m$, i.e., $m^{2-Ω(1)}$ per iteration. The speedup comes from a sparse activation, a shifted ReLU whose threshold at each layer is proportional to the norm of the layer input. With this threshold every layer is positively homogeneous, so our convergence proof needs a width only polynomial in the depth $L$, in $n$ and in the inverse smallest kernel eigenvalues. The inputs of the trained layer are fixed and sparse. In this setting, simpler algorithms without a data structure reach the same cost per iteration, and maintaining the products of the last layer with its inputs lowers it to $mn^{ω-1+o(1)}$, where $ω$ is the matrix multiplication exponent. Our result can be viewed as an idealized model of maintaining a small amount of state on top of a frozen pre-trained model to speed up fine-tuning, a core procedure to deploy large language models (LLMs). Our guarantees assume that the frozen layers are random, and for a pre-trained model only the cost per iteration of maintaining these products carries over.

cs.LG · cs.DS

版本更新 · v4arXiv:2306.04169

Efficient Alternating Minimization with Applications to Weighted Low Rank Approximation

Zhao Song, Mingquan Ye, Junze Yin, Lichen Zhang

原文摘要

Weighted low rank approximation is a fundamental problem in numerical linear algebra, and it has many applications in machine learning. Given a matrix $M \in \mathbb{R}^{n \times n}$, a non-negative weight matrix $W \in \mathbb{R}_{\geq 0}^{n \times n}$, a parameter $k$, the goal is to output two matrices $X,Y\in \mathbb{R}^{n \times k}$ such that $\| W \circ (M - X Y^\top) \|_F$ is minimized, where $\circ$ denotes the Hadamard product. It naturally generalizes the well-studied low rank matrix completion problem. Such a problem is known to be NP-hard and even hard to approximate assuming the Exponential Time Hypothesis [GG11, RSW16]. Meanwhile, alternating minimization is a good heuristic solution for weighted low rank approximation. In particular, [LLR16] shows that, under mild assumptions, alternating minimization does provide provable guarantees. In this work, we develop an efficient and robust framework for alternating minimization that allows the alternating updates to be computed approximately. For weighted low rank approximation, this improves the cost of each iteration of [LLR16] from $\|W\|_0k^2$ to $\|W\|_0 k$ where $\|W\|_0$ denotes the number of nonzero entries of the weight matrix. At the heart of our framework is a high-accuracy multiple response regression solver together with a robust analysis of alternating minimization. We also replace the random initialization of [LLR16], whose claimed guarantee fails, by subspace iteration from a Gaussian start, so our total running time of $\widetilde O((\|W\|_0 k+nk^3)\log(1/ε))$ includes the initialization. In exchange, our guarantee needs the weight matrix to be within spectral distance $γn$ of the all-ones matrix for a $γ$ that is polynomially small in $n$.

cs.LG · math.OC

版本更新 · 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

版本更新 · v3arXiv:2304.03426

Convex Minimization with Integer Minima in $\widetilde O(n^4)$ Time

Haotian Jiang, Yin Tat Lee, Zhao Song, Lichen Zhang

原文摘要

Given a convex function $f$ on $\mathbb{R}^n$ whose set of minimizers is nonempty and closed, lies in a box of radius $R$ with $\log R\le\mathrm{poly}(n)$, and has integral extreme points, we give a randomized algorithm that finds an integral minimizer of $f$ with high probability using $O(n^2\log n+n\log R)$ calls to a separation oracle, $O(n+\log R/\log n)$ calls to an approximate shortest vector routine such as the LLL algorithm, and $O(n^4\log(nR)\log\log n)$ other arithmetic operations. The previous best polynomial time algorithm [Jiang, SODA 2021, JACM 2022] achieves $O(n(n\log\log n/\log n+\log R))$ oracle complexity, but its overall runtime is at least $\widetildeΩ(n^8)$. We obtain our speedup by combining a variant of the volumetric center cutting plane method of [Vaidya, FOCS 1989], run on the hybrid barrier of [Lee, Sidford, Wong, FOCS 2015] with the fast implementation of [Jiang, Lee, Song, Wong, STOC 2020], and a variant of the LLL algorithm that reduces segments of consecutive basis vectors recursively. The method runs in blocks, so that shortest vectors are computed only $O(n+\log R/\log n)$ times, and each computation takes $O(n^3\log^3 n)$ arithmetic operations in exact arithmetic. For submodular function minimization, our result implies an algorithm using $O(n^3\log n)$ calls to an evaluation oracle and $O(n^4\log^3 n)$ arithmetic operations in total. Its oracle complexity is better than that of the algorithms of [Lee, Sidford, Wong, FOCS 2015] and [Dadush, Végh, Zambelli, SODA 2018, MOR 2021], which had the best running time before this work.

cs.DS · cs.DM · math.OC

版本更新 · v2arXiv:2509.16915

Differential Privacy for Euclidean Jordan Algebra with Applications to Private Symmetric Cone Programming

Zhao Song, Jianfei Xue, Lichen Zhang

原文摘要

In this paper, we study differentially private mechanisms for functions whose outputs lie in a Euclidean Jordan algebra. Euclidean Jordan algebras capture many important mathematical structures and form the foundation of linear programming, second-order cone programming, and semidefinite programming. Our main contribution is a generic Gaussian mechanism for such functions, with sensitivity measured in $\ell_2$, $\ell_1$, and $\ell_\infty$ norms. Notably, this framework includes the important case where the function outputs are symmetric matrices, and sensitivity is measured in the Frobenius, nuclear, or spectral norm. We further derive private algorithms for solving symmetric cone programs under various settings, using a combination of the multiplicative weights update method and our generic Gaussian mechanism. As an application, we present differentially private algorithms for semidefinite programming, resolving a major open question posed by [Hsu, Roth, Roughgarden, and Ullman, ICALP 2014].

math.OC · cs.CR · cs.DS · cs.LG

版本更新 · v2arXiv:2608.26552

Hadamard Flattening and Gaussian Pooling Sketch for Least Squares with Coordinate-wise Guarantee

Zhao Song, Lichen Zhang

原文摘要

Randomized sketch-and-solve algorithms accelerate overconstrained $\ell_2$ regression by replacing the input with a much smaller, randomly projected problem. While standard subspace embeddings nearly preserve the regression cost, coordinate-wise accuracy is more delicate: rather than the objective value, we want the solution vector itself to be close to the optimum in $\ell_\infty$ norm. Specifically, we seek $x'\in\mathbb{R}^d$ with $\|x'-x^\star\|_\infty\leq\fracε{\sqrt d}\|Ax^\star-b\|_2\|A^\dagger\|_{\mathrm{op}}$, where $A\in\mathbb{R}^{n\times d}$ is the design matrix, $b\in\mathbb{R}^n$ the label vector, $x^\star$ the optimal solution and $A^\dagger$ the pseudo-inverse of $A$. Price, Song and Woodruff introduced this problem and claimed that the subsampled randomized Hadamard transform (SRHT) with $O(ε^{-2}d^{1+Θ(\sqrt{\log\log n/\log d})})$ rows achieves this guarantee; we point out a gap in the proof. Song, Ye, Yin and Zhang later claimed $O(ε^{-2}d\log^3 n)$ rows, but their proof relies on an independence assumption that does not hold in general, and we exhibit an explicit instance on which it fails. To achieve a truly nearly-linear-in-$d$ row count, we introduce a new fast, dense randomized transform combining a randomized Hadamard flattening, a random permutation, and balanced, disjoint Gaussian pooling. Conditioned on the Hadamard-and-permutation stage, the sketched problem becomes an exact Gaussian regression whose noise is independent of the entire sketched design, exactly what Song, Ye, Yin and Zhang's argument was missing. Our sketch yields the $\ell_\infty$ guarantee with $m=O(ε^{-2}d\log d)$ rows, using one Hadamard pass with padded internal dimension $N=\widetilde{O}(n+ε^{-2}d^3)$. It is also efficient to apply: $(SA,Sb)$ can be computed in $O(Nd\log N)=\widetilde{O}(nd+ε^{-2}d^4)$ time.

cs.DS · cs.LG · stat.ML

版本更新 · v2arXiv:2509.16801

Sublinear Time Quantum Sensitivity Sampling

Zhao Song, David P. Woodruff, Lichen Zhang

原文摘要

We present a unified quantum sensitivity sampling framework that streamlines coreset construction for many classical approximation problems, significantly speeding up clustering, regression, and low-rank approximation. We assume $n,d\geq\mathrm{poly}(k/ε)$ and, for regression, $n\geq\mathrm{poly}(d)$: - $k$-median/$k$-means: For $n$ points in $\mathbb{R}^d$, we build an $ε$-coreset of input points of size $\tilde O(k^{4/3}ε^{-2})$ (resp. $\tilde O(k^{3/2}ε^{-2})$) in time $\tilde O(ε^{-1}n^{0.5}dk^{1.67})$ (resp. $\tilde O(ε^{-1}n^{0.5}dk^{1.75})$). Our better $d$- and linear $1/ε$-dependence improve on [Xue, Chen, Li and Jiang, ICML'23] for $d\geqΩ(k^{7/3})$ (resp. $Ω(k^{2.5})$). - $\ell_p$ regression: For $\min_x\|Ax-b\|_p$, $A\in\mathbb{R}^{n\times d}$, we build an $ε$-coreset of size $\tilde O_p(d^{\max\{1,p/2\}}ε^{-2})$ in time $\tilde O_p(n^{0.5}d^{1.5}ε^{-1})$ for $p\leq 2$ and $\tilde O_p(n^{0.5}d^{p/4+1}(ε^{-1}+d^{0.5}))$ for $p>2$, matching [Liu and Ji, ICML'26] for $p\leq 2$ and improving on the prior best quantum sampling approach [Apers and Gribling, SICOMP'26] for all $p>2$. - Low-rank approximation: We give the first quantum sublinear-time algorithm for Frobenius-norm rank-$k$ approximation of $A\in\mathbb{R}^{d\times n}$ free of data-dependent parameters, running in $\tilde O(n^{0.5}dk^{0.5}ε^{-0.5})$ time with factored output (plus $\tilde O(nk^2ε^{-2})$ to materialize them). We also give sublinear algorithms for kernel and tensor variants. - Lower bound: For generic sensitivity sampling with total sensitivity $S$, any quantum algorithm outputting an $ε$-coreset of size $o(\sqrt{nS})$ needs $Ω(\sqrt{nS})$ queries, so our query complexity is optimal up to $\mathrm{poly}(ε^{-1},\log n)$ and VC-dimension factors.

cs.DS · cs.LG · quant-ph