arXiv:2307.06886

Min-Max Optimization under Delays

Arman Adibi, Aritra Mitra, Hamed Hassani

제출 2023-07-13

원문 초록

Delays and asynchrony are inevitable in large-scale machine-learning problems where communication plays a key role. As such, several works have extensively analyzed stochastic optimization with delayed gradients. However, as far as we are aware, no analogous theory is available for min-max optimization, a topic that has gained recent popularity due to applications in adversarial robustness, game theory, and reinforcement learning. Motivated by this gap, we examine the performance of standard min-max optimization algorithms with delayed gradient updates. First, we show (empirically) that even small delays can cause prominent algorithms like Extra-gradient (\texttt{EG}) to diverge on simple instances for which \texttt{EG} guarantees convergence in the absence of delays. Our empirical study thus suggests the need for a careful analysis of delayed versions of min-max optimization algorithms. Accordingly, under suitable technical assumptions, we prove that Gradient Descent-Ascent (\texttt{GDA}) and \texttt{EG} with delayed updates continue to guarantee convergence to saddle points for convex-concave and strongly convex-strongly concave settings. Our complexity bounds reveal, in a transparent manner, the slow-down in convergence caused by delays.

함께 살펴볼 논문

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

arXiv:2607.14466v1cs.LG공통 태그 Stochastic Optimization, Adversarial Robustness

교차 노이즈 주입이 클린·손상·OOD 성능을 향상시킨다

Interleaved Noise Injection Improves Clean, Corrupted, and OOD Performance

노이즈 주입은 확률적 최적화(stochastic optimization)에서 잘 알려진 기법이다. 우리는 일반적인 단조 감쇠(monotonic decay) 스케줄 대신 교차(on-off-on-off...) 스케줄을 사용할 때 놀라울 정도의 효과가 있음을 보고한다. 노이즈 주입에 대한 이론적 분석을 제시하며, 임펄스 노이즈(impulse noise)에 의한 손상은 야코비안 정규화를 근사하고, 가우시안 노이즈(Gaussian noise)는 곡률 페널티(curvature penalty)로 작용함을 확인한다. 이러한 정규화 거동은 노이즈 주입이 모델 견고성(robustness)을 높이는 이유를 설명하는 데 사용되어 왔다. 그러나 우리가 제안한 스케줄의 교차적 특성은 최적화 목적 함수에서조차 더 나은 결과를 낸다. 노이즈가 있는 데이터 단계를 섞으면 옵티마이저가 국소 최솟값(local minima)에서 벗어나 탐험을 늘릴 수 있으며, 클린 데이터의 중요한 특징을 치명적으로 망각(catastrophically forgetting)할 위험 없이 학습할 수 있다. 클린 데이터와 노이즈 데이터 사이를 전환할 때 손실의 급격한 변화에 대해 이 학습 방식을 안정화하기 위해, 클린 그래디언트 크기에 따라 노이즈 업데이트를 스케일링하는 그래디언트 노름(gradient-norm) 안정화 기법을 도입한다. 이 방법을 다른 일반적인 증강(augmentation) 방법들과 비교한 결과, ResNet 및 ViT 아키텍처에서 CIFAR-100-C, ImageNet-C, ImageNet-R에 대한 손상 내성(corruption tolerance)과 실세계 분포 이동(distribution shift)에 대한 견고성에서 상당한 개선을 확인했으며, 다른 증강 위에 우리 방법을 쌓았을 때 최고의 결과를 얻었다. 시각적 중요도(saliency) 및 어텐션 맵을 통해, 교차 노이즈 주입의 효과가 모델의 귀납적 바이어스(inductive bias)가 장려하는 실패 모드(failure mode)에 페널티를 부과하는 데서 기인함을 보인다. 임펄스 노이즈는 합성곱(ResNet) 아키텍처의 지역성 바이어스(locality bias)에 대항하고, 가우시안 노이즈는 어텐션 기반 모델이 대규모 가짜(spurious) 특징을 포착하려는 경향을 줄인다. 따라서 교차 노이즈 주입은 사실상 추가 계산 비용 없이 클린, 노이즈, 분포 외(out-of-distribution) 데이터에 대한 테스트 성능을 향상시키는 효과적인 도구이다.

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.10666v2cs.LG공통 태그 Adversarial Robustness

