
A Lower Bound for the Sample Complexity of Inverse Reinforcement Learning
Inverse reinforcement learning (IRL) is the task of finding a reward fun...
read it

InformationTheoretic Bounds for Integral Estimation
In this paper, we consider a zeroorder stochastic oracle model of estim...
read it

Fair Sparse Regression with Clustering: An Invex Relaxation for a Combinatorial Problem
In this paper, we study the problem of fair sparse regression on a biase...
read it

A Simple Unified Framework for High Dimensional Bandit Problems
Stochastic high dimensional bandit problems with low dimensional structu...
read it

On the Fundamental Limits of Exact Inference in Structured Prediction
Inference is a main task in structured prediction and it is naturally mo...
read it

A Thorough View of Exact Inference in Graphs from the Degree4 SumofSquares Hierarchy
Performing inference in graphs is a common task within several machine l...
read it

Inverse Reinforcement Learning in the Continuous Setting with Formal Guarantees
Inverse Reinforcement Learning (IRL) is the problem of finding a reward ...
read it

Information Theoretic Limits of Exact Recovery in Subhypergraph Models for Community Detection
In this paper, we study the information theoretic bounds for exact recov...
read it

Randomized Deep Structured Prediction for DiscourseLevel Processing
Expressive text encoders such as RNNs and Transformer Networks have been...
read it

PrivSyn: Differentially Private Data Synthesis
In differential privacy (DP), a challenging problem is to generate synth...
read it

Information Theoretic Sample Complexity Lower Bound for FeedForward FullyConnected Deep Networks
In this paper, we study the sample complexity lower bound of a dlayer f...
read it

Fundamental Limits of Adversarial Learning
Robustness of machine learning methods is essential for modern practical...
read it

Fairness constraints can help exact inference in structured prediction
Many inference problems in structured prediction can be modeled as maxim...
read it

Support Union Recovery in Meta Learning of Gaussian Graphical Models
In this paper we study Meta learning of Gaussian graphical models. In ou...
read it

Exact Support Recovery in Federated Regression with Oneshot Communication
Federated learning provides a framework to address the challenges of dis...
read it

Exact Partitioning of Highorder Planted Models with a Tensor Nuclear Norm Constraint
We study the problem of efficient exact partitioning of the hypergraphs ...
read it

Provable Sample Complexity Guarantees for Learning of ContinuousAction Graphical Games with Nonparametric Utilities
In this paper, we study the problem of learning the exact structure of c...
read it

InformationTheoretic Lower Bounds for ZeroOrder Stochastic Gradient Estimation
In this paper we analyze the necessary number of samples to estimate the...
read it

First Order Methods take Exponential Time to Converge to Global Minimizers of NonConvex Functions
Machine learning algorithms typically perform optimization over a class ...
read it

Novel Change of Measure Inequalities and PACBayesian Bounds
PACBayesian theory has received a growing attention in the machine lear...
read it

The Sample Complexity of Meta Sparse Regression
This paper addresses the metalearning problem in sparse linear regressi...
read it

Provable Computational and Statistical Guarantees for Efficient Learning of ContinuousAction Graphical Games
In this paper, we study the problem of learning the set of pure strategy...
read it

Exact Partitioning of Highorder Models with a Novel Convex Tensor Cone Relaxation
In this paper we propose the first correct polytime algorithm for exact...
read it

Direct Estimation of Difference Between Structural Equation Models in High Dimensions
Discovering causeeffect relationships between variables from observatio...
read it

Exact inference in structured prediction
Structured prediction can be thought of as a simultaneous prediction of ...
read it

Minimax bounds for structured prediction
Structured prediction can be considered as a generalization of many stan...
read it

On the Correctness and Sample Complexity of Inverse Reinforcement Learning
Inverse reinforcement learning (IRL) is the problem of finding a reward ...
read it

Learning Bayesian Networks with Low Rank Conditional Probability Tables
In this paper, we provide a method to learn the directed structure of a ...
read it

On the Statistical Efficiency of Optimal Kernel Sum Classifiers
We propose a novel combination of optimization tools with learning theor...
read it

Information Theoretic Limits for Standard and OneBit Compressed Sensing with GraphStructured Sparsity
In this paper, we analyze the information theoretic lower bound on the n...
read it

Statistically and Computationally Efficient Variance Estimator for Kernel Ridge Regression
In this paper, we propose a random projection approach to estimate varia...
read it

Learning latent variable structured prediction models with Gaussian perturbations
The standard marginbased structured prediction commonly uses a maximum ...
read it

Learning MaximumAPosteriori Perturbation Models for Structured Prediction in Polynomial Time
MAP perturbation models have emerged as a powerful framework for inferen...
read it

Regularized Loss Minimizers with Local Data Obfuscation
While data privacy has been studied for more than a decade, it is still ...
read it

Learning Binary Bayesian Networks in Polynomial Time and Sample Complexity
We consider the problem of structure learning for binary Bayesian networ...
read it

Informationtheoretic Limits for Community Detection in Network Models
We analyze the informationtheoretic limits for the recovery of node lab...
read it

On the Sample Complexity of Learning from a Sequence of Experiments
We analyze the sample complexity of a new problem: learning from a seque...
read it

The Error Probability of Random Fourier Features is Dimensionality Independent
We show that the error probability of reconstructing kernel matrices fro...
read it

Learning linear structural equation models in polynomial time and sample complexity
The problem of learning structural equation models (SEMs) from data is a...
read it

Learning causal Bayes networks using interventional path queries in polynomial time and sample complexity
Causal discovery from empirical data is a fundamental problem in many sc...
read it

On the Statistical Efficiency of Compositional Nonparametric Prediction
In this paper, we propose a compositional nonparametric method in which ...
read it

Learning Identifiable Gaussian Bayesian Networks in Polynomial Time and Sample Complexity
Learning the directed acyclic graph (DAG) structure of a Bayesian networ...
read it

Information Theoretic Limits for Linear Prediction with GraphStructured Sparsity
We analyze the necessary number of samples for sparse vector recovery in...
read it

From Behavior to Sparse Graphical Games: Efficient Recovery of Equilibria
In this paper we study the problem of exact recovery of the purestrateg...
read it

InformationTheoretic Lower Bounds for Recovery of Diffusion Network Structures
We study the informationtheoretic lower bound of the sample complexity ...
read it

Informationtheoretic limits of Bayesian network structure learning
In this paper, we study the informationtheoretic limits of learning the...
read it

On the Sample Complexity of Learning Graphical Games
We analyze the sample complexity of learning graphical games from purely...
read it

Structured Prediction: From Gaussian Perturbations to LinearTime Principled Algorithms
Marginbased structured prediction commonly uses a maximum loss over all...
read it

Inverse Covariance Estimation for HighDimensional Data in Linear Time and Space: Spectral Methods for Riccati and Sparse Models
We propose maximum likelihood estimation for learning Gaussian graphical...
read it

On the Statistical Efficiency of ℓ_1,p MultiTask Learning of Gaussian Graphical Models
In this paper, we present ℓ_1,p multitask structure learning for Gaussi...
read it