The paper derives oracle inequalities for estimators with fast and slow rates.
problem Developing fast and slow oracle inequalities for estimators.
method Direct study of analysis estimator and adaptation of Dalalyan, Hebiri and Lederer's arguments.
result Constant-friendly rates for (square root) total variation regularized estimators over graphs.
Develops accelerated fixed-point methods with delayed oracles for scientific computing.
problem Approximating fixed points of nonexpansive operators.
method Combines Nesterov's acceleration and KM iteration with delayed inexact oracles.
result Establishes improved convergence rates for fixed-point approximation.
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.
Develops new oracle inequalities for Gaussian ranking estimators.
problem Lack of rigorous theoretical support for Gaussian ranking estimators.
method Novel oracle inequalities for regularized pairwise ranking.
result Derives fast learning rates under general dimension assumptions.
Crowdsourcing is an effective tool for human-powered computation on many tasks challenging for computers. In this paper, we provide finite-sample exponential bounds on the error rate (in probability and in expectation) of hyperplane binary labeling rules under the Dawid-Skene crowdsourcing model. The bounds can be appl…
The paper analyzes a method for non-negative matrix factorization using quasi-Bayesian aggregation.
problem Understanding the convergence rate of non-negative matrix factorization with quasi-Bayesian methods.
method Derives an oracle inequality for an aggregated estimator under a broad class of prior distributions.
result The prior distribution significantly influences the rate of convergence in non-negative matrix factorization.
The paper studies the benefits of curriculum learning in linear regression tasks.
problem Theoretical understanding of curriculum learning's benefits in machine learning.
method Theoretical analysis of curriculum learning in structured and unstructured multitask linear regression problems.
result Adaptive learning in the unstructured setting is fundamentally harder than oracle learning, but not in the structured setting.
New research shows fixed-budget best-arm identification cannot match static oracle performance.
problem Fixed-budget best-arm identification's performance limitations.
method Analysis of various adaptive and static algorithms for best-arm identification.
result For any algorithm, there exists at least one instance where the error decay rate is at most \((1 + \frac{\log(K)}{8})^{-1}\) times that of the static oracle.
New algorithm reduces contextual bandits to efficient regression.
problem Developing efficient algorithms for contextual bandits with general function classes.
method Reduction from contextual bandits to online regression with oracle.
result First universal and optimal reduction with no overhead.
Proposes a new method to improve estimation in Gaussian graphical models.
problem Optimal estimation in high-dimensional Gaussian graphical models.
method Graphical nonconvex optimization, approximated by a sequence of convex programs.
result Achieves the oracle rate of convergence and outperforms other methods.
Oracle inequality for sparse neural nets adapts to unknown structure.
problem Sparse deep neural nets in nonparametric regression.
method Gibbs posterior distribution with Metropolis-adjusted Langevin algorithms and mixture of uniform priors.
result Oracle inequality showing adaptation to unknown regularity and structure, achieving minimax-optimal rate of convergence.
Unified framework for bandit convex optimization with noisy gradient oracles.
problem Optimizing functions with noisy gradient feedback.
method Abstract oracle for gradient estimation, unifying previous methods.
result Achieving optimal root-n rate requires new algorithms or proof techniques.
New oracles improve stochastic optimization with noisy or biased measurements.
problem Optimizing functions with noisy or biased measurements.
method Introduced biased gradient oracles for stochastic optimization, analyzed RSG and SGD algorithms with these oracles.
result Derived non-asymptotic bounds for convergence rates of algorithms with biased gradient oracles.
The article studies a combined L 1 L_1 L 1 and concave regularization method for high-dimensional models.
problem Tackles variable selection and prediction in high-dimensional settings.
method Uses combined L 1 L_1 L 1 and concave penalties to optimize model sparsity and prediction risk. result Global optimum of the method achieves oracle prediction risk and false sign rate bounds.
The paper analyzes the efficiency of gradient estimation methods in noisy function evaluations.
problem Estimating gradients of smooth functions using noisy function evaluations.
method Information-theoretic lower bounds and finite difference method analysis.
result The finite difference method is not minimax optimal, suggesting room for improvement in gradient estimation.
Novel oracle-type inequality for logistic loss in DNNs achieves sharp convergence rates.
problem Generalization analysis for binary classification with DNNs and logistic loss.
method Established an oracle-type inequality to handle the boundedness of the target function.
result Optimal convergence rates for fully connected ReLU DNN classifiers trained with logistic loss.
Crowdsourcing has become an effective and popular tool for human-powered computation to label large datasets. Since the workers can be unreliable, it is common in crowdsourcing to assign multiple workers to one task, and to aggregate the labels in order to obtain results of high quality. In this paper, we provide finit…
The effect of errors in variables in quantization is investigated. We prove general exact and non-exact oracle inequalities with fast rates for an empirical minimization based on a noisy sample Z i = X i + ε i , i = 1 , … , n Z_i=X_i+ε_i,i=1,\ldots,n Z i = X i + ε i , i = 1 , … , n , where X i X_i X i are i.i.d. with density f f f and ε i ε_i ε i are i.i.d. with density η η η . These rates depend …
Paper develops robust regression method for heavy-tailed errors.
problem High-dimensional robust regression with heavy-tailed errors.
method Iteratively reweighted ℓ 1 \ell_1 ℓ 1 -penalized adaptive Huber regression. result Oracle convergence rate and variable selection consistency achieved.
New method improves CATE model selection with optimal regret rates.
problem Nontrivial task of selecting accurate CATE models.
method Causal Q-aggregation using doubly robust loss.
result Achieves optimal oracle model selection regret rates of log(M)/n.
Paper tackles dynamic pricing in a geometrically decaying environment, achieving better occupancy with lower rates.
problem Minimizing expected loss in a dynamically changing environment with decisions dependent on the data distribution.
method Introduces algorithms for information and loss function settings, using repeated decision deployment to allow mixing of the environment.
result Iteration complexity matches first and zero order stochastic gradient methods up to logarithmic factors.
Paper proposes estimators for sparse PCA with oracle property.
problem Estimating sparse principal subspace in high-dimensional settings.
method Semidefinite relaxation with novel regularizations.
result One estimator achieves exact support recovery and statistical rate.
We present a unified framework for low-rank matrix estimation with nonconvex penalties. We first prove that the proposed estimator attains a faster statistical rate than the traditional low-rank matrix estimator with nuclear norm penalty. Moreover, we rigorously show that under a certain condition on the magnitude of t…
New bounds on complexity for finding near-stationary points in stochastic convex optimization.
problem Finding near-stationary points in stochastic convex optimization.
method Joint analysis of local stochastic oracle and global oracle models; extensions of recursive regularization technique.
result Logarithmic dependence on smoothness in global oracle model for finding near-stationary points.
Improved Frank-Wolfe algorithm for constrained convex optimization with nearest extreme point oracle.
problem Constrained smooth convex minimization with limited linear optimization oracle access.
method Frank-Wolfe algorithm with nearest extreme point oracle.
result Improved complexity bounds for specific feasible sets, including linear convergence for 0 e x t − − 1 0 ext{--}1 0 e x t − − 1 polytopes. Nonparametric empirical Bayes denoising on Riemannian manifolds
problem Denoising measurements on compact Riemannian manifolds
method Using a surrogate oracle denoiser based on the marginal distribution of measurements
result Achieving nearly the Bayes risk in a low-noise regime
The paper improves count data regression models for overdispersed data.
problem Improving regression models for overdispersed count data.
method Double ℓ 1 \ell_1 ℓ 1 -regularized negative binomial regressions. result Oracle inequalities and consistency for Lasso estimators of partial regression coefficients.
Develops Frank-Wolfe Augmented Lagrangian for convex optimization.
problem Minimizing functions over intersections of convex sets.
method Frank-Wolfe Augmented Lagrangian (FW-AL) method.
result Sublinear convergence rate for general convex compact sets, linear for polytopes.
A discrete diffusion model learns denoising, scoring, and bridging in different coordinates.
problem Understanding what a discrete diffusion model learns in different coordinate systems.
method Rigorous derivation of continuous-time Markov chain ELBO, Oracle Distance theorem, and exact coordinates for optimizer.
result The negative ELBO is exactly equal to the data entropy plus the path KL from the oracle reverse process to the learned one.
New algorithm optimizes convex functions with noisy evaluations in one dimension.
problem Optimizing convex functions with noisy zero-order evaluations in one dimension.
method Proposed a computationally efficient algorithm achieving O ( 1 / T ) O(1/\sqrt{T}) O ( 1/ T ) convergence rate. result Achieved the optimal O ( 1 / T ) O(1/\sqrt{T}) O ( 1/ T ) convergence rate, closing the gap in one dimension. Improved GANs estimate convergence rate for density estimation.
problem Improving the accuracy of density estimation with GANs.
method Proved an oracle inequality for JS divergence between GAN estimate and true density.
result JS-divergence rate of convergence is ( log n / n ) 2 β / ( 2 β + d ) (\log{n}/n)^{2β/(2β+ d)} ( log n / n ) 2 β / ( 2 β + d ) . Study on costs of manipulating AMM-based price oracles.
problem Cost of manipulation in AMM-based on-chain price oracles.
method Analyzes the robustness of AMM-based oracles to strategic manipulation, considering different aggregation methods and market conditions.
result Manipulation costs depend on the total quote depth and can be minimized by optimal liquidity weights.
Paper introduces SGD for nonparametric additive models with optimal risk.
problem Training nonparametric additive models efficiently and accurately.
method Iterative algorithm based on stochastic gradient descent for truncated basis expansions.
result Estimator achieves minimax optimal risk in well-specified settings.
Optimizes average of convex functions with tight bounds.
problem Minimizing the average of m convex functions with gradient and prox oracles.
method Tight upper and lower bounds on complexity for deterministic and randomized optimization.
result Optimal methods for smooth and non-smooth functions, showing significant gap between deterministic and randomized settings.
Paper characterizes regularization methods' asymptotic equivalence in high-dimensional data.
problem Debate on which regularization method dominates in high-dimensional data.
method Characterizes asymptotic equivalence of convex and concave regularization methods.
result Concave methods are asymptotically equivalent to L1-regularization (Lasso) for polynomially growing dimensionality.
Paper proposes a new method to optimize deep neural networks with sparse regularization.
problem Difficulty in achieving optimal convergence rates for deep neural networks due to sparsity constraints.
method Introduces a novel penalized estimation method for sparse DNNs, resolving computational and theoretical issues.
result Establishes an oracle inequality for the excess risk of the proposed sparse-penalized DNN estimator and derives convergence rates.
Study on GANs learning distributions, deriving rates and regularization.
problem Learning distributions with GANs.
method Analysis of GANs through regularization theory.
result Optimal rates for distribution estimation under adversarial framework.
Improved non-smooth optimization methods achieve faster convergence rates.
problem Non-smooth optimization problems, especially in ℓ ∞ \ell_\infty ℓ ∞ and ℓ 1 \ell_1 ℓ 1 -SVM. method Higher-order accelerated methods, leveraging recent advances in smooth convex optimization.
result Achieved O ( ε − 4 / 5 ) O(ε^{-4/5}) O ( ε − 4/5 ) iteration complexity for ℓ ∞ \ell_\infty ℓ ∞ regression, breaking previous barriers. Develops kernel machines for missing response data.
problem Missing responses in data.
method Proposes kernel machine families for handling missing responses, including doubly-robust estimators.
result Oracle inequalities and consistency proved for kernel machine estimators.
Proposes RDIV for IV estimation avoiding limitations of existing methods.
problem Nonparametric estimation of IV regressions with practical limitations.
method Tikhonov-regularized DeepIV regression with model selection.
result Matches state-of-the-art convergence rate and provides rigorous guarantees.
Improved SGD algorithm with faster convergence.
problem Optimization of machine learning models.
method Conditional accelerated lazy stochastic gradient descent.
result Convergence rate of $O\left(\frac{1}{\varepsilon^2}
ight)$ , faster than previous methods.
New algorithm estimates partially-observed linear systems with better rates than previous methods.
problem Estimating parameters of partially-observed linear systems with long-term dependencies and semi-parametric noise.
method Prefiltered least squares estimator with semi-parametric noise model.
result First algorithm provably estimates parameters of partially-observed linear systems with rates not dependent on dependency decay rate.
Minimax PAC bounds for learning in exogenous contextual MDPs
problem PAC learning in tabular discounted Markov decision processes with exogenous i.i.d. contexts
method Variance-reduced algorithm for policy evaluation, best-value estimation, and best-policy extraction
result Minimax optimal sample complexity
A new method for faster optimization of noisy functions.
problem Optimizing noisy functions efficiently.
method A universal and adaptive second-order method for convex functions.
result Achieves O ( σ / T ) O(σ/ \sqrt{T}) O ( σ / T ) convergence for stochastic oracles and O ( 1 / T 3 ) O( 1 / T^3) O ( 1/ T 3 ) for deterministic oracles. New algorithm achieves small-loss bounds in online learning with improved rates.
problem Achieving strong stability in online learning algorithms.
method Introduces ρ ρ ρ -separation to enforce strong stability, unifying previous approaches. result Oracle-efficient algorithm achieves small-loss bounds with improved rates.
This paper establishes non-asymptotic oracle inequalities for the prediction error and estimation accuracy of the LASSO in stationary vector autoregressive models. These inequalities are used to establish consistency of the LASSO even when the number of parameters is of a much larger order of magnitude than the sample …
The paper analyzes sparse high-dimensional linear regression with random design and unknown error variance, providing adaptiveness and concentration rates.
problem Sparse high-dimensional linear regression with random design and unknown error variance.
method Analysis of posterior concentration rates, employing techniques to address model misspecification.
result Adaptiveness and concentration rates of the posterior for sparse high-dimensional linear regression.
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.