적대적 학습된 신경망의 돌출도 맵 희소성에 대한 규명

Explaining the Saliency Map Sparsity of Adversarially-Trained Neural Networks

심층 신경망이 특정 예측을 수행하는 이유를 이해하는 것은 신경망의 안전한 배포를 위해 매우 중요합니다. 컴퓨터 비전(CV) 분야에서는 예측에 가장 큰 영향을 미치는 이미지 영역을 강조하는 돌출도 맵(saliency map)이 널리 사용되는 설명 방식으로 남아 있습니다. 한 가지 실증적 관찰 결과는 적대적 학습(adversarial training)된 신경망의 그래디언트 돌출도 맵에서 뚜렷한 희소성(sparsity)이 나타난다는 점입니다. 본 논문에서는 2개 층(layer) 렐루(ReLU) 네트워크를 대상으로 이러한 현상에 대한 이론적 설명을 제안합니다. 우리는 특정 손실 함수에서 유효한 것으로 밝혀진 적대적 학습과 가중치 감쇠(weight-decay) 페널티 및 적대적 전변동(total variation) 항이 추가된 경험적 위험 최소화 사이의 기존 동등성 관계를 기반으로 논의를 전개합니다. 데이터 포인트 수와 뉴런 수가 증가하고 정규화 매개변수가 적절한 비율로 0으로 수렴함에 따라, 최소화기(minimizer)가 최소 그래디언트 및 배런 노름(Barron norm)을 갖는 베이즈 분류기(Bayes classifier)로 수렴함을 증명합니다. $\ell_\infty$ 공격을 사용하는 적대적 학습의 경우 그래디언트 노름이 비등방적(anisotropic)이며 축에 정렬된/희소한 그래디언트를 선호하기 때문에 이러한 희소성이 나타납니다. 우리는 자연 학습된 모델과 적대적 학습된 모델의 그래디언트 $\ell_1$-노름 및 임계화된 희소성을 평가하여 이론적 발견을 실험적으로 제시합니다.

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:2607.12775v3math.OC공통 태그 Stochastic Optimization

시나리오 기반 모델 예측 제어의 학습 기반 가속

Learning-enabled Acceleration of Scenario-based Model Predictive Control

시나리오 기반 모델 예측 제어(SBMPC)는 여러 예측 시나리오에 걸쳐 제어 입력을 최적화함으로써 불확실성을 명시적으로 고려하는 모델 예측 제어(MPC)의 한 변형이다. 그러나 계산 복잡도가 시나리오 수와 예측 구간에 따라 급격히 증가하여 실시간 계획 및 제어에의 적용이 제한된다. 본 논문은 병렬 계산과 Moreau 포락선 학습을 활용하여 높은 해의 정확도를 유지하면서 SBMPC 문제를 효율적으로 풀기 위한 학습 가속 교대 방향 승수법(ADMM) 알고리즘을 제시한다. 우리는 SBMPC 문제를 ADMM으로 분해할 수 있는 합의 형태로 재구성하여, 시나리오 의존적 동역학을 비예측성 제약으로부터 분리하고 시나리오와 시간 단계에 걸친 병렬 갱신을 가능하게 한다. 이 분해를 바탕으로, 비용 함수의 Moreau 포락선 학습을 활용하는 learning-to-optimize 기법으로 ADMM의 주 변수 갱신을 가속하여 계산 시간을 줄인다. 제안한 프레임워크는 부하와 재생에너지 발전의 불확실성을 갖는 마이크로그리드 에너지 관리 문제에서 평가된다. 대표적인 최신 비선형 계획법 솔버인 IPOPT 및 MadNLP와의 비교에서, 신뢰할 수 있는 폐루프 제어 성능을 유지하면서 상당한 계산 속도 향상을 보였다.

토론

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