강볼록 집합 상의 무작위화 선형 오라클 최적화에 대한 하한
Lower Bounds for Randomized Linear-Oracle Optimization over Strongly Convex Sets
원문 초록
Recent results [arXiv:2602.04378, arXiv:2602.22608] establish lower bounds for optimization over strongly convex sets, covering specified Frank-Wolfe updates and unrestricted deterministic first-order linear minimization oracle (LMO) methods, respectively. Neither establishes a lower bound for unrestricted randomized methods. We close this gap by proving an $\Omega(L\operatorname{diam}(S)^2/T^2)$ distributional lower bound after $T$ oracle calls for randomized first-order LMO methods over strongly convex sets, with final outputs required to be feasible on every instance and seed. While our construction reuses the family of [arXiv:2602.22608], our proof characterizes the conditional distribution of the hidden permutation after adaptive queries and bounds the expected decrease of a combinatorial statistic controlling optimizer variance. We also show that the same error threshold holds with probability at least $3/4$ and yields a stopping-time tail bound. Our construction uses the same curvature-diameter coupling as [arXiv:2602.22608]. Comparisons with the upper bound [arXiv:1406.1305] must account for this coupling. Separately, we show that prescribed slow exact-line-search Frank-Wolfe trajectories can locally amplify sufficiently small initialization errors, corresponding to roughly one extra bit of initialization accuracy per iteration, and that initializations satisfying a particular eventual slow envelope have planar measure zero.
제출 이력
확인된 버전만 표시합니다. 전체 제출 이력은 arXiv 원문에서 확인하세요.
- arXiv:2610.13590v2제출 시각 미확인
- arXiv:2610.13590v1
함께 살펴볼 논문
공통 태그를 근거로 연결했습니다. 실제 인용 관계나 논문의 우수성을 뜻하지 않습니다.
폴리토프 거리를 위한 보호된 블록 전이: 명시적 상수를 갖는 선형 수렴 및 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자릿수 더 느립니다. 이 알고리즘의 강점은 속도가 아니라 인증서에 있습니다.
기하학적 구조를 고려한 다중 목적 최적화: 엔트로피 기반 가중치 업데이트를 적용한 노름 제약 오라클
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에서 연구된 스펙트럼 구성을 일반적인 노름으로 확장합니다. 실험을 통해 기존 멀티태스크 옵티마이저와 제안 방법을 비교하고 오라클, 가중치 부여 및 모멘텀 선택을 검토합니다.
평활성 상수에는 무엇이 담겨 있는가? 유계 2차 이종성 하 Local SGD의 더 정밀한 수렴률
What's in a Smoothness Constant? Tighter Rates for Local SGD with Bounded Second-order Heterogeneity
Local SGD(연합 평균화(Federated Averaging)로도 알려짐)는 널리 사용되는 분산 최적화(optimization) 알고리즘이다. Local SGD는 실무에서 미니배치 SGD와 같은 대안들보다 종종 더 나은 성능을 보이지만, 이론은 현실적인 데이터 이종성 하에서 로컬 업데이트가 언제·왜 도움이 되는지를 여전히 부분적으로만 설명한다. [Patel et al., 2025]의 최근 연구는 유계 2차 이종성 가정이 강볼록 목적함수에 대한 Local SGD의 효율을 포착한다는 것을 보여 주며, 동일한 원리가 일반 볼록 설정으로 확장된다고 추측한다. 본 논문에서는 유계 2차 이종성 하 일반 볼록 목적함수에 대한 Local SGD의 개선된 수렴 보장을 확립함으로써 이 추측을 증명한다. 또한 이 설정에서 Local SGD에 대한 알려진 최선의 하한을 개선하여, 우리의 상한이 거의 tight함을 보인다. 이러한 결과를 종합하면 Local SGD에 대한 더 날카롭고 세밀한 수렴 이론이 제공된다. 기법의 추가 적용으로, 치환을 사용한 순차 SGD에 대한 하한을 제시하여 2차 이종성이 드문 고곡률(high-curvature) 클라이언트의 영향을 어떻게 포착하는지 보여 준다.
Langevin Dynamics로 학습할 때 unsafe 집합 회피
Avoiding unsafe sets when training with Langevin Dynamics
노이즈가 포함된 경사하강법으로 모델을 학습하는 과정은 과감쇠(overdamped) Langevin dynamics로 이상화할 수 있으며, 자연스러운 안전성(safety) 질문은 궤적이 지정된 실패 영역 $\mathcal{A}_H$에 놓일 확률 $ν_t(\mathcal{A}_H) = \mathbb{P}(Q_t \in \mathcal{A}_H)$를 경계(bound)하는 것이다. 우리는 $d$차원에서 매끄럽고 강볼록(strongly convex)한 손실에 대해 이를 연구하며, $\mathcal{A}_H$는 최소화점(minimizer)과 에너지 갭(energy gap)으로 분리되어 있다. 학습 종료 시 평형 질량(equilibrium mass) $π(\mathcal{A}_H)$는 $d$에 대해 지수적으로 작으며, 노이즈가 작을 때는 상보적인 에너지 장벽(energy-barrier) 속도를 따른다. 궤적을 따라 형태에 무관한(shape-free) 경계 $ν_t(\mathcal{A}_H) \le π(\mathcal{A}_H)(1 + \sqrt{χ_0^2/π(\mathcal{A}_H)}\,e^{-mt})$는 집합 내(in-set) 확률이 전역 스펙트럴 갭(global spectral gap) $m$만을 사용하여 차수 $d$의 burn-in 이후 (두 배의) 정적 값으로 완화(relax)됨을 보여준다. 구체적인 Ornstein-Uhlenbeck 예시는 이 burn-in이 필요함을 보여준다. 평형 shell의 각도 슬라이스(angular slice)는 평형 질량이 매우 작음에도 불구하고 $d$에 대해 지수적인 배수만큼 일시적으로 팽창(swell)할 수 있다. 이를 배제하기 위해 Dirichlet-form Rayleigh 몫(quotient)이 아니라 영역의 중심화된(centered) indicator의 스펙트럴 측도(spectral measure)를 통해 정의된 국소 완화율(local relaxation rate)을 도입한다. 기하학적으로 고립된(geometrically isolated) 영역에 대해 이율은 전역 값을 초과하여 burn-in을 줄이며, maximum principle 상한(ceiling)과 함께 시간에 대해 균일하게(uniformly) 궤적 확률의 상한을 설정한다. 강볼록성(strong convexity)은 학습이 얼마나 빠르게 완화되는지를 정하지만, unsafe 집합의 형태는 평형으로 향하는 과정에서 궤적이 그 집합을 통해 부풀어 오르(bulge)는지 여부를 결정한다.
WSqD: A Horizon-Free Learning Rate Schedule for Large Model Training
높은 확률로 확률적 고정점 방정식 풀기
Solving Stochastic Fixed-Point Equations with High Probability
우리는 노름 공간 $(\mathcal{E}, \|\cdot\|)$ 위에서의 확률적 고정점 방정식 $\mathbf{T}(\mathbf{x}) = \mathbf{x}$를 연구한다. 여기서 연산자 $\mathbf{T}$는 비팽창적(nonexpansive) 또는 수축적(contractive)이며, 유계 이차 중심 모멘트를 갖는 비편향 확률적 평가를 통해서만 접근 가능하다. $\varepsilon > 0$, $\delta \in (0, 1)$이 주어졌을 때, 목표는 $\|\mathbf{T}(\mathbf{x}) - \mathbf{x}\| \leq \varepsilon$을 확률 적어도 $1 - \delta$로 만족하는 $\mathbf{x} \in \mathcal{E}$를 출력하는 것이다. 우리는 이차적으로 평활화 가능한 바나흐(Banach) 공간을 위한 분산 감소(variance-reduced) 점진적 Halpern 방법인 VR-GHAL을 제안한다. 핵심 알고리즘 구성 요소는 오라클 평가의 클리핑된 차이에 기반한 재귀적 확률적 추정기이다: $\tau(\mathbf{x}; \xi)$ 자체를 클리핑하는 대신, 립시츠(Lipschitz) 스케일 $\gamma\|\mathbf{x} - \mathbf{y}\|$에서 확률적 차이를 클리핑한다. 이를 통해 추정기는 알고리즘 궤적을 따라 경로별 립시츠 성질을 유지하면서도, 원래 노름의 유한 이차 모멘트 하에서 마팅게일 집중(martingale concentration)을 허용한다. 우리의 주요 정리는 상시(anytime) 고확률 잔차 한계를 제공한다: 확률 적어도 $1 - \delta$의 단일 사건 위에서, 잔차는 하위 차수 로그 인수를 제외하고 에폭에 걸쳐 거의 기하적으로 감소한다. 유계 분산만을 가정하고 목표 오차 $\varepsilon$ 및 $\mathbf{T}$의 립시츠 상수 $\gamma \in (0, 1]$에 대한 의존성만 표시할 때, 결과적인 오라클 복잡도는 $\min\{\varepsilon^{-5}, (1-\gamma)^{-3}\varepsilon^{-2}\}$이다. 기댓값 립시츠(Lipschitz-in-expectation) 오라클 하에서는 의존성이 대응하는 $\varepsilon^{-3}$ 비팽창적 수렴률($\gamma = 1$의 경우)로 개선되며, 샘플별 비팽창성(samplewise nonexpansiveness) 하에서는 $\varepsilon^{-2}$로 개선된다.
토론
이 논문과 연결된 포럼 글이 아직 없습니다.