BZPEERPapers, people, evidence and research paths
Menu

Discover

SearchFind papers, people, topics, institutions and opportunities from one place.GraphSee how papers, authors, topics and evidence connect.

Research tools

HomeContinue from the papers, people and topics that matter now.CollectionsTurn saved papers into reading lists, evidence maps and shareable context.ResearchReconstruct the path that led you from search to paper to question.CollaborationMove from a paper, topic or expert request into a focused thread.PublishCreate full-text research articles with metadata, formulas and versions.

Network

ExpertsFind specialists whose work and reviews explain why they can help.CommunitiesJoin research groups organized around papers, topics and shared evidence.

Opportunities

ListingsBrowse roles, calls and collaborations connected to real research context.

Account

Log inReturn to your saved papers, graph views and active threads.Create accountStart saving papers, building a research trail and joining teams.
Log inCreate account

Source author record

Ayfer Özgür

Ayfer Özgür appears in the imported research catalog. Authorship, coauthor and topic links are available while profile ownership is still unclaimed.

ResearcherUnclaimed source record
Information Theorymath.ITMachine LearningCryptography and Securitymath.OCNetworking and Internet Architecture

Catalog footprint

What is connected

16works
6topics
4close collaborators

Actions

Connect this record

Log in to claim
Open graphBrowse works

Research graph

See the researcher in context

Open full explorer

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

Published work

16 published item(s)

preprint2026arXiv

Less Random, More Private: What is the Optimal Subsampling Scheme for DP-SGD?

Poisson subsampling is the default sampling scheme in differentially private machine learning, largely because its unstructured randomness yields tractable privacy amplification analyses. Yet this same randomness introduces substantial participation variance: each sample appears in very different numbers of training iterations. In this work, we show that this variance is not merely a practical artifact to be tolerated, but a fundamental source of suboptimal privacy amplification. We prove that Balanced Iteration Subsampling (BIS), a structured scheme in which each sample participates in exactly a fixed number of iterations, achieves stronger privacy amplification than Poisson subsampling and is optimal at both extremes of the noise spectrum ($σ\to 0$ and $σ\to \infty$). Our analysis reveals that the privacy-noise tradeoff is governed not by maximizing randomness, but by eliminating participation variance while preserving uniform marginal participation across iterations. To translate this asymptotic theory into finite-noise guarantees, we introduce a practical near-exact Monte Carlo accountant for BIS, which removes the analytical slack of existing RDP and composition-based PLD analyses. Evaluations across more than 60 practical DP-SGD configurations show that BIS consistently outperforms Poisson subsampling in the low-noise regimes most relevant for high-utility private training, reducing the required noise multiplier by up to $9.6\%$. These results overturn the common intuition that more sampling randomness necessarily yields stronger privacy amplification: in DP-SGD, structured participation can be both more practical and more private. Our implementation is available at https://github.com/dong-xin-ao-andy/bis-mc-accountant.

0 citations0 reviewsNo code linkedOpen access
preprint2022arXiv

The Poisson binomial mechanism for secure and private federated learning

We introduce the Poisson Binomial mechanism (PBM), a discrete differential privacy mechanism for distributed mean estimation (DME) with applications to federated learning and analytics. We provide a tight analysis of its privacy guarantees, showing that it achieves the same privacy-accuracy trade-offs as the continuous Gaussian mechanism. Our analysis is based on a novel bound on the Rényi divergence of two Poisson binomial distributions that may be of independent interest. Unlike previous discrete DP schemes based on additive noise, our mechanism encodes local information into a parameter of the binomial distribution, and hence the output distribution is discrete with bounded support. Moreover, the support does not increase as the privacy budget $\varepsilon \rightarrow 0$ as in the case of additive schemes which require the addition of more noise to achieve higher privacy; on the contrary, the support becomes smaller as $\varepsilon \rightarrow 0$. The bounded support enables us to combine our mechanism with secure aggregation (SecAgg), a multi-party cryptographic protocol, without the need of performing modular clipping which results in an unbiased estimator of the sum of the local vectors. This in turn allows us to apply it in the private FL setting and provide an upper bound on the convergence rate of the SGD algorithm. Moreover, since the support of the output distribution becomes smaller as $\varepsilon \rightarrow 0$, the communication cost of our scheme decreases with the privacy constraint $\varepsilon$, outperforming all previous distributed DP schemes based on additive noise in the high privacy or low communication regimes.

