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.
Study identifies key differences in convex relaxations for combinatorial penalties.
problem Understanding which structures are preserved by convex relaxations for combinatorial penalties.
method Examined homogeneous and non-homogeneous convex relaxations, introduced lower combinatorial envelope, and proposed adaptive estimator.
result Identified new necessary and sufficient conditions for support recovery in convex monotone regularizers.
Paper improves estimates for discrete Laplace in hyperbolic geometry.
problem Establishing compactness for discrete Laplace in hyperbolic geometry.
method Explicit estimates for discrete Laplace based on Glickenstein-Thomas formulation.
result New proofs of long time existence for Calabi flows in hyperbolic geometry.
Greedy method improves low rank matrix estimation with new approximation guarantees.
problem Low rank matrix estimation under restricted strong convexity and smoothness.
method Novel greedy algorithm analysis linking to combinatorial optimization.
result Improved approximation guarantees and statistical recovery.
New algorithm finds high-reward combinatorial sets with fewest pulls.
problem Finding high-reward combinatorial sets with unknown individual arm rewards.
method Successive acceptance and elimination based on combinatorial structure.
result Algorithm requires minimal combinatorial oracle calls, making it practical for large problems.
New methods for testing graph structures, from connectivity to cycles.
problem Testing the global structure of graphical models.
method Unified theory and novel algorithms for combinatorial inference.
result Unified theory and practical algorithms match fundamental limits.
New method for off-policy evaluation in contextual bandits reduces bias-variance tradeoff.
problem Improving off-policy evaluation in contextual bandits.
method Asymptotically optimal doubly robust estimator with shrinkage of importance weights.
result New estimators outperform state-of-the-art methods in experiments.
In this paper we provide a framework for the study of isoperimetric problems in finitely generated group, through a combinatorial study of universal covers of compact simplicial complexes. We show that, when estimating filling functions, one can restrict to simplicial spheres of particular shapes, called "round" and "u…
A new algorithm for top-k combinatorial bandits with full-bandit feedback.
problem Optimizing decisions among subsets of arms with only aggregate rewards observed.
method CSAR algorithm using Hadamard matrices for estimating individual arm rewards.
result Proved a tight lower bound on sample complexity for k = O ( 1 ) k=O(1) k = O ( 1 ) . 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.
Algorithm BGLM-OFU minimizes regret in combinatorial causal bandits with binary models.
problem Minimizing expected regret in combinatorial causal bandits with binary generalized linear models.
method BGLM-OFU algorithm based on maximum likelihood estimation for Markovian BGLMs, and causal inference techniques for linear models with hidden variables.
result Achieves O ( T log T ) O(\sqrt{T}\log T) O ( T log T ) regret for binary generalized linear models. New method improves solving combinatorial optimization problems with smoothed policies.
problem Solving combinatorial optimization problems repeatedly with varying instances.
method Smoothed policies with controlled random perturbations to linear oracle, leading to differentiable surrogate risk.
result Generalization bound decomposes excess risk into bias, estimation, and optimization components.
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.
This paper presents novel algorithms which exploit the intrinsic algebraic and combinatorial structure of the matrix completion task for estimating missing en- tries in the general low rank setting. For positive data, we achieve results out- performing the state of the art nuclear norm, both in accuracy and computation…
BPNNs learn to solve combinatorial problems faster and more accurately.
problem Generalizing belief propagation for efficient problem solving.
method BPNNs are parameterized operators that operate on factor graphs, generalizing BP. BPNN-D is a learned iterative operator that provably maintains BP's properties.
result BPNN-D converges 1.7x faster on Ising models and provides tighter bounds.
Transformer model estimates keywords for better audio captioning.
problem Indeterminacy in word selection for audio events/scenes.
method Transformer-based model with keyword estimation.
result Achieved state-of-the-art performance in AAC.
In graph theory there are intimate connections between the expansion properties of a graph and the spectrum of its Laplacian. In this paper we define a notion of combinatorial expansion for simplicial complexes of general dimension, and prove that similar connections exist between the combinatorial expansion of a compl…
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.
Deep unfolding accelerates MCMC-based COP solvers.
problem Optimizing combinatorial problems with MCMC and gradient descent.
method Combines MCMC and gradient descent, trains step sizes, uses variance estimation for non-differentiable MCMC.
result Significantly accelerates convergence speed for COPs.
A method learns to solve multilevel combinatorial problems with two players.
problem Multilevel combinatorial optimization problems with multiple players.
method Value-based multi-agent reinforcement learning in a graph neural network framework.
result Close to optimal solutions on graphs up to 100 nodes, with a significant speedup.
Paper evaluates policies for ordered item recommendations using logged data.
problem Evaluating policies that recommend ordered sets of items based on context.
method Combining techniques from combinatorial bandits, introduces a new estimator using logged data.
result The estimator is accurate in various settings, including as a subroutine in learning-to-rank tasks.
We propose an algebraic combinatorial method for solving large sparse linear systems of equations locally - that is, a method which can compute single evaluations of the signal without computing the whole signal. The method scales only in the sparsity of the system and not in its size, and allows to provide error estim…
Metaheuristics improve yield curve estimation for Costa Rica.
problem Estimating the yield curve for Costa Rica using historical data.
method Used Nelson-Siegel and Svensson models with four metaheuristics (Ant colony, Genetic, Particle Swarm, Simulated Annealing) for optimization.
result Metaheuristics achieved better results than classical methods, especially Particle Swarm and Simulated Annealing.
Optimizes link prediction using matrix logistic regression.
problem Predicting links in networks with limited data.
method Formulated as matrix logistic regression, analyzed in high dimensions, combinatorial estimator with penalized maximum likelihood.
result Achieves minimax rate for Frobenius-norm risk, cannot be computed efficiently.
QAOA matches classical tensor power iteration in spiked tensor model recovery.
problem Statistical estimation in spiked tensor model with computational gap.
method Analysis of QAOA performance on spiked tensor model.
result QAOA weak recovery threshold matches tensor power iteration.
Sharp upper bound for vertices with positive curvature in planar graphs.
problem Finding the maximum number of vertices with positive curvature in planar graphs.
method Sharp upper bound calculation based on combinatorial curvature.
result Automorphism group is finite and provides an upper bound for its order.
We present a novel algebraic combinatorial view on low-rank matrix completion based on studying relations between a few entries with tools from algebraic geometry and matroid theory. The intrinsic locality of the approach allows for the treatment of single entries in a closed theoretical and practical framework. More s…
New method uses hyperbolic space for faster phylogenetic tree inference.
problem Inefficient Euclidean-based phylogenetic inference in high dimensions.
method Developed novel hyperbolic extensions of sequential search algorithms and variational inference methods.
result Improved speed, scalability and performance in phylogenetic inference.
RNNs learn combinatorial graph problems with sample complexity bounds.
problem Learning efficient approximations for real-valued combinatorial graph problems.
method Upper bounds the sample complexity for learning real-valued RNNs.
result Real-valued RNNs can be learned with polynomial number of samples.
Novel theory combines combinatorial and topological elements.
problem Understanding combinatorial phenomena at the intersection of topology.
method Synthesizes combinatorial and topological approaches with a new framing concept.
result Framed combinatorial spaces exhibit better behavior than classical spaces.
The paper introduces combinatorial Calabi flows to find hyperbolic metrics on surfaces with boundary.
problem Finding hyperbolic metrics on surfaces with totally geodesic boundaries of given lengths.
method Introducing combinatorial Calabi flows and proving their long time existence and global convergence.
result Proves the long time existence and global convergence of combinatorial Calabi flow on surfaces with boundary.
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.
The paper compares Steklov and Laplacian eigenvalues on graphs.
problem Understanding the relationship between Steklov and Laplacian eigenvalues on graphs.
method Analyzing eigenvalues and discussing rigidity.
result Obtained Lichnerowicz-type estimates and combinatorial estimates for Steklov eigenvalues.
Improved UCB and Thompson Sampling policies for CMAB with probabilistically triggered arms achieve bounded regret.
problem Combinatorial multi-armed bandit problem with probabilistically triggered arms.
method Upper Confidence Bound (UCB) policies and Combinatorial Thompson Sampling (CTS).
result CUCB- κ κ κ and CTS achieve O ( T ) O(\sqrt{T}) O ( T ) gap-independent regret. The paper develops algorithms for finding metrics with prescribed combinatorial curvature on polyhedral surfaces.
problem Finding metrics with prescribed combinatorial curvature on polyhedral surfaces.
method Discrete uniformization theorem, combinatorial α-Yamabe flow, combinatorial α-Calabi flow, edge flipping surgery.
result Longtime existence and convergence of combinatorial α-Yamabe flow and combinatorial α-Calabi flow with surgery.
Paper proposes machine learning to optimize QAOA for combinatorial problems.
problem Optimizing QAOA parameters for solving combinatorial optimization problems.
method Develops two machine learning approaches: RL and KDE to learn optimal QAOA parameters.
result Reduces optimality gap by up to 30.15 compared to other optimizers.
New algorithm reduces super-arm selection complexity exponentially.
problem Combinatorial multi-armed bandits with cardinality constraint.
method Combination of group-testing and quantized Thompson sampling.
result Achieves same regret order as state-of-the-art algorithms with perfect oracle, but with reduced complexity.
The paper introduces combinatorial curvature and flow for polyhedral surfaces, proving rigidity and solving the Yamabe problem.
problem Discrete conformal structures on polyhedral surfaces and their rigidity.
method Parameterized combinatorial curvature, combinatorial α-Ricci flow, and flow extension through singularities.
result Existence and convergence of combinatorial α-Ricci flow for solving the Yamabe problem.
Improves scalability of Bayesian optimization for combinatorial spaces.
problem Optimizing expensive functions over large combinatorial spaces.
method Parametrized Submodular Relaxation (PSR) to solve AFO problems for BOCS.
result Significant improvements in scalability and accuracy for BOCS model.
We call a Delta Diagram any diagram of a knot or link whose regions (including the unbounded one) have 3, 4, or 5 sides. We prove that any knot or link admits a delta diagram. We define and estimate combinatorial link invariants stemming from this definition.
New framework for discrete-state diffusion models reduces sample complexity.
problem Lack of theoretical understanding and sample complexity analysis for discrete-state diffusion models.
method Developed a principled theoretical framework, decomposing score estimation error.
result Established sample complexity bound of O ~ ( ε − 2 ) \widetilde{\mathcal{O}}(ε^{-2}) O ( ε − 2 ) . For triangulated surfaces, we introduce the combinatorial Calabi flow which is an analogue of smooth Calabi flow. We prove that the solution of combinatorial Calabi flow exists for all time. Moreover, the solution converges if and only if Thurston's circle packing exists. As a consequence, combinatorial Calabi flow pro…
A new method for learning DAG structure without combinatorial constraints.
problem Estimating the structure of directed acyclic graphs (DAGs).
method Formulate structure learning as a continuous optimization problem over real matrices.
result The method outperforms existing approaches without structural assumptions.
Fractional combinatorial flow improves surface conformal structures.
problem Improving discrete conformal structures on surfaces.
method Introducing a fractional combinatorial Calabi flow for discrete conformal structures on surfaces.
result Longtime existence and global convergence of the fractional combinatorial Calabi flow for various surface types.
Combinatorial method computes Legendrian knot invariant.
problem Computing the Heegaard Floer contact invariant for Legendrian knots.
method Combining Plamenevskaya's combinatorial description with Heegaard Floer theory.
result Hat version of LOSS invariant can be computed combinatorially.
Polynomial-time method solves complex combinatorial semi-bandits.
problem Optimal strategies for combinatorial semi-bandits with uncorrelated Gaussian rewards.
method Proposes a polynomial-time method to solve the Graves-Lai optimization problem for various combinatorial structures.
result First known approach to implement asymptotically optimal algorithms in polynomial time for combinatorial semi-bandits.
New method finds metrics on surfaces with prescribed curvatures using circle packings and surgery.
problem Finding piecewise Euclidean metrics on surfaces with prescribed combinatorial curvatures.
method Combinatorial curvature flows with surgery for inversive distance circle packings.
result Longtime existence and global convergence of combinatorial curvature flows with surgery.
New combinatorial structure for hierarchically hyperbolic spaces.
problem Constructing new hierarchically hyperbolic spaces.
method Combinatorial hierarchical hyperbolicity criterion to construct and clarify HHS structures.
result HHSs admit a combinatorial structure, clarifying the application of the combinatorial HHS criterion.