Note: When clicking on a Digital Object Identifier (DOI) number, you will be taken to an external site maintained by the publisher.
Some full text articles may not yet be available without a charge during the embargo (administrative interval).
What is a DOI Number?
Some links on this page may take you to nonfederal websites. Their policies may differ from this site.

In many informationtheoretic channel coding problems, adding an input cost constraint to the operational setup amounts to restricting the optimization domain in the capacity formula. This paper shows that, in contrast to common belief, such a simple modification does not hold for the costconstrained (CC) wiretap channel (WTC). The secrecycapacity of the discrete memoryless (DM) WTC without cost constraints is described by a single auxiliary random variable. For the CC DMWTC, however, we show that two auxiliaries are necessary to achieve capacity. Specifically, we first derive the secrecycapacity formula, proving the direct part via superposition coding. Then, we provide anmore »Free, publiclyaccessible full text available January 1, 2023

Statistical divergences (SDs), which quantify the dissimilarity between probability distributions, are a basic constituent of statistical inference and machine learning. A modern method for estimating those divergences relies on parametrizing an empirical variational form by a neural network (NN) and optimizing over parameter space. Such neural estimators are abundantly used in practice, but corresponding performance guarantees are partial and call for further exploration. We establish nonasymptotic absolute error bounds for a neural estimator realized by a shallow NN, focusing on four popular 𝖿divergencesKullbackLeibler, chisquared, squared Hellinger, and total variation. Our analysis relies on nonasymptotic function approximation theorems and tools frommore »Free, publiclyaccessible full text available January 1, 2023

Statistical distances (SDs), which quantify the dissimilarity between probability distributions, are central to machine learning and statistics. A modern method for estimating such distances from data relies on parametrizing a variational form by a neural network (NN) and optimizing it. These estimators are abundantly used in practice, but corresponding performance guarantees are partial and call for further exploration. In particular, there seems to be a fundamental tradeoff between the two sources of error involved: approximation and estimation. While the former needs the NN class to be rich and expressive, the latter relies on controlling complexity. This paper explores this tradeoffmore »Free, publiclyaccessible full text available January 1, 2023

In many informationtheoretic channel coding prob lems, adding an input cost constraint to the operational setup amounts to restricting the optimization domain in the capacity formula. This paper shows that, in contrast to common belief, such a simple modification does not hold for the costconstrained (CC) wiretap channel (WTC). The secrecycapacity of the discrete memoryless (DM) WTC without cost constraints is described by a single auxiliary random variable. For the CC DMWTC, however, we show that two auxiliaries are necessary to achieve capacity. Specifically, we first derive the secrecycapacity formula, proving the direct part via superposition coding. Then, we providemore »

Statistical distances (SDs), which quantify the dissimilarity between probability distri butions, are central to machine learning and statistics. A modern method for esti mating such distances from data relies on parametrizing a variational form by a neu ral network (NN) and optimizing it. These estimators are abundantly used in prac tice, but corresponding performance guar antees are partial and call for further ex ploration. In particular, there seems to be a fundamental tradeoff between the two sources of error involved: approximation and estimation. While the former needs the NN class to be rich and expressive, the latter relies on controllingmore »

We consider the problem of softcovering with constant composition superposition codes and characterize the optimal softcovering exponent. A doubleexponential concentration bound for deviation of the exponent from its mean is also established. We demonstrate an application of the result to achieving the secrecycapacity region of a broadcast channel with confidential messages under a percodeword cost constraint. This generalizes the recent characterization of the wiretap channel secrecycapacity under an average cost constraint, highlighting the potential utility of the superposition softcovering result to the analysis of coding problems.

In offline reinforcement learning (RL), the goal is to learn a highly rewarding policy based solely on a dataset of historical interactions with the environment. The ability to train RL policies offline would greatly expand where RL can be applied, its data efficiency, and its experimental velocity. Prior work in offline RL has been confined almost exclusively to modelfree RL approaches. In this work, we present MOReL, an algorithmic framework for modelbased offline RL. This framework consists of two steps: (a) learning a pessimistic MDP (PMDP) using the offline dataset; (b) learning a nearoptimal policy in this PMDP. The learnedmore »

Minimax optimal convergence rates for numerous classes of stochastic convex optimization problems are well characterized, where the majority of results utilize iterate averaged stochastic gradient descent (SGD) with polynomially decaying step sizes. In contrast, the behavior of SGD’s final iterate has received much less attention despite the widespread use in practice. Motivated by this observation, this work provides a detailed study of the following question: what rate is achievable using the final iterate of SGD for the streaming least squares regression problem with and without strong convexity? First, this work shows that even if the time horizon T (i.e. themore »

The ability to perform offline A/Btesting and offpolicy learning using logged contextual bandit feedback is highly desirable in a broad range of applications, including recommender systems, search engines, ad placement, and personalized health care. Both offline A/Btesting and offpolicy learning require a counterfactual estimator that evaluates how some new policy would have performed, if it had been used instead of the logging policy. In this paper, we present and analyze a family of counterfactual estimators which subsumes most estimators proposed to date. Most importantly, this analysis identifies a new estimator – called Continuous Adaptive Blending (CAB) – which enjoys manymore »

Given a matrix A∈ℝn×d and a vector b∈ℝd, we show how to compute an ϵapproximate solution to the regression problem minx∈ℝd12‖Ax−b‖22 in time Õ ((n+d⋅κsum‾‾‾‾‾‾‾√)⋅s⋅logϵ−1) where κsum=tr(A⊤A)/λmin(ATA) and s is the maximum number of nonzero entries in a row of A. Our algorithm improves upon the previous best running time of Õ ((n+n⋅κsum‾‾‾‾‾‾‾√)⋅s⋅logϵ−1). We achieve our result through a careful combination of leverage score sampling techniques, proximal point methods, and accelerated coordinate descent. Our method not only matches the performance of previous methods, but further improves whenever leverage scores of rows are small (up to polylogarithmic factors). We also providemore »