<?xml version="1.0" encoding="UTF-8"?>
 <rdf:RDF xmlns="http://purl.org/rss/1.0/" xmlns:rdf="http://www.w3.org/1999/02/22-rdf-syntax-ns#" xmlns:content="http://purl.org/rss/1.0/modules/content/" xmlns:taxo="http://purl.org/rss/1.0/modules/taxonomy/" xmlns:dc="http://purl.org/dc/elements/1.1/" xmlns:cc="http://web.resource.org/cc/" xmlns:syn="http://purl.org/rss/1.0/modules/syndication/" xmlns:admin="http://webns.net/mvcb/">
  <channel rdf:about="http://pinboard.in">
    <title>Pinboard (mraginsky)</title>
    <link>https://pinboard.in/u:mraginsky/public/</link>
    <description>recent bookmarks from mraginsky</description>
    <items>
      <rdf:Seq>	<rdf:li rdf:resource="https://arxiv.org/abs/2510.15464"/>
	<rdf:li rdf:resource="https://openreview.net/forum?id=FGTDe6EA0B&amp;referrer=%5Bthe%20profile%20of%20Jon%20Kleinberg%5D(%2Fprofile%3Fid%3D~Jon_Kleinberg3)"/>
	<rdf:li rdf:resource="https://arxiv.org/abs/2411.01836"/>
	<rdf:li rdf:resource="https://arxiv.org/abs/2212.13881"/>
	<rdf:li rdf:resource="https://arxiv.org/abs/2301.06632"/>
	<rdf:li rdf:resource="https://arxiv.org/abs/2206.04030"/>
	<rdf:li rdf:resource="https://arxiv.org/abs/2205.14027"/>
	<rdf:li rdf:resource="https://arxiv.org/abs/2106.10717"/>
	<rdf:li rdf:resource="https://www.jmlr.org/papers/v23/20-1165.html"/>
	<rdf:li rdf:resource="https://arxiv.org/abs/1802.03620"/>
	<rdf:li rdf:resource="https://arxiv.org/abs/1805.04625"/>
	<rdf:li rdf:resource="https://arxiv.org/abs/1804.01619"/>
	<rdf:li rdf:resource="https://arxiv.org/abs/1502.03520"/>
	<rdf:li rdf:resource="http://arxiv.org/abs/1508.04095"/>
	<rdf:li rdf:resource="http://arxiv.org/abs/1510.02190"/>
	<rdf:li rdf:resource="http://arxiv.org/abs/1507.02803"/>
	<rdf:li rdf:resource="http://arxiv.org/abs/1507.02564"/>
	<rdf:li rdf:resource="http://arxiv.org/abs/1410.0503"/>
	<rdf:li rdf:resource="http://arxiv.org/abs/1305.4696"/>
	<rdf:li rdf:resource="http://arxiv.org/abs/1305.4548"/>
	<rdf:li rdf:resource="http://arxiv.org/abs/1212.3866"/>
	<rdf:li rdf:resource="http://arxiv.org/abs/1011.1716"/>
	<rdf:li rdf:resource="http://arxiv.org/abs/1207.3265"/>
	<rdf:li rdf:resource="http://arxiv.org/abs/1203.4626"/>
	<rdf:li rdf:resource="http://arxiv.org/abs/1007.1033"/>
	<rdf:li rdf:resource="http://ieeexplore.ieee.org/xpls/abs_all.jsp?arnumber=5961831"/>
	<rdf:li rdf:resource="http://ieeexplore.ieee.org/xpls/abs_all.jsp?arnumber=5961844"/>
	<rdf:li rdf:resource="http://ieeexplore.ieee.org/xpls/abs_all.jsp?arnumber=5961853"/>
	<rdf:li rdf:resource="http://ieeexplore.ieee.org/xpls/abs_all.jsp?arnumber=5895067"/>
	<rdf:li rdf:resource="http://ieeexplore.ieee.org/xpls/abs_all.jsp?arnumber=5895099"/>
	<rdf:li rdf:resource="http://ita.ucsd.edu/workshop/11/files/paper/paper_374.pdf"/>
	<rdf:li rdf:resource="http://ieeexplore.ieee.org/xpls/abs_all.jsp?arnumber=5730571"/>
	<rdf:li rdf:resource="http://arxiv.org/abs/1011.2952"/>
	<rdf:li rdf:resource="http://arxiv.org/abs/1001.4448"/>
	<rdf:li rdf:resource="http://arxiv.org/abs/1002.0042"/>
      </rdf:Seq>
    </items>
  </channel><item rdf:about="https://arxiv.org/abs/2510.15464">
    <title>[2510.15464] Learning to Answer from Correct Demonstrations</title>
    <dc:date>2026-05-11T19:34:28+00:00</dc:date>
    <link>https://arxiv.org/abs/2510.15464</link>
    <dc:creator>mraginsky</dc:creator><description><![CDATA[We study the problem of learning to generate an answer (or completion) to a question (or prompt), where there could be multiple correct answers, any one of which is acceptable at test time. Learning is based on demonstrations of some correct answer to each training question, as in Supervised Fine Tuning (SFT). We formalize the problem as imitation learning (i.e., apprenticeship learning) in contextual bandits, with offline demonstrations from some expert (optimal, or very good) policy, without explicitly observed rewards. In contrast to prior work, which assumes the demonstrator belongs to a bounded-complexity policy class, we propose relying only on the underlying reward model (i.e., specifying which answers are correct) being in a bounded-complexity class, which we argue is a strictly weaker assumption. We show that likelihood-maximization methods can fail in this setting, and instead present an approach that learns to answer nearly as well as the demonstrator, with sample complexity logarithmic in the cardinality of the reward class. Our method is similar to Syed and Schapire 2007, when adapted to a contextual bandit (i.e., single step) setup, but is a simple one-pass online approach that enjoys an "optimistic rate" (i.e., $1/\varepsilon$ when the demonstrator is optimal, versus $1/\varepsilon^2$ in Syed and Schapire), and works even with arbitrarily adaptive demonstrations. ]]></description>
<dc:subject>papers to-read heard-the-talk large-language-models machine-learning</dc:subject>
<dc:source>https://pinboard.in/</dc:source>
<dc:identifier>https://pinboard.in/u:mraginsky/b:f5836b2d0d6b/</dc:identifier>
<taxo:topics><rdf:Bag>	<rdf:li rdf:resource="https://pinboard.in/u:mraginsky/t:papers"/>
	<rdf:li rdf:resource="https://pinboard.in/u:mraginsky/t:to-read"/>
	<rdf:li rdf:resource="https://pinboard.in/u:mraginsky/t:heard-the-talk"/>
	<rdf:li rdf:resource="https://pinboard.in/u:mraginsky/t:large-language-models"/>
	<rdf:li rdf:resource="https://pinboard.in/u:mraginsky/t:machine-learning"/>
