Motivated by a range of applications in engineering and genomics, we consider in this paper detection of very short signal segments in three settings: signals with known shape, arbitrary signals, and smooth signals. Optimal rates of detection are established for the three cases and rate-optimal detectors are constructe…
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 “rate-optimal”
We study a nonparametric contextual bandit problem where the expected reward functions belong to a Hölder class with smoothness parameter . We show how this interpolates between two extremes that were previously studied in isolation: non-differentiable bandits (), where rate-optimal regret is achieved by run…
CARROT optimizes LLM routing by choosing the cheapest and most accurate model.
problem Optimizing query routing to the most cost-effective LLM for a given task.
method CARROT uses cost and performance estimates to select the best LLM for each query.
result CARROT is minimax optimal, selecting the best LLM for any query.
New algorithm optimizes best arm identification with minimal regret.
problem Best arm identification in multi-armed bandit problems.
method Characterized Bayesian simple regret with continuity conditions of prior, proposed a simple algorithm.
result Proposed algorithm achieves rate-optimal Bayesian simple regret.
ERM and RERM minimize error even with malicious label corruptions.
problem Malicious label corruptions in regression problems.
method Empirical Risk Minimizers (ERM) and Regularized Empirical Risk Minimizers (RERM) under a local Bernstein condition.
result The -error rate is bounded by $r_N + AL |\cO|/N$ under the local Bernstein condition.
The contextual bandit literature has traditionally focused on algorithms that address the exploration-exploitation tradeoff. In particular, greedy algorithms that exploit current estimates without any exploration may be sub-optimal in general. However, exploration-free greedy algorithms are desirable in practical setti…
Optimally tackles covariate shift in RKHS-based nonparametric regression.
problem Covariate shift in nonparametric regression over RKHS.
method Two families of covariate shift problems defined using likelihood ratios. Minimax rate-optimal estimators for KRR and reweighted KRR.
result KRR is minimax rate-optimal and strictly sub-optimal compared to naive estimator under covariate shift.
Meta learning of optimal classifier error rates allows an experimenter to empirically estimate the intrinsic ability of any estimator to discriminate between two populations, circumventing the difficult problem of estimating the optimal Bayes classifier. To this end we propose a weighted nearest neighbor (WNN) graph es…
Paper eliminates warm-up phase for PO in linear MDPs, achieving optimal regret.
problem Costly warm-up phase in PO algorithms for linear MDPs.
method Simple contraction mechanism replaces warm-up phase.
result Achieves rate-optimal regret with improved dependence on problem parameters.
Paper analyzes minimax risks of personalized federated learning algorithms.
problem Statistical heterogeneity among clients in federated learning.
method Minimax analysis of FedAvg and local training approaches.
result Threshold for optimality between FedAvg and local training depends on data heterogeneity.
Biclustering structures in data matrices were first formalized in a seminal paper by John Hartigan (1972) where one seeks to cluster cases and variables simultaneously. Such structures are also prevalent in block modeling of networks. In this paper, we develop a unified theory for the estimation and completion of matri…
Optimizes prediction error method for time-varying models.
problem Achieving optimal prediction error rates for time-varying models.
method Nonlinear least squares method for time-varying parametric models.
result First rate-optimal non-asymptotic analysis for time-varying models.
Study minimax off-policy evaluation in multi-armed bandits with known and unknown behavior policies.
problem Evaluate policies in multi-armed bandits with unknown behavior policies.
method Develop minimax rate-optimal procedures for known and unknown behavior policies, including the Switch estimator and Chebyshev polynomial-based estimator.
result Plug-in estimator achieves optimal competitive ratio up to a logarithmic factor when behavior policy is unknown.
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.
Unintended Effects on Adaptive Learning Rate for Training Neural Network with Output Scale Changecs.LG
Unintended effects from scaling neural network outputs with adaptive learning rates.
problem Adaptive learning rate optimization's behavior is altered by output scaling, leading to misinterpretation.
method Presented a modified optimization algorithm to mitigate unintended effects.
result Adaptive learning rate's effectiveness is significantly impacted by output scaling, especially for small scaling factors.
VAV method optimizes learning rate for faster, stable SGD convergence.
problem Optimizing learning rate for efficient and stable machine learning models.
method Energy-based self-adaptive learning rate with auxiliary variable .
result VAV method achieves faster convergence and superior stability with larger learning rates.
-norm constrained multi-block sparse canonical correlation analysis via proximal gradient descentstat.ME
New method finds linear relationships across multiple data blocks using proximal gradient descent with constraint.
problem Finding leading generalized eigenvectors for multi-block CCA.
method Proximal gradient descent with constraint.
result Rate-optimal solution under suitable assumptions.
Estimates treatment effects in panel data with general intervention patterns.
problem Estimating average treatment effects in panel data with heterogeneous treatment effects.
method Extends synthetic control framework to allow rate-optimal recovery of average treatment effects for general intervention patterns.
result First rate-optimal guarantees for general intervention patterns in estimating average treatment effects.
Study on estimating volatility of volatility using Fourier methods and provides insights into volatility dynamics.
problem Estimating the volatility of volatility (vol-of-vol) accurately and efficiently.
method Used Fourier methodology to estimate integrated volatility of volatility, bias-corrected and without bias-correction, comparing their asymptotic properties and accuracy.
result The bias-corrected estimator reaches the optimal rate , while the uncorrected estimator has a slower rate and smaller asymptotic variance.
A new test statistic speeds up MMD while maintaining power.
problem Efficiently testing two distributions without permutations.
method Cross-MMD statistic based on sample-splitting and studentization.
result Cross-MMD has a limiting standard Gaussian distribution under the null.
Neural networks estimate statistical divergences with performance guarantees.
problem Estimating statistical divergences with theoretical performance guarantees.
method Parametrizing empirical variational form by a neural network and optimizing over parameter space.
result Established non-asymptotic absolute error bounds for neural estimators of four -divergences.
New methods improve estimation accuracy in noisy settings.
problem Estimating treatment effects in the presence of treatment noise.
method Developed new structure-agnostic cumulant estimators and practical procedures for higher-order robustness.
result Demonstrated that existing DML estimator is suboptimal for non-Gaussian treatment noise and introduced ACE procedures for improved accuracy.
This work provides a simplified proof of the statistical minimax optimality of (iterate averaged) stochastic gradient descent (SGD), for the special case of least squares. This result is obtained by analyzing SGD as a stochastic process and by sharply characterizing the stationary covariance matrix of this process. The…
The basic model for high-frequency data in finance is considered, where an efficient price process is observed under microstructure noise. It is shown that this nonparametric model is in Le Cam's sense asymptotically equivalent to a Gaussian shift experiment in terms of the square root of the volatility function . A…
Study sharp convergence rates of empirical UOT for spatio-temporal point processes.
problem Statistical analysis of UOT for spatio-temporal point processes.
method Empirical plug-in estimators for Kantorovich-Rubinstein distance between intensity measures.
result Sharp convergence rates of empirical UOT in terms of intrinsic dimensions of measures.
Needlets have been recognized as state-of-the-art tools to tackle spherical data, due to their excellent localization properties in both spacial and frequency domains. This paper considers developing kernel methods associated with the needlet kernel for nonparametric regression problems whose predictor variables are de…
AEW estimator achieves optimal risk in expectation for large enough temperatures.
problem Understanding minimax-rate optimality of AEW estimator in model selection aggregation.
method Analyzing AEW estimator with exponential weights for squared loss under random design.
result AEW achieves excess risk in expectation for large enough temperatures.
Paper analyzes kNN estimator for KL divergence, proving its optimality.
problem Estimating KL divergence from identical samples.
method kNN estimator based on nearest neighbor distances.
result kNN method is asymptotically rate optimal for KL divergence estimation.
New model for pairwise comparisons without stochastic transitivity.
problem Suboptimal performance of models assuming stochastic transitivity in real-world scenarios.
method Proposes a general family of statistical models using a skew-symmetric matrix.
result Achieves minimax-rate optimality and adapts to data sparsity.
Greedy algorithms outperform UCB in many-armed bandit problems.
problem Optimizing multi-armed bandit problems with many arms.
method Subsampled UCB and greedy algorithms comparison.
result Greedy algorithms achieve optimal regret in many-armed bandit problems.
Study optimizes shared singular subspace estimation from noisy matrices.
problem Estimating shared singular subspaces across multiple noisy matrices.
method Low-rank matrix denoising framework with Stack-SVD and novel estimators.
result Stack-SVD achieves minimax rate-optimality for identical shared subspaces, and novel estimators for partial sharing.
Study approximates unknown function levels with queries.
problem Approximating unknown function levels through sequential queries.
method Introduce Bisect and Approximate algorithms to reduce to local function approximation.
result Rate-optimal sample complexity guarantees for H{ö}lder functions.
Robust Streaming PCAstat.ML
We consider streaming principal component analysis when the stochastic data-generating model is subject to perturbations. While existing models assume a fixed covariance, we adopt a robust perspective where the covariance matrix belongs to a temporal uncertainty set. Under this setting, we provide fundamental limits on…
New optimizers improve stock market forecasting accuracy.
problem Forecasting S&P 500 Index returns with MambaStock model.
method Evaluation of various optimizers (Adam, RMSProp, Lion, Roaree).
result Roaree optimizers combine faster training with reduced oscillations.
We analyze the Kozachenko--Leonenko (KL) nearest neighbor estimator for the differential entropy. We obtain the first uniform upper bound on its performance over Hölder balls on a torus without assuming any conditions on how close the density could be from zero. Accompanying a new minimax lower bound over the Hölder ba…
Kernel ridge regression (KRR) is a well-known and popular nonparametric regression approach with many desirable properties, including minimax rate-optimality in estimating functions that belong to common reproducing kernel Hilbert spaces (RKHS). The approach, however, is computationally intensive for large data sets, d…
We present a convergence rate analysis for biased stochastic gradient descent (SGD), where individual gradient updates are corrupted by computation errors. We develop stochastic quadratic constraints to formulate a small linear matrix inequality (LMI) whose feasible points lead to convergence bounds of biased SGD. Base…
We study estimation of (semi-)inner products between two nonparametric probability distributions, given IID samples from each distribution. These products include relatively well-studied classical and Sobolev inner products, as well as those induced by translation-invariant reproducing kernels, for whic…
New method clusters matrix-valued data by latent variables.
problem Clustering matrix-valued data with hidden structure.
method Latent variable model with hierarchical clustering.
result Algorithm attains clustering consistency in high dimensions.
Study optimizes dividend payout strategies under fluctuating interest rates.
problem Maximizing dividends under stochastic interest rates with negative values.
method Analytical HJB approach and backward SDEs for analysis.
result Explicit optimal strategies found for both time-dependent and strategy-independent stopping times.
In this paper, we study the multi-armed bandit problem in the batched setting where the employed policy must split data into a small number of batches. While the minimax regret for the two-armed stochastic bandits has been completely characterized in \cite{perchet2016batched}, the effect of the number of arms on the re…
We provide upper bounds of the expected Wasserstein distance between a probability measure and its empirical version, generalizing recent results for finite dimensional Euclidean spaces and bounded functional spaces. Such a generalization can cover Euclidean spaces with large dimensionality, with the optimal dependence…
Linear Partial Monitoring for Sequential Decision-Making: Algorithms, Regret Bounds and Applicationscs.LG
IDS algorithm optimizes sequential decisions in various monitoring settings.
problem Optimizing sequential decisions in complex monitoring scenarios.
method Information-directed sampling (IDS) algorithm for linear partial monitoring.
result IDS achieves nearly worst-case rate optimality in finite-action games.
In this paper, we propose a general framework for sparse and low-rank tensor estimation from cubic sketchings. A two-stage non-convex implementation is developed based on sparse tensor decomposition and thresholded gradient descent, which ensures exact recovery in the noiseless case and stable recovery in the noisy cas…
MARTHE optimizes learning rates online using hypergradient approximations.
problem Optimizing task-specific learning rates for better generalization.
method Online algorithm guided by hypergradient approximations, interpolating between RTHO and HD.
result Produces more stable learning rate schedules leading to better model generalization.
D-Adaptation automatically sets optimal learning rates without manual tuning.
problem Optimizing learning rates for efficient convergence in machine learning.
method D-Adaptation, which asymptotically achieves optimal learning rates without back-tracking or additional evaluations.
result D-Adaptation automatically matches hand-tuned learning rates across diverse problems.
Optimal control in changing systems without strong convexity assumptions.
problem Adversarial changes in convex costs for unknown linear systems.
method Non-convex lower confidence bounds and computationally-efficient regret minimization.
result Achieves -regret rate, optimal compared to best stabilizing controller.
We establish the consistency of an algorithm of Mondrian Forests, a randomized classification algorithm that can be implemented online. First, we amend the original Mondrian Forest algorithm, that considers a fixed lifetime parameter. Indeed, the fact that this parameter is fixed hinders the statistical consistency of …