arXiv:2606.18807v1 cs.DS

학습 강화 정확 지수 시간 알고리즘

Learning Augmented Exact Exponential Algorithms

Tatiana Belova, Yuriy Dementiev, Danil Sagunov

제출 2026-06-17

한국어 초록

학습 강화 알고리즘 분야는 기계 학습 예측이 다양한 문제 영역에서 최악의 경우 하한을 우회할 수 있음을 입증해 왔습니다. 그러나 지금까지 초점은 거의 독점적으로 다항 시간 알고리즘에 맞춰져 있었으며, 여기서 예측은 경쟁비, 근사 보장, 또는 실행 시간을 개선했습니다. 본 논문에서 우리는 예측이 NP-hard 문제에 대한 정확한 지수 시간 알고리즘의 경계를 확장할 수 있는지라는 질문을 제기합니다. 우리는 다양한 부분집합 선택 문제에 대한 최신 정확 알고리즘 계열 전체를 증강하는 일반적인 접근 방식을 제안함으로써 이 질문에 긍정적으로 답합니다. 우리는 무작위 추측보다 약간만 더 나은 노이즈 예측기(noisy predictor)도 검색 공간을 확실히 줄이기에 충분하다는 것을 보여주며, 그 결과로 얻어지는 실행 시간 단축은 예측 품질에 따라 부드럽게 스케일링됨을 보여줍니다. 중요하게도, 우리의 알고리즘은 예측의 쌍독립성(pairwise independence)만을 요구하거나, 대안으로 예측기의 정확도에 대한 지식을 요구하지 않는데, 이는 일반적으로 가정되는 설정보다 엄격하게 더 약하고 현실적인 설정입니다.

원문 초록

The field of learning-augmented algorithms has demonstrated that machine-learned predictions can bypass worst-case lower bounds across a wide range of problems. So far, however, the focus has been almost exclusively on polynomial-time algorithms, where predictions improve competitive ratios, approximation guarantees, or running times. In this paper, we raise the question of whether predictions can push the frontier of exact exponential-time algorithms for NP-hard problems. We answer this question affirmatively by proposing a general approach that augments an entire family of state-of-the-art exact algorithms for a variety of subset selection problems. We show that a noisy predictor that is only marginally better than random guessing suffices to provably reduce the search space, and that the resulting runtime speedup scales smoothly with the prediction quality. Importantly, our algorithms require only pairwise independence of predictions or, alternatively, do not require the knowledge of the predictor's accuracy - both strictly weaker and more realistic settings than typically assumed.

제출 이력

확인된 버전만 표시합니다. 전체 제출 이력은 arXiv 원문에서 확인하세요.

  1. arXiv:2606.18807v1제출 시각 미확인

함께 살펴볼 논문

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

arXiv:2610.13574v1cs.LG공통 태그 feature selection, Combinatorial Optimization

고차원 금융 회귀에서 몬테카를로 트리 탐색을 통한 $L_0$ 특징 선택

$L_0$ Feature Selection via Monte Carlo Tree Search in High-Dimensional Financial Regression

특징(feature) 선택은 수많은 엔지니어링된 변수와 예측 변수 간의 강한 상관관계로 인해 모델(model)의 안정성과 해석 가능성이 저하되는 고차원 금융 회귀에서 핵심적인 문제입니다. 희소 회귀(sparse regression)에는 $L_1$ 정규화(regularization)(Lasso)가 널리 사용되지만, 정보성 신호가 상관관계를 갖는 변수들에 걸쳐 분산되어 있을 때는 수축(shrinkage) 특성이 제약으로 작용할 수 있습니다. 정확한 희소 회귀(exact sparse regression)는 이러한 수축을 피하지만 계산상 다루기 어려운 조합 최적화(combinatorial optimization) 문제를 해결해야 하며, 일반적으로 표본 외(out-of-sample) 오차가 아닌 표본 내(in-sample) 오차를 최소화하도록 적합됩니다. 본 논문에서는 일반화된 중첩 롤아웃 정책 적응(GNRPA)을 적용한 몬테카를로 트리 탐색(Monte Carlo Tree Search) 기반의 특징 선택 프레임워크를 제시합니다. 특징 선택을 순차적 의사결정 과정으로 정식화하며, 후보 부분집합은 학습(training) 오차 대신 표본 외 검증(validation) 성능을 기준으로 점수가 매겨집니다. 또한 본 방법은 부분집합 크기와 다중공선성을 고려하는 사전식 순서화 목적함수(lexicographic objective)를 지원합니다. 저자들은 시장, 거시경제 및 팩터 데이터를 포괄하는 1,072개의 엔지니어링된 특징으로부터 NASDAQ-100 지수의 주간 수익률을 설명하는 동시적 설명 회귀(contemporaneous explanatory regression) 과제에서 이 접근법을 연구합니다. 이는 다중공선성 환경에서의 부분집합 선택의 가치를 별개의 문제인 예측적 전망(forecasting)과 분리합니다. 이 과제에서 제안된 방법은 최적화된 Lasso 기준선(baseline)보다 더 높은 표본 외 설명력을 가진 희소 특징 부분집합을 식별하여, Lasso의 0.6313 대비 0.6961의 표본 외 $R^2$에 도달합니다. 이러한 결과는 몬테카를로 트리 탐색이 금융 회귀의 희소 설명적 특징 선택에서 볼록 정규화(convex regularization)의 실용적인 대안임을 시사하며, 표본 외 적합도만큼 투명성이 중요한 팩터 귀속(factor attribution) 및 위험 분해에 잠재적 가치가 있습니다.