</rdf:Bag></taxo:topics>
</item>
<item rdf:about="https://openreview.net/forum?id=FGTDe6EA0B&amp;referrer=%5Bthe%20profile%20of%20Jon%20Kleinberg%5D(%2Fprofile%3Fid%3D~Jon_Kleinberg3)">
    <title>Language Generation in the Limit | OpenReview</title>
    <dc:date>2026-04-24T20:43:14+00:00</dc:date>
    <link>https://openreview.net/forum?id=FGTDe6EA0B&amp;referrer=%5Bthe%20profile%20of%20Jon%20Kleinberg%5D(%2Fprofile%3Fid%3D~Jon_Kleinberg3)</link>
    <dc:creator>mraginsky</dc:creator><description><![CDATA[Although current large language models are complex, the most basic specifications of the underlying language generation problem itself are simple to state: given a finite set of training samples from an unknown language, produce valid new strings from the language that don't already appear in the training data. Here we ask what we can conclude about language generation using only this specification, without further assumptions. In particular, suppose that an adversary enumerates the strings of an unknown target language L that is known only to come from one of a possibly infinite list of candidates. A computational agent is trying to learn to generate from this language; we say that the agent generates from in the limit if after some finite point in the enumeration of , the agent is able to produce new elements that come exclusively from and that have not yet been presented by the adversary. Our main result is that there is an agent that is able to generate in the limit for every countable list of candidate languages. This contrasts dramatically with negative results due to Gold and Angluin in a well-studied model of language learning where the goal is to identify an unknown language from samples; the difference between these results suggests that identifying a language is a fundamentally different problem than generating from it.]]></description>
<dc:subject>papers to-read heard-the-talk language generative-models computer-science</dc:subject>
<dc:source>https://pinboard.in/</dc:source>
<dc:identifier>https://pinboard.in/u:mraginsky/b:cf4b581b7488/</dc:identifier>
<taxo:topics><rdf:Bag>	<rdf:li rdf:resource="https://pinboard.in/u:mraginsky/t:papers"/>
	<rdf:li rdf:resource="https://pinboard.in/u:mraginsky/t:to-read"/>
	<rdf:li rdf:resource="https://pinboard.in/u:mraginsky/t:heard-the-talk"/>
	<rdf:li rdf:resource="https://pinboard.in/u:mraginsky/t:language"/>
	<rdf:li rdf:resource="https://pinboard.in/u:mraginsky/t:generative-models"/>
	<rdf:li rdf:resource="https://pinboard.in/u:mraginsky/t:computer-science"/>
</rdf:Bag></taxo:topics>
</item>
<item rdf:about="https://arxiv.org/abs/2411.01836">
    <title>[2411.01836] Some easy optimization problems have the overlap-gap property</title>
    <dc:date>2025-01-20T02:42:06+00:00</dc:date>
    <link>https://arxiv.org/abs/2411.01836</link>
    <dc:creator>mraginsky</dc:creator><description><![CDATA[We show that the shortest s-t path problem has the overlap-gap property in (i) sparse G(n,p) graphs and (ii) complete graphs with i.i.d. Exponential edge weights. Furthermore, we demonstrate that in sparse G(n,p) graphs, shortest path is solved by O(logn)-degree polynomial estimators, and a uniform approximate shortest path can be sampled in polynomial time. This constitutes the first example in which the overlap-gap property is not predictive of algorithmic intractability for a (non-algebraic) average-case optimization problem. ]]></description>
<dc:subject>papers to-read heard-the-talk computational-complexity optimization random-graphs dynamic-programming</dc:subject>
<dc:source>https://pinboard.in/</dc:source>
<dc:identifier>https://pinboard.in/u:mraginsky/b:b5073430f125/</dc:identifier>
<taxo:topics><rdf:Bag>	<rdf:li rdf:resource="https://pinboard.in/u:mraginsky/t:papers"/>
	<rdf:li rdf:resource="https://pinboard.in/u:mraginsky/t:to-read"/>
	<rdf:li rdf:resource="https://pinboard.in/u:mraginsky/t:heard-the-talk"/>
	<rdf:li rdf:resource="https://pinboard.in/u:mraginsky/t:computational-complexity"/>
	<rdf:li rdf:resource="https://pinboard.in/u:mraginsky/t:optimization"/>
	<rdf:li rdf:resource="https://pinboard.in/u:mraginsky/t:random-graphs"/>
	<rdf:li rdf:resource="https://pinboard.in/u:mraginsky/t:dynamic-programming"/>
</rdf:Bag></taxo:topics>
</item>
<item rdf:about="https://arxiv.org/abs/2212.13881">
    <title>[2212.13881] Feature learning in neural networks and kernel machines that recursively learn features</title>
    <dc:date>2023-01-18T09:06:41+00:00</dc:date>
    <link>https://arxiv.org/abs/2212.13881</link>
    <dc:creator>mraginsky</dc:creator><description><![CDATA[Neural networks have achieved impressive results on many technological and scientific tasks. Yet, their empirical successes have outpaced our fundamental understanding of their structure and function. By identifying mechanisms driving the successes of neural networks, we can provide principled approaches for improving neural network performance and develop simple and effective alternatives. In this work, we isolate the key mechanism driving feature learning in fully connected neural networks by connecting neural feature learning to the average gradient outer product. We subsequently leverage this mechanism to design \textit{Recursive Feature Machines} (RFMs), which are kernel machines that learn features. We show that RFMs (1) accurately capture features learned by deep fully connected neural networks, (2) close the gap between kernel machines and fully connected networks, and (3) surpass a broad spectrum of models including neural networks on tabular data. Furthermore, we demonstrate that RFMs shed light on recently observed deep learning phenomena such as grokking, lottery tickets, simplicity biases, and spurious features. We provide a Python implementation to make our method broadly accessible]]></description>
<dc:subject>papers to-read heard-the-talk neural-networks machine-learning kernel-methods</dc:subject>
<dc:source>https://pinboard.in/</dc:source>
<dc:identifier>https://pinboard.in/u:mraginsky/b:5f1686d94805/</dc:identifier>
<taxo:topics><rdf:Bag>	<rdf:li rdf:resource="https://pinboard.in/u:mraginsky/t:papers"/>
	<rdf:li rdf:resource="https://pinboard.in/u:mraginsky/t:to-read"/>
	<rdf:li rdf:resource="https://pinboard.in/u:mraginsky/t:heard-the-talk"/>
	<rdf:li rdf:resource="https://pinboard.in/u:mraginsky/t:neural-networks"/>
	<rdf:li rdf:resource="https://pinboard.in/u:mraginsky/t:machine-learning"/>
	<rdf:li rdf:resource="https://pinboard.in/u:mraginsky/t:kernel-methods"/>
</rdf:Bag></taxo:topics>
</item>
<item rdf:about="https://arxiv.org/abs/2301.06632">
    <title>[2301.06632] Asymptotic normality and optimality in nonsmooth stochastic approximation</title>
    <dc:date>2023-01-18T09:05:44+00:00</dc:date>
    <link>https://arxiv.org/abs/2301.06632</link>
    <dc:creator>mraginsky</dc:creator><description><![CDATA[In their seminal work, Polyak and Juditsky showed that stochastic approximation algorithms for solving smooth equations enjoy a central limit theorem. Moreover, it has since been argued that the asymptotic covariance of the method is best possible among any estimation procedure in a local minimax sense of Hájek and Le Cam. A long-standing open question in this line of work is whether similar guarantees hold for important non-smooth problems, such as stochastic nonlinear programming or stochastic variational inequalities. In this work, we show that this is indeed the case. ]]></description>
<dc:subject>papers to-read heard-the-talk optimization dynamical-systems nonsmooth-geometry stratification-theory</dc:subject>
<dc:source>https://pinboard.in/</dc:source>
<dc:identifier>https://pinboard.in/u:mraginsky/b:c9232da98331/</dc:identifier>
<taxo:topics><rdf:Bag>	<rdf:li rdf:resource="https://pinboard.in/u:mraginsky/t:papers"/>
	<rdf:li rdf:resource="https://pinboard.in/u:mraginsky/t:to-read"/>
	<rdf:li rdf:resource="https://pinboard.in/u:mraginsky/t:heard-the-talk"/>
	<rdf:li rdf:resource="https://pinboard.in/u:mraginsky/t:optimization"/>
	<rdf:li rdf:resource="https://pinboard.in/u:mraginsky/t:dynamical-systems"/>
	<rdf:li rdf:resource="https://pinboard.in/u:mraginsky/t:nonsmooth-geometry"/>
	<rdf:li rdf:resource="https://pinboard.in/u:mraginsky/t:stratification-theory"/>
</rdf:Bag></taxo:topics>
</item>
<item rdf:about="https://arxiv.org/abs/2206.04030">
    <title>[2206.04030] High-dimensional limit theorems for SGD: Effective dynamics and critical scaling</title>
    <dc:date>2023-01-16T09:27:07+00:00</dc:date>
    <link>https://arxiv.org/abs/2206.04030</link>
    <dc:creator>mraginsky</dc:creator><description><![CDATA[We study the scaling limits of stochastic gradient descent (SGD) with constant step-size in the high-dimensional regime. We prove limit theorems for the trajectories of summary statistics (i.e., finite-dimensional functions) of SGD as the dimension goes to infinity. Our approach allows one to choose the summary statistics that are tracked, the initialization, and the step-size. It yields both ballistic (ODE) and diffusive (SDE) limits, with the limit depending dramatically on the former choices. We show a critical scaling regime for the step-size, below which the effective ballistic dynamics matches gradient flow for the population loss, but at which, a new correction term appears which changes the phase diagram. About the fixed points of this effective dynamics, the corresponding diffusive limits can be quite complex and even degenerate. We demonstrate our approach on popular examples including estimation for spiked matrix and tensor models and classification via two-layer networks for binary and XOR-type Gaussian mixture models. These examples exhibit surprising phenomena including multimodal timescales to convergence as well as convergence to sub-optimal solutions with probability bounded away from zero from random (e.g., Gaussian) initializations. At the same time, we demonstrate the benefit of overparametrization by showing that the latter probability goes to zero as the second layer width grows. ]]></description>
<dc:subject>papers to-read heard-the-talk optimization dynamical-systems machine-learning gradient-flows</dc:subject>
<dc:source>https://pinboard.in/</dc:source>
<dc:identifier>https://pinboard.in/u:mraginsky/b:1e2cc35c0d94/</dc:identifier>
<taxo:topics><rdf:Bag>	<rdf:li rdf:resource="https://pinboard.in/u:mraginsky/t:papers"/>
	<rdf:li rdf:resource="https://pinboard.in/u:mraginsky/t:to-read"/>
	<rdf:li rdf:resource="https://pinboard.in/u:mraginsky/t:heard-the-talk"/>
	<rdf:li rdf:resource="https://pinboard.in/u:mraginsky/t:optimization"/>
	<rdf:li rdf:resource="https://pinboard.in/u:mraginsky/t:dynamical-systems"/>
	<rdf:li rdf:resource="https://pinboard.in/u:mraginsky/t:machine-learning"/>
	<rdf:li rdf:resource="https://pinboard.in/u:mraginsky/t:gradient-flows"/>
</rdf:Bag></taxo:topics>
</item>
<item rdf:about="https://arxiv.org/abs/2205.14027">
    <title>[2205.14027] Learning Dynamical Systems via Koopman Operator Regression in Reproducing Kernel Hilbert Spaces</title>
    <dc:date>2022-10-25T12:31:35+00:00</dc:date>
    <link>https://arxiv.org/abs/2205.14027</link>
    <dc:creator>mraginsky</dc:creator><description><![CDATA[    We study a class of dynamical systems modelled as Markov chains that admit an invariant distribution via the corresponding transfer, or Koopman, operator. While data-driven algorithms to reconstruct such operators are well known, their relationship with statistical learning is largely unexplored. We formalize a framework to learn the Koopman operator from finite data trajectories of the dynamical system. We consider the restriction of this operator to a reproducing kernel Hilbert space and introduce a notion of risk, from which different estimators naturally arise. We link the risk with the estimation of the spectral decomposition of the Koopman operator. These observations motivate a reduced-rank operator regression (RRR) estimator. We derive learning bounds for the proposed estimator, holding both in i.i.d. and non i.i.d. settings, the latter in terms of mixing coefficients. Our results suggest RRR might be beneficial over other widely used estimators as confirmed in numerical experiments both for forecasting and mode decomposition. 

]]></description>
<dc:subject>papers to-read heard-the-talk machine-learning kernel-methods dynamical-systems Koopman-operators</dc:subject>
<dc:source>https://pinboard.in/</dc:source>
<dc:identifier>https://pinboard.in/u:mraginsky/b:d99604a1f5bb/</dc:identifier>
<taxo:topics><rdf:Bag>	<rdf:li rdf:resource="https://pinboard.in/u:mraginsky/t:papers"/>
	<rdf:li rdf:resource="https://pinboard.in/u:mraginsky/t:to-read"/>
	<rdf:li rdf:resource="https://pinboard.in/u:mraginsky/t:heard-the-talk"/>
	<rdf:li rdf:resource="https://pinboard.in/u:mraginsky/t:machine-learning"/>
	<rdf:li rdf:resource="https://pinboard.in/u:mraginsky/t:kernel-methods"/>
	<rdf:li rdf:resource="https://pinboard.in/u:mraginsky/t:dynamical-systems"/>
	<rdf:li rdf:resource="https://pinboard.in/u:mraginsky/t:Koopman-operators"/>
</rdf:Bag></taxo:topics>
</item>
<item rdf:about="https://arxiv.org/abs/2106.10717">
    <title>[2106.10717] Optimal potentials for hedging algorithms</title>
    <dc:date>2022-10-25T12:12:07+00:00</dc:date>
    <link>https://arxiv.org/abs/2106.10717</link>
    <dc:creator>mraginsky</dc:creator><description><![CDATA[We study a family of potential functions for online learning. We show that if the potential function has strictly positive derivatives of order 1-4 then the min-max optimal strategy for the adversary is Brownian motion. Using that fact we analyze different potential functions and show that the Normal-Hedge potential provides the tightest upper bounds on the cumulative regret of the top {\epsilon}-percentile. ]]></description>
<dc:subject>papers to-read heard-the-talk online-learning game-theory SDEs</dc:subject>
<dc:source>https://pinboard.in/</dc:source>
<dc:identifier>https://pinboard.in/u:mraginsky/b:1f55d0ab96d4/</dc:identifier>
<taxo:topics><rdf:Bag>	<rdf:li rdf:resource="https://pinboard.in/u:mraginsky/t:papers"/>
	<rdf:li rdf:resource="https://pinboard.in/u:mraginsky/t:to-read"/>
	<rdf:li rdf:resource="https://pinboard.in/u:mraginsky/t:heard-the-talk"/>
	<rdf:li rdf:resource="https://pinboard.in/u:mraginsky/t:online-learning"/>
	<rdf:li rdf:resource="https://pinboard.in/u:mraginsky/t:game-theory"/>
	<rdf:li rdf:resource="https://pinboard.in/u:mraginsky/t:SDEs"/>
</rdf:Bag></taxo:topics>
</item>
<item rdf:about="https://www.jmlr.org/papers/v23/20-1165.html">
    <title>Approximate Information State for Approximate Planning and Reinforcement Learning in Partially Observed Systems</title>
    <dc:date>2022-03-24T19:51:42+00:00</dc:date>
    <link>https://www.jmlr.org/papers/v23/20-1165.html</link>
    <dc:creator>mraginsky</dc:creator><description><![CDATA[We propose a theoretical framework for approximate planning and learning in partially observed systems. Our framework is based on the fundamental notion of information state. We provide two definitions of information state---i) a function of history which is sufficient to compute the expected reward and predict its next value; ii) a function of the history which can be recursively updated and is sufficient to compute the expected reward and predict the next observation. An information state always leads to a dynamic programming decomposition. Our key result is to show that if a function of the history (called AIS) approximately satisfies the properties of the information state, then there is a corresponding approximate dynamic program. We show that the policy computed using this is approximately optimal with bounded loss of optimality. We show that several approximations in state, observation and action spaces in literature can be viewed as instances of AIS. In some of these cases, we obtain tighter bounds. A salient feature of AIS is that it can be learnt from data. We present AIS based multi-time scale policy gradient algorithms and detailed numerical experiments with low, moderate and high dimensional environments. ]]></description>
