PaperlayerView exact revision on arXiv

Source-linked AI summary

Constraint-Aware Discrete Black-Box Optimization Using Tensor Decomposition

Keisuke Onoue, Ryosuke Kojima

arXiv:2609.09370v1cs.LG

TL;DR

Discrete black-box optimization often uses surrogates that do not capture known logical feasibility constraints. This paper proposes CA-TD, which integrates those constraints into tensor-decomposition surrogate learning through constrained polynomial optimization and T-norm-based relaxation, improving sample efficiency across diverse benchmarks while remaining limited by high-dimensional memory demands.

  • Problem

    Existing surrogate models often ignore the symbolic feasibility structure of discrete input spaces, which can impair approximation in sparse feasible regions.

  • Method

    CA-TD integrates logical feasibility into tensor-decomposition surrogates by formulating learning as polynomial optimization and applying a differentiable T-norm-based penalty.

  • Results

    CA-TD improves sample efficiency across diverse synthetic and real-world benchmarks and achieves performance comparable or superior to strong baselines such as NN+MILP.

  • Takeaways & Limitations

    Embedding feasibility directly into the surrogate can guide exploration more effectively than handling constraints only during acquisition optimization.

  • Takeaways & Limitations

    CA-TD remains constrained by memory demands in high-dimensional search spaces, motivating sparse tensor representations and further scalability improvements.

Abstract

from arXiv · show

Discrete black-box optimization is often addressed using approaches such as Sequential Model-Based Optimization (SMBO), which aims to improve sample efficiency by fitting surrogate models that approximate a costly objective function over a discrete search space. In many real-world problems, the set of feasible inputs is often given by logical constraints known in advance. However, existing surrogate modeling techniques generally fail to capture the symbolic rules governing feasibility in discrete input spaces. In this paper, we propose a surrogate modeling approach based on tensor decomposition that captures the structure of discrete search spaces while directly integrating feasibility information. To implement this approach, we formulate surrogate model training as a constrained polynomial optimization problem and solve a relaxed formulation using a differentiable penalty term derived from T-norms. Our experiments on both synthetic and real-world benchmarks, including a pressure vessel design task, demonstrate that the proposed method improves sample efficiency by effectively guiding the search away from infeasible regions.

1 Introduction

The paper addresses discrete black-box optimization with known logical constraints by integrating feasibility into tensor-decomposition surrogate modeling. CA-TD formulates constrained surrogate learning with a differentiable T-norm penalty and improves sample efficiency across synthetic and real-world benchmarks.

  • Existing surrogate models typically treat feasibility separately from learning, which can produce poor approximations in sparse feasible regions.
  • CA-TD represents the objective with tensor decomposition while incorporating logical constraints given a priori.
  • The method formulates surrogate training as a constrained polynomial optimization problem and uses T-norms to create a differentiable penalty for gradient-based learning.
  • CA-TD improves sample efficiency compared with conventional methods on synthetic and real-world benchmarks, including an engineering design task.

2 Preliminaries

The paper frames discrete black-box optimization as costly search over finite product spaces and introduces tensor-decomposition surrogates for approximating partially observed objective tensors. Sequential model-based optimization iteratively fits a surrogate, selects the next point through an acquisition function, and updates its observation history.

  • Discrete Black-Box Optimization: Discrete BBO searches a finite product space X = X1 × · · · × Xd for an objective minimizer when derivatives and other internal information are unavailable.Evaluated values are yt = g(xt), and the accumulated observations form the history H.
  • Sequential Model-Based Optimization: SMBO fits a surrogate to prior observations, selects the next point by maximizing an acquisition function, evaluates the black-box objective, and updates the history.The objective is costly to evaluate, so the procedure seeks good solutions with as few evaluations as possible.
  • Tensor-Decomposition Surrogates: Tensor contraction combines cores over shared indices, providing the fundamental operation for tensor-based surrogate models.In TT decomposition, boundary ranks are one, and the parameter count scales as O(d n R^2).
  • Tensor-Decomposition Surrogates: A partially observed tensor stores objective values at evaluated points, while a low-rank tensor-decomposition surrogate approximates the full objective tensor.The paper considers CP, TR, and TT formats, with rank controlling model complexity.
  • Differentiable Logic: T-norms extend logical conjunction to continuous truth values, enabling symbolic rules to be incorporated into gradient-based learning.The Łukasiewicz T-norm is TL(a, b) = max(0, a + b − 1), and implication can be relaxed through a residuum.

