낙관적 곱셈 가중치 갱신의 마지막 반복 수렴
Last-Iterate Convergence of Optimistic Multiplicative Weight Update
한국어 초록
낙관적 경사하강상승법(OGDA)과 낙관적 곱셈 가중치 갱신(OMWU)은 볼록/오목 안장점 문제를 해결하는 두 가지 매우 인기 있는 알고리즘으로, OMWU는 OGDA의 비유클리드이며 엔트로피 기반 버전입니다. 1980년대부터 OGDA의 마지막 반복이 매끄러운 문제에서 안장점으로 점근적으로 수렴한다는 사실이 알려져 왔습니다. 반면, OMWU가 동일한 성질을 갖는지는 여전히 알려져 있지 않습니다. 본 논문에서는 충분히 작은 상수 학습률을 사용할 때, OMWU가 매끄러운 볼록-오목 안장점 문제에 대해 점근적으로 수렴함을 보입니다. 이 결과는 해의 유일성, 엄격한 상보성, 오차 한계, 또는 해 근처에서의 초기화를 요구하지 않습니다. 주요한 새로운 요소는 모든 집적점이 비활성 좌표 KKT 부등식을 만족한다는 것을 보여주는 경계 논증입니다. 이 경계 논증은 ChatGPT의 도움을 받아 발견되었으며, 부록에 기록되어 있습니다.
원문 초록
Optimistic Gradient Descent Ascent (OGDA) and Optimistic Multiplicative-Weights Update (OMWU) are two very popular algorithms to solve convex/concave saddle-point problems, where OMWU is the non-Euclidean, entropic version of OGDA. It is known since the '80s that the last iterate of OGDA asymptotically converges to a saddle point in smooth problems. On the other hand, it is unknown if OMWU has the same property. In this paper, I show that OMWU converges asymptotically for smooth convex-concave saddle-point problems, with a small enough constant learning rate. The result does not require uniqueness, strict complementarity, an error bound, or initialization near a solution. The main new ingredient is a boundary argument showing that every cluster point satisfies the inactive-coordinate KKT inequalities. The boundary argument was discovered with assistance from ChatGPT and is documented in the appendix.
제출 이력
확인된 버전만 표시합니다. 전체 제출 이력은 arXiv 원문에서 확인하세요.
- arXiv:2606.11773v1제출 시각 미확인
함께 살펴볼 논문
공통 태그를 근거로 연결했습니다. 실제 인용 관계나 논문의 우수성을 뜻하지 않습니다.
Proxy OPD: On-Policy Distillation with Transferable Relative Proxy Update for Large Language Models
LISA: 효율적 긴 컨텍스트 추론을 위한 Linear-Indexed Sparse Attention
LISA: Linear-Indexed Sparse Attention for Efficient Long-Context Reasoning
토큰이 아닌 턴 주입하기: 자기 수정을 위해 LLM 추론을 리디렉션할 위치 학습
Inject a Turn, Not a Token: Learning Where to Redirect LLM Reasoning for Self-Correction
대규모 언어 모델(LLM)은 자신의 추론 과정에서 발생한 오류를 안정적으로 식별하고 수정하는 데 어려움을 겪는다. 수정이나 피드백을 생성하도록 LLM을 미세조정하는 기존의 학습 기반 접근법과 달리, 우리는 실패한 롤아웃에서 어디에 개입할지를 학습하고 이를 어떻게 리디렉션할지를 결정한다. 개입 위치를 선택하기 위해, 우리는 최종 답안의 정답 여부만을 이용해 고정된 인코더 위에 130K개의 매개변수를 가진 MLP 헤드를 학습시킨다. 리디렉션의 경우, 고정된 생성 예산 하에서 테스트한 인라인 주입(inline injection)은 추론을 안정적으로 리디렉션하지 못하는 반면, 동일한 지시문을 새로운 사용자 턴(user turn)으로 제시하면 모델의 진행 방향이 바뀐다는 것을 발견했다. 그 결과로 만들어진 수정 프레임워크인 UPTURN(User-Prompt TURN injection at a learned position)은 LLM의 미세조정을 전혀 요구하지 않는다: 선택된 접두 문맥(prefix)을 유지하고, 지시문을 새로운 사용자 턴으로 주입한 뒤, 나머지 부분을 재생성한다. 네 가지 추론 모델과 여섯 가지 수학 벤치마크 전반에서, UPTURN은 32회 롤아웃 기준선(baseline) 대비 모든 설정에서 평균 정확도를 향상시킨다. 동일한 수정 예산 하에서 자기 수정(self-correction) 및 리플렉션 토큰(reflection-token) 주입 기준선을 능가하며, 재학습 없이도 다른 추론 모델과 GPQA-Diamond로 전이되고, GRPO 및 자기 수정 기법과도 상호보완적이다.
Geometric Signatures of Reasoning: A Spectral Perspective on Task Hardness
사고 모델을 위한 온-정책 자기 지식 증류의 재고찰
Rethinking On-Policy Self-Distillation for Thinking Models
Continual Graph Memory and Community Infrastructure for AI-Assisted Mathematical Discovery
토론
이 논문과 연결된 포럼 글이 아직 없습니다.