Sublinear LSVI via LSH reduces runtime to sublinear in actions.
problem Efficiently estimating value functions in reinforcement learning with sublinear runtime.
method Formulated as approximate maximum inner product search, used LSH to solve with sublinear time complexity.
result Sublinear runtime while maintaining LSVI's regret.
Open problem seeks an online learning algorithm for binary classification.
problem Existence of an online learning algorithm for binary classification with sublinear mistakes.
method Assumption of sequence allowing learning algorithm's existence.
result Specific condition determines sequence's learnability.
New algorithms for constrained online optimization with memory and predictions.
problem Control of constrained dynamical systems and scheduling with reconfiguration budgets.
method Proposed algorithms achieving sublinear regret and constraint violation under time-varying constraints, both with and without predictions.
result First algorithms achieving sublinear regret and constraint violation in constrained online optimization with memory.
New algorithm achieves sublinear regret in CMDPs without error cancellations.
problem Safety constraints in reinforcement learning with error cancellations.
method Model-based primal-dual algorithm for CMDPs with multiple constraints.
result Achieves sublinear regret without error cancellations.
Paper presents a faster classical algorithm for principal component regression.
problem Efficiently solving principal component regression problems.
method Uses quantum-inspired linear algebra techniques.
result Achieves polylogarithmic runtime, significantly faster than state-of-the-art.
The paper connects discrete choice models to multi-armed bandit algorithms with sublinear regret bounds.
problem Optimizing user choices in a multi-armed bandit setting.
method Establishes connections between discrete choice models and multi-armed bandit algorithms, providing sublinear regret bounds and novel algorithms.
result Sublinear regret bounds for a family of algorithms, including the Exp3 algorithm.
LIBO optimizes repeated bandit tasks without prior knowledge or regret.
problem Optimizing repeated bandit tasks without prior knowledge or regret.
method LIBO sequentially meta-learns a kernel to adapt to the environment and solve tasks with the latest estimate.
result LIBO achieves sublinear lifelong regret, converging to oracle performance as more tasks are solved.
Online learning is a powerful tool for analyzing iterative algorithms. However, the classic adversarial setup sometimes fails to capture certain regularity in online problems in practice. Motivated by this, we establish a new setup, called Continuous Online Learning (COL), where the gradient of online loss function cha…
New algorithm improves game learning with randomised optimism.
problem Learning in matrix games with unknown payoffs and bandit feedback.
method Integrates evolutionary algorithms into bandit framework for randomised optimism.
result Achieves sublinear regret, outperforming classical methods.
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 O ( poly log T ) O(\operatorname{poly} \log T) O ( poly log T ) cumulative expected regret. Online learning algorithms are designed to learn even when their input is generated by an adversary. The widely-accepted formal definition of an online algorithm's ability to learn is the game-theoretic notion of regret. We argue that the standard definition of regret becomes inadequate if the adversary is allowed to a…
LaPSRL achieves optimal regret for isoperimetric RL distributions.
problem Designing RL algorithms with sublinear regret for non-log-concave distributions.
method Posterior Sampling (PSRL) and Langevin sampling (LaPSRL) for isoperimetric distributions.
result LaPSRL achieves order-optimal regret and subquadratic complexity.
The paper shows how sublinear biLipschitz equivalences affect Morse boundaries of metric spaces.
problem Understanding how sublinear biLipschitz equivalences affect Morse boundaries of metric spaces.
method Defining sublinear biLipschitz equivalence and Morse boundaries, proving invariance under SBEs, using sublinear rays.
result κ-Morse boundaries of proper geodesic metric spaces are invariant under suitable sublinear biLipschitz equivalences.
Two new algorithms reduce online kernel regression's computational cost while maintaining optimal regret bounds.
problem Trade-off between regret and computational cost in online kernel regression.
method AOGD-ALD and NONS-ALD algorithms dynamically maintain nearly orthogonal basis to approximate kernel mapping and control approximate error.
result Achieves nearly optimal regret bounds at sublinear computational complexity.
New data structure identifies close match from multiple distributions.
problem Identify the closest distribution to a given sample.
method Developed a sublinear-time data structure for identifying the closest distribution.
result First data structure that identifies the closest distribution in sublinear time.
The paper develops methods for time-varying constrained online convex optimization.
problem Time-varying loss and constraint functions in online convex optimization.
method Model-based augmented Lagrangian methods (MALM) for time-varying and delayed feedback.
result Sublinear regret and constraint violation for both time-varying and delayed feedback scenarios.
New approach for distributed online optimization of non-convex losses with sublinear regret.
problem Regret evaluation and consensus in distributed, multi-agent systems with non-convex losses.
method Composite regret metric and consensus-based online normalized gradient (CONGD) approach for pseudo-convex losses; offline optimization oracle for general non-convex losses.
result First sublinear regret bound for general distributed online non-convex learning.
GP-UCB resolves sublinear regret for kernelized bandits.
problem Minimizing regret in kernelized bandit problems.
method Using a new regularization technique for kernel ridge estimators, improving GP-UCB's sublinear regret rate.
result GP-UCB achieves nearly optimal sublinear regret for the Matérn kernel.
Efficiently trains large GMMs with millions to billions of parameters.
problem Training large Gaussian Mixture Models (GMMs) is computationally expensive.
method Derives a variational approximation integrated with mixtures of factor analyzers (MFAs) to reduce complexity.
result Sublinear scaling in training GMMs, achieving significant speed-ups.
Sublinear algorithms detect cliques in graphs with high probability.
problem Detecting a planted clique in random graphs efficiently.
method Non-adaptive low-degree polynomial queries of adjacency matrix entries.
result Sublinear time detection is possible for a specific range of clique sizes.
New algorithm tackles delayed feedback in Lipschitz bandits with sublinear regret.
problem Delayed feedback in Lipschitz bandits.
method Design of algorithms for bounded and unbounded stochastic delays.
result Sublinear regret guarantees for both bounded and unbounded delays.
New algorithm controls systems with unknown, changing losses.
problem Control systems with adversarial perturbations and unknown loss function.
method Efficient sublinear regret algorithm for bandit convex optimization with memory.
result Achieves efficient control with sublinear regret in the presence of unknown, changing losses.
Algorithm achieves logarithmic regret with sublinear hints.
problem Online linear optimization with limited hints.
method Using logarithmic hints to improve regret from sqrt(T) to log(T).
result O(log T) regret with O(sqrt(T)) hints, and O(sqrt(T)) regret with o(sqrt(T)) hints.
New sublinear sketches improve ANN and KDE for massive data streams.
problem Efficiently approximate nearest neighbors and kernel density estimation in large datasets.
method Developed sublinear space and query time algorithms for ANN and A-KDE in streaming and sliding-window models.
result Achieved near-optimal trade-offs between memory size and approximation error for ANN.
Two-stage mechanism designs reduce regret in recommender systems with stochastic covariates.
problem Designing effective recommender systems with user covariates sampled online.
method Two-stage algorithm integrating incentivized exploration with offline learning methods.
result Achieves sublinear regret while maintaining incentive compatibility.
Study online control of unknown time-varying systems with negative and positive results.
problem Online control of time-varying systems with unknown dynamics.
method Algorithmic upper bounds and lower bounds for different policy classes.
result Sublinear adaptive regret bounds for Disturbance Response policies.
Study online learning in unknown Markov games with sublinear regret.
problem Online learning in unknown Markov games with unobservable opponents.
method Introduced an algorithm achieving sublinear regret against the minimax value.
result First sublinear regret bound for unknown Markov games, independent of action spaces size.
New algorithms reduce communication for sparse mean estimation in noisy distributed systems.
problem Sparse normal means estimation with limited communication in a distributed setting.
method Two distributed algorithms for estimating a sparse mean vector with sublinear communication.
result Correct support of the sparse mean can be recovered with significantly less communication than previously required.
A well-known problem in data science and machine learning is {\em linear regression}, which is recently extended to dynamic graphs. Existing exact algorithms for updating the solution of dynamic graph regression require at least a linear time (in terms of n n n : the size of the graph). However, this time complexity might…
We present the first provably sublinear time algorithm for approximate \emph{Maximum Inner Product Search} (MIPS). Our proposal is also the first hashing algorithm for searching with (un-normalized) inner product as the underlying similarity measure. Finding hashing schemes for MIPS was considered hard. We formally sho…
The alternating gradient descent (AGD) is a simple but popular algorithm which has been applied to problems in optimization, machine learning, data ming, and signal processing, etc. The algorithm updates two blocks of variables in an alternating manner, in which a gradient step is taken on one block, while keeping the …
New algorithms reduce private bandit regret to nearly non-private levels.
problem Differentially private adversarial bandits and expert advice.
method Conversion of non-private algorithms to private, new algorithms for bandits and expert advice.
result Improved regret bounds for private bandits, sublinear for small ε.
Study on scheduling jobs with unknown types, achieving sublinear excess cost.
problem Optimizing job scheduling with unknown job types and varying durations.
method Design of algorithms for non-preemptive and preemptive scenarios, proving lower bounds.
result Preemptive algorithms can significantly outperform non-preemptive ones when job types have distinct durations.
New framework guides resource usage to achieve sublinear regret in adversarial settings.
problem Achieving sublinear regret in online decision making with changing reward and cost distributions.
method General primal-dual methods guided by spending plans that ensure balanced resource usage.
result Achieves sublinear regret with respect to spending plans that balance resource usage.
Quantum algorithm speeds up Gibbs partition function estimation.
problem Estimating partition functions in sublinear time.
method Sublinear-time quantum algorithm using quantum phase and amplitude estimation.
result First sublinear-time speed-up for partition function estimation.
We study the problem of estimating the expected reward of the optimal policy in the stochastic disjoint linear bandit setting. We prove that for certain settings it is possible to obtain an accurate estimate of the optimal policy value even with a number of samples that is sublinear in the number that would be required…
Study on optimal rates for sequential probability assignment using smoothed analysis.
problem Optimal rates for sequential probability assignment under smoothed adversaries.
method General-purpose reduction from minimax rates to transductive learning, development of an efficient algorithm using MLE oracle.
result Optimal (logarithmic) fast rates for parametric and finite VC dimension classes, sublinear regret for general classes.
Proposes H-UCRL for efficient model-based RL with sublinear regret.
problem Greedy policy exploration in model-based RL ignores epistemic uncertainty.
method Reparameterizes plausible models, hallucinates control, augments input space, solves with greedy planners.
result H-UCRL achieves provably sublinear regret for Gaussian Process models.
Paper generalizes extragradient methods for solving equations and inclusions with improved convergence rates.
problem Solving equations and inclusions using extragradient methods.
method Unified and generalized extragradient methods for a broader class of algorithms, analyzing sublinear convergence rates.
result Unified and improved convergence results for various extragradient variants.
Algorithm learns multiple tasks with minimal planning, achieving near-optimal performance.
problem Learning multiple tasks efficiently in a reinforcement learning setting.
method UCB Lifelong Value Distillation (UCBlvd) algorithm with structural assumption for shared exploration.
result Sublinear regret bound of i l d e O ( ( d 3 + d ′ d ) H 4 K ) ilde{\mathcal{O}}(\sqrt{(d^3+d^\prime d)H^4K}) i l d e O ( ( d 3 + d ′ d ) H 4 K ) with O ( d H log ( K ) ) \mathcal{O}(dH\log(K)) O ( d H log ( K )) planning calls. Paper proposes OPF policy for fair resource allocation with sublinear regret.
problem Fair resource allocation in an online setting against an unrestricted adversary.
method Online Proportional Fair (OPF) policy achieving approximate sublinear regret.
result OPF policy achieves c α c_α c α -approximate sublinear regret with c α ≤ 1.445 c_α \leq 1.445 c α ≤ 1.445 . The aim of this paper is to introduce the sublinear Higson corona and show that the sublinear Higson corona of Euclidean cone of P and X is decomposed into the product of P and that of X. Here P is a compact metric space and X is unbounded proper metric space. For example, the sublinear Higson corona of n-dimensional E…
Paper tackles stochastic k k k -submodular bandits with full feedback, achieving sublinear regret.
problem Online optimization of k k k -submodular functions with full-bandit feedback. method Proposes online algorithms for various k k k -submodular stochastic combinatorial multi-armed bandit problems. result Achieves sublinear α α α -regret bounds for multiple k k k -submodular stochastic combinatorial multi-armed bandit problems. A new federated algorithm reduces regret in X-armed bandit problems.
problem Collaborative optimization of heterogeneous local objectives.
method Fed-PNE algorithm using hierarchical partitioning and weak smoothness.
result Achieves sublinear cumulative regret with minimal communication.
Quantum algorithms reduce clustering input size, achieving near-linear approximation.
problem Efficiently clustering large datasets in quantum computing.
method Quantum coresets for k k k -clustering with sublinear query complexity. result Achieves near-linear approximation for k k k -clustering with coresets. New model for Knightian uncertainty with jumps.
problem Knightian uncertainty and non-linear jumps.
method Probabilistic construction of non-linear affine processes with jumps.
result Tractable model for Knightian uncertainty with sublinear expectations.
We give a proof of the sublinear tracking property for sample paths of random walks on various groups acting on spaces with hyperbolic-like properties. As an application, we prove sublinear tracking in Teichmueller distance for random walks on mapping class groups, and on Cayley graphs of a large class of finitely gene…
New algorithms tackle machine learning problems using manifold proximal point methods.
problem Maximizing the ℓ1 norm of a linear map over the sphere in machine learning.
method Manifold Proximal Point Algorithms (ManPPA) and Stochastic ManPPA (StManPPA).
result ManPPA and StManPPA achieve faster convergence rates than existing methods.