3 Proposed Method: Constraint-Aware Tensor Decomposition Surrogate

CA-TD integrates known feasibility constraints directly into a tensor-decomposition surrogate for discrete SMBO. It formulates constrained surrogate learning as polynomial optimization and uses a differentiable T-norm penalty, while ensemble uncertainty supports acquisition-based exploration and exploitation.

  • Constraint-Aware Surrogate: CA-TD embeds feasibility information directly into tensor-decomposition surrogate training rather than handling constraints only through acquisition optimization.The surrogate is intended to learn feasibility information and maintain awareness of feasible regions throughout the search.
  • Constraint Formulation: The constrained surrogate must satisfy ˆY[x] ≥ τt on infeasible inputs, where τt is based on the maximum feasible value observed so far.If no feasible point has been observed, τt is set to a predefined sufficiently large value.
  • Constraint Formulation: The resulting constrained learning problem is a polynomial optimization problem because the surrogate tensor is polynomial in its core parameters.A semidefinite-programming hierarchy is used as an alternative solver, referred to as HSDP.
  • PGRAD Training: PGRAD relaxes the infeasibility rule with Łukasiewicz implication and penalizes expected violations over the infeasible region during gradient-based surrogate training.The penalty discourages the surrogate from assigning low objective values to known-infeasible inputs.
  • Uncertainty-Aware Acquisition: An ensemble of independently initialized tensor-train models yields predictive means and standard deviations used in expected improvement to prioritize low predictions with high uncertainty.The empirical predictive distribution is formed from ensemble predictions at each input.

4 Related Work

Prior constrained black-box optimization methods commonly modify acquisition functions or optimize them over feasible regions, while tensor-decomposition methods have mainly addressed unconstrained optimization or initialization. CA-TD instead integrates logical feasibility constraints into surrogate updates throughout the search.

  • Constrained Black-Box Optimization: Existing constrained BBO approaches commonly use Gaussian-process constraint models, augmented Lagrangians, level-set estimation, or acquisition optimization under explicit constraints.Examples include GP-based feasibility estimates combined with expected improvement and GP or neural-network optimization through mixed-integer programming.
  • Constrained Black-Box Optimization: CA-TD differs from most constrained BBO methods by incorporating known feasibility information directly into surrogate training rather than modifying only the acquisition function.This design aims to make the surrogate itself approximate both objective behavior and feasibility structure.
  • Tensor-Decomposition Optimization: OptimaTT and TTOpt primarily target unconstrained optimization, whereas PROTES encodes feasibility in a binary tensor to guide initial exploration.These approaches provide context for CA-TD’s focus on constraint integration beyond initialization.
  • Tensor-Decomposition Optimization: CA-TD incorporates constraints into surrogate updates at every optimization step, aiming to improve sample efficiency by maintaining feasible-region awareness throughout the search.This contrasts with approaches that use constraints only during proxy initialization.
  • Logic-Integrated Tensor Decomposition: Unlike prior constrained tensor decomposition focused on non-negativity or orthogonality, CA-TD imposes point-wise logical constraints derived from task feasibility rules.The paper presents this as a neuro-symbolic application to tensor-based global optimization.

5 Experiments

Experiments evaluate CA-TD across synthetic, engineering, path, medical, and combinatorial benchmarks, comparing training strategies, baselines, and tensor formats. Results show that integrating feasibility into surrogate training improves efficiency, while scalability and tensor-format performance remain problem-dependent.

  • Experiment 1: HSDP vs. PGRAD: PGRAD scales better than HSDP on larger Ackley grids, while HSDP converges slightly earlier on small grids.HSDP times out at 4000 seconds per round on the 7 × 7 case, whereas PGRAD remains under one second per round.
  • Experiment 1: HSDP vs. PGRAD: Constraint-aware variants outperform unconstrained variants in both convergence speed and final objective value across Ackley cases.The experiments compare explicit feasibility integration against unconstrained training.
  • Experiment 2: Baseline Comparison: Constraint-aware CA-TD improves sample efficiency and performs competitively with NN+MILP across diverse combinatorial benchmarks.The comparison includes multiple tensor formats and baselines across five benchmark tasks.
  • Experiment 2: Baseline Comparison: CA-TD consistently outperforms GP-u, TPE-u, GP-c, and TPE-c, while performing comparably to NN+MILP methods.The results distinguish models that learn constraints during surrogate training from methods that use constraints only during acquisition.
  • Experiment 3: Tensor Formats: No tensor format dominates universally: TT is robust, whereas CP achieves the lowest objectives on some GAP and Ising tasks and TR is competitive in several instances.The framework’s constraint-penalty approach remains effective across TT, CP, and TR formats.
  • Discussion: CA-TD remains limited by memory demands in high-dimensional search spaces, despite PGRAD speedups and preliminary mini-batching.Sparse tensor representations are identified as an important direction for future scalability.

