arXiv:1803.07954

Resilient Monotone Sequential Maximization

Vasileios Tzoumas, Ali Jadbabaie, George J. Pappas

제출 2018-03-21

원문 초록

Applications in machine learning, optimization, and control require the sequential selection of a few system elements, such as sensors, data, or actuators, to optimize the system performance across multiple time steps. However, in failure-prone and adversarial environments, sensors get attacked, data get deleted, and actuators fail. Thence, traditional sequential design paradigms become insufficient and, in contrast, resilient sequential designs that adapt against system-wide attacks, deletions, or failures become important. In general, resilient sequential design problems are computationally hard. Also, even though they often involve objective functions that are monotone and (possibly) submodular, no scalable approximation algorithms are known for their solution. In this paper, we provide the first scalable algorithm, that achieves the following characteristics: system-wide resiliency, i.e., the algorithm is valid for any number of denial-of-service attacks, deletions, or failures; adaptiveness, i.e., at each time step, the algorithm selects system elements based on the history of inflicted attacks, deletions, or failures; and provable approximation performance, i.e., the algorithm guarantees for monotone objective functions a solution close to the optimal. We quantify the algorithm's approximation performance using a notion of curvature for monotone (not necessarily submodular) set functions. Finally, we support our theoretical analyses with simulated experiments, by considering a control-aware sensor scheduling scenario, namely, sensing-constrained robot navigation.

함께 살펴볼 논문

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

arXiv:2605.22432v3cs.LG공통 태그 Scheduling

AMUSE: 안정적 그래디언트 평가를 갖춘 Anytime Muon

AMUSE: Anytime Muon with Stable Gradient Evaluation

현대 심층 학습은 일반적으로 지정된 학습률 스케줄과 함께 AdamW에 의존하지만, 최근 연구들은 두 요소 모두에 이의를 제기한다. Schedule-Free 최적화는 반복 평균화를 통해 명시적 스케줄을 제거하고, Muon은 행렬 파라미터에 대해 모멘텀을 직교화함으로써 업데이트 기하학을 개선한다. Muon의 강력한 실증적 성능에도 불구하고, 그 근본 메커니즘은 부분적으로만 이해되고 있다. 우리는 river-valley 손실 지형을 통해 Muon을 연구한다. 여기서 유용한 학습 진행은 평탄하고 낮은 곡률의 bulk 부분공간(river)을 따라 이루어지며, 높은 곡률의 지배적 방향은 가파른 계곡 벽(valley walls)을 형성하여 진동을 유발한다. 우리는 실증적으로 Muon의 직교화가 bulk 성분을 증가시켜 river 진행을 가속하지만, 동시에 지배적 방향 노이즈를 증폭하여 진동하는 궤적을 유발함을 보인다. 이를 바탕으로, 우리는 Muon의 빠른 bulk 진행과 Schedule-Free 평균화의 안정화 효과를 통합하는 Anytime Muon with Stable Gradient Evaluation(AMUSE)를 제안한다. AMUSE는 시간에 따라 변하는 보간 계수를 사용하여, 초기에는 빠른 Muon 시퀀스 근처에서 그래디언트를 평가하여 신속한 적응을 이루고, 이후 점진적으로 안정적인 평균화된 시퀀스 쪽으로 이동하여 계곡 벽 진동을 억제한다. 그 결과 AMUSE는 학습률 스케줄이 필요 없으며 anytime 학습을 지원한다. 비전 태스크와 대규모 언어 모델 사전학습 전반에 걸쳐, AMUSE는 (Schedule-Free) AdamW 및 Muon 대비 성능-반복 파레토 프론티어를 일관되게 개선한다.

토론

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