arXiv:2103.04392

A Retrospective Approximation Approach for Smooth Stochastic Optimization

David Newton, Raghu Bollapragada, Raghu Pasupathy, Nung Kwan Yip

제출 2021-03-07

원문 초록

Stochastic Gradient (SG) is the defacto iterative technique to solve stochastic optimization (SO) problems with a smooth (non-convex) objective $f$ and a stochastic first-order oracle. SG's attractiveness is due in part to its simplicity of executing a single step along the negative subsampled gradient direction to update the incumbent iterate. In this paper, we question SG's choice of executing a single step as opposed to multiple steps between subsample updates. Our investigation leads naturally to generalizing SG into Retrospective Approximation (RA) where, during each iteration, a "deterministic solver" executes possibly multiple steps on a subsampled deterministic problem and stops when further solving is deemed unnecessary from the standpoint of statistical efficiency. RA thus rigorizes what is appealing for implementation -- during each iteration, "plug in" a solver, e.g., L-BFGS line search or Newton-CG, as is, and solve only to the extent necessary. We develop a complete theory using relative error of the observed gradients as the principal object, demonstrating that almost sure and $L_1$ consistency of RA are preserved under especially weak conditions when sample sizes are increased at appropriate rates. We also characterize the iteration and oracle complexity (for linear and sub-linear solvers) of RA, and identify a practical termination criterion leading to optimal complexity rates. To subsume non-convex $f$, we present a certain "random central limit theorem" that incorporates the effect of curvature across all first-order critical points, demonstrating that the asymptotic behavior is described by a certain mixture of normals. The message from our numerical experiments is that the ability of RA to incorporate existing second-order deterministic solvers in a strategic manner might be important from the standpoint of dispensing with hyper-parameter tuning.

함께 살펴볼 논문

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

arXiv:2609.26811v1cs.LG공통 태그 Image Classification, Stochastic Optimization

드리프트 계약: 깊이에 강건한 로컬 학습을 위한 스펙트럼 업데이트

The Drift Contract: Spectral Updates for Depth-Robust Local Learning

로컬 학습(local learning)은 전역 역전파(global backward pass) 없이 각 층(layer)을 자체 보조 손실(loss)로 학습(training)하므로 층 업데이트를 구조적으로 병렬화할 수 있게 합니다. 그러나 깊이가 깊어질수록 정확도가 저하되고 하이퍼파라미터가 취약하다는 두 가지 문제로 인해 비주류에 머물러 있었습니다. 본 연구에서는 기존에 연구되지 않았던 교집합 영역으로서, 층별 로컬 업데이트에 Muon 스타일의 스펙트럼 업데이트 기하학(스펙트럼 스텝 스케일링을 결합한 모멘텀 직교화)을 적용합니다. 로컬 선형 헤드를 갖춘 CIFAR-10 MLP 벤치마크(benchmark)에서, 로컬 Adam은 너비와 깊이 두 축 모두에서 재튜닝이 필요하고 깊이 48에서는 여전히 붕괴(깊이별 재튜닝 시 31.3%, 깊이 12 설정을 전이했을 때 19%, 반면 스펙트럼 업데이트는 변경되지 않은 설정에서 42.7%)하는 반면, 스펙트럼 업데이트는 단일 스텝 크기 설정만으로 테스트된 너비 128~2048 및 깊이 12~48 격자에서 최적의 값을 보였습니다. 5개의 시드와 너비 512에서 스펙트럼 업데이트는 로컬 Adam을 뚜렷한 마진(margin)으로 앞섭니다(48.9 +/- 0.5 대 46.6 +/- 0.3). 전향적으로 명시된 대조 실험을 통해 이러한 전이 성능과 대부분의 깊이 강건성이 그 위의 어떤 스텝 크기 규칙보다는 스펙트럼 기하학 자체에 기인함을 확인했습니다. 추가로 스텝 크기를 드리프트 계약(drift contract), 즉 lr = epsilon / RMS(input)으로 정형화하여, 현재 입력을 조건으로 각 층의 스텝당 가중치(weight) 유도 사전 활성화(pre-activation) 변화를 제한합니다. 이 계약은 해당 기준선(baseline)이 측정된 지점에서 최적의 고정 학습률(learning rate) 대비 약간의 성능 향상을 가져오고, 스텝 크기를 해석 가능하게 만들며, 표준 최적화(optimization) 도구가 제공하지 못하는 층별·입력 조건부 드리프트 한계를 제공합니다. 한 가지 부정적 결과도 보고합니다. 트렁크(trunk)에 RMSNorm과 가중치 감쇠(weight decay)가 포함된 경우 스펙트럼 업데이트의 안정성 이점은 로컬 학습이 아닌 전역 학습에 귀속되므로, 로컬 학습의 이점은 정확히 정규화(normalization)가 부재한 곳에 집중됩니다.

arXiv:2607.14466v1cs.LG공통 태그 Image Classification, Stochastic Optimization

교차 노이즈 주입이 클린·손상·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.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.22862v2cs.NE공통 태그 Stochastic Optimization