6 Conclusion

The paper concludes that CA-TD is a constraint-aware tensor-decomposition surrogate for discrete sequential black-box optimization, trained through polynomial optimization and a relaxed gradient-based procedure. Experiments across synthetic and real-world benchmarks are reported to improve sample efficiency, while future work targets scalability and broader variable domains.

  • Conclusion: CA-TD integrates symbolic feasibility information directly into tensor-decomposition surrogates for discrete sequential black-box optimization.The approach is designed as a constraint-aware surrogate modeling method.
  • Conclusion: The method formulates learning as polynomial optimization and introduces PGRAD as a scalable relaxed gradient-based algorithm for neuro-symbolic integration.PGRAD embeds logical constraints through a penalty during surrogate training.
  • Conclusion: Experiments across diverse synthetic and real-world benchmarks demonstrated improved sample efficiency compared with conventional methods.The conclusion attributes the reported outcome to embedding constraints into the surrogate rather than relying solely on acquisition optimization.
  • Future Work: Future work includes higher-dimensional discrete spaces, sparse tensor representations, automatic rank selection, and extensions to continuous or mixed-variable optimization.These directions define the stated scope for improving scalability and applicability.

A.1 Benchmarks for Experiment 2

The benchmarks cover constrained discrete optimization across synthetic functions, engineering design, path planning, treatment planning, and combinatorial tasks. Each task defines a discrete search space, objective, and feasibility rules drawn from geometry, domain knowledge, or combinatorial structure.

  • The benchmark suite spans Ackley optimization, pressure-vessel design, Warcraft path planning, diabetes treatment planning, neural architecture search, DNA binding, generalized assignment, and Ising tasks.These tasks include synthetic, engineering, real-world-inspired, and combinatorial settings.
  • Pressure Vessel: Pressure Vessel minimizes cylindrical-vessel cost over four discretized variables subject to four inequality constraints.The original problem has two continuous and two integer variables, with 10 sampled levels per variable used here.
  • Warcraft: Warcraft evaluates candidate paths by traversal cost and proximity to the bottom-right corner while requiring valid start, length, and endpoint conditions.The evaluated map sizes contain 74 and 76 candidate paths for 2 × 2 and 2 × 3 grids, respectively.
  • Diabetes: The Diabetes task searches 5-level configurations of eight patient features for lower predicted diabetes probability while penalizing deviations from the original individual.A random forest supplies the probability prediction, and lower objective values represent medically plausible, effective suggestions.
  • Diabetes: Feasibility constraints exclude physiologically contradictory diabetes configurations, such as simultaneously low insulin and high glucose under specified thresholds.The setup tests whether CA-TD can internalize symbolic prior knowledge in a real-world-inspired search space.
  • Additional constrained tasks: The additional combinatorial benchmarks impose constraints on assignments, neural architectures, DNA sequences, and item-selection vectors while optimizing task-specific metrics.Examples include capacity constraints in GAP, operation or channel-count limits in NAS, GC-content restrictions in DNA binding, and group-balance constraints in Ising tasks.

B Experimental Details

Experiments ran in a controlled computational environment using fixed hardware, software, memory, and timeout allocations. The tensor-decomposition training pipeline used semidefinite-programming tools alongside standard numerical libraries.

  • Each run used 4 Intel Xeon Gold 6230R CPU cores, 8 GB memory, and a 3600-second timeout on Ubuntu 22.04.5 LTS.The software environment used Python 3.12.2, PyTorch 2.4.1, and NumPy 2.1.2.
  • HSDP training used ncpol2sdpa and cvxpy with SDPA as the backend semidefinite-programming solver.

C Detailed Experimental Results