0 citations0 reviewsNo code linkedOpen access
preprint2021arXiv

Advances and Open Problems in Federated Learning

Federated learning (FL) is a machine learning setting where many clients (e.g. mobile devices or whole organizations) collaboratively train a model under the orchestration of a central server (e.g. service provider), while keeping the training data decentralized. FL embodies the principles of focused data collection and minimization, and can mitigate many of the systemic privacy risks and costs resulting from traditional, centralized machine learning and data science approaches. Motivated by the explosive growth in FL research, this paper discusses recent advances and presents an extensive collection of open problems and challenges.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

Lower Bounds and a Near-Optimal Shrinkage Estimator for Least Squares using Random Projections

In this work, we consider the deterministic optimization using random projections as a statistical estimation problem, where the squared distance between the predictions from the estimator and the true solution is the error metric. In approximately solving a large scale least squares problem using Gaussian sketches, we show that the sketched solution has a conditional Gaussian distribution with the true solution as its mean. Firstly, tight worst case error lower bounds with explicit constants are derived for any estimator using the Gaussian sketch, and the classical sketching is shown to be the optimal unbiased estimator. For biased estimators, the lower bound also incorporates prior knowledge about the true solution. Secondly, we use the James-Stein estimator to derive an improved estimator for the least squares solution using the Gaussian sketch. An upper bound on the expected error of this estimator is derived, which is smaller than the error of the classical Gaussian sketch solution for any given data. The upper and lower bounds match when the SNR of the true solution is known to be small and the data matrix is well conditioned. Empirically, this estimator achieves smaller error on simulated and real datasets, and works for other common sketching methods as well.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

The Courtade-Kumar Most Informative Boolean Function Conjecture and a Symmetrized Li-Médard Conjecture are Equivalent

We consider the Courtade-Kumar most informative Boolean function conjecture for balanced functions, as well as a conjecture by Li and Médard that dictatorship functions also maximize the $L^α$ norm of $T_pf$ for $1\leqα\leq2$ where $T_p$ is the noise operator and $f$ is a balanced Boolean function. By using a result due to Laguerre from the 1880's, we are able to bound how many times an $L^α$-norm related quantity can cross zero as a function of $α$, and show that these two conjectures are essentially equivalent.

0 citations0 reviewsNo code linkedOpen access
preprint2016arXiv

Channel Diversity needed for Vector Space Interference Alignment

We consider vector space interference alignment strategies over the $K$-user interference channel and derive an upper bound on the achievable degrees of freedom as a function of the channel diversity $L$, where the channel diversity is modeled by $L$ real-valued parallel channels with coefficients drawn from a non-degenerate joint distribution. The seminal work of Cadambe and Jafar shows that when $L$ is unbounded, vector space interference alignment can achieve $1/2$ degrees of freedom per user independent of the number of users $K$. However wireless channels have limited diversity in practice, dictated by their coherence time and bandwidth, and an important question is the number of degrees of freedom achievable at finite $L$. When $K=3$ and if $L$ is finite, Bresler et al show that the number of degrees of freedom achievable with vector space interference alignment is bounded away from $1/2$, and the gap decreases inversely proportional to $L$. In this paper, we show that when $K\geq4$, the gap is significantly larger. In particular, the gap to the optimal $1/2$ degrees of freedom per user can decrease at most like $1/\sqrt{L}$, and when $L$ is smaller than the order of $2^{(K-2)(K-3)}$, it decays at most like $1/\sqrt[4]{L}$.