매개변수화된 CEC 2017 벤치마크를 이용한 변환의 민감도 분석

Sensitivity Analysis of the Transformation Using a Parameterized CEC 2017 Benchmark

CEC 2017은 편향(bias), 이동(shift), 회전(rotation)을 동시에 적용하므로 각각이 알고리즘 동작에 미치는 개별 효과가 가려진다. 우리는 원래의 함수와 변환 데이터를 보존하면서 이들을 독립적으로 제어하는 매개변수화된 구현을 소개한다. 이를 이용하여, 예측 후보 메커니즘이 수치적 목적함수 값과 좌표별 재구성에 의존하는 하이브리드 해양 포식자 알고리즘(hMPA)을 진단한다. 심층 통계 비교(DSC)와 확장 DSC(eDSC)를 알고리즘 수준의 비교에서 구성 수준의 진단으로 적응시켰다. 우리가 아는 한, 이는 매개변수화된 CEC 2017 벤치마크의 편향-이동-회전 8개 구성 전체에 대한 최초의 철저한 DSC 및 eDSC 분석이다. 29개 함수, 차원 10, 30, 50, 100, 30회의 독립 실행, 차원당 10,000회의 목적함수 평가라는 고정 예산을 사용하여, 가능한 56개의 3개 구성 부분집합 전부와 변환하지 않은 대조군과의 비교를 검토한다. DSC와 eDSC는 모든 차원에서 구성 간 통계적으로 유의한 차이를 보이지만, 순위는 함수에 따라 달라 일관된 순서를 정할 수 없다. 대부분의 개별 효과 크기 신뢰구간은 0을 포함한다. 0을 포함하지 않는 경우 중에서는, 차원 10에서는 MPA가, 차원 50과 100에서는 hMPA가 유리한 비교가 더 많다. 이동은 대체로 목적함수 값 결과를 악화시킨다. 단독 회전은 체계적인 성능 저하를 일으키지 않으며, 단독 편향은 최종 해 분포를 거의 바꾸지 않는다. 이동과 회전의 결합은 대조군과 가장 일관되게 다르다. 수렴 곡선은 함수 및 차원에 따라 달라지는 분리, 정체 구간, 후반부 개선을 보여 준다. 수치적 결과는 hMPA에 한정되지만, 이 프레임워크는 다른 연속 최적화 알고리즘으로 확장될 수 있고 CEC 2024 및 CEC 2025를 포함한 관련 CEC 벤치마크에도 적용할 수 있다.

arXiv:2609.27710v3cs.CV공통 태그 Image Classification

FFM-CP: 퓨샷 계산병리학을 위한 비전-언어 기반 모델의 교차 백본 융합

FFM-CP: Cross-Backbone Fusion of Vision-Language Foundation Models for Few-Shot Computational Pathology

병리학 비전-언어 기반 모델은 질환과 과제에 따라 성능이 달라지며, 어떤 단일 모델도 일관되게 최고 성능을 내지 못한다. 전문가 병리 주석의 높은 비용은 과제별 적응에 사용할 수 있는 라벨 데이터를 제한하기도 한다. 상호 보완적인 사전학습 표현을 결합하는 것은 이러한 한계에 대한 잠재적 접근이지만, 소수의 라벨 예시로부터 효과적인 융합을 학습하는 것은 여전히 어렵다. 본 연구는 퓨샷 학습 설정에서 여러 병리학 비전-언어 모델을 결합하는 프레임워크인 Few-shot Fusion Foundation Models of Computational Pathology(FFM-CP)를 제안한다. 이 프레임워크는 먼저 대응하는 서포트 이미지로부터 추정한 폐형식(closed-form) 직교 프로크루스테스(Orthogonal Procrustes) 변환을 사용하여 이질적인 표현을 정렬한다. 이 정렬은 추가 정렬 네트워크를 학습하지 않고도 모델 내부 특징 기하를 보존한다. 정렬된 공간 안에서 통합 그래프는 서포트 이미지 특징과 시각·텍스트 클래스 프로토타입을 공동으로 정제함으로써 백본 간 정보 교환을 가능하게 한다. 이렇게 정제된 표현은 의미적 클래스 지식과 클래스 내 시각적 변이를 각각 포착하는 상호 보완적인 텍스트-프로토타입 분기와 케이스 검색(case-retrieval) 분기를 지원한다. 각 분기는 모든 순서화된 백본 쌍의 예측을 결합하는 방법을 학습하여, 한 모델로 인코딩된 쿼리가 다른 모델이 표현한 증거를 활용할 수 있게 한다. 우리는 6개의 조직병리학 데이터셋에서 클래스당 4, 8, 16샷 조건으로 3가지 백본 조합을 평가했다. FFM-CP는 54번 비교 중 50번에서 각 융합 집합의 개별 적응 멤버 중 가장 강한 모델보다 더 높은 평균 macro-F1을 달성했다. 이러한 결과는 주석이 제한될 때 상호 보완적인 사전학습 표현의 결합이 조직병리학 분류를 개선할 수 있음을 시사한다.

토론

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