폴리토프 거리를 위한 보호된 블록 전이: 명시적 상수를 갖는 선형 수렴 및 SVM 학습을 위한 갭 인증 스크리닝
Guarded Block Transfers for Polytope Distance: Linear Convergence with Explicit Constants and Gap-Certified Screening for SVM Training
한국어 초록
하드 마진(hard-margin) SVM 학습은 두 볼록 껍질(convex hull) 사이의 거리 문제이며, 삼각형 알고리즘(Triangle Algorithm, TA)은 이를 인증된 쌍대성 갭(duality gap)과 함께 해결합니다. 본 논문에서는 보호된 블록 전이(guarded block transfers)를 제안합니다. 이는 스캔당 $k$개의 Mitchell–Demyanov–Malozemov(MDM) 전이를 하나의 정확한 선 탐색(line search)으로 집약하며, 점의 수 $n$과 무관한 비용으로 단일 최적 전이와의 비교를 통해 보호되고, 선행 전이가 용량 제한(capacity-clipped)될 경우 어웨이 스텝(away step)으로 대체됩니다. 목적 함수가 $1$-강볼록($1$-strongly convex)인 민코프스키 차이(Minkowski-difference) 폴리토프에서, 우리는 조합적 스왑 스텝(swap-step) 한계 없이 명시적 상수를 갖는 전역 선형 수렴(global linear convergence)을 증명합니다. 단계당 수축(per-step contraction)은 $k$와 무관하며 드롭 횟수 한계(drop-count bound)만이 $k$에 따라 증가하므로, 스캔 절감은 증명된 것이 아니라 측정된 것인 반면 집약은 증명 가능하게 안전합니다. TA 인증서는 Frank–Wolfe 갭을 현재 거리로 나눈 값이므로 갭-안전 스크리닝(gap-safe screening)이 적용되며, 기하학적 요소의 로그 인수를 제외하고 최적 페이스(optimal face) 바깥의 모든 가중치 0인 점을 제거한 후의 반복 횟수를 $O\!\left(\tfrac{k}ρ\log\tfrac{1}τ\right)$로 제한합니다. 여기서 $ρ$는 수렴 속도 상수이고 $τ$는 최적 페이스 마진입니다. 5개의 LIBSVM 벤치마크에서, 본 논문의 제출본보다 더 공정한 베이스라인들을 적용했을 때 제안하는 솔버는 양쪽 모두 수렴하는 모든 경우에서 베이스라인과 4~5자리까지 일치하며, 희소 지지(sparse-support) 하드 마진에서는 LIBSVM과 대등하고 자체 블렌디드 쌍별 조건부 그래디언트(BPCG)보다 우수합니다. 그러나 자체 전체 캐시 순차적 최소 최적화(SMO) 코드는 커널 $L_2$ 마진에서 이와 대등하거나 능가하고, LIBLINEAR의 쌍대 솔버는 분리 가능한 $L_2$ 마진에서 최대 $4.5\times$ 더 빠르며, 제안하는 솔버는 밀집 지지(dense-support) $L_2$ 마진에서는 LIBLINEAR의 뉴턴(Newton) 솔버보다, 거의 맞닿는 커널 껍질에서는 LIBSVM보다 1~3자릿수 더 느립니다. 이 알고리즘의 강점은 속도가 아니라 인증서에 있습니다.
원문 초록
Hard-margin SVM training is the distance problem between two convex hulls, which the Triangle Algorithm (TA) solves with a certified duality gap. We propose \emph{guarded block transfers}: $k$ Mitchell--Demyanov--Malozemov (MDM) transfers per scan are aggregated into one exact line search, guarded by a comparison with the single best transfer at a cost independent of the number of points $n$, and replaced by an away step when the leading transfer is capacity-clipped. On the Minkowski-difference polytope, where the objective is $1$-strongly convex, we prove global linear convergence with explicit constants and no combinatorial swap-step bounds; the per-step contraction is $k$-independent and only the drop-count bound grows with $k$, so aggregation is provably safe while the saving in scans is measured, not proved. Since the TA certificate is the Frank--Wolfe gap divided by the current distance, gap-safe screening applies, and we bound the iteration after which it has removed every zero-weight point off the optimal faces by $O\!\left(\tfrac{k}ρ\log\tfrac{1}τ\right)$ up to logarithmic factors in the geometry, $ρ$ the rate constant and $τ$ the optimal-face margin. On five LIBSVM benchmarks, with fairer baselines than our submission, the solver matches the baselines to four or five digits wherever both converge, ties LIBSVM on sparse-support hard margins and beats our blended pairwise conditional gradients (BPCG). But our full-cache sequential minimal optimisation (SMO) code ties or beats it on kernel $L_2$ margins, LIBLINEAR's dual solver is up to $4.5\times$ faster on the separable $L_2$ margin, and our solver is one to three orders of magnitude slower than LIBLINEAR's Newton solver on dense-support $L_2$ margins and than LIBSVM on a nearly touching kernel hull. Its edge is the certificate, not speed.
제출 이력
확인된 버전만 표시합니다. 전체 제출 이력은 arXiv 원문에서 확인하세요.
함께 살펴볼 논문
공통 태그를 근거로 연결했습니다. 실제 인용 관계나 논문의 우수성을 뜻하지 않습니다.
강볼록 집합 상의 무작위화 선형 오라클 최적화에 대한 하한
Lower Bounds for Randomized Linear-Oracle Optimization over Strongly Convex Sets
존 타원체 근사에서 평균화를 넘어서: 레버리지 점수 모델에서의 고정밀 알고리즘
Beyond Averaging in John Ellipsoid Approximation: High-Accuracy Algorithms in the Leverage-Score Model
대칭 다면체(symmetric polytope) $P=\{\mathbf{x}\in\mathbb{R}^d:\|\mathbf{A}\mathbf{x}\|_\infty\le1\}$ ($\mathbf{A}\in\mathbb{R}^{n\times d}$)의 존 타원체(John ellipsoid)는 Cohen, Cousins, Lee 및 Yang (COLT 2019)부터 그 후속작들 [WY24, CLS+25]에 이르는 긴 계보의 레버리지 점수(leverage-score) 알고리즘들을 통해 계산되며, 이들은 모두 $\Theta(\varepsilon^{-1}\log(n/d))$ 반복(iteration) 내에 $(1+\varepsilon)$-근사에 도달합니다. 우리는 이 복잡도를 현대의 연구들이 혼동하는 세 가지 비용(인증(certification), 식별(identification), 정확도(accuracy))으로 분리하고, 역사적인 $\varepsilon^{-1}$ 항이 첫 번째 비용(인증)에만 있음을 밝혀냅니다. 이와 동등한 D-최적 설계(D-optimal-design) 형태 $\min_{\mathbf{p}\in\Delta_n}-\log\det(\sum_i p_i\mathbf{a}_i\mathbf{a}_i^\top)$에서 레버리지 점수 오라클(leverage-score oracle)은 정확히 1차 오라클(first-order oracle)이며, $(1+\varepsilon)$-존 보장은 Frank-Wolfe 간격(Frank-Wolfe gap) $g(\mathbf{p})\le\varepsilon d$에 해당합니다; 이러한 대응 관계를 통해 비용들이 분리됩니다. $\varepsilon^{-1}$은 인증 인공물(artifact)입니다: 해당 계보 전반에 걸쳐 사용되는 인증서인 반복(iterates)의 균일한 평균은 각 반복(iteration)이 얼마나 저렴하게 만들어지든 간에 정확히 $\Theta(1/T)$의 간격을 가집니다. 대신 마지막 반복점(last iterate)을 목표로 삼는다면 동일한 오라클은 빠릅니다: $\varepsilon$와 무관한 설정 $C(\mathbf{A})$ 이후, 웜 스타트된 가속화된 방법은 $C(\mathbf{A})+O(\sqrt{\kappa}\log(1/\varepsilon))$ 번의 질의(query)로 보장 조건에 도달하며, 최적 면(optimal face)이 식별되면 면상 문제(facial problem)는 오라클이 헤시안(Hessian)을 정확히 복원하는 비제약 자기 콩코드 최소화(unconstrained self-concordant minimization)가 되므로 감쇠 뉴턴(damped Newton)은 $O(\log\log(1/\varepsilon))$ 단계만 필요하며, 총 $C(\mathbf{A})+O(d^2\log\log(1/\varepsilon))$ 번의 질의가 소요됩니다. 따라서 정확도 의존성은 $\varepsilon$와 무관하고 조건(condition)에 의존적인 설정 이후 이중 로그(double logarithmic) 형태를 띱니다; 남아있는 개방 문제는 식별 비용(최적 면에 도달하기 위한 조건 무관(condition-free) 상계)과 하한(lower bounds)입니다. 정확도는 장애 요소가 아닙니다.
기하학적 구조를 고려한 다중 목적 최적화: 엔트로피 기반 가중치 업데이트를 적용한 노름 제약 오라클
Geometry-Aware Multi-Objective Optimization: Norm-Constrained Oracles with Entropic Weight Updates
다중 경사하강법(Multiple-gradient descent)은 일반적으로 유클리드 기하학에서 공식화되는 반면, 행렬 인식 옵티마이저는 다른 노름(norm)에 의해 유도된 방향을 사용합니다. 본 논문에서는 노름 제약이 있는 선형 최소화 오라클과 태스크 가중치의 엔트로피 업데이트를 결합한 단일 루프 다중 목적 최적화 기법을 분석합니다. 유한 차원 노름 쌍에 대해 결정론적 환경에서 $O(T^{-1/2})$의 에르고딕 정지성(ergodic stationarity) 수렴 속도를 확립하며, 비정규화된 경우 평활성(smoothness) 및 하한 유계성으로부터 필요한 궤적 그래디언트 경계를 유도합니다. 확률적 그래디언트와 유계 그래디언트 가정 하에서는 단일 지속 혼합 그래디언트 모멘텀 버퍼를 통해 선행 항이 태스크 수에 명시적으로 의존하지 않는 $O(T^{-1/4})$ 수렴 속도를 산출합니다. 또한 임의의 유계 그래디언트 시퀀스에 대해 내부 가중치 목적식의 정적 리그릿(static regret)을 확립하고, 엔트로피 정규화와 가중치 하한(weight floor)을 적용하여 궤적 그래디언트 경계를 조건으로 에르고딕 정지성을 유지하면서 웜업(burn-in) 이후 반복별 내부 갭 제어를 달성합니다. 최적의 혼합 그래디언트는 스펙트럼 및 부호 기하학에서 유일하지 않을 수 있으므로, 선택에 독립적인 내부 갭의 필요성을 부여합니다. 본 분석은 동시 연구인 MOON에서 연구된 스펙트럼 구성을 일반적인 노름으로 확장합니다. 실험을 통해 기존 멀티태스크 옵티마이저와 제안 방법을 비교하고 오라클, 가중치 부여 및 모멘텀 선택을 검토합니다.
완전 양의 리프팅을 통한 선형 신경망의 정확한 볼록 재구성
Exact Convex Reformulations of Linear Neural Networks via Completely Positive Lifting
본 논문에서는 제곱 손실(squared loss) 하에서 심층 선형 신경망(deep linear neural network)의 학습 문제가 일반화된 완전 양(completely positive)의 원뿔 위로 리프팅된 공간에서 정확한 볼록 재구성(exact convex reformulation)을 허용함을 보인다. 이 재구성은 원래의 비볼록 문제와 동일한 최적값을 가지며 리프팅된 변수에 대해 선형이고, 모든 비볼록성은 원뿔 제약조건 내에 인코딩된다. 리프팅된 주변 공간의 차원은 네트워크의 깊이 및 데이터 포인트 수와는 무관하게 입력 및 출력 차원에만 의존하며, 병목 너비는 스칼라 제약조건을 통해서만 관여한다. 이러한 구성은 다층 매개변수화를 이중선형 인수분해로 축소하고, 이를 계수 제약이 있는 준정부호 계획법(rank-constrained semidefinite program)으로 리프팅한 뒤, 상보성 조건(complementarity condition)을 통해 계수 제약을 표현하고, 완전 양의 리프팅을 적용함으로써 진행된다. 결과로 도출된 정식화는 선형 인수분해로 인해 유도된 비볼록성에 대한 원뿔형 표현을 제공하며, 선형 신경망 학습을 쌍양(copositive) 프로그래밍과 연결한다.
경사하강법의 마지막 반복점은 종종 (약간) 차선책이다
Gradient Descent's Last Iterate is Often (slightly) Suboptimal
본 논문에서는 경사하강법(GD) 또는 그 확률적 변형인 확률적 경사하강법(SGD)을 사용하여 볼록 립시츠(convex Lipschitz) 함수를 최소화하는 널리 연구된 설정을 고려하고, 마지막 반복점 수렴(last iterate convergence)을 살펴봅니다. 현재까지 표준적인 보폭(stepsize) 선택을 사용할 경우 $T$단계 후 $\log T/\sqrt{T}$의 마지막 반복점 수렴 속도를 보이는 것으로 알려져 있습니다. Jain 등[2019]의 획기적인 연구에서는 비표준 보폭 시퀀스를 구성하여 최적의 $1/\sqrt{T}$ 속도를 회복했습니다. 그러나 이 시퀀스는 임의의 시간 지평(time horizon)에 적용 가능한 일반적인 보폭 스케줄과 달리 $T$를 사전에 선택해야 합니다. 또한 Jain 등은 $T$에 대한 사전 지식 없이는 어떤 보폭 시퀀스도 SGD의 마지막 반복점에 대해 최적의 오차를 보장할 수 없다고 추측했으나, 이는 지금까지 증명되지 않은 상태로 남아 있었습니다. 본 연구에서는 이 추측을 증명하며, 실제로 노이즈가 없는 GD의 경우에도 임의 시점(anytime) 마지막 반복점 보장을 고려할 때 $T$에 대한 추가적인 폴리로그(poly-log) 인수를 피하는 것이 불가능함을 보입니다.
입력 볼록 신경망을 위한 쌍대 보증 화이트박스 추론
Dual Certified White-Box Inference for Input Convex Neural Networks
입력 볼록 신경망(Input Convex Neural Networks, ICNN)은 최소화점(minimizer)이 의사결정을 정의하는 볼록 목적함수를 학습하는 데 사용되므로, 효율적이고 신뢰할 수 있는 최적화가 추론의 핵심이 됩니다. 비매끄러운(nonsmooth) 입력에서 자동 미분은 최적성과 하강을 지배하는 완전한 열미분(subdifferential) 대신 단일 도함수만을 반환합니다. 2차 원뿔 ICNN(SOC-ICNN)은 매개변수화된 2차 원뿔 프로그램의 가치 함수로서 정확한 표현을 제공하여, 최적 쌍대 승수로부터 완전한 열미분을 복원하고 매끄러운 영역에서 명시적인 헤시안(Hessian)을 유도하는 화이트박스 접근법을 제공합니다. 이러한 표현을 바탕으로, 본 연구에서는 네트워크와 실행 가능 영역(feasible set)의 기하학적 구조를 결합하여 정확한 정류성 보증(stationarity certificates) 및 접 공통 하강 방향을 얻는 쌍대 보증 추론(DCI)을 개발합니다. DCI는 뉴턴 가속을 위해 국소 곡률을 활용하며 정확한 근위 안전장치(proximal safeguard)를 사용합니다. 본 연구에서는 전역 수렴을 확립하고, 표준 정규성 조건하에서 구조적으로 비퇴화인 내부 최소화점 부근에서의 국소 2차 수렴을 입증합니다. 수치 실험을 통해 복원된 기하학적 구조를 검증하고 DCI의 신뢰성과 효율성을 입증합니다. 코드는 https://anonymous.4open.science/r/DCI-ICNN-507D/ 에서 확인할 수 있습니다.
토론
이 논문과 연결된 포럼 글이 아직 없습니다.
저자 비고
arXiv Comments
Accepted as a poster at OPT 2026: 18th Annual Workshop on Optimization for Machine Learning (NeurIPS 2026 workshop). 19 pages (6 pages main text), 3 figures. Code: https://github.com/iammayankg/triangle-algorithm-sv