Greedy Algorithm

Follow this topic Ask about this topic

Momentum

0 papers in the last four weeks, against 1 the four weeks before. 0.0% of all new papers.

Jul 6Week of Sep 21

Latest papers 16

Sep 30, 2026cs.RO

CLIPPER Beyond Shortlisting: Auditable Decision Support for Changing Municipal Micromobility Policies

In municipal planning workshops, planners and other stakeholders compare shared-micromobility parking policies by varying no-parking zones, retained sites, spacing, or area allocations. Each edit changes feasible sites and how much demand they cover, so the alternative must be reoptimized on the same spatial data. Full-set greedy, the transparent reference for this task, takes tens of seconds per alternative at city scale. We present Constraint-exact Low-latency Iterative Planning with Pooled Evaluation and Replay (CLIPPER), an optimizer with audit functions developed for requirements elicited with the City of Braunschweig. In each greedy round, it forms a deterministic candidate pool of bounded size, computes how much still-uncovered demand each candidate would add, and rejects candidates that violate an active constraint. An optional offline audit scans every remaining feasible candidate and records what the restricted pool omitted. We evaluate these functions on complete eleven-state edit chains (

E_0,\ldots,E_{10}

) in Braunschweig, Munich, and Berlin. With

K=1024

candidates per group, the fixed-width mode CLIPPER-F has mean coverage gaps to full-set greedy under the same policy of 0.245, 0.003, and 0.001 percentage points in Braunschweig, Munich, and Berlin, respectively, while mean rollout time falls by factors of 13.6--28.9; no audited run terminates while a candidate outside the pool could still increase coverage. Plans computed from two checksummed versions of Braunschweig's official no-parking-zone data differ in 30 of about 540 selected sites although coverage moves by only about 0.1 percentage points. These changes still require municipal assessment and implementation. The findings inform a proposed municipal process that versions policy inputs, reports site changes beside coverage, and scans the full candidate set before a final decision.

Julian Teusch, Jörg Philipp Müller, Monika Sester

Institute of Computer Science Clausthal University of Technology Clausthal-Zellerfeld, Germany · Institute of Cartography and Geoinformatics Leibniz University Hannover Hannover, Germany

Urban Mobility Long-Run Coverage Guarantees Shortest Paths Greedy Algorithm Software Engineering Decision Support

Aug 4, 2026cs.LG

Approximate Speculative Decoding

Speculative decoding accelerates autoregressive generation by verifying a draft block with a target model in parallel. Under standard greedy verification, decoding stops at the first draft token that differs from the target argmax, discarding the remaining target-scored suffix. Although accepting such a mismatch changes the decoding trajectory, it can make a contiguous suffix reusable when its tokens remain target-greedy under the realized prefix. In this paper, we introduce \textbf{Approximate Speculative Decoding (ASD)}, a training-free verifier that replaces binary first-mismatch truncation with budgeted longest-prefix selection. ASD accepts selected mismatches subject to a local target-logit regret gate, a per-block exception cap, and a persistent request-level regret budget, then reuses the contiguous target-greedy suffix without additional approximate decisions or target-model forward passes. ASD requires neither a new draft model nor fine-tuning, and exactly reduces to standard greedy verification when the budget is zero. Experiments show that ASD improves fixed-workload throughput by

3.05\%

--

15.26\%

over matched strict verification and averages a

7.78\%

gain across seven Qwen3-14B + DSpark-14B tasks. On DeepSeek-V4-Flash (284B) with DSpark it also raises verifier-side acceptance by roughly

10\%

--

16\%

on GSM8K and MATH-500 in an FP4-to-FP8 compatibility setting. The source code is publicly available at: https://github.com/Kissmetothemoon/ASD

Yuannuo Feng, Zegang Peng, Yuxin Xie +5

School of Integrated Circuit Science and Engineering, Beihang University, Beijing, China · Department of Precision Instrument, Tsinghua University, Beijing, China · Faculty of Engineering, The University of Hong Kong, Hong Kong SAR, China +2

Speculative Decoding Truncation Deepseek Greedy Algorithm

Aug 2, 2026cs.CV

Think in Sets for Streaming Video Token Compression