The detailed results compile full method and baseline comparisons across the initial benchmarks and tensor ranks. Penalty sensitivity is broadly stable, with only a minor slowdown at very high penalties on one Warcraft setting.

  • Tables 5–7 provide comprehensive performance details for proposed methods, baselines, and tensor ranks, including comparisons against NN+MILP.
  • Performance is remarkably robust to λ from 0.0001 to 10 across CP-c, TR-c, and TT-c surrogates, supporting λ = 1.0 as the standard setting.Figure 4 reports nearly identical convergence behavior across this range and all benchmarks.
  • CA-TD remains competitive on Warcraft 2 × 3 even when high penalties slightly slow initial convergence.The exception occurs at λ = 10 and λ = 5 and is attributed to overly penalizing constraints on a more difficult landscape.

D.2 Effect of Offline Training on GP and TPE Baselines

Offline infeasible-point information generally harmed GP and TPE optimization, while baseline-specific ablations identified settings that balance convergence and computational cost.

  • Offline training: Increasing pre-trained infeasible points generally degraded GP-c and TPE-c optimization performance across all five benchmarks.The study varied the number of offline infeasible inputs from 0 to 2000; degradation was especially severe for GP because of cubic scaling.
  • Offline training: GP-c suffered truncated convergence and premature termination as additional data increased computational overhead.TPE-c was more computationally robust but showed a similar degradation trend.
  • NN+MILP ablation: For NN+MILP, constrained problems favored one initial point, whereas unconstrained problems benefited from 50 initial points.The preferred initialization depended on the constraint setting.
  • NN+MILP ablation: NN+MILP performance gains generally plateaued at 1000 epochs, making longer training comparatively inefficient.Further training up to 25,000 epochs yielded diminishing returns relative to its computational cost.
  • PROTES ablation: PROTES performed most reliably with batch size B = 100 and top-sample count K = 10 across tested tasks.TT-ranks 3, 4, and 5 were often similar after selecting these settings, so rank 4 was adopted.

E Constraint Violation during Training

The analysis examines constraint violations during CA-TD and PGRAD optimization, while also identifying memory usage as the main scalability bottleneck addressed by mini-batching.

  • Constraint violations: CA-TD did not theoretically guarantee feasibility, yet it practically proposed feasible points almost exclusively during SMBO optimization.The cumulative number of rejected proposals did not increase throughout optimization.
  • Constraint violations: PGRAD violations were measured as the fraction of constraint-violating samples among all samples used in each gradient step.Figure 9 reports this ratio during surrogate-model training.
  • Scalability: Memory usage is the main bottleneck for tensor decomposition-based methods and motivates batching as a mitigation.Dense Float32 tensors require 0.4 GB for 10^8, 4.0 GB for 10^9, and 40.0 GB for 10^10 search-space sizes.
  • Mini-batching: The mini-batch method samples loss and acquisition computations while always including previously observed feasible points in each training batch.This design avoids loading the entire search space into memory and is expected to reduce computational and memory loads.

F.1 Ablation Study on Batch Size

Batch size strongly affects tensor-decomposition optimization: larger batches approach full-batch behavior, while mini-batching enables high-dimensional optimization but can lose accuracy later.

  • Batch-size ablation: Larger batches improved convergence toward the full-batch baseline in the 10^4-space Ackley experiment.The study varied batch sizes 128, 256, 512, and 1024 for tensor training and acquisition inference.
  • Tensor batch size: Reducing the tensor-training batch size substantially degraded convergence and final objective values, whereas larger batches behaved similarly to full-batch training.This effect was observed while acquisition evaluation remained full-batch.
  • High-dimensional scalability: Mini-batched CA-TD enabled optimization in a 10^10 search space where direct full-batch tensor decomposition was computationally infeasible.With mini-batch size 1024, the execution time was approximately 4.43 ms per iteration.
  • High-dimensional comparison: CA-TD outperformed NN+MILP early on the high-dimensional task, but NN+MILP performed better in later optimization stages.The later-stage shift is attributed to accumulated approximation errors in mini-batched tensor decompositions.
  • Polynomial formulation: The constrained surrogate-learning problem is a polynomial optimization problem because TT parameters define polynomial objectives and polynomial inequality constraints.The decision variables are TT core elements, the objective is polynomial least-squares error, and constraints impose polynomial lower bounds.
Loading 2609.09370v1…