Round handles are affiliated with smooth 4-manifolds in two major ways: 5-dimensional round handles appear extensively as the building blocks in cobordisms between 4-manifolds, whereas 4-dimensional round handles are the building blocks of broken Lefschetz fibrations on them. The purpose of this article is to shed more…
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,742 papers · 148 categories
Trend · papers per month
48 results for “logarithmic rounds”
We study the decades-old problem of online portfolio management and propose the first algorithm with logarithmic regret that is not based on Cover's Universal Portfolio algorithm and admits much faster implementation. Specifically Universal Portfolio enjoys optimal regret for financial instrum…
Logarithmic regret strategies for safe multi-armed bandits with safety risk constraints.
problem Maximizing reward while avoiding unsafe arms under safety risk constraints.
method Doubly optimistic strategies with pseudo-regret formulation.
result Logarithmic regret bounds for safe multi-armed bandits.
New algorithm for online portfolio selection with reduced runtime.
problem Maximizing total return in online portfolio selection.
method Minimizes current logarithmic loss regularized by log-determinant of Hessian.
result Achieves regret guarantee similar to Universal Portfolios with reduced runtime.
Sharp upper diameter limit found for Ricci solitons.
problem Bounding the diameter of compact shrinking Ricci solitons.
method Used a sharp logarithmic Sobolev inequality and Vitali-type covering argument.
result Sharp upper diameter bound established in terms of scalar curvature and entropy.
New insights into multi-armed bandits with budget constraints.
problem Multi-armed bandits with supply/budget constraints.
method Characterization of logarithmic regret rates, simple regret, and reduction to other bandit problems.
result Full characterization of logarithmic, instance-dependent regret rates for BwK.
We propose a novel, efficient approach for distributed sparse learning in high-dimensions, where observations are randomly partitioned across machines. Computationally, at each round our method only requires the master machine to solve a shifted ell_1 regularized M-estimation problem, and other workers to compute the g…
The paper develops a robust algorithm for contextual bandits with heavy-tailed rewards.
problem Contextual bandits with heavy-tailed rewards.
method Develops an algorithm based on Catoni's estimator for robust statistics, applying it to contextual bandits with general function approximation.
result Establishes regret bounds that depend on cumulative reward variance and logarithmically on the reward range and number of rounds.
Decentralized learning for matching markets with time-varying preferences.
problem Matching between competing agents and supply arms with time-varying preferences.
method Linear contextual bandit framework, learning algorithms to identify latent environment and stable matchings.
result Achieve instance-dependent logarithmic regret, applicable for large markets.
Two new algorithms optimize decentralized convex optimization with reduced communication rounds.
problem Decentralized minimization of smooth strongly convex functions in a network.
method Proposes two new algorithms based on accelerated Forward Backward methods.
result First algorithm is optimal in terms of communication rounds and gradient computations.
Paper tackles adaptive submodularity in sequential decision making.
problem Maximizing adaptive submodular functions with limited adaptive rounds.
method Proposes an efficient semi-adaptive policy with logarithmic adaptive rounds.
result Achieves an almost tight approximation guarantee.
The Logarithmic Singularities of the Green Functions of the Conformal Powers of the Laplacianmath.DG
Green functions play an important role in conformal geometry. In this paper, we explain how to compute explicitly the logarithmic singularities of the Green functions of the conformal powers of the Laplacian. These operators include the Yamabe and Paneitz operators, as well as the conformal fractional powers of the Lap…
Oracle-efficient algorithms reduce combinatorial semi-bandit regret to logarithmic time.
problem Scalability issue in combinatorial semi-bandit problems due to high combinatorial optimization costs.
method Oracle-efficient frameworks that minimize oracle queries while maintaining tight regret guarantees.
result Achieved regret with oracle queries for worst-case linear rewards.
Study on individual regret in cooperative MAB with agents communicating over a graph.
problem Individual regret in cooperative stochastic multi-armed bandits with communication constraints.
method Analyzed COOP-SE algorithm, derived individual regret bounds under various communication constraints.
result First to show an individual regret bound in cooperative stochastic MAB independent of graph diameter.
We introduce the community exploration problem that has many real-world applications such as online advertising. In the problem, an explorer allocates limited budget to explore communities so as to maximize the number of members he could meet. We provide a systematic study of the community exploration problem, from off…
Paper analyzes and improves KL-regularized RL for LLMs with logarithmic regret.
problem Improving efficiency of RL fine-tuning for large language models.
method Optimism-based KL-regularized online contextual bandit algorithm with novel regret analysis.
result Achieves an logarithmic regret bound.
The Milnor fiber conjecture is proven for splice type singularities.
problem Proving the Milnor fiber conjecture for a specific class of singularities.
method Combining techniques from tropical geometry, log geometry, and rounding of logarithmic spaces.
result The Milnor fiber conjecture is proven for splice type singularities.
We study a basic private estimation problem: each of users draws a single i.i.d. sample from an unknown Gaussian distribution, and the goal is to estimate the mean of this Gaussian distribution while satisfying local differential privacy for each user. Informally, local differential privacy requires that each data …
We introduce a new model of stochastic bandits with adversarial corruptions which aims to capture settings where most of the input follows a stochastic pattern but some fraction of it can be adversarially changed to trick the algorithm, e.g., click fraud, fake reviews and email spam. The goal of this model is to encour…
Paper generalizes VB-FTRL for online learning of quantum states with logarithmic loss.
problem Online learning of quantum states with logarithmic loss.
method Generalizes VB-FTRL algorithm for LL-OLQS with polynomial-time implementation.
result Achieves a regret rate of for LL-OLQS.
For a closed surface M with metric g, the Robin mass m(p) at the point p is the value of the Green function G(p,q) at p=q after the logarithmic singularity has been removed. The Laplacian-mass is the average value of the Robin mass, minus the value of the Robin mass for the round sphere of the same area. The Laplacian-…
New algorithm reduces online logistic regression regret without exponential constant.
problem Improper learning in online logistic regression with logarithmic regret.
method Regularized empirical risk minimization with surrogate losses.
result Regret scaling as O(B log(Bn)) with low computational complexity.
A new bandit algorithm observes arm rewards before playing, reducing regret.
problem Balancing exploration and exploitation with pre-observation costs.
method Design of OBP-UCB for single-player and C-MP-OBP for multi-player settings.
result Proved regret bounds for both single-player and multi-player settings.
Improved cumulative regret for sequence prediction with limited expert advice.
problem Minimizing cumulative regret in sequence prediction with limited information.
method Convex combination of experts with limited observation, achieving constant regret.
result Strategies achieve constant regret independent of the horizon T, improving over standard bounds.
Study optimal adaptive allocation for multi-armed bandits with Markovian rewards.
problem Optimal adaptive allocation for multi-armed bandits with Markovian rewards.
method Round-robin Kullback-Leibler upper confidence bounds for optimal adaptive allocation.
result Logarithmic dependence of regret on time horizon, asymptotically optimal.
A distributed bootstrap method for high-dimensional data reduces communication rounds efficiently.
problem Simultaneous inference on massive, high-dimensional data stored across many machines.
method Distributed bootstrap based on de-biased lasso with efficient cross-validation tuning.
result Theoretical lower bound on communication rounds for statistical accuracy and efficiency.
We define the "sum of squares of the wavelengths" of a Riemannian surface (M,g) to be the regularized trace of the inverse of the Laplacian. We normalize by scaling and adding a constant, to obtain a "mass", which is scale invariant and vanishes at the round sphere. This is an anlaog for closed surfaces of the ADM mass…
Study online learning with delays and capacity constraints, achieving optimal regret bounds.
problem Online learning with delays and capacity constraints.
method Novel scheduling and preemptive techniques, matching upper and lower bounds.
result Achieves optimal regret bounds across all capacity levels.
The paper ranks experts based on task performance with noisy evaluations.
problem Ranking experts based on their performance across multiple tasks with noisy evaluations.
method Develops adaptive strategies for ranking experts with a bound on the number of queries.
result Proves strategies allowing to recover the correct ranking of experts with high probability.
We study the question of whether parallelization in the exploration of the feasible set can be used to speed up convex optimization, in the local oracle model of computation. We show that the answer is negative for both deterministic and randomized algorithms applied to essentially any of the interesting geometries and…
Optimizes financial decisions with illiquid assets using Kelly criterion.
problem Determining optimal betting strategies in games with external capital constraints.
method Dynamic programming and WKB approximation for multi-round games; Kelly criterion for single-round games.
result Rational players adjust their risk-taking based on the proportion of their capital locked away.
Efficient RL for linear MDPs with unknown transitions.
problem Long planning horizons and unknown state transitions in linear mixture MDPs.
method Horizon-free algorithm using weighted least squares with variance and uncertainty awareness.
result Achieves optimal regret up to logarithmic factors.
We study a variant of the stochastic -armed bandit problem, which we call "bandits with delayed, aggregated anonymous feedback". In this problem, when the player pulls an arm, a reward is generated, however it is not immediately observed. Instead, at the end of each round the player observes only the sum of a number…
Capacity-Constrained Online Convex Optimization with Delayed Feedback
problem Online learning with delayed feedback under a hard capacity constraint
method Reduction to a delayed and weighted OCO problem using a scheduler
result First regret guarantees for capacity-constrained OCO under convex and strongly convex losses
Unified framework for expert selection with bandit and lower-bound feedback.
problem Selecting the best expert in scenarios with bandit feedback and lower-bound information.
method Introduces a new feedback model combining bandit and lower-bound information, proving optimal regret bounds for modified Exp3 algorithms.
result Optimal regret bounds for modified Exp3 algorithms, generalizing both bandit and full-information settings.
Paper tackles non-monotonic resource utilization in sequential decision-making.
problem Sequential decision-making under uncertainty with resource constraints.
method Introduces a new MDP policy with constant regret against LP relaxation.
result Develops a learning algorithm with logarithmic regret for unknown outcome distributions.
Near-Optimal Regret Bounds for Contextual Combinatorial Semi-Bandits with Linear Payoff Functionsstat.ML
Improved regret bounds for contextual combinatorial semi-bandits with linear payoffs.
problem Maximizing rewards in decision-making problems with feature vectors and constraints.
method Proposed C^2UCB algorithm and modified reward estimates for general constraints.
result Optimal regret bounds of C^2UCB algorithm and modified algorithm for various constraints.
Algorithm identifies Pareto front using multiple context directions and reuses exploration samples.
problem Identifying a set of arms with undominated mean reward vectors in linear bandits.
method Proposes a new estimator that updates estimates along multiple context directions and reuses exploration samples.
result Optimal sample complexity and logarithmic regret compared to optimal algorithms.
We study the problem of repeated play in a zero-sum game in which the payoff matrix may change, in a possibly adversarial fashion, on each round; we call these Online Matrix Games. Finding the Nash Equilibrium (NE) of a two player zero-sum game is core to many problems in statistics, optimization, and economics, and fo…
Improved guarantees for misspecified kernelized bandit optimization.
problem Misspecification in kernelized bandit optimization.
method Localization and domain splitting techniques.
result Logarithmic or polylogarithmic growth of misspecification amplification.
We propose a contextual-bandit approach for demand side management by offering price incentives. More precisely, a target mean consumption is set at each round and the mean consumption is modeled as a complex function of the distribution of prices sent and of some contextual variables such as the temperature, weather, …
We consider the problem of strongly-convex online optimization in presence of adversarial delays; in a T-iteration online game, the feedback of the player's query at time t is arbitrarily delayed by an adversary for d_t rounds and delivered before the game ends, at iteration t+d_t-1. Specifically for \algo{online-gradi…
Gradient descent with biased rounding errors converges faster under certain conditions.
problem Stagnation or negative impact of rounding errors in neural network training with low precision.
method Analysis of gradient descent with stochastic fixed-point rounding errors under the Polyak-Lojasiewicz inequality.
result Biased rounding errors can improve convergence rates, especially when the Polyak-Lojasiewicz inequality holds.
A distributed algorithm reduces communication cost in linear bandits to near-optimal levels.
problem Cooperative linear bandit optimization with stochastic contexts.
method DisBE-LUCB algorithm, DecBE-LUCB algorithm, sharing information through a central server or immediate neighbors.
result Communication cost of DisBE-LUCB matches information-theoretic lower bound up to logarithmic factors.
This paper sets communication complexity bounds for distributed RL.
problem Establishing minimum communication requirements for distributed RL.
method Information-theoretic lower bounds and algorithm development.
result Developed algorithms achieving optimal risk up to logarithmic factors.
In this paper, we consider a class of finite-sum convex optimization problems defined over a distributed multiagent network with agents connected to a central server. In particular, the objective function consists of the average of () smooth components associated with each network agent together with a s…
Small Total-Cost Constraints in Contextual Bandits with Knapsacks, with Application to Fairnessstat.ML
New method reduces total cost constraints in CBwK to sqrt(T) with fairness application.
problem Maximize rewards while adhering to total cost constraints in CBwK.
method Dual strategy based on projected-gradient-descent updates.
result Total cost constraints reduced to sqrt(T) with poly-logarithmic terms.
Adapts Exp3 to adversarial bandits with delays and data.
problem Adversarial multi-armed bandits with delayed feedback.
method Tuned Exp3 variants with step-size adaptation and implicit exploration.
result Optimal regret bounds of with high probability.