Cover Image

Theoretically Grounded Pruning of Large Ground Sets for Constrained, Discrete Optimization

Fuente: arXiv

Saved in:

Bibliographic Details
Main Authors:	Nath, Ankur, Kuhnle, Alan
Format:	Preprint
Published:	2024
Subjects:	Data Structures and Algorithms Machine Learning
Online Access:	Acceder al recurso
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

Submodular Ground-Set Pruning: Monotone Tightness and a Non-Monotone Separation
by: Kuhnle, Alan
Published: (2026)

Discretely Beyond $1/e$: Guided Combinatorial Algorithms for Submodular Maximization
by: Chen, Yixin, et al.
Published: (2024)

Best of Both Worlds: Practical and Theoretically Optimal Submodular Maximization in Parallel
by: Chen, Yixin, et al.
Published: (2021)

Curvature Beyond Positivity: Greedy Guarantees for Arbitrary Submodular Functions
by: Chen, Yixin, et al.
Published: (2026)

Practical and Parallelizable Algorithms for Non-Monotone Submodular Maximization with Size Constraint
by: Chen, Yixin, et al.
Published: (2020)

Scalable Distributed Algorithms for Size-Constrained Submodular Maximization in the MapReduce and Adaptive Complexity Models
by: Chen, Yixin, et al.
Published: (2022)

Breaking Barriers: Combinatorial Algorithms for Non-monotone Submodular Maximization with Sublinear Adaptivity and $1/e$ Approximation
by: Chen, Yixin, et al.
Published: (2025)

Bypassing the Noisy Parity Barrier: Learning Higher-Order Markov Random Fields from Dynamics
by: Gaitonde, Jason, et al.
Published: (2024)

The tractability landscape of diffusion alignment: regularization, rewards, and computational primitives
by: Moitra, Ankur, et al.
Published: (2026)

Better Models and Algorithms for Learning Ising Models from Dynamics
by: Gaitonde, Jason, et al.
Published: (2025)

Steering diffusion models with quadratic rewards: a fine-grained analysis
by: Moitra, Ankur, et al.
Published: (2026)

Overcomplete Tensor Decomposition via Koszul-Young Flattenings
by: Kothari, Pravesh K., et al.
Published: (2024)

$O(\sqrt{T})$ Static Regret and Instance Dependent Constraint Violation for Constrained Online Convex Optimization
by: Vaze, Rahul, et al.
Published: (2025)

Learning $\mathsf{AC}^0$ Under Graphical Models
by: Chandrasekaran, Gautam, et al.
Published: (2026)

Finite and Corruption-Robust Regret Bounds in Online Inverse Linear Optimization under M-Convex Action Sets
by: Oki, Taihei, et al.
Published: (2026)

Optimal Algorithms for Augmented Testing of Discrete Distributions
by: Aliakbarpour, Maryam, et al.
Published: (2024)

Guessing Efficiently for Constrained Subspace Approximation
by: Bhaskara, Aditya, et al.
Published: (2025)

Precedence-Constrained Decision Trees and Coverings
by: Szyfelbein, Michał, et al.
Published: (2026)

Decision-Theoretic Approaches for Improved Learning-Augmented Algorithms
by: Angelopoulos, Spyros, et al.
Published: (2025)

Deterministic Policies for Constrained Reinforcement Learning in Polynomial Time
by: McMahan, Jeremy
Published: (2024)

Learning-augmented Maximum Independent Set
by: Braverman, Vladimir, et al.
Published: (2024)

Learning-Augmented Ski Rental with Discrete Distributions: A Bayesian Approach
by: Kang, Bosun, et al.
Published: (2025)

Taming Imperfect Process Verifiers: A Sampling Perspective on Backtracking
by: Rohatgi, Dhruv, et al.
Published: (2025)

$k$NN Attention Demystified: A Theoretical Exploration for Scalable Transformers
by: Haris, Themistoklis
Published: (2024)

Model Stealing for Any Low-Rank Language Model
by: Liu, Allen, et al.
Published: (2024)

Gradient-Free Method for Heavily Constrained Nonconvex Optimization
by: Shi, Wanli, et al.
Published: (2024)

Optimal Bounds for Adversarial Constrained Online Convex Optimization
by: Ferreira, Ricardo N., et al.
Published: (2025)

Convex Optimization with Nested Evolving Feasible Sets
by: M., Karthick Krishna, et al.
Published: (2026)

Submodular Maximization in Exactly $n$ Queries
by: Balkanski, Eric, et al.
Published: (2024)

GIST: Greedy Independent Set Thresholding for Max-Min Diversification with Submodular Utility
by: Fahrbach, Matthew, et al.
Published: (2024)

No-Regret M${}^{\natural}$-Concave Function Maximization: Stochastic Bandit Algorithms and Hardness of Adversarial Full-Information Setting
by: Oki, Taihei, et al.
Published: (2024)

Accelerated Algorithms for Constrained Nonconvex-Nonconcave Min-Max Optimization and Comonotone Inclusion
by: Cai, Yang, et al.
Published: (2022)

Approximation Algorithms for Combinatorial Optimization with Predictions
by: Antoniadis, Antonios, et al.
Published: (2024)

Semi-Bandit Learning for Monotone Stochastic Optimization
by: Agarwal, Arpit, et al.
Published: (2023)

Replicable Learning of Large-Margin Halfspaces
by: Kalavasis, Alkis, et al.
Published: (2024)

Accelerating Matroid Optimization through Fast Imprecise Oracles
by: Eberle, Franziska, et al.
Published: (2024)

Lower Bounds for Greedy Teaching Set Constructions
by: Compton, Spencer, et al.
Published: (2025)

Structure learning of Hamiltonians from real-time evolution
by: Bakshi, Ainesh, et al.
Published: (2024)

Learning quantum Hamiltonians at any temperature in polynomial time
by: Bakshi, Ainesh, et al.
Published: (2023)

Optimization of Inter-group Criteria for Clustering with Minimum Size Constraints
by: Laber, Eduardo S., et al.
Published: (2024)