arXiv:2212.01518

Hedging Complexity in Generalization via a Parametric Distributionally Robust Optimization Framework

Garud Iyengar, Henry Lam, Tianyu Wang

제출 2022-12-03

원문 초록

Empirical risk minimization (ERM) and distributionally robust optimization (DRO) are popular approaches for solving stochastic optimization problems that appear in operations management and machine learning. Existing generalization error bounds for these methods depend on either the complexity of the cost function or dimension of the random perturbations. Consequently, the performance of these methods can be poor for high-dimensional problems with complex objective functions. We propose a simple approach in which the distribution of random perturbations is approximated using a parametric family of distributions. This mitigates both sources of complexity; however, it introduces a model misspecification error. We show that this new source of error can be controlled by suitable DRO formulations. Our proposed parametric DRO approach has significantly improved generalization bounds over existing ERM and DRO methods and parametric ERM for a wide variety of settings. Our method is particularly effective under distribution shifts and works broadly in contextual optimization. We also illustrate the superior performance of our approach on both synthetic and real-data portfolio optimization and regression tasks.

함께 살펴볼 논문

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

arXiv:2607.22467v1cs.LG공통 태그 Stochastic Optimization, Generalization Bounds

투영 경사하강법 솔버 반복 학습의 복잡도 상한과 접근법

Complexity Bounds and Approaches to Learning Projected Gradient Descent Solver Iterates

데이터 부족은 수치적으로 계산 비용이 큰 매개변수 최적화 문제에 대한 초기 추정값을 생성하기 위해 생성 모델을 학습하는 데 근본적인 난제를 제기한다. 따라서 우리는 수렴한 해의 데이터셋을 솔버의 중간 반복값으로 보강하여 추가적인 솔버 실행 없이 학습 데이터량을 늘리는 $k$-neighborhood 데이터 수집 전략을 연구한다. 이 접근법의 이점을 이해하기 위해, 우리는 Rademacher 복잡도에 기반한 일반화 상한을 도출하여 $k$-neighborhood와 관련 매개변수의 역할을 밝힌다. 이 결과를 얻기 위해, 우리는 투영 경사하강법으로 풀리는 일측 상자 제약 2차 계획법(one-sided box-constrained quadratic programs)에 초점을 맞춘다. 우리는 두 가지 예제에서 이 솔버의 동작을 설명한다. 본 논문에서 제안하는 접근법은 데이터-모델-최적화 루프의 효율을 개선함으로써 더 유능한 DDDAS 패러다임을 가능하게 한다. 마지막으로 솔버 반복 데이터 학습에 대한 두 가지 관점을 논의하고, 우리의 분석을 새로운 데이터 효율적 전역 탐색 방법인 GLENS와 연결한다.

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:2607.09820v1cs.LG공통 태그 Stochastic Optimization, Portfolio Optimization

의사결정 중심 분포 강건 최적화를 위한 예측적 모호성 집합 학습

Learning Predictive Ambiguity Sets for Decision-Focused Distributionally Robust Optimization

예측 후 최적화(Predict-then-optimize) 시스템은 일반적으로 불확실성을 점 예측(point forecast)으로 압축한 뒤, 해당 예측이 신뢰 가능한 것처럼 가정하고 다운스트림 최적화 문제를 풀어낸다. 분포 강건 최적화(DRO, Distributionally Robust Optimization)는 잘못된 명세(misspecification)에 대한 보호를 제공하지만, 모호성 집합(ambiguity set)은 흔히 과거 샘플을 중심으로 하며 고정된 반지름을 사용한다. 본 논문에서는 학습된 예측적 모호성 집합(LPAS, learned predictive ambiguity sets)을 제안한다: 심층 컨텍스트 모델이 유한한 명목 시나리오 분포, 상태 의존적 와서스테인(Wasserstein) 반지름, 그리고 선택적으로 비등방성 기저 거리(anisotropic ground metric)를 출력한다. 이 출력들은 DRO 의사결정 층에 공급되는 컨텍스트 모호성 집합을 정의한다. 반지름은 조건부 분위수 보정, 크기 정규화, 그리고 다운스트림 의사결정 손실의 조합으로 학습되어, 강건성이 전역 고정값이 아닌 적응적으로 조정된다. 의사결정 층에서 사용되는 유한 쌍대 형식(finite dual form)을 유도하고, 단계적 학습 알고리즘을 제시하며, 2018년부터 2026년까지의 S&P 500 구성 종목 20개를 대상으로 한 분포 강건 포트폴리오 최적화에서 방법론을 평가한다. 제안된 방법은 동일 가중치, 예측 후 최적화, 과거 와서스테인 DRO 기준선을 크게 상회하며, 26.28%의 연환산 수익률, 샤프 비율 1.30, 최종 자산 1.61을 달성하고, 더 작은 평균 반지름을 사용하면서도 심층 고정 반지름 DRO 기준선보다 낮은 테일 손실을 기록한다. 결과는 학습된 모호성 반지름이 불필요한 보수성을 줄이고 레짐 적응성(regime adaptivity)을 개선하면서 강력한 고정 반지름 DRO의 성능 대부분을 회복할 수 있음을 보여준다.

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임을 보인다.

토론

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