arXiv:2308.10630

A Homogenization Approach for Gradient-Dominated Stochastic Optimization

Jiyuan Tan, Chenyu Xue, Chuwen Zhang, Qi Deng, Dongdong Ge, Yinyu Ye

제출 2023-08-21

원문 초록

Gradient dominance property is a condition weaker than strong convexity, yet sufficiently ensures global convergence even in non-convex optimization. This property finds wide applications in machine learning, reinforcement learning (RL), and operations management. In this paper, we propose the stochastic homogeneous second-order descent method (SHSODM) for stochastic functions enjoying gradient dominance property based on a recently proposed homogenization approach. Theoretically, we provide its sample complexity analysis, and further present an enhanced result by incorporating variance reduction techniques. Our findings show that SHSODM matches the best-known sample complexity achieved by other second-order methods for gradient-dominated stochastic optimization but without cubic regularization. Empirically, since the homogenization approach only relies on solving extremal eigenvector problem at each iteration instead of Newton-type system, our methods gain the advantage of cheaper computational cost and robustness in ill-conditioned problems. Numerical experiments on several RL tasks demonstrate the better performance of SHSODM compared to other off-the-shelf methods.

함께 살펴볼 논문

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

arXiv:2607.15229v1cs.LG공통 태그 Stochastic Optimization, Management

데이터 기반 블록 교체 스케줄링

Data Driven Block Replacement Scheduling

우리는 \textit{블록 교체 정책(block replacement policy)} 하에서 $N$대의 독립 동형 기계를 유지·관리하기 위한 데이터 기반 알고리즘을 개발한다. 이 정책에서는 각 기계가 고장 시 교체되고, 모든 기계가 길이 $k$의 정규 간격으로 일괄 교체된다. 수명 분포가 알려지지 않은 경우 운영 데이터로부터 비용을 최소화하는 간격 $k^*$를 학습하는 것이 목표이다. 각 의사결정 시점마다 운영자는 $k \in \{1, 2, \ldots, K\}$를 선택하고, 그 결과 고장 이력(완전 수명과 우측 검열(right-censored) 수명의 혼합)을 관측하며, 갱신 함수(renewal function)에 의해 결정되는 단위 시간당 비용을 부담한다. 이를 확률적 다중 팔 밴딧(stochastic multi-armed bandit)으로 형식화하고, $O(K \log T)$ 후회(regret)를 달성하는 Hoeffding 및 Bernstein 기반 하한 신뢰 구간(lower-confidence-bound) 알고리즘을 제안하며, 이는 Lai--Robbins 하한과 일치한다. 블록 교체에 고유한 중첩 관측(nested observation) 성질을 활용한 상관 변형(correlated variants)은 $O((K-k^*)\log T)$ 후회를 달성하고, 차선 arm $k < k^*$에 대한 직접 pull은 $O(1)$번만 필요하다. 보완적으로 Kaplan--Meier 갱신 알고리즘은 검열 데이터로부터 수명 분포를 비모수적으로 추정하여, 거의 확실(almost-sure)한 정책 일관성을 달성하고 장기 구간에서 실증적으로 거의 0에 가까운 추가 후회를 보인다. 또한 평균 비용 MDP 두 가지를 분석한다. 경과 시간(time-elapsed) 형식화는 임의의 수명 분포에 대해 블록 교체가 해당 정책 클래스 내에서 최적임을 보이고, 연령 벡터(age-vector) 형식화는 증가하는 고장률(increasing failure rate) 분포 하에서 단조 임계값(monotone threshold) 구조를 증명하며 gold-standard 비용 벤치마크를 제공한다. 수치 실험은 이론적 순서를 확인하고, 최적 블록 교체와 연령 의존(age-dependent) 교체 사이의 구조적 비용 격차를 밝힌다.

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.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와의 비교에서, 신뢰할 수 있는 폐루프 제어 성능을 유지하면서 상당한 계산 속도 향상을 보였다.

arXiv:2608.16666v3cs.AI공통 태그 Reinforcement Learning (RL)

Chronocooked: 강화학습 에이전트의 시간 간격 측정 능력을 위한 벤치마크

Chronocooked: A Benchmark for Interval Timing in Reinforcement Learning Agents

구간 시간 지각(interval timing)은 인간 인지의 중요한 측면으로 여겨진다. 인공 에이전트가 인간과 함께 기능하는 경우가 늘어나면서 이들의 구간 시간 지각 능력을 연구할 필요가 있다. 그러나 이 분야의 연구는 아직 제한적이고 산재해 있다. 본 논문은 강화학습(RL) 에이전트의 구간 시간 지각 능력을 체계적으로 연구할 수 있는 RL 벤치마크 환경 Chronocooked를 제시한다. 이 제품군은 심리학 문헌에서 착안한 구간 시간 지각 과제를 포함하는 요리 시나리오로 구성된다. 각 과제에는 RL 에이전트의 구간 시간 지각의 여러 측면, 즉 과제 성능, 인간과 유사한 시간 지각, 확장성을 연구하기 위한 평가 지표가 함께 제공된다. 비순환 모델(CNN), 순환 모델(LSTM), 생물학적으로 영감을 받은 순환 모델(CTRNN)을 사용한 기준선을 보고한다. CNN 모델은 기본적인 시간 지각 과제를 수행하는 능력이 제한적이었다. 반면 충분한 메모리를 갖춘 두 순환 모델은 시간 지각 과제를 성공적으로 수행했고, 고정 간격(FI) 과제에서 시간적 통제를 보였으며, 시간 이분(Temporal Bisection) 과제에서 인간과 유사한 심리측정 곡선을 정성적으로 재현했다. 그러나 인간과 유사한 시간 지각 행동에 대한 정량적 증거는 발견되지 않았다. 인공 에이전트의 구간 시간 지각에 대한 체계적인 연구는 인간-로봇 상호작용(HRI)과 같은 분야에서 과제 성능을 개선하기 위한 보완적 관점을 제공할 수 있으며, 시간 지각에 관한 더 넓은 연구에도 기여할 수 있다.

토론

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