Paper tackles non-stationary kernelized bandits with near-optimal algorithm.
problem Minimizing regret in a time-varying reward function.
method Near-optimal algorithm with a novel restarting phased elimination with random permutation (R-PERP).
result Regret upper bound matches the lower bound, making the algorithm near-optimal.
Short proof for ideal polygons with near optimal orthogeodesic decomposition.
problem Decomposing ideal polygons into orthogeodesics.
method Short proof with orthogeodesic decomposition of length at most 2 log ( n ) 2 \log(n) 2 log ( n ) . result Optimal orthogeodesic decomposition of ideal polygons with length 2 log ( n ) 2 \log(n) 2 log ( n ) . New framework for DP-SMO with near-optimal privacy-loss trade-off.
problem Optimal trade-off between privacy and population loss in DP-SMO.
method General framework using Phased-ERM method and black-box optimization.
result Near-linear time algorithms with near-optimal guarantees.
Bayesian method estimates dynamics from near-optimal trajectories.
problem Estimating dynamics from near-optimal expert trajectories in reinforcement learning.
method Constraint-based Bayesian approach integrating expert near-optimality.
result Significant improvements in decision-making and transfer success.
We consider the fundamental learning problem of estimating properties of distributions over large domains. Using a novel piecewise-polynomial approximation technique, we derive the first unified methodology for constructing sample- and time-efficient estimators for all sufficiently smooth, symmetric and non-symmetric, …
A new RL approach learns near-equivalent actions for healthcare decisions.
problem Finding optimal actions in healthcare settings where actions may be near-equivalent.
method Temporal difference learning with a near-greedy heuristic for action selection.
result The proposed algorithm discovers meaningful near-equivalent actions and converges well.
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…
New algorithms find near-stationary points in convex optimization.
problem Finding near-stationary points in convex optimization.
method Memory-saving variant of OGM-G, accelerated SVRG, adaptively regularized accelerated SVRG.
result Schemes achieve fast rates for minimizing gradient norm and function value.
Efficient streaming algorithms for robust statistics with near-optimal memory.
problem High-dimensional robust statistics tasks in streaming model.
method First efficient streaming algorithms with near-optimal memory requirements.
result Near-optimal error guarantees and space complexity nearly-linear in the dimension for robust mean estimation.
A single policy suffices for near-optimal parallel exploration in RL.
problem Quantitative effects of parallel exploration in reward-free RL.
method Using a single policy to guide exploration across all agents.
result Near-linear speedup and near-minimax optimality for linear MDPs.
The article calculates the near horizon limit of Wang--Yau quasi-local mass.
problem Calculating the near horizon limit of quasi-local mass.
method Utilizing the properties of the mean curvature vector and optimal embedding equation.
result Existence and uniqueness of optimal embedding and continuity of quasi-local mass.
A new method finds diverse near-optimal portfolios using quality-diversity.
problem Optimizing financial portfolios with robustness to input parameter uncertainties.
method Quality-Diversity (QD) optimization using CVT-MAP-Elites algorithm.
result Diverse set of near-optimal portfolios identified.
The paper offers simple, near-optimal algorithms for multi-group learning.
problem Learning predictors within subgroups of a population, addressing fairness and hidden stratification.
method Studies the structure of solutions and provides simple, near-optimal algorithms.
result Simple and near-optimal algorithms for multi-group learning.
New algorithm detects changes quickly without knowing parameters, near optimally.
problem Quickest change detection with unknown parameters.
method Leverages theoretical asymptotic properties to derive a scalable approximate algorithm with near optimal performance.
result Detects changes in constant complexity with near optimal performance.
Near-optimal algorithms for predicting across multiple loss functions efficiently.
problem Predicting optimally across various loss functions simultaneously.
method Developed near-optimal online and offline learning algorithms for omniprediction.
result Achieved near-optimal complexity for both online and offline settings.
New DP algorithms achieve near-optimal regret bounds for online learning problems.
problem Online learning problems with zero-loss solutions and differential privacy constraints.
method Developed new Differentially Private algorithms with near-optimal regret bounds.
result Achieved near-optimal regret bounds for various online prediction and convex optimization problems.
We study the problem of regret minimization for distributed bandits learning, in which M M M agents work collaboratively to minimize their total regret under the coordination of a central server. Our goal is to design communication protocols with near-optimal regret and little communication cost, which is measured by the…
Algorithm extsc{Pedel} learns near-optimal policies efficiently on specific problems.
problem Learning near-optimal policies in linear MDPs with minimal samples.
method Online experiment design to focus exploration on relevant directions.
result Achieves instance-dependent complexity, outperforming minimax-optimal algorithms.
Paper tackles clustering with ordinal comparisons, achieving near-optimal results.
problem Clustering with ordinal comparisons when similarity measures are not available.
method Two-step procedure: estimate similarity matrix from comparisons, then apply SDP clustering.
result Near-optimal recovery of planted clustering using near-optimal number of comparisons.
Develops a high-dimensional differentially-private EM algorithm with near-optimal statistical guarantees.
problem Designing differentially-private EM algorithms for high-dimensional latent variable models.
method Noisy iterative hard-thresholding, statistical guarantees, near-optimal convergence rates.
result Near-optimal statistical guarantees and minimax rate optimality in high-dimensional settings.
New method quantifies uncertainty for near-optimal ML algorithms.
problem Uncertainty quantification for near-Bayes optimal ML algorithms.
method Developed a martingale posterior to recover Bayesian posterior from ML algorithms.
result Proved practical uncertainty quantification method applicable to general ML algorithms.
In this work, we propose a robust approach to design distributed controllers for unknown-but-sparse linear and time-invariant systems. By leveraging modern techniques in distributed controller synthesis and structured linear inverse problems as applied to system identification, we show that near-optimal distributed con…
Ensembles of random-feature models can't outperform a single large model.
problem Finding the optimal balance between model size and ensemble size.
method Deterministic equivalent risk estimates and scaling laws analysis.
result Ensembles of random-feature models achieve near-optimal performance only under specific conditions.
New algorithm solves complex optimization problems efficiently.
problem Minimizing convex upper-level functions over optimal lower-level solutions.
method Reformulates bilevel problems into functionally constrained problems, achieving near-optimal rates.
result Achieves near-optimal rates for both smooth and nonsmooth problems.
AE-LSVI identifies near-optimal policies in complex systems with minimal data.
problem Identifying near-optimal policies in complex, costly data acquisition systems.
method Combines optimism and pessimism for active exploration in a generative model setting.
result Proves near-optimal policy identification over entire state spaces with polynomial sample complexity.
Efficiently find near-optimal medical treatments with less trial and error.
problem Finding effective medical treatments through trial and error.
method Formalizes the problem, uses a causal inference framework, and proposes model-based dynamic programming and greedy algorithms.
result Our methods compare favorably to model-free reinforcement learning, offering a more transparent trade-off between search time and treatment efficacy.
Improved algorithm for adaptive dueling bandits with near-optimal regret bound.
problem Non-stationary dueling bandits with unknown number of preference changes.
method Elimination-based rescheduling algorithm for adaptive dynamic regret.
result Near-optimal i l d e O ( S e x t t t C W T ) ilde{O}(\sqrt{S^{ exttt{CW}} T}) i l d e O ( S e x ttt C W T ) dynamic regret bound. Algorithm finds near-optimal VaR portfolios using MILP, improving risk management.
problem Computing optimal VaR portfolios is hard due to non-convexity and combinatorial nature.
method Formulates VaR portfolio problem as MILP, uses alternate formulations for guarantees.
result Near-optimal VaR portfolios with near-optimality guarantees.
Study near-maturity convergence rates of American put prices in Lévy models.
problem Analyzing convergence rates of optimal exercise prices in Lévy models.
method Examined two settings: jumps of unbounded and bounded variation, deriving near-maturity expansions.
result Near-maturity convergence rate of optimal exercise price is of order √(T-t).
New algorithms improve robust estimation in contaminated Gaussian models.
problem Simultaneous estimation of location and variance matrix in contaminated Gaussian models.
method Tractable adversarial algorithms with spline discriminators for robust estimation.
result Achieve minimax optimal rates or near-optimal rates under Huber's contamination model.
This paper introduces a new metric, ULI, for RL that ensures both cumulative and instantaneous performance.
problem High-stakes applications require RL algorithms to avoid playing bad policies.
method Introduces uniform last-iterate (ULI) guarantee, a stronger metric capturing both cumulative and instantaneous performance.
result ULI directly implies near-optimal cumulative performance across various metrics, but not the other way around.
A new UCB algorithm for heavy-tailed bandits with near-optimal regret.
problem Sequential decision making in uncertain environments with heavy-tailed rewards.
method Data-driven, distribution-free UCB algorithm combining resampled median-of-means and UCB.
result Near-optimal regret bound for heavy-tailed distributions.
Neural networks can overfit perfectly to noisy data and then grok near-optimal generalization.
problem Neural networks' ability to overfit perfectly to noisy data and then generalize near-optimally.
method Two-layer ReLU networks trained by gradient descent on XOR cluster data.
result Neural networks can achieve perfect fit to noisy training data and then grok near-optimal generalization.
New algorithm reduces bias in trained models, near-optimal performance proven.
problem Reduction of bias in trained machine learning models.
method Scalable post-processing algorithm for debiasing trained models, including deep neural networks (DNNs).
result Proven to be near-optimal by bounding its excess Bayes risk.
New algorithms ensure reproducibility and optimal convergence in convex optimization.
problem Trade-off between reproducibility and convergence rate in convex optimization.
method Regularization-based algorithms for smooth convex minimization and minimax optimization.
result Achieves optimal reproducibility and near-optimal gradient complexity for various oracle settings.
New algorithms minimize risk in MNL bandits, achieving near-optimal performance.
problem Minimizing risk in multi-armed bandit problems.
method Designing algorithms for various risk criteria (e.g., CVaR, Sharpe ratio, entropy risk).
result Near-optimal regret for the designed algorithms.
New method finds near-optimal solutions for non-convex optimization problems.
problem Finding near-optimal solutions for non-convex optimization problems.
method Riemannian stochastic recursive momentum method
result Achieves a near-optimal complexity of i l d e O ( ε − 3 ) ilde{\mathcal{O}}(ε^{-3}) i l d e O ( ε − 3 ) . Study asymptotic behaviors of solutions near singular boundaries for the Yamabe problem.
problem Boundary behavior of the singular Yamabe problem near singular boundaries.
method Analysis of asymptotic behaviors and derivation of optimal estimates for background metrics.
result Solutions are well approximated by solutions in tangent cones at singular points.
Optimal resource allocation is a fundamental challenge for dense and heterogeneous wireless networks with massive wireless connections. Because of the non-convex nature of the optimization problem, it is computationally demanding to obtain the optimal resource allocation. Recently, deep reinforcement learning (DRL) has…
Optimal subspace embedding with near-optimal sparsity for high-dimensional data.
problem Efficiently preserving norms of vectors in high-dimensional subspaces.
method Near-optimal sparsity oblivious subspace embedding with decoupling argument and cumulant method.
result Achieved near-optimal sparsity of O ~ ( 1 / ε ) \tilde O(1/ε) O ~ ( 1/ ε ) non-zeros per column. New method learns near-optimal policies with polynomial samples in A and H.
problem Episodic latent MABs with partial observations are challenging.
method Experiment design and method-of-moments approach.
result Polynomial samples in A and H for near-optimal policy learning.
Improved Gumbel watermark detection method.
problem Detecting Gumbel watermarking with high accuracy.
method A near-optimal model-agnostic detection mechanism.
result Demonstrates near-optimal performance under i.i.d. assumptions.
New algorithm speeds up Gaussian process optimization.
problem Scalability issues in Gaussian process optimization.
method BBKB (Batch Budgeted Kernel Bandits) algorithm that selects candidates in batches and adaptively delays updates.
result Provable near-linear time complexity and significant speedup over existing methods.
CD algorithm achieves near-optimal convergence rate for unnormalized models.
problem Training unnormalized models with high efficiency.
method Non-asymptotic analysis of contrastive divergence algorithm.
result CD can achieve O ( n − 1 / 2 ) O(n^{-1 / 2}) O ( n − 1/2 ) convergence rate under regularity assumptions. A major challenge in Bayesian Optimization is the boundary issue (Swersky, 2017) where an algorithm spends too many evaluations near the boundary of its search space. In this paper, we propose BOCK, Bayesian Optimization with Cylindrical Kernels, whose basic idea is to transform the ball geometry of the search space us…
SARAH and SPIDER are two recently developed stochastic variance-reduced algorithms, and SPIDER has been shown to achieve a near-optimal first-order oracle complexity in smooth nonconvex optimization. However, SPIDER uses an accuracy-dependent stepsize that slows down the convergence in practice, and cannot handle objec…
Near-optimal confidence intervals for bounded data.
problem Online inference for sequential decision problems like A/B testing.
method Utilizing Bentkus' concentration results to improve on existing methods.
result Near-optimal confidence intervals confirmed favorable in synthetic and practical applications.
We decode latent states in Block MDPs and learn near-optimal policies.
problem Model estimation and reward-free learning in Block MDPs.
method Information-theoretical lower bound and efficient model estimation algorithm.
result Our algorithm approaches the information-theoretical limit for latent state decoding and converges to optimal policies.