PAC 학습 가능한 오라클을 활용한 학습 증강 매끄러운 정수 계획법
Learning-augmented smooth integer programs with PAC-learnable oracles
한국어 초록
본 연구는 MAX-CUT과 MAX-k-SAT을 포함하는 폭넓은 불리언 다항식 최적화 문제 부류인 매끄러운 정수 계획법을 위한 종단간 학습 증강 프레임워크를 연구한다. 표본 인스턴스로부터 학습된 오라클은 보지 못한 각 인스턴스에 대해 전체 불리언 할당을 예측한다. 고정 차수 목적함수에 대해, 다항 시간 파이프라인인 LEAP는 예측된 할당 주변에서 목적함수를 선형화하고, 오차 예산이 설정된 선형 계획 문제를 풀며, 분수 해를 반올림한다. 본 연구는 두 가지 보장을 증명한다. 첫째, 임의의 예측에 대해 LEAP의 근사 손실은 예측 오차에 따라 완만하게 악화되며, 이는 잘못 예측된 좌표가 목적함수의 국소 계수를 얼마나 교란할 수 있는지를 정량화하는 오차 풋프린트로 제어된다. 둘째, LEAP가 유도하는 비용 클래스의 유사 차원(pseudo-dimension)을 유계화하여, 알려지지 않은 분포에서 추출한 인스턴스에 대한 경험적 위험 최소화를 통해 예측기 클래스로부터 오라클을 학습하는 PAC 방식의 보장을 얻는다. 이 결과들을 종합하면 클래스 내 최선 오라클의 기대 풋프린트 손실과 학습의 통계적 오차를 분리하는 종단간 한계가 도출된다. MAX-CUT과 MAX-SAT 실험에서 LEAP는 불완전한 예측을 상당히 보정하였고, 경험적 위험 최소화는 효과적인 오라클 후보를 선택하였으며, 파이프라인은 최대 200만 개의 절을 갖는 응용 벤치마크까지 확장되었다.
원문 초록
We study an end-to-end learning-augmented framework for smooth integer programs, a broad class of Boolean polynomial optimization problems including MAX-CUT and MAX-k-SAT. An oracle learned from sampled instances predicts a full Boolean assignment for each unseen instance. For fixed-degree objectives, our polynomial-time pipeline, LEAP, linearizes the objective around the predicted assignment, solves an error-budgeted linear program, and rounds the fractional solution. We establish two guarantees. First, for any prediction, the approximation loss of LEAP degrades gracefully with prediction error: it is controlled by an error footprint that quantifies how much mispredicted coordinates can perturb the objective's local coefficients. Second, we bound the pseudo-dimension of the LEAP-induced cost class, yielding a PAC-style guarantee for learning an oracle from a predictor class via empirical risk minimization on instances from an unknown distribution. Together, these results give an end-to-end bound that separates the expected footprint loss of the best oracle in the class from the statistical error of learning. In experiments on MAX-CUT and MAX-SAT, LEAP substantially repairs imperfect predictions, empirical risk minimization selects effective oracle candidates, and the pipeline scales to application benchmarks with up to two million clauses.
제출 이력
확인된 버전만 표시합니다. 전체 제출 이력은 arXiv 원문에서 확인하세요.
- arXiv:2602.02505v2제출 시각 미확인
함께 살펴볼 논문
공통 태그를 근거로 연결했습니다. 실제 인용 관계나 논문의 우수성을 뜻하지 않습니다.
공통 태그로 연결된 공개 논문이 아직 없습니다.
토론
이 논문과 연결된 포럼 글이 아직 없습니다.