arXiv:2308.10154

Adaptive pruning-based Newton's method for distributed learning

Shuzhen Chen, Yuan Yuan, Youming Tao, Tianzhu Wang, Zhipeng Cai, Dongxiao Yu

제출 2023-08-20

원문 초록

Newton's method leverages curvature information to boost performance, and thus outperforms first-order methods for distributed learning problems. However, Newton's method is not practical in large-scale and heterogeneous learning environments, due to obstacles such as high computation and communication costs of the Hessian matrix, sub-model diversity, staleness of training, and data heterogeneity. To overcome these obstacles, this paper presents a novel and efficient algorithm named Distributed Adaptive Newton Learning (\texttt{DANL}), which solves the drawbacks of Newton's method by using a simple Hessian initialization and adaptive allocation of training regions. The algorithm exhibits remarkable convergence properties, which are rigorously examined under standard assumptions in stochastic optimization. The theoretical analysis proves that \texttt{DANL} attains a linear convergence rate while efficiently adapting to available resources and keeping high efficiency. Furthermore, \texttt{DANL} shows notable independence from the condition number of the problem and removes the necessity for complex parameter tuning. Experiments demonstrate that \texttt{DANL} achieves linear convergence with efficient communication and strong performance across different datasets.

함께 살펴볼 논문

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

arXiv:2607.22788v1cs.LG공통 태그 Stochastic Optimization, Diversity

FMOPF: AC 최적 전력 흐름을 위한 제약 인식 상호작용 사전 기반 잠재 플로우 매칭

FMOPF: Latent Flow Matching with Constraint-Aware Interaction Priors for AC Optimal Power Flow

AC 최적 전력 흐름(OPF)은 비선형 전력 평형 제약 하에서 최소 비용 발전 배치를 결정하며, 전력 시장 운영에서 하루에 수천 번 풀린다. 부하 조건에서 OPF 해법으로의 직접 매핑을 학습하면 이 계산을 가속할 수 있지만, 재생에너지 침투가 심화되면서 단일 최적 배치만으로는 더 이상 충분하지 않다. 운영자는 위험 정량화, 민감도 분석, 다목적 트레이드오프 평가를 위해 실행 가능한 근최적 해법 분포의 특성화가 필요하다. 지도 학습 신경망은 빠른 점 예측을 제공하지만 이 조건부 분포를 포착할 수 없다. 확산 기반 생성 모델은 원칙적으로 다양한 해법을 샘플링할 수 있지만, 원시 상태 공간에서 동작하는 기존 방법은 해법 품질이 저하되고 중간 규모 시스템 이상으로 확장하지 못한다. 우리는 근본 원인을 단일 모델 내에서 두 가지 서로 다른 과제가 혼재된 것으로 확인했다. 고차원 OPF 해법 매니폴드를 압축하는 것이 한 과제이고, 부하에서 그 매니폴드로의 조건부 매핑을 학습하는 것이 또 다른 과제이다. 본 논문은 잠재 플로우 매칭(latent flow matching)을 통해 압축과 생성을 분리하고, Constraint-Aware Interaction Prior Network를 통해 부하-상태 결합을 명시적으로 모델링함으로써 이러한 혼재를 해소하는 프레임워크인 FMOPF를 제안한다. 4개 IEEE 테스트 시스템에서의 실험은 FMOPF가 가장 효과적인 Newton-Raphson 웜 스타트(warm start)를 제공하고, 생성 방법 중 최저 꼬리 위험(tail risk)을 달성하며, 완전한 실행 가능성을 유지하면서 수백 개 버스(bus) 규모 시스템까지 확장 가능한 최초의 방법임을 보여준다. Ablation 연구는 잠재 생성 파이프라인이 물리적 실행 가능성의 필요 조건이며, 상호작용 사전(prior)이 후단 꼬리 위험 제어기로 기능함을 확인한다.

arXiv:2607.23408v1cs.AI공통 태그 Stochastic Optimization, Diversity

NeurGO: 메타 블랙박스 고비용 최적화를 위한 엘리트 후보 생성 학습

NeurGO: Learning to Generate Elite Candidates for Meta-Black-Box Expensive Optimization

