Unified framework for combinatorial and rounding algorithms in experimental design.
problem Designing and analyzing combinatorial and rounding algorithms for experimental design problems.
method Local search framework for combinatorial algorithms and regret minimization framework for rounding algorithms.
result Unified approach to match and improve all known results in D/A/E-design and obtain new results in unknown settings.
VSD efficiently learns conditional distributions for combinatorial designs.
problem Learning conditional distributions for rare combinatorial designs.
method Variational Search Distributions (VSD) using variational inference.
result VSD outperforms existing methods on real sequence-design problems.
A new experimental design method for combinatorial interventions reduces complexity and improves accuracy.
problem Efficiently conducting all possible combinatorial interventions with multiple treatments and potential interactions.
method Probabilistic factorial experimental design, applying random combinations of treatments and adapting over multiple rounds.
result Optimal dosage of 1/2 for each treatment yields near-optimal design for estimating any k-way interaction model.
New method for mixed-variable GSA improves material design efficiency.
problem Designing materials with both quantitative and qualitative variables.
method Integrates LVGP with Sobol' analysis for mixed-variable GSA.
result Accelerates exploration of novel MOF candidates in combinatorial design spaces.
Paper solves no-swap regret minimization for combinatorial bandits with polylogarithmic dependence on N.
problem Design efficient no-swap regret algorithms for combinatorial bandits with exponentially large action space.
method Introduces a no-swap-regret learning algorithm with polylogarithmic dependence on N and demonstrates efficient implementation.
result Achieves no-swap regret with polylogarithmic dependence on N, resolving an open problem.
AntBO optimizes antibody design using Bayesian optimization for efficient and effective CDRH3 sequence generation.
problem Designing optimal antigen-specific CDRH3 regions in antibody design due to combinatorial sequence space.
method Combinatorial Bayesian optimization framework with trust region for developability.
result AntBO designs CDRH3 regions with diverse biophysical properties and outperforms existing methods.
New algorithms tackle adversarial combinatorial bandits with switching costs.
problem Adversarial combinatorial bandits with switching costs.
method Design algorithms operating in batches to restrict switches, proving lower bounds and achieving upper bounds on regret.
result Achieved upper bounds on regret for both bandit and semi-bandit feedback settings.
This paper tackles combinatorial pure exploration for dueling bandits, aiming to find the best candidate-position match.
problem Finding the best candidate-position match in a dueling bandit setting.
method The paper adapts combinatorial pure exploration for multi-armed bandits to dueling bandits, considering both Borda winner and Condorcet winner cases. It designs PAC and exact algorithms for Borda winner and a fully polynomial time approximation scheme (FPTAS) for Condorcet winner.
result The paper introduces the first algorithm with polynomial running time per round for identifying the Condorcet winner in CPE-DB.
Automates supervised learning pipeline design with matrix and tensor factorization.
problem Designing effective supervised learning pipelines with many choices.
method Uses matrix and tensor factorization to model pipeline search space and develops greedy experiment design protocols.
result Demonstrates the effectiveness of the approach on real-world classification problems.
End-to-end trainable graph matching using improved combinatorial solvers.
problem Graph matching in deep learning.
method Combining deep learning with optimized combinatorial solvers.
result Advances state-of-the-art on deep graph matching benchmarks.
DeepCO uses deep learning for offline combinatorial optimization in warehouse operations.
problem Optimizing warehouse operation sequences in offline settings.
method DeepCO framework utilizing distribution regularized optimization for TSP.
result DeepCO reduces route length by 5.7% on average for TSP problems.
RL improves combinatorial optimization by automating heuristic search.
problem Hard combinatorial optimization problems with suboptimal solutions.
method Training RL agents to solve these problems.
result RL can outperform traditional algorithms in solving complex problems.
Greedy MI maximization method outperforms existing approaches in nonlinear models.
problem Maximizing mutual information in nonlinear models with non-Gaussian noise.
method Greedy approaches based on log-Sobolev inequalities for computationally inexpensive MI lower bounds.
result Proposed method outperforms random selection and Gaussian approximations.
New GFlowNet training framework using policy gradients for combinatorial object generation.
problem Training efficiency and robustness in GFlowNet models.
method Policy-dependent rewards and coupled training strategy for forward and backward policies.
result Advanced RL perspectives for robust gradient estimation improve GFlowNet performance.
The paper offers efficient algorithms for combinatorial and linear bandits using empirical process theory.
problem Optimal algorithms for combinatorial and linear bandits with practical sample complexity.
method Empirical process theory, Gaussian-width, minimizing experimental design objective.
result Sample complexity matches lower bounds, especially for combinatorial classes.
The aim of our paper is to construct pseudo H H H -type algebras from the covering free nilpotent two-step Lie algebra as the quotient algebra by an ideal. We propose an explicit algorithm of construction of such an ideal by making use of a non-degenerate scalar product. Moreover, as a bypass result, we recover the existe…
MOCA-HESP optimizes high-dimensional combinatorial and mixed spaces using hyper-ellipsoid partitioning.
problem Challenges in optimizing high-dimensional, combinatorial and mixed spaces.
method MOCA-HESP uses hyper-ellipsoid space partitioning with different categorical encoders and multi-armed bandit for adaptive selection.
result MOCA-HESP outperforms existing methods on various synthetic and real-world benchmarks.
Unified framework for gradient estimation in combinatorial spaces.
problem Scaling relaxed gradient estimators to large combinatorial distributions.
method Introducing stochastic softmax tricks within the perturbation model framework.
result Stochastic softmax tricks improve model performance and discover more latent structure.
New algorithm for adaptive experimental design in scientific settings.
problem Identifying true positives while controlling false discoveries in adaptive experimental design.
method Provably sample efficient adaptive algorithm for FDR control.
result First provably sample efficient adaptive algorithm for adaptive experimental design.
Bayesian optimization method tackles combinatorial spaces, scalable for large data.
problem Optimization over combinatorial categorical spaces in natural sciences.
method Combines variational optimization and continuous relaxations for gradient-based optimization.
result Method performs comparably to state-of-the-art methods while scaling well.
Paper proposes new gradient codes for robust distributed machine learning.
problem Robustness against slow machines (stragglers) in distributed machine learning.
method Constructs gradient codes based on probabilistic and Kronecker product methods.
result Gradient codes exist for a wide range of system parameters with comparable error performance.
GFlowNets improve combinatorial optimization by efficiently sampling from solution spaces.
problem NP-hard combinatorial optimization problems with structured constraints.
method Design Markov decision processes and train conditional GFlowNets to sample solutions.
result GFlowNet policies find high-quality solutions efficiently on various CO tasks.
A new algorithm balances exploration and exploitation in online decision-making.
problem Balancing exploration and exploitation in online decision-making.
method Proposed C 4 C^4 C 4 -UCB algorithm incorporating conservative mechanism. result Proved n-step upper regret bound for two situations.
This paper presents a framework to tackle combinatorial optimization problems using neural networks and reinforcement learning. We focus on the traveling salesman problem (TSP) and train a recurrent network that, given a set of city coordinates, predicts a distribution over different city permutations. Using negative t…
New experimental design minimizes regret in bandits.
problem Minimizing regret in online stochastic linear and combinatorial bandits.
method Experimental design-based algorithm balancing information gain and reward.
result State-of-the-art finite time regret guarantees and computational efficiency.
Designs efficient factorial experiments for product design under budget constraints.
problem Designing effective experiments for product design with limited traffic and overlapping experiments.
method Two-stage design: first stage samples and infers performance, second stage selects a final policy.
result The method outperforms one-shot tensor completion and unstructured best-arm benchmarks.
Generative models enhance BO for large batch optimization.
problem Efficiently sampling solutions in high-dimensional, combinatorial design spaces.
method Train generative models to sample solutions proportional to expected utility.
result Generative models can approximate optimal target distributions under certain conditions.
New algorithm reduces combinatorial semi-bandit regret efficiently.
problem Optimizing rewards from uncorrelated items in combinatorial semi-bandits.
method Developed an approximate version of ESCB with polynomial complexity.
result Achieved statistically efficient and polynomial time algorithm for combinatorial semi-bandits.
We propose a new framework for designing estimators for off-policy evaluation in contextual bandits. Our approach is based on the asymptotically optimal doubly robust estimator, but we shrink the importance weights to minimize a bound on the mean squared error, which results in a better bias-variance tradeoff in finite…
Transforms offline greedy algorithms to online algorithms for combinatorial problems.
problem Online decision-making in time-varying combinatorial environments.
method General framework using Blackwell approachability and Bandit Blackwell approachability.
result Achieves O ( T ) O(\sqrt{T}) O ( T ) regret in full information setting and O ( T 2 / 3 ) O(T^{2/3}) O ( T 2/3 ) regret in bandit setting. New analysis shows Thompson Sampling can work with greedy approximations in combinatorial bandits.
problem Thompson Sampling's theoretical limits with greedy approximations in combinatorial semi-bandits.
method Study with greedy oracle, providing lower and upper bounds on regret.
result First theoretical results showing TS can work with greedy approximations, breaking misconceptions.
Optimistic covariance-adaptive algorithms improve combinatorial semi-bandits regret.
problem Optimal regret in stochastic combinatorial semi-bandits with adaptive covariance estimation.
method Design of OLS-UCB-C and COS-V algorithms leveraging online covariance estimation.
result Improved gap-free regret with T^1/2 complexity for COS-V.
New algorithm for combinatorial bandit problems reduces regret.
problem Optimal selection of sets of arms in bandit problems.
method SGB algorithm with optimized exploration of unselected arms.
result Achieves ( 1 − 1 / e ) (1-1/e) ( 1 − 1/ e ) -regret bound of O ( n 1 3 k 2 3 T 2 3 log ( T ) 2 3 ) \mathcal{O}(n^{\frac{1}{3}} k^{\frac{2}{3}} T^{\frac{2}{3}} \log(T)^{\frac{2}{3}}) O ( n 3 1 k 3 2 T 3 2 log ( T ) 3 2 ) . Master-slave architecture tackles combinatorial multi-armed bandits with diversity constraints.
problem Solving top- K K K combinatorial multi-armed bandits with non-linear feedback and diversity constraints. method Master-slave architecture with six slave models, teacher learning, and policy co-training.
result Significantly outperforms existing algorithms in synthetic and real datasets.
Attention weights may not accurately highlight important parts due to combinatorial shortcuts.
problem Inaccurate interpretation of attention weights in models.
method Theoretical analysis and design of experiments to show combinatorial shortcuts. Proposed two methods to mitigate this issue.
result Proposed methods improve the interpretability of attention mechanisms.
We give a combinatorial model for r-spin surfaces with parametrised boundary based on Novak (2015). The r-spin structure is encoded in terms of Z r \mathbb{Z}_r Z r -valued indices assigned to the edges of a polygonal decomposition. This combinatorial model is designed for our state sum construction of two-dimensional topolog…
Algorithm improves movie recommendation efficiency with fairness constraints.
problem Improving movie recommendation efficiency with fairness constraints in combinatorial semi-bandits.
method Adopted Thompson Sampling with beta priors and Bernoulli likelihoods to handle fairness constraints.
result Time-averaged regret upper bounded by $\frac{N}{2η} + O\left(\frac{\sqrt{mNT\ln T}}{T}
ight)$ , with fairness constraints satisfied.
New algorithm reduces regret in combinatorial causal bandits without graph structure.
problem Minimizing regret in combinatorial causal bandits without graph structure.
method Design of algorithms for binary general causal models and BGLMs without graph skeleton.
result Achieves O ( T ln T ) O(\sqrt{T}\ln T) O ( T ln T ) expected regret for causal models and O ( T 2 3 ln T ) O(T^{\frac{2}{3}}\ln T) O ( T 3 2 ln T ) for BGLMs. Synthetic Combinations learns unit-specific causal outcomes for combinatorial interventions.
problem Estimating unit-specific causal outcomes for all combinations of p p p interventions in a heterogeneous setting. method Latent factor model with Fourier expansion sparsity, imposing structure across units and interventions.
result Synthetic Combinations provides consistent estimation with poly(r) * (N + s^2p) observations, outperforming previous methods.
New algorithm tackles non-stationary combinatorial semi-bandit problems with optimal regret bounds.
problem Non-stationary combinatorial semi-bandit problems in switching and dynamic environments.
method Developed algorithms for both switching and dynamic cases, achieving nearly optimal regret bounds.
result Achieved nearly optimal regret bounds in both switching and dynamic cases.
The paper tackles combinatorial pure exploration with various feedback structures and proposes efficient algorithms.
problem Identifying the optimal action in a combinatorial space with limited feedback and nonlinear rewards.
method Designs polynomial-time adaptive algorithms for CPE-BL and CPE-PL, providing sample complexity analyses.
result The proposed algorithms achieve sample complexity close to lower bounds and outperform existing methods.
Deep RL improves Diplomacy performance, outperforming previous methods.
problem Applying RL to complex, many-agent, simultaneous-move games like Diplomacy.
method Best response policy iteration and fictitious play approximation.
result Deep RL agents convincingly outperform previous Diplomacy agents.
Linear-time graph optimization using reinforcement learning.
problem Solving combinatorial optimization problems on real-world graphs.
method Graph neural network trained with reinforcement learning.
result Approximate solutions in linear time for various graph problems.
Combinatorial optimization problems are typically tackled by the branch-and-bound paradigm. We propose a new graph convolutional neural network model for learning branch-and-bound variable selection policies, which leverages the natural variable-constraint bipartite graph representation of mixed-integer linear programs…
We improve the efficiency of algorithms for stochastic \emph{combinatorial semi-bandits}. In most interesting problems, state-of-the-art algorithms take advantage of structural properties of rewards, such as \emph{independence}. However, while being optimal in terms of asymptotic regret, these algorithms are inefficien…
A new method reduces both input and output dimensions for better goal-oriented analysis.
problem Simultaneous reduction of input and output dimensions for more accurate analysis.
method Coupled input-output dimension reduction, optimizing gradient-based bounds.
result Determine most informative sensors and influential parameters efficiently.
Can we automatically design a Convolutional Network (ConvNet) with the highest image classification accuracy under the latency constraint of a mobile device? Neural Architecture Search (NAS) for ConvNet design is a challenging problem due to the combinatorially large design space and search time (at least 200 GPU-hours…
The problem of multi-armed bandits (MAB) asks to make sequential decisions while balancing between exploitation and exploration, and have been successfully applied to a wide range of practical scenarios. Various algorithms have been designed to achieve a high reward in a long term. However, its short-term performance m…