Streaming VideoLLMs process frames causally while visual tokens grow continuously, making compression essential for controlling prefilling latency and memory. Existing training-free methods independently rank tokens, ignoring marginal-gain interactions among retained tokens. We argue that streaming video token compression should instead be formulated as set selection, where each candidate is valued by what it adds beyond the tokens already retained. Unlike existing set-wise methods designed for offline tasks, streaming makes causal, frame-by-frame pruning decisions, so modeling cross-frame interactions requires an explicit historical reference. This creates a reference-set dilemma: the reference must adequately represent previously conveyed content while remaining bounded for real-time inference. We introduce NovaCov, to our knowledge the first training-free, plug-and-play set-wise token compressor designed for streaming video. NovaCov maintains a capacity-bounded, recency-weighted Historical Reference Bank and optimizes a dual-branch submodular coverage objective that preserves representative current-frame content while prioritizing information insufficiently covered by history. Both branches are facility-location functions, so greedy selection retains the classical (1-1/e) approximation guarantee. Across streaming and offline benchmarks, NovaCov outperforms existing training-free compression methods, retaining 99.6% of ReKV accuracy while reducing LLM prefilling latency by 46%.

Moxu Duan, Jingwen Fu, Yuwang Wang

Beijing Jiaotong University · Zhongguancun Academy · Tsinghua University

Token Compression Task-Aware Compression Data Compression Methods Streaming Greedy Algorithm

Jul 31, 2026stat.ML

The Greedy Advantage in Finite-Horizon Bandits

Organizations increasingly rely on sequential experimentation to improve decision-making. While the multi-armed bandit literature has developed algorithms with strong asymptotic regret guarantees, many practical applications operate over finite and externally imposed horizons. Motivated by the finite-horizon setting, we develop a class of regularized greedy algorithms for multi-armed Bernoulli bandits. We derive the first finite-horizon regret envelopes for regularized greedy bandits, showing that finite-horizon regret decomposes into transient exploration costs and a suboptimal convergence term that decays exponentially with the regularization strength. This characterization yields principled calibration rules for the regularization parameters and, as a limiting case, sharper regret guarantees for the classical greedy policy. Across extensive numerical experiments, calibrated regularized greedy policies consistently match or outperform state-of-the-art algorithms. These results suggest that regularized greedy policies can provide an effective approach for finite-horizon bandit problems.

Kai Zhou, Michael Lingzhi Li, Kai Wang

Tsinghua University · Harvard Business School

Stochastic Multi-Armed Bandits Interval Regret Bandits Entropy Regularized Reinforcement Learning Greedy Algorithm Optimal Policies

Jul 27, 2026cs.LG

Why does Greedy Search produce Optimal Clustering Outcomes? A Fixed-Core Assignment Theory