과학과 공학에서 고비용 블랙박스 최적화는 함수 평가가 비용이 크고 평가 예산이 제한적인 상황에서 널리 사용됩니다. 전통적인 진화 알고리즘과 메타 블랙박스 최적화(MetaBBO) 접근법은 일반적으로 대부분의 평가를 후보 선택에 소비하며, 종종 열등한 해에 소중한 예산을 낭비합니다. 서로게이트 보조 진화와 베이지안 최적화는 서로게이트 모델을 통해 평가 횟수를 줄이는 것을 목표로 하지만, 제한된 데이터로부터 정확한 전역 모델을 구축하는 것은 여전히 어려우며, 모델 바이어스가 탐색을 지역 최적해에 쉽게 갇히게 할 수 있습니다. 이러한 한계를 극복하기 위해, 우리는 역사적 개체군 상태로부터 엘리트 후보를 직접 합성하는 생성형 MetaBBO 프레임워크인 NeurGO를 제안합니다. 구체적으로, 개체군 수준의 탐색 추세를 포착하기 위해 어텐션 기반 인코더를 사용하고, 이 표현을 조건으로 디코더를 작동시켜 고품질 후보를 생성함으로써 대규모 자손 풀의 고비용 평가를 피합니다. 그다음 탐색 전반에 걸쳐 해의 품질과 개체군 다양성을 유지하기 위해 품질-다양성 손실을 설계합니다. CEC 2008 및 COCO BBOB 테스트 스위트에 대한 광범위한 벤치마킹을 통해, 우리 방법은 동일한 평가 예산 하에서 더 나은 최적화 성능을 달성하고 더 빠른 수렴을 보입니다.

arXiv:2607.12172v1cs.DC공통 태그 Stochastic Optimization, Diversity

분산 경사하강법: 병목 구간과 예산 복잡도

Decentralized Gradient Descent: Bottleneck Regimes and Budget Complexity

분산 경사하강법(decentralized gradient descent, DGD)은 에이전트 네트워크에서 분산 최적화 문제를 풀기 위해 널리 사용된다. 수렴 특성은 잘 이해되어 있지만, 규정된 정확도를 달성하는 데 필요한 통신 및 계산 자원에 대해서는 상대적으로 덜 알려져 있다. 본 논문에서는 자원 인식(resource-aware) 관점에서 DGD를 연구하고, 목표 오차 수준을 달성하는 데 필요한 통신-계산 예산을 특성화한다. 우리는 서로 다른 오차 규모에서 최적화 역학을 지배하는 요인이 달라지는 병목 중심(bottleneck-centric) 프레임워크를 제안한다. 구체적으로 초기화, 목적 함수 이질성(objective heterogeneity) 및 네트워크 연결성, 그래디언트 노이즈, 통신 노이즈가 지배하는 동작 구간을 식별한다. 이러한 효과를 포착하기 위해 두 가지 기본량인 그래디언트 다양성 대 네트워크 연결성 비율(gradient-Diversity-to-Network-connectivity Ratio, DNR)과 그래디언트 대 통신 노이즈 비율(Gradient-to-Communication-noise Ratio, GCR)을 도입한다. 이들이 최적화 과정에서 순차적으로 등장하는 병목의 순서와 그에 대응하는 예산 최적 동작 전략을 결정함을 보인다. 다단계 분석을 통해 규정된 정확도 달성에 필요한 예산 자원을 정량화하는 최적 보폭(stepsize) 선택과 명시적 예산-복잡도 상한을 도출한다. 결과 식은 전체 예산이 연속적인 병목에 대응하는 기여로 어떻게 분해되는지 밝히고, 목적 함수 이질성, 네트워크 연결성, 그래디언트 노이즈, 통신 노이즈 사이의 근본적 트레이드오프에 대한 통찰을 제공한다.

arXiv:2608.23986v4math.OC공통 태그 Stochastic Optimization

지능의 그림자 가격: LLM 추론에서의 품질 저하와 재시도 피드백

The Shadow Price of Intelligence: Quality Degradation and Retry Feedback in LLM Inference

대규모 언어 모델 제공자는 연산 자원이 제약되어 있으며, 혼잡에 대한 일반적인 대응은 서비스를 저하시키는 것이다. 즉, 질의를 더 작은 모델로 라우팅하거나, 추론 예산을 줄이거나, 컨텍스트 윈도를 단축한다. 만족스럽지 못한 답을 받은 사용자는 재시도하여 시스템이 바쁜 동안 부하를 늘리거나, 이탈하여 잠재적으로 고객 이탈로 이어진다. 우리는 추론 서비스를 서비스 품질이 제공자의 의사결정인 제어 문제로 모델링한다. 재시도를 서비스율에 포함한 2국면 유체 근사는 닫힌 형태의 궤적과 교차 시간을 제공하므로, 품질 등급에 대한 동적 계획법에 시뮬레이션이 필요하지 않다. 우리는 더 약한 등급이 작업당 에너지는 덜 쓰지만 작업당 용량은 더 쓰는 영역을 규명하고, 유체 모델에서 그러한 등급으로의 반응적 스로틀링이 큐가 해소되지 못하게 할 수 있음을 보인다. 이질적인 고객이 있는 경우 이 문제는 재시도로 부풀려진 용량 계수를 갖는 수송 문제가 되며, 최적 라우팅은 $c\mu$ 유형의 지수를 따르고, 용량 제약의 쌍대는 클래스와 시간별로 질의 하나를 더 처리하는 한계 비용을 제공한다. 우리는 공개 벤치마크 데이터로 보정한 다섯 가지 사례에서 이 방법을 예시한다.

