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.
Greedy algorithm optimizes consumption habits with power utility.
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…
The paper gives a systematic study of the approximate versions of three greedy-type algorithms that are widely used in convex optimization. By approximate version we mean the one where some of evaluations are made with an error. Importance of such versions of greedy-type algorithms in convex optimization and in approxi…
The contextual bandit literature has traditionally focused on algorithms that address the exploration-exploitation tradeoff. In particular, greedy algorithms that exploit current estimates without any exploration may be sub-optimal in general. However, exploration-free greedy algorithms are desirable in practical setti…
Paper analyzes Greedy-GQ for reinforcement learning with Markovian noise.
Improved greedy 2-coordinate updates for optimization problems with constraints.
Greedy algorithms outperform UCB in many-armed bandit problems.
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 between the low rank estimation and combinatorial optimization, so much so that our bounds are reminisce…
Greedy algorithm nearly outperforms exploration in contextual bandits.
Transforms offline greedy algorithms to online algorithms for combinatorial problems.
New algorithm speeds up learning of graphical models.
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…
Partial Wasserstein Covering aims to identify missing patterns in datasets.
Greedy selection works well in a toy model of independent increments.
Proposes an efficient alternative to nonconvex-nonconcave min-max optimization.
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…
Optimal selection of a subset of items from a given set is a hard problem that requires combinatorial optimization. In this paper, we propose a subset selection algorithm that is trainable with gradient-based methods yet achieves near-optimal performance via submodular optimization. We focus on the task of identifying …
Improved Thompson Sampling for Bayesian Optimization.
Greedy pruning reduces neural networks by a logarithmic number of tickets, improving accuracy.
Chebyshev Greedy Algorithm is a generalization of the well known Orthogonal Matching Pursuit defined in a Hilbert space to the case of Banach spaces. We apply this algorithm for constructing sparse approximate solutions (with respect to a given dictionary) to convex optimization problems. Rate of convergence results in…
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 …
We propose a new concept named adaptive submodularity ratio to study the greedy policy for sequential decision making. While the greedy policy is known to perform well for a wide variety of adaptive stochastic optimization problems in practice, its theoretical properties have been analyzed only for a limited class of p…
This work improves RLHF performance guarantees using greedy sampling.
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.
A new method combines classical and machine learning PDE solvers efficiently.
New insights into how randomization affects greedy model selection.
Given a finite family of functions, the goal of model selection aggregation is to construct a procedure that mimics the function from this family that is the closest to an unknown regression function. More precisely, we consider a general regression model with fixed design and measure the distance between functions by …
New methods optimize experiment selection for sequential data, improving model accuracy.
Greedy PIG adapts integrated gradients for better feature attribution.
Coordinate descent with random coordinate selection is the current state of the art for many large scale optimization problems. However, greedy selection of the steepest coordinate on smooth problems can yield convergence rates independent of the dimension , and requiring upto times fewer iterations. In this pap…
We study sparse approximate solutions to convex optimization problems. It is known that in many engineering applications researchers are interested in an approximate solution of an optimization problem as a linear combination of elements from a given system of elements. There is an increasing interest in building such …
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 makes selecting a sampling set non-trivial and hard to analyze. Indeed, though conditions for graph …
Often times, in many design problems, there is a need to select a small set of informative or representative elements from a large ground set of entities in an optimal fashion. Submodular optimization that provides for a formal way to solve such problems, has recently received significant attention from the controls co…
Kernel -Greedy optimizes multi-armed bandits with covariates for sub-linear regret.
We study sparse approximation by greedy algorithms. We prove the Lebesgue-type inequalities for the Weak Chebyshev Greedy Algorithm (WCGA), a generalization of the Weak Orthogonal Matching Pursuit to the case of a Banach space. The main novelty of these results is a Banach space setting instead of a Hilbert space setti…
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…
New analysis shows Thompson Sampling can work with greedy approximations in combinatorial bandits.
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…
This paper analyzes and guarantees convergence of prior-guided ZO algorithms.
AEGiS optimizes expensive function evaluations asynchronously.
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…
The design of multiple experiments is commonly undertaken via suboptimal strategies, such as batch (open-loop) design that omits feedback or greedy (myopic) design that does not account for future effects. This paper introduces new strategies for the optimal design of sequential experiments. First, we rigorously formul…
Proposes batch version of Greenkhorn for multimarginal OT, proving convergence.
In this report paper we first present a report of the Advanced Machine Learning Course Project on the provided data set and then present a novel heuristic algorithm for exact Bayesian network (BN) structure discovery that uses decomposable scoring functions. Our algorithm follows a different approach to solve the probl…
ATA optimizes task allocation in distributed machine learning.
We study the problem of sampling a bandlimited graph signal in the presence of noise, where the objective is to select a node subset of prescribed cardinality that minimizes the signal reconstruction mean squared error (MSE). To that end, we formulate the task at hand as the minimization of MSE subject to binary constr…
A new method achieves optimal uniformity in designs with minimal flexibility.