New algorithm speeds up learning of graphical models.
problem Learning graphical models with sparse structure efficiently.
method Vertex-greedy score-based algorithm for learning DAGs.
result Polynomial runtime for learning DAG models.
On-device research index
arXiv research
A locally-built, LLM-digested index of recent arXiv papers in quant finance, geometry/topology, and statistical ML — keyword search served straight from SQLite on this machine.
168,695 papers · 148 categories
Trend · papers per month
48 results for “greedy learning”
Paper analyzes Greedy-GQ for reinforcement learning with Markovian noise.
problem Analyzing Greedy-GQ for reinforcement learning with Markovian noise.
method Develops finite-sample analysis for Greedy-GQ with linear function approximation under Markovian noise.
result Provides theoretical justification for choosing stepsizes for faster convergence.
Study on rapid policy changes in reinforcement learning.
problem Rapid change of greedy policy in reinforcement learning.
method Empirical study and ablation analysis.
result Policy churn is a beneficial form of implicit exploration.
This paper proposes and evaluates the k-greedy equivalence search algorithm (KES) for learning Bayesian networks (BNs) from complete data. The main characteristic of KES is that it allows a trade-off between greediness and randomness, thus exploring different good local optima. When greediness is set at maximum, KES co…
Simpler ε-greedy with longer action durations improves exploration.
problem Limited exploration capability of ε-greedy in complex domains.
method Temporally extended ε-greedy with repeated actions for random durations.
result Temporally extended ε-greedy outperforms sophisticated methods on various domains.
Multiple-step lookahead policies have demonstrated high empirical competence in Reinforcement Learning, via the use of Monte Carlo Tree Search or Model Predictive Control. In a recent work \cite{efroni2018beyond}, multiple-step greedy policies and their use in vanilla Policy Iteration algorithms were proposed and analy…
We consider interactive learning and covering problems, in a setting where actions may incur different costs, depending on the response to the action. We propose a natural greedy algorithm for response-dependent costs. We bound the approximation factor of this greedy algorithm in active learning settings as well as in …
This paper analyzes the sample complexity of two timescale reinforcement learning algorithms.
problem Analyzing the sample complexity of two timescale reinforcement learning algorithms.
method Non-asymptotic analysis of linear and nonlinear TDC and Greedy-GQ algorithms under Markovian sampling with constant stepsize.
result The paper provides non-asymptotic convergence results for two timescale linear and nonlinear TDC and Greedy-GQ algorithms.
Introduces greedy feature selection for classifier-dependent feature ranking.
problem Feature selection for classification tasks.
method Greedy feature selection, identifying the most important feature at each step based on the selected classifier.
result Theoretical and numerical benefits of greedy feature selection.
Proposes ContSup to boost local learning by supplying context between isolated modules.
problem Local learning's performance degrades with more isolated modules.
method Theoretical analysis and ContSup scheme to supply context between modules.
result Significant performance improvement with minimal overhead.
This work improves RLHF performance guarantees using greedy sampling.
problem Learning the KL-regularized target with preference feedback.
method General preference model, greedy sampling.
result Order-wise improvements over existing RLHF performance guarantees.
A new method combines classical and machine learning PDE solvers efficiently.
problem Combining classical and machine learning PDE solvers to reduce computational cost and improve accuracy.
method Proposes an approximate greedy router to select solvers at each iteration, mimicking a greedy approach.
result Consistently reduces final error and AUC of the error trajectory compared to single-solver baselines and hybrid approaches.
Greedy algorithm nearly outperforms exploration in contextual bandits.
problem Balancing exploration and exploitation in online learning.
method Smoothed analysis of the greedy algorithm in linear contextual bandits.
result Greedy algorithm nearly matches Bayesian regret rate under diversity conditions, with regret at most .
Sparsity learning with known grouping structure has received considerable attention due to wide modern applications in high-dimensional data analysis. Although advantages of using group information have been well-studied by shrinkage-based approaches, benefits of group sparsity have not been well-documented for greedy-…
Greedy PIG adapts integrated gradients for better feature attribution.
problem Interpreting deep learning model predictions.
method Unified discrete optimization framework for feature attribution and selection.
result Greedy PIG improves feature attribution on various tasks.
Novel hybrid method for Bayesian network structure learning reduces computational time without sacrificing accuracy.
problem Bayesian network structure learning efficiency and accuracy trade-off.
method Partitioned PC (pPC), -value adjacency thresholding (PATH), hybrid greedy initialization (HGI).
result pHGS achieves significant computational reductions compared to the PC algorithm without sacrificing structure learning accuracy.
New algorithm for reinforcement learning reduces complexity and guarantees convergence.
problem Reinforcement learning problems with convex occupancy measures.
method MD-CURL, inspired by mirror descent, uses non-standard regularization.
result Achieves convergence guarantees and simple closed-form solution.
Breathing k-means outperforms greedy k-means++ in clustering.
problem Improving k-means clustering solutions.
method Dynamic adjustment of centroids through breathing technique.
result Breathing k-means outperforms other k-means techniques, especially greedy k-means++.
Greedy training of recursive partitioning estimators faces a computational barrier when the true function doesn't satisfy a specific property.
problem Computational inefficiency of greedy training for recursive partitioning estimators.
method Analysis of greedy training for sparse regression functions over binary features.
result Greedy training requires exponential samples when the true function doesn't satisfy a specific property (MSP), but only logarithmic samples when it does.
Greedy policies perform poorly in imperfectly observed contextual bandits.
problem Performance of Greedy policies in bandits with partially observed contexts.
method Analysis of Greedy reinforcement learning policies under imperfectly observed contextual bandits.
result Worst-case regret grows poly-logarithmically with the time horizon and the failure probability.
In this paper we consider the task of estimating the non-zero pattern of the sparse inverse covariance matrix of a zero-mean Gaussian random vector from a set of iid samples. Note that this is also equivalent to recovering the underlying graph structure of a sparse Gaussian Markov Random Field (GMRF). We present two no…
Greedy algorithms are widely used for problems in machine learning such as feature selection and set function optimization. Unfortunately, for large datasets, the running time of even greedy algorithms can be quite high. This is because for each greedy step we need to refit a model or calculate a function using the pre…
Transforms offline greedy algorithms to online algorithms for combinatorial problems.
problem Online decision-making in time-varying combinatorial environments.
method General framework using Blackwell approachability and Bandit Blackwell approachability.
result Achieves regret in full information setting and regret in bandit setting.
Quantum control is valuable for various quantum technologies such as high-fidelity gates for universal quantum computing, adaptive quantum-enhanced metrology, and ultra-cold atom manipulation. Although supervised machine learning and reinforcement learning are widely used for optimizing control parameters in classical …
Slow-Growing Treesstat.ML
A single slow-growing tree matches Random Forest's performance.
problem Matching Random Forest's performance with a single tree.
method SGT uses a learning rate to tame CART's greedy algorithm, improving on greedy ML algorithms.
result SGT and tree ensembles like Booging, BT, and RF improve performance.
We consider learning a convex combination of basis models, and present some new theoretical and empirical results that demonstrate the effectiveness of a greedy approach. Theoretically, we first consider whether we can use linear, instead of convex, combinations, and obtain generalization results similar to existing on…
Proposes a novel neural architecture for sparse coding using learned greedy pursuit.
problem Lack of interpretability in neural network architectures for sparse coding.
method Unfolded and learned version of Orthogonal Matching Pursuit (OMP) algorithm.
result Demonstrates flexibility and efficiency of the Learned Greedy Method (LGM) in various experiments.
Large-scale L1-regularized loss minimization problems arise in high-dimensional applications such as compressed sensing and high-dimensional supervised learning, including classification and regression problems. High-performance algorithms and implementations are critical to efficiently solving these problems. Building…
Greedy algorithm achieves sublinear regret for various distributions.
problem Efficient performance of greedy algorithms in linear contextual bandit problems.
method Introduced Local Anti-Concentration (LAC) condition to ensure sublinear regret.
result Greedy algorithm achieves cumulative expected regret.
Greedy algorithm optimizes consumption habits with power utility.
problem Optimizing lifetime consumption with habit formation under power utility.
method Developed a greedy algorithm using Monte Carlo simulation.
result Greedy solution is a good approximation to the optimal solution.
GUM tackles MARL by avoiding overestimation through state-marginal restriction.
problem Overestimation of values in large joint state-action spaces.
method Greedy UnMixing through state-marginal restriction and unmixing.
result Superior performance compared to existing Q-learning and general MARL algorithms.
We study the worst-case adaptive optimization problem with budget constraint that is useful for modeling various practical applications in artificial intelligence and machine learning. We investigate the near-optimality of greedy algorithms for this problem with both modular and non-modular cost functions. In both case…
Bayesian approach improves -greedy exploration in RL.
problem Improving -greedy exploration in model-free RL.
method Introducing a Bayesian model update for based on BMC.
result Proposed - exttt{BMC} algorithm efficiently balances exploration and exploitation.
In this work we propose a new deep learning tool called deep dictionary learning. Multi-level dictionaries are learnt in a greedy fashion, one layer at a time. This requires solving a simple (shallow) dictionary learning problem, the solution to this is well known. We apply the proposed technique on some benchmark deep…
Improved Thompson Sampling for Bayesian Optimization.
problem Handling the exploitation-exploration dilemma in Bayesian optimization.
method Incorporating epsilon-greedy policy into Thompson Sampling.
result Epsilon-greedy Thompson Sampling outperforms standard TS extremes.
We present an information-theoretic framework for sequential adaptive compressed sensing, Info-Greedy Sensing, where measurements are chosen to maximize the extracted information conditioned on the previous measurements. We show that the widely used bisection approach is Info-Greedy for a family of -sparse signals b…
Greedy pruning reduces neural networks by a logarithmic number of tickets, improving accuracy.
problem Pruning large neural networks to reduce size while maintaining accuracy.
method Greedy optimization-based pruning method with exponential decay guarantee.
result The discrepancy between pruned and original networks decays exponentially with network size.
Recent successful deep reinforcement learning algorithms, such as Trust Region Policy Optimization (TRPO) or Proximal Policy Optimization (PPO), are fundamentally variations of conservative policy iteration (CPI). These algorithms iterate policy evaluation followed by a softened policy improvement step. As so, they are…
We propose a new method for learning deep neural network models that is based on a greedy learning approach: we add one basis function at a time, and a new basis function is generated as a non-linear activation function applied to a linear combination of the previous basis functions. Such a method (growing deep neural …
We present a probabilistic framework for studying adversarial attacks on discrete data. Based on this framework, we derive a perturbation-based method, Greedy Attack, and a scalable learning-based method, Gumbel Attack, that illustrate various tradeoffs in the design of attacks. We demonstrate the effectiveness of thes…
New Classes of the Greedy-Applicable Arm Feature Distributions in the Sparse Linear Bandit Problemcs.LG
New distributions allow greedy arm selection in sparse bandit problems.
problem Sparse contextual bandit problem with sparse parameters and feature distributions.
method Introduced new distribution classes and demonstrated that mixtures of these distributions are also greedy-applicable.
result Greedy algorithm applicable to a wider range of arm feature distributions, including those with origin-asymmetric support.
This work proves lower bounds on a greedy teaching set construction algorithm.
problem Characterize the best-case teaching dimension of a concept class.
method A greedy algorithm that iteratively adds points to the teaching set to restrict the concept class the most.
result Lower bounds on the performance of the greedy approach for small k, extending up to k ≤ c*d for small constant c.
This paper is a follow up to the previous author's paper on convex optimization. In that paper we began the process of adjusting greedy-type algorithms from nonlinear approximation for finding sparse solutions of convex optimization problems. We modified there three the most popular in nonlinear approximation in Banach…
We expand the item response theory to study the case of "cheating students" for a set of exams, trying to detect them by applying a greedy algorithm of inference. This extended model is closely related to the Boltzmann machine learning. In this paper we aim to infer the correct biases and interactions of our model by c…
Enhances PMD with lookahead to improve RL performance.
problem Improving RL performance with greedy policies over 1-step.
method Integrates multi-step greedy policies into PMD with lookahead.
result Shows faster convergence rate for -PMD.
New algorithm improves privacy in high-dimensional machine learning models.
problem Privacy issues in learning large machine learning models.
method Differentially private greedy coordinate descent (DP-GCD) algorithm.
result Achieves logarithmic dependence on dimension for quasi-sparse solutions.
A commonly cited inefficiency of neural network training by back-propagation is the update locking problem: each layer must wait for the signal to propagate through the full network before updating. Several alternatives that can alleviate this issue have been proposed. In this context, we consider a simpler, but more e…
Greedy policy maximizes information in unknown linear systems.
problem Exploration in unknown linear dynamical systems.
method Online greedy policy maximizing information.
result Competitive performance compared to gradient-based methods.