Folded concave penalization methods have been shown to enjoy the strong oracle property for high-dimensional sparse estimation. However, a folded concave penalization problem usually has multiple local solutions and the oracle property is established only for one of the unknown local solutions. A challenging fundamenta…
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,657 papers · 148 categories
Trend · papers per month
48 results for “oracle property”
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 investigate properties of estimators obtained by minimization of U-processes with the Lasso penalty in high-dimensional settings. Our attention is focused on the ranking problem that is popular in machine learning. It is related to guessing the ordering between objects on the basis of their observed predictors. We p…
Two important goals of high-dimensional modeling are prediction and variable selection. In this article, we consider regularization with combined and concave penalties, and study the sampling properties of the global optimum of the suggested method in ultra-high dimensional settings. The -penalty provides th…
We present a probabilistic modeling framework and adaptive sampling algorithm wherein unsupervised generative models are combined with black box predictive models to tackle the problem of input design. In input design, one is given one or more stochastic "oracle" predictive functions, each of which maps from the input …
New algorithm achieves faster multicalibration in online settings.
problem Achieving fair predictions in online settings with limited interaction.
method Generalized multicalibration to arbitrary bounded hypothesis classes and introduced swap multicalibration. Proposed an oracle-efficient algorithm achieving faster multicalibration error.
result Oracle-efficient algorithm achieves -swap multicalibration error with high probability, improving on previous bounds.
High throughput genetic sequencing arrays with thousands of measurements per sample and a great amount of related censored clinical data have increased demanding need for better measurement specific model selection. In this paper we establish strong oracle properties of nonconcave penalized methods for nonpolynomial (N…
Semi-supervised active clustering (SSAC) utilizes the knowledge of a domain expert to cluster data points by interactively making pairwise "same-cluster" queries. However, it is impractical to ask human oracles to answer every pairwise query. In this paper, we study the influence of allowing "not-sure" answers from a w…
Method discovers symmetries in data with neural networks.
problem Discovering symmetries in high-dimensional data.
method Fully connected neural networks trained with a loss function for symmetry.
result Generators for symmetries in latent space.
Paper develops methods for non-quadratic loss low-rank matrix recovery.
problem Recovery of low-rank matrices with non-quadratic losses.
method Projected gradient method with a regularity projection oracle.
result Projected gradient method converges globally and linearly.
Simplifies online learning with consistent oracle to fewer mistakes.
problem Online learning with computationally intractable Littlestone dimension computation.
method Novel algorithm making at most mistakes, simpler proof.
result No algorithm can make less than mistakes.
Develops algorithms for multi-class Neyman-Pearson classification with cost sensitivity.
problem Asymmetric misclassification costs in multi-class classification problems.
method Establishes connection with cost-sensitive learning, proposes two algorithms, extends NP oracle properties.
result Proposes algorithms with theoretical guarantees for multi-class Neyman-Pearson classification.
Oracle inequalities and variable selection properties for the Lasso in linear models have been established under a variety of different assumptions on the design matrix. We show in this paper how the different conditions and concepts relate to each other. The restricted eigenvalue condition (Bickel et al., 2009) or the…
Extracts fairness truth from classifiers using an oracle.
problem Fairness in classification algorithms without context.
method Uses fairness oracle to learn underlying fairness truth.
result Extracts metric fairness from classifiers.
We consider the finite sample properties of the regularized high-dimensional Cox regression via lasso. Existing literature focuses on linear models or generalized linear models with Lipschitz loss functions, where the empirical risk functions are the summations of independent and identically distributed (iid) losses. T…
New algorithm reduces high-dimensional data processing costs and achieves true sparsity.
problem High computational costs and difficulty in achieving true sparsity in distributed inference.
method Two-stage distributed best subset selection with oracle property.
result Correctly finds true sparsity pattern and achieves the oracle property.
This paper investigates tradeoffs among optimization errors, statistical rates of convergence and the effect of heavy-tailed errors for high-dimensional robust regression with nonconvex regularization. When the additive errors in linear models have only bounded second moment, we show that iteratively reweighted $\ell_1…
A new Bayesian method optimizes time-dependent expensive functions with lookahead.
problem Maximizing a time-dependent, expensive oracle with limited evaluations.
method Recursive, two-step lookahead expected payoff (r2LEY) acquisition function.
result r2LEY outperforms myopic methods in synthetic and real-world datasets.
We present a new method for design problems wherein the goal is to maximize or specify the value of one or more properties of interest. For example, in protein design, one may wish to find the protein sequence that maximizes fluorescence. We assume access to one or more, potentially black box, stochastic "oracle" predi…
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…
We investigate the computational complexity of several basic linear algebra primitives, including largest eigenvector computation and linear regression, in the computational model that allows access to the data via a matrix-vector product oracle. We show that for polynomial accuracy, calls to the oracle are nece…
The paper explores MAB strategies for very short horizons, introducing new methods and showing improved performance.
problem Short horizon multi-armed bandit problems in games.
method Regression oracles, forced exploration, UCBT strategy.
result Combination of epsilon-greedy or epsilon-decreasing with regression oracles outperforms other strategies.
High-dimensional data analysis has motivated a spectrum of regularization methods for variable selection and sparse modeling, with two popular classes of convex ones and concave ones. A long debate has been on whether one class dominates the other, an important question both in theory and to practitioners. In this pape…
BEAUTY Powered BEASTstat.ME
A new test method improves goodness-of-fit tests for copulas.
problem Developing robust tests for copula goodness-of-fit.
method Binary Expansion Approximation of UniformiTY (BEAUTY) and Binary Expansion Adaptive Symmetry Test (BEAST).
result The BEAST method improves empirical power against various alternatives.
We discuss the problem of adaptive discrete-time signal denoising in the situation where the signal to be recovered admits a "linear oracle" -- an unknown linear estimate that takes the form of convolution of observations with a time-invariant filter. It was shown by Juditsky and Nemirovski (2009) that when the $\ell_2…
Unified framework for understanding GRPO as U-statistic.
problem Theoretical properties of GRPO remain less studied.
method Unified framework through classical U-statistics.
result GRPO is asymptotically equivalent to an oracle policy gradient algorithm.
Proposes a new robust expectile regression method for high-dimensional data.
problem Heterogeneity in high-dimensional data with heteroscedastic variance or inhomogeneous covariate effects.
method Iteratively reweighted ℓ1-penalization for robust expectile regression (retire).
result Oracle convergence rate after log(log d) iterations in high-dimensional settings.
Researchers compare different gradient methods for ridge regression, finding conjugate gradients have similar performance.
problem Comparing statistical properties of different gradient methods in ridge regression.
method Explicit non-standard error decomposition to bound prediction error of conjugate gradient iterates.
result Conjugate gradient iterates share optimality properties with gradient flow and ridge regression up to a constant factor.
Oracle-efficient algorithms reduce combinatorial semi-bandit regret to logarithmic time.
problem Scalability issue in combinatorial semi-bandit problems due to high combinatorial optimization costs.
method Oracle-efficient frameworks that minimize oracle queries while maintaining tight regret guarantees.
result Achieved regret with oracle queries for worst-case linear rewards.
New method recovers clusters in non-convex finite metric spaces with oracle queries.
problem Exact recovery of clusters in non-convex finite metric spaces.
method Introducing -convexity and a deterministic algorithm using oracle queries.
result Clusters can be recovered using same-cluster queries.
New analysis shows Thompson Sampling can work with greedy approximations in combinatorial bandits.
problem Thompson Sampling's theoretical limits with greedy approximations in combinatorial semi-bandits.
method Study with greedy oracle, providing lower and upper bounds on regret.
result First theoretical results showing TS can work with greedy approximations, breaking misconceptions.
New algorithms sample convex bodies using Markov chains and restricted Gaussian oracles.
problem Sampling uniformly from convex bodies efficiently.
method Markov chain Monte Carlo with proximal sampler and restricted Gaussian oracle.
result Efficient implementation of RGO for uniform sampling on convex bodies.
MAMBA learns policies competitive with multiple conflicting oracles.
problem Learning policies from multiple conflicting oracles in reinforcement learning.
method MAMBA uses a gradient estimator in the style of GAE to optimize policies, leveraging demonstrations from multiple weak oracles.
result MAMBA outperforms the state-of-the-art in learning policies competitive with multiple conflicting oracles.
We study the problem of interactively learning a binary classifier using noisy labeling and pairwise comparison oracles, where the comparison oracle answers which one in the given two instances is more likely to be positive. Learning from such oracles has multiple applications where obtaining direct labels is harder bu…
ConfHit provides valid guarantees for generative models without oracle access.
problem Reliable guarantees for novel candidate generation in generative models.
method Formalizes certification and refinement of generated sets, leveraging weighted exchangeability and density-ratio weighted conformal p-values.
result Consistently delivers valid coverage guarantees and compact certified sets across various generative tasks.
New oracle uses uncertainty for active classification with noisy feedback.
problem Improving query complexity in interactive binary classifier learning.
method Proposes a new pairwise comparison oracle that considers uncertainty and an adaptive labeling algorithm.
result Demonstrates improved performance and efficiency compared to existing methods.
Quantum oracles help identify counterfactuals better than classical ones.
problem Identifying unknown causal parameters in causal models.
method Using quantum oracles to query and identify all causal parameters and counterfactuals.
result Quantum oracles enable identification of all two-way joint counterfactuals and tighter bounds on higher-order counterfactuals.
SoQal reduces oracle label requests in active learning by up to 35%.
problem Exploiting unlabelled data in healthcare requires costly oracle labeling.
method Dynamic questioning strategy to minimize oracle label requests.
result SoQal reduces oracle label requests by up to 35%.
Paper addresses online alignment of large language models under uncertain preference feedback.
problem Online alignment of large language models with misspecified preference feedback.
method Formulates an oracle-robust objective as a worst-case optimization problem for log-linear policies, and develops projected stochastic composite updates.
result Shows that the robust objective admits an exact closed-form decomposition and achieves oracle complexity.
We consider the problem of minimizing the sum of submodular set functions assuming minimization oracles of each summand function. Most existing approaches reformulate the problem as the convex minimization of the sum of the corresponding Lovász extensions and the squared Euclidean norm, leading to algorithms requiring …
Algorithm solves online binary classification and infinite games using ERM oracle.
problem Online learning and solving infinite games with computationally inefficient oracles.
method Proposes an algorithm relying solely on ERM oracle calls for online binary classification and nonparametric games.
result Achieves finite and sublinearly growing regret in various settings.
The lasso and related sparsity inducing algorithms have been the target of substantial theoretical and applied research. Correspondingly, many results are known about their behavior for a fixed or optimally chosen tuning parameter specified up to unknown constants. In practice, however, this oracle tuning parameter is …
Vanilla GANs are connected to Wasserstein distance for better understanding.
problem Understanding the statistical properties of Vanilla GANs.
method Connecting Vanilla GANs to Wasserstein distance and proving an oracle inequality.
result An oracle inequality for Vanilla GANs in Wasserstein distance is obtained.
New algorithm learns efficiently with a simple 'yes/no' oracle.
problem Can efficient learning be achieved with a simpler oracle than ERM?
method Developed an oracle that returns 'yes' or 'no' for realizable datasets.
result Learnability is possible with a polynomial price in VC dimension.
New study shows Gaussian samplers struggle with heavy-tailed targets, while stable samplers excel.
problem The difficulty of sampling from heavy-tailed distributions using Gaussian versus stable oracles.
method Comparison of Gaussian and stable oracles for proximal samplers.
result Gaussian samplers have a fundamental barrier for high-accuracy guarantees in heavy-tailed sampling, while stable samplers excel.
Average Oracle outperforms DCC+NLS in portfolio optimization.
problem Optimizing portfolio performance in volatile markets.
method Comparing the Average Oracle to various DCC+NLS variants.
result The Average Oracle consistently yields higher Sharpe ratios.
Lower Complexity Bounds for Nonconvex-Strongly-Convex Bilevel Optimization with First-Order Oraclescs.LG
New lower bounds for bilevel optimization with first-order oracles.
problem Complexity of bilevel optimization with first-order oracles.
method Development of hard instances and proof of lower bounds.
result Nontrivial lower bounds for first-order zero-respecting algorithms.
The paper derives Cramer-Rao bounds for Laplacian matrix estimation under various constraints.
problem Estimating Laplacian matrices with structural constraints and sparsity.
method Linear reparametrization and closed-form expressions for Cramer-Rao bounds tailored to Laplacian matrix estimation.
result The derived CRBs provide performance limits for Laplacian matrix estimation and are validated in various applications.