0 citations0 reviewsNo code linkedOpen access
preprint2016arXiv

Universally Near Optimal Online Power Control for Energy Harvesting Nodes

We consider online power control for an energy harvesting system with random i.i.d. energy arrivals and a finite size battery. We propose a simple online power control policy for this channel that requires minimal information regarding the distribution of the energy arrivals and prove that it is universally near-optimal for all parameter values. In particular, the policy depends on the distribution of the energy arrival process only through its mean and it achieves the optimal long-term average throughput of the channel within both constant additive and multiplicative gaps. Existing heuristics for online power control fail to achieve such universal performance. This result also allows us to approximate the long-term average throughput of the system with a simple formula, which sheds some light on the qualitative behavior of the throughput, namely how it depends on the distribution of the energy arrivals and the size of the battery.

0 citations0 reviewsNo code linkedOpen access
preprint2015arXiv

Capacity Approximations for Gaussian Relay Networks

Consider a Gaussian relay network where a source node communicates to a destination node with the help of several layers of relays. Recent work has shown that compress-and-forward based strategies can achieve the capacity of this network within an additive gap. Here, the relays quantize their received signals at the noise level and map them to random Gaussian codebooks. The resultant gap to capacity is independent of the SNRs of the channels in the network and the topology but is linear in the total number of nodes. In this paper, we provide an improved lower bound on the rate achieved by compress-and-forward based strategies (noisy network coding in particular) in arbitrary Gaussian relay networks, whose gap to capacity depends on the network not only through the total number of nodes but also through the degrees of freedom of the min cut of the network. We illustrate that for many networks, this refined lower bound can lead to a better approximation of the capacity. In particular, we demonstrate that it leads to a logarithmic rather than linear capacity gap in the total number of nodes for certain classes of layered networks. The improvement comes from quantizing the received signals of the relays at a resolution decreasing with the total number of nodes in the network. This suggests that the rule-of-thumb in literature of quantizing the received signals at the noise level can be highly suboptimal.

0 citations0 reviewsNo code linkedOpen access
preprint2015arXiv

Cooperative Binning for Semideterministic Channels

The capacity regions of semideterministic multiuser channels, such as the semideterministic relay channel and the multiple access channel with partially cribbing encoders, have been characterized using the idea of partial-decode-forward. However, the requirement to explicitly decode part of the message at intermediate nodes can be restrictive in some settings; for example, when nodes have different side information regarding the state of the channel. In this paper, we generalize this scheme to $\textit{cooperative-bin-forward}$ by building on the observation that explicit recovering of part of the message is not needed to induce cooperation. Instead, encoders can bin their received signals and cooperatively forward the bin index to the decoder. The main advantage of this new scheme is illustrated by considering state-dependent extensions of the aforementioned semideterministic setups. While partial-decode-forward is not applicable in these new setups, cooperative-bin-forward continues to achieve capacity.

0 citations0 reviewsNo code linkedOpen access
preprint2015arXiv

Multicoding Schemes for Interference Channels

The best known inner bound for the 2-user discrete memoryless interference channel is the Han-Kobayashi rate region. The coding schemes that achieve this region are based on rate-splitting and superposition coding. In this paper, we develop a multicoding scheme to achieve the same rate region. A key advantage of the multicoding nature of the proposed coding scheme is that it can be naturally extended to more general settings, such as when encoders have state information or can overhear each other. In particular, we extend our coding scheme to characterize the capacity region of the state-dependent deterministic Z-interference channel when noncausal state information is available at the interfering transmitter. We specialize our results to the case of the linear deterministic model with on/off interference which models a wireless system where a cognitive transmitter is noncausally aware of the times it interferes with a primary transmission. For this special case, we provide an explicit expression for the capacity region and discuss some interesting properties of the optimal strategy. We also extend our multicoding scheme to find the capacity region of the deterministic Z-interference channel when the signal of the interfering transmitter can be overheard at the other transmitter (a.k.a. unidirectional partial cribbing).