arXiv:2607.14545v1cs.LG공통 태그 Combinatorial Optimization, learning-augmented algorithms

CASP: 검증 가능한 증명서와 유계 손실 PAC 보증을 갖춘 학습 증강 오프라인 근사

CASP: Learning-Augmented Offline Approximation with Verifiable Certificates and Bounded-Loss PAC Guarantees

기계학습 예측은 오프라인 NP-hard 최적화를 가속할 수 있지만, 예측기에게 무엇을 해야 할지 묻는 것은 문제를 푸는 것과 같으며, 검증되지 않은 예측을 확정하면 모든 최악의 경우 보장을 포기한다. CASP(Certificate-Augmented Solution Pruning)는 대신 탐색 공간의 어느 부분을 무시할 수 있는지 묻고, 각 답변은 건전한 다항 시간 검증기가 확인한 후에만 수용하므로 정확성은 예측 품질에 의존하지 않는다. 우리는 이 설계의 학습 이론을 개발한다. 검증기는 유도된 손실 클래스를 균일하게 유계로 만들므로, 증명서 매개변수는 $\tilde O(\varepsilon^{-2}\log K)$개의 샘플($K$는 최대 인스턴스 크기)로부터 학습 가능하다. 반면 검증되지 않은 확정 클래스는 분포 무관 수렴률을 허용하지 않으며, 비용 확산 $R$ 하에서는 $Ω(R/\varepsilon^2)$ 미만의 수렴률도 없다. 검증 가능한 신뢰도로 노이즈 예측을 필터링하는 방식은 닫힌 형식으로 계산한 마진을 갖고 표준 min-combiner보다 우수하며, LP가 주어져도 예측은 여전히 유용하다. 이는 퇴화 최적 면에서 동점을 깨기 때문인데, 여기서 확정이 인스턴스에 대해 검증 가능한 신뢰도 값을 통해서만 의존하는 모든 대칭 LP 정책은 증명 가능하게 정체된다. 5개 문제에 대한 실험은 이론의 정량적 예측을 검증한다. 학습된 예측기를 사용하면, 검증되지 않은 가지치기는 분포 이동 하에서 최적값의 최대 26%를 잃지만, 동일한 예측의 검증된 배포는 아무것도 잃지 않는다.

arXiv:2607.21609v2cs.AI공통 태그 Combinatorial Optimization

HierFlow: Hierarchical Coupled Dual-Space Search for Automatic Agentic Workflow Generation

구조화된 워크플로우는 대규모 언어 모델(LLM)이 복잡한 문제를 해결할 수 있게 해주지만, 이를 자동으로 생성하는 것은 방대한 조합적 탐색 공간으로 인해 심각하게 저해되며, 이는 종종 유연하지 않고 자원을 많이 소모하는 오프라인 학습 의존성을 초래한다. 이를 해결하기 위해, 우리는 워크플로우 생성을 상위 토폴로지 층이 하위 작업 경계를 규정하고 하위 수준의 실행 결과가 토폴로지 자체를 능동적으로 재형성하는, 토폴로지와 실행이 맞물린 탐색 패러다임으로 개념화한다. 이 기반 위에서, 우리는 피드백 기반 토폴로지 조정과 하위 워크플로우 최적화를 위한 빠른 MCTS(Monte Carlo Tree Search) 기반 트리 탐색을 결합하여 에이전트형 워크플로우 설계를 자동화하는, 학습 불필요·테스트 시점 계층적 탐색 아키텍처인 HierFlow를 제안한다. HierFlow는 맥락적 필요에 따라 실행 수준 탐색을 선택적으로 트리거하는 지능형 게이팅 모듈을 통해 효율성을 극대화하며, 우리는 작업 간 결합 정도가 계층적 분할의 효과에 미치는 영향을 상세히 분석함으로써 이 메커니즘을 추가로 뒷받침한다. 질의응답, 수학적 추론, 코드 생성 벤치마크에 걸친 종합적인 테스트는 HierFlow가 강력한 베이스라인을 지속적으로 능가하며, 추가 학습 부담 없이 고품질 결과와 계산 효율성의 최적 균형을 제공함을 확인한다.

