연속 블랙박스 최적화의 알고리즘 선택을 위한 기하학적 프로빙
Geometric Probing for Algorithm Selection in Continuous Black-Box Optimization
한국어 초록
연속 블랙박스 최적화(continuous black-box optimization)를 위한 자동화된 알고리즘 선택은 제한된 프로빙(probing) 예산 내에서 문제로부터 어떤 정보를 획득하고 그 정보를 어떻게 표현하는지에 따라 결정됩니다. 본 연구에서는 위치, 방향 및 스케일에 걸쳐 다중 스케일 2차원 제한(restriction)을 샘플링하고, 유효성 인식 합성곱(validity-aware convolutional) 처리 및 순열 불변(permutation-invariant) 집계를 통해 정규화된 목적 함수 값 맵을 인코딩하는 기하학적 프로빙 프레임워크를 제안합니다. 동일한 예산 조건, 문제 내 및 문제 수준 전이, 융합, 표현 및 예산 분석 하에서 제안 기법을 고전적 ELA 및 Deep-ELA와 비교합니다. 나아가 통제된 절제 연구(ablation study)를 통해 프로브 획득과 프로브 처리를 분리하여 분석합니다. 실험 결과에 따르면 제안된 시각적 표현은 ELA 계열 특징(feature)과 상호 보완적인 솔버 성능 정보를 드러내며, 문제 수준 전이 상황에서 상대적 기대 실행 시간 측면의 상대적 우위를 유지하는 반면, 더 넓은 탐색 범위나 더 풍부한 특징, 혹은 예측 용이성만으로는 더 나은 알고리즘 선택을 보장하지 못함을 보여줍니다.
원문 초록
Automated algorithm selection for continuous black-box optimization depends on what information is acquired from a problem under a limited probing budget and how that information is represented. We introduce a geometric probing framework that samples multi-scale two-dimensional restrictions across location, orientation, and scale, and encodes their normalized objective-value maps with validity-aware convolutional processing and permutation-invariant aggregation. We compare our method with classical ELA and Deep-ELA under matched budgets, within-problem and problem-level transfer, fusion, representation, and budget analyses. We further disentangle probe acquisition from probe processing by controlled ablation. The results show that the proposed visual representation exposes solver-performance information complementary to ELA-family features and retains a relative advantage for relative expected runtime under problem-level transfer, while greater coverage, feature richness, or predictive accessibility alone does not guarantee better selection.
제출 이력
확인된 버전만 표시합니다. 전체 제출 이력은 arXiv 원문에서 확인하세요.
함께 살펴볼 논문
공통 태그를 근거로 연결했습니다. 실제 인용 관계나 논문의 우수성을 뜻하지 않습니다.
랜덤 투영을 통한 차원 축소가 경관 특징을 보존하는가
Does Dimensionality Reduction via Random Projections Preserve Landscape Features?
탐색적 경관 분석(ELA)은 블랙박스 최적화 문제를 특성화하기 위한 수치적 특징을 제공한다. 그러나 고차원 환경에서 ELA는 희소성 효과, 높은 추정기 분산, 그리고 여러 특징 클래스 계산에 드는 막대한 비용으로 인해 어려움을 겪는다. 이에 따라 차원 축소가 이러한 환경에서 ELA를 적용 가능하게 만드는 방법으로 제안되어 왔으나, 축소된 공간에서 계산된 특징이 원래 경관의 내재적 특성을 여전히 반영하는지는 불명확한 상태이다. 본 연구에서는 랜덤 가우시안 임베딩(RGE)을 통한 차원 축소 하에서 ELA 특징의 견고성을 조사한다. 동일한 샘플 점과 목적함수 값에서 출발하여, 투영된 공간에서 ELA 특징을 계산하고 이를 다양한 샘플 예산과 임베딩 차원에 걸쳐 원래 탐색 공간에서 얻은 특징과 비교한다. 실험 결과, 선형 랜덤 투영은 ELA와 관련된 기하학적 및 위상적 구조를 자주 변형하여 원래 문제를 더 이상 대표하지 않는 특징 값을 산출하는 것으로 나타났다. 일부 소수의 특징은 비교적 안정적으로 유지되지만, 대부분의 특징은 임베딩에 매우 민감하다. 또한 투영 하에서의 견고성이 반드시 정보성을 의미하지는 않는데, 겉보기에 견고한 특징이라도 경관의 내재적 특성이 아닌 투영으로 인한 아티팩트를 반영할 수 있기 때문이다.
탐색적 경관 분석 맥락에서 제한된 데이터 조건의 무작위 부분공간 샘플링
Sampling on Random Subspaces under Limited Data in the Context of Exploratory Landscape Analysis
고전적인 공간 충전 설계(space-filling design)는 고차원 문제나 기타 자원 제약 환경에서 흔히 나타나는 평가 예산이 제한된 경우, 탐색적 경관 분석(ELA)에 대한 신뢰할 수 있는 통계적 결과를 제공하지 못하는 경우가 많으며, 이로 인해 잡음이 많고 불안정한 경관 기술자(landscape descriptor)가 생성된다. 이 문제를 해결하기 위해, 우리는 무작위 선형 임베딩(random linear embedding)에 기반한 ELA의 대안적 샘플링 전략을 제안한다. 전체 결정 공간에서 균일하게 샘플링하는 대신, 무작위로 방향이 설정된 저차원 부분공간에 예산을 할당하고, 이것이 결과적인 경관 기술자의 강건성(robustness)을 향상시키는지 조사한다. 우리는 20차원 설정에서 COmparing Continuous Optimizers(COCO) 환경의 노이즈 없는 블랙박스 최적화 벤치마킹(BBOB) 테스트 스위트에 대해 여러 고전적인 ELA 특징 집합에 걸쳐 전체 공간 샘플링 전략과 임베딩 기반 샘플링 전략을 비교한다. 우리의 결과는 무작위 선형 임베딩이 예산 제약 ELA에 대한 유망한 대안을 구성함을 시사하나, 그 효과는 특징 클래스와 기반 문제에 따라 달라진다.
타원체 샘플링을 활용한 무매개변수 영차 최적화
Parameter-Free Zeroth-Order Optimization with Ellipsoidal Sampling
영차 최적화(zeroth-order optimization) 방법은 그래디언트 정보를 사용할 수 없거나 계산 비용이 많이 드는 블랙박스 문제를 해결하는 데 필수적입니다. 본 논문에서는 부분공간 사전조건화(subspace preconditioning)와 타원체 무작위 샘플링(ellipsoidal randomized sampling)을 통합하여 최근의 POEM 방법을 확장한 새로운 무매개변수(parameter-free) 확률적 영차 알고리즘인 POEM-ES를 제시합니다. 등방성(isotropic) 무작위 방향에 의존하는 전통적인 영차 접근 방식과 달리, POEM-ES는 기저의 저차원 기하학적 구조를 인코딩하는 고정된 구조적 대칭 양의 준부호(SPSD) 사전조건자 $\hatΣ$에 의해 유도되는 비등방성(anisotropic) 샘플링을 수행합니다. $λ_{\max}(\hatΣ) = 1$인 표준 구조적 스펙트럼 정규화 조건 하에서, 본 연구는 문제의 내재적 차원을 반영하고 샘플링 및 무작위 스무딩 매개변수 스케줄 모두를 유도하는 경험적 유효 차원 $d^* = \operatorname{tr}(\hatΣ)$의 활용을 도입합니다. 실제 적용에서 이러한 사전조건자는 파일럿 샘플링, 과거 궤적 또는 도메인 특화 전문가 지식을 통해 효과적으로 얻을 수 있습니다. 본 연구에서는 POEM-ES가 저계수 구조적 가정을 만족할 때 차원이 축소된 수렴 속도를 달성하며, 단지 $\tilde{\mathcal{O}}\left( \frac{\left( r^2 κ(\hatΣ) + d^* \right) L^2 D_{\mathcal{X}}^2}{\varepsilon^2} \right)$회의 확률적 영차 오라클 쿼리만을 요구함을 증명합니다. 제안된 방법은 완전히 매개변수 없이(parameter-free) 유지되며, $d^* \ll d$인 저계수 구조를 가진 문제에서 기존 POEM 대비 현저한 개선을 입증합니다. LibSVM 데이터셋을 사용한 힌지 손실 이진 분류 태스크에 대한 수치 실험은 제안된 접근법의 실질적인 우수성을 확인해 줍니다.
텍스트 임베딩을 통해 도메인 지식 없이 수행하는 알고리즘 선택
Algorithm Selection with Zero Domain Knowledge via Text Embeddings
수작업으로 설계된 인스턴스 특징 대신 사전학습(pre-training)된 텍스트 임베딩(embedding)을 활용하는 특징 없는 알고리즘 선택 접근법인 ZeroFolio를 제안합니다. 이 방법은 원시 인스턴스 파일을 일반 텍스트로 읽어 사전학습된 임베딩 모델로 임베딩한 후, 가중치 적용 k-최근접 이웃(weighted k-nearest neighbors)을 통해 알고리즘을 선택합니다. 우리의 접근법은 사전학습된 임베딩이 어떠한 도메인 지식이나 태스크별 학습(training) 없이도 문제 인스턴스를 구별할 수 있다는 관찰에 기반합니다. ZeroFolio는 텍스트 기반 인스턴스 형식을 가진 모든 문제 도메인에 적용할 수 있습니다. 7개 도메인(SAT, MaxSAT, QBF, ASP, CSP, MIP 및 그래프 문제)에 걸친 11개 ASlib 시나리오에서 접근법을 평가합니다. ZeroFolio는 11개 시나리오 중 9개에서 수작업 특징으로 학습된 랜덤 포레스트(random forest)보다 우수한 성능을 보이며, 종종 큰 폭의 성능 향상을 기록하고, 그중 8개 시나리오에서는 모든 직렬화 시드(serialization seed)에 대해 뛰어난 성능을 보입니다. 시나리오별로 튜닝된 랜덤 포레스트를 상대로도 11개 시나리오 중 8개에서 승리합니다. 2015 ICON 챌린지에서 공개된 AutoFolio 결과가 있는 3개 시나리오에서, ZeroFolio는 시나리오별 튜닝 없이도 AutoFolio와 근소한 마진 내의 성능을 달성합니다. SAT12-ALL에 대한 절제 연구(ablation study)는 역거리 가중치(inverse-distance weighting)와 라인 셔플링이 성능을 향상시킴을 보여줍니다. 나아가 직렬화 시드에 대한 접근법의 민감도를 분석합니다. 랜덤 포레스트가 더 강력한 SAT12-ALL 시나리오의 경우, 소프트 보팅(soft voting)을 통해 두 방식을 결합함으로써 추가적인 성능 향상을 얻을 수 있습니다.
LLM을 통한 풍부한 보조 정보를 활용한 베이즈 최적화
Bayesian Optimization with Rich Auxiliary Information via LLMs
베이즈 최적화(Bayesian Optimization, BO)는 비용이 많이 드는 블랙박스 함수를 최적화하는 데 널리 사용되지만, 일반적으로 각 고비용 실험을 입력값과 목적함수 값으로만 단순화하여 실험에서 생성되는 많은 정보를 버립니다. 이러한 보조 정보에는 하이퍼파라미터 최적화에서의 학습 곡선, 과학 실험에서의 전문가 노트 및 이미지, 또는 특정 최적화 문제에 대해 알려진 사실 등이 포함될 수 있습니다. 대규모 언어 모델(LLM)이 다양하고 비정형화된 정보를 처리할 수 있는 능력을 활용하여, 본 논문에서는 두 가지 방법을 소개합니다. 즉, 보조 정보를 사용하여 최적값의 위치에 대한 신념을 발전시키는 AuxBO-Evolve와, 보조 정보를 활용해 획득 함수(acquisition function)를 국소적으로 안내하는 AuxBO-Vicinity입니다. 합성 작업, 하이퍼파라미터 최적화 벤치마크, 과학자가 작성한 비정형 로그가 포함된 핵융합 작업 전반에서 제안 방법들은 최적화 성능을 일관되게 향상시키며 표준 BO 및 기존 LLM 기반 접근법들을 능가합니다. 나아가 본 연구는 LLM이 점별(pointwise) 목적함수 값을 모델링하기보다는 유력한 최대화 지점의 위치를 모델링할 때 더욱 효과적인 확률론적 가이드를 제공한다는 점을 밝혀냈습니다. 전반적으로 본 연구 결과는 표준 $(\mathbf{x}, y)$ 상호작용을 넘어선 풍부한 정보를 활용하는 것이 BO 성능을 대폭 향상시킬 수 있음을 입증합니다.
대규모 언어 모델을 활용한 온라인 자동 알고리즘 설계
Online Automated Algorithm Design with Large Language Models
대규모 언어 모델(LLM)은 추론과 코드 합성을 통해 자동 알고리즘 설계(AAD)를 가능하게 한다. 그러나 기존의 LLM 기반 AAD 방법 대부분은 알고리즘 설계와 대상 최적화를 분리하여, 최적화 상태가 변화하는 동안에도 고정된 설계를 그대로 배포한다. 기존의 적응형 옵티마이저는 이러한 변화에 대응할 수 있지만, 그 조정은 사전에 정의된 파라미터, 연산자 또는 전략의 범위에 국한된다. 이러한 한계를 해결하기 위해, 본 논문은 알고리즘 자체를 상태 의존적 결정 변수로 취급하는 새로운 최적화 패러다임인 온라인 LLM 기반 AAD를 제안한다. 각 단계에서 LLM 에이전트는 현재의 최적화 상태로부터 새로운 동작 로직을 갖춘 알고리즘을 합성한다. 생성된 알고리즘을 실행하면 탐색이 진행되고 이후 설계를 위한 피드백이 제공되므로, 별도의 오프라인 알고리즘 사전학습 단계 없이도 알고리즘 설계와 대상 최적화가 결합된다. 이 패러다임을 구현하기 위해 본 논문은 상충하는 설계 관점을 조율하여 실행 가능한 알고리즘을 합성하고, 실행 피드백을 활용해 이후 설계를 위해 런타임 증거를 해석하는 방식을 개선하는 멀티 에이전트 프레임워크인 OnDesign을 제안한다. 우리는 두 가지 주류 블랙박스 최적화 패러다임에 걸친 세 가지 시나리오, 즉 베이지안 최적화, 진화적 연속 최적화, 진화적 혼합 변수 최적화에서 OnDesign을 평가한다. 여섯 개의 벤치마크 스위트와 하나의 공학 문제에 대해 다양한 문제 차원에서 수행한 광범위한 실험을 통해, 기존 옵티마이저와 오프라인 LLM 기반 AAD 방법보다 우수한 전반적 성능을 보임을 입증한다.
토론
이 논문과 연결된 포럼 글이 아직 없습니다.
저자 비고
arXiv Comments
21 pages, 15 figures, 4 tables; extended journal version of a GECCO Companion 2026 paper; code available at https://doi.org/10.5281/zenodo.22822605