0 citations0 reviewsNo code linkedOpen access
preprint2015arXiv

Near Optimal Energy Control and Approximate Capacity of Energy Harvesting Communication

We consider an energy-harvesting communication system where a transmitter powered by an exogenous energy arrival process and equipped with a finite battery of size $B_{max}$ communicates over a discrete-time AWGN channel. We first concentrate on a simple Bernoulli energy arrival process where at each time step, either an energy packet of size $E$ is harvested with probability $p$, or no energy is harvested at all, independent of the other time steps. We provide a near optimal energy control policy and a simple approximation to the information-theoretic capacity of this channel. Our approximations for both problems are universal in all the system parameters involved ($p$, $E$ and $B_{max}$), i.e. we bound the approximation gaps by a constant independent of the parameter values. Our results suggest that a battery size $B_{max}\geq E$ is (approximately) sufficient to extract the infinite battery capacity of this channel. We then extend our results to general i.i.d. energy arrival processes. Our approximate capacity characterizations provide important insights for the optimal design of energy harvesting communication systems in the regime where both the battery size and the average energy arrival rate are large.

0 citations0 reviewsNo code linkedOpen access
preprint2015arXiv

When are dynamic relaying strategies necessary in half-duplex wireless networks?

We study a simple question: when are dynamic relaying strategies essential in optimizing the diversity-multiplexing tradeoff (DMT) in half-duplex wireless relay networks? This is motivated by apparently two contrasting results even for a simple 3 node network, with a single half-duplex relay. When all channels are assumed to be i.i.d. fading, a static schedule where the relay listens half the time and transmits half the time combined with quantize-map-forward (QMF) relaying is known to achieve the full-duplex performance. However, when there is no direct link between source and destination, a dynamic-decode-forward (DDF) strategy is needed to achieve the optimal tradeoff. In this case, a static schedule is strictly suboptimal and the optimal tradeoff is significantly worse than the full-duplex performance. In this paper we study the general case when the direct link is neither as strong as the other links nor fully non-existent, and identify regimes where dynamic schedules are necessary and those where static schedules are enough. We identify 4 qualitatively different regimes for the single relay channel where the tradeoff between diversity and multiplexing is significantly different. We show that in all these regimes one of the above two strategies is sufficient to achieve the optimal tradeoff by developing a new upper bound on the best achievable tradeoff under channel state information available only at the receivers. A natural next question is whether these two strategies are sufficient to achieve the DMT of more general half-duplex wireless networks. We propose a generalization of the two existing schemes through a dynamic QMF (DQMF) strategy, where the relay listens for a fraction of time depending on received CSI but not long enough to be able to decode. We show that such a DQMF strategy is needed to achieve the optimal DMT in a parallel channel with two relays.

0 citations0 reviewsNo code linkedOpen access
preprint2014arXiv

On feedback in Gaussian multi-hop networks

The study of feedback has been mostly limited to single-hop communication settings. In this paper, we consider Gaussian networks where sources and destinations can communicate with the help of intermediate relays over multiple hops. We assume that links in the network can be bidirected providing opportunities for feedback. We ask the following question: can the information transfer in both directions of a link be critical to maximizing the end-to-end communication rates in the network? Equivalently, could one of the directions in each bidirected link (and more generally at least one of the links forming a cycle) be shut down and the capacity of the network still be approximately maintained? We show that in any arbitrary Gaussian network with bidirected edges and cycles and unicast traffic, we can always identify a directed acyclic subnetwork that approximately maintains the capacity of the original network. For Gaussian networks with multiple-access and broadcast traffic, an acyclic subnetwork is sufficient to achieve every rate point in the capacity region of the original network, however, there may not be a single acyclic subnetwork that maintains the whole capacity region. For networks with multicast and multiple unicast traffic, on the other hand, bidirected information flow across certain links can be critically needed to maximize the end-to-end capacity region. These results can be regarded as generalizations of the conclusions regarding the usefulness of feedback in various single-hop Gaussian settings and can provide opportunities for simplifying operation in Gaussian multi-hop networks.