arXiv:2609.27144v2cs.LG공통 태그 Prediction

미관측 교란 변수에 강건한 위험 점수 학습

Learning Risk Scores Robust to Unobserved Confounders

미관측 교란의 영향을 받는 역사적 관찰 데이터로부터, 희소 자원이나 개입 대상 개인의 우선순위를 정하기 위한 위험 점수를 학습하는 문제를 다룬다. 누가 희소 자원을 받을지에 대한 결정은 설문 응답과 같이 기록된 특성에 기반한 위험 점수에 의해 종종 안내된다. 이러한 위험 점수는 개인의 특성, 배분 결정, 결과에 대한 역사적 기록인 관찰 데이터로부터 직접 학습되는 경우가 점점 늘고 있다. 역사적 배분 정책이 도입한 바이어스를 보정하는 역 성향 가중치(inverse propensity weighting, IPW)와 같은 표준 방법은, 역사적 결정 과정이 기록된 특성으로 완전히 설명될 수 있다면 정확한 위험 점수를 학습하는 데 사용될 수 있다. 그러나 실무에서는 역사적 결정이 종종 기록되지 않은 정보에 의존하여, 학습된 위험 점수가 과거 우선순위를 이끌었던 기록되지 않은 상황을 가진 개인들을 정확히 체계적으로 과소 우선순위화하게 만든다. IPW를 기반으로, 이러한 종류의 미관측 교란에 강건한 위험 점수를 학습하는 방법을 제안한다. 미관측 교란 하에서는 성향 가중치를 신뢰할 수 있게 추정할 수 없으므로, 대신 관측 가능한 데이터와 교란 정도에 대한 도메인 정보 기반 추정치로 결정되는 불확실성 집합에 속하는 것으로 취급하며, 인과 추론(causal inference)의 민감도 분석(sensitivity analysis)과 Wasserstein 분포적 강건 최적화(Wasserstein distributionally robust optimization)를 결합한다. 그 결과 강건 위험 점수 학습 문제는 표본 기반 근사를 허용하며, 이를 기성 솔버와 호환되는 지수 원뿔 프로그램(exponential cone program)으로 재공식화한다. UCI Machine Learning Repository의 데이터셋에서 파생된 반합성(semi-synthetic) 데이터에서 접근법의 효과를 입증한다. 제안 방법은 다른 지표를 손상하지 않으면서, 전통적 벤치마크 대비 보정(calibration)을 최대 29.2%까지, 최신(state of the art) 대비 최대 11.1%까지 개선한다.

arXiv:2607.23316v2cs.NE공통 태그 Combinatorial Optimization

학생 학습 자원 배분을 위한 유전 알고리즘

A genetic algorithm for student academic resource allocation

개별 학생에게 학습 자원을 최적으로 배분하는 것은 학습자 다양성을 다루고 공평한 교육 성과를 촉진하는 데 필수적이다. Erasmus+ KA220-SCH 프로젝트의 틀 안에서, 본 논문은 고등학교 수학 학생을 위한 교육 자료 선택을 엄격한 학습 시간 제약을 따르는 0-1 이진 조합 최적화(optimization) 문제로 모델링한다. 이 공식화의 NP-hard 복잡도를 고려할 때, 자원 카탈로그가 확대될수록 정확한 해법은 계산적으로 다루기 어려워진다. 이 과제를 해결하기 위해, 우리는 이진 결정 공간을 효과적으로 탐색하기 위해 특화된 제약 복구 메커니즘과 통합된 유전 알고리즘(Genetic Algorithm)을 제안한다. 10회의 독립 실행에 걸친 실험적 평가는 빠른 수렴, 높은 해 품질, 그리고 서로 다른 기본 시드에 걸친 강한 알고리즘적 안정성을 보여준다. 이 결과는 중등 교육에서 실시간 의사결정 지원 시스템을 위한 메타휴리스틱(metaheuristic) 접근법의 실용적 유용성을 확인한다.

토론

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