FTPL achieves optimal regret in online non-convex learning.
problem Online non-convex learning with non-convex losses.
method Follow the Perturbed Leader (FTPL) algorithm.
result FTPL achieves optimal regret rate of .
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.
169,051 papers · 148 categories
Trend · papers per month
48 results for “FTPL algorithm”
This paper improves FTPL algorithm for semi-bandit problems with best-of-both-worlds guarantees.
problem Optimizing regret in adversarial and stochastic -set semi-bandit problems.
method Extending FTPL with geometric resampling (GR) to -set semi-bandits and analyzing its performance.
result FTPL with Fréchet and Pareto distributions achieves regret in adversarial setting and logarithmic regret in stochastic setting.
New algorithm optimizes multi-armed bandits with low computational cost.
problem Optimizing multi-armed bandits with low computational cost.
method Proposes a new FTPL algorithm with optimistic principle for ambiguity.
result Unified regret analysis and low computational costs.
Adaptive learning rates improve FTPL's BOBW guarantees in bandit problems.
problem Improving Follow-the-Perturbed-Leader's BOBW guarantees in bandit problems.
method Introducing surrogate probability functions to compute adaptive learning rates without exact probabilities.
result BOBW guarantees for FTPL with Pareto perturbations for any .
FTPL method shows near-optimal regret bounds for AMDPs with bandit feedback.
problem Minimizing regret in AMDPs with adversarial losses and bandit feedback.
method Follow-the-Perturbed-Leader (FTPL) method for AMDPs.
result FTPL achieves near-optimal regret bounds for AMDPs with bandit feedback.
Paper analyzes FTPL's effectiveness in combinatorial semi-bandit problems.
problem Optimizing FTPL policy in combinatorial semi-bandit problems.
method Geometric resampling (GR) and conditional geometric resampling (CGR) for FTPL in semi-bandit setting.
result FTPL achieves optimal regret bounds in both Fréchet and Pareto distributions.
Recent work on follow the perturbed leader (FTPL) algorithms for the adversarial multi-armed bandit problem has highlighted the role of the hazard rate of the distribution generating the perturbations. Assuming that the hazard rate is bounded, it is possible to provide regret analyses for a variety of FTPL algorithms f…
Unified algorithm for linear bandits with improved regret bound.
problem Adversarial linear bandits with improved regret.
method Self-concordant perturbations in FTPL framework.
result Regret bound of for hypercube and ball.
Paper optimizes FTPL for adversarial and stochastic bandits with specific tail distributions.
problem Optimizing Follow-the-Perturbed-Leader (FTPL) policy for bandit problems.
method Analyzes FTPL with Fréchet-type tail distributions in adversarial and stochastic settings.
result FTPL with certain Fréchet-type tail distributions achieves regrets in adversarial bandits.
Improved FTPL algorithm reduces regret in predictable minimax games.
problem Online learning and minimax games with predictable loss sequences.
method Optimistic modification of FTPL with dual regularization view.
result Tighter regret bounds for predictable sequences, accuracy.
Advances FTPL results for bandit problems with unbounded perturbations.
problem Improving analytical foundations of FTPL in bandit problems.
method Revisiting classical FTRL-FTPL duality for unbounded perturbations.
result Establishes Best-of-Both-Worlds (BOBW) results for FTPL under a broad family of asymmetric unbounded perturbations.
FTPL policy achieves best-of-both-worlds regret in decoupled bandits with reduced computational cost.
problem Decoupled multi-armed bandit problem with observed and unobserved losses.
method Follow-the-Perturbed-Leader (FTPL) policy that avoids convex optimization and resampling.
result Achieves constant regret in stochastic regime and optimal regret in adversarial regime.
Coop-FTPL algorithm minimizes network regret in semi-bandit settings.
problem Online combinatorial optimization with semi-bandit feedback on a network of agents.
method Cooperative Follow The Perturbed Leader (Coop-FTPL) algorithm with new loss estimation procedure.
result Expected regret of Coop-FTPL is of order Q mkT log(k)(kα1 /Q + m), with a state-of-the-art computational complexity of T^3/2.
New algorithm reduces prediction errors across various loss functions.
problem Online forecasting algorithms' inability to adapt to different loss functions.
method Design of a novel Follow-the-Perturbed-Leader (FTPL) algorithm with self-concordant noise.
result Simultaneously achieves regret for bounded proper losses and regret for bounded smooth proper losses.
FTPL with Fréchet perturbation achieves near optimal regret bounds for m-set semi-bandit problems.
problem Optimizing regret bounds for m-set semi-bandit problems in adversarial and stochastic settings.
method Follow-the-Perturbed-Leader (FTPL) with Fréchet perturbation.
result Achieves near optimal regret bounds of in adversarial setting and logarithmic regret in stochastic setting.
New methods improve online matrix optimization with reduced computational cost.
problem Online matrix optimization with operator norm constraints.
method Gradient-based prediction scheme with smoothed potentials for nuclear norm.
result Adaptive matrix optimizers match Shampoo's regret up to a constant factor.
We study a general online linear optimization problem(OLO). At each round, a subset of objects from a fixed universe of objects is chosen, and a linear cost associated with the chosen subset is incurred. To measure the performance of our algorithms, we use the notion of regret which is the difference between the to…
Online learning with one-sided feedback aims to maximize accuracy while ensuring fairness.
problem Maximizing accuracy in online learning with limited feedback and ensuring fairness.
method Extending the framework of Bechavod et al. (2020) to incorporate dynamic panels of auditors, reducing the problem to a contextual combinatorial semi-bandit, and leveraging Exp2 and Context-Semi-Bandit-FTPL algorithms.
result Multi-criteria no regret guarantees for accuracy and fairness are provided.
Examines algorithmic modeling across three cultures.
problem Tackles algorithmic modeling in different cultural contexts.
method Uses parametric regressions, interpretable algorithms, and complex algorithms.
result Extension of Leo Breiman's thesis to include cultural differences.
Playing repeated matrix games (RMG) while maximizing the cumulative returns is a basic method to evaluate multi-agent learning (MAL) algorithms. Previous work has shown that , , or algorithms have good behaviours on average in RMG. Besides, hedging algorithms have been shown to be effective on predi…
Meta-algorithm selection aims to choose the best algorithm selector for a given problem instance.
problem Selecting the best algorithm selector for a specific problem instance.
method Apply algorithm selection to the selection of other algorithms (meta-algorithm selection).
result Meta-algorithm selection can be beneficial in some cases but faces challenges in solving the meta-level problem.
Proposes CLRS benchmark to evaluate algorithmic reasoning.
problem Difficulty in transferring results across publications due to targeted algorithmic data.
method Develops a comprehensive benchmark covering various algorithmic tasks.
result Demonstrates performance of algorithmic reasoning baselines on the CLRS benchmark.
Combines multiple bandit algorithms to create a nearly optimal single algorithm.
problem Designing a single bandit algorithm that performs nearly as well as the best individual algorithm in a stochastic environment.
method Develops two general corralling algorithms that achieve favorable regret guarantees.
result The regret of the corralling algorithms is no worse than the best individual algorithm's performance.
Accelerated Randomized Coordinate Descent Algorithms for Stochastic Optimization and Online Learningcs.LG
We propose accelerated randomized coordinate descent algorithms for stochastic optimization and online learning. Our algorithms have significantly less per-iteration complexity than the known accelerated gradient algorithms. The proposed algorithms for online learning have better regret performance than the known rando…
The exchange algorithm is studied for its convergence and asymptotic variance.
problem Theoretical limitations of the exchange algorithm in sampling from doubly-intractable distributions.
method Theoretical analysis of the exchange algorithm's convergence speed and asymptotic variance.
result The exchange algorithm converges at a geometric rate and satisfies a Central Limit Theorem.
New algorithms optimize algorithm parameters in online settings with reduced computational costs.
problem Optimizing algorithm parameters in online settings with volatile and discontinuous losses.
method Developed semi-bandit optimization algorithms that leverage extra information to reduce computational costs.
result Achieved regret bounds as good as full-information feedback with significantly less computational effort.
Bayesian networks (BN) are used in a big range of applications but they have one issue concerning parameter learning. In real application, training data are always incomplete or some nodes are hidden. To deal with this problem many learning parameter algorithms are suggested foreground EM, Gibbs sampling and RBE algori…
No algorithm outperforms uniform sampling in A/B testing.
problem Identifying the best arm in A/B testing with fixed budget.
method Introducing consistent and stable algorithms, deriving lower bounds, and proving optimality of uniform sampling.
result No algorithm performs better than uniform sampling in A/B testing.
Improves algorithm selection for thousands of candidates using dyadic features.
problem Selecting the best algorithm from a large set of candidates for specific problems.
method Proposes extreme algorithm selection (XAS) with dyadic feature representation.
result Improves significantly over current state of the art in various metrics.
Combines online learning algorithms to achieve better performance.
problem Improving online learning algorithms with varying guarantees.
method Adding iterates of two parameter-free algorithms to create a new algorithm with improved regret.
result Generates efficient algorithms that adapt to multiple norms and maintain dimension-free guarantees.
New ELM algorithms reduce computation time and complexity.
problem Efficient computation of extreme learning machine (ELM) algorithms.
method Developed inverse-free ELM algorithms using recursive matrix inverse and inverse LDL' factorization.
result Proposed algorithms significantly reduce computational complexity.
This review article surveys data augmentation MCMC algorithms.
problem Sampling from intractable probability distributions.
method Comprehensive study of DA MCMC algorithms, their convergence properties, and acceleration strategies.
result Synthesizes recent developments and provides insights for researchers.
The Bayesian Learning Rulestat.ML
Bayesian learning rule unifies and generalizes various machine learning algorithms.
problem Machine learning algorithms are diverse and not always understood.
method Bayesian principles and natural gradients are used to derive algorithms.
result Derives a wide range of algorithms including classical and modern ones.
Learning to Optimizecs.LG
Algorithm design is a laborious process and often requires many iterations of ideation and validation. In this paper, we explore automating algorithm design and present a method to learn an optimization algorithm, which we believe to be the first method that can automatically discover a better algorithm. We approach th…
This review summarizes five Lasso optimization algorithms.
problem Optimizing the Lasso objective function.
method Five representative algorithms: ISTA, FISTA, CGDA, SLA, PFA.
result Comparison of convergence rates and strengths/weaknesses.
Neural networks mimic algorithms to solve complex problems.
problem Current machine learning methods struggle with generalisation and efficiency.
method Representing algorithms in a continuous space and adapting them to real-world problems.
result Neural networks can execute classical algorithms more efficiently.
Paper proposes a reinforcement learning framework for efficient hyper-parameter tuning of stochastic optimization algorithms.
problem Efficient tuning of hyper-parameters for stochastic optimization algorithms.
method Modeling hyper-parameter tuning as a Markov decision process and using policy gradient algorithms.
result The proposed framework significantly reduces the time required for hyper-parameter tuning compared to Bayesian optimization.
Approximate probabilistic inference algorithms are central to many fields. Examples include sequential Monte Carlo inference in robotics, variational inference in machine learning, and Markov chain Monte Carlo inference in statistics. A key problem faced by practitioners is measuring the accuracy of an approximate infe…
In this paper, we propose a convergent parallel best-response algorithm with the exact line search for the nondifferentiable nonconvex sparsity-regularized rank minimization problem. On the one hand, it exhibits a faster convergence than subgradient algorithms and block coordinate descent algorithms. On the other hand,…
Describes MLC search spaces in MEKA and WEKA software.
problem Understanding MLC algorithms and their transformations into SLC problems.
method Overviewed 26 MLC algorithms and 28 SLC algorithms, proposed a context-free grammar.
result Formal description of MLC search spaces and their transformations.
New algorithms reduce bilevel optimization complexity to ε^(-1.5).
problem Efficiently solving bilevel optimization problems in machine learning.
method Proposed two new algorithms: one using momentum-based recursive iterations, the other using recursive gradient estimations.
result Achieved computational complexity of ε^(-1.5), significantly faster than previous methods.
Researchers analyze how algorithmic and implementation choices affect RL performance.
problem Difficulty in separating algorithmic and implementation differences in RL performance.
method Unified derivations through a single control-as-inference objective, categorizing algorithms as EM or KL minimization.
result Implementation details are co-adapted with algorithmic choices, some transferable across algorithms.
Study on selecting between base algorithms in stochastic bandit problems.
problem Model selection in stochastic environments with contextual information.
method Developed a meta-algorithm-base algorithm abstraction with a smoothing transformation for optimal guarantees.
result Optimal model selection guarantees for stochastic contextual bandit problems.
New bounds derived for KG algorithm's performance in finite time.
problem Best arm identification problem in multi-armed bandit.
method Theoretical analysis of finite-time performance, deriving bounds for sample allocation, error probability, and regret.
result Upper and lower bounds for the probability of error and simple regret of the KG algorithm.
Paper proves linear convergence of SCMS algorithm for directional data.
problem Identifying density ridges in directional data.
method Generalized SCMS algorithm to directional data, derived from SCGA with adaptive step size.
result Linear convergence of the proposed directional SCMS algorithm.
MLE and CVE are equivalent under exponential families, leading to faster and more stable EM algorithms.
problem Finding maximum likelihood estimators (MLE) efficiently and stably.
method Proved equivalence between MLE and CVE under exponential families, leading to an EM algorithm.
result EM algorithm achieves the same asymptotic variance as MLE and is faster and more stable.
We resolve the fundamental problem of online decoding with general order ergodic Markov chain models. Specifically, we provide deterministic and randomized algorithms whose performance is close to that of the optimal offline algorithm even when latency is small. Our algorithms admit efficient implementation vi…
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.