Many existing clustering methods are designed based on a set-oriented definition---a cluster is a set of similar points---relying a point-to-point similarity function to find similar points. This works well for compact clusters, but clustering performance can deteriorate badly when cluster shapes are irregular, and densities or sizes vary between clusters. Recent `Cluster-as-Distribution' (CaD) clustering has been shown to discover these generic types of clusters in practice by treating each cluster as a set of independent and identically distributed points generated from some unknown distribution via a greedy search, achieving a clustering objective equivalent to that of Spectral Clustering, but with better clustering outcomes without eigen-decomposition. However, a theoretical analysis of this phenomenon is still lacking. Our analyses are from two angles. First, we analyze the approximation error between the true and empirical distribution embeddings. Second, we show that the greedy search employed to achieve the CaD clustering objective can be mapped to a partition matroid---yielding greedy optimality. These yield a near-optimality guarantee for the CaD clustering objective, with regret controlled by the approximation error. This is the first analysis that explains why CaD clustering via greedy search can discover clusters of arbitrary shapes, densities and sizes (where all set-oriented clustering methods have failed to discover) when the estimated cluster embeddings faithfully approximate the underlying cluster distributions.

Kaifeng Zhang, Kai Ming Ting, Sanjay Chawla

School of Artificial Intelligence Nanjing University, China · Qatar Computing Research Institute, HBKU

Clustering Greedy Algorithm Distributions Credit Assignment

Jul 27, 2026cs.LG

Greedy dynamical meta-learning

Gradient descent scales well to large models, but becomes unstable over long time horizons. Gradient-free optimizers can scale to arbitrary timespans, but are hobbled by high dimensions. Since learning occurs in large models over long timescales, neither of these approaches is likely to produce traits which can accelerate the learning process. Instead, we propose a meta-learning algorithm in which the agent learns to modify its own weights and biases. Our algorithm consists of an inner loop, wherein the agent performs some high-dimensional optimization upon itself, and an outer loop, wherein we perform some low-dimensional optimization upon the inner loop. Since the outer loop handles very few parameters, standard zeroth-order methods may be used.

Aria Yom

Rhodora

Meta-Learning Gradient-Based Optimization Gradient Descent Timescale Greedy Algorithm

Jul 15, 2026eess.AS

Greedy Volume Maximization of Gradient Embeddings for Long-Tailed Frame-Level Bioacoustic Active Learning

Bioacoustic call-type classification relies on costly expert annotation. Active learning can reduce this burden by selecting a small batch of segments for expert annotation and using the labeled segments for training the classifier. The setting is hard: the target calls are extremely sparse and the call-type distribution is long-tailed, so a tight budget must be spent on the few rare, informative segments. We propose BADGE-Greedy-DPP, a deterministic batch selector that greedily adds the segment whose BADGE gradient embedding most enlarges the volume spanned by the batch; because this log-volume objective is submodular, the greedy rule guarantees a batch value at least a (1-1/e) fraction of the optimum of this objective, a guarantee not provided by BADGE's existing k-means++ and MCMC DPP sampling heuristics. There is also a temporal granularity mismatch in the task. The acquisition function scores whole segments, yet the informative frames inside them are few. Uniform averaging therefore washes them out. We show that the BADGE construction naturally addresses this mismatch when applied frame-wise, as prediction residuals weight the aggregated pseudo-gradient, so confidently predicted no-call frames contribute little while a single uncertain rare-call frame can still set the segment's direction. Across 10 runs on a sparse, imbalanced hyena call-type dataset, BADGE-Greedy-DPP achieves the best overall and rare-call-type performance among all compared query strategies, including MFFT, the strongest non-BADGE baseline, and the two vanilla BADGE traversals.

Shiqi Zhang, Marius Faiß, Ariana Strandburg-Peshkin +1

1Audio Research Group, Tampere University, Tampere, Finland · Department for the Ecology of Animal Societies, Max Planck Institute of Animal Behavior · 3International Max Planck Research School for Quantitative Behavior, Ecology and Evolution +1

Passive Acoustic Monitoring Active Learning Label Propagation Df-Wild Dataset Greedy Algorithm Text Embeddings

Jul 7, 2026cs.LG

The Approximation Ratio for the Risk of Myopic Bayesian Active Learning for Linear Regression

Active learning studies the fundamental question: what data should we choose to observe? The greedy algorithm in optimal experiment design is a common heuristic and also equivalent to myopic Bayesian active learning for linear regression, the common framework where long-term planning is replaced with the one-step optimal choice. In this work, we prove a first-of-its-kind approximation ratio for the greedy algorithm's risk that is tight up to an absolute constant. The approximation ratio is linear in the maximum initial leverage score (MILS), a newly identified quantity fundamental to the greedy algorithm's performance. Finally, we illustrate the results with simple numerical simulations.

Stephen Mussmann

School of Computer Science Georgia Institute of Technology

Pool-Based Active Learning Active Learning Greedy Algorithm Bayesian Experimental Design Approximation Algorithms Risk

Jun 16, 2026cs.CL

The Benchmark Illusion: Pruned LLMs Can Pass Multiple Choice but Fail to Answer

Compressing large language models reduces memory use and inference cost, but it can also create failures that standard benchmarks miss. A pruned model may still perform well on multiple-choice evaluations, yet fail to answer the same question in open generation. We ask what pruning changes: does it erase the correct answer, or does it make the answer harder to produce as the top output? We study this question with multilingual question answering, tracking the same questions before and after pruning. We find a benchmark illusion. Under high-sparsity pruning, especially Wanda, models often fail in greedy open generation while still selecting the correct answer under multiple-choice scoring. In these recognition-only errors, the answer is usually not gone, but demoted: it often reappears with beam search, sampling, or one in-context example. Overall, multiple-choice benchmarks can overstate the usability of compressed LLMs, creating an evaluation blind spot. Compressed models should be tested on what they can produce, not only on what they can recognize.

Rui Wen, Lu Sun, Jiayang Liu +3

Institute of Science Tokyo · Tohoku University · Nanyang Technological University +2

Multiple-Choice Questions Greedy Algorithm

Jun 8, 2026cs.LG

Importance-Aware Scheduling for High-Dimensional Hyperparameter Optimization

Hyperparameter Optimization (HPO) is essential for building high-performing ML/DL models, yet conventional optimizers often struggle in high-dimensional spaces where evaluations are costly and progress is diluted across many low-impact variables. We propose Greedy Importance First (GIF), an importance-aware scheduling strategy that uses a small-sample warm start to estimate hyperparameter importance, forms importance-based groups, allocates trials proportionally, and retains a full-space fallback. We evaluate GIF under fixed evaluation budgets on five anisotropic analytic functions, Bayesmark, and NAS-Bench-301. On the higher-dimensional benchmarks, GIF reaches better incumbents with faster convergence than TPE, BOHB, Random Search, and Sequential Grouping. On Bayesmark, where the effective dimensionality is smaller, GIF remains competitive but the margins are smaller. Ablation studies show that importance estimation, proportional allocation, and the fallback step all contribute to the gains. We also verify that the HIA component recovers the intended anisotropy on the analytic benchmarks. These results suggest that GIF is a simple and plug-compatible way to improve sample efficiency in high-dimensional HPO.

Ruinan Wang, Ian Nabney, Mohammad Golbabaee

University of Bristol, Bristol, United Kingdom

General Grid Search Framework High-Dimensional Importance Schedulers Greedy Algorithm

May 15, 2026cs.LG

Parameter Efficient Multi-Class Intelligent Scheduling for Multimodal Online Distributed Industrial Anomaly Detection

Industrial anomaly detection has attracted significant attention as a fundamental challenge in industrial systems. The rapid advancement of heterogeneous industrial sensors has driven industrial anomaly detection from unimodal to multimodal paradigms. However, existing methods are primarily designed for centralized and offline settings, overlooking the distributed and continuously generated data characteristic of real-world industrial environments. With the advancement of edge intelligence, modern edge devices are increasingly capable of not only data acquisition but also distributed model training, enabling collaborative intelligence across the system. Industrial anomaly detection represents a critical application in this context. Motivated by these challenges, we propose a novel framework termed Multimodal Online Distributed Industrial Anomaly Detection (MODIAD). We first present a comprehensive workflow for MODIAD and then formulate a Multi-class Intelligent Scheduling (MIS) problem to coordinate cross class model updates by balancing data sufficiency and class update frequency. To efficiently solve this problem, we design a Sequential Marginal Gain Greedy (SMG) algorithm that enables effective multi-class training under resource constraints. Furthermore, to improve the computational and communication efficiency during training, we propose an Resource Efficient Class-Wise Low Rank Adaptation (REC-LoRA) strategy, which significantly reduces system overhead while preserving detection performance. Extensive experiments on two representative multimodal industrial anomaly detection datasets, MVTec 3D-AD and Eyecandies demonstrate that the proposed approach achieves superior performance and efficiency under the MODIAD scenario.

Heqiang Wang, Weihong Yang, Zheyuan Yang +4

Pengcheng Laboratory, Shenzhen, 518066, China · Shenzhen International Graduate School, Tsinghua University, Shenzhen, 518055, China

Multimodal Industrial Anomaly Detection Schedulers Multi-Modal Data Heterogeneous Modeling Tools Domain Adaptation Greedy Algorithm+1

May 14, 2026cs.CL

Greedy or not, here I come: Language production under vocabulary constraints in humans and resource-rational models

Communicating using only a limited vocabulary is a common but challenging cognitive phenomenon, requiring an ideal communicator to plan carefully to optimize for intelligibility while circumventing a constrained lexicon. In this work, we investigate how humans respond to a broad array of questions under variable vocabulary limitations, consisting of only 250 highly frequent words at the most restrictive. We provide theoretically motivated comparisons to greedy and globally optimal sampling algorithms using Sequential Monte Carlo inference with large language models. Humans generally resemble greedy sampling more than globally optimal sampling, though more skilled humans are more likely to backtrack and revise -- a non-greedy behavior. An observed human pattern of leaning on semantically light words in high-constraint settings falls out of both greedy and globally optimal sampling. We discuss the results and their broader implications for resource-rational cognition, psycholinguistics, L2 communication, and language impairments.

Thomas Hikaru Clark, Sihan Chen, Laura Nicolae

Department of Brain and Cognitive Sciences, MIT · Department of Economics, Harvard University

Linguistics Greedy Algorithm Textual Priors Limited Data Rationality

May 8, 2026cs.LG

Curvature Beyond Positivity: Greedy Guarantees for Arbitrary Submodular Functions

Submodular functions -- functions exhibiting diminishing returns -- are central to machine learning. When the objective is monotone and non-negative, the greedy algorithm achieves a tight

63\%

approximation. But many practical objectives incorporate costs that make them negative on some inputs, and all existing multiplicative guarantees require non-negativity. Prior work handles negativity through additive bounds for the special class of decomposable functions and non-monotonicity through partial-monotonicity parameters, but these address each difficulty in isolation and neither extends the classical structural theory. We extend \emph{curvature} -- a parameter measuring how far a function deviates from linearity -- to all submodular functions, handling both non-monotonicity and negativity through a single classical concept. A greedy algorithm with pruning achieves a curvature-controlled multiplicative ratio for \emph{any} submodular function, including those taking negative values -- the first such guarantee beyond monotonicity and non-negativity. In the non-monotone regime

1 \le c_g < 2.2

, the bound strictly beats the best known uniform ratio of

0.401

(for non-negative

f

), and it recovers the classical

(1-e^{-c_g})/c_g

guarantee for monotone functions. A multilinear-extension variant extends the framework to general combinatorial constraints via multilinear relaxation. Experiments on cost-penalized experimental design, coverage, feature selection, and a curvature sweep on Multi-News passage selection support the theory.

Yixin Chen, Alan Kuhnle

Department of Computer Science & Engineering, Texas A&M University

Submodular Functions Local Curvature Greedy Algorithm Monotonicity Bayesian Experimental Design

May 3, 2026cs.LG

Multi-User Dueling Bandits: A Fair Approach using Nash Social Welfare

Learning from human preference data is becoming a useful tool, from fine-tuning large language models to training reinforcement learning agents. However, in most scenarios, the model is trained on the average preference of all human evaluators, which, under large variations of preferences, can be unfair to minority groups. In this work, we consider fairness in dueling bandits, a standard framework for online learning from preference data. We assume that each user has a (potentially distinct) Condorcet winner, which is an arm preferred to every other arm. Using these user-specific Condorcet winners as reference points, we evaluate and score arms according to their performance relative to the corresponding winner. To promote fairness across heterogeneous users, we adopt the well-established Nash Social Welfare objective, which maximizes the product of user utilities, thereby inherently penalizing inequality and preventing the marginalization of any single user. Within this framework, we construct a hard instance to establish a regret lower bound of

Ω(T^{2/3}\min(K,D)^\frac{1}{3})

for a time horizon

T

,

K

arms, and

D

users, which, to the best of our knowledge, is the first result quantifying the cost of fairness in dueling bandits with heterogeneous preferences. We then present the Fair-Explore-Then-Commit and Fair-

ε

-Greedy algorithms with a Condorcet winner identification phase. We further derive their regret upper bounds that match the lower-bound dependence on

T

up to logarithmic factors.

Maheed H. Ahmed, Mahsa Ghasemi

Electrical and Computer Engineering Purdue University

Algorithmic Fairness Stochastic Multi-Armed Bandits Bandits Preference Alignment Learning Greedy Algorithm

Jan 2, 2026cs.LG

Precision autotuning for linear solvers via contextual bandit-based RL

We propose a reinforcement learning (RL) framework for \xy{responsive} precision tuning for linear solvers, which can be extended to general algorithms. The framework is formulated as a contextual bandit problem and solved using incremental action-value estimation with a discretized state space to select optimal precision configurations for computational steps, \xy{retaining} precision and computational efficiency. To verify its effectiveness, we apply the framework to iterative refinement for solving linear systems

Ax = b

. In this application, our approach dynamically chooses precisions based on calculated features from the system while maintaining acceptable accuracy and convergence. In detail, an action-value estimator takes discretized features (e.g., approximate condition number and matrix norm) as input and outputs estimated action values, from which a policy selects the actions (chosen precision configurations for specific steps), optimized via an

ε

-greedy strategy to maximize a multi-objective reward to balance accuracy and computational cost. Empirical results demonstrate effective precision selection, \xy{increasing the use of lower-precision arithmetic} while maintaining accuracy comparable to double-precision baselines. \xy{We further evaluate the learned policies in a compiled CPU GMRES-IR implementation using FP16, FP32, and FP64 arithmetic for solver-level native validation.} The framework generalizes to diverse out-of-sample data and provides insights into applying RL precision selection to other numerical algorithms, advancing mixed-precision numerical methods in scientific computing. To the best of our knowledge, this is the first work on precision autotuning with RL with verification on unseen datasets.

Erin Carson, Xinye Chen

Charles University Prague, Czech · Sorbonne Université, CNRS, LIP6 Paris, France

Solver Iterations Full-Precision Performance Precision Offline Reinforcement Learning Greedy Algorithm Value Functions

Jul 15, 2024cs.DS

Faster and Simpler Greedy Algorithm for $k$ -Median and $k$ -Means

Clustering problems such as

k

-means and

k

-median are staples of unsupervised learning, and many algorithmic techniques have been developed to tackle their numerous aspects. In this paper, we focus on the class of greedy approximation algorithm, that attracted less attention than local-search or primal-dual counterparts. In particular, we study the recursive greedy algorithm developed by Mettu and Plaxton [SIAM J. Comp 2003]. We provide a simplification of the algorithm, allowing for faster implementation, in graph metrics or in Euclidean space, where our algorithm matches or improves the state-of-the-art.

Max Dupré la Tour, David Saulpic

K-Means Approximation Algorithms Clustering Greedy Algorithm Maximum Mean Discrepancy Unsupervised+1