arXiv:2307.07735v4 math.OC

구조적 선형 및 커널 서포트 벡터 머신을 위한 더 빠른 알고리즘

Faster Algorithms for Structured Linear and Kernel Support Vector Machines

Yuzhou Gu, Zhao Song, Lichen Zhang

제출 2023-07-15

한국어 초록

서포트 벡터 머신(SVM)을 포함하여 많은 기계 학습 문제는 이차 계획법이다. 일반적인 이차 계획 문제의 입력 크기는 $\Theta(n^2)$이며, 강한 지수 시간 가설(SETH)을 가정하면 목적 행렬이 양의 준정부호일 때 $O(n^{2-o(1)})$ 시간 알고리즘은 존재하지 않는다(Backurs, Indyk, and Schmidt, NeurIPS'17). 그러나 SVM은 $n$이 흔히 $d$보다 훨씬 큰 $d$차원의 $n$개 데이터 점으로 주어지며 등식 제약이 $O(1)$개뿐이다. 본 연구에서는 이차 목적 행렬의 저계수 분해가 주어지고, 선형 제약의 수가 작으며, 목적 함수의 계수와 어떤 최적해가 $\mathrm{poly}(n)$으로 유계이고, 어떤 가능해의 모든 원소가 $1/\mathrm{poly}(n)$과 $\mathrm{poly}(n)$ 사이에 있을 때 이차 계획 문제를 푸는 최초의 거의 선형 시간 알고리즘을 설계한다. $d$차원 데이터에 대한 선형 SVM의 경우, $(d+1)^{\omega-1}\le n$이고 데이터 점의 노름이 최대 $\mathrm{poly}(n)$이며 마진이 최소 $1/\mathrm{poly}(n)$일 때, 우리의 확률적 알고리즘은 기대 시간 $\widetilde O(nd^{(\omega+1)/2}\log(n/\epsilon))$에 실행된다. 여기서 $\omega<2.258$은 행렬 곱셈 지수이다. 이 알고리즘의 출력은 등식 제약을 근사적으로만 만족한다. 가우시안 커널 SVM의 경우, $d=O(\log n)$이고, 데이터셋 반지름의 제곱이 $o(\log n/\log\log n)$이며, 쌍대 변수가 $R\le\mathrm{poly}(n)$인 상자 $[0,R]^n$ 안에 있을 때, 우리의 확률적 알고리즘은 $\epsilon\ge 1/\mathrm{poly}(n)$인 임의의 정확도에 대해 기대 시간 $n^{1+o(1)}$에 실행된다. 또한 SETH를 가정할 때, 데이터셋 반지름의 제곱이 $\Omega(\log^2 n)$이면 편향항이 없는 문제에서 오차 $\exp(-\Theta(\log^2 n))$에 도달하기 위해 일부 입력에서 $\Omega(n^{2-o(1)})$ 시간이 필요함을 증명한다. 이는 차원 $d$와 데이터셋 반지름의 제곱 모두에서 기존 최선의 하계를 개선한다.

원문 초록

Many machine learning problems are quadratic programs, including Support Vector Machines (SVMs). A general quadratic program has input size $\Theta(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^{(\omega+1)/2}\log(n/\epsilon))$ when $(d+1)^{\omega-1}\le n$ and the data points have norms at most $\mathrm{poly}(n)$ and margin at least $1/\mathrm{poly}(n)$, where $\omega<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 $\epsilon\ge 1/\mathrm{poly}(n)$. We also prove that, assuming SETH, when the squared dataset radius is $\Omega(\log^2 n)$, $\Omega(n^{2-o(1)})$ time is required on some inputs to reach error $\exp(-\Theta(\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.

제출 이력

확인된 버전만 표시합니다. 전체 제출 이력은 arXiv 원문에서 확인하세요.

  1. arXiv:2307.07735v4제출 시각 미확인

함께 살펴볼 논문

공통 태그를 근거로 연결했습니다. 실제 인용 관계나 논문의 우수성을 뜻하지 않습니다.

공통 태그로 연결된 공개 논문이 아직 없습니다.

토론

이 논문과 연결된 포럼 글이 아직 없습니다.