arXiv:2610.13590v2math.OC공통 태그 Stochastic Optimization

강볼록 집합 상의 무작위화 선형 오라클 최적화에 대한 하한

Lower Bounds for Randomized Linear-Oracle Optimization over Strongly Convex Sets

최근 결과들[arXiv:2602.04378, arXiv:2602.22608]은 강볼록 집합 위의 최적화에 대한 하한을 각각 특정 Frank-Wolfe 갱신과 제한 없는 결정론적 1차 선형 최소화 오라클(LMO) 방법에 대해 확립하였다. 어느 쪽도 제한 없는 무작위화 방법에 대한 하한은 확립하지 못한다. 우리는 최종 출력이 모든 인스턴스와 시드에서 실현 가능해야 한다는 조건 하에, 강볼록 집합 위의 무작위화 1차 LMO 방법에 대해 오라클 호출 $T$회 후 $\Omega(L\operatorname{diam}(S)^2/T^2)$ 분포적 하한을 증명함으로써 이 간극을 메운다. 우리의 구성은 [arXiv:2602.22608]의 족을 재사용하지만, 증명은 적응적 질의 이후 숨겨진 순열의 조건부 분포를 규명하고 최적화기 분산을 제어하는 조합적 통계량의 기대 감소량에 대한 상계를 제시한다. 또한 동일한 오차 임계값이 적어도 $3/4$의 확률로 성립하며 정지 시간 꼬리 한계를 도출함을 보인다. 우리의 구성은 [arXiv:2602.22608]과 동일한 곡률-지름 결합을 사용한다. 상계 [arXiv:1406.1305]와의 비교는 이 결합을 반드시 고려해야 한다. 별도로, 규정된 느린 정확 직선 탐색 Frank-Wolfe 궤적이 충분히 작은 초기화 오차를 국소적으로 증폭할 수 있음을 보이며, 이는 반복당 대략 1비트의 추가 초기화 정확도에 해당한다. 또한 특정한 최종 느린 포락선을 만족하는 초기화는 평면 측도가 0임을 보인다.

arXiv:2606.31584v3cs.NE공통 태그 Stochastic Optimization

공정 예산 연속 및 이산 벤치마크에서 MMAO의 대규모 실증 평가

A Large-Scale Empirical Evaluation of MMAO Under Fair-Budget Continuous and Discrete Benchmarks

본 논문은 프레임워크 자체를 다시 소개하는 대신, 더 엄격한 경험적 프로토콜 하에서 대사 다중 에이전트 최적화기(MMAO)를 평가한다. 연구는 MMAO의 폐루프 자원 할당 원리가 더 광범위하고 더 표준적이며 예산이 더 명시적으로 통제된 연속 및 이산 벤치마크에서도 신뢰성을 유지하는지를 묻는다. 완료된 주요 행렬은 각각 20개 시드를 갖는 10D와 30D의 CEC2017 함수 8개와 각각 20개 시드를 갖는 TSPLIB 인스턴스 5개를 다루며, PSO-lite, ES-lite, 반복 탐욕 2-opt 경로 기준선을 포함한 더 강력한 재현 가능 기준선과 함께 평가한다. 여기에 공동 예산, 성공률, 역할 진화, 개체군 교체에 대한 궤적 수준 진단을 추가하고, 이산 증거를 경로 문제 너머로 확장하기 위해 보조적인 OR-Library 다중 배낭 문제 일부도 더한다. 이 프로토콜 하에서 MMAO는 연속 영역과 TSPLIB 영역 모두에서 외부 기준선 집합을 뚜렷하게 능가하며, 제거 변형들은 외부 기준선보다 전체 방법에 훨씬 더 가깝게 유지된다. 결과는 시험한 영역 전반에서 내생적 자원 재분배를 뒷받침하지만, 더 정밀한 메커니즘 분리와 더 폭넓은 대회 수준 비교는 열린 과제로 남는다.

토론

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