<dc:subject>papers to-read reinforcement-learning dynamic-programming control-theory heard-the-talk</dc:subject>
<dc:source>https://pinboard.in/</dc:source>
<dc:identifier>https://pinboard.in/u:mraginsky/b:50e2a0f7f6dd/</dc:identifier>
<taxo:topics><rdf:Bag>	<rdf:li rdf:resource="https://pinboard.in/u:mraginsky/t:papers"/>
	<rdf:li rdf:resource="https://pinboard.in/u:mraginsky/t:to-read"/>
	<rdf:li rdf:resource="https://pinboard.in/u:mraginsky/t:reinforcement-learning"/>
	<rdf:li rdf:resource="https://pinboard.in/u:mraginsky/t:dynamic-programming"/>
	<rdf:li rdf:resource="https://pinboard.in/u:mraginsky/t:control-theory"/>
	<rdf:li rdf:resource="https://pinboard.in/u:mraginsky/t:heard-the-talk"/>
</rdf:Bag></taxo:topics>
</item>
<item rdf:about="https://arxiv.org/abs/1802.03620">
    <title>[1802.03620] Optimal approximation of continuous functions by very deep ReLU networks</title>
    <dc:date>2018-07-08T14:25:12+00:00</dc:date>
    <link>https://arxiv.org/abs/1802.03620</link>
    <dc:creator>mraginsky</dc:creator><dc:subject>papers to-read neural-networks approximation-theory heard-the-talk</dc:subject>
<dc:source>https://pinboard.in/</dc:source>
<dc:identifier>https://pinboard.in/u:mraginsky/b:952b5767e0bd/</dc:identifier>
<taxo:topics><rdf:Bag>	<rdf:li rdf:resource="https://pinboard.in/u:mraginsky/t:papers"/>
	<rdf:li rdf:resource="https://pinboard.in/u:mraginsky/t:to-read"/>
	<rdf:li rdf:resource="https://pinboard.in/u:mraginsky/t:neural-networks"/>
	<rdf:li rdf:resource="https://pinboard.in/u:mraginsky/t:approximation-theory"/>
	<rdf:li rdf:resource="https://pinboard.in/u:mraginsky/t:heard-the-talk"/>
</rdf:Bag></taxo:topics>
</item>
<item rdf:about="https://arxiv.org/abs/1805.04625">
    <title>[1805.04625] Strong Converse using Change of Measure Arguments</title>
    <dc:date>2018-07-08T14:24:17+00:00</dc:date>
    <link>https://arxiv.org/abs/1805.04625</link>
    <dc:creator>mraginsky</dc:creator><description><![CDATA[The strong converse for a coding theorem shows that the optimal asymptotic rate possible with vanishing error cannot be improved by allowing a fixed error. Building on a method introduced by Gu and Effros for centralized coding problems, we develop a general and simple recipe for proving strong converse that is applicable for distributed problems as well. Heuristically, our proof of strong converse mimics the standard steps for proving a weak converse, except that we apply those steps to a modified distribution obtained by conditioning the original distribution on the event that no error occurs. A key component of our recipe is the replacement of the hard Markov constraints implied by the distributed nature of the problem with a soft information cost using a variational formula introduced by Oohama. We illustrate our method by providing a short proof of the strong converse for the Wyner-Ziv problem and new strong converse theorems for interactive function computation, common randomness and secret key agreement, and the wiretap channel. ]]></description>
