16 citations · 66 across the 23 of their papers we have counts for
26 papers
Stronger Hardness for Submodular Maximization Subject to a Matroid Constraint
Moran Feldman, Alan Kuhnle
Maximizing a submodular function subject to a matroid constraint is a cornerstone problem in combinatorial optimization. The state-of-the-art algorithm for this problem obtains $0.…
How Inefficient Is Natural Gradient Descent? From Exact Optimality to Θ( \sqrt{ \log d } ) Divergence
Guni Sharon, Alan Kuhnle
Natural gradient descent (NGD) underlies common methods in ML. For dually flat families, idealized NGD on the forward Kullback--Leibler objective follows the mixture geodesic which…
Submodular Maximization in Exactly Queries
Eric Balkanski, Steven DiSilvio, Alan Kuhnle +1
In this work, we study the classical problem of maximizing a submodular function subject to a matroid constraint. We develop deterministic algorithms that are very parsimonious wit…
Discretely Beyond : Guided Combinatorial Algorithms for Submodular Maximization
Yixin Chen, Ankur Nath, Chunli Peng +1
For constrained, not necessarily monotone submodular maximization, all known approximation algorithms with ratio greater than require continuous ideas, such as queries to the…
Unveiling the Limits of Learned Local Search Heuristics: Are You the Mightiest of the Meek?
Ankur Nath, Alan Kuhnle
In recent years, combining neural networks with local search heuristics has become popular in the field of combinatorial optimization. Despite its considerable computational demand…
RELS-DQN: A Robust and Efficient Local Search Framework for Combinatorial Optimization
Yuanhang Shao, Tonmoy Dey, Nikola Vuckovic +2
Combinatorial optimization (CO) aims to efficiently find the best solution to NP-hard problems ranging from statistical physics to social media marketing. A wide range of CO applic…