Study recovers tree structure in noisy MRFs with support size 3 or more.
problem Learning tree-structured MRFs with symmetric noise.
method Characterized recoverability based on joint PMF, provided algorithm for recovery.
result Structure of leaf clusters can be partially or fully identifiable.
The Lasso performs well in ultra-sparse linear models with finite support size.
problem Performance analysis of Lasso in ultra-sparse linear models.
method Novel application of replica method from statistical physics, rigorous analysis of average case performance.
result Average performance of Lasso assessed without scaling assumptions, offering sample complexity bounds.
New estimators amplify data, achieving plug-in accuracy with fewer samples.
problem Efficiently estimating distribution properties with minimal data.
method Linear-time computable estimators that amplify data.
result Achieve plug-in accuracy with n samples, compared to nlogn for empirical estimators. PAC learning sample complexity is decidable with finite support bounds.
problem Determining the exact sample complexity for PAC learning concepts.
method Observation and proof of decidability with a-priori bounds.
result Sample complexity can be exactly determined for various concepts with finite support bounds.
Distributionally robust optimization (DRO) problems are increasingly seen as a viable method to train machine learning models for improved model generalization. These min-max formulations, however, are more difficult to solve. We therefore provide a new stochastic gradient descent algorithm to efficiently solve this DR…
New interior-point method tackles Wasserstein barycenter problem efficiently.
problem Computing Wasserstein barycenter for large support measures.
method Adapted interior-point method exploiting problem's matrix structure.
result Achieves a well-balanced tradeoff between accuracy and speed.
New algorithms improve distributional TD learning with linear approximations.
problem Estimating return distributions in reinforcement learning.
method Fine-grained analysis of linear-categorical Bellman equation, variance reduction techniques.
result Tight sample complexity bounds for distributional TD learning with linear approximations.
Proposes efficient bounds for causal effect estimation under weak confounding.
problem Estimating causal effects with weakly confounded variables.
method Develops an efficient linear program to derive upper and lower bounds on causal effect under small entropy of unobserved confounders.
result Bounds are consistent and tighter for weakly confounded variables.
New algorithms test independence with fewer samples by using predictive information.
problem Testing independence of distributions with limited samples.
method Augmented distribution testing framework that incorporates predictive information.
result Optimal sample complexity achieved, matching lower bounds.
The paper tackles adaptive targeting in networks with interference effects.
problem Adaptive targeting under network interference in a bandit setting.
method Linear model in a sparse regime, analyzing different levels of knowledge of the interference structure.
result Unified view of how knowledge of the interference structure affects online learning efficiency.
Study quantile multi-armed bandits for identifying the best arm with a specified quantile level.
problem Identifying the arm with the highest quantile in multi-armed bandits with private rewards.
method Proposed a (non-private) and differentially private successive elimination algorithms for best-arm identification.
result The proposed algorithms are essentially optimal for quantile bandit problems, with finite sample complexity even for distributions with infinite support-size.
We introduce a new method for estimating the support size of an unknown distribution which provably matches the performance bounds of the state-of-the-art techniques in the area and outperforms them in practice. In particular, we present both theoretical and computer simulation results that illustrate the utility and p…
Federated learning supports exact support recovery with minimal communication.
problem Learning the exact support of sparse linear regression in federated learning.
method One-shot communication algorithm for exact support recovery without optimization.
result Polynomial sample complexity and logarithmic number of clients required.
A new method for fast, accurate cross-validation in high dimensions.
problem Efficiently approximating cross-validation in high-dimensional settings.
method A novel approximation method that works well in high dimensions, especially for sparse parameters.
result One approximation method performs well in high dimensions, with running time and error dependent on the support size.
New algorithm finds best subset in high-dimensional data models.
problem Finding the best subset of predictors in high-dimensional data models.
method Proposes a scalable algorithm using a generalized information criterion.
result Directly proves consistency and oracle property for the best-subset selection.
Algorithm learns near-optimal policies for reward-mixing MDPs with few latent contexts.
problem Episodic reinforcement learning in reward-mixing Markov decision processes with a few latent contexts.
method Sample-efficient algorithm EM^2 using higher-order method-of-moments approach.
result Provides an ε-optimal policy using O(ε^(-2) * S^d A^d * poly(H, Z)^d) episodes for arbitrary M ≥ 2.
This work optimizes signal estimation for sparse MRA with collision-free signals.
problem Recovering an unknown signal from repeated observations under cyclic isometries with high noise.
method Investigates minimax optimality for collision-free signals in the MRA model.
result The minimax optimal rate of estimation is \( \sigma^2/\sqrt{n} \) for sparse MRA.
This paper presents quantum and classical algorithms for approximate submodular function minimization.
problem Approximate minimization of submodular functions.
method Classical and quantum algorithms for submodular minimization, with a new quantum sampling method.
result Quantum algorithm for approximate submodular minimization with improved time complexity.
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.
The paper efficiently estimates parameters from truncated Gaussian and linear models.
problem Estimating parameters from truncated Gaussian and linear models.
method Minimizes finite population negative log-likelihood function with an l1-regularization term.
result Efficient estimation of parameters from truncated samples.
New findings show sparse signals in MRA model require fewer measurements than previously thought.
problem Learning an unknown signal from repeated noisy images under group actions.
method Enhanced probabilistic method and analysis of uniform uncertainty principles.
result Sparse signals exhibit intermediate σ4 sample complexity, improving over traditional σ2. New algorithm efficiently estimates symmetric properties using approximate PML.
problem Estimating symmetric properties of a distribution efficiently.
method Developed an algorithm to compute an approximate PML distribution in nearly linear time.
result Achieved nearly linear time universal plug-in estimator for all symmetric functions.
New algorithms learn MNL weights efficiently for any slate size.
problem Efficiently learn weights for MNL models given query access.
method Two algorithms: adaptive and non-adaptive, with specific query complexities.
result Optimal query complexities for both adaptive and non-adaptive cases.
We consider a sparse linear regression model Y=Xβ^{*}+W where X has a Gaussian entries, W is the noise vector with mean zero Gaussian entries, and β^{*} is a binary vector with support size (sparsity) k. Using a novel conditional second moment method we obtain a tight up to a multiplicative constant approximation of th…