<dc:subject>papers to-read heard-the-talk information-theory lower-bounds</dc:subject>
<dc:source>https://pinboard.in/</dc:source>
<dc:identifier>https://pinboard.in/u:mraginsky/b:cf489de5601a/</dc:identifier>
<taxo:topics><rdf:Bag>	<rdf:li rdf:resource="https://pinboard.in/u:mraginsky/t:papers"/>
	<rdf:li rdf:resource="https://pinboard.in/u:mraginsky/t:to-read"/>
	<rdf:li rdf:resource="https://pinboard.in/u:mraginsky/t:heard-the-talk"/>
	<rdf:li rdf:resource="https://pinboard.in/u:mraginsky/t:information-theory"/>
	<rdf:li rdf:resource="https://pinboard.in/u:mraginsky/t:lower-bounds"/>
</rdf:Bag></taxo:topics>
</item>
<item rdf:about="https://arxiv.org/abs/1804.01619">
    <title>[1804.01619] Stability and Convergence Trade-off of Iterative Optimization Algorithms</title>
    <dc:date>2018-04-17T02:44:40+00:00</dc:date>
    <link>https://arxiv.org/abs/1804.01619</link>
    <dc:creator>mraginsky</dc:creator><description><![CDATA[The overall performance or expected excess risk of an iterative machine learning algorithm can be decomposed into training error and generalization error. While the former is controlled by its convergence analysis, the latter can be tightly handled by algorithmic stability. The machine learning community has a rich history investigating convergence and stability separately. However, the question about the trade-off between these two quantities remains open. In this paper, we show that for any iterative algorithm at any iteration, the overall performance is lower bounded by the minimax statistical error over an appropriately chosen loss function class. This implies an important trade-off between convergence and stability of the algorithm -- a faster converging algorithm has to be less stable, and vice versa. As a direct consequence of this fundamental tradeoff, new convergence lower bounds can be derived for classes of algorithms constrained with different stability bounds. In particular, when the loss function is convex (or strongly convex) and smooth, we discuss the stability upper bounds of gradient descent (GD) and stochastic gradient descent and their variants with decreasing step sizes. For Nesterov's accelerated gradient descent (NAG) and heavy ball method (HB), we provide stability upper bounds for the quadratic loss function. Applying existing stability upper bounds for the gradient methods in our trade-off framework, we obtain lower bounds matching the well-established convergence upper bounds up to constants for these algorithms and conjecture similar lower bounds for NAG and HB. Finally, we numerically demonstrate the tightness of our stability bounds in terms of exponents in the rate and also illustrate via a simulated logistic regression problem that our stability bounds reflect the generalization errors better than the simple uniform convergence bounds for GD and NAG. ]]></description>
<dc:subject>papers to-read machine-learning optimization stability heard-the-talk</dc:subject>
<dc:source>https://pinboard.in/</dc:source>
<dc:identifier>https://pinboard.in/u:mraginsky/b:05eccbec22c8/</dc:identifier>
<taxo:topics><rdf:Bag>	<rdf:li rdf:resource="https://pinboard.in/u:mraginsky/t:papers"/>
	<rdf:li rdf:resource="https://pinboard.in/u:mraginsky/t:to-read"/>
	<rdf:li rdf:resource="https://pinboard.in/u:mraginsky/t:machine-learning"/>
	<rdf:li rdf:resource="https://pinboard.in/u:mraginsky/t:optimization"/>
	<rdf:li rdf:resource="https://pinboard.in/u:mraginsky/t:stability"/>
	<rdf:li rdf:resource="https://pinboard.in/u:mraginsky/t:heard-the-talk"/>
</rdf:Bag></taxo:topics>
</item>
<item rdf:about="https://arxiv.org/abs/1502.03520">
    <title>[1502.03520] RAND-WALK: A Latent Variable Model Approach to Word Embeddings</title>
    <dc:date>2017-02-28T16:32:15+00:00</dc:date>
    <link>https://arxiv.org/abs/1502.03520</link>
    <dc:creator>mraginsky</dc:creator><dc:subject>papers machine-learning representation-learning word-embeddings heard-the-talk</dc:subject>
<dc:source>https://pinboard.in/</dc:source>
<dc:identifier>https://pinboard.in/u:mraginsky/b:f724ed7b88f9/</dc:identifier>
<taxo:topics><rdf:Bag>	<rdf:li rdf:resource="https://pinboard.in/u:mraginsky/t:papers"/>
	<rdf:li rdf:resource="https://pinboard.in/u:mraginsky/t:machine-learning"/>
	<rdf:li rdf:resource="https://pinboard.in/u:mraginsky/t:representation-learning"/>
	<rdf:li rdf:resource="https://pinboard.in/u:mraginsky/t:word-embeddings"/>
	<rdf:li rdf:resource="https://pinboard.in/u:mraginsky/t:heard-the-talk"/>
</rdf:Bag></taxo:topics>
</item>
<item rdf:about="http://arxiv.org/abs/1508.04095">
    <title>[1508.04095] Algorithmic Aspects of Optimal Channel Coding</title>
    <dc:date>2016-07-12T09:16:48+00:00</dc:date>
    <link>http://arxiv.org/abs/1508.04095</link>
    <dc:creator>mraginsky</dc:creator><description><![CDATA[A central question in information theory is to determine the maximum success probability that can be achieved in sending a fixed number of messages over a noisy channel. This was first studied in the pioneering work of Shannon who established a simple expression characterizing this quantity in the limit of multiple independent uses of the channel. Here we consider the general setting with only one use of the channel. We observe that the maximum success probability can be expressed as the maximum value of a submodular function. Using this connection, we establish the following results: 
1. There is a simple greedy polynomial-time algorithm that computes a code achieving a (1-1/e)-approximation of the maximum success probability. Moreover, for this problem it is NP-hard to obtain an approximation ratio strictly better than (1-1/e). 
2. Shared quantum entanglement between the sender and the receiver can increase the success probability by a factor of at most 1/(1-1/e). In addition, this factor is tight if one allows an arbitrary non-signaling box between the sender and the receiver. 
3. We give tight bounds on the one-shot performance of the meta-converse of Polyanskiy-Poor-Verdu.]]></description>
<dc:subject>papers to-read information-theory channel-coding heard-the-talk</dc:subject>
<dc:source>https://pinboard.in/</dc:source>
<dc:identifier>https://pinboard.in/u:mraginsky/b:85457006c28d/</dc:identifier>
<taxo:topics><rdf:Bag>	<rdf:li rdf:resource="https://pinboard.in/u:mraginsky/t:papers"/>
	<rdf:li rdf:resource="https://pinboard.in/u:mraginsky/t:to-read"/>
	<rdf:li rdf:resource="https://pinboard.in/u:mraginsky/t:information-theory"/>
	<rdf:li rdf:resource="https://pinboard.in/u:mraginsky/t:channel-coding"/>
	<rdf:li rdf:resource="https://pinboard.in/u:mraginsky/t:heard-the-talk"/>
</rdf:Bag></taxo:topics>
</item>
<item rdf:about="http://arxiv.org/abs/1510.02190">
    <title>[1510.02190] Data compression with low distortion and finite blocklength</title>
    <dc:date>2015-10-10T05:09:45+00:00</dc:date>
    <link>http://arxiv.org/abs/1510.02190</link>
    <dc:creator>mraginsky</dc:creator><description><![CDATA[This paper considers lossy source coding of n-dimensional continuous memoryless sources with low mean-square error distortion and shows a simple, explicit approximation to the minimum source coding rate. More precisely, a nonasymptotic version of Shannon's lower bound is presented. Lattice quantizers are shown to approach that lower bound, provided that the source density is smooth enough and the distortion is low, which implies that fine multidimensional lattice coverings are nearly optimal in the rate-distortion sense even at finite n. The achievability proof technique avoids both the usual random coding argument and the simplifying assumption of the presence of a dither signal.]]></description>
<dc:subject>papers to-read heard-the-talk information-theory rate-distortion</dc:subject>
<dc:source>https://pinboard.in/</dc:source>
<dc:identifier>https://pinboard.in/u:mraginsky/b:41cad441378d/</dc:identifier>
<taxo:topics><rdf:Bag>	<rdf:li rdf:resource="https://pinboard.in/u:mraginsky/t:papers"/>
	<rdf:li rdf:resource="https://pinboard.in/u:mraginsky/t:to-read"/>
	<rdf:li rdf:resource="https://pinboard.in/u:mraginsky/t:heard-the-talk"/>
	<rdf:li rdf:resource="https://pinboard.in/u:mraginsky/t:information-theory"/>
	<rdf:li rdf:resource="https://pinboard.in/u:mraginsky/t:rate-distortion"/>
</rdf:Bag></taxo:topics>
</item>
<item rdf:about="http://arxiv.org/abs/1507.02803">
    <title>[1507.02803] Logarithmic Sobolev inequalities in discrete product spaces: a proof by a transportation cost distance</title>
    <dc:date>2015-07-13T20:03:35+00:00</dc:date>
    <link>http://arxiv.org/abs/1507.02803</link>
    <dc:creator>mraginsky</dc:creator><description><![CDATA[The aim of this paper is to prove an inequality between relative entropy and the sum of average conditional relative entropies of the following form: For a fixed probability measure $q^n$ on $\mathcal X^n$, ($\mathcal X$ is a finite set), and any probability measure $p^n=\mathcal L(Y^n)$ on $\mathcal X^n$, we have \begin{equation}\label{*} D(p^n||q^n)\leq Const. \sum_{i=1}^n \Bbb E_{p^n} D(p_i(\cdot|Y_1,\dots, Y_{i-1},Y_{i+1},\dots, Y_n) || q_i(\cdot|Y_1,\dots, Y_{i-1},Y_{i+1},\dots, Y_n)), \end{equation} where $p_i(\cdot|y_1,\dots, y_{i-1},y_{i+1},\dots, y_n)$ and $q_i(\cdot|x_1,\dots, x_{i-1},x_{i+1},\dots, x_n)$ denote the local specifications for $p^n$ resp. $q^n$. The constant shall depend on the properties of the local specifications of $q^n$. 
Inequality (*) is meaningful in product spaces, both in the discrete and the continuous case, and can be used to prove a logarithmic Sobolev inequality for $q^n$, provided uniform logarithmic Sobolev inequalities are available for $q_i(\cdot|x_1,\dots, x_{i-1},x_{i+1},\dots, x_n)$, for all fixed $i$ and all fixed $(x_1,\dots, x_{i-1},x_{i+1},\dots, x_n)$. Inequality (*) directly implies that the Gibbs sampler associated with $q^n$ is a contraction for relative entropy. 
We derive inequality (*), and thereby a logarithmic Sobolev inequality, in discrete product spaces, by proving inequalities for an appropriate Wasserstein-like distance. A logarithmic Sobolev inequality is, roughly speaking, a contractivity property of relative entropy with respect to some Markov semigroup. It is much easier to prove contractivity for a distance between measures than for relative entropy, since distances satisfy the triangle inequality, and for them well known linear tools, like estimates through matrix norms can be applied.]]></description>
<dc:subject>papers heard-the-talk measure-concentration probability have-read</dc:subject>
<dc:source>https://pinboard.in/</dc:source>
<dc:identifier>https://pinboard.in/u:mraginsky/b:0f7d5503f45a/</dc:identifier>
<taxo:topics><rdf:Bag>	<rdf:li rdf:resource="https://pinboard.in/u:mraginsky/t:papers"/>
	<rdf:li rdf:resource="https://pinboard.in/u:mraginsky/t:heard-the-talk"/>
	<rdf:li rdf:resource="https://pinboard.in/u:mraginsky/t:measure-concentration"/>
	<rdf:li rdf:resource="https://pinboard.in/u:mraginsky/t:probability"/>
	<rdf:li rdf:resource="https://pinboard.in/u:mraginsky/t:have-read"/>
</rdf:Bag></taxo:topics>
</item>
<item rdf:about="http://arxiv.org/abs/1507.02564">
    <title>[1507.02564] Sampling from a log-concave distribution with Projected Langevin Monte Carlo</title>
    <dc:date>2015-07-11T03:53:18+00:00</dc:date>
    <link>http://arxiv.org/abs/1507.02564</link>
    <dc:creator>mraginsky</dc:creator><description><![CDATA[We extend the Langevin Monte Carlo (LMC) algorithm to compactly supported measures via a projection step, akin to projected Stochastic Gradient Descent (SGD). We show that (projected) LMC allows to sample in polynomial time from a log-concave distribution with smooth potential. This gives a new Markov chain to sample from a log-concave distribution. Our main result shows in particular that when the target distribution is uniform, LMC mixes in O~(n7) steps (where n is the dimension). We also provide preliminary experimental evidence that LMC performs at least as well as hit-and-run, for which a better mixing time of O~(n4) was proved by Lov{\'a}sz and Vempala.]]></description>
<dc:subject>papers to-read heard-the-talk optimization sampling MCMC</dc:subject>
<dc:source>https://pinboard.in/</dc:source>
<dc:identifier>https://pinboard.in/u:mraginsky/b:463782c93bf6/</dc:identifier>
<taxo:topics><rdf:Bag>	<rdf:li rdf:resource="https://pinboard.in/u:mraginsky/t:papers"/>
	<rdf:li rdf:resource="https://pinboard.in/u:mraginsky/t:to-read"/>
	<rdf:li rdf:resource="https://pinboard.in/u:mraginsky/t:heard-the-talk"/>
	<rdf:li rdf:resource="https://pinboard.in/u:mraginsky/t:optimization"/>
	<rdf:li rdf:resource="https://pinboard.in/u:mraginsky/t:sampling"/>
	<rdf:li rdf:resource="https://pinboard.in/u:mraginsky/t:MCMC"/>
</rdf:Bag></taxo:topics>
</item>
<item rdf:about="http://arxiv.org/abs/1410.0503">
    <title>[1410.0503] On Bayes Risk Lower Bounds</title>
    <dc:date>2014-10-03T20:12:24+00:00</dc:date>
    <link>http://arxiv.org/abs/1410.0503</link>
    <dc:creator>mraginsky</dc:creator><description><![CDATA[This paper provides a general technique to lower bound the Bayes risk for arbitrary loss functions and prior distributions in the standard abstract decision theoretic setting. A lower bound on the Bayes risk not only serves as a lower bound on the minimax risk but also characterizes the fundamental limitations of the statistical difficulty of a decision problem under a given prior. Our bounds are based on then notion of f-informativity of the underlying class of probability measures and the prior. Application of our bounds requires upper bounds on the f-informativity and we derive new upper bounds on f-informativity for a class of f functions which lead to tight Bayes risk lower bounds. Our technique leads to generalizations of a variety of classical minimax bounds. As applications, we present Bayes risk lower bounds for several concrete estimation problems, including Gaussian location models, Bayesian Lasso, generalized linear models and principle component analysis for spiked covariance models.]]></description>
<dc:subject>papers to-read information-theory statistics heard-the-talk</dc:subject>
<dc:source>https://pinboard.in/</dc:source>
<dc:identifier>https://pinboard.in/u:mraginsky/b:e8aa46bbcc91/</dc:identifier>
<taxo:topics><rdf:Bag>	<rdf:li rdf:resource="https://pinboard.in/u:mraginsky/t:papers"/>
	<rdf:li rdf:resource="https://pinboard.in/u:mraginsky/t:to-read"/>
	<rdf:li rdf:resource="https://pinboard.in/u:mraginsky/t:information-theory"/>
	<rdf:li rdf:resource="https://pinboard.in/u:mraginsky/t:statistics"/>
	<rdf:li rdf:resource="https://pinboard.in/u:mraginsky/t:heard-the-talk"/>
</rdf:Bag></taxo:topics>
</item>
<item rdf:about="http://arxiv.org/abs/1305.4696">
    <title>[1305.4696] Tight Bounds for Set Disjointness in the Message Passing Model</title>
    <dc:date>2013-10-07T14:16:16+00:00</dc:date>
    <link>http://arxiv.org/abs/1305.4696</link>
    <dc:creator>mraginsky</dc:creator><dc:subject>papers to-read computer-science communication-complexity heard-the-talk</dc:subject>
<dc:source>https://pinboard.in/</dc:source>
<dc:identifier>https://pinboard.in/u:mraginsky/b:33f0dad3eb9c/</dc:identifier>
<taxo:topics><rdf:Bag>	<rdf:li rdf:resource="https://pinboard.in/u:mraginsky/t:papers"/>
	<rdf:li rdf:resource="https://pinboard.in/u:mraginsky/t:to-read"/>
	<rdf:li rdf:resource="https://pinboard.in/u:mraginsky/t:computer-science"/>
	<rdf:li rdf:resource="https://pinboard.in/u:mraginsky/t:communication-complexity"/>
	<rdf:li rdf:resource="https://pinboard.in/u:mraginsky/t:heard-the-talk"/>
</rdf:Bag></taxo:topics>
</item>
<item rdf:about="http://arxiv.org/abs/1305.4548">
    <title>[1305.4548] Distributed Learning of Distributions via Social Sampling</title>
    <dc:date>2013-06-14T01:48:44+00:00</dc:date>
    <link>http://arxiv.org/abs/1305.4548</link>
    <dc:creator>mraginsky</dc:creator><description><![CDATA[A protocol for distributed estimation of discrete distributions is proposed. Each agent begins with a single sample from the distribution, and the goal is to learn the empirical distribution of the samples. The protocol is based on a simple message-passing model motivated by communication in social networks. Agents sample a message randomly from their current estimates of the distribution, resulting in a protocol with quantized messages. Using tools from stochastic approximation, the algorithm is shown to converge almost surely. Examples illustrate three regimes with different consensus phenomena. Simulations demonstrate this convergence and give some insight into the effect of network topology.]]></description>
<dc:subject>papers to-read heard-the-talk social-networks distributed-systems stochastic-approximation</dc:subject>
<dc:source>https://pinboard.in/</dc:source>
<dc:identifier>https://pinboard.in/u:mraginsky/b:8f207b3532b1/</dc:identifier>
<taxo:topics><rdf:Bag>	<rdf:li rdf:resource="https://pinboard.in/u:mraginsky/t:papers"/>
	<rdf:li rdf:resource="https://pinboard.in/u:mraginsky/t:to-read"/>
	<rdf:li rdf:resource="https://pinboard.in/u:mraginsky/t:heard-the-talk"/>
	<rdf:li rdf:resource="https://pinboard.in/u:mraginsky/t:social-networks"/>
	<rdf:li rdf:resource="https://pinboard.in/u:mraginsky/t:distributed-systems"/>
	<rdf:li rdf:resource="https://pinboard.in/u:mraginsky/t:stochastic-approximation"/>
</rdf:Bag></taxo:topics>
</item>
<item rdf:about="http://arxiv.org/abs/1212.3866">
    <title>[1212.3866] Agnostic insurability of model classes</title>
    <dc:date>2012-12-19T03:03:42+00:00</dc:date>
    <link>http://arxiv.org/abs/1212.3866</link>
    <dc:creator>mraginsky</dc:creator><description><![CDATA[Our task is to predict finite upper bounds on a future draw from an unknown distribution p over the set of natural numbers, using only past observations generated independently and identically distributed according to p. While p is unknown, it is known to belong to a given collection P of probability distributions on the natural numbers. The support of the distributions p in P may be unbounded, and the prediction occurs for infinitely many draws. We are allowed to make observations without predicting upper bounds for some time, but must start and then continue to predict upper bounds after a finite time with probability 1 irrespective of which p in P governs the observations. If it is possible for any prescribed probability, however close to 1, to come up with a sequence of upper bounds that is never violated, over the infinite time window, with probability at least as big as the prescribed one, we say the model class P is insurable. We characterize insurability by a condition on how the neighborhood of distributions p in P should behave, one that is both necessary and sufficient.]]></description>
<dc:subject>papers to-read heard-the-talk probability large-deviations information-theory</dc:subject>
<dc:source>https://pinboard.in/</dc:source>
<dc:identifier>https://pinboard.in/u:mraginsky/b:92fec8b5ac99/</dc:identifier>
<taxo:topics><rdf:Bag>	<rdf:li rdf:resource="https://pinboard.in/u:mraginsky/t:papers"/>
	<rdf:li rdf:resource="https://pinboard.in/u:mraginsky/t:to-read"/>
	<rdf:li rdf:resource="https://pinboard.in/u:mraginsky/t:heard-the-talk"/>
	<rdf:li rdf:resource="https://pinboard.in/u:mraginsky/t:probability"/>
	<rdf:li rdf:resource="https://pinboard.in/u:mraginsky/t:large-deviations"/>
	<rdf:li rdf:resource="https://pinboard.in/u:mraginsky/t:information-theory"/>
</rdf:Bag></taxo:topics>
</item>
<item rdf:about="http://arxiv.org/abs/1011.1716">
    <title>[1011.1716] Least Squares Ranking on Graphs</title>
    <dc:date>2012-11-08T05:28:58+00:00</dc:date>
    <link>http://arxiv.org/abs/1011.1716</link>
    <dc:creator>mraginsky</dc:creator><description><![CDATA[Given a set of alternatives to be ranked, and some pairwise comparison data, ranking is a least squares computation on a graph. The vertices are the alternatives, and the edge values comprise the comparison data. The basic idea is very simple and old: come up with values on vertices such that their differences match the given edge data. Since an exact match will usually be impossible, one settles for matching in a least squares sense. This formulation was first described by Leake in 1976 for rankingfootball teams and appears as an example in Professor Gilbert Strang's classic linear algebra textbook. If one is willing to look into the residual a little further, then the problem really comes alive, as shown effectively by the remarkable recent paper of Jiang et al. With or without this twist, the humble least squares problem on graphs has far-reaching connections with many current areas ofresearch. These connections are to theoretical computer science (spectral graph theory, and multilevel methods for graph Laplacian systems); numerical analysis (algebraic multigrid, and finite element exterior calculus); other mathematics (Hodge decomposition, and random clique complexes); and applications (arbitrage, and ranking of sports teams). Not all of these connections are explored in this paper, but many are. The underlying ideas are easy to explain, requiring only the four fundamental subspaces from elementary linear algebra. One of our aims is to explain these basic ideas and connections, to get researchers in many fields interested in this topic. Another aim is to use our numerical experiments for guidance on selecting methods and exposing the need for further development.]]></description>
<dc:subject>papers to-read computational-topology ranking graph-theory heard-the-talk</dc:subject>
<dc:source>https://pinboard.in/</dc:source>
<dc:identifier>https://pinboard.in/u:mraginsky/b:12db251932bc/</dc:identifier>
<taxo:topics><rdf:Bag>	<rdf:li rdf:resource="https://pinboard.in/u:mraginsky/t:papers"/>
	<rdf:li rdf:resource="https://pinboard.in/u:mraginsky/t:to-read"/>
	<rdf:li rdf:resource="https://pinboard.in/u:mraginsky/t:computational-topology"/>
	<rdf:li rdf:resource="https://pinboard.in/u:mraginsky/t:ranking"/>
	<rdf:li rdf:resource="https://pinboard.in/u:mraginsky/t:graph-theory"/>
	<rdf:li rdf:resource="https://pinboard.in/u:mraginsky/t:heard-the-talk"/>
</rdf:Bag></taxo:topics>
</item>
<item rdf:about="http://arxiv.org/abs/1207.3265">
    <title>[1207.3265] The Sufficiency Principle for Decentralized Data Reduction</title>
    <dc:date>2012-07-16T04:05:19+00:00</dc:date>
    <link>http://arxiv.org/abs/1207.3265</link>
    <dc:creator>mraginsky</dc:creator><description><![CDATA[This paper develops the sufficiency principle suitable for data reduction in decentralized inference systems. Both parallel and tandem networks are studied and we focus on the cases where observations at decentralized nodes are conditionally dependent. For a parallel network, through the introduction of a hidden variable that induces conditional independence among the observations, the locally sufficient statistics, defined with respect to the hidden variable, are shown to be globally sufficient for the parameter of inference interest. For a tandem network, the notion of conditional sufficiency is introduced and the related theories and tools are developed. Finally, connections between the sufficiency principle and some distributed source coding problems are explored.]]></description>
<dc:subject>papers heard-the-talk to-read information-theory networks statistics sufficiency</dc:subject>
<dc:source>https://pinboard.in/</dc:source>
<dc:identifier>https://pinboard.in/u:mraginsky/b:e0c3a864a50c/</dc:identifier>
<taxo:topics><rdf:Bag>	<rdf:li rdf:resource="https://pinboard.in/u:mraginsky/t:papers"/>
	<rdf:li rdf:resource="https://pinboard.in/u:mraginsky/t:heard-the-talk"/>
	<rdf:li rdf:resource="https://pinboard.in/u:mraginsky/t:to-read"/>
	<rdf:li rdf:resource="https://pinboard.in/u:mraginsky/t:information-theory"/>
	<rdf:li rdf:resource="https://pinboard.in/u:mraginsky/t:networks"/>
	<rdf:li rdf:resource="https://pinboard.in/u:mraginsky/t:statistics"/>
	<rdf:li rdf:resource="https://pinboard.in/u:mraginsky/t:sufficiency"/>
</rdf:Bag></taxo:topics>
</item>
<item rdf:about="http://arxiv.org/abs/1203.4626">
    <title>[1203.4626] Active Sequential Hypothesis Testing</title>
    <dc:date>2012-03-22T00:38:37+00:00</dc:date>
    <link>http://arxiv.org/abs/1203.4626</link>
    <dc:creator>mraginsky</dc:creator><description><![CDATA[Consider a decision maker who is responsible to dynamically collect observations so as to enhance his information in a speedy manner about an underlying phenomena of interest while accounting for the penalty of wrong declaration. The special cases of the problem are shown to be that of variable-length coding with feedback and noisy dynamic search. Due to the sequential nature of the problem, the decision maker relies on his current information state to adaptively select the most "informative" sensing action among the available ones. 
In this paper, using results in dynamic programming, a lower bound for the optimal total cost is established. Moreover, upper bounds are obtained via an analysis of heuristic policies for dynamic selection of actions. It is shown that the proposed heuristics achieve asymptotic optimality in many practically relevant problems including the problems of variable-length coding with feedback and noisy dynamic search; where asymptotic optimality implies that the relative difference between the total cost achieved by the proposed policies and the optimal total cost approaches zero as the penalty of wrong declaration or the number of hypotheses (hence the number of collected samples) increases. Furthermore, using the obtained bounds, the gain of adaptive selection of sensing actions is shown to be at least logarithmic in the penalty associated with wrong declarations.]]></description>
<dc:subject>papers to-read control-theory information-theory adaptive-systems heard-the-talk</dc:subject>
<dc:source>https://pinboard.in/</dc:source>
<dc:identifier>https://pinboard.in/u:mraginsky/b:f4add78bdb48/</dc:identifier>
<taxo:topics><rdf:Bag>	<rdf:li rdf:resource="https://pinboard.in/u:mraginsky/t:papers"/>
	<rdf:li rdf:resource="https://pinboard.in/u:mraginsky/t:to-read"/>
	<rdf:li rdf:resource="https://pinboard.in/u:mraginsky/t:control-theory"/>
	<rdf:li rdf:resource="https://pinboard.in/u:mraginsky/t:information-theory"/>
	<rdf:li rdf:resource="https://pinboard.in/u:mraginsky/t:adaptive-systems"/>
	<rdf:li rdf:resource="https://pinboard.in/u:mraginsky/t:heard-the-talk"/>
</rdf:Bag></taxo:topics>
</item>
<item rdf:about="http://arxiv.org/abs/1007.1033">
    <title>[1007.1033] A Theory of Network Equivalence, Parts I and II</title>
    <dc:date>2012-02-07T07:42:40+00:00</dc:date>
    <link>http://arxiv.org/abs/1007.1033</link>
    <dc:creator>mraginsky</dc:creator><description><![CDATA[A family of equivalence tools for bounding network capacities is introduced. Part I treats networks of point-to-point channels. The main result is roughly as follows. Given a network of noisy, independent, memoryless point-to-point channels, a collection of communication demands can be met on the given network if and only if it can be met on another network where each noisy channel is replaced by a noiseless bit pipe with throughput equal to the noisy channel capacity. This result was known previously for the case of a single-source multicast demand. The result given here treats general demands -- including, for example, multiple unicast demands -- and applies even when the achievable rate region for the corresponding demands is unknown in the noiseless network. In part II, definitions of upper and lower bounding channel models for general channels are introduced. By these definitions, a collection of communication demands can be met on a network of independent channels if it can be met on a network where each channel is replaced by its lower bounding model andonly if it can be met on a network where each channel is replaced by its upper bounding model. This work derives general conditions under which a network of noiseless bit pipes is an upper or lower bounding model for a multiterminal channel. Example upper and lower bounding models for broadcast, multiple access, and interference channels are given. It is then shown that bounding the difference between the upper and lower bounding models for a given channel yields bounds on the accuracy of network capacity bounds derived using those models. By bounding the capacity of a network of independent noisy channels by the network coding capacity of a network of noiseless bit pipes, this approach represents one step towards the goal of building computational tools for bounding network capacities.]]></description>
<dc:subject>papers to-read information-theory networks multiagent-systems heard-the-talk</dc:subject>
<dc:source>https://pinboard.in/</dc:source>
<dc:identifier>https://pinboard.in/u:mraginsky/b:e9fe2881a938/</dc:identifier>
<taxo:topics><rdf:Bag>	<rdf:li rdf:resource="https://pinboard.in/u:mraginsky/t:papers"/>
	<rdf:li rdf:resource="https://pinboard.in/u:mraginsky/t:to-read"/>
	<rdf:li rdf:resource="https://pinboard.in/u:mraginsky/t:information-theory"/>
	<rdf:li rdf:resource="https://pinboard.in/u:mraginsky/t:networks"/>
	<rdf:li rdf:resource="https://pinboard.in/u:mraginsky/t:multiagent-systems"/>
	<rdf:li rdf:resource="https://pinboard.in/u:mraginsky/t:heard-the-talk"/>
</rdf:Bag></taxo:topics>
</item>
<item rdf:about="http://ieeexplore.ieee.org/xpls/abs_all.jsp?arnumber=5961831">
    <title>IEEE Xplore - The Entropy Per Coordinate of a Random Vector is Highly Constrained Under Convexity Conditions</title>
    <dc:date>2011-07-25T22:09:00+00:00</dc:date>
    <link>http://ieeexplore.ieee.org/xpls/abs_all.jsp?arnumber=5961831</link>
    <dc:creator>mraginsky</dc:creator><dc:subject>papers heard-the-talk information-theory probability measure-concentration</dc:subject>
<dc:identifier>https://pinboard.in/u:mraginsky/b:3d388fc61a97/</dc:identifier>
<taxo:topics><rdf:Bag>	<rdf:li rdf:resource="https://pinboard.in/u:mraginsky/t:papers"/>
	<rdf:li rdf:resource="https://pinboard.in/u:mraginsky/t:heard-the-talk"/>
	<rdf:li rdf:resource="https://pinboard.in/u:mraginsky/t:information-theory"/>
	<rdf:li rdf:resource="https://pinboard.in/u:mraginsky/t:probability"/>
	<rdf:li rdf:resource="https://pinboard.in/u:mraginsky/t:measure-concentration"/>
</rdf:Bag></taxo:topics>
</item>
<item rdf:about="http://ieeexplore.ieee.org/xpls/abs_all.jsp?arnumber=5961844">
    <title>IEEE Xplore - Feedback in the Non-Asymptotic Regime</title>
    <dc:date>2011-07-25T22:07:07+00:00</dc:date>
    <link>http://ieeexplore.ieee.org/xpls/abs_all.jsp?arnumber=5961844</link>
    <dc:creator>mraginsky</dc:creator><dc:subject>papers to-read heard-the-talk feedback-information-theory</dc:subject>
<dc:identifier>https://pinboard.in/u:mraginsky/b:490b7ab258d7/</dc:identifier>
<taxo:topics><rdf:Bag>	<rdf:li rdf:resource="https://pinboard.in/u:mraginsky/t:papers"/>
	<rdf:li rdf:resource="https://pinboard.in/u:mraginsky/t:to-read"/>
	<rdf:li rdf:resource="https://pinboard.in/u:mraginsky/t:heard-the-talk"/>
	<rdf:li rdf:resource="https://pinboard.in/u:mraginsky/t:feedback-information-theory"/>
</rdf:Bag></taxo:topics>
</item>
<item rdf:about="http://ieeexplore.ieee.org/xpls/abs_all.jsp?arnumber=5961853">
    <title>IEEE Xplore - MMSE Dimension</title>
    <dc:date>2011-07-25T22:06:37+00:00</dc:date>
    <link>http://ieeexplore.ieee.org/xpls/abs_all.jsp?arnumber=5961853</link>
    <dc:creator>mraginsky</dc:creator><dc:subject>papers to-read heard-the-talk information-theory statistics probability estimation</dc:subject>
<dc:identifier>https://pinboard.in/u:mraginsky/b:e40b5d262bcc/</dc:identifier>
<taxo:topics><rdf:Bag>	<rdf:li rdf:resource="https://pinboard.in/u:mraginsky/t:papers"/>
	<rdf:li rdf:resource="https://pinboard.in/u:mraginsky/t:to-read"/>
	<rdf:li rdf:resource="https://pinboard.in/u:mraginsky/t:heard-the-talk"/>
	<rdf:li rdf:resource="https://pinboard.in/u:mraginsky/t:information-theory"/>
	<rdf:li rdf:resource="https://pinboard.in/u:mraginsky/t:statistics"/>
	<rdf:li rdf:resource="https://pinboard.in/u:mraginsky/t:probability"/>
	<rdf:li rdf:resource="https://pinboard.in/u:mraginsky/t:estimation"/>
</rdf:Bag></taxo:topics>
</item>
<item rdf:about="http://ieeexplore.ieee.org/xpls/abs_all.jsp?arnumber=5895067">
    <title>IEEE Xplore - Rate-Constrained Simulation and Source Coding i.i.d. Sources</title>
    <dc:date>2011-06-21T20:56:59+00:00</dc:date>
    <link>http://ieeexplore.ieee.org/xpls/abs_all.jsp?arnumber=5895067</link>
    <dc:creator>mraginsky</dc:creator><dc:subject>papers to-read information-theory ergodic-theory source-coding heard-the-talk</dc:subject>
<dc:identifier>https://pinboard.in/u:mraginsky/b:21170ee04926/</dc:identifier>
<taxo:topics><rdf:Bag>	<rdf:li rdf:resource="https://pinboard.in/u:mraginsky/t:papers"/>
	<rdf:li rdf:resource="https://pinboard.in/u:mraginsky/t:to-read"/>
	<rdf:li rdf:resource="https://pinboard.in/u:mraginsky/t:information-theory"/>
	<rdf:li rdf:resource="https://pinboard.in/u:mraginsky/t:ergodic-theory"/>
	<rdf:li rdf:resource="https://pinboard.in/u:mraginsky/t:source-coding"/>
	<rdf:li rdf:resource="https://pinboard.in/u:mraginsky/t:heard-the-talk"/>
</rdf:Bag></taxo:topics>
</item>
<item rdf:about="http://ieeexplore.ieee.org/xpls/abs_all.jsp?arnumber=5895099">
    <title>IEEE Xplore - Minimum Expected Length of Fixed-to-Variable Lossless Compression Without Prefix Constraints</title>
    <dc:date>2011-06-21T20:55:42+00:00</dc:date>
    <link>http://ieeexplore.ieee.org/xpls/abs_all.jsp?arnumber=5895099</link>
    <dc:creator>mraginsky</dc:creator><dc:subject>papers to-read information-theory source-coding heard-the-talk</dc:subject>
<dc:identifier>https://pinboard.in/u:mraginsky/b:426f5f4818fb/</dc:identifier>
<taxo:topics><rdf:Bag>	<rdf:li rdf:resource="https://pinboard.in/u:mraginsky/t:papers"/>
	<rdf:li rdf:resource="https://pinboard.in/u:mraginsky/t:to-read"/>
	<rdf:li rdf:resource="https://pinboard.in/u:mraginsky/t:information-theory"/>
	<rdf:li rdf:resource="https://pinboard.in/u:mraginsky/t:source-coding"/>
	<rdf:li rdf:resource="https://pinboard.in/u:mraginsky/t:heard-the-talk"/>
</rdf:Bag></taxo:topics>
</item>
<item rdf:about="http://ita.ucsd.edu/workshop/11/files/paper/paper_374.pdf">
    <title>Sergio Verdu: Shannon's inequality (ITA 2011 slides)</title>
    <dc:date>2011-03-19T01:50:19+00:00</dc:date>
    <link>http://ita.ucsd.edu/workshop/11/files/paper/paper_374.pdf</link>
    <dc:creator>mraginsky</dc:creator><dc:subject>information-theory slides heard-the-talk filetype:pdf media:document</dc:subject>
<dc:identifier>https://pinboard.in/u:mraginsky/b:28b8bc1f1929/</dc:identifier>
<taxo:topics><rdf:Bag>	<rdf:li rdf:resource="https://pinboard.in/u:mraginsky/t:information-theory"/>
	<rdf:li rdf:resource="https://pinboard.in/u:mraginsky/t:slides"/>
	<rdf:li rdf:resource="https://pinboard.in/u:mraginsky/t:heard-the-talk"/>
	<rdf:li rdf:resource="https://pinboard.in/u:mraginsky/t:filetype:pdf"/>
	<rdf:li rdf:resource="https://pinboard.in/u:mraginsky/t:media:document"/>
</rdf:Bag></taxo:topics>
</item>
<item rdf:about="http://ieeexplore.ieee.org/xpls/abs_all.jsp?arnumber=5730571">
    <title>IEEE Xplore - Lower Bounds for the Minimax Risk Using f-Divergences, and Applications</title>
    <dc:date>2011-03-17T13:44:21+00:00</dc:date>
    <link>http://ieeexplore.ieee.org/xpls/abs_all.jsp?arnumber=5730571</link>
    <dc:creator>mraginsky</dc:creator><dc:subject>papers have-read heard-the-talk statistics information-theory</dc:subject>
<dc:identifier>https://pinboard.in/u:mraginsky/b:1e604b21f3d9/</dc:identifier>
<taxo:topics><rdf:Bag>	<rdf:li rdf:resource="https://pinboard.in/u:mraginsky/t:papers"/>
	<rdf:li rdf:resource="https://pinboard.in/u:mraginsky/t:have-read"/>
	<rdf:li rdf:resource="https://pinboard.in/u:mraginsky/t:heard-the-talk"/>
	<rdf:li rdf:resource="https://pinboard.in/u:mraginsky/t:statistics"/>
	<rdf:li rdf:resource="https://pinboard.in/u:mraginsky/t:information-theory"/>
</rdf:Bag></taxo:topics>
</item>
<item rdf:about="http://arxiv.org/abs/1011.2952">
    <title>[1011.2952] Balanced Reduction of Nonlinear Control Systems in Reproducing Kernel Hilbert Space</title>
    <dc:date>2010-11-16T05:42:12+00:00</dc:date>
    <link>http://arxiv.org/abs/1011.2952</link>
    <dc:creator>mraginsky</dc:creator><description><![CDATA["We introduce a novel data-driven order reduction method for nonlinear control systems, drawing on recent progress in machine learning and statistical dimensionality reduction. The method rests on the assumption that the nonlinear system behaves linearly when lifted into a high (or infinite) dimensional feature space where balanced truncation may be carried out implicitly. This leads to a nonlinear reduction map which can be combined with a representation of the system belonging to a reproducing kernel Hilbert space to give a closed, reduced order dynamical system which captures the essential input-output characteristics of the original model. Empirical simulations illustrating the approach are also provided."
]]></description>
<dc:subject>papers to-read heard-the-talk control-theory machine-learning dynamical-systems</dc:subject>
<dc:identifier>https://pinboard.in/u:mraginsky/b:66d8e9e14a35/</dc:identifier>
<taxo:topics><rdf:Bag>	<rdf:li rdf:resource="https://pinboard.in/u:mraginsky/t:papers"/>
	<rdf:li rdf:resource="https://pinboard.in/u:mraginsky/t:to-read"/>
	<rdf:li rdf:resource="https://pinboard.in/u:mraginsky/t:heard-the-talk"/>
	<rdf:li rdf:resource="https://pinboard.in/u:mraginsky/t:control-theory"/>
	<rdf:li rdf:resource="https://pinboard.in/u:mraginsky/t:machine-learning"/>
	<rdf:li rdf:resource="https://pinboard.in/u:mraginsky/t:dynamical-systems"/>
</rdf:Bag></taxo:topics>
</item>
<item rdf:about="http://arxiv.org/abs/1001.4448">
    <title>[1001.4448] R'enyi Divergence and Majorization</title>
    <dc:date>2010-06-14T15:35:30+00:00</dc:date>
    <link>http://arxiv.org/abs/1001.4448</link>
    <dc:creator>mraginsky</dc:creator><description><![CDATA["R'enyi divergence is related to R'enyi entropy much like information divergence (also called Kullback-Leibler divergence or relative entropy) is related to Shannon's entropy, and comes up in many settings. It was introduced by R'enyi as a measure of information that satisfies almost the same axioms as information divergence. We review the most important properties of R'enyi divergence, including its relation to some other distances. We show how R'enyi divergence appears when the theory of majorization is generalized from the finite to the continuous setting. Finally, R'enyi divergence plays a role in analyzing the number of binary questions required to guess the values of a sequence of random variables."
]]></description>
<dc:subject>to-read information-theory statistics majorization heard-the-talk papers</dc:subject>
<dc:identifier>https://pinboard.in/u:mraginsky/b:c7b5614fdf29/</dc:identifier>
<taxo:topics><rdf:Bag>	<rdf:li rdf:resource="https://pinboard.in/u:mraginsky/t:to-read"/>
	<rdf:li rdf:resource="https://pinboard.in/u:mraginsky/t:information-theory"/>
	<rdf:li rdf:resource="https://pinboard.in/u:mraginsky/t:statistics"/>
	<rdf:li rdf:resource="https://pinboard.in/u:mraginsky/t:majorization"/>
	<rdf:li rdf:resource="https://pinboard.in/u:mraginsky/t:heard-the-talk"/>
	<rdf:li rdf:resource="https://pinboard.in/u:mraginsky/t:papers"/>
</rdf:Bag></taxo:topics>
</item>
<item rdf:about="http://arxiv.org/abs/1002.0042">
    <title>[1002.0042] Lower bounds for the minimax risk using $f$-divergences and applications</title>
    <dc:date>2010-06-14T15:34:17+00:00</dc:date>
    <link>http://arxiv.org/abs/1002.0042</link>
    <dc:creator>mraginsky</dc:creator><description><![CDATA[Very nice: "A new lower bound involving $f$-divergences between the underlying probability measures is proved for the minimax risk in estimation problems. The proof just uses the convexity of the function $f$ and is extremely simple. Special cases and straightforward corollaries of our bound include well known inequalities for establishing minimax lower bounds such as Fano's inequality, Pinsker's inequality and inequalities based on global entropy conditions. Two applications are provided: a new minimax lower bound for the reconstruction of convex bodies from noisy support function measurements and a different proof of a recent minimax lower bound for the estimation of a covariance matrix."
]]></description>
<dc:subject>papers have-read information-theory statistics heard-the-talk</dc:subject>
<dc:identifier>https://pinboard.in/u:mraginsky/b:3093e83dcb76/</dc:identifier>
<taxo:topics><rdf:Bag>	<rdf:li rdf:resource="https://pinboard.in/u:mraginsky/t:papers"/>
	<rdf:li rdf:resource="https://pinboard.in/u:mraginsky/t:have-read"/>
	<rdf:li rdf:resource="https://pinboard.in/u:mraginsky/t:information-theory"/>
	<rdf:li rdf:resource="https://pinboard.in/u:mraginsky/t:statistics"/>
	<rdf:li rdf:resource="https://pinboard.in/u:mraginsky/t:heard-the-talk"/>
</rdf:Bag></taxo:topics>
</item>
</rdf:RDF>