On Bounds for Greedy Schemes in String Optimization based on Greedy Curvatures

2024-04-10 · Bowen Li, Brandon Van Over, Edwin K. P. Chong, Ali Pezeshki

We consider the celebrated bound introduced by Conforti and Cornu\'ejols (1984) for greedy schemes in submodular optimization. The bound assumes a submodular function defined on a collection of sets forming a matroid and is based on greedy curvature. We show that the bound holds for a very general class of string problems that includes maximizing submodular functions over set matroids as a special case. We also derive a bound that is computable in the sense that they depend only on quantities along the greedy trajectory. We prove that our bound is superior to the greedy curvature bound of Conforti and Cornu\'ejols. In addition, our bound holds under a condition that is weaker than submodularity.

📄 PDF Abstract BibTeX arXiv:2404.06669

Code (0)

등록된 구현이 없습니다.

Methods 이 논문이 사용한 방법론

SET Dynamic Sparse Training method where weight mask is updated randomly periodically

A Performance Bound for the Greedy Algorithm in a Generalized Class of String Optimization Problems

2024-09-08 · Brandon Van Over, Bowen Li, Edwin K. P. Chong, Ali Pezeshki

We present a simple performance bound for the greedy scheme in string optimization problems that obtains strong results. Our approach vastly generalizes the group of previously established greedy curvature bounds by Conf…

Greedy Sampling of Graph Signals

2017-04-05 · Luiz. F. O. Chamon, Alejandro Ribeiro

Sampling is a fundamental topic in graph signal processing, having found applications in estimation, clustering, and video compression. In contrast to traditional signal processing, the irregularity of the signal domain …

Clustering Video Compression

On Approximation Guarantees for Greedy Low Rank Optimization

2017-03-08 · ICML 2017 8 · Rajiv Khanna, Ethan Elenberg, Alexandros G. Dimakis, Sahand Negahban

We provide new approximation guarantees for greedy low rank matrix estimation under standard assumptions of restricted strong convexity and smoothness. Our novel analysis also uncovers previously unknown connections betw…

Combinatorial Optimization

Finite-Time Error Bounds for Greedy-GQ

2022-09-06 · Yue Wang, Yi Zhou, Shaofeng Zou

Greedy-GQ with linear function approximation, originally proposed in \cite{maei2010toward}, is a value-based off-policy algorithm for optimal control in reinforcement learning, and it has a non-linear two timescale struc…

reinforcement-learning Reinforcement Learning Reinforcement Learning (RL)

Forward-Backward Greedy Algorithms for General Convex Smooth Functions over A Cardinality Constraint

2013-12-31 · Ji Liu, Ryohei Fujimaki, Jieping Ye

We consider forward-backward greedy algorithms for solving sparse feature selection problems with general convex smooth functions. A state-of-the-art greedy method, the Forward-Backward greedy algorithm (FoBa-obj) requir…

Activity Recognition feature selection