0 citations0 reviewsNo code linkedOpen access
preprint2013arXiv

Achieving the Capacity of the N-Relay Gaussian Diamond Network Within log N Bits

We consider the N-relay Gaussian diamond network where a source node communicates to a destination node via N parallel relays through a cascade of a Gaussian broadcast (BC) and a multiple access (MAC) channel. Introduced in 2000 by Schein and Gallager, the capacity of this relay network is unknown in general. The best currently available capacity approximation, independent of the coefficients and the SNR's of the constituent channels, is within an additive gap of 1.3 N bits, which follows from the recent capacity approximations for general Gaussian relay networks with arbitrary topology. In this paper, we approximate the capacity of this network within 2 log N bits. We show that two strategies can be used to achieve the information-theoretic cutset upper bound on the capacity of the network up to an additive gap of O(log N) bits, independent of the channel configurations and the SNR's. The first of these strategies is simple partial decode-and-forward. Here, the source node uses a superposition codebook to broadcast independent messages to the relays at appropriately chosen rates; each relay decodes its intended message and then forwards it to the destination over the MAC channel. A similar performance can be also achieved with compress-and-forward type strategies (such as quantize-map-and-forward and noisy network coding) that provide the 1.3 N-bit approximation for general Gaussian networks, but only if the relays quantize their observed signals at a resolution inversely proportional to the number of relay nodes N. This suggest that the rule-of-thumb to quantize the received signals at the noise level in the current literature can be highly suboptimal.

0 citations0 reviewsNo code linkedOpen access
preprint2013arXiv

Generalized Diversity-Multiplexing Tradeoff of Half-Duplex Relay Networks

Diversity-multiplexing trade-off has been studied extensively to quantify the benefits of different relaying strategies in terms of error and rate performance. However, even in the case of a single half-duplex relay, which seems fully characterized, implications are not clear. When all channels in the system are assumed to be independent and identically fading, a fixed schedule where the relay listens half of the total duration for communication and transmits the second half combined with quantize-map-and-forward relaying (static QMF) is known to achieve the full-duplex performance [1]. However, when there is no direct link between the source and the destination, a dynamic decode-and-forward (DDF) strategy is needed [2]. It is not clear which one of these two conclusions would carry to a less idealized setup, where the direct link can be neither as strong as the other links nor fully non-existent. In this paper, we provide a generalized diversity-multiplexing trade-off for the half-duplex relay channel which accounts for different channel strengths and recovers the two earlier results as two special cases. We show that these two strategies are sufficient to achieve the diversity-multiplexing trade-off across all channel configurations, by characterizing the best achievable trade-off when channel state information (CSI) is only available at the receivers (CSIR). However, for general relay networks we show that a generalization of these two schemes through a dynamic QMF strategy is needed to achieve optimal performance.

0 citations0 reviewsNo code linkedOpen access
preprint2013arXiv

Improved Capacity Approximations for Gaussian Relay Networks

Consider a Gaussian relay network where a number of sources communicate to a destination with the help of several layers of relays. Recent work has shown that a compress-and-forward based strategy at the relays can achieve the capacity of this network within an additive gap. In this strategy, the relays quantize their observations at the noise level and map it to a random Gaussian codebook. The resultant capacity gap is independent of the SNR's of the channels in the network but linear in the total number of nodes. In this paper, we show that if the relays quantize their signals at a resolution decreasing with the number of nodes in the network, the additive gap to capacity can be made logarithmic in the number of nodes for a class of layered, time-varying wireless relay networks. This suggests that the rule-of-thumb to quantize the received signals at the noise level used for compress-and-forward in the current literature can be highly suboptimal.

0 citations0 reviewsNo code linkedOpen access