Paper develops MOSP for online resource allocation with sub-linear regret and fit.
problem Adversarial online convex optimization with delayed constraints.
method Developed a modified online saddle-point (MOSP) scheme for dynamic network resource allocation.
result MOSP achieves sub-linear dynamic regret and fit.
Bayesian optimisation algorithm for unknown search spaces with sub-linear regret.
problem Efficient optimisation of expensive black-box functions in unknown search spaces.
method Expands search space over iterations based on a hyperharmonic series, scales to high dimensions.
result Sub-linear regret growth for both algorithms.
New strategy for gambling with changing environments achieves sub-linear regret.
problem Optimizing rewards in a non-stationary X \mathcal{X} X -armed bandit problem. method Proposes a novel strategy for environments that change behavior abruptly.
result Proves the proposed strategy attains sub-linear cumulative regret.
New method speeds up diffusion models inference to sub-linear time.
problem Efficient inference of diffusion models for high-dimensional data.
method Parallel sampling with Picard iterations within blocks.
result Achieves sub-linear time complexity of O ~ ( p o l y log d ) \widetilde{\mathcal{O}}(\mathrm{poly} \log d) O ( poly log d ) . Study finds exact limits for sparse regression with fewer observations than usual.
problem Understanding sparse linear regression with sublinear sparsity.
method Adaptive interpolation method and modified AMP algorithm.
result Exact asymptotic expressions for mutual information and MMSE in sublinear sparsity.
Kernel ε ε ε -Greedy optimizes multi-armed bandits with covariates for sub-linear regret.
problem Optimizing multi-armed bandits with covariates in a reproducing kernel Hilbert space.
method Online weighted kernel ridge regression estimator for mean reward function estimation.
result Achieves sub-linear regret rate and optimal T \sqrt{T} T regret rate under margin condition. New model for multi-armed bandits with growing arms.
problem Balancing exploration and exploitation in a growing set of arms.
method Introduces Ballooning Multi-Armed Bandits (BL-MAB) and analyzes existing algorithms.
result Achieves sub-linear regret under certain conditions.
Optimal Liouville theorem for minimal disks in any codimension.
problem Characterizing harmonic functions on minimal disks in high-dimensional spaces.
method Analyzing harmonic functions and using Liouville's theorem.
result Optimal Liouville theorem for minimal disks in any codimension.
Efficiently designs distributed controllers for sparse systems with sub-linear sample complexity.
problem Designing robust distributed controllers for unknown-but-sparse linear systems.
method Combining distributed controller synthesis and structured linear inverse problems for system identification.
result Near-optimal distributed controllers can be learned with sub-linear sample complexity and near-linear time complexity.
Paper certifies k-means clustering optimality efficiently.
problem Detecting k k k -means optimality in suboptimal partitions. method Sub-linear Monte Carlo algorithm based on semidefinite relaxation.
result 3-approximation certificate with 99% confidence for mixtures of Gaussians.
The paper tackles online optimization with DR-submodular functions and linear budgets.
problem Optimizing points over time with long-term budget constraints and DR-submodular objectives.
method Proposes OSPHG algorithm to achieve sub-linear regret and budget violation bounds.
result Achieves sub-linear bounds for both regret and total budget violation under certain window lengths.
Paper tackles LDP bandits learning with improved results and sub-linear regret.
problem Contextual bandits learning with LDP privacy constraints.
method Simple black-box reduction frameworks for context-free bandits, extended to GLB.
result First result for BCO with multi-point feedback under LDP, sub-linear regret for GLB.
First robust bandit algorithm for contextual bandits with sub-linear regret.
problem Vulnerability of linear contextual bandit algorithms to adversarial attacks.
method Proposes a robust bandit algorithm for stochastic linear contextual bandits under fully adaptive and omniscient attacks.
result Sub-linear regret under various attacks without requiring attack information.
New algorithm tackles adversarial corruption in Lipschitz bandits with sub-linear regret.
problem Adversarial corruption in Lipschitz bandits.
method Developed robust Lipschitz bandit algorithms for weak and strong adversaries.
result Achieved sub-linear regret under both weak and strong adversaries.
Novel algorithm recovers sparse parameters in high-dimensional data with constant corruption.
problem Sparse regression with high dimensionality and constant fraction of corruptions.
method Robust Iterative Hard Thresholding, filtering algorithm for outlier removal.
result Near information-theoretically optimal error guarantee with sub-linear sample complexity.
In this work, we study the problem of aggregating a finite number of predictors for nonstationary sub-linear processes. We provide oracle inequalities relying essentially on three ingredients: (1) a uniform bound of the ℓ 1 \ell^1 ℓ 1 norm of the time varying sub-linear coefficients, (2) a Lipschitz assumption on the predict…
Deep Retrieval learns a retrievable structure for efficient large-scale recommendations.
problem Efficiently retrieving top relevant candidates in large-scale recommendation systems.
method Deep Retrieval learns a retrievable structure directly from user-item interaction data, encoding candidates into a discrete latent space and optimizing a model to maximize accuracy.
result Deep Retrieval achieves almost the same accuracy as brute-force baseline and significantly outperforms ANN baselines in a live production system.
New algorithms reduce slate bandit regret for large slates, outperforming existing methods.
problem Non-separable reward functions in slate bandits with many slates.
method Design of algorithms with sub-linear regret.
result Sub-linear regret with respect to the time horizon for large number of slates.
In this paper, we consider the problem of preserving privacy in the online learning setting. We study the problem in the online convex programming (OCP) framework---a popular online learning setting with several interesting theoretical and practical implications---while using differential privacy as the formal privacy …
New algorithms for planning with adversarial changes in costs.
problem Planning with adversarial changes in costs over time.
method Developed algorithms for adversarial SSP with high probability regret bounds.
result Obtained sub-linear regret bounds for adversarial SSP.
SGP combines PushSum with stochastic gradient updates for robust distributed deep learning.
problem Synchronization issues in distributed deep learning.
method Stochastic Gradient Push (SGP) using PushSum for approximate distributed averaging.
result SGP converges to a stationary point at the same rate as SGD and achieves consensus.
Paper tackles domain adaptation for contextual bandits with sub-linear regret.
problem Adapting contextual bandit algorithms across domains with distribution shift.
method Learn a bandit model for the target domain using feedback from the source domain.
result Sub-linear regret bound maintained across domains.
Study of deep Stable neural networks with various activation functions.
problem Characterizing the infinitely wide limits of deep Stable neural networks.
method Investigation of large-width properties of deep Stable NNs with a generalized central limit theorem for heavy tails.
result Extension of characterization to a broader class of activation functions, including sub-linear, asymptotically linear, and super-linear functions.
COBRA addresses strategic behavior in online platforms by ensuring truthful reporting without monetary incentives.
problem Ensuring truthful reporting from strategic agents in online platforms.
method Proposes COBRA, an algorithm for contextual bandits involving strategic agents that disincentivizes strategic behavior.
result COBRA achieves sub-linear regret guarantee and incentive compatibility without monetary incentives.
Proposes a transductive matrix completion method with calibration for multi-task learning.
problem Improving multi-task learning with multiple related data sources.
method Transductive matrix completion with calibration constraint.
result The proposed algorithm recovers incomplete feature and target matrices with improved results.
Safe Gaussian Process Bandit Optimization with sub-linear regret bounds.
problem Sequential decision-making under uncertainty and safety constraints.
method Developed SGP-UCB, a safe variant of GP-UCB with modifications to respect safety constraints.
result First sub-linear regret bounds for safe Gaussian Process Bandit Optimization.
Proposes SPFB method for optimizing partition functions in stochastic learning.
problem Optimizing partition functions in stochastic learning settings.
method Stochastic Gradient Bound (SPFB) method based on upper-bounding the partition function with a quadratic surrogate.
result Sub-linear convergence rate of SPFB method and efficient training of deep learning models.
New algorithms for uncoordinated spectrum access with multi-user multi-armed bandits.
problem Uncoordinated spectrum access with unknown number of users and channels.
method Developed algorithms for stochastic and adversarial settings, combining Exp3.P for dynamic scenarios.
result Sub-linear regret guarantees for both stochastic and adversarial cases, even when users outnumber channels.
New algorithm reduces risk in online games with limited feedback.
problem Risk-averse learning in repeated unknown games with bandit feedback.
method Proposes a momentum-based algorithm to estimate CVaR using historical cost values.
result Achieves sub-linear regret and outperforms existing methods in numerical experiments.
Upper bounds on ribbonlength of various knots, showing linear and sub-linear behavior.
problem Estimating the ribbonlength of different types of knots.
method Using Kauffman's model of folded ribbon knots, we derive upper bounds on ribbonlength for specific knot types.
result Upper bounds on ribbonlength are linear in crossing number for some knots and sub-linear for others.
A new algorithm improves stochastic linear bandit performance using residual bootstrap.
problem Improving performance in stochastic linear bandit problems.
method Residual bootstrap exploration to estimate mean reward and pull the arm with the highest estimate.
result Proposed algorithm exttt{LinReBoot} achieves high-probability sub-linear regret under mild conditions.
New algorithms for fair item allocation with limited copies.
problem Fair division of numerous items with few copies.
method Modeling as a contextual bandit problem with sub-linear regret guarantees.
result Proposed algorithms achieve sub-linear regret in fair item allocation.
The paper tackles minimax optimality in continuum contextual bandits with Hölder continuity.
problem Minimizing regret in a continuum of contexts with Hölder continuity.
method Proves a static-to-contextual regret conversion theorem and analyzes various dependency cases.
result Achieves minimax optimal contextual regret for convex and strongly convex bandits.
This paper addresses robust CBs for linear SEMs with model fluctuations.
problem Designing interventions in causal systems with linear SEMs that are robust to model fluctuations.
method Develops a robust CB algorithm and analyzes its regret under model deviation.
result The proposed algorithm achieves nearly optimal i l d e O ( T ) ilde{\mathcal{O}}(\sqrt{T}) i l d e O ( T ) regret when C C C is o ( T ) o(\sqrt{T}) o ( T ) and maintains sub-linear regret for a broader range of C C C . G-framework is presented by Peng [41] for measure risk under uncertainty. In this paper, we define fractional G-Brownian motion (fGBm). Fractional G-Brownian motion is a centered G-Gaussian process with zero mean and stationary increments in the sense of sub-linearity with Hurst index H ∈ ( 0 , 1 ) H\in (0,1) H ∈ ( 0 , 1 ) . This process has sta…
New NTK bounds show deep networks with minimum over-parameterization can still memorize and optimize.
problem Understanding memorization and optimization in sub-linear over-parameterized deep networks.
method Lower bound on NTK eigenvalues for deep networks with minimum over-parameterization.
result Deep networks with minimum over-parameterization can still be powerful memorizers and optimizers.
New BO method optimizes functions efficiently even with unknown hyperparameters.
problem Inaccurate estimation of Gaussian process hyperparameters degrades BO performance.
method Exploits multi-armed bandit and novel training loss function for consistent hyperparameter estimation.
result Sub-linear convergence to global optimum with unknown hyperparameters.
New algorithm detects network outliers with missing links.
problem Identifying outliers in networks with missing links.
method Proposes a new algorithm that detects outliers and predicts missing links.
result Proves the algorithm exactly detects outliers and achieves best error for missing link prediction.
Two models predict similar high-frequency price dynamics but differ in low-frequency impact strength.
problem Understanding the relationship between market prices and fundamental information.
method Comparing a microfounded linear model with a data-driven model at high and low frequencies.
result Both models predict similar high-frequency price dynamics but differ in low-frequency impact strength.
Paper tackles online DR-submodular maximization with stochastic constraints.
problem Maximizing utility while adhering to a cumulative resource constraint in an online setting.
method Proposes OLFW algorithm to solve the problem of online continuous DR-submodular maximization with linear stochastic constraints.
result Obtains sub-linear regret and constraint violation bounds.
Study designs steering rewards for MFGs with unknown dynamics and model uncertainty.
problem Designing incentives for large populations of agents in MFGs with uncertain model details.
method Developed optimistic exploration algorithms for agents with no-adaptive regret behaviors.
result Sub-linear regret guarantees for cumulative gaps between agent behaviors and desired outcomes.
Algorithm learns optimal arm selection in unsupervised sequential selection with contextual information.
problem Learning optimal arm selection in unsupervised sequential selection with contextual information.
method Proposes an algorithm for the contextual USS problem under the CWD property, demonstrating sub-linear regret.
result Demonstrates sub-linear regret for the proposed algorithm.
A new algorithm for restless bandits handles long-range dependencies.
problem Generalization of linear bandits with time-dependent parameters.
method LinMix-UCB algorithm with Berbee's coupling lemma.
result Sub-linear regret of $\mathcal{O}\left(\sqrt{d n\mathrm{polylog}(n) }
ight)$ .
Revisits elastic string model to explain interest rate correlations.
problem Describing the forward interest rate curve using an elastic string model.
method Reinterprets Baaquie and Bouchaud's (2004) model to highlight market forces.
result Model accurately reproduces FRC correlation structure with minimal parameters.
LNUCB-TA improves MAB performance by dynamically adjusting exploration rates and recognizing spatiotemporal patterns.
problem Suboptimal performance in environments with rapidly changing reward structures and static exploration rates.
method Hybrid model combining linear and nonlinear estimation, with adaptive k-NN for temporal attention.
result Significantly outperforms state-of-the-art algorithms in cumulative and mean reward, convergence, and robustness.
Study online learning with individual fairness without known similarity measure.
problem Online learning with individual fairness constraints without a known similarity measure.
method Reduction to standard online classification, leveraging auditor feedback.
result Achieves sub-linear regret and fairness violations with stochastic data.
Develops algorithms for CCBs with non-linear costs, improving safety and performance.
problem Safety constraints in sequential decision making with non-linear arm costs.
method Innovative algorithms using Inverse Gap Weighting (IGW) and online regression oracle.
result Sub-linear regret bounds for C-SquareCB and first-order regret for C-FastCB.
Adaptive PCA algorithms for changing environments.
problem Static adversarial regret is not suitable for changing environments.
method Online adaptive algorithms for PCA and variance minimization with sub-linear adaptive regret guarantees.
result The proposed algorithms adapt to changing environments.